NP-полные задачи. Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да»

Презентация:



Advertisements
Похожие презентации
Класс NP и NP-полные задачи. NP-полнота задачи выполнимости Задача выполнимости булевой функции: Вход: булева функция, заданная формулой Требуется определить,
Advertisements

NP-полнота Основные NP-полные задачи. Задача «Независимое множество» Условие. Задан граф G=(V,E) и целое число k. Вопрос. Существует ли независимое множество.
Классификация задач по классам сложности Классификация задач по классам сложности – (P-сложные, NP-сложные, экспоненциально сложные и др.).P-сложныеNP-сложные.
Вычислительная сложность Классы сложности P и NP. Сергей Казаков, аспирант каф. КТ, НИУ ИТМО.
NP-полнота Теорема Кука. Полиномиальная сводимость Пусть Π 1 =(X 1,Y 1 ) и Π 2 =(X 2,Y 2 ) задачи распознавания. Будем говорить, что Π 1 полиномиально.
Графы Лекция 2. Графы Неориентированным графом (графом) называется тройка (V, E, ), где V и E конечные множества и {X V : | X | = 2}. Ориентированным.
1 Комбинаторные алгоритмы Задача о k-центрах. 2 Метрическая задача o k центрах Дано: Полный граф G = (V, E), стоимости ребер cost: E Q + такие, что для.
Анализ трудоёмкости алгоритмов Анализ трудоёмкости алгоритмов позволяет найти оптимальный алгоритм для решения данной задачи. трудоемкость алгоритма количество.
Раскраски графов Раскраска вершин Пусть Г (V,E,Ф) – граф, раскраска вершин Г в n цветов – отображение f : V {1,2,…,n } Правильная раскраска вершин графа.
Комбинаторные алгоритмы Задача о покрытии. Задача о покрытии множествами Дано: Совокупность U из n элементов, и набор подмножеств U, S = {S 1,…, S k },
Алгоритм Эдмондса Лекция 11. Идея алгоритма Эдмондса Пусть есть некоторое паросочетание M, построим M-чередующийся лес F. Начинаем с множества S вершин.
Основные понятия теории NP-полноты P NP?. Задачи распознавания свойств Класс задач распознавания свойств (ЗРС) – множество проблем, решением которых является.
M-чередующаяся декомпозиция Лекция 10. Нечетная декомпозиция Теорема 9.7 (Lovász [1972] ) Граф является фактор-критическим тогда и только тогда, когда.
1 Приближенные алгоритмы Комбинаторные алгоритмы.
Теория графов Основные определения. Задание графов Графический способ – Привести пример графического задания графа, состоящего из вершин А, В и С, связанных.
Алгоритмы на графах. Задача о максимальном потоке в сетях Требуется от источника к стоку передать максимальное количество энергии. В условиях задачи о.
Алгоритмы на графах Волновой метод. Постановка задачи Постановка задачи. Пусть G – неориентированный связный граф, а и b – две его вершины. Требуется.
Паросочетания в двудольных графах Лекция 8. Паросочетание Паросочетанием в графе G называется множество попарно несмежных ребер.
Построение остовного (покрывающего) дерева графа Преподаватель «И и ИКТ» ГБОУ лицея 1557 Куленчик Олеся Николаевна.
ДМ граф Ж.Алгоритм Дп Управление проектом задание характеристики раскраска Эйлеровость Гамильтоновы графы Кривошеев О.И. МЭСИ, каф. Прикладной математики.
Транксрипт:

NP-полные задачи

Сложность задач Задачи формулируем как множества языков, распознаваемых МТ. То есть, на вход МТ подаётся «вопрос» и она отвечает «да» (входное слово распознаётся) или «нет». Рассматриваем детерминированную машину Тьюринга (ДМТ) и недетерминированную (НМТ) Класс P – множество всех языков, допускаемых ДМТ с полиномиальной временной сложностью, т.е. {L | M ДМТ, полином p(n): временная сложность M оценивается полиномом p(n) и M распознаёт в точности L ( L(M)=L ) } Так же определяется класс NP для НМТ.

Пример задачи из класса NP Задача о клике: Вход: граф G(V,E), число k Требуется определить, содержит ли G клику (полный подграф) размером k. Алгоритм для НМТ: выбираем k вершин графа проверяем, что любые две вершины из выбранных соединены ребром

NP-полные задачи Определение. Язык L 0 NP называется полным для класса NP (NP-полным), если по M ДМТ, такому что L(M) = L 0, с временной сложностью T(n) и L NP можно эффективно построить M ДМТ, L(M) = L с временной сложностью T(p L (n)), где p L (n) – полином. Говорят, что L сводиться к L 0.

NP-полные задачи 1.Выполнимость булевой функции 2.Выполнимость КНФ 3.Выполнимость 3-КНФ 4.Клика размером k 5.Гамильтонов цикл в ориентированном графе 6.Вершинное покрытие k вершинами 7.Рёберное покрытие k рёбрами 8.Раскраска в k цветов 9.k вершин, разрезающих все циклы 10.k рёбер, разрезающих все циклы 11.Разбиение множества чисел на две части с равной суммой 12.Покрытие k множествами