Лектор: Лепин Виктор Васильевич.

1-й курс, 2-й семестр 1998-1999 учебного года.
Краткое описание курса.

1. Множества и операции над ними.
2. Размещения, перестановки, сочетания.
3. Сочетания с повторениями.
4. Бином Ньютона.
5. Бинарные отношения.
6. Основные понятия теории графов. Геометрическая реализация графов.
7. Способы задания графов. Пример.
8. Планарность графов. Теорема Понтрягина-Куратовского.
9. Деревья (два определения). Теорема Лупанова.
10. Функции алгебры логики. Основы логики.
11. Элементарные булевы функции. Некоторые законы тождества.
12. Понятие формулы.
13. Принцип двойственности.
14. Разложение булевых функций по переменным.
15. Специальные виды формул. Совершенные ДНФ и КНФ.
16. Полином Жегалкина.
17. Понятие полноты. Примеры полных систем. Лемма о двух системах.
18. Замыкание и его свойства. Замкнутые классы.
19. Классы функций, сохраняющих константы.
20. Класс самодвойственных функций. Лемма о несамодвойственной функции.
21. Класс монотонных функций. Лемма о немонотонной функции.
22. Класс линейных функций. Лемма о линейной функции.
23. Лемма о нелинейной функции.
24. Критерий полноты Поста.
25. Следствия из критерия полноты.
26. Базис. Теорема о мощности базиса.
27. Задача минимизации ДНФ. Тривиальный алгоритм нахождения МДНФ.
28. Импликанта, простая импликанта, сокращённая ДНФ.
29. Упрощение ДНФ. Тупиковые ДНФ.
30. Геометрическая модель минимизации ДНФ по совершенной ДНФ. Пример.
31. Построение сокращённой ДНФ по совершенной ДНФ. Пример.
32. Алгоритм построения минимальных ДНФ по сокращённой ДНФ. Пример.
33. Определение схем из функциональных элементов.
34. Проблема синтеза схем из функциональных элементов. Функция Шеннона. Теорема Ляпунова.
35. Соединения и оценка их числа. Тривиальный алгоритм построения минимальных схем.
36. Метод синтеза, основанный на моделировании ДНФ.
37. Метод синтеза, основанный на компьютерной реализации множества всех конъюнкций.
38. Метод каскадов. Пример.
39. Синтез универсального многополюсника для P2(n).
40. Понятие "алгоритм" и необходимость его уточнения. Тезис Тьюринга.
41. Понятие машины Тьюринга. Основной машинный код.
42. Проблема самоприменимости машин Тьюринга. Теорема.
43. Классы числовых функций. Понятие вычислимой функции.
44. Простейшие функции и их вычислимость.
45. Операции суперпозиции, примитивной рекурсии.
46. Операции примитивной рекурсии и минимизации.
47. Классы рекурсивных функций. Простейшие примеры рекурсивных функций.
48. Алфавитное кодирование. Префиксные и разделённые коды. Критерий Маркова.
49. Теорема Крафта.
50. Теорема Макмиллана.
51. Оптимальное кодирование. Теорема о существовании оптимального кода.
52. Свойства оптимальных префиксных кодов.
53. Теорема и метод Хаффмана построения оптимальных кодов.
54. Самокорректирующиеся коды Хэмминга.

• Яблонский С. В. "Введение в Дискретную Математику". Москва, Наука, 1986.
• Нефедов, Осипова. "Курс Дискретной Математики". Москва, Издательство МАИ, 1992.
• Гаврилов Г. П., Сапоженко А. А. "Задачи и Упражнения по Курсу Дискретной Математики". Москва, Наука, 1992.
• Мощенский В. А. "Элементы Комбинаторики и Теории Конечных Графов". Минск, БГУ, 1992.