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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Объявления)
(→‎О проведении экзамена)
 
(не показаны 130 промежуточные версии 1 участника)
Строка 1: Строка 1:
−
Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.
+
Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр)
  
−
Лектор - доцент [[Селезнева Светлана Николаевна]].
+
Лекции - 16 ч, отчетность - экзамен.
 +
 
 +
Лектор - [[Селезнева Светлана Николаевна]].
  
 
== Объявления ==
 
== Объявления ==
  
−
==Вопросы к экзамену==
+
==Программа курса==
  
−
#Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Теорема о рекуррентной формуле числа сочетаний без повторений. Теорема о числе сочетаний с повторениями.
+
'''Тема 1. Многозначные логики'''.
−
#Теоремы о свойствах последовательности биномиальных коэффициентов. Формула включений-исключений. Перестановки-"беспорядки". Формула числа перестановок-"беспорядков".
+
−
#Линейные однородные рекуррентные уравнения (ЛОРУ). Лемма о линейной комбинации частных решений ЛОРУ. Характеристический многочлен ЛОРУ. Лемма о простом корне характеристического многочлена ЛОРУ и частном решении этого ЛОРУ. Теорема об общем решении ЛОРУ, характеристический многочлен которого имеет только простые корни. Лемма о кратном корне характеристического многочлена ЛОРУ и частном решении этого ЛОРУ. Теорема об общем решении ЛОРУ, характеристический многочлен которого имеет кратные корни. Линейные неоднородные рекуррентные уравнения (ЛНРУ) и соответствующие им ЛОРУ. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ.
+
−
#Транспортная сеть, поток в сети, величина потока в сети. Сечения, пропускная способность сечения. Теорема Форда-Фалкерсона о величине максимального потока в транспортной сети. Алгоритм построения максимального потока в сети.
+
−
#Графовая модель задачи распределения рейсов дням. Независимое множество вершин графа, раскраска вершин графа, хроматическое число графа. Критерий двураскрашиваемости графа. Теорема о верхней оценке хроматического числа графа. Теорема о нижней оценке хроматического числа графа.
+
−
#Определение графа интервалов. Клика графа, максимальная клика графа. Последовательное упорядочение клик графа. Алгоритм построения интервального представления графа по последовательному упорядочению клик. Графовая модель задачи управления сигналами светофора. Построение приближенного решения управления сигналами светофора. 
+
  
−
== Лекции ==
+
Лекция 1. Функции k-значной логики. Способы их представления: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.
−
*'''Лекция 1''': Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел. [[Media:dm-mag-lect1-selezn.pdf|Лекция 1]]
+
−
*'''Лекция 2''': Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств. Принцип включений-исключений. [[Media:dm-mag-lect2-selezn.pdf|Лекция 2]]
+
−
*'''Лекция 3''': Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры. [[Media:dm-mag-lect3-selezn.pdf|Лекция 3]]
+
−
*'''Лекции 4-5''': Графы. Транспортная задача. Поток в транспортной сети и его величина. Сечения, пропускная способность сечения. Теорема Форда-Фалкерсона о величине максимального потока в транспортной сети. Алгоритм построения максимального потока в сети. [[Media:dm-mag-lect4-selezn.pdf|Лекции 4-5]]
+
−
*'''Лекция 6''': Задача выбора маршрутов и ее частный случай - задача распределения рейсов по дням. Графовая модель задачи распределения рейсов. Хроматическое число графа. Критерий двураскрашиваемости графа. Верхние и нижние оценки хроматических чисел графов. [[Media:dm-mag-lect6-selezn.pdf|Лекция 6]]
+
−
*'''Лекция 7''': Графы интервалов. Применения графов интервалов. Задача регулирования транспорта светофором. Графовая модель задачи управления сигналами светофора. [[Media:dm-mag-lect7-selezn.pdf|Лекция 7]]
+
  
−
== Литература ==
+
Лекция 2. Алгоритм распознавания полноты в P_k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы.
 +
 
 +
Лекция 3. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным базисом.
 +
 
 +
'''Тема 2. Графы'''.
 +
 
 +
Лекция 4. Графы. Простейшие свойства графов.Деревья, остовные деревья. Число остовных деревьев полного помеченного графа. Оценка числа висячих вершин в остовном дереве графа.
 +
 
 +
Лекция 5. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Оценки хроматического числа графа.
 +
 
 +
Лекция 6. Наследственные свойства графов. Оценка числа ребер в графе с наследственным свойством. Планарные графы, наибольшее число ребер в планарном графе. Наибольшее число ребер в графе без треугольников. Теорема Турана о наибольшем числе ребер в графе без полного графа с n вершинами.
 +
 
 +
Лекция 7. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея.
 +
 
 +
'''Литература'''
 
#Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
 
#Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
−
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.  
+
#Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
−
#Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
+
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
−
#Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
+
#Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 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 ч (одна пара).
 +
 
 +
За письменную работу можно получить не более 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).
 +
<!---[[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).

Источник — «https://mk.cs.msu.ru/index.php?title=Дискретные_модели&oldid=10862»