Дискретные модели
Обязательный курс для студентов магистратуры, 1-й курс, 2-й семестр.
Лектор - Селезнева Светлана Николаевна.
Объявления
Итоги экзамена от 8 июня появятся на этой странице во вторник, 9 июня, после 16 ч.
Конференция с помощью zoom с лектором, на которой можно будет задать вопросы по оценкам, состоится, во вторник, 9 июня, с 19 ч до 19 ч 30 мин (по московскому времени). После 19 ч 30 мин оценки будут поставлены в ведомость.
Всем, у кого возникнет необходимость участвовать в этой конференции, просьба написать лектору, чтобы узнать идентификатор конференции и пароль.
Экзамен - 8 июня, начало экзамена - в 16 ч.
Экзамен состоится удаленно. В 16 ч на эл. почту студентам рассылаются экзаменационные работы. Примерный вариант экзаменационной работы приведен ниже на этой странице. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. Затем работу нужно сфотографировать или отсканировать и сдать на проверку фотографию или скан работы в формате png, jpg или pdf. Работы надо сдать до 17 ч 45 мин (иначе считается, что студент работу не сдал).
Лектор проверяет работы. При этом если в нескольких работах встречаются совпадающие решения какого-то задания, то это задание не засчитывается во всех этих работах. Затем итоги экзамена появляются на странице курса и объявляется время, когда студенты могут задать вопросы лектору по оценкам в своих работах. После этого оценки за экзамен выставляются в ведомость.
Все вопросы, связанные с отсутствием интернета во время экзамена, будут решаться отдельно в каждом случае.
Программа курса
- Лекция 1: Многозначные логики. Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах. Теорема о представлении функций k-значной логики полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба. [1] стр. 43-50, 69-71, [2] стр. 24-25.
- Лекция 2: Многозначные логики. Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы. [1] стр. 50-53, 54.
- Лекция 3: Многозначные логики. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик. [1] стр. 65-69.
- Лекция 4: Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного помеченного графа. Теорема об оценке числа висячих вершин в остовном дереве графа. [2] стр. 29-31, [6] стр. 77-80, [7] стр. 48-51, [8] стр. 94-97.
- Лекция 5: Графы. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Теоремы об оценках хроматического числа графа. [4] (стр. 235-240), [5] (стр. 359-361), [6] стр. 284-285, [7] стр. 152-153.
- Лекция 6: Графы. Наследственные свойства графов. Экстремальные графы. Теорема об оценке числа ребер в графе с наследственным свойством. Планарные графы, теорема о наибольшем числе ребер в планарном графе. Теорема о наибольшем числе ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами. [2] стр. 34-35, 38, [6] стр. 270-273, [7] стр. 30-33
- Лекция 7: Графы. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея. [5] (стр. 308-313), [6] стр. 273-276, [7] стр. 28-30.
Лекции по "Дискретным моделям" (текст лекций 4-7, замечание: теорема 2.3 не входит в программу курса в 2018 г.)
Литература
- Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.
- Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
- Оре О. Теория графов. М.: Наука, 1980.
- Харари Ф. Теория графов. М.: Мир, 1973.
- Липский В. Комбинаторика для программистов. М.: Мир, 1988.
О проведении экзамена
Экзамен проходит в виде письменной работы. На экзамене не разрешается пользоваться никакими материалами. Письменная работа содержит 10 заданий. Задания 1-4 - типовые задачи, каждая из которых оценивается в 3 балла (примерный перечень типовых задач ниже). Каждое из заданий 5-8 - определение или формулировка теоремы с дополнительным вопросом, который проясняет суть определения или теоремы. Каждое из заданий 5-8 оценивается в 3 балла. Задания 9-10 - нестандартные задачи или доказательство теоремы или ее части. Каждое из заданий 9-10 оценивается в 4 балла. Продолжительность работы - 1,5 ч (одна пара).
За письменную работу можно получить не более 32 баллов. Критерии оценок:
не менее 27 баллов - "отлично";
20-26 баллов - "хорошо";
13-19 баллов - "удовлетворительно";
не более 12 баллов - "неудовлетворительно".
Примерный перечень типовых задач к экзамену:
1) доказать заданное тождество для функций k-значной логики ([3] гл. III 1.1(1-12));
2) записать заданную функцию k-значной логики в 1-й или во 2-й форме при заданном k ([3] гл. III 1.11);
3) построить полином по модулю k для заданной функции k-значной логики при заданном простом k ([3] гл. III 2.7);
4) выяснить, задается ли полиномом по модулю k заданная функция k-значной логики при заданном составном k ([3] гл. III 2.12);
5) исследовать заданную систему функций на полноту ([3] гл. III 2.13, 2.19, 2.21, 2.22);
6) найти число попарно неизоморфных графов определенного вида и перечислить эти графы ([3] гл. VI 1.3-1.8, 1.29);
7) построить код заданного остовного дерева полного графа или восстановить остовное дерево полного графа по его коду ([4] стр. 79-80);
8) построить остовное дерево для заданного связного графа с заданным числом висячих вершин;
9) найти хроматическое число заданного графа ([3] гл. VI 2.18, 2.19);
10) найти наибольшее число ребер в графе с заданным наследственным свойством ([3] гл. VI 2.8, 2.9, 2.10, 2.17).
