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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Лекции)
(Лекции)
Строка 6: Строка 6:
  
 
== Лекции ==
 
== Лекции ==
*'''Лекция 1''': Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число и рекуррентные формулы для них. Примеры. [[Media:dm-mag-lect1-selezn.pdf|Лекция 1]]
+
*'''Лекция 1''': Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число и рекуррентные формулы для них. Примеры. [[Media:dm-mag-lect1-selezn.pdf|Лекция 1]]
*'''Лекция 2''': Свойства комбинаторных чисел. Производящие функции, их применения для подсчета комбинаторных сумм и доказательств комбинаторных тождеств.
+
*'''Лекция 2''': Свойства комбинаторных чисел. Производящие функции, подсчет комбинаторных сумм и доказательство комбинаторных тождеств.
 
*'''Лекция 3''': Принцип включений-исключений.  
 
*'''Лекция 3''': Принцип включений-исключений.  
 
*'''Лекция 4''': Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения, их решения.
 
*'''Лекция 4''': Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения, их решения.

Версия 16:40, 10 февраля 2014

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

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

Объявления

Лекции

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

Литература

  1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
  2. Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.