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

Последнее изменение: 14/12/2024 06:00:03

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

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

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

Зачет для студентов потока КБ 3-го курса пройдет 21-го декабря с 12:50, ауд. 611.

Задачи к зачету

Экзамен для студентов алгоритмического бакалаврита ИРИТ-РТФ пройдет 14-го января с 09:00, ауд. 628.

Вопросы к экзамену

Консультация перед экзаменом пройдет 13-го января с 10:40, ауд. 625.

План курса

  • Лекция 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 + полезная презентация про задачу упаковки в контейнеры (на английском языке)

  • Лекция 12 (30.11): Приближенные полиномиальные схемы. Связь между вполне полиномиальными приближенными схемами и псевдополиномиальными алгоритмами
  • Лекция 13 (07.12): L-сводимость. Класс MAXSNP.
  • Лекция 14 (14.12): Существование алгоритмов с конечной погрешностью для задач из класса MAXSNP. MAXSNP-полные задачи.

Литература

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