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

Доказать, что n − 1 является нижней границей длясложности алгоритмов, решающих задачу.38. Бинарный алгоритм возведения в степень ( a n ) не является оптимальным, если в качестверазмера входа брать n. Будет ли он оптимальным, если в качестве размера входа взятьν (n) .39. Имеется отрезок и число n. Требуется разбить отрезок на n частей. Показать, что нижняяn −1граница сложности для алгоритмов, решающих эту задачу, составляет.240.

Алгоритм вычисляет следующую сумму: 1 + 2 + ... + n . n — размер входа. Тщательноисследовать алгоритм на сложность.41. Пусть алгоритм вычисляет Fn (число Фибоначчи) через n − 1 сложение. Доказать, что( )сложность такого алгоритма допускает оценку: O n 2 .64Решение. Битовая длина числа Фибоначчиν ( Fn ) = ν ( Fn−1 + Fn−2 ) ≤ {Fn−1 > Fn−2 } ≤ ν (Fn−1 + Fn−1 ) = ν (2 Fn−1 ) = 1 +ν ( Fn−1 ) , ν ( F1 ) = 1 ⇒*ν ( Fn ) ≤ n . Известна оценка битовой сложности для сложения: TAdd(m) = Θ(m) , поэтомуT (n) = (n − 1)O(n) = O(n 2 ) .42. Пусть p — простое, u ∈ N , u < p . Показать, что C up ≡ 0(mod p ) .p!p( p − 1) ⋅ ... ⋅ ( p − u + 1)=. Т.к.

число сочетаний является целымu!( p − u )!u!числом, то все множители знаменателя обязаны сократиться с множителями числителя,а т.к. p — простое, то в результате сокращения в числители оно останется ⇒C up ≡ 0(mod p ) .Решение. C up =43. Используя задачу 42 и индукцию по u, доказать утверждение: если p — простое, u ∈ N⇒ u p ≡ u (mod p) . Если дополнительно p не делит u, то u p −1 ≡ 1(mod p) .Решение. Проведём индукцию по u: для u = 1 очевидно, что u p ≡ u (mod p) . Пустьтеперь утверждение верно для u − 1 , т.е. (u − 1) ≡ u − 1(mod p ) , и докажем его для u:pu p = (1 + (u − 1)) , согласно формуле бинома Ньютона, последнее перепишется в виде:pp −1(1 + (u − 1))p = 1 + ∑ C ip (u − 1)i + (u − 1)p .i =1C ip ≡ 0(mod p ) (задача 42), (u − 1) ≡ u − 1(mod p )p(предположение индукции), откуда следует u p ≡ u (mod p) .kkk44. Доказать, что если a, b ∈ Z , p — простое, k ∈ N , то (a + b) p ≡ a p + b p (mod p ) .()()p k p k − 1 ⋅ ...

⋅ p k − i + 1, т.к. число сочетаний является целым числом,i!то все сомножители знаменателя должны необходимо сократится с множителямичислителя, но при i < p k все множители знаменателя < p k ; p — простое число, поэтомухотя бы одно p в числителе останется. Тогда C ip k ≡ 0(mod p) .Решение. C ip k =(a + b )pk=apk+p k −1∑ C14a2b43 + bi =1ipkip k −ipkkkk⇒ (a + b) p ≡ a p + b p (mod p ) .≡ 0 (mod p )45. Ханойские башни. Имеется 3 шеста, на один из которых одето n дисков разного радиуса:в самом низу большой, вверху — самый маленький. Требуется перенести все диски спервого шеста на 2, за раз перекладывая только один диск. Запрещается класть дискбольшего радиуса на диск меньшего.312Подсчитать цену решения (через рекуррентное соотношение), в случае, если за одноперекладывание мы платим: 1) 1 ед.; 2) i ед.

(где i — порядок номера диска считая сверхув начальной пирамиде); 3) i 2 ; 4) 2i .Решение. Алгоритм решения изобразим следующим образом:65T1T n −1T n −1⎧⎪n −1 ⎨⎪⎩⇒T (n) = 2T (n − 1) + T (1)T (0) = 0⎧T (n) = 2T (n − 1) + 1⎧T (n) − 2T (n − 1) = 1или ⎨. Решаем полученное⎨⎩T (0) = 0⎩T (0) = 0рекуррентное соотношение: характеристическим уравнением для него будетλ − 2 = 0 ⇔ λ = 2 , и общим решением однородного рекуррентного уравнения будетT о.о. (n) = C ⋅ 2 n . В правой части стоит квазиполином нулевой степени, поэтому частноерешение неоднородного уравнения будем искать в виде T ч.н.

