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

2020/2021

Учебный год

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)

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

• Контрольная работа
• Конрольная работа
• экзамен

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

• Промежуточная аттестация (4 модуль)
  0.25 * Конрольная работа + 0.25 * Контрольная работа + 0.5 * экзамен

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

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

• Алексеев В.Е., Таланов В.А. - Графы и алгоритмы - Национальный Открытый Университет "ИНТУИТ" - 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.