Магистерская диссертация на тему: Анализ алгоритма Евклида в Евклидовых кольцах

Введение

Один из героев великого французского писателя Мольера, месье Журден, был страшно удивлён, узнав, что всю жизнь пользуется прозой. Мы с вами, тоже можем удивляться, узнав, что всю жизнь мы исполняем огромное число всякого рода алгоритмов.

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

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

Разве можно перечислить все задачи, при решении которых мы используем определённые алгоритмы?

Слово алгоритм стало широко употребляться в последнее время. Оно означает описание совокупности действий, составляющих некоторый процесс. Обычно здесь подразумевают процесс решения некоторой задачи, но и кулинарный рецепт, и инструкция по пользованию стиральной машиной, и описание процедуры проявления фотоплёнки, и ещё многие другие правила, не имеющие отношения к математике, являются алгоритмами.

Термин " алгоритм" произошёл от имени учёного VIII - IХ веков Аль-Хорезми. Его имя говорит, что родился он в городе Хорезми, который сейчас входит в состав Узбекистана. Большую часть своей жизни Аль-Хорезми провёл при дворе багдадских халифов. Из математических работ Аль-Хорезми до нас дошли всего две - алгебраическая и арифметическая. От названия первой книги родилось слово АЛГЕБРА.

Первые строки второй книги были переведены так: "Сказал Алгоритми. Воздадим хвалу Бог, нашему вождю и защитнику". Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово "алгоритм".

В своей работе я поставила цель исследовать известное в математике понятие "Алгоритм Евклида". В связи с этим были поставлены следующие задачи:

1. Изучить алгоритм Евклида.

2. Рассмотреть применение алгоритма Евклида для нахождения НОД чисел и многочленов.

3. Установить связь с числами Фибоначчи.

4. Найти аналоги чисел Фибоначчи в иных Евклидовых кольцах

Оглавление

- Введение

- Алгоритм Евклида

- Применение алгоритма Евклида

- Математическая проблема календаря

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

- Евклидовы кольца

- Аналоги чисел Фибоначчи Заключение

- Список использованных источников

Заключение

Данная работа посвящена расширенному алгоритму Евклида. Алгоритму Евклида более 2000 лет и он традиционно используется для нахождения наибольшего общего делителя натуральных чисел посредством остатков от деления.

Со временем алгоритм Евклида стали применять и в диафантовом анализе (для решения уравнений в целых числах), и в механизме цепных дробей (для наилучшего приближения действительных чисел рациональными), используется и для быстрого возведения в степень в компьютерных алгоритмах, и в криптографии.

Как было показано, числа Фибоначчи обладают экстремальным свойствам: при подстановке в алгоритм Евклида чисел Фибоначчи с номерами n и n1, алгоритм выполняется за n шагов.

В своей работе я нашла многочлены обладающие теми же свойствами. В дальнейшем я планирую исследовать свойства этих многочленов и построить степенные ряды, обладающие теми же свойствами.

Список литературы

1. С. Ленг, Алгебра, М., 1968

2. С. Коунтинхо, Введение в теорию чисел. Алгоритм RSA, - М. 2001

3. Н.М. Бескин, Замечательные дроби, -М.,1980 г.

4. А.И. Кострикин, Введение в алгебру, - М., 2000

5. Энциклопедия для детей Аванта + "математика" том 11 2002 г.

6. О. Зарисский, Коммутативная алгебра, т.1.,- М., 1963

7. Л.Я. Куликов, Алгебра и теория чисел - М.,1979 г.

8. А.Г. Цыпкин, Справочник по математике для средних учебных заведений, - 1984 г.

9. А.П. Савин, Я познаю мир. Сер. "Математика" / А.П. Савин, В.В. Станцо, А.Ю. Котова, - М. 2006 г.