Вход в аккаунт

Вы здесь

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

Содержание

Введение

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

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

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

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

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

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

Заключение

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

Одним из древнейших математических алгоритмов является алгоритм Евклида для нахождения наибольшего общего делителя двух положительных чисел. Вот его простейший вид. Пусть заданы два целых числа. Если они равны, то их наибольшим делителем будет каждое из них. В этом случае процесс заканчивается на первом шаге. Если они не равны, то вычитаем из большего числа меньшее. Это шаг алгоритма. Теперь рассмотрим вычитаемое и разность. Проделаем с ними ту же самую процедуру. Этот процесс будет продолжаться до тех пор, пока вычитаемое и разность не станут равны. Поскольку большее число в парах на каждом шаге уменьшается, но всегда не меньше единицы, то такой процесс не может продолжаться бесконечно, а закончится через несколько шагов.

Загрузить весь реферат (RTF)

Рейтинг@Mail.ru Индекс цитирования