ОС-320-328-11 (программа 3 потока, 2011 год) (Программа курса), страница 2

Операция суперпозиции схем и еѐ корректность. Разделительные КС и леммаШеннона ([1: гл.2, §§1,6]).16. Некоторые модификации и частные случаи основных классов схем (каскадныеКС и BDD, КМОП-схемы, вычисляющие программы и др.) ([1: гл.2, §§4,7]).3III.Синтез и сложность управляющих систем.17. Задача синтеза. Простейшие методы синтеза схем и связанные с ними верхниеоценки сложности функций ([1:гл.4,§1]).18. Некоторые нижние оценки сложности ФАЛ, нижние мощностные оценкифункций Шеннона ([1:гл.4,§§2,4]).19. Метод каскадов для КС и СФЭ, примеры его применения. Метод Шеннона([1:гл.4,§3]).20.

Регулярные разбиения единичного куба и моделирование ФАЛ переменными.Синтез схем для некоторых дешифраторов и мультиплексоров ([1:гл.4,§§6,7]).21. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучшийметод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).22. Асимптотически наилучший метод синтеза формул в базисе Б0, поведениефункции Шеннона для глубины ФАЛ ([1:гл.4,§6]).23. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).24. Синтез схем для ФАЛ из специальных классов. Оценки сложностииндивидуальных ФАЛ, минимальность некоторых схем ([1: гл.4, §§2,4,5],[2:часть I, разделы 2,3], [7: §§5-7], [11:гл.8]).25. Реализация автоматных функций схемами из функциональных элементов иэлементов задержки, схемы с «мгновенными» обратными связями ([7: §8], [2:часть I, разд.

I, гл.3, §§2-3]).26. Схемы на КМОП-транзисторах и реализация ими простейших функций. Задачалогического синтеза СБИС ([1:гл.2,§7], [9]).IV.Надежность и контроль управляющих систем.27. Модели ненадежных схем, надежность СФЭ и теорема Неймана. Повышениенадежности СФЭ с помощью элемента голосования ([2: ч.3, раздел 1, §§1-3]).28. Самокорректирующиеся КС и методы их построения.

Асимптотическинаилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([4:§7],[2: ч.3, раздел 2, §1]).29. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов,оценки длины диагностического теста ([1:гл.1,§8]).V.Некоторые вопросы сложности алгоритмов.30. Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировкатеоремы Кука. Примеры NP – полных проблем ([6: §§4.1, 4.5-4.8]).31. Доказательство теоремы Кука ([6 : §4.6]).6.

Типовые задачи к экзамену.I. Задачи на ДНФ.1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумматупиковых, все тупиковые ДНФ.II. Задачи на эквивалентные преобразования и структурное моделирование.1. По заданным эквивалентным формулам или КС построить эквивалентноепреобразование, переводящее их друг в друга с помощью основных тождеств.2.

По заданной формуле построить подобную ей формулу минимальной глубины.3. По заданной формуле с поднятыми отрицаниями построить моделирующую ееπ-схему и обратно.44. По данной каскадной КС построить инверсную каскадную КС.III. Задачи на синтез схем.1. По заданной ФАЛ с помощью простейших методов, метода каскадов илиметода Шеннона построить реализующую ее СФЭ или КС.2.

Оценить сверху или снизу сложность конкретной ФАЛ или сложность самойсложной ФАЛ из заданного множества в заданном классе схем.IV. Задачи на самокоррекцию и тесты.1. По заданной КС построить эквивалентную ей самокорректирующуюся КС.2. По заданной таблице или КС и списку ее неисправностей построить всетупиковые проверяющие (диагностические) тесты.7. План семинарских занятий.1.

Представление ФАЛ с помощью ДНФ. Сокращенная ДНФ и методы ее построения.а) Теоретический материал: [1:с.27-35], [5:с.47, 296-298].б) В классе ([5]): гл. I – 2.3(3); гл. IX – 2.1(1,2), 2.5 (1,5), 2.6 (1), 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), 2.2 (3,4), 2.3 (3,4), 2.9 (6).2. Проводится на лекции 21.II: Ядро и ДНФ Квайна, ДНФ «сумма тупиковых». Построениевсех тупиковых ДНФ.а) Теоретический материал: [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. Тесты для таблиц, тесты для контактных схем.а) Теоретический материал: [1:с.65-72, 51-55], [4:с.29-32, 35-36].б) В классе ([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.4. Эквивалентные преобразования формул. Оптимизация подобных формул по глубине.а) Теоретический материал: [1:с.147-161, 86-90], [4:с.29-32, 35-36].б) В классе ([4, 1]): 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, 1]); 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 подобную ей формулуминимальной глубины.5.

