Линейная сводимость

Задачи

12 2. Игра «Ханойские башни». К горизонтальной доске приделаны три вертикальных столбика. На первый нанизано n дисков, диамет­ры которых убывают вверх (рис. 21). Требуется, перекладывая диски

V/////A

V/////////A

V///////////A

///////////A

/////

/////

Рис. 21. Игра «Ханойские башни». Исходное положение.

по ке.

одному, расположить их в прежнем порядке на третьем столби-

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

123. (Продолжение предыдущей задачи.) Требуется определить временную сложность алгоритма перекладывания дисков в игре «Ха­нойские башни» при условии, что затраты на перекладывание со столбика на столбик i -го по величине диска равна а) i; б) i ²; в) У.

Y2A. Сформулировать правило нахождения частного решения ре­куррентного уравнения a_dy{n) + a_d-_iy{n - 1) +... + a₀y(.n - d) = f (n) для случая, когда f (n) принимает постоянное значение c.

125. Пусть функция f (n) определена для всех n е N+ и пусть a — ненулевое число. Любое определенное для всех n eN решение рекуррентного уравнения y (n) - ay{n - 1) = f (n) имеет вид y(n) =

f (k) a^k

ⁿ

= an (y (0) + 2

Указание. Индукция по n.

k =i

\1Ь. Для чисел Фибоначчи выполнено равенство £ F_i = F_n+2 - 1,

n= 1,2,3,

i = l

Указание. Решением рекуррентного уравнения y (n)- y (n - 1)= F_n, y (0) 1, является y (n)= F_{n +2}.

182 Глава 6. Рекуррентные соотношения и сложность алгоритмов

127. Верно ли, что для любого полинома р{п) найдется полином q{n) (оба с вещественными коэффициентами) такой, что q (n + l)- — q{n) =р{п), и если да, то как различаются степени полиномов р{п) и q{n)?

128. Найти множество всех вещественных последовательностей, удовлетворяющих рекуррентному уравнению у(п + 1) + у{п) = 0.

129. Вернемся к алгоритму V _Rec из § 24. Пусть 1 s= k s= п. Сколько раз при построении множества V_n будет выполнено построение мно­жества V_k?

Ответ. F_n__k.

130. Найти общее решение рекуррентного равенства (24.11) при к = 1. Найти частное решение, удовлетворяющее условию у(0) = 0. (При к = 1 рекурсия (24.10) не приводит к избыточным вычислениям значений U.)

131. Назовем перестановку г_ъг₂,..., z „ чисел 1,...,п критической длины п, если на ней достигается максимум числа сравнений, тре­буемых рекурсивной сортировкой слияниями для массивов длины п. Пусть п > 1, а х_ъ...,X| n/ 2j и Уг> ■■■>У\п/2\ суть некоторые критические перестановки длины ^ и ^. Тогда числа z₁,z₂, ■■■,z_n, равные, со­ответственно,

2х_ъ..., 2 x _{L n/ 2J}, 2у_г - 1,..., 2у_{[п / 21} - 1

образуют критическую перестановку длины п (рис. 22).

Рис. 22. Случай, когда при п = 7 для сортировки слияниями потребуется мак­симальное число сравнений.

13 2. Как выглядят критические перестановки длины 6, 7, 8 и 9, по­лученные с помощью предложенного в предыдущей задаче подхода?

Задачи

133. Имеет место равенство (25.16).
Указание. См. задачу 131.

134. (Продолжение задачи 131, в которой фактически в рекурсив­ной форме описан алгоритм построения некоторой критической пе­рестановки длины п.) Исследовать сложности описанного алгоритма построения некоторой критической перестановки длины п по чис­лу умножений на два и по числу вычитаний единицы. Предложить нерекурсивный алгоритм (например, можно рассмотреть последова­тельное построение критических перестановок, длины которых суть соответственно 1, 2,..., п) и исследовать его сложности по названным операциям.

135. Чему равно наименьшее п вида 2^к, для которого число срав­нений при рекурсивной сортировке слияниями превосходит [log₂ n il?

136. Оценка (25.22) является следствием оценки T _RS(n) = A(n) + + А*(п)-2.

137. Для сложности алгоритма бинарного поиска места элемента в упорядоченном массиве обосновать рекуррентное неравенство

(1, еслип = 1,

TnsM^ г\п\Л

tbsIIj\)+1> еслип > 1,

не прибегая к известному явному выражению для T _BS(n). Из этого рекуррентного неравенства получить оценку для T _BS(n).

138. Указать алгоритм построения пересечения п полуплоскостей

щх + Цу + с^О, i = l, 2,..., п,

имеющий временную сложность G(n log n) по общему числу опе­раций.

Указание. Пересечением будет выпуклый многоугольник (возможно, не­ограниченный). Опираясь на алгоритм Шеймоса—Хоя (задача 14), использо­вать стратегию «разделяй и властвуй».

139. По сравнению с теоремами 26.1, 26.2 предложения 25.1, 25.2
представляют собой более сильные утверждения, имеющие к тому же
более широкое применение. Используя эти предложения, получить
асимптотические оценки для

(О, если п = 1,

Kill) +K\l]) +^LP^' еслип > 1, при If (П) = l0g₂ П и If (n) = n log₂ n.

184 Глава 6. Рекуррентные соотношения и сложность алгоритмов

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

141. Обобщить предложенную в этой главе технику решения ре­куррентных неравенств на случай, когда задача с размером входа п

разбивается на s задач, размер каждой из которых — это - или

-, где s — некоторое натуральное число ^2. Как будут выглядеть теоремы 26.1, 26.2 в этом случае?

142. Доказать соотношение (27.10).

Указание. Рассмотреть количество умножений чисел битовой длины 1 в процессе применения алгоритма Карацубы к входу размера т и показать, что G(m) является для него нижней оценкой.

143. а) Для любого е > 0 можно указать JV > 0 такое, что ЗГ_км(т) <
< Г_км(2т) < (3 + е)Т_км(т) при всех т ^ N.

