• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
5
Кредиты

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

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

Аннотация

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

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

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

Результаты освоения дисциплины

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

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

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

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

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

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

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

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