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

Термин «алгоритм» произошел от имени ученого 18-19 веков Аль-Хорезми. Его имя говорит, что родился он в городе Хорезме, ко­торый сейчас входит в состав Узбекистана. Большую часть своей жизни Аль-Хорезми провел при дворе багдадских халифов. С его именем связывают создание в Багдаде «Дома мудрости» — багдадского хранилища рукопи­сей. Из математических работ Аль-Хорезми до нас дошли всего две — алгебраическая и арифметическая. Алгебраическая работа назы­вается «Альджебр уаль-мукабала», что озна­чает «Восстановление и противоположение». Восстановлением он назвал перенос отрица­тельных членов в другую часть уравнения, а противоположением — сокращение равных членов в разных частях уравнения. От назва­ния этой книги родилось слово алгебра.

Вторая книга, долгое время считавшаяся потерянной, была найдена в 1857 году в биб­лиотеке Кембриджского университета (Вели­кобритания). Точнее, был найден ее перевод на латинский язык. В этой книге даны четкие правила арифметических действий, практи­чески те же самые, что используются сейчас. Первые ее строки были переведены так: «Ска­зал Алгоритми. Воздадим хвалу Богу, наше­му вождю и защитнику». Так имя Аль-Хорезми перешло в Алгоритми, откуда и появилось слово «алгоритм». Его ввел в обиход немецкий математик Эрнст Шредер (1841-1902) для обозначения вычислительных процедур меха­нического характера.

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

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

Интуитивное представление об алгоритме как о системе предписаний для действий не могло удовлетворить математиков еще в про­шлом веке, не говоря уже о нынешнем, когда информатика прочно вошла во все сферы че­ловеческой деятельности.

В двадцатых годах нашего века задача точ­ного определения понятия алгоритма стала одной из центральных проблем математики. Дело в том, что тогда существовало две точки зрения на математические проблемы:

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

Есть проблемы, для решения которых вообще не может существовать алгоритма. Правы оказались сторонники второй точки зрения, но для того, чтобы ее обосновать, необ­ходимо было дать четкое определение алгорит­ма. Это было сделано трудами целой плеяды математиков. Любопытно, что важной вехой в этой работе было создание умозрительной машины, которая на бесконечной ленте могла лишь ставить и стирать точки и передвигать эту ленту влево и вправо, но при этом оказа­лось, что она может выполнять все логические операции. Ее назвали «машиной Тьюринга» по имени английского математика и инжене­ра Алана Тьюринга (1912-1954), описавшего ее в 1936 году.

Точное определение алгоритма дало воз­можность к настоящему времени доказать ал­горитмическую неразрешимость более десят­ка математических проблем.

Если алгоритм предназначен для выполне­ния на вычислительной машине, то его нуж­но записать на языке, понятном этой машине. Такая запись называется программой, а язык, на котором записана программа, называется языком программирования. Таких языков придумано довольно много: БЕЙСИК, ФОРТ­РАН, ПАСКАЛЬ, АДА, СИ. Каждый из них имеет свои достоинства и недостатки, а поэто­му и свою область применения — статистика, экономика, физика и т. д.