Лекции о сложности алгоритмов. С. А. Абрамов (1121249), страница 32

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

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

Если используется именно этотто оценка числа операций для формулы (.) есть Θ(n4 ).нение бинарного алгоритма (пример .) для возведения вбулевой матрицы C позволяет перейти к оценкеΘ(n3 log n).требуетспособ,Приместепень(.)Если нежелательно связывать основанный на формуле (.) алгоритм построения транзитивно-рефлексивного замыкания с конкретным способом умножения матриц, то верхнюю оценку числа битовыхопераций можно записать какn + B(n)(λ(n) + λ∗ (n) − 2),(.)где B(n) — сложность используемого алгоритма умножения булевых(n × n)-матриц; слагаемое n отражает расход на сложение с матрицей I.Рассмотренный пример высвечивает связь задачи построениятранзитивно-рефлексивного замыкания ориентированного графа с задачей умножения булевых матриц.

Эта связь оказывается очень тесной, о чем мы еще будем говорить в § .В следующем примере задача построения транзитивно-рефлексивного замыкания решается без использования умножения булевыхматриц.Пример .. Исследуем сложность алгоритма С. Уоршелла, предназначенного для построения матрицы C ∗ . В процессе примененияэтого алгоритма матрица C ∗ строится за n = | V | шагов, после k-гошага получается матрица D (k) = (dij(k)), и dij(k) = 1, если и только еслиi-я вершина соединена таким путем с j-й, номера всех промежуточных вершин которого не выходят за пределы множества {1, 2, ..., k}.Вначале полагаем D (0) = I ∨ C.

Затем для каждого k = 1, 2, ..., n находим D (k) :(k −1)(k −1)dij(k) = dij(k−1) ∨ (dik∧ dkj).(.)После этого C ∗ = D (n) .Формула (.) отражает то, что путь из i-й вершины в j-ю, всепромежуточные вершины которого принадлежат {1, 2, ..., k}, существует, если и только если реализуется хотя бы одна из следующихвозможностей:• имеется путь из i-й вершины в j-ю, все промежуточные вершиныкоторого принадлежат {1, 2, ..., k − 1};§ . Булева арифметика• имеются пути из i-й вершины в k-ю и из k-й в j-ю, все промежуточные вершины которых принадлежат {1, 2, ..., k − 1}.На вычисление D (0) уходит n битовых операций, вычисление каждой из матриц D (k) , 1 ¶ k ¶ n, требует 2n2 операций. Итого, требуется2n3 + n операций.Алгоритм Уоршелла вычисляет матрицу C ∗ , т.

е. строит транзитивно-рефлексивное замыкание ориентированного графа G с n вершинами, заданного матрицей смежности, затрачивая 2n3 + n битовыхопераций.Алгоритм Уоршелла можно легко реализовать так, что хранитьсяв памяти будут только D (k−1) и D (k) .

Но на самом деле алгоритм Уоршелла позволяет производить все вычисления, расходуя всего n2 битов под хранение матричных элементов. Если мы вычислим D = I ∨ C,а затем n раз обновим матрицу D (каждый раз всю целиком, неоставляя незатронутых элементов), используя на k-м этапе обновления матрицы D присваиванияdij := dij ∨ (dik ∧ dkj ),k = 1, 2, ... n, то получим искомую матрицу связности. В самом деле,индукцией по k можно доказать, что после k-го этапа обновления получаем матрицу, равную D (k) , при этом индуктивный переход от k − 1к k основывается на том, что имеют место очевидные соотношения(k)(k −1)dik= dik,(k)(k −1)dkj= dkj,k = 1, 2, ..., n, т.

е. при обновлении элемента dij на k-м этапе не имеет никакого значения, был ли уже обновлен какой-то из элементовdik , dkj или нет.Если строить матрицу C ∗ на месте исходной матрицы C, то алгоритм можно изобразить так:for l = 1 to n do cll := 1 od;for k = 1 to n dofor i = 1 to n dofor j = 1 to n doodcij := cij ∨ (cik ∧ ckj )ododПодводя итог рассмотрению алгоритма Уоршелла, заметим, что,как и алгоритм Евклида в расширенной версии, он дает довольноГлава . Битовая сложностьредкий пример, когда низкие временные затраты сочетаются с малымрасходом памяти.Алгоритм Уоршелла построения замыкания ориентированногографа имеет битовую временную сложность 2n3 + n, где n = | V | — число вершин графа.

Пространственная сложность этого алгоритмаограничена константой.При рассмотрении | V |, | E | в качестве двух параметров размеравхода сказанное сохраняет силу, так как затраты алгоритма Уоршеллане зависят от числа ребер заданного входного графа.Задачи. Исследовать битовую сложность вычисления величины 1 ++ 2 + ... + n последовательными сложениями. Размером входа считатьбитовую длину m целого числа n.. Для временной битовой сложности «сверхнаивного» умножения (пример .) при использовании параметров m1 , m2 верна оценкасверху O(2max{m1 ,m2 } max{m1 , m2 }), а оценка Θ(2max{m1 ,m2 } max{m1 , m2 })неверна.Указание. Неверна оценка Ω(2max{m1 ,m2 } max{m1 , m2 }): она противоречилабы оценке O(2m2 m1 ), так как для любого N > 0 существуют m1 , m2 > N такие,что m1 = 2m2 ..

