• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

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

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

Аннотация

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

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

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

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

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

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

  • Алгоритмы и алгоритмические модели
  • Эвристические алгоритмы
  • Алгоритмы подсказанные природой (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.