Основные алгоритмы сортировки и поиска

Задачи

Hi

Hi

И.

г32

h2

Рис. 25. Построение графа G_F для вершин, б) проведение ребер.

F = ­xi v ­*₂) л (х₂) Л (jq v х₂): а) выбор

Доказано также, что задача распознавания гамильтоновости графа является NP-полной¹. Упомянем еще одну очень известную NP-пол-ную задачу, называемую задачей о рюкзаке. Задано конечное множе­ство U, размер s(u) gN⁺ и стоимость v (u) gN⁺ каждого u e U, а также a, b е N⁺. Существует ли такое подмножество U' с U, что X! s (") ^ ^а,

2 v (u)^ b? ^{u e U} '

u e!7'?

Из теоремы Кука следует, что для решения проблемы Р = NP доста­точно со всей тщательностью рассмотреть какой-нибудь один NP-пол-ный предикат, например, тот же предикат Sat, и ответить на вопрос о его принадлежности классу Р. Если он принадлежит классу Р, то Р = NP в силу NP-полноты рассматриваемого предиката, если не при­надлежит, то Р ф NP, так как найден предикат, принадлежащий NP и не принадлежащий Р. Но этот заманчивый план до сих пор реали­зовать не удалось, усилия многих исследователей не привели к ре­шению этой проблемы, хотя и устоялось мнение, что, скорее всего, РФ NP. Это предположение влечет за собой рекомендацию: если дока­зано, что решаемая практическая задача (при надлежащей формали­зации в виде предиката на словах в алфавите) является NP-полной, то было бы опрометчивостью рассчитывать на нахождение в короткие сроки полиномиального алгоритма ее решения, и лучше попробовать решить эту задачу приближенно.

Многие задачи фактического построения некоторого математиче­ского объекта вписываются в следующую схему: дано х; если су­ществует у такое, что х вместе с у удовлетворяют фиксированно­му условию R{x,y), то найти такое у. Соответствующая задача рас-

Огромное число примеров NP-полных задач собрано в [13].

Глава 7. Сводимость

познавания выглядит так: дано х; требуется определить, существует ли у такое, что х вместе с у удовлетворяют фиксированному условию R{x,у). Мы полагаем, что х и у — это коды некоторых математиче­ских объектов, т. е. слова в некотором алфавите Л.

Пусть задача распознавания связана указанным образом с задачей построения, пусть R{x, у)еР и полином р таков, что если существу­ет какое-то решение задачи построения, то существует и такое реше­ние у, что |у|^р(|х|). Тогда задача распознавания принадлежит NP в соответствии с определением 30.1, причем в качестве сертификата для х выступает это решение у.

В примерах из § 30 по рассмотренным задачам распознавания лег­ко восстанавливаются соответствующие им задачи построения (по­строить набор логических значений переменных; построить делитель данного числа; построить клику в графе, имеющую определенное ко­личество вершин, и т.д.). Для доказательства принадлежности клас­су NP задачи распознавания мы брали в качестве сертификата само решение соответствующей вычислительной задачи.

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

Быстрый алгоритм распознавания наличия какого-то математиче­ского объекта, кодируемого словом из Л*, может в некоторых случа­ях позволить быстро решать и задачу фактического построения этого объекта. Проиллюстрируем это примером.

Пример 32.3. Мы знаем, что задача распознавания простоты нату­рального числа п принадлежит классу Р, — алгоритм Агравала, Кай-ала и Саксены (пример 22.2) имеет битовую сложность 0{т^1г), где т — битовая длина п. Вопрос о существовании полиномиального ал­горитма факторизации (разложения на простые множители) остается без ответа до сих пор при том, что алгоритмы факторизации имеют огромную важность, например, для криптографии. Вернемся в связи с этим вопросом к принадлежащей NP задаче, рассмотренной в при­мере 30.2: для заданных п, k е N⁺, к < п, выяснить, имеется ли у чис­ла п делитель I такой, что 1 < I s= к. Полиномиальный алгоритм реше-

Задачи

ния этой задачи тоже неизвестен, но можно показать, что открытие такого алгоритма—назовем его A — автоматически дало бы полино­миальный алгоритм факторизации (кстати сказать, существование A автоматически следовало бы из равенства Р = NP, если бы оно вдруг было доказано). Для этого можно воспользоваться бинарным поис­ком.

Пусть уже установлено, что n не имеет делителей, меньших n₁, где n₁ < n, и пусть n₂ таково, что n₁ < n₂ < n, и мы интересуемся наи­меньшим принадлежащим отрезку [n_г, n₂] простым множителем чис-