б) Для любого е > 0 можно указать JV > 0 такое, что 7T_St(n) < < r_St(2 n) < (7 + e) T _St(n) при всех n^N.

Указание. См. (27.10), (27.8) и, соответственно, (27.12).

144. Теоремы о рекуррентных неравенствах часто формулируются
иначе. Например, в [4] и [5] теорема дается, с точностью до обо­
значений и используемых слов, в следующем виде. Пусть s — целое
^ 2, и при любом п вида s^k, k = 1, 2,..., вещественная функция /(п)
натурального аргумента удовлетворяет неравенству

f(n)^wf(-) +cn^d, s

где w,c,d — константы, причем w > 0, о 0, d ^ 0. Пусть при этом /(п) не убывает на каждом отрезке [ s ^ + l. s *]. Тогда

(o(n^d log n), если d = log _sw,

f(n) = \0{n^d), если d> log _sw,

[о(п^1о&^№), если d< log _sw.

Доказать эту теорему. (Заметим, что в условии теоремы 26.1 нет тре­бования неубывания /(п) на каждом отрезке [s^k + l,s^k], но зато тре­буется, чтобы, например, неравенство (26.1) выполнялось для всех п, а не только для п вида 2^fc.)

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

В этой главе мы рассматриваем только временную сложность алго­ритмов и считаем, что размер входа — это неотрицательное целое число.

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

Определение 28.1. Пусть Р и Q —две вычислительные задачи. Если любому алгоритму A_Q решения задачи Q можно сопоставить такой алгоритм А_Р решения задачи Р, что

Г, {п) = 0{Т_А (п)), (28.1)

то говорят, что задача Р линейно сводится к задаче Q, и пишут P^Q. В специально оговариваемых случаях утверждение Р ^ Q предполага­ет, что рассматриваются лишь такие алгоритмы A_Q, сложности кото­рых удовлетворяют некоторым фиксированным условиям.

Слово «линейно» в этом определении означает лишь то, что слож­ность получаемого алгоритма А_Р не является, скажем, квадратом, ку­бом и т.д. сложности алгоритма A_Q. Возможное присутствие условий (ограничений) на сложности алгоритмов решения задачи Q облегча­ет или просто делает возможным доказательство (28.1). В то же вре­мя, предполагается, что эти ограничения отсекают нерациональные алгоритмы; тогда смысл отношения Р ^ Q состоит в том, что каж-

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

дому приемлемому («хорошему») алгоритму решения задачи Q мы можем сопоставить алгоритм решения задачи Р такой, что выполне­но (28.1).

Пример 28.1. Будем рассматривать задачи умножения М и возве­дения в квадрат S неотрицательных целых чисел, заданных в двоич­ной системе, считая размером входа в первой задаче максимальную из битовых длин чисел п ₁, п₂, а во второй — битовую длину данного числа п (будем обозначать этот размер через т), в качестве затрат будем рассматривать битовые затраты.

Из равенства п ² = п-п следует, что S^M, так как это равенство дает требуемый определением 28.1 алгоритм. Дает ли равенство

(n1 + n2 ⁾² -n ²¹ -n ²²
п ₁ -п ₂ = ------------------ 2 ----- ^;--------------------------------- (28.2)

основание считать, что М ^S? Битовая длина числа п ₁ + п ₂ может оказаться равной т + 1. Если бы для возведения в квадрат исполь­зовался некоторый чрезвычайно нерациональный алгоритм, имею­щий, скажем, сложность m!, то соответствующий алгоритм умноже­ния имел бы сложность порядка ( т + 1)!. Легко видеть, что равенство (т + 1)! = 0(т!) места не имеет. Можно пытаться определить умно­жение через возведение в квадрат как-то иначе, но можно и не отка­зываться от формулы (28.2): при установлении линейной сводимости обычно считается, что сложность любого приемлемого алгоритма вы­полнения какой-либо мультипликативной арифметической операции (умножения, возведения в квадрат, деления и т.д.) удовлетворяет, хо­тя бы для всех достаточно больших т, условиям

1) Т (т)^т,

2) Т (т ) не убывает при возрастании т,

3) Г(2т) «S 4Г(т)

