Бакалавриат
2020/2021
Алгоритмы исследования операций
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Когда читается:
3-й курс, 4 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Бурашников Евгений Павлович
Язык:
русский
Кредиты:
5
Контактные часы:
60
Программа дисциплины
Аннотация
Изучение дисциплины «Алгоритмы исследования операций» базируется на следующих дисциплинах: - Дискретная математика; - Основы и методология программирования; - Алгоритмы и структуры данных; - Исследование операций. Для освоения учебной дисциплины студенты должны владеть следующими знаниями и компетенциями: • знать основные структуры данных и уметь реализовывать и использовать их на одном из языков программирования; • знать основные понятия и алгоритмы дискретной математики, исследования операций • обладать навыками разработки программ на одном или нескольких языках программирования
Цель освоения дисциплины
- Целями освоения дисциплины «Алгоритмы исследования операций» являются овладение студентами теоретическими знаниями и практическими навыками для решения задач из области исследования операций
Планируемые результаты обучения
- Иметь навык оценки сложности задач и алгоритмов
- Уметь реализовывать эвристические алгоритмы
- Уметь реализовывать алгоритмы, подсказанные природой
- Иметь навык построения точных алгоритмов
Содержание учебной дисциплины
- Алгоритмы и алгоритмические моделиПонятие алгоритма. Свойства алгоритма. Формализация понятия алгоритма. Алгоритмические модели. Алгорифмы Маркова. Детерминированная машина Тьюринга. Равнодоступная адресная машина (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.