Главная » Просмотр файлов » Лекции о сложности алгоритмов. С. А. Абрамов

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

Файл №1121249 Лекции о сложности алгоритмов. С. А. Абрамов (Лекции о сложности алгоритмов. С. А. Абрамов) 30 страницаЛекции о сложности алгоритмов. С. А. Абрамов (1121249) страница 302019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

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

Это дает нам оценку сверху3c(log2 a1 )(3 log2 a1 + log2 a0 )для числа битовых операций при a1 > 1. Учитывая, что a0 ¾ a1 , мыполучаем отсюда следующее.Количество битовых операций, затрачиваемых при примененииалгоритма Евклида к a0 , a1 , допускает оценкуO(log a0 log a1 )(.)и оценки O(log2 a0 ), O(m2 ), m = λ(a0 ).Приведенные оценки получены в предположении, что для построения остатков используется наивное деление, имеющее квадратичнуюсложность.

Может ли быть так, что привлечение имеющего меньшуюбитовую сложность алгоритма деления с остатком приведет к существенно меньшим битовым затратам алгоритма Евклида? Ответ отрицательный: нетрудно, например, показать, что если a0 берется в качестве размера входа, то для битовой сложности алгоритма Евклидавыполняется оценка Ω(log2 a0 ).В самом деле, в примере . было показано, что для каждого a0 можно подобрать меньшее его a1 такое, что для числа деленийс остатком выполняется неравенство (.).

Если обозначить это число делений через n, то будем иметь n = Ω(log a0 ), при этомλ(a0 ), λ(a1 ), ..., λ(an )Глава . Битовая сложностьявляется невозрастающей конечной последовательностью натуральных чисел, и в силу предложения . никакое значение не встречаетсяв ней более двух раз. Так как деление с остатком ai−1 на ai требуетне менее λ(ai ) битовых операций, то общее число битовых операций не jможетkбыть меньше, чем 1 + 1 + 2 + 2 + ...

+ k + k = k(k + 1)n+1и n = Ω(log a0 ). Следовательно, общее число битовыхпри k =2операций есть Ω(log2 a0 ).Вместе с ранее установленной оценкой O(log2 a0 ) это дает оценкуΘ(log2 a0 ). Теорема . из §  приводит нас к оценке Θ(m2 ) для битовой сложности алгоритма Евклида при избрании битовой длины mчисла a0 в качестве размера входа. Итак:Если алгоритм Евклида основывается на некотором алгоритме деления с остатком, битовые затраты которого применительно к делимому v и делителю w допускают верхнюю оценку O(log v log w),то при рассмотрении большего входного числа a0 в качестве размера входа битовая сложность алгоритма Евклида допускает оценкуΘ(log2 a0 ).

При рассмотрении m = λ(a0 ) в качестве размера входа имеем оценку Θ(m2 ).Оказывается, что полученные оценки сохраняют силу и при рассмотрении расширенного алгоритма Евклида (пример .) — обстоятельство, имеющее большое значение для модулярной арифметики(§ ).Предложение .. Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целымv и w допускают верхнюю оценку O(log v log w). Тогда, при рассмотрении большего входного числа a0 в качестве размера входа, битовая сложность расширенного алгоритма Евклида допускает оценкуΘ(log2 a0 ), а при рассмотрении битовой длины m большего числа a0в качестве размера входа — оценку Θ(m2 ).Доказательство.

Исходя из вычислительных формул (.) и принимая во внимание (.), (.), мы заключаем, что битовые затраты, дополнительные к затратам собственно алгоритма Евклида («нерасширенного») на вычисление sn , tn , допускают оценкуO(log a0 log a1 ) — это обосновывается так же, как оценка (.). Поэтому сложность добавочной части расширенного алгоритма Евклида допускает оценку O(log2 a0 ) и, в силу теоремы ., оценку O(m2 ).Остается заметить, что, например, Θ(m2 ) + O(m2 ) = Θ(m2 ).§ . Модулярная арифметика§ . Модулярная арифметикаМногие арифметические алгоритмы основываются на вычисленияхпо некоторому целому модулю k, или, как говорят, на модулярныхвычислениях; соответственно, говорят о модулярной арифметике. Далее в этом параграфе мы считаем k фиксированным целым положительным числом.Целые a и b называют сравнимыми по модулю k и пишутa ≡ b (mod k),(.)если k | (a − b), т.

