У День програміста. Хто придумав алгоритм?

Нещодавно я подумав, що в очах юних громадян двадцять першого століття, з дитинства звикли до комп'ютера, я - мамонт якийсь, який жив у доісторичні часи. Мені довелося працювати ще на обчислювальних агрегатах, які займали кілька кімнат. Підручники, за якими мені довелося вчитися, поминали давньоримський абак і Аль-Хорезмі (786 - 850).

Втім, і зараз ми ні-ні та й пом'янемо великого цього вченого, до місця і не до місця вставляючи в свою промову слово «алгоритм». Тому що сталося це слово з латинської написання (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 # 231-ois Vi # 232-te) (1540 - 1603).

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