Презентация на тему АиФП 6. Ограничение мощи алгориитмов

асcимптотической эффективности и посмотреть, где он находится в иерархии

классов эффективности.
Ответить на вопрос о том, как соотносится эффективность конкретного алгоритма с другими алгоритмами для решения той же задачи.

(НГ) основан на подсчете количества элементов входных данных, которые

следует обработать.
Граница называется плотной, если уже существуют алгоритм, удовлетворяющий этой нижней границе.
Пример: вычисление полинома
P(x)=Anxn+ An-1xn-1+…+A0 для заданных коэффициентов.
Размер входных данных: n.
Любой алгоритм вычисления полинома должен иметь эффективность Ω(n).
Эта граница является плотной, т.к. существует схема Горнера с линейным временем работы.

эффективности алгоритма на основе количества информации, которую он производит.

известна
Нижняя граница неизвестна

длины, узлами которого являются n точек на декартовой плоскости.
Задача

с известной нижней границей: задача единственности элементов.
Приведение: множество из n действительных чисел x1, x2 …, xn прелобразуется в множество точек на плоскости (x1,0), (x2 ,0),…, (xn,0).
Нижняя граница: Ω(n log n)

листьями: h>= ⎡log2l⎤ (1)
Наибольшее количество листьев в таком дереве

равно 2h .

a

a

b

a

c

b

c

да

да

да

нет

нет

нет

решения для произвольного алгоритма сортировки:
Сworst>= ⎡log2 n!⎤ .

a

log2√2πn (n/e)n=
=n log2 n - n log2 e

+ (log2 n)/2 + (log2√2π)/2 ≈
n log2 n .
Вывод: необходимо примерно n log2 n сравнений для сортировки n–элементного списка любым алгоритмом сортировки, который основан на сравнениях.

решает задачу за полиномиальное время, если его временная эффективность

в наихудшем случае принадлежит классу O( p(n)),
где p(n) – полином от размера задачи n.
Задача, решаемая за полиномиальное время называется легкой, в противном случае- трудной.

быть решены с применением некоторого алгоритма за полиномиальное время.

Эти задачи можно рассматривать как множество, которое называют классом Р.
Более формальное определение включает в Р только задачи принятия решения, представляющие собой задачи, выходом которых могут быть только ответы : «да» и «нет».

решения, которые могут быть решены (детерминистическим алгоритмом) за полиномиальное

время.
Этот класс задач называется полиномиальным.

объяснить следующими причинами.
Во-первых, разумно сразу же исключить задачи, не

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

вообще никаких алгоритмов. Такие задачи называются алгоритмически неразрешимыми.

Задача останова

(Алан Тьюринг, 1936 г.) Суть её состоит в следующем:
для данной компьютерной программы необходимо определить, завершится ли выполнение программы или она будет выполняться бесконечно.

А – алгоритм, который решает задачу останова, то есть

для любой программы Р и входных данных I.
Функция преобразования входных данных в выходные может быть описана следующим образом:

неё самой и использовать выход алгоритма А для пары

(Р, Р) для построения программы Q следующим образом:
Завершается, если А(Р,Р)=0, т.е. программа Р не завершается
при входных данных Р;
Q(P)= Не завершается, если А(Р,Р)=1, т.е. программа Р завершается
при входных данных Р.

т.е. программа Q не завершается
при входных данных Q;
Q(Q)= Не

завершается, если А(Q,Q)=1, т.е. программа Q завершается
при входных данных Q.
Мы пришли к противоречию, поскольку ни один из выходов программы Q невозможен, что и завершает доказательство.

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

построения гамильтонова цикла;
Задача о коммивояжере. Требуется найти кратчайший маршрут по n городам с известными целочисленными расстояниями между ними;
Задача о рюкзаке. Обсуждалась в разделе 5;
Задача о разделении. Даны n положительных целых числа. Требуется определить, можно ли разделить их на два непересекающихся подмножества с одинаковыми суммами;
Задача об упаковке корзин. Даны n предметов, размеры которых представляют собой положительные рациональные числа, не превышающие единицу. Их необходимо разместить в наименьшем количестве корзин ёмкостью единица;
Задача о раскраске графа. Обсуждалась в разделе 5;
Задачи целочисленного линейного программирования. Требуется найти максимальное (минимальное) значение линейной функции нескольких целочисленных переменных при условии выполнения конечного множества ограничений в виде линейных равенств и (или) неравенств.

получает в качестве входа экземпляр I задачи принятия решения

и делает следующее:
недетерминистический этап («угадывание»): генерируется строка S, которая рассматривается в качестве кандидата на решение I;
детерминистический этап («проверка»): детерминистический алгоритм получает I и S в качестве входных данных и выдает «да», если S – решение задачи I и «нет» – в противном случае.
НДА является недетерминистическим полиномиальным (НДП), если временная эффективность этапа проверки полиномиальная.

решения, которые могут быть решены НДП алгоритмом.
Этот класс задач

называется недетерминистическим полиномиальным. Большинство задач принятия решения принадлежит классу NP.
Прежде всего этот класс включает все задачи класса Р: Р⊆NP.
Это соотношение истинно, так как если задача принадлежит классу Р, мы можем использовать ДПА, который решает её на этапе проверки НДА, просто проигнорировав строку S, генерируемую на этапе «угадывания».

поиска гамильтонова цикла и т.п. С другой стороны, задача

останова находится среди тех задач принятия решения, о которых известно, что они не входят в класс NP.
Это приводит к наиболее важному открытому вопросу теоретической информатики: является ли класс Р истинным подмножеством NP или на самом деле оба этих класса совпадают, т.е. Р≡NP.

каждая из многих сотен задач принятия решения может быть

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

полиномиально приводимой к задаче принятия решения З2, если имеется

функция t, которая преобразует экземпляры З1 в экземпляры З2 так, что
t отображает все экземпляры З1 с положительным ответом на экземпляры З2 с положительным ответом, и все экземпляры З1 с отрицательным ответом на экземпляры З2 с отрицательным ответом;
t вычислима при помощи алгоритма с полиномиальным временем работы.

принадлежит классу NP и
любая задача NP полиномиально приводима

к D.
Понятие NP-полноты требует полиномиальной приводимости всех задач в NP, как известных, так и неизвестных, к рассматриваемой задаче

этапа:
Показать, что рассматриваемая задача является NP-задачей, т.е. случайным образом

сгенерированная строка может быть проверена на пригодность в качестве решения задачи за полиномиальное время;
Показать, что любая задача из множества NP приводима к рассматриваемой задаче за полиномиальное время. Для выполнения этого этапа достаточно показать, что известная NP-полная задача может быть приведена к рассматриваемой задаче за полиномиальное время.

будет найден детерминистический алгоритм решения одной из NP-полных задач,

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