Алгоритмы исследования операций

2019/2020

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Кто читает:

Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс по выбору

Когда читается:

3-й курс, 4 модуль

Преподаватели

Бурашников Евгений Павлович

Гречихин Иван Сергеевич

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

Аннотация

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

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

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

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

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

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

• Алгоритмы и алгоритмические модели
  Понятие алгоритма. Свойства алгоритма. Формализация понятия алгоритма. Алгоритмические модели. Алгорифмы Маркова. Детерминированная машина Тьюринга. Равнодоступная адресная машина (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.