Г ⁿ 1+ ⁿ 21

ла n. Тогда, применяя Aкn, n ₃, где n ₃ = — —^ —^£, мы сузим диапазон поиска примерно вдвое: в зависимости от результата применения A мы перейдем от отрезка [n_ъ n₂] либо к отрезку [n_ъ n ₃], либо к отрез­ку [ n ₃ + 1, n₂]. Первоначально же полагаем n_г = 2,n₂ = n. Применив алгоритм A не более m = [log₂(n + 1)1 раз, мы найдем наименьший простой множитель t числа n. Повторяем те же вычисления для

n' = t (32.2)

и т.д. Общее число простых множителей числа n с учетом их крат­ности ограничено сверху величиной log₂ n, и, значит, величиной m. Битовые затраты каждого деления (32.2) не превосходят Cm², где C — некоторая константа. Если битовая сложность алгоритма A есть O{m^d), то сложность описанного алгоритма факторизации будет до­пускать оценку O{m^d+2), т.е. этот алгоритм будет полиномиальным.

145. Задача умножения квадратных булевых матриц линейно сводится к задаче построения транзитивно-рефлексивного замыка­ния (предполагается, что для сложностей рассматриваемых алгорит­мов построения транзитивно-рефлексивного замыкания выполнено T (З n) = O (T (n))).

Указание. Пусть M_г и M ₂—две булевы матрицы порядка n. Пусть X — бу­лева матрица порядка З n:

0 0 M ₂. \0 0 0 /

Чему равны X²,X³? Воспользоваться формулой (23.1) для транзитивно-ре­флексивного замыкания.

Глава 7. Сводимость

146. Здесь речь идет о линейной сводимости P^Q задач, связан­
ных с мультипликативными операциями над квадратными числовы­
ми матрицами порядка п. Рассматриваются лишь такие алгоритмы
решения задачи Q, для сложности по числу арифметических опера­
ций каждого из которых выполняется соотношение Т (кп) = 0(Т (п)),
к = 2,3.

Требуется показать, что задача умножения произвольных квадрат­ных матриц линейно сводится к задаче

а) умножения симметричных квадратных матриц;

б) умножения верхних треугольных матриц;

в) обращения невырожденных матриц.

Указание. Так же, как в предыдущей задаче, здесь можно прибегнуть к матрицам размера, большего п, используя исходные матрицы как блоки для построения новых матриц. В пункте в) полезно предварительно устано­вить вид матрицы

fl_n М ₁ 0 V1

0 1_п М₂, V0 0 ¹п) где M₁,M₂ — исходные матрицы, 1_п — единичная матрица порядка п.

147. а) Доказать свойство (R2) рациональных функций, сформули­
рованное в § 29.

Указание. Достаточно доказать, что если полином р(х ₁, х₂,...,х_п) тожде­ственно равен нулю на некотором непустом открытом множестве U аШ^п, то этот полином нулевой. При п = 1 утверждение очевидно. Пусть п > 1 и точ­ка v = (v ₁, v ₂,..., v_n)eIR ⁿ такова, что р(у ₁, v ₂,..., v) ф 0. Пусть ueU. Множе­ство U — открытое, поэтому у точки и существует окрестность некоторого радиуса г > 0, целиком принадлежащая U. Пусть I — расстояние от и до v, а с₁,с₂,...,с_п —координаты вектора единичной длины, направленного из и в v. Если t пробегает множество Ж, то формулы

x₁ = u₁+c₁t, x₂ = u₂+c₂t,..., x_n=u_n+c_nt (32.3)

задают прямую в Ш^п, причем при t = 0 получается точка и, а при t = l — точ­ка v. Остается рассмотреть для полинома p (t) одной переменной t, получаю­щегося подстановкой (32.3) в р(х₁,х₂,...,х_п), его значения в точке t = l и на интервале -г <t<r.

б) Для каких целых n ^ 1 справедливо утверждение, что ес­ли произвольный полином с вещественными коэффициентами от х ₁, х₂,...,х_п обращается в нуль на бесконечном подмножестве мно­жества Ж", то этот полином является нулевым?

148. Функция /(n) = |"log₂ n!l является нижней границей сложно­
сти по числу сравнений алгоритмов сортировки массивов длины п

Задачи

попарно различных рациональных чисел c помощью сравнений и че­тырех арифметических операций (в предложении 29.1 речь шла о сор­тировке вещественных чисел).

