Основы кибернетики - Список вопросов 2011 (1133253)
Текст из файла
Предварительный список вопросов к экзаменупо курсу «Основы кибернетики»(весенний семестр 2010-2011 уч. года, 320-328 группы,лектор – профессор С.А. Ложкин).I.Минимизация дизъюнктивных нормальных форм и связанные с ней задачи.1. Представление функций алгебры логики (ФАЛ) дизъюнктивными нормальнымиформами (ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ иразложение Шеннона, критерий единственности ДНФ ([1:гл.1,§§2,5]).2.
Сокращенная ДНФ и способы ее построения ([1:гл.1,§3]).3. Тупиковая ДНФ, ядро и ДНФ пересечение тупиковых. ДНФ Квайна, критерийвхождения простых импликант в тупиковые ДНФ и его локальность([1:гл.1,§4]).4. Особенности ДНФ монотонных ФАЛ. Функция покрытия, таблица Квайна ипостроение всех тупиковых ДНФ ([1:гл.1,§§5,6]).5. Градиентный алгоритм и оценка длины градиентного покрытия, лемма о«протыкающих» наборах. Использование градиентного алгоритма дляпостроения ДНФ ([1:гл.1,§6]).6. Задача минимизации ДНФ. Поведение функций Шеннона и оценки типичныхзначений для ранга и длины ДНФ ([1:гл.1,§7]).7. Алгоритмические трудности минимизации ДНФ и нижние оценкимаксимальных значений некоторых связанных с ней параметров – длинысокращенной ДНФ, числа тупиковых ДНФ ([1:гл.1,§§,3,7]). ТеоремаЮ.И. Журавлева о ДНФ сумма минимальных ([1:гл.1,§5]).II.Основные классы дискретных управляющих систем.
Оценка числа схем, ихструктурные представления и эквивалентные преобразования.8. Формулы, задача эквивалентных преобразований на примере формул ([1: гл.1,§1, гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).9. Полнота системы основных тождеств для эквивалентных преобразованийформул базиса Б0 ([1:гл.3,§2]).10. Задание формул графами, схемы из функциональных элементов (СФЭ).
Оценкачисла формул и СФЭ в базисе Б0={&,۷,[( }ך1:гл.2,§§2,3]).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]).1III.Синтез и сложность управляющих систем.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. По заданной формуле с поднятыми отрицаниями построить моделирующую ееπ-схему и обратно.24.
По данной каскадной КС построить инверсную каскадную КС.III. Задачи на синтез схем.1. По заданной ФАЛ с помощью простейших методов, метода каскадов илиметода Шеннона построить реализующую ее СФЭ или КС.2. Оценить сверху или снизу сложность конкретной ФАЛ или сложность самойсложной ФАЛ из заданного множества в заданном классе схем.IV.
Задачи на самокоррекцию и тесты.1. По заданной КС построить эквивалентную ей самокорректирующуюся КС.2. По заданной таблице или КС и списку ее неисправностей построить всетупиковые проверяющие (диагностические) тесты.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}
