Дискретные модели — различия между версиями
Материал из Кафедра математической кибернетики
(→Программа курса) |
(→Литература) |
||
| Строка 19: | Строка 19: | ||
== Литература == | == Литература == | ||
#Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001. | #Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001. | ||
| + | #Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012. | ||
#Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. | #Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. | ||
| + | #Оре О. Теория графов. М.: Наука, 1980. | ||
| + | #Харари Ф. Теория графов. М.: Мир, 1973. | ||
| + | #Kleitman D.J., West D.B. | ||
#Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966. | #Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966. | ||
#Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986. | #Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986. | ||
[[Категория:Лекционные курсы кафедры МК]] | [[Категория:Лекционные курсы кафедры МК]] | ||
Версия 13:06, 16 февраля 2015
Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.
Лектор - доцент Селезнева Светлана Николаевна.
Объявления
Вопросы к экзамену
Программа курса
- Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел.
- Лекция 2: Функции алгебры логики. Замкнутый класс и полная система. Теорема Поста о функциональной полноте. Базис замкнутого класса. Теорема о максимальном числе функций алгебры логики. Предполный класс. Теорема о предполных классах алгебры логики. Результаты Э. Поста о замкнутых классах алгебры логики.
- Лекция 3: Функции k-значной логики. Теоремы о представлении функций k-значной логики в 1-й и 2-й формах и полиномами по модулю k. Полная система. Теорема о полноте системы Поста и следствия из нее. Функция Вебба.
- Лекция 4: Функции k-значной логики. Алгоритм распознавания полноты конечных систем функций k-значной логики. Теоремы Янова и Мучника о существовании замкнутых классов многозначных логик без базиса и со счетным базисом. Особенности многозначных логик.
- Лекция 5: Графы. Деревья, остовные деревья. Алгоритм построения остовного дерева связного графа. Теорема о числе остовных деревьев полного графа. Теорема о двух остовных деревьях графа. Теоремы об оценках числа висячих вершин в остовном дереве графа.
- Лекция 6: Графы. Раскраски графов. Хроматическое число графа. Критерий Кёнига двураскрашиваемости графа. Теоремы об оценках хроматического числа графа.
- Лекция 7: Графы. Наследственные свойства графов. Экстремальные графы. Теорема о максимальном числе ребер в графе без треугольников. Теорема Турана о максимальном числе ребер в графе без полного графа с n вершинами. Числа Рамсея и их оценки.
Литература
- Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
- Алексеев В.Б. Лекции по дискретной математике. М.: Инфра-М, 2012.
- Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
- Оре О. Теория графов. М.: Наука, 1980.
- Харари Ф. Теория графов. М.: Мир, 1973.
- Kleitman D.J., West D.B.
- Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
- Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.
