книги из ГПНТБ / Садовников, В. И. Потоки информации в системах управления

Приведенный способ получения эквивалентных фор­ мул вычисления значений СК используется на этапе фор­ мирования Генеральной спецификации структурных ком­ понент потока информации (§ 3-7).

и ) О б о б щ е н н а я с т р у к т у р а и н ф о р м а ц и о н н о г о м а с с и в а

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

Здесь рассматриваются три возможных способа орга­ низации информационного массива (массива CK): 1) в ви­

аргументов (zJt z2, ..., f n); 2) в виде вектор-функций, ко­

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

Скалярные функции

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

вя СК, записанные на ОИЯ. Отдельная CK (ja, г,, г2,...,г„)

содержит характеристику р. и набор признаков г. СК можно рассматривать как функцию, аргументами которой

служат признаки. Набораргументов"(г,, z2, ...,zn) каждой функции представляет собой вектор. Такая СК является

скалярной функцией' f(zt, z2, .../г„) вектора (z^, г2, ..., г„). Рассмотрим представление информационного масси­ ва, элементами которого являются скалярные функции,

в памяти системы.

Все элементы структурных компонент записываются

привязка к массивам, содержащим реализованные зна­ чения функций и аргументов, осуществляются с помощью системы управляющих слов. Управляющие слова делят­ ся на управляющие слова функций (УСФ 1) и управляю­ щие слова аргументов (УСА).

Структура УСФ 1, описывающего скалярную функ­ цию, показана в табл. 1-36.

р — признак УСФ 1, тождественно равный 0 (см. ниже УСФ 2);

f — номер функции (структурной компоненты) х; L — Логическая шкала, состоящая из 0 и 1;

118

â — базовый адрес массива реализованных значений компоненты х ;

b — базовый адрес таблицы косвенных адресов (ТКА) аргументов*

входящих в состав компоненты х ;

п — число реализаций компоненты х.

соответствующее ей УСФ 1 (соответствие определяется по части управляющего слова).

2. По логической шкале L найденного УСФ 1 опреде­ ляются коды аргументов этой функции. Число разрядов в L соответствует числу всех аргументов рассматривае­ мого массива структурных компонент. Между номерами разряда в L и кодами аргументов существует однознач­ ное соответствие. Если в некотором разряде L данного УСФ 1 стоит 1, то это означает, что функция зависит от соответствующего данному разряду L аргумента.

3. По части п УСФ 1 определяется общее число реа­ лизаций СК (количество значений).

Для того чтобы извлечь конкретное значение СК, используется базовый адрес а массива реализованных значений компоненты. Этот адрес — адрес расположения первого слова массива в ЗУ ЭВМ, т. е. пе_рвой реализа­ ции компоненты. Адрес /-й реализации данной компонен­ ты получается сложением базового адреса а с относи­ тельным адресом — числом (}—1).

4. Чтобы найти значения аргументов конкретной, на­ пример /-й, реализации СК, надо воспользоваться ТКА и УСА. Базовый адрес ТКА указан в части b УСФ 1. Это истинный адрес первого слова ТКА в ЗУ ЭВМ. ТКА — это прямоугольная таблица, число строк которой равно числу реализаций СК, а число столбцов — числу аргу­ ментов, от которых зависит эта компонента. Номера строк соответствуют номерам реализаций, а номера столбцов — порядковым номерам аргументов в СК (т. е. самый левый аргумент, найденный в L, является первым, а самый правый — последним). В клетках ТКА записы­ ваются косвенные адреса значений аргументов в масси­ вах значений аргументов.

Таким образом, чтобы найти значения аргументов, соответствующие /-й реализации СК, надо найти /-ю строку соответствующей ТКА. Это немедленно дает на­ бор косвенных адресов значений для всех аргументов.

119

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

Таким образом, по L находятся УСА, из них извлека­ ются базовые адреса, которые складываются с косвен­ ными адресами, извлеченными из ТКА. По этим истин­ ным адресам находятся значения аргументов.

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

Вектор-функции

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

