Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Вопросы к экзамену по курсу «ОСНОВЫ КИБЕРНЕТИКИ»

(весенний семестр 2001-2002 уч.года, 3 курс, 3 поток)

лектор - профессор С. А. Ложкин

I. Минимизация дизъюнктивных нормальных форм (ДНФ), некоторые задачи дискретной оптимизации и контроля управляющих систем (УС).

1. Единичный куб и функции алгебры логики (ФАЛ). ДНФ и КНФ, их «геометрическая» интерпретация.

2. Сокращенная ДНФ и методы ее построения.

3. Тупиковые ДНФ, ядро и ДНФ Квайна. Критерий вхождения простых импликант в ДНФ сумма тупиковых.

4. Особенности ДНФ для ФАЛ из некоторых классов (линейных, монотонных и др.). Оценка числа тупиковых ДНФ.

5. Задача о покрытии. Алгоритм построения всех неприводимых подпокрытий конечного множества его подмножествами (всех тупиковых ДНФ).

6. Градиентный алгоритм и оценка длины получаемого покрытия. Примеры его применения.

7. Задача минимизации ДНФ. Оценки ранга и длины ДНФ для почти всех ФАЛ, поведение соответствующих функций Шеннона.

8. Задача контроля управляющих систем (УС), тесты для таблиц. Алгоритм построения всех тупиковых тестов, некоторые оценки длины диагностического теста

II. Основные классы УС, их эквивалентные преобразования и структурное моделирование.

1. Формулы и их эквивалентные преобразования . Построение конечной полной системы тождеств (КПСТ) для формул базиса б₀ ={&,V,-}.

2. Определение схем из функциональных элементов (СФЭ), их модификации и частные случаи. Оценка числа формул и СФЭ.

3. Эквивалентные преобразования СФЭ. Построение КПСТ для СФЭ базиса бо.

4. Определение контактных схем (КС), их модификации и частные случаи. Оценка числа КС.

5. Эквивалентные преобразования КС. Основные тождества, вывод обобщенных тождеств.

6. Полнота системы основных тождеств для КС.

7. Отсутствие КПСТ для класса всех КС.

III. Синтез, сложность и надежность УС.

1. Задача синтеза, сложность ФАЛ и функция Шеннона. Простейшие методы синтеза схем и реализация некоторых ФАЛ.

2. Метод каскадов для КС и СФЭ, примеры его применения.

3. Операция суперпозиции для СФЭ и КС. Разделительные КС, лемма Шеннона.

4. Метод Шеннона и связанные с ним верхние оценки функций Шеннона для СФЭ, КС.

5. Нижние мощностные оценки функции Шеннона.

6. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б.Лупанова для синтеза СФЭ.

7. Регулярные сдвиговые разбиения единичного куба. Асимптотически наилучший метод синтеза формул.

8. Асимптотически наилучший метод синтеза КС

9. Поведение функции Шеннона для глубины ФАЛ.

10. Нижние оценки сложности некоторых ФАЛ. Асимптотика сложности контактного дешифратора.

11. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание).

IV. Структурные модели высокого уровня и некоторые вопросы сложности алгоритмов.

1. Автоматные функции и их реализация схемами из функциональных элементов и элементов задержки. Схемы с "мгновенными" обратными связями.

2. Представление о схемах программ Янова.

3. Полиномиальная сводимость языков. Классы Р и NP, представление о теореме Кука.

4. Окрестностные алгоритмы в задаче минимизации ДНФ. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов.

ТИПОВЫЕ ЗАДАЧИ К ЭКЗАМЕНУ

I. Задачи на ДНФ.

1. По заданной ФАЛ построить ее сокращенную ДНФ, ДНФ Квайна, ДНФ сумма тупиковых, все тупиковые ДНФ.

П. Задачи на тесты.

1. По заданной таблице или КС и списку ее неисправностей построить все тупиковые проверяющие (диагностические) тесты.

III. Задачи на эквивалентные преобразования.

1. По заданным эквивалентным формулам или КС построить эквивалентное преобразование, переводящее их друг в друга с помощью основных тождеств.

2. По заданной формуле с поднятыми отрицаниями построить моделирующую ее пи-схему и обратно.

IV. Задачи на синтез схем.

1. По заданной ФАЛ с помощью простейших методов, метода каскадов или метода Шеннона построить реализующую ее СФЭ или КС.

2. Оценить сверху или снизу сложность конкретной ФАЛ или сложность самой сложной ФАЛ из заданного множества в заданном классе схем.

3. По заданной КС построить эквивалентную ей самокорректирующуюся КС.

ЛИТЕРАТУРА

1. Яблонский С.В. Введение в дискретную математику. М., Наука, 1986. Часть V, гл.1, §§1-6.

2. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. М., МГУ, 1984.

3. Дискретная математика и математические вопросы кибернетики. М., Наука, 1974, с.116-117,136-137, 72-74.

4. Эквивалентные преобразования управляющих систем. Составитель -Яблонский С.В. М., МГУ, 1986.

5. Яблонский С.В. Некоторые вопросы надежности и контроля управляющих систем. Сб. «Математические вопросы кибернетики», М., Наука, 1988, с. 5-26.

6. Нигматуллин Р.Г. Сложность булевых функций. М., Наука, 1991.

7. Алексеев В.Б., Ложкин С. А. Элементы теории графов, схем и автоматов. М., МГУ, 2000.

8. Ложкин С.А. Структурное моделирование и декомпозиция для некоторых классов схем. М., МГУ, 2001.

9. Сапоженко А. А. Некоторые вопросы сложности алгоритмов. М., МГУ, 2001.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов вопросов/заданий