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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
Строка 1: Строка 1:
 +
Программа обязательного курса для студентов магистратуры, 1-й курс, 2-й семестр.
 +
 +
== Лекторы ==
 +
[[Селезнева Светлана Николаевна|Селезнева С.Н.]]
 +
 +
== Объявления ==
 +
 +
== Лекции ==
 +
*Лекция 1: Элементы комбинаторики: размещения, перестановки, сочетания, размещения с повторениями, сочетания с повторениями. Их число, рекуррентные формулы и свойства.
 +
*Лекция 2: Элементы комбинаторики: биномиальные и полиномиальные коэффициенты, их свойства.
 +
*Лекция 3: Отношения на множествах. Формула включений-исключений. Отношения эквивалентности и частичного порядка.
 +
*Лекция 4: Рекуррентные уравнения. Линейные однородные и неоднородные рекуррентные уравнения, их общие решения.
 +
*Лекция 5: Графы. Транспортная задача. Теорема Форда-Фалкерсона. Алгоритм построения максимального потока в сети.
 +
*Лекция 6: Графы интервалов. Применения графов интервалов. Задача регулирования транспорта светофором. Графовая модель задачи управления сигналами светофора.
 +
*Лекция 7: Задача выбора маршрутов и ее частный случай - задача распределения рейсов по дням. Графовая модель задачи распределения рейсов. Хроматическое число графа. Критерий двураскрашиваемости графа. Верхние и нижние оценки хроматических чисел графов.
 +
 +
== Литература ==
 +
#Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, 2001.
 +
#Форд Л.Р., Фалкерсон Д.Р. Потоки в сетях. М.: Мир, 1966.
 
[[Категория:Лекционные курсы кафедры МК]]
 
[[Категория:Лекционные курсы кафедры МК]]

Версия 23:01, 25 декабря 2013

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

Лекторы

Селезнева С.Н.

Объявления

Лекции

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

Литература

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