Экзамен по кибернетике

Список вопросов к экзамену
по курсу «Основы кибернетики»
(весенний семестр 2009-2010 уч. года, 320-328 группы,
лектор – профессор С.А. Ложкин).

1. Минимизация дизъюнктивных нормальных форм и связанные с ней задачи.

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]).

1. Основные классы дискретных управляющих систем. Оценка числа схем, их структурные представления и эквивалентные преобразования.

1. Формулы, задача эквивалентных преобразований на примере формул ([1: гл.1, §1, гл.3,§1]). Оптимизация подобных формул по глубине ([1:гл.2§2]).

2. Полнота системы основных тождеств для эквивалентных преобразований формул базиса Б₀ ([1:гл.3,§2]).

3. Задание формул графами, схемы из функциональных элементов (СФЭ). Оценка числа формул и СФЭ в базисе Б₀={&,۷,ך} ([1:гл.2,§§2,3]).

4. Эквивалентные преобразования СФЭ, моделирование эквивалентных преобразований формул в классе СФЭ. Моделирование эквивалентных преобразований в различных базисах, теорема перехода. ([1:гл.3, §§1,3]).

5. Контактные схемы (КС) и π-схемы, оценка их числа. Особенности функционирования многополюсных КС ([1:гл.2,§§5,6]).

6. Эквивалентные преобразования КС. Основные тождества, вывод вспомогательных и обобщенных тождеств ([1:гл.3,§4]).

7. Полнота системы основных тождеств. Отсутствие конечной полной системы тождеств в классе всех КС ([1:гл.3,§5]).

8. Операция суперпозиции схем и её корректность. Разделительные КС и лемма Шеннона ([1: гл.2, §§1,6]).

9. Некоторые модификации и частные случаи основных классов схем (каскадные КС и BDD, вычисляющие программы и др.) ([1: гл.2, §§4,7]).

1. Синтез и сложность управляющих систем.

1. Задача синтеза. Простейшие методы синтеза схем и связанные с ними верхние оценки сложности функций ([1:гл.4,§1]).

2. Простейшие нижние оценки сложности ФАЛ, нижние мощностные оценки функций Шеннона ([1:гл.4,§§2,4]).

3. Метод каскадов для КС и СФЭ, примеры его применения. Метод Шеннона ([1:гл.4,§3]).

4. Регулярные разбиения единичного куба и моделирование ФАЛ переменными. Синтез схем для некоторых дешифраторов и мультиплексоров ([1:гл.4,§§6,7]).

5. Дизъюнктивно-универсальные множества ФАЛ. Асимптотически наилучший метод О.Б. Лупанова для синтеза СФЭ в базисе Б₀ ([1:гл.4,§5]).

6. Асимптотически наилучший метод синтеза формул в базисе Б_0, поведение функции Шеннона для глубины ФАЛ ([1:гл.4,§6]).

7. Асимптотически наилучший метод синтеза КС ([1:гл.4,§7]).

8. Синтез схем для ФАЛ из специальных классов. Оценки сложности индивидуальных ФАЛ, минимальность некоторых схем ([1: гл.4, §§2,4,5], [2:часть I, разделы 2,3], [7: §§5-7], [11:гл.8]).

9. Реализация автоматных функций схемами из функциональных элементов и элементов задержки, схемы с «мгновенными» обратными связями ([7: §8], [2: часть I, разд. I, гл.3, §§2-3]).

1. Надежность и контроль управляющих систем.

1. Самокорректирующиеся КС и методы их построения. Асимптотически наилучший метод синтеза КС, корректирующих 1 обрыв (1 замыкание) ([4:§7], [2: ч.3, раздел 2, §1]).

2. Задача контроля схем и тесты для таблиц. Построение всех тупиковых тестов, оценки длины диагностического теста ([1:гл.1,§8]).

1. Некоторые вопросы сложности алгоритмов.

1. Полиномиальная сводимость языков. Классы P и NP, NP-полнота, формулировка теоремы Кука. Примеры NP – полных проблем ([6: §§4.1, 4.5-4.8]).

2. Доказательство теоремы Кука ([6 : §4.6]).

Типовые задачи к экзамену.

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

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

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

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

2. По заданной формуле построить подобную ей формулу минимальной глубины.

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

4. По данной каскадной КС построить инверсную каскадную КС.

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

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

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

IV. Задачи на самокоррекцию и тесты.

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

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

Литература.

Основная:

1. Ложкин С.А. Лекции по основам кибернетики. М.: МГУ, 2004.

2. Яблонский С.В. Элементы математической кибернетики. М.: Высшая школа, 2007.

3. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1986.

4. Алексеев В.Б., Вороненко А.А., Ложкин С.А., Романов Д.С., Сапоженко А.А., Селезнева С.Н. Задачи по курсу «Основы кибернетики». М.: МГУ, 2002.

5. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: ФИЗМАТЛИТ, 2004.

6. Алексеев В.Б. Введение в теорию сложности алгоритмов. М.: Изд-во МГУ, 2002.

Дополнительная:

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

2. Дискретная математика и математические вопросы кибернетики. М.: Наука, 1974.

3. Ложкин С.А., Марченко А.М. Математические вопросы проектирования СБИС. http://mathcyb.cs.msu.su (учебники)

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

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

3