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

Последнее изменение: 28/11/2024 17:24:14

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

Лекции по субботам третьей парой (с 12:50), ауд. 611.

Внимание: В субботу 16.11 лекции не будет

Практические занятия по пятницам нечетных недель начиная с 20.09 второй парой (с 10:40), ауд. 532.

План курса

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

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

Конспект лекции 1

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

Конспект лекции 2

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

  • Лекция 3 (14.09): Рекурсивные и рекурсивно перечислимые множества. Неразрешимость проблемы остановки.

Конспект лекции 3

  • Лекция 4 (21.09): Сводимость по Тьюрингу. Примеры неразрешимых проблем. Временная сложность.

Конспект лекции 4

  • Лекция 5 (28.09): Полиномиальная сводимость. Пример (сведение задачи о гамильтоновом пути к задаче SAT). Класс NP. Принадлежность к NP задач с полиномиальной проверкой.

Конспект лекции 5

  • Лекция 6 (5.10): Теорема Кука-Левина.

Конспект лекции 6

  • Лекция 7 (12.10): NP-полнота задач ВЕРШИННОЕ ПОКРЫТИЕ, НЕЗАВИСИМОЕ МНОЖЕСТВО и КЛИКА

Конспект лекции 7

Статья Карпа Reducibilty among combinatorial problems

  • Лекция 8 (19.10): NP-полнота задач ГАМИЛЬТОНОВ ЦИКЛ, РАЗБИЕНИЕ и РЮКЗАК

Конспект лекции 8

  • Лекция 9 (02.11): NP-полнота задач 3-СОЧЕТАНИЕ и ТОЧНОЕ ПОКРЫТИЕ 3-ЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ. Псевдополиномиальные алгоритмы. NP-полнота в сильном смысле.

Конспект лекции 9

  • Лекция 10 (09.11): NP-полнота в сильном смысле задачи 4-РАЗБИЕНИЕ. Сводимость по Тьюрингу.
  • Лекция 11 (23.11): Эквивалентность по Тьюрингу задач распознавания и задач оптимизации (на примере задачи коммивояжера). Приближенные алгоритмы.

Конспект лекций 10 и 11 + полезная презентация про задачу упаковки в контейнеры (на английском языке)

Литература

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