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