Курс
Дискретные модели
Александр Дайняк
В процессе обучения мы рассмотрим общие подходы к решению задач дискретной оптимизации, чтобы после окончания курса слушатели могли уверенно чувствовать себя, когда столкнутся с практически любой задачей оптимизации, поставленной на естественном языке. Мы рассмотрим все этапы: от построения сбалансированной математической модели до написания эффективных алгоритмов её обсчёта.
Лектор
Программа курса
1. Отношения (предикаты). Транзитивность, рефлексивность, симметричность, антисимметричность.
2. Композиция отношений. Операция join в базах данных.
3. Отношения частичного порядка. Наибольший/наименьший элемент, максимальные/минимальные элементы. Цепи и антицепи. Оператор skyline в базах данных.
4. Отношения эквивалентности. Классы эквивалентности.
5. Инъекция, сюръекция, биекция, функция. Равномощность. Принцип Дирихле.
2. Композиция отношений. Операция join в базах данных.
3. Отношения частичного порядка. Наибольший/наименьший элемент, максимальные/минимальные элементы. Цепи и антицепи. Оператор skyline в базах данных.
4. Отношения эквивалентности. Классы эквивалентности.
5. Инъекция, сюръекция, биекция, функция. Равномощность. Принцип Дирихле.
1. Основные комбинаторные конфигурации: сочетания, размещения (перестановки). Определения «прямые» и через классы эквивалентности.
2. Комбинаторные правила сложения и умножения. Деревья выбора (decision trees).
3. Точное нахождение и оценки количества комбинаторных конфигураций. Понятие «комбинаторного взрыва». Формула Стирлинга и её следствия.
4. Комбинаторные суммы и тождества. Техника двойного подсчёта (смена порядка суммирования).
5. Рекуррентные соотношения. Линейные рекуррентные соотношения с постоянными коэффициентами. Построение рекуррентных соотношений; метод выделенного элемента.
2. Комбинаторные правила сложения и умножения. Деревья выбора (decision trees).
3. Точное нахождение и оценки количества комбинаторных конфигураций. Понятие «комбинаторного взрыва». Формула Стирлинга и её следствия.
4. Комбинаторные суммы и тождества. Техника двойного подсчёта (смена порядка суммирования).
5. Рекуррентные соотношения. Линейные рекуррентные соотношения с постоянными коэффициентами. Построение рекуррентных соотношений; метод выделенного элемента.
1. Различные виды графов. Смежность и инцидентность.
2. Матрицы, ассоциированные с графами.
3. Связность. Мосты, точки сочленения. Связность орграфов.
4. Расстояния в графах. Центр графа. Различные возникающие из прикладных задач показатели центральности.
5. Деревья: эквивалентные определения, применение.
6. Обходы графов в ширину, глубину. Эйлеровы и гамильтоновы цепи/циклы.
7. Клики и независимые множества. Паросочетания. Покрытия.
8. Применение линейной алгебры в теории графов: отрисовка графов на плоскости, вычисление PageRank.
2. Матрицы, ассоциированные с графами.
3. Связность. Мосты, точки сочленения. Связность орграфов.
4. Расстояния в графах. Центр графа. Различные возникающие из прикладных задач показатели центральности.
5. Деревья: эквивалентные определения, применение.
6. Обходы графов в ширину, глубину. Эйлеровы и гамильтоновы цепи/циклы.
7. Клики и независимые множества. Паросочетания. Покрытия.
8. Применение линейной алгебры в теории графов: отрисовка графов на плоскости, вычисление PageRank.
(Это не самостоятельный пункт программы, а перечисление некоторых вещей, с которыми мы познакомимся по ходу прохождения других пунктов)
1. Использование Python как интерактивного экспериментального инструмента.
2. Релевантные встроенные структуры данных Python.
3. Средства библиотеки itertools для перечисления комбинаторных конфигураций.
4. Библиотека networkx для работы с графами.
1. Использование Python как интерактивного экспериментального инструмента.
2. Релевантные встроенные структуры данных Python.
3. Средства библиотеки itertools для перечисления комбинаторных конфигураций.
4. Библиотека networkx для работы с графами.
Aimasters 2023 © All Rights Reserved. aimasters.msu@gmail.com Персональные данные опубликованы в соответствии со ст.10.1 Федерального закона РФ № 152-ФЗ от 27 июля 2006г. «О персональных данных» с согласия субъекта. Какая-либо иная обработка, в том числе, дальнейшее распространение персональных данных третьими лицами запрещена.
Мы собираем данные Cookies. Оставаясь на сайте, вы соглашаетесь с нашей политикой сбора и обработки персональных данных.
ок