Моделирование формул и π-схем. Эквивалентные преобразования КС.а) Теоретический материал: [1:с.115-117,169-185].б) В классе ([1, 4]): по заданной формуле с поднятыми отрицаниями построитьмоделирующую π-схему и обратно; 4.1 (2,5, 7-9), 4.3 (1).в) На дом ([4]): 4.1 (10-13), 4.3 (3).6. Сложность ФАЛ и простейшие методы синтеза схем. Метод Шеннона.а) Теоретический материал: [1: с. 186-210].б) В классе ([5, гл.

X]):1.1 (2, 3, 4, ФАЛ 1 – как в классе СФЭ, так и в классе КС, а такжеФАЛ x1  x2  x3  x1  x2  x4 – в классе КС); 2.4 (1); доказать минимальность некоторых из5построенных в предыдущих задачах схем; разлагая ФАЛ от 3 или 4 БП по всем БП, кромепоследней, построить для неѐ КС по методу Шеннона.в) На дом ([5, гл. X]): 1.1 (5-7), 2.4 (2); доказать минимальность некоторых из построенных впредыдущих задачах схем; разлагая ФАЛ от 3 или 4 БП по всем БП, кроме последней,построить для неѐ КС по методу Шеннона.7. Каскадные КС, метод каскадов для КС и СФЭ.

Синтез самокорректирующихся КС.а) Теоретический материал: [1: с. 186-210], [4, с. 47-48].б) В классе: [5, гл. X]: 2.13 (1,7), 2.14 (1), 2.14 (5 – как КС и СФЭ) и т.п.; для заданнойкаскадной КС построить инверсную к ней КС; ([4]) 7.7(б), 7.8 (1), 7.11 (1).в) На дом ([5, гл. X]): 2.13 (2,6), 2.14 (2), 2.14 (6 – как КС, так и СФЭ); для заданной каскаднойКС построить инверсную к ней КС; ([4]) 7.7 (в), 7.8 (2),7.9 (а).8.

Асимптотически наилучшие методы синтеза, синтез схем для ФАЛ из специальныхклассов.а) Теоретический материал: [1, с. 215-216, 222-224].б) В классе: установить асимптотику функции Шеннона для сложности класса всех ФАЛравных 1 при x1=1 (КС), класса всех самодвойственных ФАЛ (СФЭ), класса всех ФАЛсимметричных по первым трем БП (КС), класса операторов из трех ортогональных ФАЛ(СФЭ).в) На дом: установить асимптотику функции Шеннона для сложности класса всех ФАЛ,равных 0 при x1=x2=0 (КС), класса, состоящего из всех тех ФАЛ, у которых любаяподфункция от первых трех БП линейна (СФЭ), класса операторов из трехстрогоортогональных ФАЛ.9.

Предварительный график проведения тестов (контрольных работ).Раздел I и вопрос 29:тест №1 – 25 февраля (1 час).тест - контрольная №2 – 18 марта (2 часа).Раздел II:тест №3 – 1 апреля (1 час).тест - контрольная №4 – 15 апреля (2 часа).Разделы III – IV (без вопроса 29): тест №5 – 6 мая (1 час)тест - контрольная №6 – 20 мая (2 часа).10. О проведении экзамена по курсу «Основы кибернетики».Для студентов, имеющих предварительную оценку «5», экзамен проводится в формесобеседования по программе курса на определения, формулировки утверждений и идеи ихдоказательства, методы решения задач. Для студентов, имеющих предварительную оценку«2», экзамен представляет собой письменный тест – контрольную.Все остальные студенты (с предварительной оценкой «3-», «3» и «4») получают билет сдвумя вопросами и одной задачей и после 15-20 минутной подготовки отвечают на негосначала на уровне определений, формулировок утверждений и идей их доказательства, атакже методов решения задач.

Затем студент, по усмотрению экзаменатора, должен раскрытьте или иные детали доказательства утверждений из вопросов билета по конспектам или инымисточникам, а также полностью или частично решить задачу билета в течение выделенногоспециально для этого времени. Студенты, набравшие не менее 80% от суммы баллов позадачам тестов и тестов - контрольных соответствующего раздела, от решения билетнойзадачи данного типа освобождаются. Последний этап экзамена представляет собой описанноевыше собеседование по другим вопросам или задачам программы.В соответствии с общими правилами итоговая экзаменационная оценка не можетпревосходить предварительную оценку больше, чем на один балл.

Студент, который имеетпредварительную оценку «3» или «4» и не претендует на более высокую итоговую оценку,сдает экзамен, как правило, по упрощенной процедуре (в форме собеседования по билету ипрограмме без предварительной подготовки) с целью подтверждения этой оценки.11. Дополнительные лекции (занятия)15, 22, 29 марта, 1435 и 1620, П-6 (вместо лекций С.А. Абрамова)6.