С.А. Абрамов - Вычислительная сложность алгоритмов (1123766), страница 13

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

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

Имеется алгоритм A, два слова x, y ∈ A* и k ∈ N .Алгоритм заключается в определении, можно ли из x получить y не более, чем за kопераций, в качестве которых допустимыми являются вычеркивание символа иперестановка двух соседних символов. Доказано, что эта задача NP-полная.2. Имеется квадратная матрица порядка n из нулей и единиц и натуральное число k.Алгоритм заключается в определении, можно ли все единицы покрыть не более чемk прямоугольниками, не покрывая при этом ни одного нуля. Эта задача тожеявляется NP-полной.3. «Задача о рюкзаке». Задано конечное множество U. Для каждого u ∈ U определёнразмер s (u ) и цена v(u ) .

Заданы b, k ∈ N , и спрашивается, можно ли выбратьподмножество U ′ ⊂ U такое, что∑ s(u ) ≤ b , ∑ v(u ) ≥ k .u∈U ′u∈U ′Эта задача тоже является NP-полной.544. Задан набор пар целых чисел (ai , bi ) ∈ Z 2 , i = 1, 2, ... , n , bi ≥ 0 . Рассматриваетсяполином видаn∑a zi =1ibiи спрашивается, есть ли у него корень в комплекснойплоскости, лежащий на единичной окружности ( z = 1 ). Эта задача является NPтрудной, но принадлежность её к классу NP, не установлена.55Задачи1.

Доказать равенства:⎢n⎥ ⎡n⎤n = ⎢ ⎥ + ⎢ ⎥ , n∈N⎣2⎦ ⎢2⎥⎡a ⎤ = − ⎣− a ⎦ , a ∈ Rn ⎢n⎥ ⎡n⎤=k==2 ⎢⎣ 2 ⎥⎦ ⎢⎢ 2 ⎥⎥⎢n⎥ ⎡n⎤⎢n⎥⎡n⎤⇒ ⎢ ⎥ + ⎢ ⎥ = k + k = 2k = n . Если n нечётно, т.е. n = 2k + 1 ⇒ ⎢ ⎥ = k ; ⎢ ⎥ = k + 1⎣2⎦ ⎢2⎥⎣2⎦⎢2⎥⎢n⎥ ⎡n⎤⇒ ⎢ ⎥ + ⎢ ⎥ = k + k + 1 = 2k + 1 = n .⎣2⎦ ⎢2⎥Решение. 1) В случае чётного n решение тривиально: n = 2k ⇒2) Если a ∈ Z , то очевидно, что ⎡a ⎤ = a; ⎣− a ⎦ = − a , что доказывает равенство. Если a неявляется целым, то найдется такое целое число n и такое 0 < ε < 1 , что a = n + ε . Тогда⎡a ⎤ = ⎡n + ε ⎤ = n + 1 , ⎣− a ⎦ = ⎣− n − ε ⎦ = −n − 1 ⇒ ⎡a ⎤ = − ⎣− a ⎦ .2. Доказать равенство:k , n ∈ N, k > 1 ⇒ ⎣log k n ⎦ + 1 = ⎡log k (n + 1)⎤Решение.

Не трудно видеть, что для данного n всегда найдётся такое целое число m,что выполняется оценка: k m ≤ n < k m+1 . Тогда ⎣log k n ⎦ = m . Так как k целое, тоk m < n + 1 ≤ k m+1 , откуда m < log k (n + 1) ≤ m + 1 ⇒ ⎡log k (n + 1)⎤ = m + 1 что и доказываетравенство.3. Считая в алгоритме сортировки простыми вставками операцию обмена a ↔ bреализованной следующим образом: с := a; a := b; b := c, определить, чемуравны TI1 и TI 2 .4.

Имеется железнодорожный разъезд с тупиком (см. рис.), в одной части которогонаходятся 2n вагонов двух типов: n белых и n чёрных. Порядок вагонов не определён.Имеется 3 операции перемещения вагонов: 1) МИМО, 2) В (в тупик) и 3) ИЗ (из тупика).Требуется привести алгоритм сортировки вагонов, в результате работы которого сдругой стороны будет составлена последовательность из 2n вагонов, цвета которыхчередуются.МИМОИЗ2nВРешение. Требуется переправить вагоны справа на лево, изменив их порядок так,чтобы цвета вагонов чередовались. Предлагаемый алгоритм заключается в следующем:если цвет первого вагона формируемого состава не имеет значения, то первый вагонпросто проходит МИМО.

