Дискретные модели — различия между версиями
(→Объявления) |
(→Информация к экзамену) |
||
| Строка 22: | Строка 22: | ||
'''Примерный перечень типовых задач к экзамену:''' | '''Примерный перечень типовых задач к экзамену:''' | ||
| − | 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] гл. VI 1.3-1.8, 1.29); |
| − | 6) | + | 6) построить код заданного остовного дерева полного графа или восстановить остовное дерево полного графа по его коду; |
| − | 7) построить | + | 7) построить остовное дерево для заданного связного графа с заданным числом висячих вершин; |
| − | 8) | + | 8) найти хроматическое число заданного графа ([3] гл. VI 2.18, 2.19); |
| − | 9) найти | + | 9) найти наибольшее число ребер в графе с заданным наследственным свойством ([3] гл. VI 2.8, 2.9, 2.10, 2.17). |
| − | + | ||
| − | 10) | + | |
==Программа курса== | ==Программа курса== | ||
Версия 16:37, 13 апреля 2016
Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.
Лектор - доцент Селезнева Светлана Николаевна.
Объявления
Информация к экзамену
Экзамен проходит в виде письменной работы. На экзамене не разрешается пользоваться никакими материалами. Письменная работа содержит 10 заданий. Задания 1-4 - типовые задачи, каждая из которых оценивается в 3 балла (примерный перечень типовых задач ниже). Каждое из заданий 5-8 - определение или формулировка теоремы с дополнительным вопросом, который проясняет суть определения или теоремы. Каждое из заданий 5-8 оценивается в 3 балла. Задания 9-10 - нестандартные задачи или доказательство теоремы или ее части. Каждое из заданий 9-10 оценивается в 4 балла. Продолжительность работы - 1,5 ч (одна пара).
За письменную работу можно получить не более 30 баллов. Критерии оценок:
не менее 26 баллов - "отлично";
20-25 баллов - "хорошо";
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] гл. VI 1.3-1.8, 1.29);
6) построить код заданного остовного дерева полного графа или восстановить остовное дерево полного графа по его коду;
7) построить остовное дерево для заданного связного графа с заданным числом висячих вершин;
8) найти хроматическое число заданного графа ([3] гл. VI 2.18, 2.19);
9) найти наибольшее число ребер в графе с заданным наследственным свойством ([3] гл. VI 2.8, 2.9, 2.10, 2.17).
Программа курса
- Лекция 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.
- Слайды к лекции 1
- Слайды к лекции 5
- Слайды к лекции 6
