Информационные материалы

Курс «Элементы теории дискретныхуправляющих систем» для бакалавров(интегрированных магистров)направления 01400 «Прикладная математика иинформатика» профиля «Математическиеметоды обработки информации и принятиярешений» кафедры математическойкибернетики1. Общая информация(учебная нагрузка, формы контроля и др.)Курс является обязательным для всех бакалавров (интегрированных магистров)кафедры математической кибернетики.Он читается в 7 семестре в объёме 36 часов лекций, и завершается экзаменом, накоторый выносятся как теоретические вопросы, так и задачи, изложенные на лекциях.В разделах 2-6 данного описания приводится подробная информация о содержаниикурса, программах и планах его изучения в 2016-2017 уч.

году, методическихматериалах, а в разделах 7 и 8 – об особенностях организации учебного процесса,формах и сроках проведения контрольных мероприятий.В соответствии с этими планами в течение семестра проводятся 2 основные (на 2часа) и, возможно, несколько промежуточных (до 1 часа) тестов (контрольных). Порезультатам указанных тестов (контрольных) с учётом посещаемости студентов, ихработы на лекциях и семинарах, а также самостоятельной работы (см.

раздел 7)выставляется предварительная оценка, которая играет существенную роль приформировании окончательной оценки на экзамене (см. раздел 8).Чтение курса обеспечивается кафедрой математической кибернетики, лектор 20162017 уч. года – профессор Ложкин С.А. (lozhkin@cs.msu.su).2. АннотацияКурс «Элементы теории дискретных управляющих систем» читается параллельнос курсом «Основы кибернетики» и является дополнением последнего курса. Онпосвящён более глубокому изучению ряда моделей, методов и результатов теориидискретных управляющих систем (УС), связанных с задачей схемной или структурнойреализации дискретных функций и алгоритмов, а также некоторых вопросов контроляУС. В нём рассматриваются дополнительные вопросы как массового так ииндивидуального синтеза УС. В программу курса входят, в частности, результаты обасимптотике функции Шеннона для сложности формул, схем из функциональныхэлементов, контактных и итеративно-контактных схем в произвольном базисе, а такжео поведении функции Шеннона для глубины функций алгебры логики (ФАЛ) впроизвольном базисе.

Изучается сложность реализации ряда ФАЛ и систем ФАЛ,встречающихся в приложениях, в некоторых классах УС.В рамках модели контактных схем излагаются некоторые вопросы контроля УС,связанные, в частности, с построением полного диагностического и полногопроверяющего тестов.13. ПрограммаАсимптотически наилучшие методы синтеза формул, схем изфункциональных элементов (СФЭ) и схем проводящего типа впроизвольном базисеНекоторые модификации контактных схем (КС) итеративные КС (ИКС), верхниеоценки числа проводящих схем различных типов, формул и СФЭ в произвольномбазисе, нижние мощностные оценки соответствующих функций Шеннона.Асимптотически наилучшие методы синтеза КС, ИКС, формул и СФЭ в произвольномбазисе.II. Синтез схем для некоторых специальных ФАЛ и оценки их сложностиНижние оценки сложности реализации «больших» систем ФАЛ в классе КС,асимптотика сложности универсального контактного многополюсника.

Методзабивающих констант и незабиваемые множества переменных. Асимптотикасложности мультиплексора в некоторых классах схем, сложность линейной ФАЛ вклассах π-схем, КС и самокорректирующихся КС, СФЭ.III. Некоторые вопросы контроля контактных схемПостроение полного диагностического или проверяющего теста для КС.I.4. Предварительный список вопросов к экзамену по курсу«Элементы теории дискретных управляющих систем»(осенний семестр 2016-2017 уч. года; 418 группа).Асимптотически наилучшие методы синтеза схем в некоторых моделяхдискретных управляющих систем1. Формулы и СФЭ в произвольном базисе, функционалы их сложности и основныесоотношения между этими функционалами.

Верхняя оценка числа формул и СФЭ.См. [1:гл.2,§4], [2:гл.1,§2].2. Некоторые модификации контактных схем (КС), итеративные КС (ИКС). Верхниеоценки числа схем контактного типа. См. [1:гл.2,§7], [2:гл.1,§1].3. Нижние мощностные оценки функции Шеннона для сложности схем контактноготипа, для сложности и задержки формул и СФЭ в произвольном базисе.См. [1:гл.4,§4], [2:гл.1,§§1,2].4. Универсальные множества ФАЛ и их построение.

Асимптотически наилучшиеметоды синтеза СФЭ в произвольном базисе и ИКС. См. [1:гл.4,§8], [2:гл.1,§§3-5].5. Асимптотически наилучший метод синтеза КС и формул в произвольном базисе.См. [1:гл.4,§8], [2:гл.1,§6].6. Поведение функции Шеннона для задержки ФАЛ в произвольном базисе.Построение СФЭ асимптотически оптимальных как по сложности, так и позадержке.

