С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 36

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

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

К горизонтальной доске приделанытри вертикальных столбика. На первый нанизано n дисков, диаметры которых убывают вверх (рис. ). Требуется, перекладывая дискиРис. . Игра «Ханойские башни». Исходное положение.по одному, расположить их в прежнем порядке на третьем столбике. Ограничение состоит в том, что больший диск никогда не можетрасполагаться над меньшим. Разработать рекурсивный алгоритм решения этой задачи и определить его временную сложность по числуперекладываний дисков.. (Продолжение предыдущей задачи.) Требуется определитьвременную сложность алгоритма перекладывания дисков в игре «Ханойские башни» при условии, что затраты на перекладывание состолбика на столбик i-го по величине диска равна а) i; б) i 2 ; в) 2i ..

Сформулировать правило нахождения частного решения рекуррентного уравнения ad y(n) + ad−1 y(n − 1) + ... + a0 y(n − d) = f (n)для случая, когда f (n) принимает постоянное значение c.. Пусть функция f (n) определена для всех n ∈ N+ и пустьa — ненулевое число. Любое определенное для всех n ∈ N решениерекуррентного уравнения y(n) − ay(n − 1) = f (n) имеет вид y(n) =nPf (k).= an y(0) +kk =1aУказание. Индукция по n.. Для чисел Фибоначчи выполнено равенствоn = 1, 2, 3, ...nPi =1Fi = Fn+2 − 1,Указание.

Решением рекуррентного уравнения y(n) − y(n − 1) = Fn , y(0) == 1, является y(n) = Fn+2 .Глава . Рекуррентные соотношения и сложность алгоритмов. Верно ли, что для любого полинома p(n) найдется полиномq(n) (оба с вещественными коэффициентами) такой, что q(n + 1) −− q(n) = p(n), и если да, то как различаются степени полиномов p(n)и q(n)?. Найти множество всех вещественных последовательностей,удовлетворяющих рекуррентному уравнению y(n + 1) + y(n) = 0.. Вернемся к алгоритму VRec из § .

Пусть 1 ¶ k ¶ n. Сколькораз при построении множества Vn будет выполнено построение множества Vk ?Ответ. Fn−k .. Найти общее решение рекуррентного равенства (.) приk = 1. Найти частное решение, удовлетворяющее условию y(0) = 0.(При k = 1 рекурсия (.) не приводит к избыточным вычислениямзначений U.). Назовем перестановку z1 , z2 , ..., zn чисел 1, ..., n критическойдлины n, если на ней достигается максимум числа сравнений, требуемых рекурсивной сортировкой слияниями для массивов длины n.Пусть n > 1, а x1 , ..., xj⌊n/k2⌋ и ly1 ,m..., y⌈n/2⌉ суть некоторые критическиеперестановки длиныответственно,n2иn.

Тогда числа z1 , z2 , ..., zn , равные, со22x1 , ..., 2x⌊n/2⌋ , 2 y1 − 1, ..., 2 y⌈n/2⌉ − 1образуют критическую перестановку длины n (рис. ).Рис. . Случай, когда при n = 7 для сортировки слияниями потребуется максимальное число сравнений.. Как выглядят критические перестановки длины 6, 7, 8 и 9, полученные с помощью предложенного в предыдущей задаче подхода?Задачи. Имеет место равенство (.).Указание. См. задачу .. (Продолжение задачи , в которой фактически в рекурсивной форме описан алгоритм построения некоторой критической перестановки длины n.) Исследовать сложности описанного алгоритмапостроения некоторой критической перестановки длины n по числу умножений на два и по числу вычитаний единицы.

Предложитьнерекурсивный алгоритм (например, можно рассмотреть последовательное построение критических перестановок, длины которых сутьсоответственно 1, 2, ..., n) и исследовать его сложности по названнымоперациям.. Чему равно наименьшее n вида 2k , для которого число сравнений при рекурсивной сортировке слияниями превосходит ⌈log2 n!⌉?. Оценка (.) является следствием оценки TRS (n) = λ(n) ++ λ∗ (n) − 2.. Для сложности алгоритма бинарного поиска места элементав упорядоченном массиве обосновать рекуррентное неравенство(1, j kесли n = 1,TBS (n) ¶n+ 1, если n > 1,TBS2не прибегая к известному явному выражению для TBS (n). Из этогорекуррентного неравенства получить оценку для TBS (n)..

Указать алгоритм построения пересечения n полуплоскостейai x + bi y + ci ¾ 0,i = 1, 2, ..., n,имеющий временную сложность Θ(n log n) по общему числу операций.Указание. Пересечением будет выпуклый многоугольник (возможно, неограниченный). Опираясь на алгоритм Шеймоса—Хоя (задача ), использовать стратегию «разделяй и властвуй».. По сравнению с теоремами ., . предложения ., .представляют собой более сильные утверждения, имеющие к тому жеболее широкое применение. Используя эти предложения, получитьасимптотические оценки для(0,j kесли n = 1,l mf (n) =nnf+f+ ϕ (n), если n > 1,22при ϕ (n) = log2 n и ϕ (n) = n log2 n.Глава .

Рекуррентные соотношения и сложность алгоритмов. Рекуррентное неравенство вида (.) может иметь более одного решения, однако во всех трех случаях, предусмотренных формулой (.), по крайней мере для одного решения соответствующаяоценка из (.) является точной.. Обобщить предложенную в этой главе технику решения рекуррентных неравенств на случай, когда задача с размеромj входаnknилиразбивается на s задач, размер каждой из которых — этоsl mn, где s — некоторое натуральное число ¾ 2. Как будут выглядетьsтеоремы ., . в этом случае?. Доказать соотношение (.).Указание. Рассмотреть количество умножений чисел битовой длины 1 впроцессе применения алгоритма Карацубы к входу размера m и показать,что G(m) является для него нижней оценкой..

а) Для любого ǫ > 0 можно указать N > 0 такое, что 3TKM (m) << TKM (2m) < (3 + ǫ )TKM (m) при всех m ¾ N.б) Для любого ǫ > 0 можно указать N > 0 такое, что 7TSt (n) << TSt (2n) < (7 + ǫ )TSt (n) при всех n ¾ N.Указание. См. (.), (.) и, соответственно, (.).. Теоремы о рекуррентных неравенствах часто формулируютсяиначе. Например, в [] и [] теорема дается, с точностью до обозначений и используемых слов, в следующем виде.

