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

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

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

Объявления

Пересдача экзамена состоится 6 сентября (в понедельник) удаленно. Начало в 10 ч.

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

Литература

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

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