Дискретные модели

Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.

Лектор - доцент Селезнева Светлана Николаевна.

Вопросы к экзамену

1. Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Теорема о рекуррентной формуле числа сочетаний без повторений. Теорема о числе сочетаний с повторениями.
2. Теоремы о свойствах последовательности биномиальных коэффициентов. Формула включений-исключений. Перестановки-"беспорядки". Формула числа перестановок-"беспорядков".
3. Линейные однородные рекуррентные уравнения (ЛОРУ). Лемма о линейной комбинации частных решений ЛОРУ. Характеристический многочлен ЛОРУ. Лемма о простом корне характеристического многочлена ЛОРУ и частном решении этого ЛОРУ. Теорема об общем решении ЛОРУ, характеристический многочлен которого имеет только простые корни. Лемма о кратном корне характеристического многочлена ЛОРУ и частном решении этого ЛОРУ. Теорема об общем решении ЛОРУ, характеристический многочлен которого имеет кратные корни. Линейные неоднородные рекуррентные уравнения (ЛНРУ) и соответствующие им ЛОРУ. Теорема об общем решении ЛНРУ. Теорема о частном решении ЛНРУ.
4. Транспортная сеть, поток в сети, величина потока в сети. Сечения, пропускная способность сечения. Теорема Форда-Фалкерсона о величине максимального потока в транспортной сети. Алгоритм построения максимального потока в сети.
5. Графовая модель задачи распределения рейсов дням. Независимое множество вершин графа, раскраска вершин графа, хроматическое число графа. Критерий двураскрашиваемости графа. Теорема о верхней оценке хроматического числа графа. Теорема о нижней оценке хроматического числа графа.
6. Определение графа интервалов. Клика графа, максимальная клика графа. Последовательное упорядочение клик графа. Алгоритм построения интервального представления графа по последовательному упорядочению клик. Графовая модель задачи управления сигналами светофора. Построение приближенного решения управления сигналами светофора.

Лекции

• Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел. Лекция 1
• Лекция 2: Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств. Принцип включений-исключений. Лекция 2
• Лекция 3: Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры. Лекция 3
• Лекции 4-5: Графы. Транспортная задача. Поток в транспортной сети и его величина. Сечения, пропускная способность сечения. Теорема Форда-Фалкерсона о величине максимального потока в транспортной сети. Алгоритм построения максимального потока в сети. Лекции 4-5
• Лекция 6: Задача выбора маршрутов и ее частный случай - задача распределения рейсов по дням. Графовая модель задачи распределения рейсов. Хроматическое число графа. Критерий двураскрашиваемости графа. Верхние и нижние оценки хроматических чисел графов. Лекция 6
• Лекция 7: Графы интервалов. Применения графов интервалов. Задача регулирования транспорта светофором. Графовая модель задачи управления сигналами светофора. Лекция 7

Литература

1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
3. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
4. Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986.