Вопросы по разделу <<Дискретные модели>> 

курса <<Дискретные и вероятностные модели>> 

(магистратура, 1 курс, 2 семестр, 2004/05 учебный год, лектор В. П. Воронин)

1. Функции алгебры логики. Табличное и векторное задание функций. Существенные и фиктивные переменные. Равенство функций. Конгруэнтность функций. Число функций, зависящих от переменный x₁,x₂,...,x_n .

2. Формулы над множествами функций. Эквивалентность формул. Основные эквивалентности.

3. Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме. Теорема о совершенной конъюнктивной нормальной форме.

4. Операция замыкания. Свойства операции замыкания. Полные системы. Примеры полных систем (с доказательством полноты).

5. Теорема Жегалкина о представимости функции алгебры логики полиномом. Алгоритм построения полинома Жегалкина по векторному заданию функции.

6. Замкнутые классы. Замкнутость классов T₀, T₁ и L . Число функций в этих классах, зависящих от переменный x₁,x₂,...,x_n .

7. Двойственные функции. Принцип двойственности. Класс самодвойственных функций, его замкнутость. Число самодвойственных функций, зависящих от переменный x₁,x₂,...,x_n .

8. Отношение предшествования на множестве двоичных наборов. Класс монотонных функций, его замкнутость.   Распознавание   монотонности   булевых функций.

9. Леммы о несамодвойственной функции (L1), о немонотонной функции (L2), о нелинейной функции (L3).

10. Теорема Поста о полноте системы функций алгебры логики.

11. Теорема о максимальном числе функций в базисе алгебры логики. Шефферова функция. Примеры базисов из одной, двух, трех и четырех функций.

12. Критерий шефферовости. Число шефферовых функций, зависящих от переменный x₁,x₂,...,x_n .

13. Предполные классы. Теорема о предполных классах. Результаты Поста о базисах замкнутых классов и числе замкнутых классов (без доказательства).

14. Конечнозначные логики. Примеры k -значных функций. Теорема о существовании конечной полной системы в множестве k-значных функций. Отличия k-значных логик при k3  от алгебры логики (без доказательства).

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

16. Дешифратор. Асимптотика сложности дешифратора. Верхняя оценка сложности реализации произвольной функции алгебры логики.

17. Мультиплексор. Верхняя оценка сложности мультиплексора. Функция Шеннона L(k) . Метод Шеннона. Шифратор. Верхняя оценка сложности шифратора.

18. Асимптотически наилучший метод реализации функций алгебры логики схемами из функциональных элементов.

19. Сумматор. Верхняя оценка сложности сумматора. Вычитатель.

20. Метод Карацубы построения схемы для умножения, верхняя оценка ее сложности.

Литература.

1. Яблонский С. В. Введение в дискретную математику. -М.: Высшая школа, 2003. - 384 с.

2. Алексеев В. Б. Лекции по дискретной математике. -М.: Издательский отдел Факультета ВМиК МГУ им. М. В. Ломоносова, 2004. - 76 с.

3. Лупанов О. Б. Асимптотические оценки сложности управляющих систем. -М.: Изд-во Моск. ун-та, 1984. -138 с.

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