С.А. Абрамов - Лекции о сложности алгоритмов (pdf) (1123764), страница 43

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

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

Элемент, взятый первым, расположенна (p + 1)-м месте и сравнивается со следующим за ним. Равенствоp + q = n − 1 означает, что разбиение завершено.Сîðòèðîâêà. Выполняется разбиение; в результате элемент, ранеерасполагавшийся в массиве первым, занимает нужное место (с некоторым номером k, 1 ¶ k ¶ n). Затем быстрая сортировка применяетсярекурсивно к сегментам x1 , x2 , ..., xk−1 и xk+1 , xk+2 ..., xn .A. ПоискЧисловой массив x1 , x2 , ..., xn имеет попарно различные элементы.В п.

 элементы предполагаются упорядоченными по возрастанию.. Поиск наименьшего. Просматриваются последовательно x2 ,x3 , ..., xn и каждый новый элемент xi сравнивается с уже найденнымнаименьшим среди x1 , x2 , ..., xi−1 .. Поиск m-го наименьшего. Элементы x1 , x2 , ..., xn переставляются в соответствии с процедурой разбиения (см. алгоритм быстрой сортировки). Пусть элемент, бывший в исходном массиве первым, после выполнения процедуры стал k-м, 1 ¶ k ¶ n. Если m = k, тозадача решена. Если m < k, то разыскивается m-e наименьшее среди x1 , x2 , ..., xk−1 ; если m > k, то разыскивается (m − k)-е наименьшеесреди xk+1 , xk+2, ..., xn .. Одновременный поиск наименьшего и наибольшего.

Элементы x1 , x2 , ..., xn просматриваются последовательными парами:x1 , x2 , затем x3 , x4 и т. д. (последний элемент может остаться безпары). При рассмотрении k-й пары x2k−1 , x2k в ней выбираются наименьший и наибольший элементы, которые сравниваются с уженайденными наименьшим и, соответственно, наибольшим средиx1 , x2 , ..., x2k−2 . Если n нечетно, то на последнем шаге xn сравнивается с уже найденными наименьшим и наибольшим среди x1 , x2 , ......, xn−1 ..

Бинарный поиск места элемента. Кроме упорядоченного массива x1 < x2 < ... < xn дано число y, для которого априори может осуществляться любая из возможностейy ¶ x1 ,x1 < y ¶ x2 , ...,x n −1 < y ¶ x n ,xn < y.Этим возможностям присваиваются номера 1, 2, ..., n + 1. Требуется найти номер фактически осуществившейся возможности. Первоначальный диапазон поиска — от 1 до n + 1. Каждый шаг би-Основные алгоритмы сортировки и поисканарного поиска сужает диапазон примерно вдвое: если перед очередным шагом диапазон был от p до q, то y сравнивается с xr ,r = ⌊(p + q)/2⌋. При xr < y диапазон дальнейшего поиска — от r + 1до q (в дальнейшем рассматривается сегмент xr +1 , xr +2 , ..., xq−1), впротивном случае — от p до r (в дальнейшем рассматривается сегмент x p , x p+1 , ..., xr ).

И так далее до совпадения границ диапазона.Приложение BОценивание сумм значений монотонныхфункцийПредложение B.. Пусть f — неубывающая или невозрастающаянепрерывная на отрезке [n0 , n1 ] функция, n0 , n1 ∈ Z. ТогдаZ n1Z n1n1Xf (k) ¶f (x) dx + f (n0 ) ¶n0f (x) dx + f (n1 )в случае неубывающей f иZ n1f (x) dx + f (n1 ) ¶n0n1X(B.)n0k = n0Zn1f (k) ¶f (x) dx + f (n0 )(B.)n0k = n0в случае невозрастающей f .Доказательство.

Пусть f — неубывающая функция. Рис.  поnPnP1 −11 −1R n1казывает, чтоf (k) ¶ n f (x) dx (значениеf (k) равно сумме0k = n0...Рис. .nP1 −1k = n0f (k) ¶n1 − 1n1...n0n0 + 1n0 + 2k = n0R n1n0f (x) dx .Оценивание сумм значений монотонных функцийплощадей выделенных прямоугольников с вертикальными сторонами f (n0 ), f (n0 + 1), ..., f (n1 − 1)). Соответственно, рис.  показывает,...n1PРис.

.f (k) ¾k = n0 + 1чтоn1Pf (k) ¾R n1k = n 0 +1n0n1 − 1n1n0n0 + 1n0 + 2...R n1n0f (x) dx .n1Pf (x) dx (значениеf (k) равно сумме пло-k = n 0 +1щадей выделенных прямоугольников с вертикальными сторонамиf (n0 + 1), f (n0 + 2), ... f (n1 )). Это дает нам (B.).

