БизенцТорра

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

№ 15

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

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

Предисловие

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

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

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

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

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

Глава 1

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

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

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

Происхождение систем счисления

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

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

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

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