История компьютерных вычислений и возникновение компьютерной алгебры

С давних времен человек мечтал о машине, которая могла бы выполнять вычисления. Однако что значит вычислять! Когда компьютеры только появились, они, в основном, были предназначены для численных расчетов. Затем они начали применяться для решения задач управления. И хотя в этих приложениях численные расчеты играют весьма важную роль, всегда были ученые, которые понимали, что результаты вычислений могут интерпретироваться не только как числовые значения физических величин. Еще Лейбниц мечтал построить машину для "вычисления истины".

Впрочем, в самом понятии "научные вычисления" всегда была двусмысленность: прежде чем на сцене появился компьютер, вычисления представляли смесь численного счета с тем, что многие называют "алгебраическими вычислениями", т.е. с операциями над математическими формулами.

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

Жак Иноди

Жак Иноди — один из наиболее известных и самых популярных молниеносных вычислителей. Он родился в 1867 году в очень бедной семье, в Онорато {Пьемонт). Иноди был пастухом, около шести лет от роду его захватила страсть к цифрам. Охраняя свое стадо, он практиковался, работая с числами в голове, и в семь лет мог в уме умножать числа, получая пятизначные результаты. И при этом он не знал таблицу умножения! После смерти матери он оставил родные места и отправился бродяжничать с братом, демонстрируя ручную белку. Брат играл на шарманке, а Жак показывал белку и собирал деньги.

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

Вскоре Иноди начал выступать в кафе, где его представлял коммивояжер М. Домби, который стал его импресарио и повез в турне по провинции, а затем привез в Париж в возрасте 13 лет. Здесь он привлек внимание Камиля Фламмариона, который написал несколько статей о нем в различные научные журналы. Известный антрополог Поль Брока, обследовал его и в своем отчете отметил, что голова Жака Иноди была очень большая и неровная.

В 1892 году, когда ему было 24 года, он вернулся в Париж. К этому времени он уже научился читать и писать и его интеллект заметно развился. По свидетельству Альфреда Бине, он вел себя тихо и скромно, говорил мало и был собран. Его образование было не слишком обширным; и следовательно, число тем для разговоров было ограничено.

Его импресарио М. Торси представил Иноди Академии Наук, которая сформировала комитет по изучению счетчика. В этот комитет входили Дарбу, Пуанкаре, Тиссерант и Шарко; позже в него вошел и Альфред Бине. После многочисленных тестов комитет дал свое заключение. Оно было выражено в отчете Дарбу. По мнению известного математика, фантастические результаты, прежде всего, были обусловлены чудесной памятью. Иноди мог запоминать 400-значные числа. 22-значное число Иноди смог вспомнить через восемь дней, хотя его не предупреждали, что когда-либо попросят об этом. Дарбу отмечает очень важный, хотя и пропущенный большинством проверяющих следующий факт: все методы были изобретены самим вычислителем. Правила, открытые Иноди, отличались от принятых в Европе, хотя некоторые из них имели сходство с применяемыми в Индии.

Альфред Бине предложил Иноди представить число 13411 в виде суммы четырех квадратов. Через три минуты Иноди назвал ему четыре следующих числа:

115, квадрат которого равен 13225; 13, квадрат которого равен 169; 4, квадрат которого равен 16; 1, квадрат которого равен 1. Сумма всех четырех квадратов равна 13411.

Минутой позже счетчик нашел другое решение:

113, которое в квадрате дает 12 769; 25, которое в квадрате дает 625; 4, которое в квадрате дает 16; 1, которое в квадрате дает 1. Сумма четырех квадратов равна 13411.

Наконец, некоторое время спустя (точное время не было записано) Иноди нашел третье решение:

113, которое в квадрате дает 12769; 23, которое в квадрате дает 529; 8, которое в квадрате дает 64; 7, которое в квадрате дает 49. Сумма четырех квадратов равна 13411.

