слов algiros [больной] и arithmas [число], другие не соглашались с таким толкованием и утверждали, что это слово происходит от "King Algor of Castile". Наконец историки математики обнаружй-ди истинное происхождение слова "algorism": оно берет начало от имени автора знаменитого персидского учебника по математике, Abu Abd Allah Muhammad ibn Musa al-Khwarizmi (Абу Абд Аллах Мухаммед ибн Муса аль-Хорезми) (ок. 825 г.), означающего буквально "Отец Абдуллы, Мухаммед, сын Мусы, уроженец Хорезма"*. Аральское море в Центральной Азии когда-то называлось озером Хорезм, и район Хорезма (Khwarizm) расположен в бассейне реки Амударьи южнее этого моря. Аль-Хорезми написал знаменитую книгу Kitab al-jabr w&l-muq&bala (Китаб аль-джебр валь-мукабала- "Книга о восстановлении и противопоставлении"). От названия этой книги, которая была посвящена решению линейных и квадратных уравнений, произошло еще одно слово-"алгебра". [О жизни и научной деятельности аль-Хорезми речь идет в работе Н. Zemanek, Lecture Notes in Computer Science 122 (1981), 1-81.]

Постепенно форма и значение слова algorism исказились; как объясняется в словаре Oxford English Dictionary, это слово "претерпело множество псевдоэтимологических искажений, включая последний вариант algorithm, где произошла путаница" с корнем слова греческого происхождения arithmetic. Этот переход от "algorism" к "algorithm" кажется вполне закономерным ввиду того, что происхождение рассматриваемого слова было полностью забыто. В старинном немецком математическом словаре VoUstandiges mathematisches Lexicon (Leipzig, 1747) дается следующее определение слова algorithmus: "Этот термин включает в себя понятие о четырех типах арифметических операций, а именно: о сложении, умножении, вычитании и делении". Латинское выражение algorithmus infinitesimalis в то время использовалось для определения "способов выполнения действий с бесконечно малыми величинами, открытых Лейбницем (Leibniz)".

К 1950 году слово "алгоритм" чаще всего ассоциировалось с алгоритмом Евклида, который представляет собой процесс нахождения наибольшего общего делителя двух чисел. Этот алгоритм приведен в книге Евклида (Euclid) Начала (книга 7, предложения 1 и 2). Думаю, имеет смысл привести здесь описание этого алгоритма.

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

El. [Нахождение остатка.] Разделим m на п, и пусть остаток от деления будет равен г (где О <г < п).

Е2. [Сравнение с нулем.] Если г = О, то выполнение алгоритма прекращается; п -

искомое значение. ЕЗ. [Замещение.] Присвоить тп п, п <- г и вернуться к шагу Е1.

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

Каждому рассматриваемому алгоритму присваивается идентифицирующая буква (в предыдущем примере использовалась буква Е), а шагам алгоритма-эта

* В русскоязычных источниках это историческое лицо обычно упоминается под именем "аль-Хорезми" . - Прим. перев.

же буква в сочетании с числом (Е1, Е2, ЕЗ). Главы книги подразделяются на пронумерованные разделы; внутри раздела алгоритмы обозначаются только буквами. Но когда на эти алгоритмы делаются ссылки из других разделов, то к букве присоединяется номер соответствующего раздела. Например, сейчас мы находимся в разделе 1.1; внутри этого раздела алгоритм Евклида называется "Алгоритм Е", но ссылаться на него в последующих разделах мы будем как на алгоритм 1.1Е.

Каждый шаг любого алгоритма, например Е1 в вышеприведенном алгоритме, начинается заключенной в квадратные скобки фразой, которая как можно более кратко выражает содержание данного шага. Обычно эта фраза отражается также в сопровождающей алгоритм блок-схеме, такой как на рис. 1, чтобы читатель мог легко представить себе описанный алгоритм.

Рис. 1. Блок-схема алгоритма Е.

