Дискретные модели — различия между версиями

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Объявления)
(О проведении экзамена)
 
(не показаны 22 промежуточных версий 1 участника)
Строка 1: Строка 1:
Курс для студентов неинтегрированной магистратуры, 1-й курс, 2-й семестр.
+
Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр)
 +
 
 +
Лекции - 16 ч, отчетность - экзамен.
  
 
Лектор - [[Селезнева Светлана Николаевна]].
 
Лектор - [[Селезнева Светлана Николаевна]].
Строка 5: Строка 7:
 
== Объявления ==
 
== Объявления ==
  
'''Экзамен состоится 5 июня (в пятницу) удаленно. Начало в 10 ч'''.
+
==Программа курса==
  
В 10 ч на эл. почту студентам рассылаются экзаменационные задания. Примерный вариант экзаменационной работы приведен ниже на этой странице. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. Выполненную работу нужно отсканировать или сфотографировать. Затем скан или фотографию работы (в формате pdf, jpg или png) загрузить на проверку по ссылке, присланной в письме вместе с заданием. На сканирование/фотографирование и загрузку работы отводится 15 мин. Т.е. выполненные работы нужно загрузить до 11 ч 45 мин (иначе считается, что студент работу не сдал).
+
'''Тема 1. Многозначные логики'''.
  
Лектор проверяет работы. При этом если в нескольких работах встречаются совпадающие решения какого-то задания, то это задание не засчитывается во всех этих работах. Затем итоги экзамена появляются на странице курса и объявляется время, когда студенты могут задать вопросы лектору по оценкам в своих работах. После этого оценки за экзамен выставляются в ведомость.  
+
Лекция 1. Функции k-значной логики. Способы их представления: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
Все вопросы, связанные с отсутствием интернета во время экзамена, будут решаться отдельно в каждом случае.
+
Лекция 2. Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы.
  
<!---[[Media: dm-exam2-2019.pdf | Итоги пересдачи]] от 7 сентября 2019 г. Посмотреть работу и получить оценку в зачетку можно в среду, 11 сентября, с 15-30 до 16-00 в ауд. 595.--->
+
Лекция 3. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом.
  
==Программа курса==
+
'''Тема 2. Графы'''.
 +
 
 +
Лекция 4. Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.
 +
 
 +
Лекция 5. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
  
*[[Media: dm-l1-selezn.pdf |'''Лекция 1''']]: Многозначные логики. Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах. Теорема о представлении функций k-значной логики полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба. [1] стр. 43-50, 69-71, [2] стр. 24-25.
+
Лекция 6. Наследственные свойства графов. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.  
*[[Media: dm-l2-selezn.pdf |'''Лекция 2''']]: Многозначные логики. Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы. [1] стр. 50-53, 54.
+
*[[Media: dm-l3-selezn.pdf |'''Лекция 3''']]: Многозначные логики. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик. [1] стр. 65-69.
+
*[[Media: dm-l4-selezn.pdf |'''Лекция 4''']]: Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного помеченного графа. Теорема об оценке числа висячих вершин в остовном дереве графа. [2] стр. 29-31, [6] стр. 77-80, [7] стр. 48-51, [8] стр. 94-97.
+
*[[Media: dm-l5-selezn.pdf |'''Лекция 5''']]: Графы. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Теоремы об оценках хроматического числа графа. [4] (стр. 235-240), [5] (стр. 359-361), [6] стр. 284-285, [7] стр. 152-153.
+
*[[Media: dm-l6-selezn.pdf |'''Лекция 6''']]: Графы. Наследственные свойства графов. Экстремальные графы. Теорема об оценке числа ребер в графе с наследственным свойством. Планарные графы, теорема о наибольшем числе ребер в планарном графе. Теорема о наибольшем числе ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами. [2] стр. 34-35, 38, [6] стр. 270-273, [7] стр. 30-33
+
*[[Media: dm-l7-selezn.pdf |'''Лекция 7''']]: Графы. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея. [5] (стр. 308-313), [6] стр. 273-276, [7] стр. 28-30.
+
  
<!--[[Media:dm-mag-selezn.pdf|'''Лекции по "Дискретным моделям" ''']] (текст лекций 4-7, замечание: теорема 2.3 не входит в программу курса в 2018 г.)-->
+
Лекция 7. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.  
  
 
'''Литература'''
 
'''Литература'''
Строка 32: Строка 32:
 
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 
#Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.  
 
#Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.  
#Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
+
#Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.
#Оре О. Теория графов. М.: Наука, 1980.
+
#Харари Ф. Теория графов. М.: Мир, 1973.
+
#Липский В. Комбинаторика для программистов. М.: Мир, 1988.
+
  
 
==О проведении экзамена==
 
==О проведении экзамена==
Строка 73: Строка 70:
  
 
10) найти наибольшее число ребер в графе с заданным наследственным свойством ([3] гл. VI 2.8, 2.9, 2.10, 2.17).
 
10) найти наибольшее число ребер в графе с заданным наследственным свойством ([3] гл. VI 2.8, 2.9, 2.10, 2.17).
 
+
<!---[[Media:exam-mag-dm.pdf|'''Примерный вариант экзаменационной работы''']]--->
[[Media:exam-mag-dm.pdf|'''Примерный вариант экзаменационной работы''']]
+
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Текущая версия на 00:09, 6 января 2024

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

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

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

Объявления

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

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

Лекция 1. Функции k-значной логики. Способы их представления: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 2. Алгоритм распознавания полноты в 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).