Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата

2. Полиномиальные алгоритмы

Четыре приведённых ниже алгоритма относятся к разряду так называемых полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит m, то сложность алгоритмов этого типа оценивается величиной
O(lncm), где c – некоторая абсолютная постоянная. Во всех приведённых примерах с =1.

Следующий алгоритм вычисляет admod m. При этом, конечно, предполагается, что натуральные числа a и d не превосходят по величине m.

2.1 Алгоритм вычисления ad mod m

1. Представим d в двоичной системе счисления d = d02r+…+dr-12+dr, где di, цифры в двоичном представлении, равны 0 или 1, d0 = 1.

2. Положим a0 = a и затем для i = 1,…,r вычислим ai ( a2i-1adi (mod m).

3. ar есть искомый вычет admod m.

Справедливость этого алгоритма вытекает из сравнения

ai ( a2i-1ad02^i+…+di (mod m),

легко доказываемого индукцией по i.

Так как каждое вычисление на шаге 2 требует не более трёх умножений по модулю m и этот шаг выполняется r ( log2 m раз, то сложность алгоритма может быть оценена величиной O(ln m).

2.2 Дихотомический алгоритм возведения в степень.

В общем виде дихотомический алгоритм позволяет вычислить n–ю степень в моноиде. Будучи применён к множеству целых чисел с операцией сложения, этот метод позволяет умножать два целых числа и более известен как египетское умножение.

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

Возьмём моноид М с операцией умножения и рассмотрим некоторый элемент x0 из М, а также произвольное натуральное число n0. Для того, чтобы вычислить

, представим n0 в двоичной системе счисления: n0 = bt2t + bt – 12t – 1 + … + b121 + b020, предполагая, что n0 содержит (t + 1)двоичных цифр (т. е. что bt ( 0 и bt +
1 = 0). В этих условиях вычисляемое выражение может быть записано:

или же .

Если задана последовательность (xi)0 ( i ( t, первый элемент которой есть x0 и xi для i( [1,t] определено соотношением xi = xi – 12, то можно записать = (xi . Чтобы завершить построение алгоритма и иметь возможность получить значение предыдущего произведения, необходимо вычислить биты bi числа n0. Для последовательности
(ni) 0 ( i ( t+1 (с начальным элементом n0), определённой соотношением ni =
[ni–1/2] для любого i ( [1, t + 1], бит bi равен нулю, если ni чётно, и равен единице в противном случае. Первое значение индекса i, для которого ni равно нулю, есть t + 1.

Ясно, что число итераций, необходимых для выполнения алгоритма, зависит только от показателя n.

2t ( n ( 2t + 1 или t ( log2n < t + 1.

Первая часть этого свойства может быть выражена следующим образом: [n/2t
+ 1] = 0 и [n/2t] ( 0, что позволяет точно определить число совершаемых делений n, равное числу итераций алгоритма при заданном значении n.
Очевидно, нужно совершить t + 1 итераций, чтобы выполнить алгоритм, т. е.
[log2n] + 1 итераций. Следовательно, трудоёмкость алгоритма есть O(log n).

Третий алгоритм – это классический алгоритм Евклида вычисления наибольшего общего делителя целых чисел. Мы предполагаем заданными два натуральных числа a и b и вычисляем их наибольший общий делитель (a,b).

2.3 Алгоритм Евклида
1. Вычислим r – остаток от деления числа a на b, a = bq+r, 0 ( r < b.
2. Если r = 0, то b есть искомое число.
3. Если r ( 0, то заменим пару чисел (a,b) парой (b,r) и перейдём к шагу1.

Не останавливаясь на объяснении, почему алгоритм действительно находит
(a,b), докажем некоторую оценку его сложности.

Теорема 1. При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

Рекомендуем скачать другие рефераты по теме: доклад 6 класс, здоровый образ жизни реферат.





Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата