Алгоритмы и структуры данных 2 2017/2018 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→Лекции) |
.obj (обсуждение | вклад) (→Лекции) |
||
| Строка 15: | Строка 15: | ||
* '''12 сентября.''' Доказательство теоремы Кука – Левина. NP-полнота задач 3SAT и MINESWEEPER. | * '''12 сентября.''' Доказательство теоремы Кука – Левина. NP-полнота задач 3SAT и MINESWEEPER. | ||
* '''15 сентября.''' NP-полнота задач о сумме подмножества, рюкзаке, раскраске графа. Соотношение классов NP и EXPTIME. | * '''15 сентября.''' NP-полнота задач о сумме подмножества, рюкзаке, раскраске графа. Соотношение классов NP и EXPTIME. | ||
| + | * '''19 сентября.''' Теорема об иерархии задач по времени. Три подхода к решению NP-трудных задач: эффективные алгоритмы для частных случаев (пример — минимальное вершинное покрытие для дерева), эвристические алгоритмы (пример — 2-приближенный алгоритм поиска минимального вершинного покрытия), экспоненциальные алгоритмы, отличные от полного перебора (алгоритм для поиска вершинного покрытия размера ''k'' в графе с ''m'' ребрами с временем работы ''O''(2<sup>''k''</sup>''m''). | ||
== Страницы групп == | == Страницы групп == | ||
[[Алгоритмы_и_структуры_данных_2_2016/2017/165-1 | группа 165-1]] | [[Алгоритмы_и_структуры_данных_2_2016/2017/165-1 | группа 165-1]] | ||
Версия 17:22, 19 сентября 2017
Лектор: С. Объедков
Расписание лекций:
вторник 15:10 – 16:30, ауд. 622
пятница 10:30 – 11:50, ауд. 509
Дополнительная лекция — суббота 23 сентября 12:10 – 13:30, ауд. 622.
Консультации:
понедельник 18:00 – 20:00, к. 324
четверг 16:30 – 18:00, к. 324
Лекции
- 5 сентября. Детерминированная одноленточная машина Тьюринга. Детерминированная многоленточная машина Тьюринга. Имитация многоленточной машины с временем работы t(n) > n на одноленточной машине за время O(t(n)2). Недетерминированная одноленточная машина Тьюринга. Время работы недетерминированной машины Тьюринга. Класс P: определение, примеры задач. Алгоритм верификации. Полиномиальная верифицируемость. Класс NP: определения через алгоритм верификации и недетерминированную машину Тьюринга, их эквивалентность, примеры задач. Класс coNP. Возможное соотношение классов.
- 8 сентября. Полиномиальные сведения. NP-трудные и NP-полные задачи. Формулировка теоремы Кука – Левина. Сведение задачи 3SAT к задаче Not-All-Equal-3SAT и задачи Not-All-Equal-3-SAT к задаче о максимальном разрезе.
- 12 сентября. Доказательство теоремы Кука – Левина. NP-полнота задач 3SAT и MINESWEEPER.
- 15 сентября. NP-полнота задач о сумме подмножества, рюкзаке, раскраске графа. Соотношение классов NP и EXPTIME.
- 19 сентября. Теорема об иерархии задач по времени. Три подхода к решению NP-трудных задач: эффективные алгоритмы для частных случаев (пример — минимальное вершинное покрытие для дерева), эвристические алгоритмы (пример — 2-приближенный алгоритм поиска минимального вершинного покрытия), экспоненциальные алгоритмы, отличные от полного перебора (алгоритм для поиска вершинного покрытия размера k в графе с m ребрами с временем работы O(2km).
