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

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

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

При быстрой сортировке (в любом из рассмотренных ее вариантов) число пар индексов (i, j), попадающих в стек отложенныхзаданий, не превосходит длины n исходного массива.. Верно ли, что определение усредненных затрат некоторогорандомизированного алгоритма требует задания распределения вероятностейа) на множестве всех допустимых входов?б) на каждом из множеств всех входов фиксированного размера?. Если измерять затраты рандомизированной быстрой сортировки количеством обращений к генератору случайных чисел, то сложность этой сортировки есть величина порядка n. То же самое верно,если в определении функции затрат вместо математического ожидания взять максимум затрат по соответствующим сценариям..

Идея, лежащая в основе быстрой сортировки, может бытьиспользована для нахождения m-го наименьшего элемента средиa1 , a2 , ..., an , 1 ¶ m ¶ n (самый маленький элемент — это -й наименьший, следующий элемент — -й наименьший и т. д.). Разбиение массива с использованием случайно выбранного разбивающего элементапорождает два массива длины i − 1 и n − i при некотором 1 ¶ i ¶ n.

Если m = i, то поиск закончен, если m ¶ i − 1, то далее рекурсивно находится m-й наименьший в первом массиве, а если m > i, то рекурсивнонаходится (m − i)-й наименьший во втором массиве. Можно ввестисложность по числу сравнений при рассмотрении двух параметровГлава . Сложность в среднемn, m размера входа. Беря максимум этих сложностей по всем m та¯ким, что 1 ¶ m ¶ n, определяем сложности T(n), ¯T(n)по числу сравнений в худшем случае и в среднем с использованием n в качестве¯размера входа. Показать, что T (n) = Θ(n2 ) и ¯T(n)< 4n.Указание. Возьмем U(n) = max ¯T̄ (k).

Очевидно, что U(n) не убывает при1¶ k ¶ nвозрастании n и что ¯T̄(n) ¶ U(n). Доказывается неравенство1nU(n) ¶ (U(n − 1) + max{U(1), U(n − 2)} + ...... + max{U(n − 2), U(1)} + U(n − 1)) + n − 1,из которого, в силу неубывания U(n), следуетj k2nU(n) ¶U(n − 1) + U(n − 2) + ... + U+ n.n2Отсюда с помощью индукции выводится, что U(n) < 4n для всех n ¾ 1.. В инверсионном векторе (b1 , b2 , ..., bn ) произвольной перестановки (a1 , a2 , ..., an ) ∈ Πn каждая компонента bi равна количеству целых j таких, что 1 ¶ j < i и a j > ai . Например, инверсионный векторперестановки (2, 4, 3, 1, 6, 5) — это (0, 0, 1, 3, 0, 1).

Показать, что каждому целочисленному вектору (b1 , b2 , ..., bn ), для которого 0 ¶ bi < i,i = 1, 2, ..., n, соответствует некоторая перестановка длины n, для которой этот вектор является инверсионным.Указание. Очевидно, что если bn = k, 1 ¶ k < n, то an = n − k, и это соображение приводит к алгоритму построения (a1 , a2 , ..., an ), применимомук любому вектору b, удовлетворяющему оговоренным условиям: просматриваем компоненты вектора b, продвигаясь от последней к первой, находимзначение соответствующей компоненты перестановки a и удаляем найденное значение из множества M , первоначально равного {1, 2, ..., n}; при этомзначение ai , i = n, n − 1, ..., 1, определяется как (bi − 1)-й наибольший в множестве M (самый большой элемент — это первый наибольший, следующийпо величине элемент — это второй наибольший и т.

д.).. Показать, что один этап пузырьковой сортировки понижает наединицу значение каждой неотрицательной компоненты инверсионного вектора перестановки (см. предыдущую задачу) и не изменяетнулевые компоненты. Показать, что вероятность того, что значениемаксимума компонент инверсионного вектора выбранной наугад перестановки длины n равно k, 0 ¶ k < n, естьkn−k k!.n!Указание ко второй части задачи. Количество векторов (b1 , b2 , ..., bn ), длякаждого из которых bi ∈ N+ , 0 ¶ bi < i, i = 1, 2, ..., n, и max{b1 , b2 , ..., bn } ¶ k,Задачи1 ¶ k ¶ n − 1, равно k! kn−k−1 , так как bi может принимать любое значениемежду 0 и i − 1 при i ¶ k и любое значение между 0 и k − 1 для k < i ¶ n..

Показать, что математическое ожидание числа этапов пузырьковой сортировки совпадает с (.).Указание. Пользуясь решением предыдущей задачи, легко получить, чтоэто математическое ожидание естьn1 X(k(kn−k k! − (k − 1)n−k+1 (k − 1)!),n!что равноXn1n!k =1k =1(kn−k+1 k! − (k − 1)n−k+2 (k − 1)!) −n‹X(k − 1)n−k+1 (k − 1)! .k =1В упрощении последнего выражения поможет дискретный аналог формулыНьютона—Лейбница (см. задачу ).. Используя идею решения задачи , предложить рандомизированный алгоритм восстановления перестановки длины n по ее инверсионному вектору (см.

задачу ), имеющий сложность в среднемпо числу сравнений O(n2 ).. Пусть (a1 , a2 , ..., an ) — произвольная перестановка длины n. Еепреобразованиеfor i = n downto 2 do j := 1 + random(i − 1); ai ↔ a j od1. (Этоможет дать любую перестановку длины n с вероятностьюn!дает алгоритм построения случайных перестановок с равномернымраспределением вероятностей.).

Предположим, что у нас нет другого генератора случайных чисел, кроме генератора, в результате обращения к которому появля1(аналог подбрасыванияется 0 или 1 с одинаковой вероятностью2монеты), и пусть p, 0 ¶ p ¶ 1, — заданное вещественное число. Каким образом с помощью этого генератора можно определить генератор randp, в результате обращения к которому появляется 0 или 1с вероятностями соответственно p и 1 − p (незначительные отклонения допустимы)? Сложность в среднем алгоритма получения одногослучайного числа с помощью randp должна быть меньше 2 (затратыопределяются числом обращений к изначально имеющемуся генератору).Указание. Представить 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.

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

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