Дискретные модели — различия между версиями
(→Литература) |
(→О проведении экзамена) |
||
| (не показаны 108 промежуточные версии 1 участника) | |||
| Строка 1: | Строка 1: | ||
| − | + | Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр) | |
| − | Лектор - | + | Лекции - 16 ч, отчетность - экзамен. |
| + | |||
| + | Лектор - [[Селезнева Светлана Николаевна]]. | ||
== Объявления == | == Объявления == | ||
| − | + | ==Программа курса== | |
| + | |||
| + | '''Тема 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 ч (одна пара). | ||
| − | За письменную работу можно получить не более | + | За письменную работу можно получить не более 32 баллов. |
Критерии оценок: | Критерии оценок: | ||
| − | не менее | + | не менее 27 баллов - "отлично"; |
| − | 20- | + | 20-26 баллов - "хорошо"; |
13-19 баллов - "удовлетворительно"; | 13-19 баллов - "удовлетворительно"; | ||
| Строка 24: | Строка 51: | ||
'''Примерный перечень типовых задач к экзамену:''' | '''Примерный перечень типовых задач к экзамену:''' | ||
| − | 1) | + | 1) доказать заданное тождество для функций k-значной логики ([3] гл. III 1.1(1-12)); |
| − | 2) | + | 2) записать заданную функцию k-значной логики в 1-й или во 2-й форме при заданном k ([3] гл. III 1.11); |
| − | 3) | + | 3) построить полином по модулю k для заданной функции k-значной логики при заданном простом k ([3] гл. III 2.7); |
| − | 4) | + | 4) выяснить, задается ли полиномом по модулю k заданная функция k-значной логики при заданном составном k ([3] гл. III 2.12); |
| − | 5) | + | 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|'''Примерный вариант экзаменационной работы''']]---> | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] | ||
Текущая версия на 00:09, 6 января 2024
Курс для студентов неинтегрированной магистратуры (1-й курс, 2-й семестр)
Лекции - 16 ч, отчетность - экзамен.
Лектор - Селезнева Светлана Николаевна.
Объявления
Программа курса
Тема 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 ч (одна пара).
За письменную работу можно получить не более 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).