Иноди действительно вычислял с удивительной скоростью. Так, в 1924 году в Обществе Гражданских Инженеров был организован матч между счетчиком и вычислительной машиной (арифмометром) того времени. Иноди победил машину в сложении, вычитании, возведении в степень, извлечении корня и в большинстве умножений. Только в умножении пятизначных чисел машина опередила человека. Кроме того, подобно большинству молниеносных вычислителей, Иноди называл день недели, на который приходится та или иная дата, почти мгновенно, что машина не могла делать.

Психолог Альфред Бине отметил, что память Иноди была сильно специализирована. Хотя Иноди запоминал сотни чисел, он не мог повторить более пяти или шести букв, предъявленных в определенном порядке, например в порядке а, т, g, f, s, m, t, u. Он не мог запомнить две строчки стихов или прозы. С другой стороны, он мог поддерживать разговор и отвечать на вопросы остроумно и по существу, решая в то же время предложенные ему задачи.

Все знаменитые великие вычисления XIX века содержат большое количество манипуляций с формулами. Наиболее известным является, несомненно, расчет Леверье орбиты Нептуна, который был основан на возмущениях орбиты Урана и привел к открытию Нептуна. Наиболее впечатляющие вычисления с карандашом и бумагой выполнены также в области астрономии: Делоне потребовалось 10 лет для вычисления орбиты Луны и еще 10 лет для ее проверки (проверка выявила несколько ошибок в знаках и несколько "потерянных" двоек). Результат не является численным, поскольку он состоит, в основном, из формулы, которая сама по себе занимает 128 страниц 4-й главы его книги. Если бы Делоне мог установить систему Mathematica на Pentium 166, то все вычисления, без учета времени на набор формул, заняли бы около 10 минут!

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

Тем не менее, как уже упоминалось, численные расчеты не позволяют полностью исключить необходимость в алгебраических вычислениях. Ведь написание даже простейших программ требует вывода формул, на которых основан алгоритм. Кроме того, имея удобные формулы, вычисления можно выполнить существенно быстрее, чем без них. И это может играть решающую роль: едва ли кого-нибудь (кроме самих метеорологов) может интересовать 48-часовый прогноз погоды через две недели. Кроме того, во многих численных методах (например, сеточных²) при уменьшении шага объем вычислений возрастает экспоненциально (показателем является обычно размерность сетки).

Поэтому с усложнением решаемых задач роль алгебраических вычислений не только не уменьшилась, но и, наоборот, значительно возросла. Однако часто их приходится выполнять вручную, хотя первые эксперименты по их автоматизации были поставлены еще на машинах первого поколения (в 1953 году). Очень скоро выяснилось, что программное обеспечение алгебраических вычислений должно представлять собой полную систему, включающую метод представления нечисловых данных весьма специальной структуры (формул, уравнений и т.д.), язык, позволяющий манипулировать ими, и библиотеку функций для выполнения необходимых базовых алгебраических операций. Значительно раньше, еще в XIX столетии, Ж. Адамаром была осознана важность так называемых некорректно поставленных задач, для которых оказалось, что арифметика, реализованная традиционным способом, не обладает точностью, достаточной для реализации численных алгоритмов их решения. Поэтому уже в начале 60-х годов прошлого столетия велись интенсивные научные исследования алгоритмов выполнения арифметических операций над числами произвольной длины и произвольного диапазона (так называемая арифметика произвольной разрядности). Уже в середине 60-х годов появились малые ЭВМ, на которых арифметические операции были реализованы не традиционным аппаратным способом, а микропрограммно. В 1965 году в Киеве была создана одна из наиболее уникальных таких ЭВМ — МИР-1. Занимая совсем немного места (стол и тумбочка с пишущей машинкой) и обладая весьма скромной, даже по тем временам, памятью — всего 4 Кбайт, она обладала уникальными возможностями в проведении различных инженерных и научных расчетов. Так как эта машина практически полностью была спроектирована математиками, в ней отсутствовали дорогие технические решения. Зато она обладала входным языком высокого уровня (ассемблер отсутствовал, программа на входном языке высокого уровня интерпретировалась) и возможностью выполнения арифметических операций с произвольной (заданной в начале программы) разрядностью. Конечно, о миллионах цифр не приходилось даже и мечтать, так как программа и все данные должны были уместиться в памяти объемом 4 Кбайт. Чтобы скрыть недостаток финансирования (точнее, его следствие — малый объем памяти), по умолчанию разрядность равнялась 6 (десятичным разрядам). Однако многие задачи решались при разрядности 9, 10, 12, а то и. 18-20 разрядов. Отдельные задачи решались при разрядности 100. Простота входного языка и арифметика произвольной разрядности обеспечили необычно маленькой (по тем временам) и дешевой машине больший успех, чем был у флагмана советской вычислительной техники — БЭСМ-6. Вместе с тем попытки решить новые и все более сложные задачи обнаружили ее основной недостаток — отсутствие возможности выполнять аналитические выкладки. И уже через три года после появления МИР-1, в 1968 году была создана МИР-2, входной язык которой, хотя и являлся расширением входного языка машины МИР-1, имел недвусмысленное название — Аналитик. Это был первый, реализованный в СССР полноценный язык программирования с возможностью выполнять "алгебраические" вычисления. И долгое время, вплоть до появления его очередной версии, он был лучшим.

