Том 15. От абака к цифровой революции. Алгоритмы и вычисления - Бизенц Торра

БизенцТорра

«Мир математики»

№ 15

«От абака к цифровой революции.

Алгоритмы и вычисления»

Предисловие

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

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

Вычисления и технологии связаны между собой с древних времен. Вычислительные инструменты всегда были продуктом технологий и способов счисления, которые использовались в тех или иных культурах в тот или иной период. Древнеегипетские методы вычислений и римские устройства для счета, например абак, подчинялись правилам вычислений, которые были приняты в этих культурах. Это влияние было взаимным: римская система счисления сохранилась вплоть до Средних веков благодаря широкому применению абака. Аналогичным образом использование бумаги способствовало распространению арабских цифр. Венцом этой эволюции являются информатика и компьютеры, которые создавались с одной целью: разработать всё более и более мощные устройства для выполнения всё более и более сложных вычислений.

Число 71 прекрасно иллюстрирует эволюцию вычислений и их взаимосвязь с технологиями. Еще в Месопотамии и Древнем Египте предпринимались попытки вычислить 71 с помощью доступных в то время приспособлений. Были получены удивительные результаты: уже Архимед в III веке до н. э. рассчитал приближенное значение 71 с невероятно малой погрешностью в 0,002. С развитием информатики вычислялись всё новые и новые знаки 71: в настоящее время известно несколько триллионов знаков этого числа. Были созданы алгоритмы, позволяющие вычислить любой отдельный знак числа 71.

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

Глава 1

Начало эпохи вычислений. Позиционные системы счисления

Методы вычислений развивались на протяжении многих тысяч лет.

Этот процесс изначально проходил очень медленно, и ему предшествовало развитие систем счисления. Подобно многим другим проявлениям культуры, вычисления и системы счисления возникли в разных частях Земли. Изначально они не были связаны между собой, но затем широко распространились и оказали взаимное влияние друг на друга. Различные системы счисления были известны в Месопотамии, Древнем Египте, Древней Греции, Риме, Индии и других государствах. Им на смену пришли арабские цифры и позиционная система счисления, появление которой произвело переворот, сравнимый с тем, что произвела теория Коперника в астрономии.

Цифры и системы счисления появились в древности. У разных культур они различались, а где-то, например у амазонского народа пирахан, цифры отсутствовали вовсе.

Старейшие свидетельства использования чисел — кости с отметками, найденные на археологических раскопках. Древнейшая из подобных находок — кость бабуина, обнаруженная в горах Лебомбо африканского государства Свазиленд во время раскопок в 1973 году, возраст которой оценивается в 35 000 лет. На этой кости нанесено 29 отметок. Считается, что она использовалась для подсчета фаз луны; возможно также, что она применялась в качестве календаря менструального цикла. Эта кость напоминает палочки, которые и поныне в ходу у бушменов Намибии.

Другое примечательное свидетельство — волчья кость, найденная в 1937 году в Вестонице (Моравия). На эту кость нанесено 55 отметок, объединенных в пять групп по пять отметок. После отметки под номером 25 нанесена одна дополнительная. Эта кость является артефактом ориньякской культуры, а ее возраст — порядка 30000 лет. Поблизости от нее была найдена голова мраморной статуи Венеры.

Следующий выдающийся экземпляр — так называемая кость Ишанго, найденная в Конго в 1960 году, возраст которой оценивается не менее чем в 20000 лет.

Кость Ишанго, одно из древнейших доказательств использования чисел, хранится в Королевском институте естественных наук в Бельгии.

Существует две теории, описывающие происхождение чисел, которые также объясняют, какие числа появились первыми — количественные (один, два, три) или порядковые (первый, второй, третий). Согласно более популярной теории, числа возникли потому, что требовалось подсчитывать предметы, поэтому сначала появились количественные числа, а затем — порядковые.

Сторонники второй теории полагают, что числа возникли в ритуалах. В церемониях участники должны были располагаться в определенном порядке; поэтому сначала появились порядковые числа, а затем количественные. Последняя теория утверждает, что числа возникли в конкретном географическом регионе, откуда распространились по миру. В ней же целые числа делятся на четные и нечетные: нечетные считаются мужскими, четные — женскими. Эта классификация сегодня встречается во многих мировых культурах.

Использование десяти цифр и системы счисления по основанию 10 для представителей современной западной цивилизации кажется крайне логичным и естественным. Нам сложно представить, что эта система была известна не во всем мире.

Однако факты неоспоримы: например, исследования нескольких сотен племен американских индейцев показывают, что они использовали совершенно разные системы счисления, некоторые из которых применялись чаще других. Почти в трети племен была принята десятичная система, однако почти столько же индейцев использовали пятеричную систему (в некоторых случаях пятерично-десятичную). В оставшейся трети племен применялась преимущественно двоичная система (свыше 20 %), затем — двадцатеричная (10 %) и троичная (1 %).

* * *

ПИРАХАН

Эта история больше похожа на сюжет приключенческого романа. В 1970-е годы американский миссионер Дэн Эверетт, который сегодня является одним из ведущих лингвистов современности, прибывает в Амазонию, чтобы изучить удивительный язык племени пирахан и проповедовать туземцам христианство. После семи лет, проведенных с жителями племени, сам Зверей утратил веру. Племя пирахан в высшей степени удивительно: в языке племени, также известном под названием пираха, в отличие от всех известных современных языков отсутствует подчинительная связь. Кроме того, язык содержит всего десять фонем. У туземцев этого племени нет мифов и коллективной памяти. Они упоминают лишь о событиях, которые видели своими глазами они сами или кто-то из известных им людей, а также не представляют себе отдаленное будущее. Но самым удивительным результатом исследований Эверетта оказалось то, что в языке племени полностью отсутствуют числа и способы счета. Например, индейцы племени не различают единственное и множественное число и практически не проводят грань между исчисляемыми и неисчисляемыми предметами. Дэн Зверей рассказал о результатах своего исследования в книге Don't Sleep, There Are Snakes: Life and Language in the Amazonian Jungle, опубликованной в 2008 году.

* * *

С другой стороны, в поисках доказательств существования разных систем счисления совершенно не обязательно изучать далекие племена. В индоевропейских языках слово, означающее «восемь», происходит от слова, означающего «четыре», а латинское слово novem, означающее «девять», по-видимому, происходит от novus — «новый», что опять-таки указывает на использование систем счисления с основанием 4 и 8. Остатки двадцатеричной системы счисления прослеживаются в словах языка басков hogei, berrogei, hirurogei и laurogei, которые означают 20, 40, 60 и 80, в буквальном переводе — 20, 2·20, 3·20, 4·20, а также во французском слове «восемьдесят» — quatre-vingt. Аналогично в английском языке, где используется десятичная система счисления, можно заметить артефакты древности: eleven («одиннадцать») и twelve («двенадцать») происходят от one left — «остался один» и two left — «осталось два» (в том смысле, что они «остались» после 10).