В День программиста. Кто придумал алгоритм?

Впрочем, и сейчас мы нет-нет да и помянем великого этого ученого, к месту и не к месту вставляя в свою речь слово «алгоритм». Потому что произошло это слово из латинского написания (alhorithm) арабского имени ученого: «аль-Хорезми», то есть «из Хорезма».

Благодаря тому, что Хорезм вместе со всем Узбекистаном в свое время входил в Советский Союз, аль-Хорезми считался более «нашим», чем другие ученые — его современники. Хотя судя по другому его имени, «аль-Маджуси» (из магов), происхождения он был, скорее всего, персидского, из рода зороастрийских жрецов, которых называли «магами». Впрочем, в те времена, графы «национальность» ни в каких документах не ставили, поскольку и понятия такого в заводе не было.

В Хиве сейчас и памятник стоит знаменитому земляку. Хотя большую часть своей жизни аль-Хорезми прожил вдали от Хорезма, в Багдаде. Багдад того времени был город молодой и динамичный. Его основали в 762 году как столицу новорожденного халифата. Несколько поколений халифов (среди них и знаменитый по «Тысяче и одной ночи» Гарун аль-Рашид) строили и украшали свою новую столицу. Сын Гаруна аль-Рашида, аль-Мамун, организовал в Багдаде «дом мудрости», нечто вроде академии. Очень скоро «дом мудрости» стал одним из главных средоточий учености в тогдашнем мире.

И не только учености мусульманской. В здешнюю библиотеку собирали труды античных, византийских, индийских, персидских ученых и философов и переводили их на арабский язык. Труд переводчиков оплачивался замечательно — золота за работу отвешивали столько же, сколько весил переведенный трактат. В библиотеке «дома мудрости» (а это была только одна из многих багдадских библиотек) переждали тяжелые времена труды многих древнегреческих философов, чтобы спустя столетия-лихолетия возвратиться в Европу и заложить основу европейской науки и философии.

Именно эту библиотеку при халифе аль-Мамуне возглавил аль-Хорезми. Однако был он не только библиотекарем и собирателем книг, но и ученым.

Подобно тому, как на багдадском рынке встречались товары из Индии, из Аравии и из Европы, так и в «доме мудрости» сходились учения и умения из всех окрестных стран. На багдадском базаре происходил обмен товаров. В багдадском «доме мудрости» происходил обмен знаниями. Но знания, в отличие от ковров или пряностей, обладают замечательным свойством: отдавая, ты их не теряешь.

Аль-Хорезми написал трактат по арифметике, который назывался «Об индийском счёте». Для того времени книга эта оказалась таким же «усилителем интеллекта», каким в двадцатом веке стал компьютер. Сложение и вычитание больших чисел перестало быть сокровенным знанием, за которое в университетах выдавали степень доктора. А произошло это всего-навсего из-за двух изобретений. Оба изобретения кажутся нам сейчас очевидными, что, впрочем, не умаляет их гениальности. Оба родились в Индии, но всему миру рассказал о них аль-Хорезми по-арабски.

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

Все достоинства позиционной системы становятся очевидными, если сравнить привычную нам десятеричную систему счисления с какой-нибудь непозиционной системой записи чисел. Например, с римской, в которой для записи чисел применяются буквы латинского алфавита. I=1, V=5, X=10, L=50, C=100, D=500, M=1000. Число записывается слева направо, сначала бо`льшие цифры, потом меньшие. Результирующее число получается сложением всех цифр. MDCLXVI=1000+500+100+50+10+1=1661. Запись IVXLCDM считается неправильной, потому что в ней цифры с меньшим значением предшествуют цифрам с бо`льшим значением. Если рядом стоят две или три одинаковые римские цифры I, C или M, они складываются. II=2, MMM=3000. Вместо написания подряд четырех одинаковых цифр I, X и C, эту цифру вычитают из цифр V, L и D соответственно. Для этого меняют порядок следования цифр и меньшую ставят слева от бо`льшей. IV=5−1=4. XL=50−10=40. Запись IC — неправильная, потому что из C вычитание не производится. Запись IL — тоже неправильная, потому что из L можно вычесть только соседнюю младшую цифру, X. Четыре одинаковые цифры римляне писали только в одном случае: IIII=4. Это делалось для того, чтобы не употреблять без надобности инициал верховного божества, Юпитера, IV.

Ну что, все понятно? Тогда небольшое упражнение. Какое событие произошло в MDCDLXI году?
В MDCDLXI=1000+500−100+500+50+10+1=1961 году произошло много событий, но главное, вероятно, полет человека в космос. Который вряд ли совершился бы, если бы баллистические расчеты производились в римской, непозиционной, и потому очень громоздкой системе счисления.

Ну, и второй вопрос. Какое самое большое число можно написать с помощью римских цифр?
Очевидно, MMMCMXCIX=3000+900+90+9=3999. Мы тут боимся, что в 2012 году произойдет конец света из-за того, что кончается календарь майя, а у древних римлян вся арифметика на 4000 заканчивалась — и ничего страшного!

Вторым великим изобретением, облегчившим человечеству счет, было создание знака, обозначающего отсутствие какого-либо числа. Индийцы называли этот знак «сунья» («пустота»). Аль-Хорезми перевел его на арабский словом «сифр», имеющим то же значение. От этого слова произошло слово «цифра». И слово «шифр» тоже. Мы называем эту цифру «нулем» от латинского слова «nullus» («никакой»).

Благодаря этим двум великим изобретениям стало возможным всего лишь с помощью десяти цифр единообразно записать как сколь угодно большое, так и сколь угодно малое число. Более того, теперь правила сложения и вычитания многозначных чисел упростились настолько, что стало возможным обучить им даже ребятишек. Все мы выучили эти правила еще в первом классе и запомнили их навсегда. Если вдруг под рукой не оказалось калькулятора, любой сможет произвести вычисления «на бумажке». Или уже не любой?

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

Другой трактат аль-Хорезми был посвящен решению линейных и квадратных уравнений. В этой книге (опять же в виде алгоритмов) был описан процесс решения задач, сводимых к линейным или квадратным уравнениям. Трактат назывался «Книга о восстановлении и противопоставлении», или по-арабски «Китаб аль-джебр валь-мукабала». От этого самого «аль-джебр» произошло слово «алгебра», как название науки о решении уравнений. Таким образом, книгу аль-Хорезми можно считать самым первым учебником алгебры, но без привычных нам формул. Формульную запись алгебраических алгоритмов ввел только французский математик Франсуа Виет (François Viète)(1540 — 1603).

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