Реферат: Анализ алгоритма Евклида в Евклидовых кольцах

1год=365 суток 5 часов 48 минут 46 секунд = [365; 4, 7, 1, 3, 5, 64] суток.

Примечание 1. π – иррациональное число. Оно выражается бесконечной цепной дробью. Величина года – эмпирическая. Всякая эмпирическая величина измеряется лишь с определённой точностью, и говорить об её рациональности или иррациональности не имеет смысла. Приведённая выше величина года - принятая, и мы должны считать её точной. Она выражается конечной цепной дробью.

Примечание 2. Чтобы выразить длину года в виде цепной дроби, незачем выражать её десятичной дробью в долях суток (аналогично тому, как мы делали с числом π). Это вычисление производится так (целая часть отброшена):

Находим несколько первых подходящих дробей. Целую часть опустим, так как наличие в каждом году 365 целых суток не требует напоминаний:

Каждый столбец дает решение проблемы календаря. Например, первый столбец дает для длины года приближенное значение 365 суток. Чтобы реализовать такую длину года, надо считать високосным 1 год из 4. Вообще, третья строка дает величину цикла или периода, а вторая – число високосных лет в цикле. Например, второй столбец соответствует такому решению: 7 високосных лет из каждых 29. Средняя длина года при этом получится 365 суток. Это точнее, чем 365, но зато сложнее.

2. Анализ алгоритма Евклида

Прежде чем, приступить к анализу алгоритма Евклида рассмотрим числа Фибоначчи.

Суть последовательности Фибоначчи в том, что начиная с 1,1 следующее число получается сложением двух предыдущих.

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 ….

Приступим к анализу алгоритма Евклида. Нас будет интересовать наихудший случай — когда алгоритм работает особенно долго? Спросим точнее: какие два наименьших числа надо засунуть в алгоритм Евклида, чтобы он работал в точности заданное число шагов? Ответ на этот вопрос дает

Теорема (Ламэ, 1845 г.). Пусть n Î N , и пусть a > b > 0 такие, что алгоритму Евклида для обработки а и b необходимо выполнить точно n шагов (делений с остатком), причем а - наименьшее с таким свойством. Тогда а = F _{n +2} , b = F _{n +1} , где F _k — k- ое число Фибоначчи.

Следствие. Если натуральные числа a и b не превосходят N Î N , то число шагов (операций деления с остатком), необходимых алгоритму Евклида для обработки a и b не превышает

é log _Ф ( Ö 5 N ) ù - 2,

где é a ù - верхнее целое a , F = (1 + Ö 5)/2 — больший корень характеристического уравнения последовательности Фибоначчи.

log _Ф ( Ö 5 N ) » 4,785 · lg N + 1,672, поэтому, например, с любой парой чисел, меньших миллиона, алгоритм Евклида разбирается не более, чем за é 4,785 · 6 + 1,672 ù - 3 = 31 - 3 = 28 шагов.

3. Евклидовы кольца

Неформально, евклидово кольцо — в абстрактной алгебре — кольцо, в котором «работает» алгоритм Евклида.

Примеры

· Кольцо целых чисел Z . Пример евклидовой функции — абсолютное значение .

· Кольцо целых гауссовых чисел Z [i] (где i — мнимая единица, i ² = − 1) с нормой d (a + ib ) = a ² + b ² — евклидово.

· Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.

· Кольцо многочленов в одной переменной K [x ] над полем K . Пример евклидовой функции — степень deg.

· Кольцо формальных степенных рядов K [[x ]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).

· Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z .

· Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C [x ].

4 Аналоги чисел Фибоначчи

Мною были построены аналоги чисел Фибоначчи в кольце многочленов и исследованы некоторые их свойства. Для этих целей я использовала программу Mathematica 5.1.