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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Объявления)
(Содержимое страницы заменено на «Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП Категория:Лек…»)
 
(не показаны 27 промежуточные версии 1 участника)
Строка 1: Строка 1:
 
Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП
 
Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП
 
   
 
   
Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
 
 
==Объявления==
 
 
'''Экзамен состоится 16 мая (в среду) в ауд. 582. Выдача вопросов в 16 ч. Начало опроса в 17 ч.'''
 
 
Экзамен проходит устно. В билете - два вопроса. Подготовка к ответу в течение одного часа, можно пользоваться любыми источниками. Ответ на билет у доски. Сначала аспирант выписывает на доске заметки к ответу, при этом можно пользоваться только своими записями, сделанными во время часа подготовки. После ответа на оба вопроса билета аспиранту предлагается дополнительный вопрос (определение, теорема, идея доказательства). Ответ на дополнительный вопрос - без источников.
 
 
==Лекции==
 
 
'''Лекция 1'''.  Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.
 
 
Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов. [1] стр. 171-183, 213-214, [[Media: dmus1-selezn.pdf| Слайды к лекции 1]]
 
 
'''Лекция 2'''. Графы. Граф и сеть. Оценки числа графов и сетей различных видов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.
 
 
Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. Планарные графы. Формула Эйлера для планарных графов. Теорема о наибольшем числе ребер в планарном графе. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. [1] стр. 222-227, 230-233, [2] стр. 26-38, [3, 4], [[Media: dmus2-selezn.pdf| Слайды к лекции 2]]
 
 
'''Лекция 3'''. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.
 
 
Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея. [3, 4], [[Media: dmus3-selezn.pdf| Слайды к лекции 3]]
 
 
'''Лекция 4'''. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста.
 
 
Функции k-значной логики. Способы представления k-значных функций: 1-я и 2-я формы, полиномы. Полные системы. Теорема о полноте системы Поста в k-значной логике. [1] стр. 43-50, 69-73, [[Media: dmus4-selezn.pdf| Слайды к лекции 4]]
 
 
'''Лекция 5'''. Многозначные логики. Алгоритм распознавания полноты конечных систем k-значных функций. Теорема Кузнецова о функциональной полноте.
 
 
Теорема о существовании алгоритма распознавания полноты в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. [1] стр. 50-56, [[Media: dmus5-selezn.pdf| Слайды к лекции 5]]
 
 
'''Лекция 6'''. Многозначные логики. Теорема Яблонского. Теорема Слупецкого. 
 
 
Существенные функции. Три леммы о существенных функциях. Теорема Яблонского. Теорема Слупецкого. [1] стр. 56-65, [[Media: dmus6-selezn.pdf| Слайды к лекции 6]]
 
 
'''Лекция 7'''. Многозначные логики. Особенности многозначных логик.
 
 
Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. [1] стр. 67-69,  [[Media: dmus7-selezn.pdf| Слайды к лекции 7]]
 
 
'''Лекция 8'''. Конечные автоматы. Регулярные события и их представления в автоматах.
 
 
Конечные автоматы без выхода, детерминированные и недетерминированные. Автоматные множества. Пример неавтоматного множества. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата. [5], [[Media: dmus8-selezn.pdf| Слайды к лекции 8]]
 
 
'''Лекция 9'''. Конечные автоматы. Регулярные события и их представления в автоматах.
 
 
Операции над автоматными множествами: дополнение, объединение, пересечение, произведение, итерация, их автоматность. [5], [[Media: dmus9-selezn.pdf| Слайды к лекции 9]]
 
 
'''Лекция 10'''. Конечные автоматы. Регулярные события и их представления в автоматах.
 
 
Регулярные выражения и регулярные множества. Совпадение классов автоматных и регулярных множеств. [5], [[Media: dmus10-selezn.pdf| Слайды к лекции 10]]
 
 
'''Лекция 11'''. Конечные автоматы. Эксперименты с автоматами.
 
 
Конечные автоматы с выходом. Преобразование периодических последовательностей конечными автоматами с выходом. Отличимость состояний в конечных автоматах с выходом. Упрощение автоматов. [2], [[Media: dmus11-selezn.pdf| Слайды к лекции 11]]
 
 
'''Лекция 12'''. Конечные поля и их основные свойства.
 
 
Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Поле остатков от деления на неприводимый многочлен над полем. [6, 7], [[Media: dmus12-selezn.pdf| Слайды к лекции 12]]
 
 
'''Лекция 13'''. Конечные поля и их основные свойства.
 
 
Построение конечных полей. Вычисления в конечных полях. Свойства мультипликативной группы конечного поля. [6, 7], [[Media: dmus13-selezn.pdf| Слайды к лекции 13]]
 
 
'''Лекция 14'''. Конечные поля и их основные свойства.
 
 
Произведение неприводимых многочленов степени, кратной n. Число неприводимых многочленов над простым полем. Расширения полей. Корни неприводимых многочленов над простым полем в его расширении. Существование и единственность поля с p^n элементами, где p - простое число, n \ge 1. [6, 7], [[Media: dmus14-selezn.pdf| Слайды к лекции 14]]
 
 
'''Литература'''
 
 
# Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
# Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 
# Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
 
# Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
 
# Марченков С.С. Конечные автоматы. М.: Физматлит, 2008.
 
# Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
 
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
 
 
==Вопросы к экзамену==
 
 
Весенний семестр 2017-2018 учебного года
 
 
# Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
 
# Поведение последовательности биномиальных коэффициентов. Верхняя оценка биномиального коэффициента. Асимптотика суммы биномиальных коэффициентов.
 
# Граф. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. 
 
# Планарный граф. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (только формулировка).
 
# Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в планарном графе.
 
# Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
 
# Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
 
# Полная система. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике.
 
# Полная система. Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
 
# Полная система. Теорема о существовании алгоритма распознавания полноты в k-значной логике.
 
# Полная система. Замкнутый класс. Теорема Кузнецова о функциональной полноте.
 
# Замкнутый класс. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk.
 
# Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
 
# Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
 
# Шефферовы функции. Критерий шефферовости.
 
# Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
 
# Детерминированные конечные автоматы без выхода, их функционирование и способы представления. Автоматные множества, лемма об их свойствах. Пример неавтоматного множества.
 
# Недетерминированные конечные автоматы без выхода. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата.
 
# Операции над автоматными множествами: дополнение, объединение, пересечение, произведение и итерация, их автоматность.
 
# Регулярные выражения и регулярные множества. Совпадение классов автоматных и регулярных множеств.
 
# Детерминированные конечные автоматы с выходом, их функционирование и способы представления. Преобразование периодических последовательностей конечными автоматами с выходом.
 
# Отличимость состояний в конечных автоматах с выходом. Теорема Мура о длине слова, отличающего два отличимые состояния конечного автомата. Упрощение автоматов.
 
 
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

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

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