Теория алгоритмов
Последнее изменение: 14/11/2024 08:45:47Обязательный курс для потока КБ 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.
- Лекция 2 (07.09): Универсальная машина Тьюринга.
Примеры универсальных машин Тьюринга
- Лекция 3 (14.09): Рекурсивные и рекурсивно перечислимые множества. Неразрешимость проблемы остановки.
- Лекция 4 (21.09): Сводимость по Тьюрингу. Примеры неразрешимых проблем. Временная сложность.
- Лекция 5 (28.09): Полиномиальная сводимость. Пример (сведение задачи о гамильтоновом пути к задаче SAT). Класс NP. Принадлежность к NP задач с полиномиальной проверкой.
- Лекция 6 (5.10): Теорема Кука-Левина.
- Лекция 7 (12.10): NP-полнота задач ВЕРШИННОЕ ПОКРЫТИЕ, НЕЗАВИСИМОЕ МНОЖЕСТВО и КЛИКА
Статья Карпа Reducibilty among combinatorial problems
- Лекция 8 (19.10): NP-полнота задач ГАМИЛЬТОНОВ ЦИКЛ, РАЗБИЕНИЕ и РЮКЗАК
- Лекция 9 (02.11): NP-полнота задач 3-СОЧЕТАНИЕ и ТОЧНОЕ ПОКРЫТИЕ 3-ЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ. Псевдополиномиальные алгоритмы. NP-полнота в сильном смысле.
- Лекция 10 (09.11): NP-полнота в сильном смысле задачи 4-РАЗБИЕНИЕ. Сводимость по Тьюрингу.
Литература
- Н.К. Верещагин, А.Х. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. 4-е изд. МЦНМО, 2012.
- C.M. Papadimitriou. Computational complexity. Addison-Wesley, 1995.
Смотрите также: