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

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

• Общее
  

  Общее

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

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

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

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

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

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

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

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

    
    

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

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

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

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

  • Лекция 4. Динамическое программирование Файл
  • Задание 4. Решение задачи "Рюкзак" методом динамического программирования

    Необходимо реализовать "альтернативный" ("двойственный") метод из тех двух, про которые я рассказывал на лекции. Формат входных и выходных данных - такой же, как для задания 1. Пример тестового набора прилагается.

• Модуль 3. Приближённые алгоритмы не доступен
• Модуль 4. Вероятностные и эвристические алгоритмы не доступен
• Экзамен не доступен