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

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

Программа спецкурса "Дискретные системы и процессы"

Руководитель курса: проф. Бабин Д.Н.
Время и место проведения:   в ауд.  .

Программа 2021 года: 2021_discrete_systems.pdf

.

 

Архив: предыдущая версия программы:

1 семестр

  1. Графы. Оценки для семейств графов. Эйлеровы циклы, критерий существования. Теорема Шеннона о реберной раскраске графов.
  2. Критерий Понтрягина-Куратовского для плоской реализации графов. Теорема о вершинной раскраске плоских графов.
  3. Алгоритм вычисления расстояний между вершинами взвешенного графа. Теорема Форда-Фолкерсона о потоке через сеть.
  4. Алфавитное кодирование. Теорема Маркова об однозначности декодирования. Префиксные коды. Неравенство Макмиллана.
  5. Оптимальное кодирование. Коды Хафмана. Самокорректирующиеся коды. Kоды Хемминга.
  6. Дискретная оптимизация. Алгоритм построения минимального остовного дерева. Задачи о коммивояжере и рюкзаке.
  7. Понятие автомата. Абстрактные автоматы. Способы задания автоматов: информационные деревья, канонические уравнения, диаграммы Мура.
  8. Отличимость состояний и автоматов. Теоремы Мура об отличимости эксперементами. Теорема Мура о длине установочного эксперимента.
  9. Теорема Клини о представлении событий.
  10. Теорема Мак-Ноттона о представлении сверхсобытий.
  11. Структурные автоматы. Oперации суперпозиции и композиции. Операторы С- и К- замыкания. Проблема полноты и выразимости. Теорема Бабина об С-полноте двуместных автоматов. Теорема Кудрявцева о континуальности критериальных систем для К-полноты автоматов.
  12. Теорема Кратко об алгоритмической неразрешимости К-полноты для автоматов. Теорема Летичевского о разрешимости К-полноты для специальных систем автоматов.
  13. Геометрический, вероятностный и комбинаторно-логический подходы в распознавании образов. Перцептрон, теорема Новикова.
  14. Понятие тупикового теста пары таблиц. Алгоритм голосования по тестам.

Литература

  1. Яблонский С.В. Введение в дискретную математику. М.: Наука, 1979
  2. Кудрявцев В.Б., Гаврилов Г.П., Яблонский С.В., Функции алгебры логики и классы Поста. Наука, М., 1966.
  3. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. "Введение в теорию конечных автоматов".- М.: Наука, 1985 г.
  4. Автоматы. Сборник статей под редакцией Маккарти и Шеннона, ИЛ, Москва, 1956
  5. Мальцев А.И. Алгоритмы и вычислимые функции. М.:Наука,1965.
  6. Проблемы кибернетики, вып. 1,2,5,9,10,13.
  7. Кибернетический сборник, вып. 1,3. М.:ИЛ,1960-1961.
  8. Труды Математического института им. В.А. Стеклова, т.51. М.: Изд. АН СССР, 1958.
  9. Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.
  10. Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.
  11. Чегис И.А., Яблонский С.В., Логические способы контроля электрических схем // Труды МИАН им. В.А. Стеклова т.51, 1958, с. 270-360.
  12. Алешин С.В. Распознавание динамических образов, изд. МГУ, 1996.

Наверх

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