(условие 3 отсекает алгоритмы умножения, сложность которых растет быстрее чем т²). Приняв, что сложность алгоритма A _s удовлетворяет этим условиям, мы имеем

Т_А (т + 1) «S Т_А (2т) «S 4 Т_А (т),

что дает Т_А (m) = 0(T_A (т)) для описанного с помощью (28.2) алго-ритма умножения. Мы используем здесь то, что операции вычитания и деления на 2 имеют сложность 0(т), и то, что Т_А (т) ^ т по усло-

вию 1.

Таким образом, если принимаются ограничения 1—3 для сложно­стей алгоритмов решения задачи S, то М ^ S.

§ 28. Линейная сводимость

Пример 28.2. Из формулы (23.2) нельзя сделать вывода, что зада­ча построения транзитивно-рефлексивного замыкания графа с п вер­шинами (или, в другой терминологии, транзитивно-рефлексивного замыкания булевой матрицы порядка п) линейно сводится к зада­че умножения двух булевых матриц порядка п, так как само число умножений матриц в этой формуле существенно зависит от п. Но мы покажем, что соответствующая линейная сводимость имеет ме­сто, если принять, что для любого из рассматриваемых алгоритмов умножения булевых матриц порядка п его сложность В(п) (примем это упрощенное обозначение) удовлетворяет, хотя бы для всех доста­точно больших п, условиям

1) В(1) = 1,

2) В(п) не убывает при возрастании п,

3) 4 B (n)^ B (2 n)^8 B (n).

Комментарий к условию 3. Неравенство В (2п) s= 8В(п) отсекает те алгоритмы умножения булевых матриц, сложность которых рас­тет быстрее чем п³. Алгоритм должен построить п² элементов матри­цы-произведения, поэтому его сложность не может расти медленнее чем п², и в соответствии с этим в ограничения включается неравен­ство 4В(п)^В(2п).

Для булевой матрицы X порядка п будем, как и прежде, обозна­чать ее транзитивно-рефлексивное замыкание через X*.

Пусть G — ориентированный граф с п вершинами и С —его мат­рица смежности. Предположим вначале, что п—четное число: п = 21. Разобьем множество вершин V = { v ₁, v ₂,..., v_2l} графа G на два под­множества У ₁ = { v ₁, v ₂,..., V;} и V₂ = { v _;+1, v_l+2,...,v_2l}, а множество ре­бер графа G — на четыре подмножества Е_{1 1}, Е₁₂,Е_{2 1}, Е₂₂: начало каж­дого из ребер из множества E_pq принадлежит V_p, а конец — V_q, где p, q e{1, 2}. Если исходная матрица С представлена в блочном виде

( 11 с12л

с21 C 22,

где каждый блок—это матрица порядка I, то матрица C_pq несет пол­ную информацию о ребрах из множества E_pq. Рассмотрим пути в гра­фе G, соединяющие вершины из множества У ₁. Назовем ходом путь из вершины в вершину этого множества, представляющий собой

• либо продвижение по ребру, принадлежащему Е_{1 1},

• либо продвижение по ребру, принадлежащему Е₁₂, за которым сле­дует некоторый путь по ребрам из Е₂₂ и затем продвижение по ребру, принадлежащему Е₂₁.

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

Непосредственно видно, что (i, j)-элемент матрицы C _nv(C ₁₂A C *₂A C ₂₁) равен 1, если и только если существует ход, соединяющий вершины

V;, V j G У_г. При этом ясно, что из V; можно добраться в V j О;, V j е V _x) по

ребрам графа G, если и только если существует последовательность хо­дов, приводящая из v_t в у,-, т. е. если и только если (i, _/)-элемент мат­рицы

(C _nV(C ₁₂A C *₂A C ₂₁))*

равен 1. Обозначим эту матрицу F _n. Мы имеем

*21 ^2₂

для некоторых матриц F ₁₂, F ₂₁, F ₂₂, при этом матрица F_pq, р, q g {1, 2}, несет информацию о существовании путей из вершин множества V_p в вершины множества V_q. Рассуждениями, сходными с приведенными выше, можно показать, что

F ₁₂ = F _nA C ₁₂A C *₂, F ₂₁ = C *₂A C ₂₁A F _n, F₂₂ = С*₂₂ V (С*₂ А С₂₁ A F _n А С₁₂ А С*₂);

эти выражения удобны для вычисления матрицы С*: четыре матри­цы F_{p q}, р, q g {1, 2}, можно найти, выполнив два построения транзи-тивно-рефлексивных замыканий, шесть умножений и два сложения матриц порядка Z:

U = С*₂, V = С₁₂ A LT, W = U А С_2Ъ F _n = (C _nV(V A C ₂₁))*, F ₁₂= F _nA V, F₂₁ = W AF_n, F₂₂ = UV(F₂₁AV).

Мы указали рекурсивный переход от матриц порядка 21 к матрицам порядка Z. Учитывая, что С* = С для матрицы первого порядка, мы получаем алгоритм вычисления С* для случаев, когда порядок п мат­рицы равен 2^к, к^О. Пусть для умножения булевых матриц исполь­зуется алгоритм со сложностью В{п), которая удовлетворяет услови­ям 1—3, приведенным в начале этого примера. Для п = 2^к мы име­ем следующее соотношение, которому будет удовлетворять сложность

§ 28. Линейная сводимость

T (n) полученного алгоритма построения транзитивно-рефлексивного замыкания:

0, если k =0, 2 T (2 ^{k -1}) +6 B (2 ^{k -1})+2·2^{2(k -1)}, если k > 0.

,. О, если к = и, _г ___

^ГС2⁵^---------------------------------------------- (^ЖЗ)

В силу условия 3 имеем В (2^-) ^ 4 B (2^fc-²) при fc ^ 2. Дополнительное использование условия 1 дает нам B (2^2fc-1) ^2^2(fc-1) при fc^ 1. Заме­няя 2²*-¹⁵ во второй строке соотношения (28.3) на B (2^fc-1), получаем

0, если k =0, 2 T (2 ^{k -1})+8 B (2 ^{k -1}), если k > 0.

т^к ^' если к = и,

Г(2)*S (28.4)

Докажем по индукции, что

r(2^fcK4 B (2^fc), fc = 0,l,... (28.5)

Для к = 0 это неравенство очевидно, так как ГЦ) = О, ВЦ) = 1. Пусть ЬОи неравенство выполнено для к - 1. Тогда 2Т(2^к-¹) s= 8 B (2^fc-¹), и, как следствие (28.4), мы получаем Т{2^к) ^ 16 B (2^fc-1). В силу условия 3

мы имеем B (2^fc-!) ^ \в{2^к), откуда следует (28.5).

Если п не есть число вида 2^к, то от матрицы С переходим к мат­рице

^С'=»,°

С (Г

порядка 2^к, взяв единичную матрицу I_s некоторого порядка, мень­шего чем порядок матрицы С. Таким образом, порядок матрицы С' меньше, чем 2п, т. е. 2^к < 2п. Из (28.5) следует, что

T (n) = r(2^fc)^4 B (2^fc).

Так как 2^к < 2п и функция В(п) —неубывающая, получаем 4 B (2^fc) ^ ^4В(2п). Отсюда

Т{п) s= 4 B (2 n) SS 4 ■ 8 • В(п) = 32В(п)

для всех п и

Т{п) = 0{В{п)), (28.6)

что и требовалось.

Из сказанного следует, что если использовать для умножения квад­ратных булевых матриц алгоритм со сложностью, растущей медлен­нее, чем п³, и удовлетворяющей условиям 1—3, то можно строить тран-зитивно-рефлексивное замыкание со сложностью, растущей медлен­нее, чем сложность алгоритма Уоршелла (пример 23.2). Напомним, что

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

алгоритм Штрассена умножения матриц, модифицированный для бу­лева случая (пример 27.2), имеет сложность O (n ^1о&⁷). Но для неболь­ших значений n условия 1—3 здесь выполняться не будут. Однако со­отношение (28.6) можно доказать при более слабых предположени­ях, чем использованные выше, и обсуждавшееся доказательство не по­требует больших изменений. А именно, достаточно предположить, что B{n) удовлетворяет условиям 2—3 для n > n₀, где n ₀ — некоторое на­туральное число (см. задачу 143б). Получится оценка T{n) s= cB{n), где c зависит от B (n ₀), но эта зависимость не влияет на (28.6).

Для нахождения транзитивно-рефлексивного замыкания ориенти­рованного графа с n вершинами существует алгоритм, сложность ко­торого допускает оценку O (n ²>⁸²), или, более точно, оценку O (n ^1о&7).

Как показывает последний пример, если P ^ Q, то прогресс в уме­нии быстро решать задачу Q может в некоторых случаях обеспечить прогресс и в умении быстро решать задачу P. Но это не всегда так. Допустим, что n является нижней границей сложности для алгорит­мов решения задачи Q и в то же время для задачи P имеется алго­ритм решения со сложностью, меньшей n. Согласно определению 28.1 мы имеем P ^ Q, но наличие этой линейной сводимости ничего не дает для продвижения в умении быстро решать задачу P.

Отношение линейной сводимости, очевидно, рефлексивно. Если не рассматривать упомянутых в определении 28.1 дополнительных условий, то это отношение будет транзитивным. В тех случаях, когда такие условия наложены, необходима осмотрительность: если для за­дач P, Q и R мы имеем P ^ Q при некоторых условиях на сложность алгоритмов решения Q, а также Q ^ R при соответствующих условиях на сложность алгоритмов решения R, то чтобы на основании этого утверждать, что P ^R, надо дополнительно установить, что сложно­сти тех алгоритмов решения задачи Q, которые сопоставляются алго­ритмам решения задачи R, удовлетворяют условиям, налагаемым на сложности алгоритмов решения задачи Q при доказательстве отноше­ния P^Q. Это обстоятельство иногда безосновательно игнорируется.

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