Программа курса, предварительный вариант вопросов к экзамену (2014-04-24) (1133267), страница 2
Текст из файла (страница 2)
См. [1:гл.4,§§6,7].21. Асимптотически наилучший метод синтеза формул в базисе Б0, поведение функцииШеннона для глубины ФАЛ [1:гл.4,§6].22. Асимптотически наилучший метод синтеза КС. См. [1:гл.4,§7].23. Задача синтеза схем для ФАЛ из специальных классов. Асимптотическиоптимальные методы синтеза СФЭ и КС для ФАЛ из некоторых классов.См. [1:гл.4,§§4,5], [10:гл.5].IV. Эквивалентные преобразования управляющих систем (14.IV–25.IV)24.
Эквивалентные преобразования формул с помощью тождеств. Полнота системыосновных тождеств для эквивалентных преобразований формул базиса Б0.См. [1:гл.3,§2].25. Эквивалентные преобразования СФЭ и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентных преобразований формул и схем вразличных базисах, теорема перехода. См. [1:гл.3,§§1,3].26. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательныхи обобщённых тождеств. См. [1:гл.3,§4].27.
Полнота системы основных тождеств. Отсутствие конечной полной системытождеств в классе всех КС. См. [1:гл.3,§5].V. Надёжность и контроль управляющих систем (07.IV, 04.III)28. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов,оценки длины диагностического теста. См. [1:гл.1,§8].29. Самокорректирующиеся КС и методы их построения. Асимптотически наилучшийметод синтеза КС, корректирующих 1 обрыв (1 замыкание).
См. [4:§7], [2: часть III,разд. 2, §1].VI. Некоторые вопросы сложности алгоритмов (12.III, 19.III)30. Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировкатеоремы Кука. Примеры NP-полных проблем. См. [6:§§4.1,4.5-4.8].31. Доказательство теоремы Кука [6:§4.6].45. Типовые задачи к экзаменуI. Задачи на ДНФ1. По заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумматупиковых, все тупиковые ДНФ.1.2.3.4.5.II-III. Задачи на структурное моделирование и синтез схемПо заданной формуле построить подобную ей формулу минимальной глубины.По заданной формуле с поднятыми отрицаниями построить моделирующую еёπ-схему и обратно.По данной каскадной КС построить инверсную каскадную КС.По заданной ФАЛ с помощью простейших методов, метода каскадов или методаШеннона построить реализующую её СФЭ или КС.Оценить сверху и снизу сложность конкретной ФАЛ или сложность самой сложнойФАЛ из заданного множества в заданном классе схем.IV.
Задачи на эквивалентные преобразования1. По заданным эквивалентным формулам или КС построить эквивалентноепреобразование, переводящее их друг в друга с помощью основных тождеств.V. Задачи на самокоррекцию и тесты1. По заданной КС построить эквивалентную ей самокорректирующуюся КС.2. По заданной таблице или КС и списку её неисправностей построить все тупиковыепроверяющие (диагностические) тесты.6. Планы семинарских занятий и даты их проведенияПриведённый ниже график семинарских занятий содержит 7 занятий, проводимыхпо основному расписанию (ОР), и 1 занятие, которое пройдёт в каждой группе подополнительному расписанию (ДР), отличающемуся от ОР чётностью недели ивозможным изменением времени, аудитории и дня его проведения.
Как правило, этидополнительные занятия будут проходить либо во вторник на соответствующей неделев 1250 (вместо лекции С.А. Абрамова), либо в среду.Семинар 1 (гр.1 II нед. – 12.II ОР, гр. I нед. – 19.II ОР)Представление ФАЛ с помощью ДНФ. Сокращённая ДНФ и методы её построенияТеоретический материал [1: с. 27-35], [5: с. 47, 296-298].В классе. Из [5]: гл. I – 2.3 (3); гл.
IX – 2.1 (1,2), 2.5 (1,5), 2.6 (1,5), 2.3 (1,2), 2.2 (1,2),2.9 (1,2).На дом. Из [5]: гл. I – 2.3 (4); гл. IX – 2.1 (3), 2.5 (2,6), 2.6 (2,6), 2.2 (3,4), 2.3 (3,4),2.9 (6).Семинар 2 (гр. II нед. – 26.II ОР, гр. I нед. – 5.III ОР)Ядро и ДНФ Квайна, ДНФ сумма тупиковых. Построение всех тупиковых ДНФ.Теоретический материал [1: с. 38-43, 51-55], [5: с. 301-302].В классе.
Из [5, гл. IX]: 3.1 (1, 5), 3.3 (1, 2 – построить ядро, ДНФ Квайна и ДНФ сумматупиковых), 3.4 (3), 3.6 (1, 4, 7).На дом. Из [5, гл. IX]: 3.1 (4, 6), 3.3 (3, 4 – построить ядро, ДНФ Квайна и ДНФ сумматупиковых), 3.4 (4), 3.6 (3, 6, 8).Семинар 3 (гр. I нед. – 11.III, 12.III ДР, гр. II нед. – 12.III ОР)Тесты для таблиц, тесты для контактных схем.Теоретический материал: [1: с. 65-72, 51-55], [4: с.32-34, 37-38].В классе.
Из [4]: 5.1 (1, 2 – все тупиковые диагностические тесты), 5.1 (3 – всетупиковые проверяющие тесты), 6.2, 6.4, 6.11 (если хватит времени).1Группы I недели – 321, 327, все остальные группы – группы II недели.5На дом. Из [4]: 5.1 (5 – все тупиковые диагностические тесты, 6 – все тупиковыепроверяющие тесты), 6.3, 6.5, 6.14.Семинар 4 (гр. I нед. – 19.III ОР, гр. II нед. – 26.III ОР)Оптимизация подобных формул по глубине, моделирование формул и π-схем.Сложность ФАЛ и методы синтеза схем на основе ДНФ.Теоретический материал [1: с. 86-90, 115-117, 186-210].В классе. Построить формулу минимальной глубины подобную формулеx1 x2 x3 x1 x3 x2 x4 x5 x4 x5 x6 ; по заданной формуле с поднятыми отрицаниямипостроить моделирующую π-схему и обратно.Из [5: гл.
X]: 1.1 (2, 3, 4, ФАЛ 1 – как в классе СФЭ, так и в классе КС, а также ФАЛx1 x2 x3 x1 x2 x4 – в классе КС); 2.4 (1); доказать минимальность некоторых изпостроенных в предыдущих задачах схем.На дом. Из [5: гл. X]: 1.1 (5-7), 2.4 (2); доказать минимальность некоторых изпостроенных в предыдущих задачах схем; построить формулу минимальной глубиныподобную формуле x1 x2 x3 x4 x5 x2 x3 x4 x4 x5 x5 x6 .Семинар 5 (гр. II нед. – 01.IV, 02.IV ДР, гр.
I нед. – 02.IV ОР)Каскадные КС и инверсные КС; метод каскадов для КС и СФЭ. Метод Шеннона.Теоретический материал [1: с. 186-210].В классе. Из [5: гл. X]: 2.13 (1, 7), 2.14 (1), 2.14 (5 – как КС и СФЭ) и т.п. Для заданнойкаскадной КС построить инверсную к ней КС. Разлагая ФАЛ от 3 или 4 БП по всем БП,кроме последней, построить для неё КС по методу Шеннона.На дом. Из [5: гл.
X]: 2.13 (2, 6), 2.14 (2), 2.14 (6 – как КС, так и СФЭ). Для заданнойкаскадной КС построить инверсную к ней КС. Разлагая ФАЛ от 3 или 4 БП по всем БП,кроме последней, построить для неё КС по методу Шеннона.Семинар 6 (гр. II нед. – 09.IV ОР, гр. I нед. – 16.IV ОР)Асимптотически наилучшие методы синтеза, синтез схем для ФАЛ из специальныхклассов. Синтез самокорректирующихся КС.Теоретический материал [1, с. 215-216, 222-224], [4: с. 49-50].В классе. Установить асимптотику функции Шеннона для сложности класса всех ФАЛравных 1 при x1=1 (КС), класса всех самодвойственных ФАЛ (СФЭ), класса всех ФАЛсимметричных по первым трем БП (КС), класса операторов из трёх ортогональныхФАЛ (СФЭ). Из [4]: 7.9 (б), 7.10 (1), 7.13 (по книге [4] 2002 года: 7.7 (б), 7.8 (1),7.11 (1)).На дом.
Установить асимптотику функции Шеннона для сложности класса всех ФАЛ,равных 0 при x1=x2=0 (КС), класса, состоящего из всех тех ФАЛ, у которых любаяподфункция от первых трёх БП линейна, класса операторов из трёх строгоортогональных ФАЛ (СФЭ). Из [4]: 7.9 (в), 7.10 (2), 7.11 (а) (по книге [4] 2002 года:7.7 (в), 7.8 (2), 7.9 (а)).Семинар 7 (гр. II нед. – 23.IV ОР, гр. I нед. – 30.IV ОР)Эквивалентные преобразования формул.Теоретический материал [1: с. 146-161], [4: с. 19].В классе. Из [4]: 3.1 (1), 3.3 (1, 4), 3.8 (1-3), 3.9 (1).На дом. Из [4]: 3.1 (2), 3.3 (3, 6), 3.8 (5-9), 3.9 (2).Семинар 8 (гр. II нед.
– 07.V ОР, гр. I нед. – 14.V ОР)Эквивалентные преобразования КС.Теоретический материал [1: с. 169-185].В классе. Из [4]: 4.1 (2, 4, 6-8), 4.3 (1).На дом. Из [4]: 4.1 (9-12), 4.3 (3).67. ЛитератураОсновная:1. Ложкин С.А. Лекции по основам кибернетики. – М.: МГУ, 2004.
(Электронныеверсиилекцийпоследнихлетможнонайтипоадресуhttp://mk.cs.msu.ru/index.php/Основы_кибернетики_(3-й_поток) )2. Яблонский С.В. Элементы математической кибернетики. – М.: Высшая школа,2007.3. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1986.4. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А.,Селезнёва С.Н. Задачи по курсу «Основы кибернетики». – М.: МГУ, 2011.5. Гаврилов Г.П., Сапоженко А.А.
Задачи и упражнения по дискретнойматематике. – М.: ФИЗМАТЛИТ, 2004.6. Алексеев В.Б. Введение в теорию сложности алгоритмов. – М.: Изд-во МГУ,2002.Дополнительная:7. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов. –М.: МГУ, 2000.8. Дискретная математика и математические вопросы кибернетики. – М.: Наука,1974.9. Ложкин С.А., Марченко А.М. Математические модели и методы синтеза СБИС.(http://mk.cs.msu.ru/images/8/87/Lozhkin-Marchenko-VSLI-models.pdf)10. Лупанов О.Б. Асимптотические оценки сложности управляющих систем.
–М.: МГУ, 1984.11. Нигматулин Р.Г. Сложность булевых функций. – М.: Наука, 1991.8. Особенности организации и контроля аудиторной исамостоятельной работы студентов.Данный вариант курса «Основы кибернетики» является достаточно сложным иобъёмным математическим курсом, усвоение которого требует от студентовполноценной и регулярной как аудиторной, так и самостоятельной работы, чтоневозможно без чёткой организации занятий, строгой дисциплины и систематическогоконтроля. При этом предполагается, что в рамках самостоятельной работы2 студентыне только прорабатывают пройденный материал, но и знакомятся с материаломпредстоящей лекции или семинара.Для контроля за освоением программы курса, как уже говорилось, в течениесеместра проводятся 3 основных (по 2 часа) и, возможно, несколько промежуточных(до 1 часа) тестов (контрольных) на знание и понимание определений, формулировокутверждений и т.п., а также на умение решать задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