Определение чисел Фибоначчи, данное в § , позволяет вычислить Fn , выполнив n − 1 сложение. Битовая сложность этого алгоритма допускает оценку O(n2 ) при рассмотрении n в качестве размера входа.. Обосновать использованный в доказательстве предложения∗∗. переход от оценки TND(m1 , m2 ) = O((m1 − m2 + 1)(m2 + 1)) к∗∗TND (m1 , m2 ) = O((m1 − m2 + 1)m2 )..

Можно ли усилить предложение ., заменив приведенныетам оценки O(log a log b), O(log2 a) на Θ(log a log b), Θ(log2 a)?. Рассмотрим m = λ(n) в качестве размера входа алгоритма вычисления факториала (пример .). Верна ли для соответствующейвременной битовой сложности оценка O(2m m)?. К числу, первоначально равному нулю, прибавляется шаг зашагом по единице до получения значения 2n − 1, n ¾ 0. При этих сложениях потребуется 2n − n − 1 переносов единицы в старший разряд.. Пусть p — простое, a и b — произвольные целые, k — натуkkkральное.

Тогда (a + b) p ≡ a p + b p (mod p).Задачи. а) Аддитивная группа кольца Zk является циклической, в качестве образующей этой группы может выступать любой класс, содержащий число l, взаимно простое с k.б) Пусть p — простое, тогда мультипликативная группа поля Z p ,т. е. группа всех ненулевых элементов по умножению, является циклической.. Еслиp — простое, а k — неотрицательное целое, мень числоpшее p, то≡ 0 (mod p).kУказание. Предварительно показать, что p не делит k!.. Индукцией по a доказать малую теорему Ферма.Указание.

Использовать равенство a p = (1 + (a − 1)) p и предыдущую задачу.. Имеет место следующая китайская теорема об остатках:пусть k1 , k2 , ..., k n — взаимно простые натуральные числа (модули); тогда для любых b1 , b2 , ..., bn ∈ Z найдется f ∈ N такое, что f ≡≡ bi (mod k i ), i = 1, 2, ..., n. (Задача восстановления числа по остаткамобсуждалась в древних китайских математических трактатах.) Датьконструктивное доказательство этой теоремы, т. е. доказательство,содержащее в себе алгоритм построения подходящего f (каждыйтакой алгоритм может быть назван китайским алгоритмом).Указание.

Пусть k = k1 k2 ... kn и gi = k/ki , i = 1, 2, ..., n. При всех i = 1, 2, ......, n числа ki и gi взаимно просты, поэтому расширенным алгоритмом ЕвклиnPbj h j gj .да можно определить hi так, что hi gi ≡ 1 (mod ki ) и положить f =j =1. Исходя из того, что значение полинома f (x) в точке x = aравно по теореме Безу остатку от деления f (x) на x − a, установитьпараллелизм между интерполяционной формулой Лагранжа и формулой для значения f , данной в указании к задаче ..

Битовая сложность китайского алгоритма, эскизно обрисованного в указании к задаче  и основывающегося на расширенномалгоритме Евклида, наивном делении и наивном умножении, допускает оценку O(log2 k), если в качестве размера входа рассмотреть k,и оценку O(m2 ), если в качестве размера входа рассмотреть битовуюдлину m числа k.Указание. По поводу сложности вычисления g см. пример .; сложность‹Pnэтапа вычисления всех gi допускает оценку Olog g log ki и т.

д.i =1Глава . Битовая сложность. Верно ли, что для битовой сложности m в среднем алгоритма4пробных делений справедлива оценка Ω?3. Битовая сложность в среднем алгоритма наивного умножениядвух неотрицательных целых чисел a и b допускает оценку Ω(m2 ),а тем самым — и Θ(m2 ), где m = max{λ(a), λ(b)}.Указание. Битовые затраты при наивном умножении a на b не могут бытьменьше, чем cλ(a)λ∗ (b).

Два случаяλ(a) = m,λ(b) ¶ mиλ(a) ¶ m,λ(b) = mприводят к двум вероятностным пространствам V1 , V2 , состоящим из соответствующих пар (a, b) с равномерными распределениями вероятностей.Определить значения вероятностей событий λ(a) = k и λ(b) = k для произвольного 0 ¶ k ¶ m для каждого из пространств V1 , V2 и найти математические ожидания случайных величин ξ(a, b) = λ(a), η(a, b) = λ∗ (b). В силунезависимости ξ и η можно воспользоваться равенством E(ξ(a, b)η(a, b)) == (E(ξ(a, b))(Eη(a, b)).. Привести полное доказательство равенства (.)..

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

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