книги из ГПНТБ / Зубов В.С. Математическое обеспечение цифровых вычислительных машин и систем учеб. пособие

-to -

Системно организованные комплексы программ, предназна­

ченные для обслуживания указанных выше секторов, принято

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

ных пользователем в процедурном виде. ПСП могут использо­

ваться как составные элементы открытых процедурных систем

программирования.

§ 2. Классификация средств общего математического обеспечения

Системная организация современного МО облегчает задачу

его классификации. Соответственно назначению СМО следует разделять на СМО технологических процессов реализации алго­

ритмов (СМО ТП), непосредственно предоставляемые пользова­ телю, и на СМО вычислительного процесса в ЭВМ (СМО ВП).

СМО ТП делятся на системы программирования (СП) и системы отладки и редактирования программ (СОТР). СМО ВП делятся на операционные системы (ОС) и системы функционального контро­ ля (СФК). Структура общего МО показана на рис. I .

Разделение, принятое в данной схеме, до некоторой сте­

пени условно. Так, некоторые средства СОТР, как правило,

-12-

РАЗДЕД I . СТРУКТУРЫ ДАННЫХ, СРЕДСТВА ИХ ОРГАНИЗАЦИИ И ИСПОЛЬЗОВАНИЯ В ЭВМ

ГЛАВА I . СТРУКТУШ ДАННЫХ

§ I . Упорядоченность мяожеотва объектов

Объектом будем называть реальность (предмет, личность,

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

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

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

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

ний объектов, либо получение информационных сущностей, ко­ торые могут рассматриваться как самостоятельные объекты. В

процессе решения обычно порождаются промежуточные информа­ ционные сущности, которые в дальнейшем именуются промежу­ точными данными. Детерминированный характер процессов в ЭВМ предполагает существование некоторой упорядоченности исход­ ных, промежуточных и окончательных данных, возможно отража­ ющей соответствующую упорядоченность объектов. Так, если в задаче из области математической физики объектами.рассмот­ рения . являются отдельные точки физического поля, то упоря­

доченность исходных данных, как правило, отражает геометри­

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

факультетов, то вероятна упорядоченность вводимых данных по факультетам. Так как для пользователя зачастую представля­

ет интерес лишь упорядоченность определённого им характера,

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

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

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

множествами и т . д . ), является существование взаимно однозна­ чного соответствия как элементов этого исходного множества,

так и элементов его подмножеств на любом из уровней иерархии

-/4-

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

дет составлен из частных номеров подмножеств более высоких уровней, в которые входит рассматриваемый элемент, и част­

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

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

ров, т . е . в определённой последовательности. Можно показать,

что и другие вида упорядоченности множества, например, дре­

весная упорядоченность [ l ] , могут быть сведены к линейной его упорядоченности.

Порядок следования объектов множества или может быть задан явно (например, последовательность букв латинского алфавита некогда была задана и теперь постоянна), или может быть получен с помощью бинарного, т . е . определённого для пар объектов множества отношения порядка ("внутреннее" от­ ношение для множества), или же может быть получен через отображение множества объектов на объекты другого, упорядо­ ченного множества ( “внешнее" отношение для множества). Со­ ответственно и реальные структуры данных, описывающих эти

объекты, могут быть образованы ещё до ввода данных в ЭВМ и 5

могут быть получены в ЭВМ по определённому правилу через использование отношения порядка или отображение ("правиль­ ные" структуры).

-/5 -

§2. Пршщиш построения последовательности объектов

В качестве отношения порядка при упорядочении может быть

использовано отношение, обладающее следующими свойствами:

1, Асимметричностью, если отношение выполняется для па­ ры объектов А и Б (будем говорить: "А в порядке к Б "), то оно не выполняется для пары объектов Б и А.

2, Транзитивностью, если А в порядке к Б, а Б в порядке

к В, то А в порядке к В.

Действительно, такое отношение даёт способ последовате­

льной выборки (нумерации) объектов множества: первым выби­ рается объект, отношение порядка для которого со всеми ос­ тальными объектами не выполняется ( существование такого объекта обусловлено свойством транзитивности отношения по­ рядка), вторым - объект, для которого выполнено отношение порядка лишь с выбранным объектом, и вообще, всякий раз вы­ бирается объект, для которого выполняется отношение порядка лишь с ранее выбранными объектами.

Распространим понятие правильной последовательности на тот случай, когда отношение порядка определено не для всех

пар объектов множества. Потребуем, чтобы для всех объектов,

из подмножества объектов, между которыми данное отношение

порядка не определено (отношение порядка может быть не един­ ственным) , отношение порядка с любым объектом, не входящим

в подмножество, либо одновременно выполнялось, либо одновре­ менно не выполнялось. Объект, для которого отношение поряд­ ка определено со всеми остальными объектами множества, мож­ но рассматривать как тривиальное подмножество указанного выше рода. Будем теперь рассматривать подмножества как структурные элементы исходного множества и распространим на

-16-

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

перед ним. Иначе говоря, в такой правильной последовательно­ сти пара объектов, для которой отношение порядка не опреде­ лено, может быть разделена лишь темя объектами, отношение

порядка которых с любым объектом данной пары также не опре­ делено.

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

например, объект неупорядоченного множества является соста­ вным и во всех объектах имеются составные части одинаковой значимости, причём одинаковые по значимости части разных объектов имеют взаимно однозначное соответствие с элемента­ ми упорядоченного множества объектов, то возможно получение упорядоченности первого множества, аналогичной упорядочен­ ности во множестве с иерархической структурой. Примером та­ кой упорядоченности является лексикографическая упорядочен­

ность множества слов в словаре, йюсмотрим принцип её получе­ ния.

4 7 -

-18-

ниыаемый характер упорядоченности множества объектов и дос­ тупа к отдельным его объектам (вне связи с "физической"

упорядоченностью описывающих их данных и средствами их хра­ нения и обработки). Рассмотрим их примеры.

Строкой именуется последовательность элементов, обычно отражающих информационные сущности, для которой характерны

привилегированные связи: наиболее значимы отношения элемен­ та строки с ближайшими по последовательности элементами,и

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

разбиение строки на части, поэлементное сравнение строк.

Массив - это множество элементов, расположенных таким образом, что упорядоченное множество целых чисел ( индексов)

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

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

-1 9 -

ру уравнений, их систем ), имеющих, зачастую, физическую сущ­

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

его положением, но положение элемента в массиве обычно пол­

ностью определяет его роль в вычислительном процессе. К та­

ким элементам можно применить лишь небольшое количество про­ стых операций: сравнение, арифметические операции. Иногда

помимо указанных фактографических сведений элемент массива содержит текстовый документ или набор документов, относя­

щихся к тому же объекту.

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

составу и размеру структуры данных, соответствующие строке.

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

элементам, расположенным внутри очереди или магазина, тре­ буется их "выталкивание" в начало или верхушку соответственна

Стеком назовём динамическую структуру, отличающуюся от магазина лишь тем, что в стеке доступ к любому элементу при чтении осуществляется как в векторе (одномерном массиве),

без выталкивания (но включение и исключение элементов допус­ кается лишь в верхушке).

Дерево мы будем определять как такую систему пересека­ ющихся последовательностей, что пересечением любых .рвух по­ следовательностей может быть только их начальный участок