Перейти к полному списку специальных курсов кафедры

Программа годового спецкурса "Введение в дискретную математику и математическую кибернетику"

1. Понятие функции, существенной переменной, равенства функций. Понятия формулы, суперпозиции, замыкания, замкнутого множества функций. Проблемы выразимости, полноты, базисов, структуры замкнутых классов.

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

3. Класс Р2. Теорема Жегалкина.

4. Замкнутость классов монотонных, линейных, самодвойственных, сохраняющих константу функций.

5. Свойства немонотонной, несамодвойственной и нелинейной функции из Р2.

6. Теорема Поста о полноте в Р2.

7.Понятие о теореме Поста для замкнутых классов в Р2.

8.Лемма Яблонского для Рк.

9. Лемма о 2-полноте существенной и всех одноместных функций Pk.

10.Лемма о подъеме значности системы функций из Pk за счет существенной функции и всех функций с не более, чем i значениями

11.Теорема Слупецкого.

12.R-множества.Лемма о замкнутости классов сохранения R-множеств.

13.Лемма о неполноте замкнутого класса, после добавления к нему селекторов.

14.Теорема Кузнецова.

15.Теорема Янова.

16.Теорема Мучника.

17.Теорема о представимости функций в Pk полиномами по модулю k.

18. Задача минимизации булевских функций. Оценка шенноновской сложности для м.д.н.ф.

19. Алгоритм Блейка и его обоснование.

20. М.д.н.ф. монотонной и линейной функций.

21. Т.д.н.ф. Теорема о поглощении элементарных конъюнкций.

22. Критерий о вхождении конъюнкции в д.н.ф. типа ∩ Т(f).

23. Критерий вхождения конъюнкции в д.н.ф. типа ∑ T(f).

24. Отсутствие локального критерия вхождения конъюнкции в д.н.ф. типа ∑ M(f).

25. Основные понятия теории кодирования. Теорема Маркова. Алгоритм распознавания однозначности декодирования.

26. Оптимальное кодирование. Теорема Мак-Миллана и теорема Крафта.

27. Редукция источника. Процедура оптимального кодирования Хаффмена.

28. Коды, исправляющие ошибки. Построение кода, исправляющего одну ошибку.

Наверх