Алгоритмы и структуры данных 2 2016/2017/152-2 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
.obj (обсуждение | вклад) (→NP-полные задачи) |
.obj (обсуждение | вклад) (→NP-полные задачи) |
||
Строка 14: | Строка 14: | ||
* наличие разреза размера не менее заданного в неориентированном графе; | * наличие разреза размера не менее заданного в неориентированном графе; | ||
* возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе; | * возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе; | ||
− | * задача о расписании экзаменов: можно ли провести ''k'' экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары); | + | * задача о расписании экзаменов: можно ли провести ''k'' экзаменов за ''n'' пар так, чтобы ни одному из ''m'' студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары); |
* задача о сумме подмножества; | * задача о сумме подмножества; | ||
* задача о рюкзаке. | * задача о рюкзаке. | ||
Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное). | Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное). |
Версия 16:33, 17 сентября 2016
NP-полные задачи
На лекциях и семинарах обсуждалась NP-полнота следующих задач:
- выполнимость булевой формулы (SAT);
- выполнимость 3-КНФ (3SAT);
- существование означивания для 3-КНФ, дающего не менее одной истинной и не менее одной ложной литеры в каждой скобке (Not-All-Equal-3SAT);
- существование клики заданного размера в графе;
- существование вершинного покрытия заданного размера в графе;
- существование независимого множества заданного размера в графе;
- наличие гамильтонова пути в ориентированном графе;
- наличие гамильтонова цикла в ориентированном графе;
- существование раскраски графа в три цвета, такой что никакие две смежные вершины не окрашены в один цвет;
- наличие разреза размера не менее заданного в неориентированном графе;
- возможность корректной расстановки мин в игре "Сапер" на произвольном неориентированном графе;
- задача о расписании экзаменов: можно ли провести k экзаменов за n пар так, чтобы ни одному из m студентов не пришлось сдавать два экзамена одновременно? (для каждого студента указаны экзамены, которые ему нужно сдать; на проведение одного экзамена достаточно одной пары);
- задача о сумме подмножества;
- задача о рюкзаке.
Всеми этим задачами можно пользоваться для доказательства NP-полноты других задач (если явно не указано иное).