Успех "алгебраических" вычислений был весьма ощутим, и уже в первой половине 70-х годов прошлого столетия появилось несколько систем компьютерной алгебры; упомяну лишь CLAM (1972 г., машина CDC-6500, 20 000 слов, ориентирована на решение задач общей теории относительности), Reduce-2 (1973 г., машины CDC-6500, 65 000 слов, и IBM-360 (и ЕС-1040), 300 Кбайт, универсальная система), Авто-Аналитик (1973 г., машина БЭСМ-6, 30 000 слов, ориентирована на решение задач математической физики) и Аналитик-74 (машина МИР-3). Если не считать Reduce-2 и Аналитик-74, у которых появились новые версии (знаменитый Reduce-З и Аналитик-79), все они довольно быстро доказали свою практическую непригодность. Ни в одной из упомянутых систем, за исключением Аналитика, например, нельзя было взять интеграл. (Интегрирование само по себе, правда, было предусмотрено в Авто-Аналитике, но фактически интеграл брался только в самых тривиальных случаях.)

Успех (или провал) систем первой половины 70-х годов прошлого столетия обусловил появление новых систем во второй половине этого же десятилетия. Для решения задач квантовой теории поля, в 1977 году в США на ассемблере машины CDC-6500 был реализован специальный язык программирования SCHOONCHIP. Но даже дифференцирование и матричная алгебра в нем предусмотрены не были. Зато в том же 1977 году появилась знаменитая система MACSYMA, на долгие годы ставшая флагманом компьютерной алгебры.

В 80-х годах прошлого столетия вышло большое число новых систем (muMath, CoCoa, AlPi и др.). Тогда же успешно развивалась SCRATCHPAD-2 и активно пополнялись библиотеки Reduce. Одновременно MACSYMA переносилась на новые типы компьютеров и успешно завоевывала сердца и умы все более широких кругов пользователей. Однако уже в 1988 году появилась система Mathematica, почти сразу же (менее чем за год) занявшая ведущие позиции в области применений компьютерной алгебры...

В настоящее время есть множество таких систем, но широко используются, пожалуй, лишь Mathematica, Maple, MuPAD и Derive. Впрочем, в 90-е годы прошлого века широко использовалась также система Axiom, разработанная фирмой IBM. Все упомянутые выше системы, так же как и большинство неупомянутых, являются весьма дружественными по отношению к пользователю. Конечно же, их языки отличаются, количество доступных функций в библиотеках варьируется от нескольких сотен до тысяч, внутренние структуры и даже используемые алгоритмы значительно отличаются друг от друга, но все лидирующие системы имеют много общего.

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

Этот раздел информатики называется "Calcul formel" во французкой литературе и "Computer algebra" — в английской. В русской литературе используются термины "компьютерная алгебра", "символьные и алгебраические вычисления", "аналитические вычисления" и др.

Содержание

Содержание раздела