(n) = a . Подставляячастное решение в исходное уравнение, определяем константу a = −1 , следовательно,окончательное решение рекуррентного уравнения будет иметь вид: T (n ) = C ⋅ 2 n − 1 .Константу C определяем из начальных условий: T (0) = C − 1 = 0 ⇒ C = 1 ⇒ T (n) = 2n − 1 .1) T (1) = 1⇒⎧T (n) = 2T (n − 1) + n2) T (1) = i ⇒ ⎨.

Решение будет аналогично пункту 1), кроме того,⎩T (0) = 0что частное решение в этом случае надо будет искать в виде T ч.н. (n) = an + b , т.к. вправой части стоит квазиполином первой степени: n = n ⋅1n . Подставляя частноерешение в исходное уравнение, получаем:an − b − 2(a (n − 1) − b ) = n ⇔ − an − b + 2a = nПриравнивая коэффициенты при одинаковых степенях n, получаем:n1 ⎧− a = 1 ⎧a = −1⇔⎨⇒ T ч.н. (n) = −n + 20 ⎨2a=bb=−2n ⎩⎩Общим решением неоднородного рекуррентного соотношения будет:T (n) = T о.о. (n) + T ч.н. (n) = C ⋅ 2n − (n + 2)Из начального условия определяем константу C: T (0) = C − 2 = 0 ⇒ C = 2T (n) = 2 n+1 − (n + 2) .⇒⎧T (n) = 2T (n − 1) + n 2⇒ ⎨.

Решается аналогично предыдущему пункту,T(0)=0⎩только на этот раз в правой части стоит квазиполином второй степени, поэтому частноерешение будем искать в виде T ч.н. (n) = an 2 + bn + c . Подставляем его в начальноеуравнение:2) T (1) = i 2[]an 2 + bn + c − 2 a(n − 1) + b(n − 1) + c = n 2 ⇔2n 2 ⎧− a = 1⎧a = −1⎪221 ⎪− an + (4a − b)n + 2b − 2a − c = n ⇒ n ⎨4a − b = 0⇔ ⎨b = −4⎪c = −6n 0 ⎪⎩2b − 2a − c = 0⎩66⇒ T ч.н. (n) = −(n 2 + 4n + 6) ⇒ T (n) = C ⋅ 2 n − (n 2 + 4n + 6)T (0) = C − 6 = 0 ⇒ C = 6 ⇒ T (n) = 6 ⋅ 2 n − (n 2 + 4n + 6) .⎧T (n) = 2T (n − 1) + 2 n.

Общее решение неоднородного уравнения ищется3) T (1) = 2i ⇒ ⎨⎩T (0) = 0аналогично предыдущим пунктам, но поиск частного решения в этом случае будетотличаться, т.к. в этом случае мы имеем в правой части квазиполином 2n , основаниестепени которого совпадает с корнем характеристического уравнения.

Согласно теории,в этом случае частное решение следует искать в виде T ч.н. (n) = an ⋅ 2n . Подставляя его висходное уравнение, получаем, что константа a может быть любой. Положим a = 1 ,тогда общее решение неоднородного рекуррентного уравнения запишется в виде:T (n) = (C + n ) ⋅ 2 n . Из начального условия получаем C = 0 и T (n) = n ⋅ 2 n .46. (Китайская теорема об остатках) Имеется несколько взаимно простых чисел большихединицы: k1 , k2 , ...

, kn , и имеются остатки ( b1 , b2 , ... , bn )от деления некоторого числа f наk1 , k2 , ... , kn соответственно. Требуется восстановить число f . Очевидно, что если f —решение, то f + k1k2 ...k n тоже будет решением.Решение. Пусть b1 , b2 , ...

, bn — известные остатки, и требуется найти f такое, чтоkf ≡ bi (mod ki ) , i = 1, 2, ... , n . Обозначим: k = k1k2 ...kn — произведение модулей, gi = ,kii = 1, 2, ... , n — произведение всех модулей, кроме i-го, тогда gi ⊥ ki (взаимно просты) всилу того, что ki взаимно простые ⇒ по расширенному алгоритму Евклида найдём hinтакие, что hi g i ≡ 1(mod ki ) . Тогда можно положить f = ∑ bi gi hi .i =147. Найти оценки сложностей, если для них выполняются следующие рекуррентныесоотношения:⎛⎢n⎥⎞1) T (n) = T ⎜⎜ ⎢ ⎥ ⎟⎟ + log 2 n⎝⎣2⎦⎠⎛ ⎢n⎥⎞2) T (n) = 2T ⎜⎜ ⎢ ⎥ ⎟⎟ + n log 2 n⎝ ⎣2⎦⎠⎛⎢n⎥⎞3) T (n) = 2T ⎜⎜ ⎢ ⎥ ⎟⎟ + n 2⎝⎣2⎦⎠Решение.

