Общая информация о курсе (1133247), страница 2
Текст из файла (страница 2)
См. [1:гл.4,§7].24. Задача синтеза схем для ФАЛ из специальных классов. Асимптотически оптимальныеметоды синтеза СФЭ и КС для ФАЛ из некоторых классов. См. [1:гл.4,§§4,5], [10:гл.5].IV. Надёжность и контроль управляющих систем (20.IV, 24.IV)25. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценкидлины диагностического теста. См.
[1:гл.1,§8].26. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший методсинтеза КС, корректирующих 1 обрыв (1 замыкание). См. [4:§7], [2: ч. III, р. 2, §1].V. Некоторые вопросы сложности алгоритмов. Некоторые модели и классы схем,связанные с программно-аппаратной реализацией алгоритмов (17.III и 24.III; 8.V и 15.V)27.
Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировка теоремыКука. Примеры NP-полных проблем. См. [6:§§4.1,4.5-4.8].28. Доказательство теоремы Кука [6:§4.6].29. Некоторые модификации основных классов схем (BDD, вычисляющие программы и др.),связанные с программной реализацией ФАЛ. См. [1:гл.2,§§4,6,7].30. Реализация автоматных функций схемами из функциональных элементов и элементовзадержки, схемы с «мгновенными» обратными связями. См.
[7:§8], [2: ч. I, р. I, гл. 3, §§2-3].31. Схемы на КМОП-транзисторах и реализация ими простейших функций. Задачилогического и топологического синтеза СБИС, основные этапы и методы их решения.См. [1:гл.2,§7], [9].5. Типовые задачи к экзаменуI.Задачи на ДНФ1.
По заданной ФАЛ построить её сокращённую ДНФ, ДНФ Квайна, ДНФ сумма тупиковых,все тупиковые ДНФ.II. Задачи на структурное моделирование и эквивалентные преобразования2. По заданной формуле построить подобную ей формулу минимальной глубины.3. По заданной формуле с поднятыми отрицаниями построить моделирующую её π-схему иобратно.4. По заданным эквивалентным формулам или КС построить эквивалентное преобразование,переводящее их друг в друга с помощью основных тождеств.III. Задачи на синтез схем5.
По данной каскадной КС построить инверсную каскадную КС.6. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннонапостроить реализующую её СФЭ или КС.7. Оценить сверху и снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛиз заданного множества в заданном классе схем.IV. Задачи на самокоррекцию и тесты. Задачи на NP-полноту8. По заданной КС построить эквивалентную ей самокорректирующуюся КС.9. По заданной таблице или КС и списку её неисправностей построить все тупиковыепроверяющие (диагностические) тесты.10. Доказать NP-полноту языка, связанного с данной проблемой.46.
Планы семинарских занятий и даты их проведенияПриведённый ниже график семинарских занятий содержит 8 занятий, проводимых либо поосновному расписанию (ОР), либо по дополнительному расписанию (ДР), отличающемуся от ОР,как правило, только чётностью недели.
При этом в группах 1 недели1 будет проведено 2, а вгруппах 2 недели – 1 занятие по ДР. По договорённости студентов и преподавателей допускаютсяи иные варианты проведения дополнительных занятий.Семинар 1 (гр. II нед. – 11.II ОР, гр. I нед. – 18.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 нед. – 25.II ОР, гр. I нед. – 4.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 (гр. II нед. – 11.III ОР, гр. I нед. – 18.III ОР)Оптимизация подобных формул по глубине, моделирование формул и π-схем. Эквивалентныепреобразования формул.Теоретический материал [1: с. 86-90, 115-117, 146-161], [4: с. 19].В классе. Из [4]: 3.1 (1), 3.3 (1, 4), 3.8 (1-3), 3.9 (1). Построить формулу минимальной глубиныподобную формуле x1 x2 x3 x1 x3 x2 x4 x5 x4 x5 x6 ; по заданной формуле с поднятымиотрицаниями построить моделирующую π-схему и обратно.На дом. Из [4]: 3.1 (2), 3.3 (3, 6), 3.8 (5-9), 3.9 (2).
Построить формулу минимальной глубиныподобную формуле x1 x2 x3 x4 x5 x2 x3 x4 x4 x5 x5 x6 , промоделировать π-схемой формулуx1 x2 x3 x4 x5 x6 x5 x6 x3 x1 x2 .Семинар 4 (гр. II нед. – 25.III ОР, гр. I нед. – 25.III ДР)Эквивалентные преобразования КС.Теоретический материал [1: с. 169-185].В классе. Из [4]: 4.1 (2, 4, 6-8), 4.3 (1).На дом.
Из [4]: 4.1 (9-12), 4.3 (3).Семинар 5 (гр. I нед. – 01.IV ОР, гр. II нед. – 08.IV ОР)Сложность ФАЛ и методы синтеза схем на основе ДНФ.Теоретический материал [1: с. 186-210].В классе. Из [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); доказать минимальность некоторых из построенных впредыдущих задачах схем.1Группы I недели – 321, 323, 327, все остальные группы – группы II недели.5Семинар 6 (гр.
I нед. – 15.IV ОР, гр. II нед. – 15.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 БП по всем БП, кроме последней,построить для неё КС по методу Шеннона.Семинар 7 (гр. II нед. – 22.IV ОР, гр. I нед. – 22.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 (а)).Семинар 8 (гр.
I нед. – 29.IV ОР, гр. II нед. – 6.V ОР)Тесты для таблиц, тесты для контактных схем.Теоретический материал: [1: с. 65-72, 51-55], [4: с.32-34, 37-38].В классе. Из [4]: 5.1 (1, 2 – все тупиковые диагностические тесты), 5.1 (3 – все тупиковыепроверяющие тесты), 6.2, 6.4, 6.11 (если хватит времени).На дом. Из [4]: 5.1 (5 – все тупиковые диагностические тесты, 6 – все тупиковые проверяющиетесты), 6.3, 6.5, 6.14.7.
ЛитератураОсновная: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.68. Особенности организации и контроля аудиторной исамостоятельной работы студентов.Данный вариант курса «Основы кибернетики» является достаточно сложным и объёмнымматематическим курсом, усвоение которого требует от студентов полноценной и регулярной какаудиторной, так и самостоятельной работы, что невозможно без чёткой организации занятий,строгой дисциплины и систематического контроля. При этом предполагается, что в рамкахсамостоятельной работы2 студенты не только прорабатывают пройденный материал, но изнакомятся с материалом предстоящей лекции или семинара.Для контроля за освоением программы курса, как уже говорилось, в течение семестрапроводятся 4 основных (по 2 часа) и, возможно, несколько промежуточных (до 1 часа) тестов(контрольных) на знание и понимание определений, формулировок утверждений и т.п., а также наумение решать задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
