Наш высокочтимый г. Л. Эйлер делает нам в назидание следующее заявление. Он откровенно признает;

III. что, являясь королем математиков, он все же вечно будет краснеть за вызов здравому смыслу и повседневному опыту, брошенный выводом из его формулы, согласно которой тело под действием силы притяжения к центру сферы внезапно изменит направление движения к центру;

IV. что он сделает все возможное, чтобы больше не изменять разуму, доверяясь ошибочной формуле. Он на коленях молит прощения за то, что как-то, имея в виду парадоксальный результат, он заявил: Вычислениям следует доверять больше, чем чувствам, даже если кажется, что это противоречит действительности ;

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

Вольтер, Памфлет доктора Акакия, ноябрь 1752 г.

ФУНДАМЕНТАЛЬНЫЕ СТРУКТУРЫ ДАННЫХ

1.1. ВВЕДЕНИЕ

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

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

В качестве примера можно рассмотреть персональный файл служащего. Каждый служащий представлен (абстрагирован) в этом файле множеством данных, существенных либо для его характеристики, либо для процедур расчета. Это множество может включать некоторую идентификацию служащего, например его имя и заработную плату. Но вряд ли оно будет содержать такие несущественные данные, как цвет волос, вес и рост.

При решении какой-либо задачи как с помощью ЭВМ, так и без нее нужно выбрать некоторую абстракцию действительности, т. е. определить множество данных, описывающих реальную ситуацию. Этот выбор зависит от задачи, которую нужно решить. Затем следует выбрать способ представления этой информации. Здесь выбор определяется инструментами, применяемыми для решения задачи, т. е. средствами, которые предоставляет вычислительная машина. В большинстве случаев эти два этапа взаимозависимы.

Выбор представления данных часто бывает затруднителен, он не определяется однозначно имеющимися средствами. Его

Lt. Введение 15

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

Известно, что вычислительные машины используют внутреннее представление данных, основанное на двоичных цифрах (разрядах). Для человека такое представление неудобно из-за большого количества цифр в числе, но оно является наиболее подходящим для электронных схем, поскольку два значения (О и 1) можно удобно и надежно кодировать наличием или отсутствием электрического тока, электрического заряда или магнитного поля.

Из приведенного примера видно, что при решении вопроса о представлении данных обычно имеется несколько уровней детализации. Пусть, например, нужно изобразить положение объекта в пространстве. На первом этапе берется пара вещественных чисел, например декартовы или полярные координаты. На втором этапе они представляются как числа с плавающей запятой: каждому вещественному числу х ставится в соответствие пара целых чисел, обозначающих мантиссу f и порядок е (например, x - f-2). На третьем этапе, когда учитывается, что данные должны располагаться в памяти ЭВМ, мы получаем двоичное позиционное представление целых чисел, и на последнем этапе двоичные числа могут представляться направлением магнитного поля в магнитном запоминающем устройстве. Ясно, что первый этап определяется в основном самой задачей, а последний тесно связан с используемым вычислительным устройством. Поэтому вряд ли следует требовать, чтобы программист сам определял способы представления чисел или даже характеристики запоминающего устройства. Эти решения низшего уровня можно предоставить разработчикам ЭВМ, так как они располагают наибольшей информацией о ее технологии, что позволяет им выбрать способ представления чисел, пригодный для всех .(Или почти всех) случаев.