Детерминированный алгоритм

3) Анализ алгоритмов связан с вопросом «для заданной функции размера и меры вычисления точно определить для данного алгоритма А, решающего проблему Т, либо сложность «для наихудшего случая», либо, при подходящих предположениях, «поведение в среднем» . (Кнут «Искусство программирования»).

4) Сложность задачи – сложность наилучшего алгоритма, известного для ее решения (нижняя оценка сложности алгоритма).

Определение: Будем говорить, что функция есть , если существует константа с такая, что для всех натуральных n.

Основной вопрос теории сложности: с какой стоимостью может быть решена заданная проблема?

(38) а) линейные ; б) быстрее их — ; в) полиномиальные алгоритмы принадлежат к классу , для которых временная сложность порядка , где целое;

г) экспоненциальные – для них не существует оценки .

Определение: Задача «труднорешаема», если для нее не существует «полиномиального» алгоритма.

Замечание: для малых «экспоненциальный» алгоритм может быть быстрее полиномиального.

Класс Р:

1) найти эйлеров цикл на графе из ребер: алгоритм проверки циклов — ; 2) задача Прима-Краскала: городов в плоской стране. Общая длина телефонных линий соединения городов минимальна. Жадный алгоритм находит «остовное» дерево за .

3) Быстрое преобразование Фурье (БПФ) за шагов; 4) Умножение целых чисел по алгоритму Шенхаге-Штрассена (Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.: Мир, 1979.-536 с.) за шагов по сравнению с умножением двух разрядных чисел по традиционному алгоритму .

5) Умножение матриц — .

КЛАСС Е:

1)  построить множество всех подмножеств; 2) все полные подграфы графа или все поддеревья графа.

ЗАДАЧИ, не принадлежащие к классу Р и не принадлежащие к классу Е :

1)  задача «коммивояжера»; 2) задача «составления расписаний при определенных условиях»; 3) задача «оптимальной загрузки емкости (рюкзака, вагонов поезда, самолета и т. д.); 4) задача «распознавания простого числа» и другие.

Определение: Детерминированный алгоритм – алгоритм, в котором переход из одного состояния в другое однозначный. Недетерминированный имеет несколько вариантов перехода (вероятностный переход).

(39) NP-трудные и NP-полные задачи

Определениe: Задача Q полиномиально сводится к задаче R тогда и только тогда, когда выполнены условия:

1)  Существуют функции и , вычисляемые за полиномиальное время ;

2)  Для любого входа и для любого частного случая задачи Q значение — вход частного случая задачи R;

3)  Для любого решения (выхода) задачи R значение — решение задачи Q:

Определение: Если одновременно задача Q полиномиально сводится к задаче R и задача R полиномиально сводится к задаче Q, то задачи Q и R полиномиально эквивалентны.

Определение: Задача является NP-трудной (или NP-сложной), если каждая задача из класса NP полиномиально сводится к ней. Задача является NP-полной, если она входит в класс NP и является NP-трудной.

Другими словами, задача Т является NP-трудной, если она по крайней мере так сложна, как любая задача в NP.

NP-полные задачи – это самые трудные из NP.

Любая NP-полная задача Т принадлежит NPР. Точнее, задача Т принадлежит к классу Р тогда и только тогда, когда Р=NP.

Теорема Кука (задача о выполнимости является NP-полной): F – формула из теории L (ИВ – исчисление высказываний) представлена в КНФ. Существует ли такое распределение истинностных значений высказывательных переменных, при которых формула F выполнима?

Доказательство: Обозначим задачу распределения истинностных значений высказывательных переменных, при которых формула F выполнима, через задачу Т. Задача о выполнимости Т полиномиально сводится к любой NP-трудной задаче, принадлежащей к классу NP, то есть она является NP-полной.

К настоящему времени установлена NP-полнота большого числа задач. Выше были перечислены некоторые задачи, которые не попадают ни в класс Р, ни в класс Е. Все они являются NP-полными.

Проблема состоит в следующем: можем ли мы надеяться, что какая-либо из этих задач имеет полиномиальную сложность?

По-видимому, ответ будет неудовлетворительным. Очень важным аргументом для такого вывода служит тот факт, что все задачи эквивалентны по сложности – стоит нам найти какой-то полиномиальный алгоритм для одной из этих задач, то все эти задачи становятся полиномиально сложны.