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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Программа курса)
(О проведении экзамена)
 
(не показаны 15 промежуточные версии 1 участника)
Строка 1: Строка 1:
Курс для студентов неинтегрированной магистратуры, 1-й курс, 2-й семестр.
+
Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр)
 +
 
 +
Лекции - 16 ч, отчетность - экзамен.
  
 
Лектор - [[Селезнева Светлана Николаевна]].
 
Лектор - [[Селезнева Светлана Николаевна]].
Строка 5: Строка 7:
 
== Объявления ==
 
== Объявления ==
  
<!---'''Пересдача экзамена состоится 6 сентября (в понедельник) удаленно. Начало в 10 ч'''.
+
==Программа курса==
  
В 10 ч на эл. почту студентам рассылаются экзаменационные задания. Примерный вариант экзаменационной работы приведен ниже на этой странице. На выполнение работы отводится 1 ч 30 мин (90 мин). Работу нужно написать от руки на светлых листах контрастной ручкой. Выполненную работу нужно отсканировать или сфотографировать. Затем скан или фотографию работы (в формате pdf, jpg или png) загрузить на проверку по ссылке, присланной в письме вместе с заданием. На сканирование/фотографирование и загрузку работы отводится 15 мин. Т.е. выполненные работы нужно загрузить до 11 ч 45 мин (иначе считается, что студент работу не сдал).
+
'''Тема 1. Многозначные логики'''.
  
Лектор проверяет работы. При этом если в нескольких работах встречаются совпадающие решения какого-то задания, то это задание не засчитывается во всех этих работах. Затем итоги экзамена появляются на странице курса и объявляется время, когда студенты могут задать вопросы лектору по оценкам в своих работах. После этого оценки за экзамен выставляются в ведомость.  
+
Лекция 1. Функции k-значной логики. Способы их представления: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
  
Все вопросы, связанные с отсутствием интернета во время экзамена, будут решаться отдельно в каждом случае.
+
Лекция 2. Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы.
  
Вопросы по содержанию курса можно направлять по эл. почте лектору Селезневой Светлане Николаевне.--->
+
Лекция 3. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом.
  
<!---[[Media: dm-exam2-2019.pdf | Итоги пересдачи]] от 7 сентября 2019 г. Посмотреть работу и получить оценку в зачетку можно в среду, 11 сентября, с 15-30 до 16-00 в ауд. 595.--->
+
'''Тема 2. Графы'''.
  
==Программа курса==
+
Лекция 4. Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.
  
'''Тема 1. Многозначные логики'''.
+
Лекция 5. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
  
*[[Media: dvm-l1-selezn.pdf |'''Лекция 1''']]: Функции k-значной логики. Формулы. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах.  
+
Лекция 6. Наследственные свойства графов. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.  
*[[Media: dvm-l2-selezn.pdf |'''Лекция 2''']]: Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота в P_k. Теорема о полноте системы Поста. Функция Вебба.
+
*[[Media: dvm-l3-selezn.pdf |'''Лекция 3''']]: Замыкание и замкнутый класс. Сохранение функцией отношения. Замкнутые классы функций, сохраняющих отношение. Критериальная система. Предполные классы.
+
*[[Media: dvm-l4-selezn.pdf |'''Лекция 4''']]: Распознавание полноты в P_k. Замкнутый класс, базис замкнутого класса. Теорема Янова и теорема Мучника. Замкнутые классы в P_k при k >= 3.
+
 
+
'''Тема 2. Графы'''.
+
  
*'''Лекция 5''': Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.
+
Лекция 7. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.  
*'''Лекция 6''': Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
+
*'''Лекция 7''': Наследственные свойства графов. Экстремальные графы. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.
+
*'''Лекция 8''': Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.  
+
  
 
'''Литература'''
 
'''Литература'''
Строка 38: Строка 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.
+
  
 
==О проведении экзамена==
 
==О проведении экзамена==
Строка 79: Строка 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).