Анализ алгоритма Евклида в Евклидовых кольцах (стр. 2 из 3)
поскольку
6+
>6+ 
.Приведенное сравнение
> 
было выполнено в IIIв. до н.э. Аристархом Самосским в трактате «О расстоянии и размерах Луны и Солнца».Сейчас известно, что подходящие дроби разложения любого (рационального или иррационального) числа в цепную дробь представляют собой наилучшие рациональные приближения этого числа.
1.2 Математическая проблема календаря
Григорий XIIIне был математиком. Он был римским папой, но его имя связано с важной математической задачей – проблемой календаря.
Природа дала нам две естественные единицы времени: год и сутки (солнечные). как сказано в одном старом учебнике космографии, «к сожалению, год не равен целому числу суток». С этим нельзя не согласиться, так как из упомянутого факта проистекает много неудобств. Зато он порождает интересную математическую проблему.
1
 |
год = 365 суток 5 часов 48 минут 46 секунд=365,2421199 суток.
Узаконить в гражданской жизни такую длину года невозможно. А что получится, если принять гражданский год равным ровно 365 суткам? На рис. показана орбита Земля. 1 января 1980 года в 0 часов Земля находилась в точке А. за 365 суток она не дойдёт до точки А и 1 января 1981 года в 0 часов окажется в точке В, а 1 января 1982 года – в точке С и т.д. Получится, что если отмечать положение Земли на орбите, соответствующие фиксированной дате, то оно будет каждый год иное: оно будет отставать почти на 6 часов. За 4 года отставание состоит почти сутки, и фиксированная дата будет попадать на разные времена года, т.е. 1 января с зимы постепенно переместится на осень, потом на лето.
Выход из этого положения есть. Надо считать, что в некоторых годах по 365 суток, а в некоторых – по 366, чередуя годы так, чтобы средняя длина года была возможно ближе к истинной. Так можно воспроизвести истинную длину года с любой точностью, но для этого может понадобиться очень сложный закон чередования коротких (простых) и длинных (високосных) годов, что нежелательно. Нужен компромисс: сравнительно простой закон чередования коротких и длинных годов, дающий среднюю длину года, достаточно близкую к истиной.
Эту задачу впервые решил Юлий Цезарь. Точнее говоря, это сделал по его поручению александрийский астроном Созиген, вызванный для этой цели в Рим. Юлий Цезарь ввёл такую систему: три года подряд коротких (простых), четвёртый – длинный (високосный). Много позже, когда было принято христианское летосчисление, високосными стали считать годы, номера которых делятся на 4.
Этот календарь называется юлианским. В России он существовал до февраля 1918 года. По юлианскому календарю средняя длина года равна 365
суток = 365 суток 6 часов.Как видно, средняя длина юлианского года больше истинной на 11 минут 14 секунд.
Юлианский календарь был улучшен папой Григорием Х111. В 1582 году он произвёл следующую реформу календаря. Сохранил чередование простых и високосных лет, но добавил правило: если номер года оканчивается двумя нулями, а число сотен не делится на 4, то этот год простой, но 1600 - високосный. Кроме того, считая. Что от начала летосчисления (от «рождества Христова») уже накопилась ошибка в 10 дней, Григорий Х111 сразу прибавил 10 дней. С тех пор накопилось ещё 3 дня (в 1700,1800, 1900 годах). Поэтому в настоящее время расхождение между юлианским и новым (григорианским) составляет 13 дней.
Какова средняя длина григорианского года? Из 400 лет по юлианскому календарю – 100 високосных. А по григорианскому – 97. Поэтому средняя длина григорианского года = 365
суток = 365,242500 суток = 365 суток 5 часов 49 минут 12 секунд, т.е. она больше истинной на 26 секунд.Как видим, весьма простыми средствами достигнута очень большая точность. Как получили этот результат?
Сначала подумаем, как мы сами решили бы проблему чередования високосных лет. Мы представили бы длину года в виде цепной дроби
1год=365 суток 5 часов 48 минут 46 секунд = [365; 4, 7, 1, 3, 5, 64] суток.
Примечание 1. π – иррациональное число. Оно выражается бесконечной цепной дробью. Величина года – эмпирическая. Всякая эмпирическая величина измеряется лишь с определённой точностью, и говорить об её рациональности или иррациональности не имеет смысла. Приведённая выше величина года - принятая, и мы должны считать её точной. Она выражается конечной цепной дробью.
Примечание 2. Чтобы выразить длину года в виде цепной дроби, незачем выражать её десятичной дробью в долях суток (аналогично тому, как мы делали с числом π). Это вычисление производится так (целая часть отброшена):
Находим несколько первых подходящих дробей. Целую часть опустим, так как наличие в каждом году 365 целых суток не требует напоминаний:
Каждый столбец дает решение проблемы календаря. Например, первый столбец дает для длины года приближенное значение 365
суток. Чтобы реализовать такую длину года, надо считать високосным 1 год из 4. Вообще, третья строка дает величину цикла или периода, а вторая – число високосных лет в цикле. Например, второй столбец соответствует такому решению: 7 високосных лет из каждых 29. Средняя длина года при этом получится 365 
суток. Это точнее, чем 365 , но зато сложнее.Прежде чем, приступить к анализу алгоритма Евклида рассмотрим числа Фибоначчи.
Суть последовательности Фибоначчи в том, что начиная с 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 шагов.
Неформально, евклидово кольцо — в абстрактной алгебре — кольцо, в котором «работает» алгоритм Евклида.
· Кольцо целых чисел Z. Пример евклидовой функции — абсолютное значение
.· Кольцо целых гауссовых чисел Z[i] (где i — мнимая единица, i2 = − 1) с нормой d(a + ib) = a2 + b2 — евклидово.
· Произвольное поле K является евклидовым кольцом с нормой, равной 1 для всех элементов, кроме 0.
· Кольцо многочленов в одной переменной K[x] над полем K. Пример евклидовой функции — степень deg.
· Кольцо формальных степенных рядов K[[x]] над полем K является евклидовым кольцом. Норма степенного ряда — номер первого ненулевого коэффициента в нём (для нулевого ряда норма равна минус бесконечности).
· Евклидовыми являются кольца конечных двоичных и конечных десятичных дробей, так как они являются кольцами частных кольца целых чисел Z.
· Евклидовыми являются кольца рациональных функций над полем C с фиксированными полюсами, так как такие кольца являются кольцами частных кольца многочленов C[x].
Мною были построены аналоги чисел Фибоначчи в кольце многочленов и исследованы некоторые их свойства. Для этих целей я использовала программу Mathematica 5.1.
Определение аналогов чисел Фибоначчи:
; 
; 
Первые 10 многочленов:
1.
2.
3.
4.
