Дискретные модели управляющих систем — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Содержимое страницы заменено на «Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП Категория:Лек…»)
 
(не показана 71 промежуточная версия 1 участника)
Строка 1: Строка 1:
 
Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП
 
Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП
 
   
 
   
Курс читает доцент [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
 
 
==Лекции==
 
 
'''Лекция 1'''. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.
 
 
Размещения, перестановки, размещения с повторениями, сочетания, их число рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов. [1] стр. 171-183, 213-214, [6]
 
 
'''Лекция 2'''. Графы и сети. Оценки графов и сетей различных типов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.
 
 
Графы и сети. Оценка числа деревьев с h ребрами. Оценка числа псевдографов с h ребрами. Оценка числа п-сетей с h ребрами. Планарные графы. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. [1] стр. 222-227, [2] стр. 33-37
 
 
'''Лекция 3'''. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.
 
 
Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея. [5] стр. 28-31
 
 
'''Лекция 4'''. Проблема полноты. Теорема о полноте систем функций двузначной логики. Алгоритм распознавания полноты систем функций k-значной логики.
 
 
Полные системы. Теорема Поста о полноте систем функций двузначной логики. Теорема о полноте системы Поста в k-значной логике. Теорема о существовании алгоритма распознавания полноты в k-значной логике. [1] стр. 43-53
 
 
'''Лекция 5'''. Теорема Слупецкого. Особенности k-значных логик.
 
 
Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого. Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. [1] стр. 56-71.
 
 
'''Лекция 6'''. Эксперименты с автоматами. Алгоритмическая неразрешимость проблемы полноты для автоматов.
 
 
Конечные автоматы-преобразователи. Отличимость состояний автомата. Теорема Мура о длине эксперимента, отличающего два отличимых состояния конечного автомата. Проблема полноты для конечных автоматов. Теорема о существовании конечных полных систем автоматов. Теорема о несводимости операций суперпозиции и обратной связи друг к другу. Теорема об алгоритмической неразрешимости распознавания полноты систем автоматов. [2] стр. 83-86, [1] стр. 86-113
 
 
'''Лекция 7'''. Проблема минимизации ДНФ. Локальные алгоритмы. Построение ДНФ сумма тупиковых в классе локальных алгоритмов. Невозможность построения ДНФ сумма минимальных в классе локальных алгоритмов. [3] стр. 12-21
 
 
'''Лекция 8'''. Асимптотически наилучший метод синтеза СФЭ. Инвариантные классы и их свойства. Синтез СФЭ для функций из некоторых инвариантных классов. [4] стр. 65-69, , [3] стр. 5-10
 
 
'''Лекция 9'''. Нижние оценки сложности реализации функций алгебры логики π-схемами и формулами.
 
 
'''Лекция 10'''. Эквивалентные преобразования формул двузначной логики. Пример Линдона.
 
 
'''Лекция 11'''. Логический подход к контролю исправности и диагностике неисправностей управляющих систем. Тесты.
 
 
'''Лекция 12'''. Конечные поля и их основные свойства. Коды Боуза-Чоудхури-Хоквингема.
 
 
 
'''Литература'''
 
 
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
# Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 
# Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ им. М.В. Ломоносова, 2001.
 
# Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.
 
# Харари Ф. Теория графов. М.: Мир, 1973.
 
# [[Media: dmus1-selezn.pdf| Слайды к лекции 1]]
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
 
==Вопросы к экзамену==
 
'''(весенний  семестр 2014/2015 учебного года, аспиранты 1 г/о кафедр ИО, МК, ММП, лектор — доцент С.Н. Селезнева)'''
 
 
 
 
'''Литература'''
 
 
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
# Сапоженко А.А. Некоторые вопросы сложности алгоритмов. М.: Издательский отдел ф-та ВМК МГУ им. М.В. Ломоносова, 2001.
 
# Нигматуллин Р.Г. Сложность булевых функций. Казань: Изд-во Казанского университета, 1983.
 
# Харари Ф. Теория графов. М.: Мир, 1973.
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
 
 
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Текущая версия на 14:05, 24 мая 2021

Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП