🗊Презентация Теория сложности алгоритмов

ТЕОРИЯ СЛОЖНОСТИ АЛГОРИТМОВ Глава 6, стр. 135

Понятие временной и емкостной сложности алгоритмов Время работы алгоритма и используемую алгоритмом память можно рассматривать как функции размера задачи n. Обычно рассматривают следующие функции сложности алгоритма: T (n) — временная сложность, C(n) — емкостная сложность. Определение 6.1. Функция f(n) есть O(g(n)), если существует константа C такая, что |f(n)| < C|g(n)| для всех n > 0. Запись f(n) = O(g(n)) читается: "функция f(n) имеет порядок g(n)"

Зависимость времени работы программы от сложности задачи Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого T (n) = O(p(n)), где p(n) — некоторая полиномиальная функция. Алгоритмы, временная сложность которых не поддается подобной оценке, называются экспоненциальными.

Разные алгоритмы имеют различную временную сложность T(n) и влияние того, какие алгоритмы достаточно эффективны, а какие нет, всегда зависит как от размера задачи, так и от порядка временной сложности, а при небольших размерах еще и от коэффициентов в выражении T(n).

Зависимость размеров задач от быстродействия ЭВМ Данные получены для задач, решаемых за один час машинного времени, если быстродействие ЭВМ возрастает в 100 или 1000 раз по сравнению с современными компьютерами.

Сколько вычислений должна потребовать задача, чтобы мы сочли ее труднорешаемой? Общепринято, что если задачу нельзя решить быстрее, чем за полиномиальное время, то ее следует рассматривать как труднорешаемую. При такой схеме классификации задачи, решаемые алгоритмами полиномиальной сложности, будут легко решаемыми. Существуют задачи, для которых в принципе не может существовать полиномиальный алгоритм — это задачи, для которых сама постановка влечет экспоненциальность алгоритма. Например, перечислить все перестановки некоторого множества из n элементов, найти все подмножества заданного множества, найти все каркасы заданного графа и т.п. Такие задачи называются экспоненциальными по постановке.

Практическая оценка временной сложности Время работы цикла любого типа можно оценить по формуле где и предназначены для выполнения начальных действий подготовки цикла и перехода к очередному шагу цикла и зависят от типа цикла, а i — условие выполнения цикла. Время — это время выполнения тела цикла.

Практическая оценка временной сложности Время работы условного оператора вычисляется как сумма времени вычисления условного выражения и максимального времени, которое может потребоваться для вычисления одной из ветвей:

Практическая оценка временной сложности Рассмотрим, например, два программных фрагмента, реализующих вычисление суммы элементов матрицы A[100][3]. Цикл типа Требует при выполнении число операций Тогда алгоритмы потребуют операций.

Анализ временной сложности рекурсивных алгоритмов Функция определяется рекурсивно: a) , т.к. начальном значении нет рекурсивного хода; b) при рекурсивном вызове. Если сложность рекурсивного алгоритма представляется следующей рекурсивной функцией то в зависимости от a и c выражение для сложности имеет вид

P-задачи и NP–задачи Если задача решается за полиномиальное время то обычно считается, что эта задача является легко решаемой. Поэтому среди множества всех задач выделен класс P –задач, для которых существует детерминированный алгоритм, решающий эту задачу за полиномиальное время. Будем называть задачу труднорешаемой, если для ее решения не существует полиномиального алгоритма. Определение 6.2. Класс задач, для решения которых существует недетерминированный алгоритм, решающий эту задачу за полиномиальное время, называется классом NP –задач.

Недетерминированный алгоритм Недетерминированный алгоритм всегда должен выдавать на выходе одно из двух сообщений: "получено решение" или "решение не получено" Смоделировать такой недетерминированный алгоритм T можно, формируя этот алгоритм из двух частей A и B, которые работают последовательно одна за другой и T = A · B. Эти составные части представляют собой недетерминированный алгоритм угадывания и детерминированный алгоритм проверки. Стадия A — недетерминированное начало алгоритма, стадия B — его детерминированное завершение, как правило, отвечающее на вопрос, построил ли недетерминированный алгоритм угадывания A решение или нет.

Детерминированная модель недетерминированного алгоритма Начальный участок алгоритма A формирует какой–то (очередной) вариант данных, которые могут быть (или не быть) решением задачи. Вторая часть — алгоритм B — получает сгенерированный вариант и проверяет, является ли он решением или нет. Если решение не достигнуто, вновь инициируется алгоритм A для получения нового варианта решения

Всякая задача, разрешимая за полиномиальное время детерминированным алгоритмом, разрешима также за полиномиальное время недетерминированным алгоритмом, т.е. класс P –задач входит в класс NP –задач.

Теорема 6.1. Если задача , то существует такой полином p(n), что задача Z может быть решена детерминированным алгоритмом с временной сложностью Теорема 6.1. Если задача , то существует такой полином p(n), что задача Z может быть решена детерминированным алгоритмом с временной сложностью Доказательство. Пусть T — полиномиальный недетерминированный алгоритм решения задачи Z. Тогда существует полином q(n), ограничивающий временную сложность алгоритма T . По определению класса NP , для каждого набора исходных данных длины n найдется некоторая последовательность данных, представляющая собой слово–догадку, длины не более q(n). При обработке этой последовательности–догадки алгоритм T на стадии проверки работает и выдает ответ "да" или "нет" за q(n) шагов. Таким образом, общее число догадок, которые нужно рассмотреть, не превосходит , где k - число символов, из которых состоит слово–догадка (если слово–догадка короче q(n), его можно дополнить пустыми символами и всегда рассматривать как слово длины q(n) ).

Доказательство (продолжение) Доказательство (продолжение) Теперь построим детерминированыый алгоритм решения задачи Z. Для этого достаточно последовательно генерировать все слова–догадки в количестве и для каждой из них запустить детерминированную стадию проверки алгоритма T , который работает не более q(n) шагов. Этот алгоритм даст ответ "да" или "нет" и всегда выполняет действия проверки за время, представляющее собой некоторую константу. Теперь достаточно добавить алгоритм анализа ответа, останавливающий процесс генерации очередного слова–догадки и, следовательно, завершающий весь алгоритм. Построенный нами алгоритм, очевидно, будет детерминированным алгоритмом, работающим с временной сложностью Логарифмируя эту экспоненту, а затем переходя к двоичным логарифмам, получим, что эта сложность не превосходит , где p(n) — полином.

Вопрос о равенстве классов сложности P и NP Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США. На основе накопленного опыта будем представлять себе класс NP так, как от изображен на рис., ожидая, что затененная область, обозначающая NP\P, не пуста.

Что если P=NP? Целый ряд задач, связанных с поиском в экспоненциальном пространстве, получит эффективное полиномиальное решение. К таким задачам относятся многие задачи комбинаторной оптимизации, в том числе проектирование цифровых схем с оптимальным энергопотреблением, задачи составления расписаний, искусственного интеллекта, проверки корректности программного обеспечения, доказательства математических теорем и пр. Можно будет доказать, что полиномиальные рандомизированные алгоритмы, использующие во время работы датчики случайных чисел, могут быть выполнены за полиномиальное же время без использования случайных чисел. То есть случайность оказывается ненужной. Многие широко используемые в настоящее время криптографические алгоритмы и технологии (RSA, SSL, PGP, цифровые подписи и пр.) перестанут работать, так как любая зашифрованная с их помощью информация может быть эффективно расшифрована без знания секретных ключей.

NP –полные задачи В классе NP содержатся NP –полные задачи. Это NP –задачи, для решения которых не существует детерминированного алгоритма, работающего за полиномиальное время. Для доказательства NP –полноты некоторой задачи A можно использовать несколько различных методов: провести независимое доказательство для задачи A; воспользоваться известным доказательством NP –полноты некоторой задачи B и провести доказательство NP –полноты задачи A по аналогии; воспользоваться методом сужения задачи, который заключается в установлении того факта, что поставленная задача A включает в качестве частного случая известную NP –полную задачу; воспользоваться полиномиальной сводимостью. Первые два пути сложны, на практике обычно используется третий или четвертый метод

Примеры NP –полных задач (Выполнимость). Дан набор дизъюнкций на конечном множестве переменных U. Существует ли на U набор значений истинности, при котором выполняются все дизъюнкции из C? Теорема Кука. Задача "выполнимость" есть NP–полная задача. (Трехмерное сочетание). Дано множество , причем W, X и Y — непересекающиеся множества, содержащие одинаковое число элементов q, q =|W|=|X|=|Y|. Содержится ли в M подмножество N ⊆ M, такое, что |N|= q и никакие два разных элемента N не имеют ни одной равной координаты? (Гамильтонов цикл). Дан граф G c n вершинами. Существует ли в графе простой цикл, проходящий через все вершины графа? Простым называется цикл, в котором вершины не повторяются. Таким образом, гамильтонов цикл — это последовательность вершин и дуг (ребер) графа, содержащая все вершины графа G по одному разу, но, может быть, содержащая не все дуги.

Примеры NP –полных задач (Раскрашиваемость). Задан граф G = (V, E) и положительное целое число . Является ли данный неориентированный граф k–раскрашиваемым? Граф называется k–раскрашиваемым, если каждой вершине графа можно поставить в соответствие такое число j (называемое "цветом" вершины ), что любые две соседние вершины графа имеют разный цвет. (Клика). Содержит ли данный граф G = (V, E) некоторую клику мощности не менее заданного целого N. Кликой мощности не менее N называется такое подмножество вершин , что и любые две вершины из соединены ребром в G. (Разбиение). Задано конечное множество A и вес S(a) каждого элемента . Существует ли множество ⊆ A такое, что

Методы решения NP-полных задач В соответствии с представлением алгоритма решения NP–полных задач с помощью алгоритма угадывания и алгоритма проверки программы, реализующие NP–полные задачи, требуют полного перебора вариантов и решаются рекурсивно, так, что алгоритм поиска решения на каждом их шаге рассматривает все возможные варианты решений на глубину 1 и оставшуюся задачу меньшего размера.

Пример Пусть имеется произвольное клеточное поле и плитки размером . Необходимо покрыть данное поле такими плитками. Очевидно, что произвольное клеточное поле можно представить матрицей, в которой клетки заданного поля имеют следующие значения: а) 0 — свободны, б) число n > 0 — клетка занята плиткой с номером n, в) число -1 — не принадлежащие полю клетки. Сначала все свободные клетки заняты нулями, а все клетки, не подлежащие заполнению, числом -1. Приведем пример подлежащего заполнению поля: Если полный перебор укладки плиток не привел к решению, следовательно задача решения не имеет.