Алгоритмы и структуры данных 2 2016/2017/152-2
Материал из Wiki - Факультет компьютерных наук
NP-полные задачи
На лекциях и семинарах обсуждалась NP-полнота следующих задач:
- выполнимость булевой формулы (SAT);
- выполнимость 3-КНФ (3SAT);
- существование означивания для 3-КНФ, дающего не менее одной истинной и не менее одной ложной литеры в каждой скобке (Not-All-Equal-3SAT);
- существование клики заданного размера в графе;
- существование вершинного покрытия заданного размера в графе;
- существование независимого множества заданного размера в графе;
- наличие гамильтонова пути в ориентированном графе;
- наличие гамильтонова цикла в ориентированном графе;
- существование раскраски графа в k цветов, такой что никакие две смежные вершины не окрашены в один цвет (k > 2 — константа);
- наличие разреза размера не менее заданного в неориентированном графе;
- возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
- задача о расписании экзаменов: можно ли провести k экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);
- задача о сумме подмножества;
- задача о рюкзаке.
Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное).
Первое домашнее задание
Распределение задач:
| Студенты | задачи второй части |
|---|---|
| Иван Аустер | 1 |
| Валерий Батурин | 2 |
| Алексей Гавриков | 3 |
| Сергей Горбачев | 4 |
| Петр Жижин | 5 |
| Ксения Закирова | 6 |
| Камиль Лотфуллин | 7 |
| Екатерина Минеева | 8 |
| Никита Нестеров | 9 |
| Олег Николаев | 10 |
| Ярослав Ребенко | 11 |
| Андрей Соколов | 12 |
| Михаил Флоринский | 13 |
| Александр Чернявский | 14 |
| Антон Чернявский | 2 |
| Александр Шарипов | 3 |
Оценки
| Студенты | д/з 1 | д/з 2 | аудиторная работа | накопленная оценка |
|---|---|---|---|---|
| Иван Аустер | 5 | 7 | 7 | 6 |
| Валерий Батурин | 8 | 10 | 8 | 9 |
| Алексей Гавриков | 9 | 10 | 8 | 9 |
| Сергей Горбачев | 5 | 10 | 10 | 8 |
| Петр Жижин | 7 | 10 | 7 | 8 |
| Ксения Закирова | 9 | 10 | 6 | 9 |
| Камиль Лотфуллин | 8 | 7 | 6 | 7 |
| Екатерина Минеева | 10 | 10 | 10 | 10 |
| Никита Нестеров | 8 | 7 | 6 | 7 |
| Олег Николаев | 2 | 7 | 2 | 4 |
| Андрей Соколов | 5 | 8 | 5 | 6 |
| Михаил Флоринский | 8 | 10 | 4 | 8 |
| Александр Чернявский | 9 | 10 | 7 | 9 |
| Антон Чернявский | 9 | 10 | 7 | 9 |
| Александр Шарипов | 1 | 9 | 1 | 4 |
