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

Algorithms of Operations Research

2019/2020
Academic Year
RUS
Instruction in Russian
5
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

Instructors


Grechikhin, Ivan

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

Аннотация

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

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

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

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

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

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

  • Алгоритмы и алгоритмические модели
    Понятие алгоритма. Свойства алгоритма. Формализация понятия алгоритма. Алгоритмические модели. Алгорифмы Маркова. Детерминированная машина Тьюринга. Равнодоступная адресная машина (RAM). Сложность алгоритмов. Алгоритмы для поиска подстро-ки в строке. Наивный алгоритм. Алгоритм Рабина-Карпа. Алгоритм Бойера-Мура. Алго-ритм Бойера-Мура-Хорспула. Алгоритм Кнута-Морриса-Пратта. Анализ сложности алгоритмов поиска подстроки. Сложность задач. Недетерминированная машина Тьюринга. Классы P, NP. NP-полные и NP-трудные задачи. Сводимость задач по Карпу. Задача о выполнимости (SAT). Задача о гамильтоновом цикле. Задача коммивояжера
  • Эвристические алгоритмы
    Эвристические алгоритмы. Алгоритм случайного поиска (random search). Алгоритмы локального поиска (local search). Локальный поиск с рестартами (repeated local search). Итеративный локальный поиск (iterated local search). Управляемый локальный поиск (guided local search). Задача о максимальной клике. Задача о максимальном независимом множестве. Поиск во многих окрестностях (variable neighborhood search). Различные схемы по-иска во многих окрестностях: Variable Neighborhood Descent, Reduced Variable Neighbor-hood Search, Basic Variable Neighborhood Search, General Variable Neighborhood Search. Алгоритм табу поиска. Задача о транспортировке грузов с временными окнами (Vehicle Routing Problem with Time Windows)
  • Алгоритмы подсказанные природой (Nature inspired algorithms)
    Алгоритм имитации отжига (Simulated Annealing). Задача о формировании производст-венных ячеек (cell formation problem). Эволюционные алгоритмы. Рассредоточенный по-иск (scatter search). Квадратичная задача о назначениях (Quadratic Assignment Problem). Эволюционные алгоритмы. Генетические алгоритмы (Genetic Algorithms). Муравьиный алгоритм. Задача о транспортировке грузов (Vehicle Routing Problem)
  • Точные методы
    Точные алгоритмы. Метод ветвей и границ (branch and bound)
Элементы контроля

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

  • неблокирующий Лабораторная работа №1
  • неблокирующий Лабораторная работа №2
  • неблокирующий Экзамен
    Экзамен проводится с использованием асинхронного прокторинга. Прокторинг на платформе Экзамус (https://hse.student.examus.net). К экзамену необходимо подключиться за 15 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям: https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf) Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать. Кратковременным нарушением связи во время экзамена считается прерывание связи до 10 минут. Долговременным нарушением связи во время экзамена считается прерывание связи 10 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
Промежуточная аттестация

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

  • Промежуточная аттестация (4 модуль)
    0.3 * Лабораторная работа №1 + 0.3 * Лабораторная работа №2 + 0.4 * Экзамен
Список литературы

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

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

  • Алексеев В.Е., Таланов В.А. - Графы и алгоритмы - Национальный Открытый Университет "ИНТУИТ" - 2016 - 153с. - ISBN: 5-9556-0066-3 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/100593

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

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