Если цвет первого вагона важен, то с помощью тупика этовсегда можно сделать. Далее, пока имеются вагоны справа, проверяем на совпадениецветов последний вагон слева с первым вагоном справа. Если их цвета не совпадают,56выполняем операцию МИМО, после чего проверяем наличие вагонов в тупике. Если втупике имеются вагоны, то выполняем операцию ИЗ и переходим к следующемувагону справа. При совпадении цветов, отправляем очередной вагон в тупик операциейВ.На псевдокоде предлагаемый алгоритм выглядит следующим образом: исходныйсостав справа обозначен массивом ai, каждый элемент которого принимает значениячёрный или белый.

Операция not меняет значение цвета с белого на чёрный инаоборот, z — текущее количество вагонов в стеке, k — цвет последнего вагонаформируемого состава слева. Основная идея алгоритма заключается в том, что в тупикев один момент времени не могут находиться вагоны разных цветов и в конце каждойитерации цикла если в тупике есть вагоны, то цвет их совпадает с цветом последнеговагона формируемого состава.z := 0; k := a1;for i = 2 to 2n doif k = ai thenВ;z := z + 1;elseМИМО;k := ai;if z > 0 thenИЗ;z := z – 1;k := not k;fifiodНе трудно видеть, что сложность представленного алгоритма по количеству операцийМИМО, В, ИЗ T = O(n) , но из постановки задачи ясно, что сложность любогоалгоритма, решающего задачу, есть Ω(n) , следовательно, сложность представленногоалгоритма T = Θ(n) .5.

Путник стоит перед бесконечной стеной в обе стороны. Известно, что на расстоянии nшагов в одну из сторон находится дверь. Требуется привести алгоритм нахождениядвери путником, сложность которого по числу шагов составляла бы O(n) .Решение. Очевидный алгоритм заключается в следующем: путник на первой итерацииделает один шаг в одну из сторон, затем возвращается и делает один шаг уже в другуюсторону и снова возвращается.

На второй итерации ситуация повторяется, но ужесовершается по два шага в обе стороны. На третьей итерации — три шага и т.д. пока небудетобнаруженадверь.Сложностьтакогоалгоритмасоставляет22 ⋅ (1 + 2 + ... + n) = n(n + 1) = O(n ) , в связи с чем, данный алгоритм не подходит.Предыдущий алгоритм базировался на арифметической прогрессии, что и далоквадратичную сложность. Попробуем оценить сложность подобного алгоритма,базирующегося на геометрической прогрессии. Пусть по прежнему на первой итерациисовершается по одному шагу в одну и другую сторону, тем самым первый членпрогрессии будет равен 1.

Выберем произвольное q ∈ N, q > 1 и на каждой k-йитерации будем совершать q k −1 шагов в обе стороны. Исходя из этих данных,получаем, что количество требуемых алгоритму итераций не превзойдёт log q n + 1 ,57тогда суммарное количество шагов не превзойдёт 2 ⋅qlog q n +1−1qn − 1= 2⋅= O(n) , что иq −1q −1требовалось.6. Доказать асимптотику сложности алгоритма пробных делений (TD), приняв за размер⎛ m2 ⎞*входа битовую длину n: TTD (m = ν (n) ) = Θ⎜⎜ 2 ⎟⎟ .⎝ ⎠Решение. При фиксированной длине числа n, равной m, получаем ограничение назначения n: 2 m−1 ≤ n < 2 m . Согласно постулату Бертрана, в интервале (2 m−1 , 2 m ) найдётсяпростое число n, для определения простоты которого алгоритму пробных делений*( m) :потребуется в точности n − 1 делений. Следовательно, получаем оценки на TTD⎣ 2 ⎦− 1 < Tm−1*TD⎣ ⎦( m) <⎣ 2 ⎦− 1m*2m−1 − 2 < TTD( m) < 2 m − 1⇔⇔mm⎛ m⎞1**⋅ 2 2 − 2 < TTD(m) < 2 2 − 1 ⇒ TTD(m) = Θ⎜⎜ 2 2 ⎟⎟ .2⎝ ⎠7.f (n) = am n m + ...

