Основы кибернетики - Список вопросов 2010 (1133251)
Текст из файла
Список вопросов к экзамену по курсу «Основы кибернетики»(весенний семестр 2008-2009 уч. года, 320-328 группы,лектор – профессор С.А. Ложкин).I.Минимизация дизъюнктивных нормальных форм и связанные с ней задачи.1. Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальнымиформами (ДНФ) и его «геометрическая» интерпретация, основные виды ДНФ(совершенная, тупиковая, минимальная). Ядро и ДНФ пересечение тупиковых,критерий единственности ДНФ ([1:гл.1,§§2,4]).2. Сокращенная ДНФ и способы ее построения ([1:гл.1,§3]).3.
ДНФ Квайна и ДНФ сумма тупиковых (∑Т). Критерий вхождения простыхимпликант в ДНФ ∑Т , его локальность ([1:гл.1,§4]). Теорема Ю.И. Журавлева оДНФ сумма минимальных ([1:гл.1,§5]).4. Особенности ДНФ монотонных ФАЛ. Функция покрытия, таблица Квайна ипостроение всех тупиковых ДНФ ([1:гл.1,§§5,6]).5. Градиентный алгоритм и оценка длины градиентного покрытия, лемма о«протыкающих» наборах. Использование градиентного алгоритма дляпостроения ДНФ ([1:гл.1,§6]).6. Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичныхзначений для ранга и длины ДНФ ([1:гл.1,§7]).7.
Алгоритмические трудности минимизации ДНФ и оценки максимальныхзначений некоторых связанных с ней параметров – длины сокращенной ДНФ,числа тупиковых ДНФ ([1:гл.1, §§ 1,3,7]).II.Основные классы дискретных управляющих систем. Оценка числа схем, ихструктурные представления и эквивалентные преобразования.8. Задание формул деревьями, схемы из функциональных элементов (СФЭ).Оценка числа формул и СФЭ в базисе Б0={&,٧,[( }ך1:гл.2,§§2,3]).9. Задача эквивалентных преобразований на примере формул ([1:гл.3,§1]).Оптимизация подобных формул по глубине ([1:гл.2§2]).10.
Полнота системы основных тождеств для эквивалентных преобразованийформул базиса Б0 ([1:гл.3,§2]).11. Эквивалентныепреобразования СФЭ,моделированиеэквивалентныхпреобразований формул в классе СФЭ. Моделирование эквивалентныхпреобразований в различных базисах, теорема перехода. ([1:гл.3, §§1,3]).12. Контактные схемы (КС) и π-схемы, оценка их числа. Особенностифункционирования многополюсных КС ([1:гл.2,§§5,6]).13. ЭквивалентныепреобразованияКС.Основныетождества,выводвспомогательных и обобщенных тождеств ([1:гл.3,§4]).14. Полнота системы основных тождеств. Отсутствие конечной полной системытождеств в классе всех КС ([1:гл.3,§5]).15. Операция суперпозиции схем и её корректность.
Разделительные КС и леммаШеннона ([1: гл.2, §§1,6]).16. Некоторые модификации и частные случаи основных классов схем (каскадныеКС, BDD, КМОП-схемы, вычисляющие программы и др.) ([1: гл.2, §§4,7]).III.Синтез и сложность управляющих систем.117. Задача синтеза. Простейшие методы синтеза схем и оценки сложности функций,нижние мощностные оценки функций Шеннона ([1:гл.4,§§1,2,4]).18. Метод каскадов для КС и СФЭ, примеры его применения.
Метод Шеннона([1:гл.4,§3]).19. Регулярные разбиения единичного куба и моделирование ФАЛ переменными.Оценкисложностинекоторыхдешифраторовимультиплексоров([1:гл.4,§§6,7]).20. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучшийметод О.Б. Лупанова для синтеза СФЭ в базисе Б0 ([1:гл.4,§5]).21.
Асимптотически наилучший метод синтеза формул в базисе Б0, поведениефункции Шеннона для глубины ФАЛ ([1:гл.4,§6]).22. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).23. Синтез схем для ФАЛ из специальных классов. Оценки сложностииндивидуальных ФАЛ, минимальность некоторых схем ([1: гл.4, §§2,4,5], [7:§7]).24. Реализация автоматных функций схемами из функциональных элементов иэлементов задержки, схемы с «мгновенными» обратными связями ([7: §8], [2:часть I, разд. I, гл.3, §3]).IV.Надежность и контроль управляющих систем.25. Самокорректирующиеся КС и методы их построения. Асимптотическинаилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([4:§7],[2: ч.3, раздел 2, §1]).26.
Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов,оценки длины диагностического теста ([1:гл.1,§8]).V.Некоторые вопросы сложности алгоритмов.27. Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировкатеорема Кука. Примеры NP – полных проблем ([6: §§4.1, 4.5-4.8]).28. Доказательство теоремы Кука ([6 : §4.6]).Типовые задачи к экзамену.I. Задачи на ДНФ.1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумматупиковых, все тупиковые ДНФ.II. Задачи на эквивалентные преобразования и структурное моделирование.1. По заданным эквивалентным формулам или КС построить эквивалентноепреобразование, переводящее их друг в друга с помощью основных тождеств.2.
По заданной формуле построить подобную ей формулу минимальной глубины.3. По заданной формуле с поднятыми отрицаниями построить моделирующую ееπ-схему и обратно.4. По данной каскадной КС построить инверсную каскадную КС.III. Задачи на синтез схем.1. По заданной ФАЛ с помощью простейших методов, метода каскадов илиметода Шеннона построить реализующую ее СФЭ или КС.22. Оценить сверху или снизу сложность конкретной ФАЛ или сложность самойсложной ФАЛ из заданного множества в заданном классе схем.IV. Задачи на самокоррекцию и тесты.1. По заданной КС построить эквивалентную ей самокорректирующуюся КС.2.
По заданной таблице или КС и списку ее неисправностей построить всетупиковые проверяющие (диагностические) тесты.Литература.Основная:1. Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.2. Яблонский С.В. Элементы математической кибернетики. М.: Высшая школа,2007.3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.4. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., СапоженкоА.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики». М.: МГУ,2002.5. Гаврилов Г.П., Сапоженко А.А.
Задачи и упражнения по дискретнойматематике. М.: ФИЗМАТЛИТ, 2004.6. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд-во МГУ,2002.Дополнительная:7. Алексеев В.Б., Ложкин С.А. Элементы теории графов, схем и автоматов.М.: МГУ, 2000.8. Дискретная математика и математические вопросы кибернетики. М.: Наука,1974.9. Лупанов О.Б.
Асимптотические оценки сложности управляющих систем.М.: МГУ, 1984.3.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
