Понятие алгоритма
Алгоритм — точно определённая система понятных исполнителю предписаний.
Алгоритм Евклида по шагам
Задайте два натуральных числа и выполняйте шаги: остаток r = a mod b, затем a := b и b := r. Каждый шаг — отдельное действие по точному правилу; когда b станет равным 0, в a — наибольший общий делитель. Для любых допустимых чисел способ один и тот же.
В информатику понятие алгоритма пришло из математики. Термин «алгоритм» произошёл от имени математика IX в. Мухаммеда ибн Мусы аль-Хорезми, который сформулировал правила четырёх основных арифметических действий. Сначала алгоритмами называли именно эти правила, позже — любой способ вычислений, единый для некоторого класса исходных данных.
Пример 1.1. Алгоритм «Решето Эратосфена» позволяет получить простые числа, не превосходящие N.
| Шаг | Действие |
|---|---|
| 1 | Выписать подряд все натуральные числа от 2 до N. |
| 2 | Взять первое число 2 и зачеркнуть каждое второе число, начиная отсчёт со следующего за двойкой числа. |
| 3 | Взять первое незачёркнутое число, большее 2 (число 3), и зачеркнуть каждое третье число, начиная отсчёт от числа, стоящего после 3 (учитывая и ранее зачёркнутые числа). |
| 4 | Продолжать действия до тех пор, пока первое незачёркнутое число не окажется больше N. |
| 5 | Незачёркнутыми окажутся все простые числа, не превосходящие N, и только они. |
Приведённое определение не является определением в математическом смысле слова: в нём использованы другие неопределённые понятия — «система предписаний», «формальное выполнение» и др. Это описание понятия «алгоритм», раскрывающее его сущность. Уточнить его можно, указав общие свойства алгоритмов.