С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 42
Текст из файла (страница 42)
Функция f (n) = ⌈log2 n!⌉ является нижней границей сложности по числу сравнений алгоритмов сортировки массивов длины nЗадачипопарно различных рациональных чисел c помощью сравнений и четырех арифметических операций (в предложении . речь шла о сортировке вещественных чисел).. Функция f (n) = ⌈log2 (n + 1)⌉ является нижней границей сложности по числу сравнений алгоритмов поиска места элемента в упорядоченном массиве длины n попарно различных вещественных чисел c помощью сравнений и четырех арифметических операций..
Пусть известен алгоритм, который по данным c, m, c > 1,1(построитьm ∈ N+ , строит m значащих двоичных цифр числаcm значащих цифр некоторого числа x, 0 < x < 1, — это в данномконтексте означает отыскать первую ненулевую цифру после запятой в двоичной записи этого числа, а затем отбросить все цифрыпосле m цифр, отсчитанных от найденной), и пусть сложность этогоалгоритма есть O( f (m)), где f (m) — некоторая функция такая, что дополнительно известен алгоритм умножения произвольных a, b ∈ N+ ,сложность которого тоже есть O( f (m)), где m = max{λ(a), λ(b)}.
Наоснове этих двух алгоритмов сконструировать алгоритм построениячастного и остатка от деления положительных целых a и b, имеющийсложность O( f (m)), m = max{λ(a), λ(b)}.Указание. Нужно построить q и r такие, что a = qb + r , 0 ¶ r < b, или11a = q + s, 0 ¶ s < 1. Возникновение погрешности при вычисленииможетbbпривести к тому, что найденное q будет отличаться на 1 от точного значения; несколько добавочных проб помогут найти точные q и r , не изменяяоценки O( f (m)) для сложности.11.
Пусть c > 0 и y0 удовлетворяет неравенствам¶ y0 ¶ ; пусть2ccпоследовательность y0 , y1 , y2 , ... получена по рекуррентной формулеyi = 2 yi−1 − ci yi2−1 ,i = 1, 2, ...1Тогда последовательность y0 , y1 , ... сходится к .c. (Продолжение предыдущей задачи.) Пусть c ∈ N+ . Справедливо следующее утверждение . Пусть y0 удовлетворяет неравенствам11¶ y0 ¶ и последовательность y0 , y1 , y2 , ...
получена по рекуррент2ccной формулеyi = 2 ỹi−1 − ci ỹi2−1 ,См. [, разд. .].i = 1, 2, ...,(.)Глава . Сводимостьгде• целое ci таково, что λ(ci ) = λ(c), и если λ(c) > 2i , то первые 2i цифрчисла ci совпадают с соответствующими цифрами числа c, а последующие цифры суть нули, если же λ(c) ¶ 2i , то ci = c;• ỹ0 получается из y0 отбрасыванием всех цифр после первой значащей цифры;• после вычисления значения yi , i > 0, по рекуррентной формуле (.) в нем отбрасываются все цифры, идущие после первых 2i значащих цифр, — это дает значение ỹi .Тогда первые 2i − 3 значащие цифры числа yi совпадают с соответ1при i > 1. Считая этот факт установствующими цифрами числаcленным и используя решение задачи , доказать, что задача деления одного целого числа на другое с остатком линейно сводитсяк задаче умножения двух целых чисел. (Размером входа считаетсяm = max{λ(a), λ(b)}, где a и b — исходные числа, при этом считаем,что m есть число вида 2k ; всюду подразумеваются битовые затраты;если это нужно, можно считать, что сложность f (m) умножения удовлетворяет условиям f (m) ¶ f (2m) ¶ 4 f (m)).Указание.
Соответствующий алгоритм построения частного и остатка ужеописан в этой задаче и задаче . Достаточно доказать, что алгоритм приближенного обращения c, описанный в этой задаче, имеет сложность R(2k )такую, что R(2k ) ¶ γ f (2k ) для некоторой константы γ. Подобрать γ так, чтобыдоказательство проводилось индукцией, и индуктивный переход был основанна неравенствеR(2k ) ¶ R(2k−1 ) + 2 f (2k−1 ) + δ2k−1 ,где константа δ определяется, в частности, тем, какой алгоритм сложениячисел используется.. Верно ли, что для доказательства того, что P = NP, достаточнопоказать, что хотя бы одна задача из NP принадлежит P?. Существуют ли в NP задачи, не являющиеся NP-полными?. Если бы оказалось, что полиномиального алгоритма распознавания простоты натурального числа не существует (забудем обалгоритме Агравала, Кайала и Саксены), то из этого бы следовало,что P 6= NP.. Дизъюнктивная нормальная форма (ДНФ) определяется какC1 ∨ C2 ∨ ...
∨ Cm ,Ci = (li1 ∧ li2 ∧ ... ∧ liki ),i = 1, 2, ..., m,при этом каждое lij является литералом. Задача выполнимости ДНФпринадлежит P.Задачи. Найти ошибку или пробел в следующем доказательстве того,что Sat ∈ P. Очевидно, что любую КНФ можно преобразовать в эквивалентную ДНФ (см. задачу ), поэтому задача выполнимости КНФсводится к задаче выполнимости ДНФ, а эта задача принадлежит P..
Для выполнимой булевой формулы назовем соответствующийнабор значений переменных выполняющим. Если P = NP, то существует полиномиальный алгоритм, который строит выполняющий набордля данной булевой формулы, если эта формула выполнима, и пустоеслово, если формула невыполнима.Приложение AОсновные алгоритмы сортировки и поискаA. СортировкаДля простоты считаем, что требуется упорядочить по возрастаниючисловой массив x1 , x2 , ..., xn с попарно различными элементами. Размер входа — число n.
Мы называем сегментом массива x1 , x2 , ..., xnлюбую его часть xi , xi+1 , ..., xk−1 , xk , 1 ¶ i ¶ k ¶ n, которая по условиюили по построению является упорядоченной.. Пузырьковая сортировка. Последовательным просмотром всехx1 , x2 , ..., xn определяется xi такое, что xi > xi+1 ; затем xi и xi+1 меняются местами, просмотр продолжается с элемента xi+1 и т. д. Темсамым в результате первого просмотра всего массива наибольшийэлемент передвинется на последнее место.
Следующие просмотры начинаются опять сначала, после уменьшения на единицу количествапросматриваемых элементов. Массив будет упорядочен после просмотра, который охватывал только первый и второй элементы, илиже раньше, если при некотором просмотре не обнаружено xi такого,что xi > xi+1 .. Сортировка выбором. Выполняется n − 1 шаг. На i-м шаге (i == 1, 2, ..., n − 1) среди элементов xi , xi+1, ..., xn отыскивается наименьший и переставляется с xi .. Сортировка простыми вставками (два варианта).
Пусть после нескольких шагов сортировки элементы x1 , x2 , ..., xi уже упорядочены (образуют сегмент): x1 < x2 < ... < xi . Тогда на следующем шагеэлемент xi вставляется в этот сегмент таким образом, что элементыx1 , x2 , ..., xi+1 оказываются упорядоченными (сегмент расширяется).В конечном счете получаем сегмент x1 , x2 , ..., xn . В первом вариантесортировки место вставки определяется последовательными сравнениями xi+1 с xi , xi−1 , ..., во втором — последовательными сравнениями xi+1 с x1 , x2 , ...Основные алгоритмы сортировки и поиска. Сортировка бинарными вставками. Отличается от сортировки простыми вставками тем, что место xi в сегменте x1 , x2 , ..., xi−1определяется алгоритмом бинарного поиска (см.
A, п. ).. Сортировка слияниями. Разнообразные виды этой сортировкииспользуют слияние сегментов. Сначала мы рассмотрим процедуруслияния, а затем опишем два варианта сортировки, основанной наэтой процедуре.Сëèÿíèå. Пусть для элементов массива e1 , e2 , ..., em выполненоe1 < e2 < ... < ek и ek+1 < ek+2 < ... < em , k ¶ m. Массив f1 , f2 , ..., fm , который является результатом слияния массивов e1 , e2 , ..., ek и ek+1 , ek+2 , ......, em , можно получить за m шагов.
После i-го шага элементыf1 , f2 , ..., fi уже имеют нужные значения, целые p и q (p + q = i) показывают, сколько элементов из числа e1 , e2 , ..., ek и ek+1 , ek+2 , ..., emуже использовано.Рåêóðñèâíûé âàðèàíò ñîðòèðîâêè ñëèÿíèÿìè. При n = 1 массив упорядочен. Пусть n > 1, тогда массив x1 , x2 , ..., xn разбивается на два примерно равных по длине подмассива x1 , x2 , ..., x⌊n/2⌋и x⌊n/2⌋+1 , x⌊n/2⌋+2 , ..., xn . Сортировка применяется рекурсивно к этимподмассивам, после чего выполняется слияние.Сîðòèðîâêà ôîí Нåéìàíà.
Первоначально элементы массиваx1 , x2 , ..., xn рассматриваются как упорядоченные одноэлементные сегменты. Затем в массиве y1 , y2 , ..., yn образуются упорядоченные сегменты длины 2, получающиеся слиянием x1 и x2 , x3 и x4 , x5 и x6 , ...Последний сегмент будет иметь один или два элемента в зависимости от четности n. Полученные сегменты сливаются в упорядоченныесегменты длины 4 (кроме последнего, который тоже упорядочен, но,возможно, имеет длину 1, 2 или 3), они последовательно попадаютв массив x1 , x2 , ..., xn . Процесс укрупнения сегментов продолжаетсядальше. В некий момент массив x1 , x2 , ..., xn или y1 , y2 , ..., yn содержиттолько один упорядоченный сегмент.. Быстрая сортировка. Эта сортировка основывается на процедуре разбиения массива.
Перед описанием сортировки мы рассмотрим эту процедуру.Рàçáèåíèå. Берется первый элемент массива и сравнивается совсеми остальными. Меньшие его элементы помещаются в начальнуючасть массива, бо́льшие — в конечную. Сам первоначально взятыйэлемент помещается между этими двумя частями, это — то место, которое ему надлежит занимать в упорядоченном массиве. Дополнительный массив для этой процедуры не требуется, достаточно двухпеременных p и q, показывающих, сколько элементов в начальнойПриложение Aи конечной частях уже занято.