+ a1n + a0 , am ≠ 0 . Доказать утверждения:1)f (n) = O(n k ) ⇔ k ≥ m ;2)f (n) = Ω(n k ) ⇔ k ≤ m ;3)f (n) = Θ(n k ) ⇔ k = m .Решение.a.f (n) = O(n k ) ⇔ ∃C > 0 : f (n) ≤ Cn k ⇔ ∃0 ≤ limb.1nkf (n) = Ω n ⇔ ∃C > 0 : f (n) ≥ Cn ⇔ ∃0 ≤ lim≤ ⇔ k ≤m.n → ∞ f ( n)Cc.f (n) = Θ(n k ) ⇔ ∃c1 , c2 > 0 : c1n k ≤ f (n) ≤ c2 n k ⇔ ∃c1 ≤ limn→∞( )kf ( n)≤ C ⇔ k ≥ m.nkkn→∞f ( n)≤ c2 ⇔ k = m .nk8. Аддитивной цепочкой называется последовательность вида n1 < n2 < ... < nk , для которойвыполнены два условия: 1) n1 = 1 ; nk = n и 2) ∀i : 1 < i ≤ k ∃s, t : 1 ≤ t ≤ s < i такие, чтоnt + ns = ni . Через l (n) обозначим минимальную длину аддитивной цепочки.Доказать: l (ab) ≤ l (a ) + l (b) − 1, a, b ∈ N .Решение.

Рассмотрим минимальную аддитивную цепочку, последним элементомкоторой является a: 1 = n1′ < ... < nl′( a ) = a . Минимальная аддитивная цепочка для b всвою очередь выглядит следующим образом: 1 = n1′′ < ... < nl′′(b ) = b . Помножим каждыйэлемент цепочки для b на a и получим ещё одну цепочку, которая, вообще говоря, неявляется аддитивной: a = n1′′′< ... < nl′′(′b ) = ab . Не трудно видеть, что последний элементцепочки {n′} равен первому элементу цепочки {n′′′} , т.е. nl′( a ) = n1′′′ . Составим из первойитретьейцепочекодну,объединивихпоравномуэлементу:l (b )6444744481 = n1′ < ...

< nl′( a ) = n1′′′< ... < nl′′(′b ) = ab . Не трудно видеть, что так составленная1442443l (a)58последовательность является аддитивной цепочкой, но не обязательно являетсяминимальной. Откуда следует, что l (ab) ≤ l (a) + l (b) − 1 .9. Дан некоторый отрезок и число n > 1 . Требуется привести алгоритм построения отрезка1от данного со сложностью O(log n) .nРешение.

Пусть дан отрезок AB. Для деления отрезка на n воспользуемся теоремойФалеса. Для этого из одного конца данного отрезка выпустим луч и отложим на нём nраз отрезок произвольной длины (пробный отрезок). Получим набор точек A1 , A2 , ..., An .После чего проведём прямую, параллельную An B , через точку A2 , тогда, согласнотеореме, она отсечёт на отрезке AB требуемый отрезок.AnAn−1...A2A1BA1ABnЕсли откладывать пробный отрезок по одному n раз, то сложность такого алгоритмабудет порядка n, и он нам не подойдёт.

Чтобы добиться логарифмической сложностиследует поступить следующим образом: после отложения 2-х пробных отрезков сразунаходим A4 , отложив от A2 отрезок AA2 . Затем сразу можно найти A8 , отложив двараза отрезок AA4 и т.д. по степеням двойки. Отсюда получаем логарифмическуюсложность, и оценка O(log n) будет верна.1 nдоказать, что сложность в среднем3 ln nне является полиномиальной.10. Используя оценку функции Эйлера π (n) >алгоритма пробных делений TTD11. Найти сложность в среднем по количеству обменов для алгоритма сортировки выбором,исключая обмены вида xk ↔ xk .12.

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

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