Основы Кибернетики, экзаменационные вопросы 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].

[править] Типовые задачи к экзамену

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