За краткой фразой следует формулировка (выраженная с помощью слов и символов) действия, которое нужно выполнить, или решения, которое нужно принять. Могут присутствовать также заключенные в круглые скобки комментарии (например, второе предложение шага El). Комментарии играют роль пояснений к шагу; с их помощью часто указываются некоторые постоянные характеристики переменных или текущие цели данного этапа, В комментариях не определяются действия, которые являются составной частью алгоритма; они служат только для удобства читателя, чтобы по возможности помочь ему разобраться в алгоритме.

Стрелка "<-", используемая на шаге ЕЗ, обозначает важнейшую операцию за-мещения, которую иногда называют присвоением или подстановкой: запись т i- п указывает, что значение переменной т замещается текущим значением переменной п. В начале работы алгоритма Е m и п - это заданные первоначальные значения, но по окончании его работы эти переменные будут иметь, вообще говоря, совершенно другие значения. Стрелка используется для того, чтобы отличать операцию замещения от отношения равенства. Мы не будем говорить: "Установим m = п", а, вероятно, спросим: "Действительно ли m = п?". Знак " = " обозначает условие, которое можно проверить, а знак " " -действие, которое можно выполнить. Операция увеличение п на единицу обозначается через п п -Ь 1 (и читается так: "п замещается значением п + 1" или "п принимает значение п 4- 1"). Вообще говоря, запись "переменная <- формула" означает, что формула будет вычислена на основании текущих значений всех входящих в нее переменных, а полученный результат будет присвоен переменной, стоящей слева от стрелки (таким образом, вычисленный по формуле результат заменит собой предыдущее значение переменной слева). Лица, не имеющие достаточного опыта программирования, иногда говорят, что "п переходит в п + 1" и для обозначения операции yвeJшчeния ?г на единицу

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

Обратите внимание, что на шаге ЕЗ очень важен порядок действий. Действительно, записи "присвоить m п, п г" и "присвоить п г, т п"-это совсем не одно и то же. Из второй записи следует, что предыдущее значение п будет потеряно до того, как его смогут присвоить т. На самом деле эквивалентом второй записи будет "присвоить п - г, т г. Когда нескольким переменным присваивается одно и то же значение, в одном выражении можно использовать несколько стрелок. Так, напри.мер, операцию "п г, m г" можно записать как "п m г". Операцию взаимного обмена значениями двух переменных можно записать так: "Обмен m п". Ее можно записать и с помощью новой переменной t следующим образом: "Присвоить t i- т, т i- п, п f\

Выполнение алгоритма начинается с шага, имеющего наименьший номер (обычно это шаг 1). Затем последовательно выполняются следующие шаги, если нет каких-либо указаний, нарушающих естественный порядок выполнения. На шаге ЕЗ указание "Вернуться к шагу Е1" явным образом определяет порядок вычислений. На шаге Е2 действию предшествует условие "Если г = О" и если г 7 О, то оставшаяся часть предложения не применяется и нет указаний на выполнение в этом случае каких-либо действий. Конечно, мы могли бы добавить дополнительное предложение "Если г 7 О, то перейти к шагу ЕЗ", но это совершенно излишне.

Жирная вертикальная черточка " ", помещенная в конце шага ЕЗ, обозначает окончание алгоритма и продолжение текста.

Итак, мы обсудили практически все соглашения об обозначениях, которые используются в алгоритмах, приведенных в книге. Осталось выяснить только, как обозначать величины с индексами (или "подстрочными" индексами), которые являются элементами упорядоченного массива. Предположим, у нас есть п величин: vi,V2, ,Vn- Для обозначения j-ro элемента вместо записи Vj часто используется запись v[j]. Аналогично массив иногда предпочитают обозначать как a[i,j], вместо того чтобы использовать два подстрочных индекса, как в записи а-. Иногда для обозначения переменных используются имена, состоящие из нескольких букв, обычно прописных. Например; temp может быть именем переменной, использующейся для временного хранения вычисленного значения, а prime [к] может обозначать к-е простое число, и т. д.

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