Файл: Садовников, В. И. Потоки информации в системах управления.pdf

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

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

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

ременных.

Так, в массиве СК, приведенном выше в качестве при­ мера, частично совпадают аргументы функций 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

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

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

10. Аргументы, отмеченные во всех наборах знака­ ми [ ] и/или ( ), удаляют, а из неотмеченных аргумен­ тов формируют новый массив.. Новые наборы распола­ гают сверху вниз в порядке убывания числа аргументов в наборе. Если нижний набор нового массива содержит один аргумент, то выполняют п. 1—7, 10. Если этот набор содержит несколько аргументов, то — п. 7—10. Процедура выделения устойчивых сочетаний считается законченной, если в результате выполнения п. 10 набор неотмеченных аргументов пуст.

11. Если нижний набор исходного массива аргумен­ тов содержит несколько аргументов, тогда выполняют­ ся п. 8—10.

( 201) , ( 222)

(201), (223) (201), (227) (206), (221) (206), (222) (206), (223) (206), (227) (215)

( 221)

(222)

(223)

(227)

127