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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Литература)
(О проведении экзамена)
 
(не показаны 108 промежуточные версии 1 участника)
Строка 1: Строка 1:
Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.
+
Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр)
  
Лектор - доцент [[Селезнева Светлана Николаевна]].
+
Лекции - 16 ч, отчетность - экзамен.
 +
 
 +
Лектор - [[Селезнева Светлана Николаевна]].
  
 
== Объявления ==
 
== Объявления ==
  
Экзамен по "Дискретным моделям" состоится в субботу, 4 апреля, в 14 ч в ауд. 505.
+
==Программа курса==
 +
 
 +
'''Тема 1. Многозначные логики'''.
 +
 
 +
Лекция 1. Функции k-значной логики. Способы их представления: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
 +
 
 +
Лекция 2. Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы.
 +
 
 +
Лекция 3. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом.
 +
 
 +
'''Тема 2. Графы'''.
 +
 
 +
Лекция 4. Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.
 +
 
 +
Лекция 5. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
 +
 
 +
Лекция 6. Наследственные свойства графов. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.
 +
 
 +
Лекция 7. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
 +
 
 +
'''Литература'''
 +
#Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
 +
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
 +
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
 +
#Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990.
 +
#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 ч (одна пара).
 
Экзамен проходит в виде письменной работы. На экзамене не разрешается пользоваться никакими материалами. Письменная работа содержит 10 заданий. Задания 1-4 - типовые задачи, каждая из которых оценивается в 3 балла (примерный перечень типовых задач ниже). Каждое из заданий 5-8 - определение или формулировка теоремы с дополнительным вопросом, который проясняет суть определения или теоремы. Каждое из заданий 5-8 оценивается в 3 балла. Задания 9-10 - нестандартные задачи или доказательство теоремы или ее части. Каждое из заданий 9-10 оценивается в 4 балла. Продолжительность работы - 1,5 ч (одна пара).
  
За письменную работу можно получить не более 30 баллов.
+
За письменную работу можно получить не более 32 баллов.
 
Критерии оценок:
 
Критерии оценок:
  
не менее 26 баллов - "отлично";
+
не менее 27 баллов - "отлично";
  
20-25 баллов - "хорошо";
+
20-26 баллов - "хорошо";
  
 
13-19 баллов - "удовлетворительно";
 
13-19 баллов - "удовлетворительно";
Строка 24: Строка 51:
 
'''Примерный перечень типовых задач к экзамену:'''
 
'''Примерный перечень типовых задач к экзамену:'''
  
1) подсчитать число комбинаторных объектов определенного вида ([3] гл. VIII 1.1-1.9, 1.18);
+
1) доказать заданное тождество для функций k-значной логики ([3] гл. III 1.1(1-12));
  
2) доказать заданное тождество для функций k-значной логики ([3] гл. III 1.1(1-12));
+
2) записать заданную функцию k-значной логики в 1-й или во 2-й форме при заданном k ([3] гл. III 1.11);
  
3) записать заданную функцию k-значной логики в 1-й или во 2-й форме при заданном k ([3] гл. III 1.11);
+
3) построить полином по модулю k для заданной функции k-значной логики при заданном простом k ([3] гл. III 2.7);
  
4) построить полином по модулю k для заданной функции k-значной логики при заданном простом k ([3] гл. III 2.7);
+
4) выяснить, задается ли полиномом по модулю k заданная функция k-значной логики при заданном составном k ([3] гл. III 2.12);
  
5) выяснить, задается ли полиномом по модулю 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);
 
6) найти число попарно неизоморфных графов определенного вида и перечислить эти графы ([3] гл. VI 1.3-1.8, 1.29);
  
7) построить код заданного остовного дерева полного графа или восстановить остовное дерево полного графа по его коду;
+
7) построить код заданного остовного дерева полного графа или восстановить остовное дерево полного графа по его коду ([4] стр. 79-80);
  
 
8) построить остовное дерево для заданного связного графа с заданным числом висячих вершин;
 
8) построить остовное дерево для заданного связного графа с заданным числом висячих вершин;
Строка 42: Строка 69:
 
9) найти хроматическое число заданного графа ([3] гл. VI 2.18, 2.19);
 
9) найти хроматическое число заданного графа ([3] гл. VI 2.18, 2.19);
  
10) найти максимальное число ребер в графе с заданным наследственным свойством.
+
10) найти наибольшее число ребер в графе с заданным наследственным свойством ([3] гл. VI 2.8, 2.9, 2.10, 2.17).
 
+
<!---[[Media:exam-mag-dm.pdf|'''Примерный вариант экзаменационной работы''']]--->
==Программа курса==
+
 
+
*'''Лекция 1''': Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел. [1] стр. 171-183, [9]
+
*'''Лекция 2''': Функции алгебры логики. Замкнутый класс и полная система. Теорема Поста о функциональной полноте. Базис замкнутого класса. Теорема о максимальном числе функций алгебры логики. Предполный класс. Теорема о предполных классах алгебры логики. Результаты Э. Поста о замкнутых классах алгебры логики. [1] стр. 33-42, [2] стр. 9-23.
+
*'''Лекция 3''': Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах и полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба. [1] стр. 43-50, 69-71, [2] стр. 24-25.  
+
*'''Лекция 4''': Функции k-значной логики. Алгоритм распознавания полноты конечных систем функций k-значной логики. Замкнутый класс и базис замкнутого класса. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик. [1] стр. 50-53, стр. 65-69.
+
*'''Лекция 5''': Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях графа. Теоремы об оценках числа висячих вершин в остовном дереве графа. [3] стр. 77-80, [4] стр. 48-50, [10]
+
*'''Лекция 6''': Графы. Раскраски графов. Хроматическое число графа. Критерий Кёнига двураскрашиваемости графа. Теоремы об оценках хроматического числа графа. [3] стр. 284-285, [4] стр. 152-153, [8].
+
*'''Лекция 7''': Графы. Наследственные свойства графов. Экстремальные графы. Теорема о максимальном числе ребер в графе без треугольников. Теорема Турана о максимальном числе ребер в графе без полного графа с n вершинами. Числа Рамсея и их оценки. [3] стр. 270-276, [4] стр. 28-33.
+
 
+
== Литература ==
+
#Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
+
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
+
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
+
#Оре О. Теория графов. М.: Наука, 1980.
+
#Харари Ф. Теория графов. М.: Мир, 1973.
+
#Kleitman D.J., West D.B.
+
#Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
+
#Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
+
#[[Media:dm-mag-lect1-selezn.pdf|Слайды к лекции 1]]
+
#[[Media:dm-mag-lect5-selezn.pdf|Слайды к лекции 5]]
+
#[[Media:dm-mag-lect6-selezn.pdf|Слайды к лекции 6]]
+
  
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Текущая версия на 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).