Александр Дайняк
Дискретные модели
»
О курсе

В процессе обучения мы рассмотрим общие подходы к решению задач дискретной оптимизации, чтобы после окончания курса слушатели могли уверенно чувствовать себя, когда столкнутся с практически любой задачей оптимизации, поставленной на естественном языке. Мы рассмотрим все этапы: от построения сбалансированной математической модели до написания эффективных алгоритмов её обсчёта.

»
Команда курса
Александр Дайняк
Лектор
Артем Курносов
Семинарист
»
Программа курса
Множества и отношения
1. Отношения (предикаты). Транзитивность, рефлексивность, симметричность, антисимметричность.
2. Композиция отношений. Операция join в базах данных.
3. Отношения частичного порядка. Наибольший/наименьший элемент, максимальные/минимальные элементы. Цепи и антицепи. Оператор skyline в базах данных.
4. Отношения эквивалентности. Классы эквивалентности.
5. Инъекция, сюръекция, биекция, функция. Равномощность. Принцип Дирихле.
Подсчёт и комбинаторные оценки
1. Основные комбинаторные конфигурации: сочетания, размещения (перестановки). Определения «прямые» и через классы эквивалентности.
2. Комбинаторные правила сложения и умножения. Деревья выбора (decision trees).
3. Точное нахождение и оценки количества комбинаторных конфигураций. Понятие «комбинаторного взрыва». Формула Стирлинга и её следствия.
4. Комбинаторные суммы и тождества. Техника двойного подсчёта (смена порядка суммирования).
5. Рекуррентные соотношения. Линейные рекуррентные соотношения с постоянными коэффициентами. Построение рекуррентных соотношений; метод выделенного элемента.

Графы
1. Различные виды графов. Смежность и инцидентность.
2. Матрицы, ассоциированные с графами.
3. Связность. Мосты, точки сочленения. Связность орграфов.
4. Расстояния в графах. Центр графа. Различные возникающие из прикладных задач показатели центральности.
5. Деревья: эквивалентные определения, применение.
6. Обходы графов в ширину, глубину. Эйлеровы и гамильтоновы цепи/циклы.
7. Клики и независимые множества. Паросочетания. Покрытия.
8. Применение линейной алгебры в теории графов: отрисовка графов на плоскости, вычисление PageRank.
Комбинаторика и графы в Python
(Это не самостоятельный пункт программы, а перечисление некоторых вещей, с которыми мы познакомимся по ходу прохождения других пунктов)

1. Использование Python как интерактивного экспериментального инструмента.
2. Релевантные встроенные структуры данных Python.
3. Средства библиотеки itertools для перечисления комбинаторных конфигураций.
4. Библиотека networkx для работы с графами.