149. Функция /(n) = [log₂(n + 1)1 является нижней границей слож­
ности по числу сравнений алгоритмов поиска места элемента в упо­
рядоченном массиве длины п попарно различных вещественных чи­
сел c помощью сравнений и четырех арифметических операций.

15 0. Пусть известен алгоритм, который по данным с,т, с > 1,

т е N⁺, строит т значащих двоичных цифр числа - (построить

с т значащих цифр некоторого числа х, 0 < х < 1, — это в данном

контексте означает отыскать первую ненулевую цифру после запя­той в двоичной записи этого числа, а затем отбросить все цифры после т цифр, отсчитанных от найденной), и пусть сложность этого алгоритма есть 0(f(m)), где /(т)—некоторая функция такая, что до­полнительно известен алгоритм умножения произвольных a, b е N⁺, сложность которого тоже есть 0(,f(m)), где m = max{A(a), А(Ь)}. На основе этих двух алгоритмов сконструировать алгоритм построения частного и остатка от деления положительных целых а и Ъ, имеющий сложность 0(f(m)), m = max{A(a), А(Ь)}.

Указание. Нужно построить q и г такие, что a = qb + r, 0 sj г < Ъ, или a-=q + s, 0^5 < 1. Возникновение погрешности при вычислении - может привести к тому, что найденное q будет отличаться на 1 от точного значе­ния; несколько добавочных проб помогут найти точные q и г, не изменяя оценки 0(f(m)) для сложности.

15 1. Пусть о 0 и jo удовлетворяет неравенствам у ^ у₀ ^ -; пусть
последовательность Уо,Ут_,У2> ■■■ получена по рекуррентной формуле

y_i = 2y_i-₁-c_iyf^L _{- 1} , i = l,2,...

Тогда последовательность Уп, y -i, ••• сходится к -.

152. (Продолжение предыдущей задачи.) Пусть c eN+. Справедли­
во следующее утверждение ^г. Пусть у₀ удовлетворяет неравенствам

9~ ^ Уо ^ ~~ и последовательность УсъУъУг» ••• получена по рекуррент­ной формуле

_Vi,

y_i=2y_i-₁-c_iyf₁, i = l,2,..., (32.4)

См. [5, разд. 8.2].

Глава 7. Сводимость

где

• целое с; таково, что А(с_г) = А(с), и если А(с) > 2*, то первые 2^г цифр числа С; совпадают с соответствующими цифрами числа с, а по­следующие цифры суть нули, если же А(с) ^ 2¹, то q = с;

• jo получается из у₀ отбрасыванием всех цифр после первой зна­чащей цифры;

• после вычисления значения у, i > 0, по рекуррентной форму­ле (32.4) в нем отбрасываются все цифры, идущие после пер­вых 2¹ значащих цифр,—это дает значение у.

Тогда первые Т - 3 значащие цифры числа у_{ совпадают с соответ­ствующими цифрами числа - при i > 1. Считая этот факт установ-ленным и используя решение задачи 150, доказать, что задача де­ления одного целого числа на другое с остатком линейно сводится к задаче умножения двух целых чисел. (Размером входа считается m = max{A(a), А(Ь)}, где а и Ъ — исходные числа, при этом считаем, что m есть число вида 2^к; всюду подразумеваются битовые затраты; если это нужно, можно считать, что сложность /(т) умножения удо­влетворяет условиям /(m) sS/(2 m) s= 4/(т)).

Указание. Соответствующий алгоритм построения частного и остатка уже описан в этой задаче и задаче 150. Достаточно доказать, что алгоритм при­ближенного обращения с, описанный в этой задаче, имеет сложность R(2^k) такую, что R(2^k) Ц yf(2^k) для некоторой константы у. Подобрать у так, чтобы доказательство проводилось индукцией, и индуктивный переход был основан на неравенстве

R(2^k)^R(2^k-¹) + 2f(2^k-¹) + 52^k-\

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

153. Верно ли, что для доказательства того, что Р = NP, достаточно показать, что хотя бы одна задача из NP принадлежит Р?

154. Существуют ли в NP задачи, не являющиеся NP-полными?

155. Если бы оказалось, что полиномиального алгоритма распо­знавания простоты натурального числа не существует (забудем об алгоритме Агравала, Кайала и Саксены), то из этого бы следовало, что Р ф NP.

156. Дизъюнктивная нормальная форма (ДНФ) определяется как

C ₁V C ₂V...V C_{m J} q = (Z_aAZ;₂A...AZ;_fc.), i = l,2,..., m,

при этом каждое Ц является литералом. Задача выполнимости ДНФ принадлежит Р.

Задачи

157. Найти ошибку или пробел в следующем доказательстве того, что Sate Р. Очевидно, что любую КНФ можно преобразовать в экви­валентную ДНФ (см. задачу 156), поэтому задача выполнимости КНФ сводится к задаче выполнимости ДНФ, а эта задача принадлежит Р.

158. Для выполнимой булевой формулы назовем соответствующий набор значений переменных выполняющим. Если Р = NP, то существу­ет полиномиальный алгоритм, который строит выполняющий набор для данной булевой формулы, если эта формула выполнима, и пустое слово, если формула невыполнима.

Приложение A

А1. Сортировка

Для простоты считаем, что требуется упорядочить по возрастанию числовой массив х₁, х₂,..., х_п с попарно различными элементами. Раз­мер входа — число п. Мы называем сегментом массива х ₁ ,х₂,...,х_п любую его часть х, x_i+1,..., х_к- ₁, x_k, 1^i^k^n, которая по условию или по построению является упорядоченной.

1. Пузырьковая сортировка. Последовательным просмотром всех
х ₁, х₂,...,х_п определяется x _t такое, что Xj >x_{i +1}; затем x _t и x_i+1 ме­
няются местами, просмотр продолжается с элемента x_i+1 и т.д. Тем
самым в результате первого просмотра всего массива наибольший
элемент передвинется на последнее место. Следующие просмотры на­
чинаются опять сначала, после уменьшения на единицу количества
просматриваемых элементов. Массив будет упорядочен после про­
смотра, который охватывал только первый и второй элементы, или
же раньше, если при некотором просмотре не обнаружено x _t такого,

что Xi>X_i+1.

2. Сортировка выбором. Выполняется п - 1 шаг. На i -м шаге (i = = 1, 2,..., п - 1) среди элементов х₁, х₁₊₁,..., х_п отыскивается наимень­ший и переставляется с x_t.

3. Сортировка простыми вставками (два варианта). Пусть по­сле нескольких шагов сортировки элементы х ₁, х₂,...,Х; уже упорядо­чены (образуют сегмент): х ₁ <х₂ <... <x_t. Тогда на следующем шаге элемент x _t вставляется в этот сегмент таким образом, что элементы х ₁, х₂,...,x_i+1 оказываются упорядоченными (сегмент расширяется). В конечном счете получаем сегмент х ₁ ,х₂,...,х_п. В первом варианте сортировки место вставки определяется последовательными сравне­ниями x_i+1 с X;, х₍-₁,..., во втором — последовательными сравнения­ми x_{i +1} с х₁,х₂,...

Основные алгоритмы сортировки и поиска

4. Сортировка бинарными вставками. Отличается от сортиров­ки простыми вставками тем, что место x_t в сегменте x₁,x₂,...,x_i_₁ определяется алгоритмом бинарного поиска (см. A2, п. 4).

5. Сортировка слияниями. Разнообразные виды этой сортировки используют слияние сегментов. Сначала мы рассмотрим процедуру слияния, а затем опишем два варианта сортировки, основанной на этой процедуре.

Слияние. Пусть для элементов массива е₁,е₂,...,е_т выполнено

^е1 <^е2<... <^ек и ^ек+1 <^ек+2<...<^ет, к^ГП. Массив /₁, /₂, ...,f_m, кото­рый является результатом слияния массивов е ₁, е₂,..., е_к и е_к+1, е_к+2,......,е_т, можно получить за т шагов. После i -го шага элементы f1,f2,...,fi уже имеют нужные значения, целые р и q (p + q = i) по­казывают, сколько элементов из числа е₁,е₂,...,е_к и е_к+1,е_к+2,...,е_т уже использовано.

Рекурсивный вариант сортировки слияниями. При п = 1 мас­сив упорядочен. Пусть п > 1, тогда массив х ₁, х₂,...,х_п разбивает­ся на два примерно равных по длине подмассива х ₁, х₂,..., x _{L n/ 2}j и x\_n/2\+1,x\n/2\+2,...,^хп. Сортировка применяется рекурсивно к этим подмассивам, после чего выполняется слияние.

Сортировка фон Неймана. Первоначально элементы массива х ₁, х₂,...,х_п рассматриваются как упорядоченные одноэлементные сег­менты. Затем в массиве У ₁ ,у₂,..., у_п образуются упорядоченные сег­менты длины 2, получающиеся слиянием х ₁ и х₂, х₃ и х₄, х₅ и х₆,... Последний сегмент будет иметь один или два элемента в зависимо­сти от четности п. Полученные сегменты сливаются в упорядоченные сегменты длины 4 (кроме последнего, который тоже упорядочен, но, возможно, имеет длину 1, 2 или 3), они последовательно попадают в массив х ₁, х₂,...,х_п. Процесс укрупнения сегментов продолжается дальше. В некий момент массив х ₁, х₂,..., х_п или у ₁, у₂,..., у_п содержит только один упорядоченный сегмент.

6. Быстрая сортировка. Эта сортировка основывается на проце­
дуре разбиения массива. Перед описанием сортировки мы рассмот­
рим эту процедуру.

Разбиение. Берется первый элемент массива и сравнивается со всеми остальными. Меньшие его элементы помещаются в начальную часть массива, большие — в конечную. Сам первоначально взятый элемент помещается между этими двумя частями, это—то место, ко­торое ему надлежит занимать в упорядоченном массиве. Дополни­тельный массив для этой процедуры не требуется, достаточно двух переменных р и q, показывающих, сколько элементов в начальной

Приложение A

и конечной частях уже занято. Элемент, взятый первым, расположен на (р + 1)-м месте и сравнивается со следующим за ним. Равенство р + q = п - 1 означает, что разбиение завершено.

Сортировка. Выполняется разбиение; в результате элемент, ранее располагавшийся в массиве первым, занимает нужное место (с неко­торым номером к, 1 ^ к ^ п). Затем быстрая сортировка применяется рекурсивно к сегментам х_г,х₂,...,х_к-_г и х_к+ъ х_к+2..., х_п.

А2. Поиск

Числовой массив х_ъх₂,...,х_п имеет попарно различные элементы. В п. 4 элементы предполагаются упорядоченными по возрастанию.

1. Поиск наименьшего. Просматриваются последовательно х₂, х₃,...,х_пи каждый новый элемент x_t сравнивается с уже найденным наименьшим среди х_ъ х₂,..., х_{-_х.

2. Поиск m -го наименьшего. Элементы х_ъх₂,...,х_п переставля­ются в соответствии с процедурой разбиения (см. алгоритм быст­рой сортировки). Пусть элемент, бывший в исходном массиве пер­вым, после выполнения процедуры стал fc-м, 1 ^ к ^ п. Если т = к, то задача решена. Если т<к, то разыскивается т-e наименьшее сре­ди х_г, х₂,...,х_к-_г; если т > к, то разыскивается (m - fc)-е наименьшее среди х_к+ъх_к+2,...,х_п.

3. Одновременный поиск наименьшего и наибольшего. Эле­менты х_г,х₂,...,х_п просматриваются последовательными парами: х_г,х₂, затем х₃,х₄ и т.д. (последний элемент может остаться без пары). При рассмотрении fc-й пары х_2к-_ъх_2к в ней выбираются наи­меньший и наибольший элементы, которые сравниваются с уже найденными наименьшим и, соответственно, наибольшим среди х_г,х₂, ■■■,х_2к-₂. Если п нечетно, то на последнем шаге х_п сравнива­ется с уже найденными наименьшим и наибольшим среди х_ъх₂,...

4. Бинарный поиск места элемента. Кроме упорядоченного мас­сива х_г < х₂ <... < х_п дано число у, для которого априори может осу­ществляться любая из возможностей

у^х_г, х_г<у ^х₂,..., х_п-₁<у^х_п, х_п<у.

Этим возможностям присваиваются номера 1,2,...,п + 1. Требует­ся найти номер фактически осуществившейся возможности. Пер­воначальный диапазон поиска — от 1 до п + 1. Каждый шаг би-

Основные алгоритмы сортировки и поиска

нарного поиска сужает диапазон примерно вдвое: если перед оче­редным шагом диапазон был от p до q, то y сравнивается с x_r, r =L(p + q) / 2J. При x_r<y диапазон дальнейшего поиска —от r + 1 до q (в дальнейшем рассматривается сегмент x_r+1,x_r+2,...,x_q_₁), в противном случае — от p до r (в дальнейшем рассматривается сег­мент x_p,x_p+1,...,x_r). И так далее до совпадения границ диапазона.

Приложение B

Дата добавления: 2014-01-11