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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Вопросы к экзамену)
(Лекции)
Строка 11: Строка 11:
 
*'''Лекция 2''': Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств. Принцип включений-исключений. [[Media:dm-mag-lect2-selezn.pdf|Лекция 2]]
 
*'''Лекция 2''': Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств. Принцип включений-исключений. [[Media:dm-mag-lect2-selezn.pdf|Лекция 2]]
 
*'''Лекция 3''': Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры. [[Media:dm-mag-lect3-selezn.pdf|Лекция 3]]
 
*'''Лекция 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]]
 
  
 
== Литература ==
 
== Литература ==

Версия 12:11, 10 февраля 2015

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

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

Объявления

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

Лекции

  • Лекция 1: Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. Свойства комбинаторных чисел. Лекция 1
  • Лекция 2: Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств. Принцип включений-исключений. Лекция 2
  • Лекция 3: Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры. Лекция 3

Литература

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