Дискретные модели управляющих систем — различия между версиями
(→Объявления) |
(→Вопросы к экзамену) |
||
Строка 73: | Строка 73: | ||
# Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007. | # Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007. | ||
− | == | + | ==Экзамен== |
− | + | Экзамен письменный. Продолжительность экзамена – 1,5 астрономических часа (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно». | |
+ | |||
+ | '''Вопросы к экзамену''' | ||
# Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. | # Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. | ||
Строка 83: | Строка 85: | ||
# Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в планарном графе. | # Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в планарном графе. | ||
# Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. | # Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. | ||
− | # Числа Рамсея. Верхняя и нижняя оценки | + | # Числа Рамсея. Верхняя и нижняя оценки числа Рамсея. |
− | # Полная система. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике. | + | # Полная система в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике. |
− | # Полная система. Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов. | + | # Полная система в k-значной логике. Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов. |
− | # Полная система. Теорема о существовании алгоритма распознавания полноты в k-значной логике. | + | # Полная система в k-значной логике. Теорема о существовании алгоритма распознавания полноты в k-значной логике. |
− | # Полная система. Замкнутый класс. Теорема Кузнецова о функциональной полноте. | + | # Полная система в k-значной логике. Замкнутый класс. Теорема Кузнецова о функциональной полноте. |
− | # Замкнутый класс. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk. | + | # Замкнутый класс в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk. |
− | # Существенные функции. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате. | + | # Существенные функции в k-значной логике. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате. |
# Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого. | # Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого. | ||
− | # Шефферовы функции. Критерий шефферовости. | + | # Шефферовы функции в k-значной логике. Критерий шефферовости. |
− | # Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. | + | # Замкнутый класс и базис замкнутого класса в k-значной логике. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. |
# Детерминированные конечные автоматы без выхода, их функционирование и способы представления. Автоматные множества, лемма об их свойствах. Пример неавтоматного множества. | # Детерминированные конечные автоматы без выхода, их функционирование и способы представления. Автоматные множества, лемма об их свойствах. Пример неавтоматного множества. | ||
# Недетерминированные конечные автоматы без выхода. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата. | # Недетерминированные конечные автоматы без выхода. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата. |
Версия 14:53, 11 февраля 2020
Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП
Курс читает Селезнева Светлана Николаевна
Объявления
Лекции
Лекция 1. Комбинаторика. Основные комбинаторные числа. Оценки и асимптотики комбинаторных чисел.
Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями. Оценки и асимптотики биномиальных коэффициентов. Оценки и асимптотики сумм биномиальных коэффициентов. [1] стр. 171-183, 213-214, Слайды к лекции 1
Лекция 2. Графы. Граф и сеть. Оценки числа графов и сетей различных видов. Планарные графы. Формула Эйлера для планарных графов. Теорема Понтрягина-Куратовского.
Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. Планарные графы. Формула Эйлера для планарных графов. Теорема о наибольшем числе ребер в планарном графе. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского. [1] стр. 222-227, 230-233, [2] стр. 26-38, [3, 4], Слайды к лекции 2
Лекция 3. Графы. Экстремальная теория графов. Теорема Турана. Теорема Рамсея.
Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами. Числа Рамсея. Оценки чисел Рамсея. [3, 4], Слайды к лекции 3
Лекция 4. Многозначные логики. Способы представления k-значных функций. Полнота. Система Поста.
Функции k-значной логики. Способы представления k-значных функций: 1-я и 2-я формы, полиномы. Полные системы. Теорема о полноте системы Поста в k-значной логике. [1] стр. 43-50, 69-73, Слайды к лекции 4
Лекция 5. Многозначные логики. Алгоритм распознавания полноты конечных систем k-значных функций. Теорема Кузнецова о функциональной полноте.
Теорема о существовании алгоритма распознавания полноты в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Теорема Кузнецова о функциональной полноте. [1] стр. 50-56, Слайды к лекции 5
Лекция 6. Многозначные логики. Теорема Яблонского. Теорема Слупецкого.
Существенные функции. Три леммы о существенных функциях. Теорема Яблонского. Теорема Слупецкого. [1] стр. 56-65, Слайды к лекции 6
Лекция 7. Многозначные логики. Особенности многозначных логик.
Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом. [1] стр. 67-69, Слайды к лекции 7
Лекция 8. Конечные автоматы. Регулярные события и их представления в автоматах.
Конечные автоматы без выхода, детерминированные и недетерминированные. Автоматные множества. Пример неавтоматного множества. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата. [5], Слайды к лекции 8
Лекция 9. Конечные автоматы. Регулярные события и их представления в автоматах.
Операции над автоматными множествами: дополнение, объединение, пересечение, произведение, итерация, их автоматность. [5], Слайды к лекции 9
Лекция 10. Конечные автоматы. Регулярные события и их представления в автоматах.
Регулярные выражения и регулярные множества. Совпадение классов автоматных и регулярных множеств. [5], Слайды к лекции 10
Лекция 11. Конечные автоматы. Эксперименты с автоматами.
Конечные автоматы с выходом. Преобразование периодических последовательностей конечными автоматами с выходом. Отличимость состояний в конечных автоматах с выходом. Упрощение автоматов. [2], Слайды к лекции 11
Лекция 12. Конечные поля и их основные свойства.
Кольца, поля. Теорема о конечном целостном кольце. Характеристика кольца. Кольцо многочленов. Деление с остатком многочленов над полем. Неприводимые многочлены над полем. Поле остатков от деления на неприводимый многочлен над полем. [6, 7], Слайды к лекции 12
Лекция 13. Конечные поля и их основные свойства.
Построение конечных полей. Вычисления в конечных полях. Свойства мультипликативной группы конечного поля. [6, 7], Слайды к лекции 13
Лекция 14. Конечные поля и их основные свойства.
Произведение неприводимых многочленов степени, кратной n. Число неприводимых многочленов над простым полем. Расширения полей. Корни неприводимых многочленов над простым полем в его расширении. Существование и единственность поля с p^n элементами, где p - простое число, n \ge 1. [6, 7], Слайды к лекции 14
Литература
- Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 2009.
- Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
- Марченков С.С. Конечные автоматы. М.: Физматлит, 2008.
- Лидл Р., Нидеррайтер Г. Конечные поля. Том 1. М.: Мир, 1988.
- Чашкин А.В. Лекции по дискретной математике. М.: Изд-во механико-математического факультета МГУ, 2007.
Экзамен
Экзамен письменный. Продолжительность экзамена – 1,5 астрономических часа (90 минут). В проверочной работе десять заданий разной сложности по содержанию курса. Первые четыре задания – стандартные задачи по курсу, они оцениваются в 3 балла каждое. Следующие четыре задания – формулировки определений или теорем с дополнительным вопросом. Вопрос проясняет понимание аспирантом формулировки. Они оцениваются также в три балла каждое. Оставшиеся два задания – вопросы или задачи повышенной сложности. Они показывают, может ли аспирант извлекать новые сведения из полученных знаний в курсе. Всего за работу можно получить не более 32 баллов. Критерии оценок: не менее 27 баллов – «отлично», 21-26 баллов – «хорошо», 15-20 баллов – «удовлетворительно», менее 14 баллов – «неудовлетворительно».
Вопросы к экзамену
- Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
- Поведение последовательности биномиальных коэффициентов. Верхняя оценка биномиального коэффициента. Асимптотика суммы биномиальных коэффициентов.
- Граф. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами.
- Планарный граф. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (только формулировка).
- Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в планарном графе.
- Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
- Числа Рамсея. Верхняя и нижняя оценки числа Рамсея.
- Полная система в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике.
- Полная система в k-значной логике. Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
- Полная система в k-значной логике. Теорема о существовании алгоритма распознавания полноты в k-значной логике.
- Полная система в k-значной логике. Замкнутый класс. Теорема Кузнецова о функциональной полноте.
- Замкнутый класс в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk.
- Существенные функции в k-значной логике. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
- Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
- Шефферовы функции в k-значной логике. Критерий шефферовости.
- Замкнутый класс и базис замкнутого класса в k-значной логике. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
- Детерминированные конечные автоматы без выхода, их функционирование и способы представления. Автоматные множества, лемма об их свойствах. Пример неавтоматного множества.
- Недетерминированные конечные автоматы без выхода. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата.
- Операции над автоматными множествами: дополнение, объединение, пересечение, произведение и итерация, их автоматность.
- Регулярные выражения и регулярные множества. Совпадение классов автоматных и регулярных множеств.
- Детерминированные конечные автоматы с выходом, их функционирование и способы представления. Преобразование периодических последовательностей конечными автоматами с выходом.
- Отличимость состояний в конечных автоматах с выходом. Теорема Мура о длине слова, отличающего два отличимые состояния конечного автомата. Упрощение автоматов.