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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Объявления)
(Программа курса)
Строка 11: Строка 11:
 
'''Тема 1. Многозначные логики'''.
 
'''Тема 1. Многозначные логики'''.
  
*[[Media: dvm-l1-selezn.pdf |'''Лекция 1''']]: Функции k-значной логики. Формулы. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах.  
+
*'''Лекция 1'''. Функции k-значной логики. Формулы. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах.  
*[[Media: dvm-l2-selezn.pdf |'''Лекция 2''']]: Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота в P_k. Теорема о полноте системы Поста. Функция Вебба.
+
*'''Лекция 2'''. Полиномы. Теорема о представлении функций k-значной логики полиномами по модулю k. Полнота в P_k. Теорема о полноте системы Поста. Функция Вебба.
*[[Media: dvm-l2-1-selezn.pdf |'''Лекция 2-1''']]: Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы.
+
*'''Лекция 3'''. Замыкание и замкнутый класс. Сохранение функцией отношения. Замкнутые классы функций, сохраняющих отношение. Критериальная система. Предполные классы.
*[[Media: dvm-l3-selezn.pdf |'''Лекция 3''']]: Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом.
+
*'''Лекция 4'''. Распознавание полноты в P_k. Замкнутый класс, базис замкнутого класса. Теорема Янова и теорема Мучника. Замкнутые классы в P_k при k >= 3.
<!---*[[Media: dvm-l3-selezn.pdf |'''Лекция 3''']]: Замыкание и замкнутый класс. Сохранение функцией отношения. Замкнутые классы функций, сохраняющих отношение. Критериальная система. Предполные классы.
+
*[[Media: dvm-l4-selezn.pdf |'''Лекция ''']]: Распознавание полноты в P_k. Замкнутый класс, базис замкнутого класса. Теорема Янова и теорема Мучника. Замкнутые классы в P_k при k >= 3.--->
+
  
 
'''Тема 2. Графы'''.
 
'''Тема 2. Графы'''.
  
*[[Media: dvm-l4-selezn.pdf |'''Лекция 4''']]: Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.  
+
*'''Лекция 5'''. Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.  
*[[Media: dvm-l5-selezn.pdf |'''Лекция 5''']]: Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
+
*'''Лекция 6'''. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
*[[Media: dvm-l6-selezn.pdf |'''Лекция 6''']]: Наследственные свойства графов. Экстремальные графы. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.  
+
*'''Лекция 7'''. Наследственные свойства графов. Экстремальные графы. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.  
*[[Media: dvm-l7-selezn.pdf |'''Лекция 7''']]: Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.  
+
*'''Лекция 8'''. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.  
  
 
'''Литература'''
 
'''Литература'''

Версия 13:28, 23 января 2023

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

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

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

Объявления

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

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

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

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

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

Литература

  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).

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