Обчислювальні методи, засоби та реалізація локально-паралельної обробки нечіткої інформації

РАЗДЕЛ 2
АЛГЕБРА РЕГИСТРОВЫХ ПРЕДСТАВЛЕНИЙ

Для построения ЛП методов обработки нечёткой информации разработан формально-описательный аппарат, учитывающий принципы реализации и особенности функционирования ВС последовательного типа общего назначения (машина Фон Неймана [53]). Теоретическую основу аппарата составляет алгебра регистровых представлений [4, 6, 13, 24, 30], поддерживающая соответствующую структуру данных и набор операций над ними. Рассматриваемые в ней объекты - регистровые представления (РгП) - наделены алгебраической структурой двойственного числового характера. Иерархическая система ЛП методов обработки включает порождение составных методов на основе базовых. Даны определения и алгоритмические описания методов, исследованы их основные свойства, представлены численные примеры.

2.1. Регистровые представления
Для описания программной интерпретационной реконфигурации структуры регистровых ресурсов ПОН введены в рассмотрение объекты специального типа - РгП.
Исходными для последующего изложения считаются общие представления дискретной теории множеств [72] и алгебраические понятия. Термин алгебра употребляется в литературе по крайней мере в четырех значениях:
* как часть математики, изучающая алгебраические операции [73] (A0);
* как формализованная система (алгебраическая система (АС)) [74] (A1),
* как множество с определенной на нем системой алгебраических операций (универсальная алгебра) [75] (A2),
* как конкретный вариант универсальной алгебры - структура, наделенная операциями сложения и умножения (A3).
Соотношение между указанными понятиями можно изобразить в виде отношения включения: A0?A1?A2?A3. В самом деле. A0 есть объемлющее понятие, включающее изучение АС. Последние есть множества с определенными на них операциями и отношениями. АС называется объект A1: , состоящий из не пустого множества A, семейства алгебраических операций O и семейства отношений R, заданных на множестве A. Частные случаи: при R=?, О??, АС A1 есть универсальная алгебра A2, при R??, О=?, АС есть модель. Наконец, A3 является частным случаем A2, при O:{+,*}.
Применительно к РгП, термин алгебра используется нами далее для обозначения частного вида АС при R=?, О??, О - специальный набор операций, рассматриваемый далее (п.п. 2.2. - 2.5.); т.е. в смысле A2.
Определение 2.1. Пучок регистровых представлений (пучок РгП) есть объект R:, в котором:
An - упорядоченный набор из n двоичных позиций: An:{a1,a2,...,an},
n - разрядность пучка РгП - число двоичных позиций в упорядоченном наборе An,
M - полное разбиение набора An на связные непересекающиеся подмножества An:{An(s1), An(s2),...,An(sk)}.
An(s1), An(s2),...,An(sk) далее называются сегментами, а M - сегментной разметкой.
Сегментная разметка задается непосредственным перечислением разрядностей si подмножеств An(si); i?{1, 2,...,k}; k>2.
M:{s1, s2,...,sk}, ,(2.1)либо указанием правил или алгоритмов, согласно которым двоичные позиции ai, (i?1,2,...,n) упорядоченного набора An:{a1, a2,...,an} соотносятся с подмножествами An(si):
An(s1):{a1, a2,...,as1},
An(s2):{a(s1)+1, a(s1)+2,...,as2},
. . . . . . . . . . . . . . . . . . . . . .
An(sk):{a(s(k-1))+1, a(s(k-1))+2,...,an},(2.2)где сегмент An(si) имеет разрядность si, i?{1,2,...,k}.
Полнота сегментной разметки M обозначает, что =An, что определяется условием (2.1).
Связность сегментов (подмножеств An(s1), An(s2),...,An(sk)) обозначает, что в An(si):{a(si)+1, a(si)+2,..., as(i+1)} и An(sj):{a(sj)+1, a(sj)+2,..., as(j+1)}; i, j?{1,2,...,k}, при i((si)+1)<((si)+2)<...<(s(i+1))<((sj)+1)<((sj)+2)<...<(s(j+1)). Не пересекаемость сегментов определяется в теоретико-множественном смысле и обозначает, что An(si)?An(sj)=?; i?j; i, j?{1,2,...,k}. Таким образом, с учетом сегментной разметки M, упорядоченный набор An имеет вид:
R=(2.3)Отдельные сегменты s1, s2,..., sk выделены круглыми скобками. Размеченный указанным способом набор An содержит полную информацию о паре . Т.о., выражение (2.3) может рассматриваться как развернутая формальная запись пучка РгП R.
Определение 2.2. Регистровое представление есть объект RB:, в котором:
An и M - соответствующие параметры пучка РгП R,
B - целое не отрицательное число, B?(2n-1), которым задается заполнение двоичных позиций упорядоченного набора An: расстановка нулей и единиц в нем.
Таким образом, РгП RB может быть определено также через пучок РгП R, как RB:, где R:.
В позиционной записи число B, так же как и An, представляет собой упорядоченный набор позиций B:{b1, b2,..., bh}. Удобно считать, что разрядности B и An совпадают: h=n, B:{b1, b2,..., bn}. Для этого пусть в случае B<(2n-1) несколько старших разрядов B будут заполнены нулями. Тогда различие между An и B состоит лишь в том, что в An, все разряды заполнены нулями. Т.е. ai?0, в отличие от bi?{0,1}, i=1,2,...,n. Соответственно, различаются также сегменты пучка РгП An(sj):{a(sj)+1, a(sj)+2,..., as(j+1)} и заполнения сегментов РгП B(sj):{b(sj)+1, b(sj)+2,..., bs(j+1)}, j=1, 2,..., k.
Пучок РгП R определяет конфигурацию сегментной разметки конкретного экземпляра RB РгП: RB:. Этим задается следующая связь между произвольными РгП Ri, принадлежащими к общему пучку R.
Теорема 2.1. Пусть есть пучок РгП R:, и два принадлежащих ему РгП: RBp:, RBq:; RBp, RBq?R. Тогда необходимо и достаточно i-е элементы j-х сегментов RBp и RBq имеют одинаковые номера двоичных позиций в Bp и Bq.
В самом деле: RBp и RBq имеют единую сегментную разметку M. В ней, согласно принятой системе обозначений (2.3), i-й элемент j-го сегмента имеет номер j+i-1. Аналогично, если для каждого из РгП RBp и RBq i-й элемент j-го сегмента имеет номер j+i-1, то разметки РгП совпадают, следовательно они принадлежат к единому пучку R. ?
Рассмотрим примеры записи. РгП RB считается заданным, если