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

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

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

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

В этом смысле применимость этого алгоритма шире, чем, например, алгоритма, основанного на малой теореме Ферма.Малая теорема Ферма. Пусть p — простое число, a — произвольное целое. Тогда a p ≡ a (mod p).(Путь доказательства показан в задаче .) Если a не делится на p,то согласно этой теореме a p−2 является обратным к a по простомумодулю p. Но это, вообще говоря, неверно для составных p.

Например, неверно, что 55 ≡ 1 (mod 6).С помощью расширенного алгоритма Евклида возможно обращениепо модулю k любого числа a, взаимно простого с k; если a ∈ Ik илиa ∈ Sk , то это обращение имеет битовую сложность O(log2 k) илиO(m2 ), коль скоро в качестве размера входа используется m = λ(k).Пример ..

Уже говорилось, что вопрос о возможности распознавания простоты со сложностью O(md ) с некоторым d ∈ N представляет большой интерес и что, скажем, алгоритм пробных делений(примеры ., ., .) не обладает указанным свойством даже прирассмотрении не битовой сложности, а сложности по числу делений,причем как в худшем случае, так и в среднем.Если для некоторого a ∈ Z, не делящегося на n, мы обнаружим,что не выполняется сравнениеan ≡ a (mod n),(.)Глава .

Битовая сложностьто по малой теореме Ферма из этого можно заключить, что n неявляется простым. Если фиксировано число a такое, что 1 < a < n,то использование бинарного алгоритма возведения в степень с заменой результата каждого из умножений остатком от деления на nпозволяет вычислить an и проверить выполнение сравнения (.),затратив O(log3 n), или, что то же самое, O(m3 ) битовых операций,где m = λ(n). Однако это не позволяет утверждать, что мы можемна основе этого распознавать простоту n за O(m3 ) битовых операций, так как существует бесконечно много составных n таких, что(.) выполняется для любых a, взаимно простых с n. Это так называемые числа Кармайкла (наименьшее из которых равно 561 == 3 · 11 · 17).Напомним, что алгоритм со сложностью O(md ), где m — размервхода, d ∈ N, называют алгоритмом с полиномиально ограниченнойсложностью или полиномиальным.

В задаче распознавания простотычисла за размер входа берется количество m двоичных цифр числа nили же log2 n. После долгих поисков, в которых принимали участиеразные исследователи, алгоритм с полиномиально ограниченной битовой сложностью был в  г. предложен тремя индийскими математиками — М. Агравалом, H. Кайалом и H. Саксеной  . Этот алгоритмполучил в литературе название AKS по первым буквам фамилий авторов. Мы обсудим лишь главную идею алгоритма AKS, основаниемкоторого служит следующее необходимое и достаточное условие простоты числа n.Предложение ..

Пусть a ∈ Z, n ∈ N взаимно просты, тогдаn является простым, если и только если выполнено полиномиальноесравнение(x − a)n ≡ x n − a (mod n),(.)которое надо понимать так, что числовые коэффициенты при одинаковых степенях x в полиномах, расположенных в левой и правойчастях, сравнимы по модулю n.Доказательство. Пусть n — простое. Если n = 2, то выполнение(.) проверяется непосредственно, и остается рассмотреть случайнечетного n.

Коэффициенты при x k в левой и правой частях дляk nслучая 1 < k < n равны соответственно (−1)an−k и 0. При этомk nделится на n, так как n простое (см. задачу ). Коэффициентыkпри x n в обеих частях (.) равны 1, свободные члены соответственСм.

[].§ . Модулярная арифметикано равны (−a)n и −a. В силу нечетности n достаточно показать, чтоan ≡ a (mod n), а это сравнение выполняется в силу малой теоремыФерма. Мы доказали, что если n — простое, то выполнено (.).Пусть теперь n — составное. Пусть, далее, простое q и l ∈ N+ таковы, что q l | n и при этом неверно, что q l +1 | n. Имеем (n − q + 1)(n − q + 2)...nn.=q!qТак как q | n, то произведение (n − q + 1)(n − q + 2)...(n − 1) не делится на q; при этом один из входящих в n множителей, равных q, сокраnтится со знаменателем. Поэтомуне делится на q l .

Помимо этого,qq l взаимно просто с an−q , так как a и q взаимно просты. Поэтому коqn− q n− q nэффициент при x в левой части (.), равный (−1) a, неqделится на q l , следовательно, не делится на n и поэтому не сравнимс  по модулю n. Мы доказали, что если n — составное, то сравнение (.) не имеет места.Из предложения . следует, что для проверки простоты числа nможно взять любое a, взаимно простое с n (подходит, например, ),и проверить (.). Но прямая такая проверка потребует Ω(n) = Ω(2m )битовых операций, так как раскрытие скобок в левой части (.)дает n + 1 слагаемое.