Пусть, например, задан массив СК, наименования которых записаны в кодах ОИЯ:

Я= 013,222,207,211 = /2 (222,207,211 ); "Я = 014,222,207,211 = /3 (222,207,211);

Я, = 020,222,207,211 = /4 (222,207,211);

Я= 031,223,201,206 = /5 (223,201,206);

X, = 046,222,207,211 = ft (222,207,211);

я= 052,222,207,211=/, (222,207,211).

Вэтом массиве полностью совпадают векторы (222.

(222, 207, 211)] = [013, 014, 020, 045,052(222,207, 211)].

120

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

Вектор-функции с устойчивыми сочетаниями аргументов

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

ременных.

Так, в массиве СК, приведенном выше в качестве при­ мера, частично совпадают аргументы функций fі и f5. При этом образуется устойчивое сочетание аргументов (223.206) . Если это сочетание принять за новый аргу­ мент, то функция fi будет зависеть от одного аргумента (223.206) , а функция f5 — от двух аргументов (201) и (223.206) .

Для представления информации в виде вектор-функ­ ций с учетом устойчивых сочетаний аргументов, кроме уже описанных управляющих слов и ТКА, используется еще одна ТКА, в которой каждая строка соответствует набору косвенных адресов реализованных значений устойчивых сочетаний аргументов, в каждый столбец—■ аргументу, входящему в состав данного устойчивого со­ четания. Назовем эту таблицу таблицей косвенных адре­ сов устойчивых сочетаний (ТКАУС). В клетках ТКАУС записываются косвенные адреса значений аргументов данного устойчивого сочетания в массивах значений ар­ гументов. Порядковый номер каждой комбинации кос­ венных адресов ТКАУС может сам являться косвенным адресом для поиска набора выделенных значений устой­ чивых сочетаний аргументов. Этот новый косвенный адрес может быть обычным способом записан в ТКА вместо набора косвенных адресов аргументов, входящих в устойчивое сочетание. В этом случае столбцы ТКА со­ ответствуют новым аргументам, среди которых находят­ ся устойчивые сочетания старых аргументов. В клетках TKÄ записываются косвенные адреса значений аргумец-

122

тов, а также косвенные адреса косвенных адресов набо­

конкретного устойчивого сочетания, соответствующие, например, /-й реализации скалярной составляющей, на­ до найти j-ю строку ТКА. В этой строке расположен косвенный адрес набора косвенных адресов реализован­ ных значений аргументов данного устойчивого сочета­ ния. Этот косвенный адрес складывается с базовым адресом ТКАУС, и в результате определяется набор кос­ венных адресов значений аргументов данного устойчиво­ го сочетания. Затем эти косвенные адреса складываются с базовыми адресами соответствующих УСА и получа­ ются истинные адреса значений конкретных аргументов из данного устойчивого сочетания аргументов.

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

Пусть, например, в информационном массиве 10 век­ тор-функций содержат одно устойчивое сочетание двух аргументов (222,201) и различное число некоторых других аргументов. Рассмотрим случай, когда аргументы 222 и 201 не выделены в устойчивое сочетание (222, 201), а ис­ пользуются как самостоятельные аргументы. Пусть каж­

строк. Пусть каждый из аргументов, входящих в эти вектор-функции, принимает не более 64 различных зна­ чений. Тогда косвенный адрес любого значения аргумен­ та содержит в ТКА не более 6 двоичных разрядов. Кос­ венный адрес для пары аргументов 222 и 201 занимает 2X 6=12 разрядов на каждую реализацию вектор-функ­ ции. Тогда количество разрядов, отведенных в ТКА под аргументы 222 и 201 по всем реализациям десяти век­ тор-функций, составляет не более (12ХАХ 10) = 120Л/.

Теперь рассмотрим случай, когда аргументы 222 и 201 выделены в устойчивое сочетание (222, 201). Пусть аргу­ мент 222 принимает не более чем п2 различных значений,

123

рая состоит из двух столбцов и не более чем из tlyXth строк. Каждая строка ТКАУС содержит пару косвенных адресов значений каждого из аргументов 222 и 201, реа­ лизованных для какого-либо одного значения некоторой из рассмотренных вектор-функций. Если «іХ «2 меньше 212, то запись в ТКА одного косвенного адреса из ТКАУС вместо пары адресов в ТКА по каждому аргументу раз­ дельно может быть более экономной по сравнению с тем случаем, когда аргументы 222 и 201 не выделены в устой­ чивое сочетание (222, 201). Пусть, например, Пі— 5, а «2=7, тогда ТКАУС будет иметь не более чем 5X7 = 35 строк, а запись косвенного адреса любой комбинации из ТКАУС будет содержать не более 6 разрядов. В этом случае ТКАУС занимает не более (2 x 6 x 3 5 ) =420 раз­ рядов. Косвенный адрес пары значений из устойчивого сочетания по всем цеализациям скаляцных составляю­ щих всех рассматриваемых вектор-функций занимает в ТКА не более бхАХІО разрядов. Общее число разря­ дов (в ТКАУС и ТКА) для адресации значений выде­ ленного устойчивого сочетания аргументов не более чем

(2X6X35) + (6 X N X 10) =420 + 60А.

Таким образом, для случая, когда не выделены устой­ чивые сочетания аргументов, количество разрядов, за­ нятых ТКА, составляет не более чем (12Х А х 10) = 120А. Для случаев, когда выделены устойчивые сочетания аргументов, количество разрядов, занятых ТКАУС и ТКА, составляет не более чем (2X6X35) + ( 6 х А х 10) = = 420+60А. Как видно из примера, экономия памяти растет с ростом N.

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

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

1. В массиве наборов находят все наборы, состоящи из одного аргумента, и отмечают их во всех наборах массива знаком ( ).

124

2. Находят все наборы, состоящие из двух аргумен­ тов, один из которых отмечен знаком ( ). Второй аргу­ мент данного набора также отмечают знаком ( ) во всех наборах массива и т. д. до тех пор, пока во всем массиве не останется ни одного набора, содержащего группу отмеченных, и один неотмеченный аргумент.

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

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

4. В том наборе, в котором аргументы были отмече­ ны знаком [ ] или ( ), находят следующий неотмеченный никаким знаком аргумент. Если такой аргумент есть, то проверяют его наличие во всех остальных наборах. Если по крайней мере еще в одном наборе встречается такой аргумент, то во всех наборах его отмечают знаком [ ]. Если нет, то данный аргумент отмечают знаком ( ) и т. д., пока не будут рассмотрены все аргументы вы­ бранного набора.

5. Переходят к следующему набору, содержащему неотмеченные аргументы, и повторяют операции п. 3 и 4. Так просматривают и отмечают все наборы аргументов.

Если в массиве нет ни одного набора, содержащего аргументы, отмеченные знаком [ ], то устойчивые соче­ тания (промежуточные аргументы функции) не вводят,

иработу прекращают.

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

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

125

набора, то ой выбирается в качестве устойчивого соче­

Пусть этот набор содержит п аргументов. Последовательно удаляя из набора один, два и т. д.

аргумента формируют новые группы аргументов и про­ веряют наличие этих групп во всех остальных наборах массива.

Внутри набора сначала удаляют первый аргумент, а заканчивают работу удалением п-го аргумента. При этом поступают следующим образом. Удаляют /-й аргу­ мент данного набора (/=1, 2, ..., п) . Если оставшиеся аргументы образуют группу, которая встречается во всех остальных наборах или в некоторых наборах встречается, а в остальных не встречается ни один аргу­

аргумент и подсчитывают число наборов, в которых встречается группа, не содержащая (/+1)-й аргумент и т. д. до и-го аргумента. 'Затем последовательно уда­ ляют все возможные комбинации аргументов данного набора, состоящие из двух аргументов, из трех аргумен­ тов и т. д. Наконец, удаляют все возможные комбина­ ции, состоящие из (п—2) аргументов данного набора, и подсчитывают количество наборов, в которых найдена та или иная группа, полученная удалением некоторой комбинации аргументов.

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

126