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-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru