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