е. если k является делителем разности a − b. Соотношение вида (.) называется сравнением. Изложение основ теориисравнений можно найти в любом учебнике алгебры  . Мы приведемосновные элементарные факты этой теории, не останавливаясь на ихдоказательстве:(i) бинарное отношение сравнимости по модулю k является отношением эквивалентности на множестве целых чисел Z;(ii) еслиa1 ≡ b1 (mod k) и a2 ≡ b2 (mod k),тоa1 ± a2 ≡ b1 ± b2 (mod k) и a1 a2 ≡ b1 b2 (mod k);(iii) каждое целое число a сравнимо по модулю k в точности с одним целым числом из множества {0, 1, ..., k − 1}.В силу (i) множество Z разбивается на классы эквивалентности помодулю k (кратко: классы по модулю k), и, согласно (ii), эти классыобразуют кольцо, если считать, что сумма двух классов — это класс,содержащий сумму каких-либо чисел, взятых по одному из складываемых классов, а произведение — это, соответственно, класс, содержащий произведение каких-либо чисел, взятых по одному из перемножаемых классов.

Нулем этого кольца является класс, содержащийчисло 0. Для введенного кольца используется обозначение Zk , его называют кольцом вычетов по модулю k (вычет — это в данном случаедругое название класса эквивалентности по модулю k).Любое множество {a0 , a1 , ..., ak−1 } чисел, взятых по одному из каждого класса по модулю k, называется полной системой представителей по модулю k.МножествоIk = {0, 1, ..., k − 1},См., например, [, § , ] и [, гл. , § , п. ].Глава .

Битовая сложностьуказанное в (iii), называется канонической (или начальной) полнойсистемой представителей по модулю k. Иногда используется и симметричная полная система представителей:mj konlk−k + 1, ..., −1, 0, 1, ...,,Sk =22которая является симметричной (при условии игнорирования знаков) только при нечетном k: например, S3 = {−1, 0, 1} и S4 == {−1, 0, 1, 2}.Пусть для изображения элементов кольца Zk используется система Ik . Операциям сложения и умножения в Zk соответствуют обычные сложение и умножение в Z с последующей заменой полученногорезультата остатком от его деления на k.

Если некоторому элементу кольца Zk соответствует число a системы Ik , то противоположному (обратному по сложению) элементу будет соответствовать числоk − a, если a 6= 0, и число 0, если a = 0.Исследуем битовую сложность операций в кольце Zk . Будем считать размером входа битовую длину m числа k и ограничимся верхними асимптотическими оценками.

Для операций сложения и нахождения противоположной величины имеем, очевидно, оценку O(m). Использование операции наивного умножения целых чисел приводитк оценке O(m2 ) для сложности умножения в Zk . Эта оценка, разумеется, сохраняется и при использовании более быстрого умноженияи деления в Z.Как известно, в случае простого k кольцо Zk является полем. Присоставном k это кольцо полем не является и, более того, содержит делители нуля: если k = pq, p > 1, q > 1, то произведение элементов Zk ,изображаемых числами p, q ∈ Ik , равно нулю.

Допустим, что k является простым и примем для этого простого числа обозначение p,по-прежнему считая его битовую длину равной m. Нахождение обратного к элементу кольца Z p , представленному целым ненулевымчислом a ∈ I p , может быть выполнено с помощью расширенного алгоритма Евклида. Так как p и a, очевидно, взаимно просты, то c помощью расширенного алгоритма Евклида можно найти s и t такие, чтоsp + ta = 1. Получаем ta ≡ 1 (mod p), т.

е. обратным к классу, содержащему a, является класс, содержащий t. В силу (.) имеем | t | < p;если t < 0, то заменяем t на t + p (напомним, что мы используемэлементы системы I p для изображения элементов поля Z p ).Пример .. Для p = 13, a = 5 получаем с помощью расширенногоалгоритма Евклида 2 · 13 + (−5) · 5 = 1, и отсюда 8 = −5 + 13 являетсяобратным для 5 в Z13 (проверка подтверждает это: 5 · 8 ≡ 1 (mod 13)).§ . Модулярная арифметикаКак следствие предложения . получаем такое утверждение.Предложение ..

Пусть расширенный алгоритм Евклида основывается на некоторых алгоритмах деления с остатком и умножения, битовые затраты каждого из которых применительно к целымv и w допускают оценку O(log v log w). Тогда битовая сложность обращения в поле Z p с помощью расширенного алгоритма Евклида допускает оценку O(log2 p) при использовании числа p в качестве размеравхода и, соответственно, оценку O(m2 ) при использовании в этомкачестве битовой длины m числа p.Несомненным достоинством алгоритма обращения, основанногона расширенном алгоритме Евклида, состоит в том, что с его помощью обращение возможно всякий раз, когда обращаемое число и модуль взаимно просты, а не только тогда, когда модуль — простое число. Например, можно определить a такое, что 5a ≡ 1 (mod 6) — средичисел, входящих в I6 , значением a является 5.

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

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

Свежие статьи
Популярно сейчас
Как Вы думаете, сколько людей до Вас делали точно такое же задание? 99% студентов выполняют точно такие же задания, как и их предшественники год назад. Найдите нужный учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6510
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее