Алгоритмы в математике

Всюду алгоритмы. Они окружают нас, переплетаются, проникают друг в друга, шага нельзя ступить, не наталкиваясь на них. Но как разительно отличаются «алгоритмические джунгли» от настоящих, в которых густые спутавшиеся растения стесняют нас, тесно держат в плену. Удивительным образом алгоритмы не связывают нас, а ведут самыми надежными путями к решению сложнейших проблем.

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

Но не всем известно, что крупнейшим достижением науки ХХ в. является теория алгоритмов – новая математическая дисциплина.
Теория электронных вычислительных машин, теория и практика программирования, а также и математика не могут обойтись без неё. Математическая логика и кибернетика предъявляют на неё свои права. Однако она является самостоятельной наукой, которая готова служить всем наукам, и иметь своё лицо, свой предмет.

Происхождение самого термина «АЛГОРИТМ» связано с математикой. Это слово происходит от Algorithmi – латинского написания имени Мухаммеда аль-Хорезми (787 – 850), выдающегося математика средневекового Востока. В своей книге "Об индийском счете" он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними столбиком. В дальнейшем АЛГОРИТМОМ стали называть точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата из исходных данных.

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

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

Но вернёмся к математике и рассмотрим некоторые общеизвестные алгоритмы:

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

Ещё в III в. до н. э. математик Евклид, известный автор дошедшего до нас теоретического трактата по математике «Начала», в геометрической форме изложил правило получения общего наибольшего делителя двух натуральных чисел.

Описание алгоритма нахождения НОД делением.

1. Большее число делим на меньшее.
2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
3. Если есть остаток, то большее число заменяем на остаток от деления.
4. Переходим к пункту 1.

Пример: Найти НОД для 30 и 18.
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)
12/6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6.

Описание алгоритма нахождения НОД вычитанием.

1. Из большего числа вычитаем меньшее.
2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
4. Переходим к пункту 1.

Пример: Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 – 6 = 0 Конец: НОД – это уменьшаемое или вычитаемое. НОД (30, 18) = 6.

Рассмотрим ещё один алгоритм.

Решето Эратосфена

Алгоритм получения простых чисел.
Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
1. Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
2. Пусть переменная p изначально равна двум — первому простому числу.
3. Зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …).
4. Найти первое незачёркнутое число в списке, большее чем p, и присвоить значению переменной p это число.
5. Повторять шаги 3 и 4, пока возможно.
Теперь все незачёркнутые числа в списке — это все простые числа от 2 до n.
На практике, алгоритм можно улучшить следующим образом. На шаге № 3 числа можно зачеркивать начиная сразу с числа p2, потому что все составные числа меньше него уже будут зачеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.

ВикипедиЯ

Можно посмотреть также:
Типы алгоритмов;
Алгоритмы, изучаемые в 5-6 классах