Неравенства (B.)доказываются аналогично.pРассмотрим некоторые примеры. Функция x не убывает на правой полуоси. ИмеемZnZnn pXpppx dx + 1 ¶k¶x dx + n,11k =1т. е.2 p 3 1( n) + ¶33n pXk =1k¶2 p 3 p2( n) + n − ,33и, как следствие,n pXk =1p2 pk = ( n)3 + O( n).3Аналогично выводится, что при любом вещественном α ¾ 0 и n → ∞nPnα+1. (Справедлива ли эта формула при всехвыполняетсяkα ∼k =0α 6= −1?)α+1ФункцияПриложение B1не возрастает при x ¾ 1. ИмеемxZn11dx+ ¶xnэто дает намln n ¶nXk =1nXk =1и, как следствие,nXk =11¶kZn1dx+ 1,x1¶ ln n + 1,k1= ln n + O(1).kПриложение CПроблема орбитC.

Показательная функция и логарифмическая оценкаВ этом разделе приложения рассказывается об одной вычислительной задаче и об эффективном решении ее некоторого частного случая; почти все факты приводятся без доказательств. В разделе C мырассмотрим оставшийся случай с бо́льшими подробностями.Речь идет об одном из вариантов известной «проблемы орбит».Даны две квадратные матрицы A и B одинакового порядка с элементами из поля Q.

Существуют ли натуральные m такие, что Am = B?Если да, то надо указать все такие m. Рассмотрение собственных значений матриц A и B приводит к вопросу о распознавании существования и поиске натуральных m таких, чтоam = b(C.)для данных алгебраических чисел a и b.Напомним, что число a ∈ C называется алгебраическим, если существует полином над полем Q, для которого a является корнем.В качестве такого полинома удобно рассматривать унитарный  полином, т. е.

полином с единичным старшим коэффициентом. Можнопоказать, что для всякого алгебраического числа существует единственный унитарный неприводимый над Q полином, для которогоa является корнем. Алгебраическое число a ∈ C называется целым алгебраическим, если соответствующий неприводимый унитарный полином является полиномом над Z, т. е.

имеет целыеp коэффициенты .Нетрудно, например, убедиться,что число (1 + 5)/2 — целое алгебpраическое, а число (3 + 4 −1)/5 — нецелое алгебраическое.Используются также термины приведенный, нормированный.Для избежания терминологической путаницы между целыми алгебраическими числами и обычными целыми, т. е. элементами Z, последние в теории алгебраическихчисел часто называют целыми рациональными числами.Приложение CЕсли | a | 6= 1, то с исследованием и решением уравнения (C.) серьезных трудностей не возникает, так как модуль значения показательной функции am монотонно возрастает или монотонно убывает,и можно получить логарифмическое ограничение на m. Задача становится интересной при | a | = 1 и при дополнительном условии, чтоa не является корнем из 1. (Если a есть корень из единицы, то задачатривиальна.)Как это следует из элементарной теории алгебраических чисел,вопрос можно переформулировать так: дан неприводимый над Q полином f (x), deg f (x) = n, и некоторый полином q(x) над Q степениdeg q(x) < n; существуют ли такие натуральные m, чтоam = q(a)(C.)при любых a ∈ C, для которых f (a) = 0, и если да, то как найти такие m? Мы сосредоточимся на последнем вопросе, опуская мелкиеподробности перехода к нему от проблемы орбит.Особенность постановки вопроса об уравнении (C.) состоит втом, что речь идет не об одном фиксированном корне полинома f (x),но обо всех его корнях.

Легко показать, что если равенство (C.) верно для одного какого-то корня a0 полинома f (x), то оно верно длявсех корней этого полинома. В самом деле, если для некоторого фиксированного m полиномы x m − q(x) и f (x) имеют общий корень a0 ,то эти полиномы имеют нетривиальный общий делитель. Наибольший общий делитель этих полиномов может быть найден алгоритмомЕвклида и, следовательно, должен иметь рациональные коэффициенты. Из этого и из неприводимости f (x) над Q следует, что наибольший общий делитель равен f (x). Отсюда получаем, что x m − q(x) делится на f (x). Это означает, что каждый корень f (x) является такжекорнем x m − q(x).Таким образом, задача о всей совокупности корней эквивалентна задаче об одном фиксированном корне, и задача об одном фиксированном корне эквивалентна задаче о любом другом корне.

Этообстоятельство позволяет справиться со случаем целого алгебраического a. К решению подводит серия результатов о корнях унитарныхполиномов над Z, начавшаяся с работ Кронекера и завершившаясяв  —-е годы XX века исследованиями А. Шинцеля, Г. Цассенхауза,П. Бланксби и Х. Монтгомери  . Выяснено, что если унитарный полином над Z степени n таков, что его корни не являются корнями изCм.

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

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