Дискретные модели

Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр)

Лекции - 16 ч, отчетность - экзамен.

Лектор - Селезнева Светлана Николаевна.

Объявления

Экзамен состоится 16 июня (в четверг) удаленно письменно. Начало в 10 ч 30 мин.

В 10 ч 30 мин на эл. почту студентам рассылаются экзаменационные задания. Примерный вариант экзаменационной работы приведен ниже на этой странице. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. Выполненную работу нужно отсканировать или сфотографировать. Затем скан или фотографию работы (в формате pdf, jpg или png) загрузить на проверку по ссылке, присланной в письме вместе с заданием. На сканирование/фотографирование и загрузку работы отводится 15 мин. Т.е. выполненные работы нужно загрузить до 11 ч 45 мин (иначе считается, что студент работу не сдал).

Лектор проверяет работы. При этом если в нескольких работах встречаются совпадающие решения какого-то задания, то это задание не засчитывается во всех этих работах. Затем итоги экзамена появляются на странице курса и объявляется время, когда студенты могут задать вопросы лектору по оценкам в своих работах. После этого оценки за экзамен выставляются в ведомость.

Все вопросы, связанные с отсутствием интернета во время экзамена, будут решаться отдельно в каждом случае.

Вопросы по содержанию курса можно направлять по эл. почте лектору Селезневой Светлане Николаевне.

Программа курса

Тема 1. Многозначные логики.

• Лекция 1: Функции k-значной логики. Формулы. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах.
• Лекция 2: Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота в P_k. Теорема о полноте системы Поста. Функция Вебба.
• Лекция 2-1: Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы.
• Лекция 3: Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом.

Тема 2. Графы.

• Лекция 4: Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.
• Лекция 5: Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
• Лекция 6: Наследственные свойства графов. Экстремальные графы. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.
• Лекция 7: Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.

Литература

1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
2. Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
3. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
4. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.
5. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.

О проведении экзамена

Экзамен проходит в виде письменной работы. На экзамене не разрешается пользоваться никакими материалами. Письменная работа содержит 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).

Примерный вариант экзаменационной работы