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

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

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

Рассмотрим n = 3k − 1, k ≥ 2 . Для таких n получаем ⎡log3 n ⎤ = k . Посмотрим,сколько взвешиваний потребуется алгоритму. На первом шаге все монеты разделятся⎛⎢n⎥ ⎢n⎥⎢n⎥⎞на три части: ⎜⎜ ⎢ ⎥, ⎢ ⎥, n − 2⎢ ⎥ ⎟⎟ = (3k −1 − 1, 3k −1 − 1, 3k −1 + 1) . Пусть фальшивая монета⎣3⎦⎠⎝⎣3⎦ ⎣3⎦оказывается всегда в третьей части, тогда на втором шаге получаем следующие части:⎛ ⎢ 3k −1 + 1⎥ ⎢ 3k −1 + 1⎥ k −1⎢ 3k −1 + 1⎥ ⎞⎜⎢⎟ = (3k −2 , 3k −2 , 3k −2 + 1) и т.д. На k-м шаге монеты,⎢, 3 + 1 − 2⎢⎥⎥⎥⎜⎟⎣ 3 ⎦⎠⎝⎣ 3 ⎦ ⎣ 3 ⎦разбиваются на следующие части: (1, 1, 2 ) , где фальшивая монета находится в третьегруппе, а значит необходимо для её выявления ещё одно взвешивание. Итого получаемk + 1 > ⎡log 3 n ⎤ = k взвешиваний.31.

Имеется конечная последовательность из нулей и единиц. Разрешается заменять группу01 на 1 0{...0 . Доказать, что алгоритм завершается.сколькоугодно32. Чему равно r ?r:=0;for i=1 to n dofor j=i+1 to n dofor k=i+j to n dor:=r+1;odododРешение. Не трудно видеть, что можно изменить правые границы циклов, следующимобразом:r:=0;⎢ n − 1⎥dofor i=1 to ⎢⎣ 2 ⎥⎦for j=i+1 to n-i dofor k=i+j to n dor:=r+1;odododЭто не изменит семантики программы, но теперь каждый цикл проработает указанное⎢ n − 1⎥и составим сумму:количество раз.

Обозначим x = ⎢⎣ 2 ⎥⎦63xn −ir=∑∑ni =1 j =i +1k =i + jИзxn −ix∑1 = ∑ ∑ [n − (i + j ) + 1] = ∑ (n − 2i)i =1 j =i +1математическогоi =1анализаизвестнаxn + 1 − 2i⎛ n(n + 1)⎞= ∑⎜− i (2n + 1) + 2i 2 ⎟22⎠i =1 ⎝формула: 12 + 22 + ... + n 2 =n(n + 1)(2n + 1)6(устанавливается по индукции). Применим её и окончательно получим:xn(n + 1) 1 + xx( x + 1)(2 x + 1)⎛ n(n + 1)⎞r = ∑⎜− i (2n + 1) + 2i 2 ⎟ = x ⋅−⋅ x(2n + 1) +2223⎠i =1 ⎝33. Для задачи 4 доказать, что f (n) = 3n − 1 является нижней границей.Решение. Худший случай работы алгоритма сортировки заключается в максимальнойзагруженности тупика. Очевидно, что в отдельно взятый момент времени вагоны втупике имеют одинаковые цвета (вагон отправляется в тупик, когда его цвет совпадаетс цветом последнего вагона формируемого состава, но тогда цвет вагонов в тупикедолжен совпадать с цветом текущего вагона, т.к.

в противном случае была бывозможность операции ИЗ). Максимальная загрузка тупика возможна на n − 1 вагон, т.к.один вагон в любом случае должен быть отправлен МИМО. Для доказательствавозможности загрузки тупика на n − 1 вагон приведём пример: исходный составсостоит из n вагонов одного цвета подряд, после которых следуют n вагонов другогоцвета. В этой ситуации первый вагон перегоняется МИМО, а остальные n − 1 вагонпопадают в тупик. Тогда для нижней границе получаем: 1 операция МИМО, n − 1операций В, каждая из которых в конечном итоге сопровождается операцией ИЗ, иоставшиеся n операций МИМО.

Итого получаем: 1 + 2 ⋅ (n − 1) + n = 3n − 1 .34. Для задачи 5 доказать, что алгоритм с O(n) является оптимальным по порядкусложности.Решение. Т.к. любой алгоритм поиска двери допускает оценку Ω(n) , то алгоритм соценкой O(n) будет являться оптимальным по порядку сложности.35. Показать, что для сложностиΘ 2 max{ma ,mb } max{ma , mb } не верна.()алгоритма«наивного»умноженияоценка**36. Верна ли для алгоритма «наивного» деления оценка TND(ma , mb ) = Θ(ma mb ) ?37. Имеется массив из попарно различных элементов и требуется найти медиану — элемент,меньше и больше которого одинаковое число элементов (в случае чётного числаэлементов возможно отличие на 1). Доказать, что 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, ...

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

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