Пусть s — целое¾ 2, и при любом n вида sk , k = 1, 2, ..., вещественная функция f (n)натурального аргумента удовлетворяет неравенству nf (n) ¶ wf+ cnd ,sгде w, c, d — константы, причем w > 0, c > 0, d ¾ 0. Пусть при этомf (n) не убывает на каждом отрезке [sk−1 + 1, sk ]. ТогдаdO(n log n), если d = logs w,f (n) = O(nd ),если d > logs w,O(nlogs w ),если d < logs w.Доказать эту теорему. (Заметим, что в условии теоремы . нет требования неубывания f (n) на каждом отрезке [sk + 1, sk ], но зато требуется, чтобы, например, неравенство (.) выполнялось для всех n,а не только для n вида 2k .)Глава СводимостьВ этой главе мы рассматриваем только временную сложность алгоритмов и считаем, что размер входа — это неотрицательное целоечисло.§ . Линейная сводимостьНиже в сопоставляемых друг с другом вычислительных задачах подразумеваются преобразования каких-то математических объектов,представляемых одинаково для всех задач, участвующих в сопоставлении.

Размер входа для алгоритмов решения рассматриваемых задачтоже должен определяться единообразно. При сравнительном исследовании задач затраты на выполнение вычислений измеряются количеством операций из одного и того же набора (например, арифметических операций, битовых операций и т. д.).Определение .. Пусть P и Q — две вычислительные задачи.Если любому алгоритму AQ решения задачи Q можно сопоставитьтакой алгоритм A P решения задачи P, чтоTAP (n) = O(TAQ (n)),(.)то говорят, что задача P линейно сводится к задаче Q, и пишут P ¶ Q.В специально оговариваемых случаях утверждение P ¶ Q предполагает, что рассматриваются лишь такие алгоритмы AQ , сложности которых удовлетворяют некоторым фиксированным условиям.Слово «линейно» в этом определении означает лишь то, что сложность получаемого алгоритма A P не является, скажем, квадратом, кубом и т.

д. сложности алгоритма AQ . Возможное присутствие условий(ограничений) на сложности алгоритмов решения задачи Q облегчает или просто делает возможным доказательство (.). В то же время, предполагается, что эти ограничения отсекают нерациональныеалгоритмы; тогда смысл отношения P ¶ Q состоит в том, что каж-Глава . Сводимостьдому приемлемому («хорошему») алгоритму решения задачи Q мыможем сопоставить алгоритм решения задачи P такой, что выполнено (.).Пример .. Будем рассматривать задачи умножения M и возведения в квадрат S неотрицательных целых чисел, заданных в двоичной системе, считая размером входа в первой задаче максимальнуюиз битовых длин чисел n1 , n2 , а во второй — битовую длину данногочисла n (будем обозначать этот размер через m), в качестве затратбудем рассматривать битовые затраты.Из равенства n2 = n · n следует, что S ¶ M, так как это равенстводает требуемый определением . алгоритм. Дает ли равенствоn1 · n2 =(n1 + n2 )2 − n21 − n222(.)основание считать, что M ¶ S? Битовая длина числа n1 + n2 можетоказаться равной m + 1.

Если бы для возведения в квадрат использовался некоторый чрезвычайно нерациональный алгоритм, имеющий, скажем, сложность m!, то соответствующий алгоритм умножения имел бы сложность порядка (m + 1)!. Легко видеть, что равенство(m + 1)! = O(m!) места не имеет. Можно пытаться определить умножение через возведение в квадрат как-то иначе, но можно и не отказываться от формулы (.): при установлении линейной сводимостиобычно считается, что сложность любого приемлемого алгоритма выполнения какой-либо мультипликативной арифметической операции(умножения, возведения в квадрат, деления и т. д.) удовлетворяет, хотя бы для всех достаточно больших m, условиям) T(m) ¾ m,) T(m) не убывает при возрастании m,) T(2m) ¶ 4T(m)(условие  отсекает алгоритмы умножения, сложность которых растетбыстрее чем m2 ). Приняв, что сложность алгоритма AS удовлетворяетэтим условиям, мы имеемTAS (m + 1) ¶ TAS (2m) ¶ 4TAS (m),что дает TAM (m) = O(TAS (m)) для описанного с помощью (.) алгоритма умножения.

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

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