Алгоритмы решения вычислительно сложных задач

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

• Общее
  

  Общее

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

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

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

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

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

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

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

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

    
    

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

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

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