Глава 1
Взлет алгоритмических рекомендаций
Алгоритм как термин просто описывает некое уравнение: любую формулу или набор правил, которые выдают желаемый результат. Самые ранние примеры восходят еще к древнему Вавилону, располагавшемуся на территории современного Ирака. На клинописных табличках, датируемых 1800–1600 годами до н. э., записаны алгоритмы для таких целей, как вычисление длины и ширины резервуара, если известны его глубина и объем вынутого грунта. По словам математика Дональда Кнута, вавилоняне “представляли каждую формулу в виде пошагового списка правил, то есть в виде алгоритма вычислений по этой формуле”. У них была специальная система записи вычислений, использующая, как пишет Кнут, “не символический язык, а представление формул на «машинном языке»”. Письменное объяснение каждого вавилонского алгоритма заканчивалось одной и той же фразой: “Таков способ”. Эта фраза подчеркивает неотъемлемое свойство алгоритмов: их можно повторять, они одинаково применимы и эффективны каждый раз, когда возникает определенная ситуация. Современный последователь Кремниевой долины назвал бы их адаптируемыми.
Алгоритмы занимают важное место в истории математики. Около 300 года до н. э. греческий философ Евклид описал в своем труде “Начала” так называемый алгоритм Евклида[9] – способ нахождения наибольшего общего делителя двух чисел. И его, и “решето Эратосфена” – алгоритм III века до н. э., который находит все простые числа, не превосходящие определенного числа, – используют до сих пор, особенно в области криптографии. Однако само слово “алгоритм” происходит от имени определенного человека – или, по крайней мере, от места его рождения.
Персидский ученый Мухаммад ибн Муса аль-Хорезми родился около 780 года в Хорезме – государстве, располагавшемся на территории современных Туркменистана и Узбекистана. О его жизни мало что известно. Он добрался до Багдада, который стал интеллектуальным центром региона после того, как мусульманский халифат Аббасидов завоевал Персию в VII веке. Там ученый занимался астрологией, географией и математикой в Доме мудрости, известном также как Большая библиотека Багдада. Подобно своей предшественнице – египетской Александрийской библиотеке – Дом мудрости являлся междисциплинарным научным центром, где ценили исследования и переводили на арабский язык тексты, написанные на латыни, санскрите, греческом и персидском языках. Около 820 года аль-Хорезми завершил работу “Книга об индийском счете”, которая в конечном итоге привела к распространению в Европе современной системы записи чисел. Он также сочинил трактат о методах решения уравнений “Китаб аль-джебр ва-ль-мукабала” (“Краткая книга о восполнении и противопоставлении”). От слова “аль-джебр” из названия (которое означает “восстановление, восполнение”, то есть сокращение одинаковых членов в обеих частях уравнения) произошло слово “алгебра”. В труде аль-Хорезми описывались методы решения квадратных уравнений и вычисления площади и объема, указывались приближенные значения числа π.
В середине XII века в Испании пересекались мусульманская, иудейская и христианская культуры – иногда мирно, иногда не очень, и между цивилизациями шел обмен идеями. Живший тогда в испанском городе Сеговия английский востоковед Роберт Честерский в 1145 году перевел “Книгу о восполнении и противопоставлении” на латынь. “Аль-джебр” превратилось в algeber, а “аль-Хорезми” – в Algoritmi. В то время слово algorismus относилось ко всем математическим операциям с использованием индийско-арабских цифр, а тех, кто занимался подобным искусством, называли алгористами. (Этим термином именуют себя визуальные художники, с 1960-х годов использующие алгоритмические процессы, однако он кажется подходящим для всех, кто работает над современной версией алгоритмов.) Такой длинный путь этимологии алгоритма показывает, что вычисления являются не только продуктом воспроизводимых научных законов, но и результатом человеческого искусства и труда.
Работа компьютеров основана на многократно выполняемых операциях. Затем с результатами, закодированными нулями и единицами, производятся новые операции, результат которых выдается пользователю. В 1822 году британский изобретатель Чарльз Бэббидж изложил свою концепцию “применения машин для вычисления астрономических и математических таблиц” – метод автоматизации вычисления с помощью системы пронумерованных шестерней и валиков, названной разностной машиной. Это устройство так и не было построено целиком, однако его более поздние реализации выглядят как внутренности фортепиано, только вместо молоточков тянутся длинные ряды колес. Спроектированная Бэббиджем машина должна была иметь высоту восемь футов и весить четыре тонны. Затем изобретателю в голову пришла идея аналитической машины, которая могла (если бы ее удалось построить) получать команды, заданные с помощью перфокарт, и выполнять простые операции программирования (циклы и условные операторы). Она стала основой для гораздо более сложных современных вычислительных машин. Сын Бэббиджа Генри в 1888 году писал: “Это всего лишь вопрос карт и времени”.