См. [2:гл.1,§7], [10:§21].II. Синтез схем для некоторых специальных ФАЛ и систем ФАЛ, оценки ихсложности7. Синтез схем для некоторых дешифраторов и мультиплексоров, оценки ихсложности. См. [1:гл.4,§7].8. Реализация «больших» систем ФАЛ в классе КС и нижние оценки её сложности.Асимптотикасложностиуниверсальногоконтактногомногополюсника.См.

[2:гл.2,§1].9. Метод забивающих констант и незабиваемые множества переменных ФАЛ.Асимптотика сложности мультиплексора в некоторых классах схем.См. [2:гл.2,§2].10. Теорема Храпченко. Сложность реализации линейной и некоторых других ФАЛ вклассе π-схем. См. [3:часть I, разд. 2,§1; разд. 3,§2], [2:гл.2,§5].11. Сферические ФАЛ. Сложность линейной и других ФАЛ в классе КС исамокорректирующихся КС. См. [3:часть III, разд. 3,§1], [2:гл.2,§4].12. Сложность реализации линейной ФАЛ в классе СФЭ. См [2:гл.II,§2], [11:гл.8,§2].I.2III. Некоторые вопросы контроля контактных схем13. Полный диагностический тест для контактных схем.

См. [7:с.132-134].14. Верхняя оценка длины полного проверяющего теста для контактных схем.См. [7:с.135-142].15. Верхняя константная оценка функции Шеннона длины единичного проверяющеготеста при моделировании булевой функции двухполюсными контактными схемамис фиксированной входной избыточностью. См.

[12:лемма 1 и теорема 4].5. Типовые задачи к экзамену1.2.3.4.1.2.3.4.1.I. Задачи на асимптотически наилучшие методы синтезаПолучение верхних оценок числа схем из заданного класса и установление нижнихмощностных оценок соответствующих функций Шеннона.Построение универсальных множеств ФАЛ.Нахождение обобщённого разложения заданной ФАЛ.Получение асимптотически точных верхних оценок функций Шеннона длясложности схем из заданного класса.II.

Задачи на индивидуальную сложность ФАЛПолучение нижних оценок сложности систем ФАЛ в классе КС, установление еёасимптотического поведения.Получение нижних оценок сложности ФАЛ с помощью метода забивающихконстантинезабиваемыхмножествпеременных,установлениееёасимптотического поведения.Получение нижних оценок сложности ФАЛ в классе КС и самокорректирующихсяКС на основе их сферичности, установление её асимптотического поведения.Получение нижних оценок сложности ФАЛ в классе π-схем с помощью теоремыХрапченко, установление её асимптотического поведения.III.

Задачи на тестыПостроить для заданной КС полный (единичный) проверяющий (диагностический)тест.6. ЛитератураОсновная:1. Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004.2. Ложкин С.А. Дополнительные главы кибернетики и теории управляющихсистем. (Электронные версии последних лет можно найти по адресу http://mk.cs.msu.ru/index.php/Дополнительные_главы_кибернетики_и_теории_управляющих_систем )3. Яблонский С.В. Элементы математической кибернетики.

– М.: Высшая школа,2007.4. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986.5. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А.,Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011.6. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретнойматематике. – М.: ФИЗМАТЛИТ, 2004.7. Редькин Н.П. Надежность и диагностика схем.

М: МГУ, 1992. 192 с.Дополнительная:8. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. –М.: МГУ, 2000.9. Дискретная математика и математические вопросы кибернетики. – М.: Наука,1974.10. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. –М.: МГУ, 1984.11. Нигматулин Р.Г. Сложность булевых функций. – М.: Наука, 1991.12. Романов Д.С., Романова Е.Ю. О единичных проверяющих тестах для схемпереключательного типа // Известия высших учебных заведений. Поволжскийрегион. Физико-математические науки. 2015, №1. С.

5-23.37. Особенности организации и контроля аудиторной исамостоятельной работы студентов.Данный курс является достаточно сложным и объёмным математическим курсом,усвоение которого требует от студентов полноценной и регулярной как аудиторной, таки самостоятельной работы, что невозможно без чёткой организации занятий, строгойдисциплины и систематического контроля. При этом предполагается, что в рамкахсамостоятельной работы1 студенты не только прорабатывают пройденный материал, нои знакомятся с материалом предстоящей лекции или семинара.Для контроля за освоением программы курса, уже говорилось, в течение семестрапроводятся 2 основных (по 2 часа) и, возможно, несколько промежуточных (до 1 часа)тестов (контрольных) на знание и понимание определений, формулировок утвержденийи т.п., а также на умение решать задачи. Планируется, кроме того, осуществлятьсистематический (выборочный) контроль за работой студентов как на семинарах, так ина лекциях.