1) используя предложение (стр. 40) получаем ассоциированное уравнение⎧0, k = 0t (k ) = ⎨⎩t (k − 1) + k , k > 0k (k + 1)решением которого будет t (k ) =⇒2⎣log 2 n⎦(⎣log 2 n⎦ + 1) ≤ T (n) ≤ ⎡log 2 n⎤(⎡log 2 n⎤ + 1) ⇒ T (n) = Θ(log 2 n ) .222) используя предложение (стр. 40) получаем ассоциированное уравнение⎧0, k = 0⎧t (k ) − 2 ⋅ t (k − 1) = k ⋅ 2 k⇔ ⎨t (k ) = ⎨k⎩2 ⋅ t (k − 1) + k ⋅ 2 , k > 0⎩t (0) = 067Характеристическим уравнением будет λ − 2 = 0 ⇒ λ = 2 поэтому общим решениемоднородного рекуррентного уравнения будет t о.о. (k ) = C ⋅ 2 k .

Частное решениенеоднородного рекуррентного уравнения будем искать в виде t ч.н. (k ) = k r p(k ) ⋅ 2k , где rсоответствует количеству совпадений основания степени из правой части ( k ⋅ 2k ),которое в нашем случае равно 2, с корнями характеристического уравнения. В нашемслучае r = 1 . Степень многочлена p(k ) совпадает со степенью многочлена из правойчасти, в нашем случае deg p(k ) = deg k = 1 , т.е. p(k ) = ak + b где a и b — константы,подлежат определению. Таким образом, частное решение будем искать в видеt ч.н. (k ) = k (ak + b) ⋅ 2 k . Подставим его исходное уравнение:k (ak + b) ⋅ 2 k − 2 ⋅ (k − 1)(a(k − 1) + b ) ⋅ 2k −1 = k ⋅ 2k ⇔ ak 2 + bk − ak 2 + ak − bk + ak − a + b = k⎧a = 1 2k 1 : ⎧2 a = 1⇔ 2ak − a + b = k ⇒⇒ t ч.н.

(k ) = k (k + 1) ⋅ 2k −1⇔ ⎨⎨0k : ⎩− a + b = 0⎩b = 1 2Общее решение неоднородного рекуррентного уравнения будет складываться изобщего решения однородного и частного неоднородного: t (k ) = t о.о. (k ) + t ч.н. (k ) ⇒t (k ) = C ⋅ 2 k + k (k + 1) ⋅ 2 k −1 . Из начальных условий определяем C: t (0) = 0 ⇒ C = 0 ⇒t (k ) = k (k + 1) ⋅ 2k −1 . Откуда для сложности, согласно предложению, получаем оценку:⎣log 2 n⎦(1 + ⎣log 2 n⎦) ⋅ 2 ⎣log2 n ⎦ ≤ T (n) ≤ ⎡log 2 n⎤(1 + ⎡log 2 n⎤) ⋅ 2 ⎡log2 n ⎤ ⇒ T (n) = Θ(n log 2 n ).223) ассоциированное уравнение⎧t (k ) − 2 ⋅ t (k − 1) = 2 2 k⎨⎩t (0) = 0Корнем характеристического уравнения будет λ = 2⇒t о.о. (k ) = C ⋅ 2 k . λ = 2 несовпадает с основанием степени в правой части: 2 2 k = (22 ) = 4 k , поэтому частноерешение будем искать в виде t ч.н.

(k ) = p(k ) ⋅ 4k , где deg p(k ) = 0 ⇔ p(k ) = a , т.е.t ч.н. (k ) = a ⋅ 4k . Для определения константы a, подставляем частное решение в исходноеуравнение:aa ⋅ 4 k − 2a ⋅ 4 k −1 = 4 k ⇔ a − = 1 ⇒ a = 2 ⇒ t ч.н. (k ) = 2 ⋅ 4 k = 2 2 k +12Общим решением рекуррентного уравнения будет t (k ) = C ⋅ 2 k + 22 k +1 . Из начальногоусловия получаем: t (0) = 0 ⇒ C + 2 = 0 ⇒ C = −2 ⇒ t (k ) = 2 2 k +1 − 2 k +1 . Поэтому длясложности получаем оценку: t (⎣log 2 n ⎦) ≤ T (n) ≤ t (⎡log 2 n ⎤) ⇔k()()2 ⋅ 2 ⎣log2 n ⎦ − 2 ⋅ 2 ⎣log2 n ⎦ ≤ T (n) ≤ 2 ⋅ 2 ⎡log2 n ⎤ − 2 ⋅ 2 ⎡log2 n ⎤ ⇒ T (n) = Θ(n 2 ) .2682.