English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

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

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

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. Коды, исправляющие ошибки. Построение кода, исправляющего одну ошибку.

Наверх

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru