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

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

• Общее
  

  Общее

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

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

  • Экзамен Задание

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

    Консультации: 

    • перенесена на 19.01 (суббота), тоже на 17:00
    • 21.01 (понедельник), в 17:00. 

    Аудитория: 302.
    

    Дата экзамена: 22 января 2019 г. (вторник), в 8:30. Аудитория: 302.
    

    
    

  • Объявление. 

    Первая консультация по курсу "Алгоритмы решения вычислительно сложных задач" официально перенесена с пятницы 18.01 на субботу 19.01. Время и место - те же: 17:00, а. 302.

    
    

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

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

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

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

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

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

    
    

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

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

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

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

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

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

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

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

  • Лекция 7. Приближённые алгоритмы. Файл
  • Лекция 8. Приближённые схемы Файл
  • Задание 6. Полностью полиномиальная приближённая схема для задачи «Рюкзак».

    Входные данные – как для задания 1, но добавляется параметр eps.
    Срок: 12.12.18
    
  • Лекция 9. Эвристические алгоритмы Файл

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

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

    
    

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