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

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

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

При использовании m = λ(a1 ) в качестве размера входа алгоритма Евклида и его расширенного варианта для соответствующихмультипликативных сложностей справедливы верхние оценки 2m − 1и, соответственно, 6m + 3.. Бинарный алгоритм Евклидана том, что если a0 и a1 a a основан01,; если a0 четно, но a1 нечетчетны, то íîä(a0 , a1 ) = 2 íîä2 2a0, a ; если a0 нечетно, но a1 четно,но, то íîä(a0 , a1 ) = íîä2 1a1; если a0 и a1 нечетны, то можно пето íîä(a0 , a1 ) = íîä a0 ,2рейти к вычислению íîä(a0 − a1 , a1 ) при a0 ¾ a1 и к вычислениюíîä(a0 , a1 − a0 ) при a0 < a1 .

Вычисления заканчиваются, как толькона некотором этапе вычитание даст нуль. Выполнение этого алгоритма завершается для любых исходных a0 , a1 , для которых a0 ¾ a1 > 0.Для числа шагов алгоритма как функции от a0 , a1 справедлива оценка O(log a0 ).Указание. По крайней мере на одном из двух последовательных шаговэтого алгоритма по крайней мере одно из чисел делится на два.Задачи.

Пусть в ходе применения алгоритма Евклида к числам a0 , a1 ,a0 > a1 , возникают ненулевые остатки a2 , a3 , ..., an , и an+1 = 0. Тогдаan−t ¾ Ft +2 , t = 0, 1, ..., n − 1. Отсюда следует справедливость следующего предложения, обычно именуемого в литературе теоремой Ламе.Пусть в ходе применения алгоритма Евклида к числам a0 , a1 , a0 > a1 ,возникают ненулевые остатки a2 , a3 , ..., an . Тогда a1 ¾ Fn+1 .. (Продолжение задачи .) Пусть в ходе применения алгоритма Евклида к числам a0 , a1 , a0 > a1 , возникаютненулевые остаткиpa2 , a3 , ..., an . Тогда n < logφ (a1 + 1) + logφ 5 − 1, и, как следствие,n < logφ a1 + c для некоторой константы c..

Привести доказательство равенства (.).. Доказать оценку (.).Указание. В §  при рассмотрении примера . уже доказано, что еслиF2n−2a0∈ Φn , n > 2, то выполнены неравенства (.). Вывести отсюда, что¶a1F2n−3F2n−1a2a2¶, т. е.∈ Φn−1 , n > 2.¶a3F2n−2a3. Разработать алгоритм, распознающий существование у уравненияax + by = c, a, b, c ∈ Z,(.)решения в неотрицательных целых числах, и исследовать мультипликативную сложность этого алгоритма.Указание.

Уравнение (.) тогда и только тогда имеет решение в целыхчислах, когда d | c, где d = íîä(a, b).. Если x0 , y0 — одно из целочисленных решений уравнения(.), то все решения описываются формуламиbdx = x0 + t,ady = y0 − t,t = 0, ±1, ±2, ...,d = íîä(a, b).Указание. Если x0 , y0 и x1 , y1 — два различных решения уравнения (.),то x0 − x1 , y0 − y1 — решение уравненияabx + y = 0.dd. Числа si , ti , получаемые в ходе выполнения расширенного алгоритма Евклида, являются взаимно простыми при i = 0, 1, ..., n + 1.Указание.

Индукцией по i доказать равенство t− q i −1 1−q1 1= i...si1010t i −1s i −1для i = 2, 3, ..., n − 1 и рассмотреть определители обеих его частей.Глава . Оценивание числа шагов (итераций) алгоритма. При некоторых значениях n число сравнений, затрачиваемыхпри бинарном поиске, не определяется однозначно исходя лишь иззначения n (например, зная лишь, что n = 6, мы не можем указатьточное число сравнений). Но существует бесконечно много n таких,для которых это значение определяется единственным образом и равно ⌊log2 n⌋ + 1.. Бинарный поиск места элемента y в упорядоченном массивеx1 < x2 < ... < xn требует ⌊log2 (n + 1)⌋ сравнений в лучшем случае.

Какследствие, для значений n вида 2k − 1, k = 1, 2, ..., и только для нихчисло сравнений однозначно определено.Указание. Пусть µ(n) — минимум числа сравнений при бинарном поискеместа элемента. Имеем µ(1) = 1, и по индукцииможно доказать, что приkjn−1+ 1. Отсюда следует, чтоn ¾ 2 выполнено µ(n) ¾ µ(n − 1) и µ(n) = µ2µ(n) равно числу положительных элементов последовательностиŸœjn−1kkj−1n−12, ...(.),n,2jЗаметим, что λkn−12k2= λ(n) − 1, если n 6= 2k , и λkjn−12k= λ(n) − 2,если n = 2 , k > 0.

