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

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

Общее

Свернуть всё Развернуть всё
- Файл
  
  Оргвопросы Файл
  
  Формат курса, структура, требования к выполнению практических заданий.
- Файл
  
  УКД курса Файл
- Задание
  
  Экзамен Задание
  
  Экзаменационная программа - в прилагаемом файле.
Модуль 1. Полный перебор

Выделено
- Файл
  
  Лекция 1. Введение. Полный перебор. Файл
  
  Введение: типы задач, сводимость задач, NP-трудные задачи.
  Метод полного перебора ("грубой силы"). Перебор бинарных строк.
  Задача "0-1 Рюкзак".
- Задание
  
  Задание 1. Решение задачи "Рюкзак" методом полного перебора
  
  Получить оценку
- Файл
  
  Лекция 2 Файл
  
  Генерация обобщённых строк, сочетаний, перестановок.
- Задание
  
  Задание 2. Решение задачи «Вершинное покрытие» методом перебора сочетаний
  
  Получить оценку
- Файл
  
  Лекция 3. Метод ветвей и границ Файл
- Задание
  
  Задание 3. Решение задачи коммивояжёра методом полного перебора и методом ветвей и границ.
  
  Получить оценку
- Файл
  
  Лекция 4. Очередь с приоритетами. Часть 1. Файл
- Файл
  
  Лекция 5. Очередь с приоритетами. Часть 2. Файл
- Задание
  
  Задание 4. МВГ + очередь с приоритетами для задачи коммивояжёра.
  
  Получить оценку
- Файл
  
  Методические указания к модулю Файл
- Тест
  
  Тест 1 (2022)
Модуль 2. Ускорение перебора
- Файл
  
  Лекция 6. Распространение ограничений Файл
- Файл
  
  Лекция 7. Параметризованные алгоритмы. Часть 1. Файл
- Файл
  
  Лекция 8. Параметризованные алгоритмы. Часть 2. Файл
- Задание
  
  Задание 5. Параметризованный алгоритм для вершинного покрытия
  
  Получить оценку
- Файл
  
  Дополнительный тест для задания 5 (параметризованный алгоритм для вершинного покрытия) Файл
- Файл
  
  Лекция 9. Динамическое программирование Файл
- Задание
  
  Тест 2. Задание
  
  Получить оценку
Модуль 3. Приближённые алгоритмы
- Файл
  
  Лекция 10. Приближённые алгоритмы с оценкой точности. Часть 1. Файл
- Файл
  
  Лекция 11. Приближённые алгоритмы с оценкой точности. Часть 2. Файл
- Файл
  
  Лекция 12. Приближённые схемы Файл
- Задание
  
  Задание 6. Полностью полиномиальная приближённая схема для задачи «Рюкзак».
  
  Получить оценку
- Файл
  
  Лекция 13. Эвристические алгоритмы. Файл
  
  1. Жадные эвристики.
  2. Локальный поиск.
- Задание
  
  Задание 7. Локальный поиск (имитация отжига) для задачи «Вершинное покрытие».
  
  Получить оценку
- Задание
  
  Тест 3 Задание
  
  Получить оценку