Oc3-3-09 (Программа курса), страница 2

Доказательство теоремы Кука ([6 : §4.6]).6. Типовые задачи к экзамену.I. Задачи на ДНФ.1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумматупиковых, все тупиковые ДНФ.II. Задачи на эквивалентные преобразования и структурное моделирование.41. По заданным эквивалентным формулам или КС построить эквивалентноепреобразование, переводящее их друг в друга с помощью основных тождеств.2. По заданной формуле построить подобную ей формулу минимальной глубины.3. По заданной формуле с поднятыми отрицаниями построить моделирующую ееπ-схему и обратно.III.

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

Сокращенная ДНФ и методы еепостроения ([5:гл.IX,§2]).2. Ядро и ДНФ Квайна, ДНФ сумма тупиковых. Построение всех тупиковых ДНФ([5:гл.IX,§3]).3. Тесты для таблиц, тесты для КС ([4:§5,6]).4. Эквивалентные преобразования формул. Оптимизация формул по глубине([4:§3]).5.

Моделирование формул и π-схем. Эквивалентные преобразования КС ([4:§4]).6. Сложность ФАЛ и простейшие методы синтеза схем. Метод каскадов и методШеннона ([5:гл.X]).7. Асимптотически наилучшие методы синтеза, синтез схем для ФАЛ изспециальных классов. Самокорректирующиеся КС ([4:§ 7]).8. Предварительный график проведения основных тестов и контрольных работ.Раздел I и вопрос 28: тест №1 – 6 мартаконтрольная работа №1 – 27 марта.Раздел II:тест №2 – 7 апреля,контрольная работа №2 – 24 апреля.Разделы III-IV (без вопроса 28): тест №3 – 5 мая,контрольная работа №3 – 19 мая.5.