Алгоритм AKS предписывает проверку (.)по двум модулям(x − a)n ≡ x n − a (mod x r − 1, n),(.)r > 0. Сравнение (.) понимается в том смысле, что все коэффициенты остатка от деления полинома (x − a)n − x n + a на x r − 1 (онибудут целыми числами) делятся на n. Вычисление остатков от деления (x − a)n и x n на x r − 1 производится с помощью бинарного алгоритма возведения в степень, результат каждого умножения сразуже заменяется остатком от деления на x r − 1. Но если взять произвольное r ∈ N+ , то может оказаться, что (.) выполняется и принекоторых составных n. Число r должно подбираться специальнымобразом, и авторы показывают, что подходящее для целей алгоритма r всегда существует и может быть выбрано без существенных затрат так, что r = O(m5 ); после выбора r сравнение (.) надо проверить для «небольшого»числа «легко определяемых» a — количествоpэтих a есть O( rm).

Итоговая сложность алгоритма допускает оценку O(m11 ). Заметим попутно, что в литературе по теории сложностиe f (m)) (Oe называется «O мягкое»),часто используются оценки вида O(Глава . Битовая сложностьза таким обозначением скрывается O( f (m) logd m), где d — положительное число, значение которого не уточняется. Авторы показывают,e 21/2 ), укачто битовая сложность их алгоритма допускает оценку O(mзывая при этом, что если верны некоторые известные в теории чиселгипотезы (для которых имеются серьезные основания полагать, чтоони верны), то можно взять r = O(m2 ), и в этом случае сложностьe 6 ).алгоритма в целом есть O(mНа этом мы завершим разговор об алгоритме AKS, добавив лишько всему сказанному, что, например, в криптографии практикуютсявероятностные (типа Монте-Карло) алгоритмы распознавания простоты, имеющие меньшую сложность, но не исключающие появления, хоть и с малой вероятностью, неверного ответа.

В нашем курсетакого рода алгоритмы не рассматриваются  .§ . Булева арифметикаСложность булевых вычислений как сложность по числу булевых операций может рассматриваться как алгебраическая сложность. Но работа с булевыми величинами является фактически работой с битами, и сложность по числу булевых операций в этом смысле совпадает с битовой сложностью. Таким образом, для алгоритмов булевойарифметики алгебраическая сложность по числу булевых операцийи битовая сложность — это одно и то же. Аналогично дело обстоити с пространственной булевой (= битовой) сложностью.Пример .. Пусть дан ориентированный граф G = (V , E), n = | V |.Пусть C = (cij ) — булева матрица смежности графа G: cij = 1, еслии только если i-я вершина соединена ребром с j-й, i, j = 1, 2, ..., n.Требуется построить для G его матрицу связности D = (dij ): dij = 1,если и только если i = j или i-я вершина соединена путем из одногоили более ребер с j-й, i, j = 1, 2, ..., n.

Если рассматривать G как графнекоторого бинарного отношения на множестве из n элементов, тозадачу можно интерпретировать как задачу построения транзитивно-рефлексивного замыкания данного бинарного отношения. Соответственно, граф, для которого D является матрицей смежности, называют транзитивно-рефлексивным замыканием графа G, а саму матрицу D — транзитивно-рефлексивным замыканием матрицы C. Дляматрицы D используется обозначение C ∗ . На рис.

 показан ориентированный граф и его транзитивно-рефлексивное замыкание. СоотПо поводу этих алгоритмов распознавания простоты числа см. [, гл. ] и [,гл. ].§ . Булева арифметика43а)4312б)1525Рис. . а) Ориентированный граф; б) его транзитивно-рефлексивное замыкание.и C ∗ выглядят следующим образом1 1 1 10 11 01 1 1 1. , C∗ = 0 11 1 1 10 0 0 10 0ветствующие матрицы C0 10 1C =1 00 0Нам понадобятся произведения булевых матриц, которые определяются как обычно: например, произведение F квадратных матрицA и B порядка n определяется формулойfij =n_(aik ∧ bkj ),i, j = 1, 2, ..., n.k =1Элемент с индексами i, j для краткости будем называть (i, j)-элементом матрицы.Легко видеть, что C 2 = C ∧ C — это матрица, для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путемдлины 2 (т.

е. состоящим из двух ребер). Аналогично, C k — матрица,для которой (i, j)-элемент равен 1, если и только если i-я вершина соединена с j-й путем длины k. Пусть I — матрица, для которой(i, j)-элемент равен 1, если и только если i = j. ТогдаC ∗ = I ∨ C ∨ C 2 ∨ ... ∨ C n−1 .Индукцией по k несложно доказать, что для любой квадратной булевой матрицы C и натурального k выполненоI ∨ C ∨ C 2 ∨ ... ∨ C k = (I ∨ C)k .(.)C ∗ = (I ∨ C)n−1 .(.)Это дает намГлава . Битовая сложностьТривиальный способ умножения булевых (n × n)-матрицΘ(n3 ) битовых операций.

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

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

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