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

Последнее изменение: 07/09/2024 11:00:47

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

Пересдача состоится 25-го января в ауд. 607.

Регламент пересдачи:

  • Письма с номерами заданий из списка задач к зачету будут отсылаться на почту с интервалом 20 минут, начиная с 9 утра 25-го января. (Первый человек получит письмо в 9 утра, второй в 9:20, и т.д.)
  • На решение задания дается один час.
  • Отвечать надо будет устно в том же порядке, в котором выдавались задания. (Первый человек отвечает в 10 утра, второй в 10:20, и т.д.)

Результаты зачета 27-го декабря:

  • В группе КБ-301 (МЕН 311005) не сдал никто.
  • В группе КБ-302 (МЕН 311001) сдали Андреева Е.А., Балдин А.С., Гусейнов А.А., Жуков И.Д., Крючков Д.М., Шевченко А.А., Шумилова Ж.С.

План курса

  • Лекция 1 (20.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 (27.09): Универсальная машина Тьюринга.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Лекция 10 (06.12): NP-полнота в сильном смысле задачи 4-СОЧЕТАНИЕ. Сводимость по Тьюрингу. Эквивалентность по Тьюрингу задач распознавания и задач оптимизации (на примере задачи коммивояжера).

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

  • Лекция 11 (13.12): Приближенные алгоритмы. Эквивалентность псевдополиномиальных алгоритмов и вполне полиномиальных приближенных схем.

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

  • Лекция 12 (19.12): L-сводимость. Класс MAXSNP

Литература

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