Algorithms of Operations Research

2022/2023

Academic Year

RUS

Instruction in Russian

4

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Elective course

When:

3 year, 4 module

Instructor

Burashnikov, Evgenii

Программа дисциплины

Аннотация

Изучение дисциплины «Алгоритмы исследования операций» базируется на следующих дисциплинах: - Дискретная математика; - Основы и методология программирования; - Алгоритмы и структуры данных; - Исследование операций. Для освоения учебной дисциплины студенты должны владеть следующими знаниями и компетенциями: • знать основные структуры данных и уметь реализовывать и использовать их на одном из языков программирования; • знать основные понятия и алгоритмы дискретной математики, исследования операций • обладать навыками разработки программ на одном или нескольких языках программирования

Цель освоения дисциплины

• Целями освоения дисциплины «Алгоритмы исследования операций» являются овладение студентами теоретическими знаниями и практическими навыками для решения задач из области исследования операций

Планируемые результаты обучения

• Иметь навык оценки сложности задач и алгоритмов
• Иметь навык построения точных алгоритмов
• Уметь реализовывать алгоритмы, подсказанные природой
• Уметь реализовывать эвристические алгоритмы

Содержание учебной дисциплины

• Алгоритмы и алгоритмические модели
• Эвристические алгоритмы
• Алгоритмы подсказанные природой (Nature inspired algorithms)
• Точные методы

Элементы контроля

• Поиск подстроки в строке
  1) Наивный алгоритм 2) Алгоритм Рабина-Карпа ИЛИ Алгоритм Бойера-Мура-Хорспула 3) Алгоритм Кнутта-Мориса-Пратта ИЛИ Алгоритм Ахо-Карасика
• Задача о рюкзаке 0-1
  Требуется реализовать следующие алгоритмы: 1) 2-approx алгоритм 2) ДП на весах или ДП на стоимостях 3) Метод ветвей и границ используя задачу LP или используя только 1 предмет 4) PTAS или FPTAS
• Генетические алгоритмы
  1) Генетический алгоритм для задачи о рюкзаке 2) Генетический алгоритм для задачи коммивояжера
• Локальный поиск
  1) Local search - best-improvement ИЛИ first-improvement 2) Iterated local search ИЛИ Guided local search
• Задача о формировании производственных ячеек
  1) Метод имитации отжига ИЛИ генетический алгоритм со встроенной эвристикой в виде локального поиска
• Задачи маршрутизации транспорта
  1) Алгоритм колонии муравьев ИЛИ Алгоритм колонии пчел

Промежуточная аттестация

• 2022/2023 учебный год 4 модуль
  0.18 * Задача о формировании производственных ячеек + 0.1 * Поиск подстроки в строке + 0.18 * Задачи маршрутизации транспорта + 0.18 * Локальный поиск + 0.18 * Генетические алгоритмы + 0.18 * Задача о рюкзаке 0-1

Список литературы

Рекомендуемая основная литература

• Алексеев, В. Е. Графы и алгоритмы : учебное пособие / В. Е. Алексеев, В. А. Таланов. — 2-е изд. — Москва : ИНТУИТ, 2016. — 153 с. — ISBN 5-9556-0066-3. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/100593 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Рекомендуемая дополнительная литература

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.

Авторы

• Бычков Илья Сергеевич
• Бурашников Евгений Павлович
• Калягин Валерий Александрович