С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 15
Текст из файла (страница 15)
Представить p (возможно, с небольшой погрешностью) в видеaaaконечной суммы вида 1 + 22 + ... + kk , где ai — это 0 или 1 для всех i,222а k — некоторое целое положительное число.Глава . Сложность в среднем. Пусть изначально у нас имеется генератор случайных вещественных чисел, принадлежащих отрезку [0, 1], и вероятность появления числа, принадлежащего отрезку [a, b], 0 ¶ a ¶ b ¶ 1, есть b − a.Пусть даны неотрицательные вещественные числа α0 , α1 , ..., αN −1 такие, что α0 + α1 + ...
+ αN −1 = 1. Как определить генератор чисел, принадлежащих множеству {0, 1, ..., N − 1}, такой, что вероятность появления числа k, 0 ¶ k ¶ N − 1, равна αk ?. Предположим, что у нас нет другого генератора случайных чисел, кроме генератора, в результате обращения к которому появляется 0 с вероятностью p или 1 с вероятностью 1 − p, причем о p мыничего не знаем, кроме того, что p 6= 0 и p 6= 1. Как с помощью этогогенератора можно сконструировать генератор, в результате обращения к которому появляется 0 или 1 с одинаковой вероятностью 1/2?Указание. Порождая подряд две цифры с помощью имеющегося генератора, мы получаем комбинации 0, 1 и 1, 0 с одинаковой ненулевой вероятностью.. (Продолжение предыдущей задачи.) Чему равно математическое ожидание числа обращений к изначально имеющемуся генератору случайных чисел при построении последовательности пар до появления 0, 1 или 1, 0? Найти сложность в среднем алгоритма полученияk «равновероятных» нулей и единиц с помощью сконструированногогенератора (затраты определяются количеством обращений к изначально имеющемуся генератору).
Можно ли указать значения p, длякоторых эта сложность имеет минимальное и, соответственно, максимальное значение?. Предложенную в указании к задаче идею обобщить на случай, когда необходимо сконструировать генератор random(N), N ¾ 1,описанный в § . Найти сложность в среднем алгоритма полученияk равновероятных случайных чисел из отрезка [0, N − 1] (затратыопределяются числом обращений к изначально имеющемуся генератору).. Сохранится ли для сложности в среднем формула 2n ln n + O(n),если в задаче о разрезании полоски клетчатой бумаги на отдельныеклетки (см. пример .) считать, что плата за вырезание одной случайно выбранной клетки равна не n − 1, а n рублей? Тот же вопрос,если эта плата составляет n2 рублей..
Известное утверждение (теорема Дирихле, г.), что два6случайных числа x, y ∈ N+ с вероятностью P, равной 2 , оказываютсяπвзаимно простыми, имеет тот смысл, что если ввести в рассмотрениечисло M(n), равное количеству пар (x, y) таких, что x и y взаимноЗадачипросты и, дополнительно, 1 ¶ x, y ¶ n, то предел limn→∞6M(n)существуетn2и равен 2 .
Предполагая (не обосновывая и не вникая в то, можπно ли это обосновать; это соответствует «физическому уровню строгости»), что множество N+ может быть превращено в вероятностное пространство так, что случайное x ∈ N+ кратно фиксированно1му d ∈ N+ с вероятностью , можно предложить несколько довольноd6простых доказательств равенства P = 2 . Для этого можно воспольπзоваться тем, что∞X1π2=2n =1n6(доказано Эйлером в г.) или свойством дзета-функции Римана,согласно которому∞XY11s =sn =1np — простое1− pи которое справедливо, например, для всех целых s > 1, и, в частности, для s = 2.6В упомянутых выше предположениях доказать равенство P = 2 ,πиспользуя следующие подходы.а) Для произвольного d ∈ N+ вычислить вероятность ϕ (d) того,что для случайных x, y ∈ N+ выполнено d = íîä(x, y).
Из равенства∞PP =1−ϕ (d) определить P. d =2б) Для произвольного простого p вычислить вероятность ψ(p) то+го, что по крайней мереQ одно из случайных x, y ∈ N не делится на p.Из равенства P =ψ(p) определить P.p — простоеУказания. а) ϕ (d) =1P; б) ψ(p) = 1 − 2 .d2pДля того чтобы сделать доказательство «настоящим», надо для произвольного n ∈ N+ детально рассмотреть ситуацию 1 ¶ x, y ¶ n и перейти к пределупри n → ∞, что потребует более кропотливой работы. См.
[, разд. ..].См. [, гл. I, разд. , прим. .].См. [, разд. .., упр. ].Глава Оценивание числа шагов (итераций)алгоритма§ . Функции, убывающие по ходу выполнения алгоритмаЧасто выполнение алгоритма является последовательностью однотипных шагов (итераций). Если все шаги равнозатратны по времени, тообщее их число с точностью до постоянного множителя эквивалентновременным затратам рассматриваемого алгоритма для данного входа, и важной задачей является определение или хотя бы оцениваниечисла этих шагов.Пример ..
Пусть a0 , a1 — натуральные числа, a0 ¾ a1 . Поиск наибольшего общего делителя (íîä) чисел a0 , a1 по алгоритму Евклидатребует выполнения серии однотипных шагов, каждый из которых —деление с остатком:a0 = q1 a1 + a2 ,a1 = q2 a2 + a3 ,...................a n −3 = q n −2 a n −2 + a n −1 ,a n −2 = q n −1 a n −1 + a n ,(.)a n −1 = q n a n .В этом случае an = íîä(a0 , a1 ), так какíîä(a0 , a1 ) = íîä(a1 , a2 ) = ...
= íîä(an , 0) = an .Последовательность получаемых остатков убывает (остаток меньшеделителя), при этом все остатки — неотрицательные целые. Не существует убывающей бесконечной последовательности, элементамикоторой являются неотрицательные целые числа, поэтому выполнение алгоритма Евклида (будем обозначать его буквой E) завершаетсядля любых натуральных a0 , a1 , и число делений с остатком не пре-§ . Функции, убывающие по ходу выполнения алгоритмавосходит a1 . Обозначив через CE (a0 , a1 ) исследуемое число деленийс остатком, получаемCE (a0 , a1 ) ¶ a1(.)(для упрощения записи мы пишем CE (a0 , a1 ) вместо CET (a0 , a1 )).
Этоговорит о том, что если a1 рассматривается как размер входа или если a0 , a1 рассматриваются как два параметра размера входа, то сложность алгоритма Евклида по числу делений не превосходит a1 . Какмы увидим, эта оценка является весьма грубой, но, привлекая сходные рассуждения, можно получать и более тонкие оценки.Формализуем те соображения, которые привели нас к этой первойоценке. Каждый шаг алгоритма имеет дело с парой неотрицательных целых (ai−1 , ai ) и при условии ai 6= 0 перерабатывает эту парув (ai , ai+1 ), где ai+1 равно остатку от деления ai−1 на ai . На множестве пар неотрицательных целых чисел k, l мы определяем функциюL(k, l), принимающую неотрицательные целые значения.
Эта функция такова, что когда при выполнении алгоритма Евклида мы переходим от пары (ai−1 , ai ) к паре (ai , ai+1 ), значения функции убывают: L(ai−1 , ai ) > L(ai , ai+1 ). Так как функция целочисленна, то ее значение убывает с каждым шагом по крайней мере на единицу.
Отсюда следует, что общее число шагов не превзойдет значения функции L на исходной паре чисел. Мы рассмотрели функцию L(k, l) = l,и это привело нас к выводу, что число шагов не превзойдет значенияL(a0 , a1 ) = a1 .Для обоснования того, что число делений в алгоритме Евклидарастет медленнее, чем a1 , было бы достаточно найти соответствующую функцию L(k, l), значения которой при больших k, l оказываются существенно меньшими, чем l. Эта функция по-прежнему должнабыть определена для любых неотрицательных целых k, l, k ¾ l, принимать неотрицательные целые значения и убывать при замене парыk, l парой l, r, где r — остаток от деления k на l.
Хотя бы одна пара целых неотрицательных k, l, k ¾ l, должна обращать L(k, l) в нуль,иначе вместо L(k, l) можно взять функцию L′ (k, l) = L(k, l) − 1 и т. д.Предложение .. Пусть k, l ∈ N+ , k > l, и пусть r — остаток отделения k на l. Тогда(i) λ(k) > λ(r), где, как обычно, λ(·) — битовая длина данногочисла;(ii) функцияL(k, l) = λ(k) + λ(l) − 2(.)такова, что L(k, l) > L(l, r).Глава . Оценивание числа шагов (итераций) алгоритмаДоказательство.
(i) Имеем k = ql + r, q ¾ 1, откуда k ¾ l + r > 2r.Следовательно, λ(k) > λ(r).(ii) Из λ(k) > λ(r) следует λ(k) + λ(l) − 2 > λ(l) + λ(r) − 2.Очевидно, что функция (.) неотрицательна. Таким образом,справедлива оценкаCE (a0 , a1 ) ¶ λ(a0 ) + λ(a1 ) − 2.(.)Но если a0 очень велико в сравнении с a1 , то λ(a0 ) + λ(a1 ) − 2 > a1 .Тем не менее, теперь для CE (a0 , a1 ) уже легко выводится хорошаяоценка. Пусть число делений с остатком больше 1. ИмеемCE (a0 , a1 ) = CE (a1 , a2 ) + 1 ¶ λ(a1 ) + λ(a2 ) − 1 ¶ 2λ(a1 ) − 1.ОценкаCE (a0 , a1 ) ¶ 2λ(a1 ) − 1,(.)очевидно, верна и в случае единственного деления: CE (a0 , a1 ) = 1 притом, что λ(a1 ) ¾ 1.Если взять a1 за размер входа (a0 , a1 ), то для сложности по числуделений будем иметьTE (a1 ) = max CE (a0 , a1 ) ¶ 2λ(a1 ) − 1 = 2⌊log2 a1 ⌋ + 2 − 1 ¶ 2 log2 a1 + 1.a0 ¾ a1Доказанное нами можно переформулировать так:Если рассматривать a1 как размер входа a0 , a1 алгоритма Евклида, то для сложности TE (a1 ) по числу делений выполнено неравенствоTE (a1 ) ¶ 2 log2 a1 + 1.(.)Эта же оценка имеет место и при рассмотрении двух параметровa0 , a1 размера входа.Для достаточно больших a1 верхняя оценка (.) существенно лучше, чем TE (a1 ) ¶ a1 .
(Несколько более точная, чем (.), оценка даетсяв задаче .)Рассматривая далее оценки сложности по числу делений алгоритма Евклида, мы будем использовать значение a1 в качестве размеравхода (значение a0 может быть очень большим в сравнении с a1 , нопервое же деление с остатком приведет к a1 , a2 , где a2 < a1 ).Известно, что алгоритм Евклида допускает разнообразные обобщения и расширения. Прежде всего, вместе с íîä(a0 , a1 ) можно находить целые s, t такие, чтоsa0 + ta1 = íîä(a0 , a1 ).(.)§ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
