Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 44

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 44)

Если бы оказалось, что полиномиального алгоритма распознавания простоты натурального числа не существует (забудем обалгоритме Агравала, Кайала и Саксены), то из этого бы следовало,что 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и конечной частях уже занято. Элемент, взятый первым, расположенна (p + 1)-м месте и сравнивается со следующим за ним. Равенствоp + q = n − 1 означает, что разбиение завершено.Сîðòèðîâêà. Выполняется разбиение; в результате элемент, ранеерасполагавшийся в массиве первым, занимает нужное место (с некоторым номером k, 1 ¶ k ¶ n). Затем быстрая сортировка применяетсярекурсивно к сегментам x1 , x2 , ..., xk−1 и xk+1 , xk+2 ..., xn .A.

ПоискЧисловой массив x1 , x2 , ..., xn имеет попарно различные элементы.В п.  элементы предполагаются упорядоченными по возрастанию.. Поиск наименьшего. Просматриваются последовательно x2 ,x3 , ..., xn и каждый новый элемент xi сравнивается с уже найденнымнаименьшим среди x1 , x2 , ..., xi−1 .. Поиск m-го наименьшего. Элементы x1 , x2 , ..., xn переставляются в соответствии с процедурой разбиения (см. алгоритм быстрой сортировки). Пусть элемент, бывший в исходном массиве первым, после выполнения процедуры стал k-м, 1 ¶ k ¶ n.

Если m = k, тозадача решена. Если m < k, то разыскивается m-e наименьшее среди x1 , x2 , ..., xk−1 ; если m > k, то разыскивается (m − k)-е наименьшеесреди xk+1 , xk+2, ..., xn .. Одновременный поиск наименьшего и наибольшего. Элементы x1 , x2 , ..., xn просматриваются последовательными парами:x1 , x2 , затем x3 , x4 и т. д. (последний элемент может остаться безпары).

При рассмотрении k-й пары x2k−1 , x2k в ней выбираются наименьший и наибольший элементы, которые сравниваются с уженайденными наименьшим и, соответственно, наибольшим средиx1 , x2 , ..., x2k−2 . Если n нечетно, то на последнем шаге xn сравнивается с уже найденными наименьшим и наибольшим среди x1 , x2 , ......, xn−1 ..

Бинарный поиск места элемента. Кроме упорядоченного массива x1 < x2 < ... < xn дано число y, для которого априори может осуществляться любая из возможностейy ¶ x1 ,x1 < y ¶ x2 , ...,x n −1 < y ¶ x n ,xn < y.Этим возможностям присваиваются номера 1, 2, ..., n + 1. Требуется найти номер фактически осуществившейся возможности. Первоначальный диапазон поиска — от 1 до n + 1. Каждый шаг би-Основные алгоритмы сортировки и поисканарного поиска сужает диапазон примерно вдвое: если перед очередным шагом диапазон был от p до q, то y сравнивается с xr ,r = ⌊(p + q)/2⌋.

При xr < y диапазон дальнейшего поиска — от r + 1до q (в дальнейшем рассматривается сегмент xr +1 , xr +2 , ..., xq−1), впротивном случае — от p до r (в дальнейшем рассматривается сегмент x p , x p+1 , ..., xr ). И так далее до совпадения границ диапазона.Приложение BОценивание сумм значений монотонныхфункцийПредложение B.. Пусть f — неубывающая или невозрастающаянепрерывная на отрезке [n0 , n1 ] функция, n0 , n1 ∈ Z. ТогдаZ n1Z n1n1Xf (k) ¶f (x) dx + f (n0 ) ¶n0f (x) dx + f (n1 )в случае неубывающей f иZ n1f (x) dx + f (n1 ) ¶n0n1X(B.)n0k = n0Zn1f (k) ¶f (x) dx + f (n0 )(B.)n0k = n0в случае невозрастающей f .Доказательство. Пусть f — неубывающая функция. Рис.

 поnPnP1 −11 −1R n1казывает, чтоf (k) ¶ n f (x) dx (значениеf (k) равно сумме0k = n0...Рис. .nP1 −1k = n0f (k) ¶n1 − 1n1...n0n0 + 1n0 + 2k = n0R n1n0f (x) dx .Оценивание сумм значений монотонных функцийплощадей выделенных прямоугольников с вертикальными сторонами f (n0 ), f (n0 + 1), ..., f (n1 − 1)). Соответственно, рис.

 показывает,...n1PРис. .f (k) ¾k = n0 + 1чтоn1Pf (k) ¾R n1k = n 0 +1n0n1 − 1n1n0n0 + 1n0 + 2...R n1n0f (x) dx .n1Pf (x) dx (значениеf (k) равно сумме пло-k = n 0 +1щадей выделенных прямоугольников с вертикальными сторонамиf (n0 + 1), f (n0 + 2), ... f (n1 )). Это дает нам (B.). Неравенства (B.)доказываются аналогично.pРассмотрим некоторые примеры.

Функция x не убывает на правой полуоси. ИмеемZnZnn pXpppx dx + 1 ¶k¶x dx + n,11k =1т. е.2 p 3 1( n) + ¶33n pXk =1k¶2 p 3 p2( n) + n − ,33и, как следствие,n pXk =1p2 pk = ( n)3 + O( n).3Аналогично выводится, что при любом вещественном α ¾ 0 и n → ∞nPnα+1. (Справедлива ли эта формула при всехвыполняетсяkα ∼k =0α 6= −1?)α+1ФункцияПриложение B1не возрастает при x ¾ 1. ИмеемxZn11dx+ ¶xnэто дает намln n ¶nXk =1nXk =1и, как следствие,nXk =11¶kZn1dx+ 1,x1¶ ln n + 1,k1= ln n + O(1).kПриложение CПроблема орбитC.

Показательная функция и логарифмическая оценкаВ этом разделе приложения рассказывается об одной вычислительной задаче и об эффективном решении ее некоторого частного случая; почти все факты приводятся без доказательств. В разделе C мырассмотрим оставшийся случай с бо́льшими подробностями.Речь идет об одном из вариантов известной «проблемы орбит».Даны две квадратные матрицы A и B одинакового порядка с элементами из поля Q. Существуют ли натуральные m такие, что Am = B?Если да, то надо указать все такие m.

Рассмотрение собственных значений матриц A и B приводит к вопросу о распознавании существования и поиске натуральных m таких, чтоam = b(C.)для данных алгебраических чисел a и b.Напомним, что число a ∈ C называется алгебраическим, если существует полином над полем Q, для которого a является корнем.В качестве такого полинома удобно рассматривать унитарный  полином, т. е. полином с единичным старшим коэффициентом. Можнопоказать, что для всякого алгебраического числа существует единственный унитарный неприводимый над Q полином, для которогоa является корнем. Алгебраическое число a ∈ C называется целым алгебраическим, если соответствующий неприводимый унитарный полином является полиномом над Z, т. е.

Характеристики

Список файлов лекций