Основы Кибернетики, экзаменационные вопросы 3 потока
Материал из eSyr's wiki.
[править] Информация о курсе
- какого цвета учебник? — розового
- как называется курс? — «Основы кибернетики»
- как зовут лектора? — профессор Сергей Андреевич Ложкин (http://mathcyb.cs.msu.su/staff/lozhkin.php)
[править] Вопросы к экзамену по курсу «Основы кибернетики»
- взято с сайта кафедры математической кибернетики (весенний семестр 2006—2007 учебного года, 320-328, 341 группы)
- I. Представление функций с помощью дизъюнктивных нормальных форм и связанные с ним задачи.
- 1. Единичный куб и функции алгебры логики (ФАЛ). Дизъюнктивные (конъюнктивные) нормальные формы, связанные с ними представления и разложения ФАЛ ([1:гл.1,§2]).
- 2. Сокращенная дизъюнктивная нормальная форма (ДНФ) и способы ее построения ([1:гл.1,§3]).
- 3. Тупиковые и минимальные ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в тупиковые ДНФ, его локальность ([1:гл.1,§4]).
- 4. Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Теорема Ю.И. Журавлева о ДНФ сумма минимальных ([1:гл.1,§5]).
- 5. Функция покрытия, таблица Квайна и построение всех тупиковых ДНФ. Градиентный алгоритм и оценка длины градиентного покрытия ([1:гл.1,§6]).
- 6. Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичных значений для ранга и длины ДНФ ([1:гл.1,§7]).
- 7. Алгоритмические трудности минимизации ДНФ и оценки максимальных значений некоторых связанных с ней параметров ([1:гл.1,§§2,3,7]).
- 8. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1:гл.1,§8]).
- II. Основные классы дискретных управляющих систем. Оценка числа схем, их структурные представления и эквивалентные преобразования.
- 9. Задание формул деревьями, схемы из функциональных элементов (СФЭ). Оценка числа формул и СФЭ в базисе Б0={&,۷,ך} ([1:гл.2,§§2,3]).
- 10. Задача эквивалентных преобразований на примере формул ([1:гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).
- 11. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б0 ([1:гл.3,§2]).
- 12. Эквивалентные преобразования СФЭ, моделирование эквивалентных преобразований формул в классе СФЭ. Моделирование эквивалентных преобразований в различных базисах, теорема перехода. ([1:гл.3,§1,3]).
- 13. Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС ([1:гл.2,§§5,6]).
- 14. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств ([1:гл.3,§4]).
- 15. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС ([1:гл.3,§5]).
- 16. Операция суперпозиции и её корректность для некоторых типов схем. Разделительные КС, лемма Шеннона ([1:гл.2,§§1,3,6]).
- III. Синтез, сложность и надежность управляющих систем.
- 17. Задача синтеза. Простейшие методы синтеза схем и оценки сложности функций ([1:гл.4,§§1,2]).
- 18. Метод каскадов для КС и СФЭ, примеры его применения ([1:гл.4,§3]).
- 19. Метод Шеннона и связанные с ним верхние оценки функций Шеннона ([1: гл.4,§3]).
- 20. Нижние мощностные оценки функций Шеннона ([1:гл.4,§4]).
- 21. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).
- 22. Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Оценки сложности некоторых дешифраторов и мультиплексоров ([1:гл.4,§§6,7]).
- 23. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).
- 24. Асимптотически наилучший метод синтеза формул в базисе Б0, поведение функции Шеннона для глубины ФАЛ ([1:гл.4,§6]).
- 25. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([2:§7], [11:§2.1]).
- 26. Задача синтеза схем для ФАЛ из специальных классов и индивидуальных ФАЛ. Методы получения верхних и нижних оценок сложности, минимальность некоторых схем ([8], [9:§2]).
- IV. Некоторые прикладные вопросы теории сложности. Структурные модели высокого уровня.
- 27. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями ([4:§8]). Схемы на КМОП-транзисторах и реализация ими простейших функций. ([1:гл.II,§7], [6]).
- 28. Вычисляющие и адресующие программы, представление о логических схемах программ. ([1:гл.2§§4,7].
[править] Типовые задачи к экзамену
- Задачи на ДНФ
- По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.
- Задачи на тесты
- По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты.
- Задачи на эквивалентные преобразования и структурное моделирование
- По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.
- По заданной формуле построить подобную ей формулу минимальной глубины.
- По заданной формуле с поднятыми отрицаниями построить моделирующую ее π-схему и обратно.
- Задачи на синтез схем
- По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.
- Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.
- По заданной КС построить эквивалентную ей самокорректирующуюся КС.