Если n = 2 − 1, k > 0, то число положительных элементов (.) равно λ(n); в остальных случаях в последовательности (.) имеется в точности один элемент вида 2k , k > 0, и число положительных элементов рассматриваемой последовательности равно λ(n) − 1.. Опорная прямая к многоугольнику P, проходящая через точку Q, внешнюю по отношению к многоугольнику, — это прямая, которой принадлежит по крайней мере одна вершина многоугольника P, и при этом все вершины этого многоугольника лежат в однойполуплоскости по отношению к этойпрямой (рис. ). Предложить имеющий сложность в O(n) по общему числу операций алгоритм проведения двухPопорных прямых к данному выпукломуn-угольнику из данной точки.QУказание. Сначала найдем сторонуn-угольника, которая видна из точки QРис.

. Опорные прямые(см. пример .). Это даст две соседние верк многоугольнику.шины n-угольника. Через точку Q и каждуюиз этих вершин проведем прямые. Затемсдвигаемся от каждой из этих двух вершин в сторону, противоположнуюдругой вершине, пока увеличивается угол с вершиной Q .Задачи. Сложность алгоритма, схематически описанного в указании кпредыдущей задаче, есть Θ(n). (Вместе с тем, возможно построениеопорных прямых со сложностью Θ(log n) — для этого надо применитьнекий вариант бинарного поиска для нахождения каждой из тех двухвершин, через которые проходят искомые опорные прямые.). Предложить имеющий сложность O(n1 + n2 ) по общему числу операций алгоритм построения выпуклой оболочки объединениядвух выпуклых многоугольников, имеющих, соответственно, n1 и n2вершин, считая n1 + n2 размером входа.Указание.

Один из известных алгоритмов этого построения основываетсяна том, что, взяв некоторую точку Q , принадлежащую первому многоугольнику, мы, в том случае, когда эта точка принадлежит и второму многоугольнику, можем путем слияния двух упорядоченных последовательностей получитьпоследовательность всех вершин обоих многоугольников, упорядоченных повеличине углов, под которыми видны эти вершины по отношению к какой-нибудь фиксированной прямой, проходящей через Q .

После этого, как в алгоритме Грэхема (см. пример .), можно удалить вдавленные вершины. Если Q непринадлежит второму многоугольнику, то проведем из Q две опорные прямыеко второму многоугольнику. Пусть S и T — вершины второго многоугольника, через которые проходят опорные прямые (если опорная прямая проходитчерез несколько вершин, то из них выбирается наиболее удаленная от Q ). Исключим из рассмотрения все принадлежащие треугольнику QST вершины второго многоугольника, кроме вершин S и T (рис. ). Оставшиеся вершины рассматриваем в порядке возрастания углов; сливаем, как и в первом случае, двеупорядоченные последовательности, а затем удаляем вдавленные вершины.а)SQб)в)QQTРис.

. Этапы построения выпуклой оболочки объединения двух выпуклыхмногоугольников.. Верно ли, что сложность по числу сравнений сортировки массива из n элементов бинарными вставками есть n log2 n + O(1)?. Обратимся к известной школьной задаче: имеются 3m монет,из которых одна фальшивая (более легкая); с помощью чашечныхвесов без гирь надо за m взвешиваний определить фальшивую мо-Глава . Оценивание числа шагов (итераций) алгоритманету. Сравнение по весу двух групп по 3m−1 монет сужает диапазонпоследующего поиска до 3m−1 монет, поэтому в итоге будет затрачено m взвешиваний, как и требуется.

Для числа монет n = 3m мыимеем алгоритм, использующий log3 n взвешиваний. (Здесь мы рассматриваем n в качестве размера исходной группы монет.) Можнообобщить этот алгоритм на произвольное число монет n так, чточисло взвешиваний будет ограничено близкой к log3 n функцией:сравниваем по весу две группы, в каждой из которых по ⌈n/3⌉ монет, это сужает диапазон дальнейшего поиска до не превосходящего⌈n/3⌉ числа монет; затем действуем тем же способом. Получить верхнюю границу ⌈log3 n⌉ для числа взвешиваний сопоставлением размеров групп с элементами последовательности 1, 3, 9, ... подобно тому, как при анализе сортировки фон Неймана количество упорядоченных сегментов сопоставлялось с элементами последовательности1, 2, 4, ....

Изменим алгоритм поиска фальшивой монеты (задача ): будем сравнивать по весу две группы, в каждой из которых по ⌊n/3⌋монет, и т. д.а) Показать, что этому алгоритму может потребоваться числовзвешиваний, которое превосходит ⌈log3 n⌉.б) Получить верхнюю границу ⌊log3 n⌋ + 2 для числа взвешиваний сопоставлением размеров групп с элементами последовательности 1 + 2, 3 + 2, 9 + 2, ... подобно тому, как в при анализе бинарногопоиска размеры сегментов сопоставлялись с элементами последовательности 1, 2, 4, .... Вернемся к начальному варианту алгоритма определения фальшивой монеты (задача ). При некоторых значениях n количествовзвешиваний не определяется однозначно исходя лишь из значения n(например, при n = 10), хотя и существует бесконечно много n таких,для которых это значение определяется единственным образом..

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

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