Рекуррентные соотношения как средство анализа сложности алгоритмов

П

Задачи

98. Исследовать битовую сложность вычисления величины 1 + + 2 +... +n последовательными сложениями. Размером входа считать битовую длину m целого числа n.

99. Для временной битовой сложности «сверхнаивного» умноже­ния (пример 19.1) при использовании параметров m_ъ m₂ верна оценка сверху O (2^{тах{ m} 1' ^m 2}тах{ m ₁, m ₂}), а оценка Q(.2^max{m^^{m }} max{m₁,m₂}) неверна.

Указание. Неверна оценка П(2^{тах{ m} ь ^m 2}_тах{ m ₁, m ₂}): она противоречила бы оценке O(2^m2m{), так как для любого N > 0 существуют m₁,m₂>N такие, что m₁ = 2^m2.

100. Определение чисел Фибоначчи, данное в § 10, позволяет вы­числить F_n, выполнив n — 1 сложение. Битовая сложность этого алго­ритма допускает оценку O{n²) при рассмотрении n в качестве разме­ра входа.

101. Обосновать использованный в доказательстве предложения 21.1 переход от оценки T*^(.m_ъm₂) = O{{m_г - m₂ + 1)(m ₂ + 1)) к T ^* (m _ъ m ₂) = O{{m_г -m₂ + 1) m ₂).

102. Можно ли усилить предложение 21.2, заменив приведенные там оценки O (log a log b), O (log² a) на e(log a log b), 6(log² a)?

103. Рассмотрим m = А(n) в качестве размера входа алгоритма вы­числения факториала (пример 20.1). Верна ли для соответствующей временной битовой сложности оценка O (2 ^mm)?

104. К числу, первоначально равному нулю, прибавляется шаг за шагом по единице до получения значения 2 n - 1, n ^ 0. При этих сло­жениях потребуется 2 n - n - 1 переносов единицы в старший разряд.

105. Пусть p — простое, a и b — произвольные целые, k — нату­ральное. Тогда (a + b)^pk=a^pk +b^pk (mod p).

Задачи

106. а) Аддитивная группа кольца Z_k является циклической, в ка­
честве образующей этой группы может выступать любой класс, со­
держащий число I, взаимно простое с к.

б) Пусть р—простое, тогда мультипликативная группа поля Z_p, т. е. группа всех ненулевых элементов по умножению, является цик­лической.

107. Если число р—простое, а к —неотрицательное целое, мень­
шее р, то (£)=0 (mod р).

Указание. Предварительно показать, что р не делит /с!.

108. Индукцией по а доказать малую теорему Ферма.

Указание. Использовать равенство а^р = (1 + (а - 1))^р и предыдущую за­дачу.

109. Имеет место следующая китайская теорема об остатках:
пусть к_ък₂,...,к_п —взаимно простые натуральные числа (моду­
ли); тогда для любых Ъ_ъ Ъ₂,..., Ъ_п е Z найдется /eN такое, что / =
= b; (mod ki), i = 1, 2,..., п. (Задача восстановления числа по остаткам
обсуждалась в древних китайских математических трактатах.) Дать
конструктивное доказательство этой теоремы, т. е. доказательство,
содержащее в себе алгоритм построения подходящего / (каждый
такой алгоритм может быть назван китайским алгоритмом).

Указание. Пусть k = k₁k₂...k_n и g; = fc / fc;, i = l,2,...,n. При всех i = l,2,......, п числа fc; и g _; взаимно просты, поэтому расширенным алгоритмом Евкли-

да можно определить h_{ так, что h _; g _; = 1 (mod fc_;) и положить /= Xi ^j^jSj.

110. Исходя из того, что значение полинома /(х) в точке х = а
равно по теореме Безу остатку от деления /(х) на х-а, установить
параллелизм между интерполяционной формулой Лагранжа и форму­
лой для значения /, данной в указании к задаче 109.

111. Битовая сложность китайского алгоритма, эскизно обрисован­
ного в указании к задаче 109 и основывающегося на расширенном
алгоритме Евклида, наивном делении и наивном умножении, допус­
кает оценку 0(log²fc), если в качестве размера входа рассмотреть к,
и оценку 0{т²), если в качестве размера входа рассмотреть битовую
длину т числа к.

Указание. По поводу сложности вычисления g см. пример 20.2; сложность этапа вычисления всех g _; допускает оценку ОI J] log g log кЛ и т. д.

Глава 5. Битовая сложность

112. Верно ли, что для битовой сложности в среднем алгоритма пробных делений справедлива оценка п((|)^Ш)?

113. Битовая сложность в среднем алгоритма наивного умножения двух неотрицательных целых чисел а и Ъ допускает оценку Г2(т²), а тем самым —и 6(т²), где т = тах{А(а), А(Ь)}.

Указание. Битовые затраты при наивном умножении а на Ъ не могут быть меньше, чем сА(а)А*(Ь). Два случая

A(a) = m, A(b)sS m и А(а)г£т, А(Ь) = т

приводят к двум вероятностным пространствам У_ЪУ₂, состоящим из со­ответствующих пар (а, Ь) с равномерными распределениями вероятностей. Определить значения вероятностей событий А (а) = к и А(Ь) = к для произ­вольного О^к^т для каждого из пространств V _l5 V ₂ и найти математи­ческие ожидания случайных величин £(a, b) = A(a), rj(a, b) = А*(Ь). В силу независимости £ и rj можно воспользоваться равенством E(£(a, b)rj(a, Ь)) = = (E(C(a, b))(Erj(a, b)).

114. Привести полное доказательство равенства (23.1).

115. Основываясь на (23.2) и бинарном алгоритме возведения в степень, построение С* можно выполнить с пространственной слож­ностью Зп² + 0(1).

116. Искомая матрица С* будет вычисляться правильно и после увеличения показателя степени в правой части (23.2).

117. Воспользовавшись утверждением, содержащимся в задаче 116, заменим показатель степени в правой части (23.2) на 2^т, где т — наименьшее целое, такое что 2^т ^ п - 1. Как изменится верхняя оцен­ка (23.4) при переходе к этой новой версии алгоритма?

118. Исследовать пространственную сложность описанного в зада­че 117 алгоритма.

119. Какой наибольшей временной сложностью может обладать алгоритм умножения булевых матриц, или, другими словами, какую верхнюю границу должна допускать функция В{п), чтобы времен­ные затраты описанного в задаче 117 алгоритма допускали бы оценку 0{п^ъ)?

120. Можно ли первую строку приведенного в § 23 псевдокода ал­горитма Уоршелла переместить в конец этого псевдокода?

Указание. Рассмотрим алгоритм в сокращенном виде, удалив эту строку из псевдокода. Влияют ли значения диагональных элементов исходной мат­рицы на значения внедиагональных элементов матрицы-результата?

12 1. Описать версию алгоритма Уоршелла для вычисления крат­
чайших путей между вершинами графа G, считая, что вместо матри-

Задачи

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

Глава 6

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