Теория алгоритмов

Последнее изменение: 27/11/2019 11:32:49

Обязательный курс для потока ФИИТ-КБ 3-го курса. Лекции по средам четвертой парой в ауд. 621.

Внимание: вложены задачи к зачету.

Внимание: лекции 4.12 и 11.12 не состоятся из-за командировки лектора. Следующая лекция 18.12.

План курса

  • Лекция 1 (04.09): Машина Тьюринга. Тезис Тьюринга.

Статья Тьюринга "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Volume s2-42, Issue 1 (1937), 230-265.

  • Лекция 2 (11.09): Универсальная машина Тьюринга.

Примеры универсальных машин Тьюринга

  • Лекция 3 (18.09): Рекурсивные и рекурсивно перечислимые множества. Неразрешимость проблемы остановки.
  • Лекция 4 (25.09): Сводимость. Примеры неразрешимых проблем. Временная сложность.
  • Лекция 5 (02.10): Полиномиальная сводимость. Пример (сведение задачи о гамильтоновом пути к задаче SAT). Класс NP. Принадлежность к NP задач с полиномиальной проверкой.
  • Лекция 6 (09.10): Теорема Кука-Левина.
  • Лекция 7 (16.10): NP-полнота задач ВЕРШИННОЕ ПОКРЫТИЕ, НЕЗАВИСИМОЕ МНОЖЕСТВО и КЛИКА
  • Лекция 8 (23.10): NP-полнота задач ГАМИЛЬТОНОВ ЦИКЛ, РАЗБИЕНИЕ и РЮКЗАК.
  • Лекция 9 (06.11): NP-полнота задач 3-СОЧЕТАНИЕ и ТОЧНОЕ ПОКРЫТИЕ 3-ЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ.
  • Лекция 10 (13.11): Псевдополиномиальные алгоритмы. NP-полнота в сильном смысле. NP-полнота в сильном смысле задачи 4-СОЧЕТАНИЕ.
  • Лекция 11 (20.11): Сводимость по Тьюрингу. Эквивалентность по Тьюрингу задач распознавания и задач оптимизации (на примере задачи коммивояжера).
  • Лекция 12 (27.11): Приближенные алгоритмы. Эквивалентность псевдополиномиальных алгоритмов и вполне полиномиальных приближенных схем.

Литература

Смотрите также: