Алгоритмы и анализ сложности

Тематический план

• Общее
  

  Общее

  • Оргвопросы Файл

    Формат курса, структура, требования к выполнению практических заданий.
    

  • УКД курса Файл
  • Экзамен Задание

    Экзаменационная программа - в прилагаемом файле. 

• Модуль 1. Полный перебор
  Текущая тема
  

  Модуль 1. Полный перебор

  • Лекция 1. Введение. Полный перебор. Файл

    Введение: типы задач, сводимость задач, NP-трудные задачи.

    Метод полного перебора ("грубой силы"). Перебор бинарных строк.

    Задача "0-1 Рюкзак".
    

    
    

  • Задание 1. Решение задачи "Рюкзак" методом полного перебора
  • Лекция 2 Файл

    Генерация обобщённых строк, сочетаний, перестановок.
    

  • Задание 2. Решение задачи «Вершинное покрытие» методом перебора сочетаний
  • Лекция 3. Метод ветвей и границ Файл
  • Задание 3. Решение задачи коммивояжёра методом полного перебора и методом ветвей и границ.
  • Лекция 4. Очередь с приоритетами. Часть 1. Файл
  • Лекция 5. Очередь с приоритетами. Часть 2. Файл
  • Задание 4. МВГ + очередь с приоритетами для задачи коммивояжёра.
  • Методические указания к модулю Файл
  • Тест 1 (2022)
• Модуль 2. Ускорение перебора
  

  Модуль 2. Ускорение перебора

  • Лекция 6. Распространение ограничений Файл
  • Лекция 7. Параметризованные алгоритмы. Часть 1. Файл
  • Лекция 8. Параметризованные алгоритмы. Часть 2. Файл
  • Задание 5. Параметризованный алгоритм для вершинного покрытия
  • Дополнительный тест для задания 5 (параметризованный алгоритм для вершинного покрытия) Файл
  • Лекция 9. Динамическое программирование Файл
  • Тест 2. Задание
• Модуль 3. Приближённые алгоритмы
  

  Модуль 3. Приближённые алгоритмы

  • Лекция 10. Приближённые алгоритмы с оценкой точности. Часть 1. Файл
  • Лекция 11. Приближённые алгоритмы с оценкой точности. Часть 2. Файл
  • Лекция 12. Приближённые схемы Файл
  • Задание 6. Полностью полиномиальная приближённая схема для задачи «Рюкзак».
  • Лекция 13. Эвристические алгоритмы. Файл

    1. Жадные эвристики.

    2. Локальный поиск.

    
    

  • Задание 7. Локальный поиск (имитация отжига) для задачи «Вершинное покрытие».
  • Тест 3 Задание