|
Теория алгоритмов
Последнее изменение: 19/10/2024 12:58:34
Обязательный курс для потока КБ 3-го курса и академического бакалаврита ИРИТ-РТФ.
Лекции по субботам третьей парой (с 12:50), ауд. 611.
Внимание: В субботу 26.10 лекции не будет
Практические занятия по пятницам нечетных недель начиная с 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
Литература
Смотрите также:
|
|