|
|
| Строка 1: |
Строка 1: |
| | Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП | | Обязательный курс для аспирантов 1 г/о кафедр ИО, МК, ММП |
| | | | |
| − | Курс читает [[Селезнева Светлана Николаевна|Селезнева Светлана Николаевна]]
| |
| − |
| |
| − | ==Объявления==
| |
| − |
| |
| − | <!---'''После получения проверенной работы в течение часа аспирант может задавать по эл. почте лектору вопросы по оценкам в своих работах. Через час после отправки проверенных работ аспирантам, оценки будут выставлены в ведомость, и ведомость будет отправлена в отдел аспирантуры'''.--->
| |
| − |
| |
| − | '''Экзамен - 12 мая, начало экзамена - в 10 ч'''.
| |
| − |
| |
| − | Экзамен состоится удаленно. В 10 ч на эл. почту аспирантам будут разосланы экзаменационные работы. Из каких заданий будет состоять экзаменационная работа приведено ниже на этой странице. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. После выполнения работы ее нужно сфотографировать или отсканировать. Затем фотографии или сканы работы в формате jpg, png или pdf прислать лектору на эл. почту selezn@cs.msu.ru. На фотографирование или сканирование работы и отправку письма отводится 15 мин. Если лектор не получает работу аспиранта через 1 ч 45 мин (105 мин) после начала экзамена, т.е. до 11 ч 45 мин, то считается, что аспирант работу не сдал.
| |
| − |
| |
| − | Лектор проверяет работы. При этом если в нескольких работах встречаются совпадающие решения какого-то задания, то это задание не засчитывается во всех этих работах. Затем итоги экзамена появляются на странице курса и объявляется время, когда аспиранты могут задать вопросы лектору по оценкам в своих работах. После этого оценки выставляются в ведомость.
| |
| − |
| |
| − | Все вопросы, связанные с отсутствием интернета во время экзамена, будут решаться отдельно в каждом случае.
| |
| − |
| |
| − | ==Лекции==
| |
| − |
| |
| − | '''Лекция 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.
| |
| − | # Марченков С.С. Избранные главы дискретной математики. М.: МАКС Пресс, 2016.
| |
| − | # Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Либроком, 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 баллов – «неудовлетворительно». [[Media: dmus-exam-var.pdf| '''Примерный вариант экзаменационной работы''']]
| |
| − |
| |
| − | '''Вопросы к экзамену'''
| |
| − |
| |
| − | # Размещения, перестановки, размещения с повторениями, сочетания, их число и рекуррентные формулы для них. Сочетания с повторениями. Теорема о числе сочетаний с повторениями.
| |
| − | # Поведение последовательности биномиальных коэффициентов. Верхняя оценка биномиального коэффициента. Асимптотика суммы биномиальных коэффициентов.
| |
| − | # Граф. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами.
| |
| − | # Планарный граф. Формула Эйлера для планарных графов. Непланарность графов K5 и K3,3. Теорема Понтрягина-Куратовского (только формулировка).
| |
| − | # Наследственные свойства графов. Теорема о числе ребер в графах с наследственным свойством. Теорема о числе ребер в планарном графе.
| |
| − | # Теорема о числе ребер в графе без треугольников. Теорема Турана о числе ребер в графе без полного графа с n вершинами.
| |
| − | # Числа Рамсея. Верхняя и нижняя оценки числа Рамсея.
| |
| − | # Полная система в k-значной логике. Теорема о представимости функций k-значной логики в 1-й форме. Теорема о полноте системы Поста в k-значной логике.
| |
| − | # Полная система в k-значной логике. Теорема о представимости функций k-значной логики во 2-й форме. Теорема о полноте системы полиномов.
| |
| − | # Полная система в k-значной логике. Теорема о существовании алгоритма распознавания полноты в k-значной логике.
| |
| − | # Полная система в k-значной логике. Замкнутый класс. Теорема Кузнецова о функциональной полноте.
| |
| − | # Замкнутый класс в k-значной логике. Классы функций, сохраняющих множество и сохраняющих разбиение, их замкнутость. Критерии их совпадения с Pk.
| |
| − | # Существенные функции в k-значной логике. Леммы о существенных функциях: лемма о трех наборах, основная лемма, лемма о квадрате.
| |
| − | # Теорема Яблонского о полноте систем функций k-значной логики, содержащих все функции одной переменной, принимающие не более (k-1) значений. Теорема Слупецкого.
| |
| − | # Шефферовы функции в k-значной логике. Критерий шефферовости.
| |
| − | # Замкнутый класс и базис замкнутого класса в k-значной логике. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и со счетным базисом.
| |
| − | # Детерминированные конечные автоматы без выхода, их функционирование и способы представления. Автоматные множества, лемма об их свойствах. Пример неавтоматного множества.
| |
| − | # Недетерминированные конечные автоматы без выхода. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура детерминизации конечного автомата.
| |
| − | # Операции над автоматными множествами: дополнение, объединение, пересечение, произведение и итерация, их автоматность.
| |
| − | # Регулярные выражения и регулярные множества. Совпадение классов автоматных и регулярных множеств.
| |
| − | # Детерминированные конечные автоматы с выходом, их функционирование и способы представления. Преобразование периодических последовательностей конечными автоматами с выходом.
| |
| − | # Отличимость состояний в конечных автоматах с выходом. Теорема Мура о длине слова, отличающего два отличимые состояния конечного автомата. Упрощение автоматов.
| |
| − | <!---#Кольца, их виды. Поля. Теорема о конечном целостном кольце. Простое поле.
| |
| − | #Характеристика кольца. Характеристика конечного целостного кольца.
| |
| − | #Кольцо многочленов над кольцом. Наследование свойств кольца в кольце многочленов.
| |
| − | #Кольцо многочленов над полем. Деление с остатком многочленов над полем.
| |
| − | #Наибольший общий делитель двух многочленов над полем. Теорема о его существовании и единственности.
| |
| − | #Неприводимые многочленов над полем. Критерий неприводимости многочленов степени два и три.
| |
| − | #Поле остатков от деления на неприводимый многочлен над полем.
| |
| − | #Теорема о мультипликативной группе конечного поля. Примитивный элемент конечного поля.
| |
| − | #Теорема о произведении неприводимых нормированных многочленов над простым полем.
| |
| − | #Формула обращения Мебиуса. Теорема о числе неприводимых многочленов степени n над простым полем. Существование поля из p^n элементов, где p – простое число, n ≥ 1.
| |
| − | #Расширения полей. Теорема о корнях неприводимых многочленов в расширении простого поля.
| |
| − | #Расширения полей. Теорема о свойствах корней неприводимых многочленов в расширении простого поля.
| |
| − | #Теорема о существовании и единственности конечного поля из p^n элементов, где p – простое число, n ≥ 1.--->
| |
| − |
| |
| − |
| |
| | [[Категория:Лекционные курсы кафедры МК]] | | [[Категория:Лекционные курсы кафедры МК]] |
