О построении клонов алгебр функциональных n-отношенеий
Рассматриваются клоны алгебр n-отношений. Данные клоны включают алгебры, равномощные алгебре Кодда. Особое внимание уделено распространению результатов, полученных ранее по полугрупповым (грамматическим и алгоритмическим) клонам на по- строенные клоны алгебр функциональных n-отношений; эти клоны о...
Gespeichert in:
| Datum: | 2006 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут програмних систем НАН України
2006
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/1516 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | О построении клонов алгебр функциональных n-отношенеий / Л.М. Захария, Т.В. Луценко, Г.Е. Цейтлин // Проблеми програмування. — 2006. — N 2-3. — С. 25-34. — Бібліогр.: 31 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859595222855450624 |
|---|---|
| author | Захария, Л.М. Луценко, Т.В. Цейтлин, Г.Е. |
| author_facet | Захария, Л.М. Луценко, Т.В. Цейтлин, Г.Е. |
| citation_txt | О построении клонов алгебр функциональных n-отношенеий / Л.М. Захария, Т.В. Луценко, Г.Е. Цейтлин // Проблеми програмування. — 2006. — N 2-3. — С. 25-34. — Бібліогр.: 31 назв. — рос. |
| collection | DSpace DC |
| description | Рассматриваются клоны алгебр n-отношений. Данные клоны включают алгебры, равномощные алгебре Кодда. Особое внимание
уделено распространению результатов, полученных ранее по полугрупповым (грамматическим и алгоритмическим) клонам на по-
строенные клоны алгебр функциональных n-отношений; эти клоны определяются посредством соответствующих суперпозиций n-
отношений и связанных с ними функций, соответственно. Очерчены одномерные и многомерные вычислительные структуры и ас-
социированные с ними предметные области.
Clones of algebras of n-relations are examined. The given clones include algebras, equipotent to Codd algebra. High emphasis is placed on
distribution of the results received on semigroup (grammatical and algorithmic) clones to the clones of algebras of functional n-relations.
Both one-dimensional and multivariate computing structures and the subject domains associated with them are outlined.
|
| first_indexed | 2025-11-27T20:20:53Z |
| format | Article |
| fulltext |
Теоретичні і методологічні основи програмування
© И.В. Редько, 2006
ISSN 1727-4907. Проблеми програмування. 2006. № 2-3. Спеціальний випуск 25
УДК 519.3
О ПОСТРОЕНИИ КЛОНОВ АЛГЕБР ФУНКЦИОНАЛЬНЫХ
n-ОТНОШЕНИЙ
Л.М. Захария, Т.В. Луценко, Г.Е. Цейтлин
Институт программных систем НАН Украины, 03187, Киев, пр. Академика Глушкова, 40
tseytlin@vikno.relc.com
Рассматриваются клоны алгебр n-отношений. Данные клоны включают алгебры, равномощные алгебре Кодда. Особое внимание
уделено распространению результатов, полученных ранее по полугрупповым (грамматическим и алгоритмическим) клонам на по-
строенные клоны алгебр функциональных n-отношений; эти клоны определяются посредством соответствующих суперпозиций n-
отношений и связанных с ними функций, соответственно. Очерчены одномерные и многомерные вычислительные структуры и ас-
социированные с ними предметные области.
Clones of algebras of n-relations are examined. The given clones include algebras, equipotent to Codd algebra. High emphasis is placed on
distribution of the results received on semigroup (grammatical and algorithmic) clones to the clones of algebras of functional n-relations.
Both one-dimensional and multivariate computing structures and the subject domains associated with them are outlined.
Введение
Понятие клона относится к числу фундаментальных понятий универсальной и общей алгебры [1, 2]. На-
ряду с традиционным его использованием при функциональных построениях в многозначных логиках [3-5]
понятие клона приобретает теоретический и прикладной интерес для алгоритмических и полугрупповых по-
строений в алгоритмике [6, 7].
Под клоном понимается, обычно, одноосновная универсальная алгебра вида K=<A; SUPER>, где A – ос-
нова, представляющая собой множество однотипных функций; SUPER – сигнатура, состоящая из операции су-
перпозиции функций (подстановки одних функций вместо переменных в другие), а также операций отождеств-
ления и переименования переменных функции (более детально различные определения суперпозиции см. [3-5,
8, 9]).
Данная статья посвящена построению клонов алгебр функциональных n-отношений [8, 10, 11]. Следует
отметить важное значение алгебр n-отношений [10] в реляционных базах данных и знаний [12, 13]. Функцио-
нальные n-отношения весьма важны и при проектировании различных объектов, характерных для построений в
методологии и технологии современного программирования. Это, в частности, связано с ответами на вопросы
"что?" и "как?" Ответ на первый вопрос сопряжён с точной постановкой решаемой задачи и может быть форма-
лизован в терминах теории отношений; а второй – с построением функций для её решения [11]. Дальнейшее
развитие теории отношений имеет важное значение и для других перспективных разделов прикладного про-
граммирования [12, 13].
Материал статьи подчинён следующей структуре. В разд. 1 приведен ряд распространённых операций
над n-отношениями: композиция бинарных отношений; свёртка де Моргана; транспозиция, отождествление и
переименование столбцов и др.
Разд. 2 посвящён операции i-суперпозиции [8], которая является естественным обобщением на n-арный
случай композиции бинарных отношений. В частности, отмечается связь между i-суперпозицией и функцио-
нальностью. Функциональные построения однородных и неоднородных преобразований вычислительных
структур различной размерности приведены в разд. 3. Наконец, в заключении подведены итоги выполненного
исследования и приведены постановки некоторых задач, определяющих перспективы дальнейшего развития
работ по алгебре алгоритмики.
1. Операции над n-отношениями
Одной из распространённых операций теории бинарных отношений следует считать их композицию, со-
стоящую в последовательном выполнении бинарных отношений.
Пусть R и G – бинарные отношения, определённые на множестве M, 2, MGR ⊆ , где 2M – декартова
степень M. Под композицией R*G понимается новое бинарное отношение GRW *= , состоящее из пар вида
Wsa ∈),( тогда и только тогда, когда в M найдётся хотя бы один промежуточный элемент b такой, что па-
ра Rba ∈),( , а пара Gsb ∈),( . Таким образом, W суть последовательное вычисление R и G.
Бинарное отношение R – функционально, если с ним связана функция )(xf так, что для любой пары
Rba ∈),( выполняется baf =)( . При этом если R и G – функциональны и с ними связаны функции
Теоретичні і методологічні основи програмування
26
)(xf и )(yg , то с композицией GRW *= связана функция )(uw , которая служит суперпозицией функций
f и g , ))(()( xfgxw = . Иными словами, вычисление значения функции saw =)( состоит в вычислении
функции baf =)( , а затем функции sbg =)( , т.е. значение функции w состоит в последовательном вычис-
лении функции f , а затем g .
Аналогом композиции для n-арных отношений )2( ≥n служит свёртка де Моргана [10]. Под n-арным
отношением (кратко, n-отношением) nR понимается подмножество n-мерного декартова произведения,
n
n MMMR *...** 21⊆ . В частности, указанные множества могут быть равны nMMM === ...21 , тогда
подразумевается декартова степень M. Примерами n-отношения могут служить ведомости, часто используемые
в экономических задачах. Например, информация о сотруднике может быть описана следующим n -
отношением: 4321 *** MMMMV c ⊂ ,
где 1M – множество табельных номеров сотрудников;
2M – множество фамилий сотрудников;
3M – множество дневных тарифов сотрудников;
4M – множество, состоящее из возможных размеров социальных льгот по налогу на доходы физиче-
ских лиц,
а табель рабочих дней может быть представлен таким n-отношением: 51 * MMT c ⊂ , где 5M – множество
целых чисел из интервала [0, 23], фиксирующее количество отработанных сотрудником дней в месяце.
Пусть k
k MMMR *...** 21⊆ и c
c LLLG *...** 21⊆ суть n-арные отношения, определённые на
декартовых произведениях указанных множеств, где ∅≠1LM k I – непустое пересечение множеств kM и
1L . Свёртка де Моргана определяется следующим образом: результирующее )1( −+ ck -арное отношение
ckck GRW *1)( =−+ представляет собой совокупность кортежей вида
{ } и ),...,,,,...,,( :~ |~
12121
1)( LMbqqbaaazzW kcn
ck ∩∈= −
−+ ,
здесь b – промежуточный элемент такой, что k
n Rbaaa ∈− ),,...,,( 121 , c
n Gqqb ∈),...,,( 2 . Данная операция
формализует процесс связывания двух таблиц баз данных по значению поля b . Для нашего примера свертка де
Моргана определит новое отношение cc TVW *5 = , которое опишет структуру исходной информации при
решении задачи начисления заработной платы в виде следующей ведомости:
Табельный но-
мер
Фамилия сотрудника Дневной тариф Количество соци-
альных льгот
Количество отрабо-
танных дней
Положим, что n-отношение nR функционально по n-й компоненте, если с ним связана n-1-местная функция
),...,,( 121 −nxxxf , областью значений которой служит множество nM . Так, для любого 1−nv кортежа значе-
ний переменных данной функции она принимает значение в множестве nM , nn Mvf ∈− )( 1 . Иллюстрацией
функционального отношения служит отношение 65321
6 **** MMMMMR ⊂ , где 6M – множество на-
численной заработной платы каждого сотрудника, определяемое функцией
начисленоднейыхотработаннколичестводневнойwf начисление == тариф *)( , 5Ww ∈ .
Пусть n-отношения kR и cG – функциональны и с ними связаны функции ),...,,( 121 −kxxxf и функ-
ция ),...,,( 121 −cxxxg ; тогда в результате свёртки де Моргана получим также функциональное )1)(( −+ ck -
арное отношение ckck GRW *1)( =−+ , с которым связана следующая суперпозиция функций:
),...,),,...,,((),...,,( 1)(11211)(21 −++−−+ = ckkkck xxxxxfgxxxh . )1(
Проиллюстрируем сказанное на примере расчета налога на доходы физических лиц для каждого сотруд-
ника. Функция )(rg , где r 65321 **** MMMMM∈ , определяет элементы множества 7M значений на-
лога на доходы физических лиц (подоходный налог составляет 13%, размер социальной льготы, не облагаемой
налогом на доходы в 2005 году составил 131 грн, количество социальных льгот для каждого сотрудника опре-
Теоретичні і методологічні основи програмування
27
деляется его социальным статусом – количество детей, инвалидность и т.п.),
( ) доходынаналогльготсоциальныхколичествоначисленоrg =−= %13*131*)( .
В результате свертки де Моргана отношений 26 PR и ( 712 * MMP ⊂ ) по полю <табельный номер>
получим следующее n-отношение, которое для наглядности представим в виде таблицы базы данных
Табельный
номер
Фамилия
сотрудника
Дневной та-
риф
Количество
социальных
льгот
Количество
отработанных
дней
Начислено Налог на
доходы
которое определяется следующей суперпозицией функций:
h(x1,x2,…,x6)=gналог(fначислено(w), x1,x2,…,x5)
(в выражении произведены отождествление и перестановка столбцов, x1∈M
1, x2∈M
2, x3∈M
3, x4∈M
4,
x5∈M
5, x6∈ M
6). Данный пример иллюстрирует процесс решения задачи начисления заработной платы в ви-
де суперпозиции функций.
Таким образом, из проведенных построений вытекает справедливость следующего утверждения.
Теорема 1. Свёртка де Моргана ckck GRW *1)( =−+ функциональных n -отношений kR и cG порож-
дает новое функциональное отношение, связанное с суперпозицией h исходных функций f и g , которая за-
дана равенством (1).
Для n-отношений естественным образом вводятся операции перестановки, отождествления и переимено-
вания столбцов (по аналогии с введенными Мальцевым [5] одноименными операциями, которые применимы в
функциональных построениях [3, 4, 8]). Тем самым справедливо утверждение.
Следствие 1. Циклическая перестановка столбцов в сочетании со свёрткой де Моргана функциональных
n -отношений снова порождает функциональные n -отношения, согласно суперпозициям соответствующих
этим n-отношениям функций.
В [10] рассмотрены и другие операции над n -отношениями: проекция, фильтрация, теоретико-
множественные булевы операции и др., которые широко используются в алгебрах структур данных, например
алгебре Кодда [12].
Следствие 2. Теория n -отношений служит математическим фундаментом в прикладном программиро-
вании при построении реляционных баз данных и знаний [12,13].
Одной из основных проблем алгебры клонов является проблема функциональной полноты. Для алгебры
логики L/2 доказана теорема о функциональной полноте Поста и построена решетка максимальных подалгебр.
Между алгеброй логики L/2 и алгеброй отношений О/2, определенной на множестве пар, состоящих из нулей и
единиц, существует связь, которая позволяет сформулировать теорему о функциональной полноте для алгебры
О/2. Для алгебры логики L/2 естественно рассмотреть обобщённую свёртку де Моргана, как распространение
обычной суперпозиции функций на случай n-отношений, тогда из принадлежности функций, участвующих в
суперпозиции, к некоторому замкнутому классу следует, что и полученная в результате суперпозиции функция
также принадлежит тому же классу. Например, пусть все функции из суперпозиции сохраняют константу 0,
тогда соответствующие n-отношения содержат наборы, состоящие из нулей; этот факт имеет место и для отно-
шения, соответствующего функции h, полученной в результате суперпозиции.
Другой пример: пусть все функции if из суперпозиции самодвойственны, тогда и результирующая
функция h также самодвойственна, но отношения, соответствующие функциям if , содержат противоположные
наборы; этому свойству удовлетворяет и отношение, соответствующее функции h.
Пусть алгебре логики L/2 соответствует алгебра отношений О/2, сигнатура операций которой содержит
обобщённую свёртку де Моргана и унарные операции для отождествления и переименования переменных. То-
гда для алгебры отношений О/2 может быть сформулирована следующая теорема.
Теорема Поста для алгебры О/2.
Произвольно выбранная система отношений функционально полна в алгебре О/2 тогда и только тогда,
когда эта система содержит:
хотя бы одно отношение, не принадлежащее подалгебре О/0, сохраняющих константу 0;
хотя бы одно отношение, не принадлежащее подалгебре О/1, сохраняющих константу 1;
хотя бы одно отношение, не принадлежащее подалгебре О/c самодвойственных функций;
хотя бы одно отношение, не принадлежащее подалгебре О/m монотонных функций;
хотя бы одно отношение, не принадлежащее подалгебре О/л линейных функций.
Следствие 1. Каждой подалгебре алгебры логики L/2 соответствует подалгебра алгебры отношений О/2.
Следствие 2. Перечисленные в сформулированной теореме Поста для алгебры О/2 классы отношений
являются для алгебры О/2 максимальными и соответствуют максимальным подалгебрам алгебры L/2.
Следствие 3. Алгебра О/2 имеет счётное множество подалгебр, решётка которых соответствует диа-
грамме Поста для алгебры L/2.
Теоретичні і методологічні основи програмування
28
2. Операция i-суперпозиции n-арных отношений
Наряду со свёрткой де Моргана ещё одним важным обобщением композиции бинарных отношений слу-
жит операция i-суперпозиции n-отношений [8].
Пусть nR1 , nR2 ,..., n
iR 1− , n
iR , n
iR 1+ ,..., n
nR – последовательность n -арных отношений. Операция i-
суперпозиции iS порождает новое n-отношение nW такое, что nn
n
nni WRRRS =),...,,( 21 тогда и только то-
гда, когда для кортежа n
niii Waaaaaa ∈+− ),...,,,,...,,( 1121 существуют n-1 промежуточных элементов
nii bbbbb ,...,,,...,, 1121 +− таких, что
n
nii Raabaaa 111121 ),...,,,,...,,( ∈+− ,
n
nii Raabaaa 212121 ),...,,,,...,,( ∈+− ,
........................................................
n
iniii Raabaaa 111121 ),...,,,,...,,( −+−− ∈ ,
n
iniii Rbbabbb ∈+− ),...,,,,...,,( 1121 ,
n
iniii Raabaaa 111121 ),...,,,,...,,( +++− ∈ ,
........................................................
n
nnini Raabaaa ∈+− ),...,,,,...,,( 1121 .
Содержательно, как и в случае композиции бинарных отношений, промежуточные элементы
nii bbbbb ,...,,,...,, 1121 +− вычисляются по соответствующим n-отношениям nR1 , nR2 ,..., n
iR 1− , n
iR 1+ ,..., n
nR , в то
же время по n-отношению n
iR и указанным промежуточным элементам определяется элемент ia , который
представляет собой i -ю компоненту кортежа n
niii Waaaaaa ∈+− ,...,,,,...,, 1121 . При этом в случае, когда n-
отношения nR1 , nR2 ,..., n
nR – функциональны (например, когда i = n), промежуточные элементы 121 ,...,, −nbbb
представляют собой значения (n-1)-местных функций gy(x1,x2,…,xn-1) (где y=1, 2,…, n-1), ассоциированных с
функциональными n-отношениями nR1 , nR2 ,..., n
nR 1− ; элемент na суть значение функции ),...,,( 121 −nxxxf ,
соответствующей n-отношению n
nR , и такой, что ),...,,( 121 −= nn bbbfa так, что получена суперпозиция
)),...,,(),...,,...,,(),,...,,((
),...,,;...;,...,,;,...,,(
)1( )1(2 )1(1 )1(11)-(n 222212)1( 112111
)1( )1(2 )1(1 )1()1 ( 22221)1( 11211
−−−−−−
−−−−−−
=
=
nnnnnn
nnnnnn
xxxgxxxgxxxgf
xxxxxxxxxh
)2(
функций, ассоциированных с n-отношениями nR1 , nR2 ,..., n
nR 1− – аргументами n-суперпозиции S
n = W
n (где
i=n).
Таким образом, справедливо следующее утверждение.
Теорема 2. Операция i-суперпозиции nn
n
n
i
nni WRRRRS =),...,,...,,( 21 функциональных n-отношений
nR1 , nR2 ,..., n
nR порождает новое функциональное отношение nW , соответствующее суперпозиции h исход-
ных функций, которая задана равенством (2).
Следует отметить, что i-суперпозиции могут быть использованы в прикладном программировании при
построении реляционных баз данных и знаний [13].
3. Функциональные построения, связанные с однородными и неоднородными преобра-
зованиями на многомерных вычислительных средах
Данный раздел посвящён функциональным построениям, связанным с рядом преобразований многомер-
ных вычислительных структур [8, 14, 15]. При этом существенно используются модификации функциональных
суперпозиций, рассмотренных в разделах 1 и 2.
3.1. Свёртка де Моргана для нескольких n-арных отношений. Свёртка де Mоргана может быть использо-
вана применительно к m функциональным n-арным отношениям, где nm ≤ (см. разд. 1).
Отметим, что построение свёртки де Моргана осуществляется циклически с перестановкой столбцов
(теорема 1, следствие 1) и определяется как частичная операция посредством следующей суперпозиции функ-
ций:
Теоретичні і методологічні основи програмування
29
)).,...,,(),...,,...,,(),,...,,((
,...,,;...;,...,,;,...,,(
) 2 1 222212 112111
n 2 1 22221 11211
21
m21
mnmmmmnn
mmmnn
xxxgxxxgxxxgf
xxxxxxxxxH
=
=
(3)
Отметим, что наряду со свёрткой де Моргана операции перестановки столбцов, их отождествления, пе-
реименования и пр. индуцируют соответствующие операции над переменными функций, введенные для функ-
циональных построений в многозначных логиках [4], в частности двузначной алгебре логики, детально иссле-
дованной Постом, которая образует клон Поста (КП) [6, 7].
3.2. Суперпозиции функций в преобразованиях многомерных структур. Под многомерными одно-
родными вычислительными структурами, ориентированными на синхронные параллельные вычисления пони-
маются, в частности, одномерные (линейные) абстрактные регистры, односторонне или двусторонне бесконеч-
ные, а также их двухмерные (плоские) и многомерные обобщения [8].
Пусть R – двоичный линейный абстрактный регистр, двусторонне бесконечный. Периодически опреде-
лённое преобразование (далее ПО-преобразование) F регистра R задаётся булевой функцией
),...,,( 21 cxxxf , которая синхронно вычисляет новое состояние ,...),,(..., 11 +−= iii bbbB регистра R по его
текущему состоянию ,...),,(..., 11 +−= iii aaaA следующим образом:
),...,,( 11 −++= ciiii aaafb ,
где ib – новое значение ячейки ir регистра R в состоянии B , 11 ,...,, −++ ciii aaa – текущие значения ячеек
окрестности в состоянии A , от которых зависит состояние произвольно выбранной ячейки ir регистра R .
Пусть заданы ПО-преобразования F и G регистра R посредством булевых функций ),...,,( 21 cxxxf и
),...,,( 21 qxxxg соответственно. Композиция FGH *= ПО-преобразований регистра R порождает новое
ПО-преобразование H данного регистра, которое определяется следующей суперпозицией функций g и f :
)),...,,(),...,,...,,(),,...,,((),...,,( 1113221121 −+++−+ = qcccqqqc xxxgxxxgxxxgfxxxh . (4)
Операция композиции ПО-преобразований удовлетворяет свойству ассоциативности, тем самым сово-
купность ПО-преобразований на абстрактном регистре образует полугруппу [8]. Справедливы следующие ут-
верждения.
Лемма 1. Полугруппа ПО-преобразований на абстрактном линейном регистре R не имеет конечного ба-
зиса [15].
На множестве всех булевых функций введём сигнатуру операций, включающую бинарную суперпози-
цию [4], а также унарные операции над переменными, предложенные в [5]. Полученную таким образом алгебру
назовём модифицированным клоном Поста КП/м.
Лемма 2. Алгебра КП/м имеет конечный базис [9].
Проведенные построения допускают распространение на случай плоских регистров и вычислительных
структур большей размерности.
3.3. Неоднородные алгоритмические преобразования на вычислительных структурах, ориентиро-
ванных на мультиобработку. Понятие ПО-преобразования на абстрактном регистре носит однородный харак-
тер в том смысле, что его вычисление осуществляется на всём регистре посредством одной функции. Естест-
венным обобщением однородного ПО-преобразования служит его неоднородная трактовка, предназначенная
для существенного расширения сферы применимости ПО-преобразований на вычислительных структурах, ори-
ентированных на мультиобработку.
Неоднородное ПО-преобразование P вычислительной структуры S определяется посредством системы
функций >< ),...,,(),...,,...,,(),,...,,( 21212211 nnnn xxxfxxxfxxxf , которые заданы на окрестности
O={y1,y2,…,yn}, распределённой по структуре S так, что
),...,,(),...,,...,,( ),,...,,( 2121222111 nnnnn aaafbaaafbaaafb === , где a1,a2,…,an – текущее, b1,b2,…,bn
– новое состояния элементов окрестности S .
Проиллюстрируем сказанное на задачах символьной мультиобработки, к которым, в частности, относит-
ся сортировка массивов [16-18].
Пример 1. Рассмотрим одномерную кольцеобразную вычислительную структуру КВС, содержимым ко-
торой является в общем случае неупорядоченный числовой массив naaam ... : 210 , свёрнутый в кольцо. В
зависимости от длины n кольцо содержит разделители–маркеры $: при нечётном n такой маркер один, а при
Теоретичні і методологічні основи програмування
30
n чётном их два. Тем самым длина кольца КВС всегда чётна. Предполагается также, что $ больше любого чис-
ла непосредственно слева от него и меньше любого числа справа.
Кольцо КВС разделено на попарно непересекающиеся окрестности-пары: значение левого элемента каж-
дой пары ),( 1+ii aa определяется функцией ),min( 1+ii aa , тогда как её правый элемент – функцией
),max( 1+ii aa .
Зададим на КВС неоднородное ПО-преобразование TRANSP-s посредством системы функций <min,
max>, суть которого состоит в перестановке всех неупорядоченных пар по кольцу КВС. В случае упорядочен-
ности массива применение оператора TRANSP-s не изменяет содержимое кольца.
На КВС определён также оператор fP сдвига содержимого кольца на одну позицию по часовой стрел-
ке, в результате которого изменяется содержимое пар. Кроме того, на КВС зададим предикат Psort – истинный,
когда массив остаётся упорядоченным до и после очередного сдвига.
Алгоритм СИН_СОРТ синхронной сортировки массива на кольце КВС представим следующей цикличе-
ской параллельной регулярной схемой
SIN_SORT ::= {[Psort] TRANSP-s * fP }.
Алгоритм SIN_SORT состоит в циклической сортировке массива в результате синхронной перестановки
всех неупорядоченных пар посредством неоднородного ПО-преобразования TRANSP-s (определённого выше) с
последующим сдвигом fP . Проверка сортируемого массива на упорядоченность осуществляется посредст-
вом предиката Psort – истинного в случае неизменности массива при двух последовательных выполнениях тела
цикла.
Отметим, что приведенная регулярная схема является аналогом шаблона в объектно-ориентированных
средах. Она задает стратегию обработки (сортировки), которая применима к данным различных типов. Данная
схема может быть представлена в виде различных изобразительных средств – регулярных схем, САА-схем с
развернутым комментарием к каждому оператору и предикату, граф-схем, по которым с помощью инструмен-
тария производится автоматизированное диалоговое проектирование программного кода в объектно-
ориентированный язык программирования с использованием техники шаблонов.
Пример 2. Пусть дана линейная вычислительная структура ЛВС, ориентированная на ПО-
преобразование данных с переменной окрестностью. Содержимым структуры ЛВС служит числовой размечен-
ный массив 0M с указателями, фиксирующими пары элементов, подлежащих перестановкам. Следует отме-
тить, что в отличие от алгоритма SIN_SORT (см. пример 1) обработка осуществляется с переменным шагом-
окрестностью, определяющей доступ к обрабатываемым данным. Рассмотрим известный метод сортировки
массивов, принадлежащий Шеллу [16, 18]. Метод Шелла (МШ) весьма эффективный метод последовательной
сортировки. В отличие от класса алгоритмов сортировки, базирующихся на перестановках соседних элементов
(к данному классу относится и приведенный выше алгоритм SIN_SORT), в основу метода Шелла положена пе-
рестановка элементов, расположенных на расстоянии 0>k друг от друга [18]. Данный метод представим сле-
дующей РС:
МШ ::= ИНИЦ * {[p] РУ(k) * СОРТ (k) * УСТ (Н) } * ФИН, (5)
где ИНИЦ – оператор инициализации с выбором начального значения параметра k := m (в частности
k:=n, где n – длина массива);
p – предикат истинный в случае упорядоченности сортируемого массива;
РУ (k) ::= {[d( 21,YY ) =m] П( 1Y ) } – оператор рассредоточения указателей на расстояние в m элементов,
m = ||k/2|| – целая часть от деления;
Р( 1Y ) – сдвиг указателя 1Y на символ вправо;
СОРТ(k) – регулярная схема РС алгоритмов сортировки подмассивов
K a...a ...a a a Y Y H: nmki2kikii21 +++im (6)
(i = 1,2,...,k) (предполагается, что Н < ai < К для любого элемента ai сортируемого массива и при достижении
маркера К указатели далее не перемещаются);
УСТ (Н) – оператор установки 1Y и 2Y на маркер Н – начало массива.
Следует отметить, что РС СОРТ(k) может быть проинтерпретирована посредством подходящих алгорит-
мов, рассмотренных в [19-21].
Таким образом, в соответствии с МШ сортируемый массив представляет собой k подмассивов, допус-
кающих асинхронную мультиобработку различными алгоритмами сортировки. Каждый из таких алгоритмов
может быть сориентирован, например, на синхронную обработку своего подмассива, подобно алгоритму
SIN_SORT (см. пример 1).
3.4. Функциональные построения клонов n-арных отношений. Рассмотрим алгебру функциональ-
ных отношений, сигнатура которой включает бинарную операцию, подобную свёртке де Моргана (см. разд.1),
Теоретичні і методологічні основи програмування
31
которую назовём суженной свёрткой функциональных n-арных отношений. Пусть
q
q
c
c MMMMMMF *...**G и *...** 2121 ⊂⊂ суть функциональные n-арные отношения, определён-
ные на декартовых произведениях указанных множеств, где ,....2,1, =qc MM
Суженная свёртка определяется следующим образом: результирующее ((c+q)-1)-арное отношение
qcck GFH *1)( =−+ представляет собой совокупность кортежей элементов
{ } ...**Mz~ | ~
21 qcck MMzw ++ ∈= , здесь ),...,,,...,,(z~ 121 qccc aaaaa ++= , причём существуют c
промежуточных элементов cbbb ,...,, 21 таких, что
q
cqccc
q
q
q
q GbaaaGbaaaGbaaa ∈∈∈ −++− ),,...,,(, ... ,),,...,,( ,),,...,,( 1)(12321121 ,
для которых выполняется следующая суперпозиция n-арных отношений
( ) ( ) ,,...,,,...,,* )21
qqq
qc GGGFxxxGFH == + (7)
причём кортеж GFaaaaa qccc *),...,,,...,,( 121 ∈++ и суженная суперпозиция функциональных n-арных от-
ношений сопряжена с суперпозицией (4) функций, ассоциированных с n-отношениями F и G.
Отметим, что n-арное отношение GF * суть последовательное вычисление n-арных отношений qG , а
затем c-арного отношения F в соответствии с суперпозицией (7).
Рассмотрим, в частности, множества MASS всех неупорядоченных числовых массивов и MUM их отсор-
тированных образов так, что пара SORTMM ∈′),( , если MUMMMASSM ∈′∈ , и M ′ получен из M
в результате перестановки его элементов; тем самым бинарное отношение SORT функционально и служит по-
становкой задачи последовательной или параллельной сортировки в зависимости от выбора алгоритма и соот-
ветствующей вычислительной среды (см. 3.3, примеры 1, 2).
Пусть Z – система образующих (СО), состоящая из операций над n-отношениями, рассмотренных в [10]
и порождающая базовые конструкции алгебры Кодда [12, 13]. Замкнём Z по обобщению свёртки де Моргана
на n-местный случай (см. разд. 1, теорема 1, следствия).
Таким образом, из проведенных построений вытекает справедливость следующего утверждения.
Теорема 3.
а) суженная свёртка GF * функциональных n-арных отношений F и G порождает новое функцио-
нальное отношение согласно суперпозиции (4);
б) бинарное отношение SORT функционально и служит постановкой задачи на последовательную или
параллельную сортировку в зависимости от выбора алгоритма и соответствующей вычислительной среды (см.
разд. 3.3, примеры 1, 2);
в) для теории клонов и решёток их подалгебр, исследованных в [11, 22, 23], могут быть построены ассо-
циированные с ними клоны функциональных n-отношений, на которые распространяются соответствующие
теоремы о функциональной полноте;
г) замыкая рассмотренные в [9, 12, 13] системы образующих из n-отношений по приведенным в данной
статье вариантам их суперпозиций, построим клоны, порождающие семейства алгебр функциональных
n-отношений, адекватных по порождающей мощности системам образующих алгебр Кодда [12, 13].
3.5. Представленный в данной статье математический аппарат позволяет исследовать алгоритмическую
структуру знаний предметных областей и тем самым определять важные для данной предметной области алго-
ритмические зависимости, порождать новые алгоритмические знания, устанавливать взаимосвязи между близ-
кими предметными областями. В то же время он положен в основу инструментальных средств создания про-
граммных систем. Аппарат алгебры алгоритмики предлагает высокоуровневые средства проектирования алго-
ритмов и структур данных специалистам предметных областей, не владеющих в совершенстве техникой объ-
ектно-ориентированного программирования. Эти средства составляют основу восходящего от синтезатора
МУЛЬТИПРОЦЕССИСТ [24] интегрированного инструментария проектирования и синтеза алгоритмов и про-
грамм для погружения в объектно-ориентированные среды с подключением развитых в них инструментальных
средств [25-29]. Например, приведенная в статье схема сортировки массивов задает только алгоритмическую
стратегию обработки и взаимодействия операторов, предикатов с данными сортируемого массива через техни-
ку указателей, а по ней синтезируется шаблон класса реализации такого алгоритма сортировки. Таким образом,
дальнейшее развитие алгебры алгоритмики в плане построения клонов n-отношений и соответствующих ал-
гебр, ориентированных на формализацию и проектирование структур данных для различных предметных об-
ластей послужит мощным стимулом для дальнейшего развития исследований в теоретическом, системном и
прикладном программировании.
Сформулируем еще одну важную задачу, решение которой в плане построения и исследования алгорит-
мической структуры предметной области позволит синтезировать и сопровождать программные системы реше-
Теоретичні і методологічні основи програмування
32
ния экономических задач. Рассмотрим в качестве иллюстративного примера такого формализованного проек-
тирования с использованием клона n-отношений задачу первичного структурированного накопления информа-
ции в экономических задачах как результат осуществления хозяйственных или другого рода операций. Пред-
ложенную ниже модель будем называть учетной. Предполагается, что прикладной пользователь имеет возмож-
ность легко модифицировать эту модель с целью настройки ее для решения задач учета конкретной предметной
области (бухгалтерского, финансового, управленческого, статистического и других видов учета для объектов
различной природы). Основными элементами такой модели являются счета, аналитические объекты, журнал
регистрации операций, документы для регистрации операций, отчеты. Счета представляют собой некоторые
учетные регистры, на которых накапливаются итоговые данные по осуществленным операциям, эти итоги
формируются с учетом временного интервала проведения операции. Такие итоговые данные могут быть разби-
ты на составляющие в соответствии с объектами, принимающими участие в осуществлении операции. Напри-
мер, счет "товар" может содержать сумму имеющихся на складе товаров и в то же время эта сумма может быть
разбита на составляющие суммы по каждому товару. В данном случае говорят о наличии аналитического учета
по данному счету, а сами объекты, по которым идет разбиение итоговых данных, – аналитическими. Каждую
операцию при функционировании предложенной модели регистрируют посредством соответствующего ей до-
кумента в специальном журнале операций. Документы представляют собой алгоритмы формирования итоговых
данных на счетах, задействованных в данной операции. Для документов пользователь самостоятельно может
определить структуру входной информации, характеризующую операцию (обычно в виде табличной ведомо-
сти), указать арифметические формулы расчетов для получения по исходной информации итоговых регистра-
ционных данных (аналогично электронным таблицам), описать алгоритмическую схему формирования итогов
на счетах и создать печатную форму документа регистрируемой операции при необходимости. Отчеты пред-
ставляют собой отображение итоговых данных по различным временным интервалам, разбиение итоговых дан-
ных по аналитическим объектам, по операциям, по взаимодействию между отдельными аналитическими объек-
тами, отчеты используются не только для анализа итоговых данных, но и для редактирования процесса регист-
рации операций. Исходя из сказанного основу модели составляют следующие n отношения:
1R – план счетов, отношение определено на декартовом произведении следующих множеств: <номера
счетов>*<наименования счетов>*<группы аналитических объектов, связанных с данным счетом>. Множество
<группы аналитических объектов> может быть пустым, в этом случае для выбранного счета не ведется анали-
тический учет.
2R – группы аналитических объектов (назовем их справочниками), отношение определено на декарто-
вом произведении множеств <номера справочников>*<наименования справочников>*<атрибуты (свойства)
аналитического объекта>, в данном случае <атрибуты аналитического объекта> могут быть множеством или
отношением, если количество атрибутов данного объекта больше 1 (например, аналитический объект "органи-
зация" характеризуется набором атрибутов, которые могут быть описаны в виде следующего отношения: <на-
именование организации>*<юридический адрес>*<банковский расчетный счет> и т.д.).
3R – журнал регистрации учетных операций, отношение определено на следующем декартовом произ-
ведении: <дата операции>*<наименование документа, регистрирующего операцию>*<состояние операции –
осуществленная или планируемая>.
4R – документы регистрации операций: отношение определено следующим образом: <номер докумен-
та>*<структура входной информации для документа>< программа формирования накопления итогов на счетах,
затрагиваемых данной операцией><печатная форма отчета по данной операции>. Здесь <структура входной
информации для документа> представляет собой отношение, описывающее в виде таблицы структуру входной
информации, которая должна быть заполнена и рассчитана во время регистрации операции. Форма отчета по
операции также определяется в виде отношения, тогда как программа формирования итоговых результатов по
факту регистрации данной операции может быть описана САА-схемой алгоритма ее функционирования над
входными данными документа и итоговыми данными учетной модели. Перечисленные отношения определяют
структуру данных функционирования такой модели, а алгоритмы регистрации и накопления информации опи-
сываются в виде САА-схем, по которым с помощью инструментальных средств строятся программы в выбран-
ном языке программирования. Инструментальные средства алгоритмики кроме автоматизированных средств
построения программ по их описаниям в САА–схемах содержат средства преобразования n-отношений описа-
ния данных в предметной области в структуру той базы данных, в среде которой будет осуществляться проек-
тирование программной системы функционирования такой модели. Манипулирование данными, представлен-
ными в виде n-отношений, сводится к использованию перечисленных (разделы 1-4) операций в клоне n-
отношений и автоматическому синтезу по выражениям в такой алгебре соответствующих операторов языка
SQL.
Заключение
Выполненное исследование относится к интенсивно развиваемой на Западе области знаний, названной
алгебраическая алгоритмика [30]. Для данной области характерно гармоничное соединение современной алгеб-
Теоретичні і методологічні основи програмування
33
ры и информатики. Точнее, алгебраические результаты, относящиеся, в частности, к различным алгебрам (по-
лугруппы, кольца, системы уравнений и пр.), дополняются алгоритмами и программами обработки соответст-
вующих структур данных. При этом вне поля зрения осталась алгебра алгоритмов [8], находящаяся на стыке
алгебры и информатики.
В данной статье получены следующие результаты:
• построены клоны n-отношений для создания алгебраического аппарата, нацеленного на совме-
стное проектирование структур данных различной природы и алгоритмов их обработки;
• намечен подход к распространению результатов по теории полугрупповых клонов (клоны фор-
мальных языков и грамматик, автоматные и алгоритмические клоны [22, 23]) на построенные в
данной статье клоны n-отношений;
• на базе полученных результатов открывается возможность дальнейшего развития интегрирован-
ного инструментария алгебры алгоритмики с целью обеспечения разноаспектного проектирова-
ния и синтеза программ по известной формуле Вирта: алгоритмы + структуры данных = про-
граммы.
В качестве перспективы дальнейшего развития аппарата алгебры алгоритмики сформулируем ряд нере-
шённых задач для последующих исследований по алгебре алгоритмики, которая восходит от результатов и па-
радигм В.М. Глушкова [31].
1. Построение системы образующих для клона алгебр n-отношений, порождающей семейство алгебр,
включающее алгебру Кодда.
2. Решение проблемы функциональной полноты для построенного клона и исследование свойств решёт-
ки его подалгебр, а также поверхности – фрагмента, состоящего из конечнопорождённых подалгебр данного
клона.
3. Разработка на базе клонов алгебр n-отношений инструментальных средств для совместного проекти-
рования структур: данных, операторов и предикатов для решения прикладных задач, относящихся к различным
предметным областям.
4. Усовершенствование на базе аппарата алгебр n-отношений методов интенсивного обучения аудитории
(в том числе и виртуальной) для проектирования и автоматизации построения обучающих систем, включая и
дистанционные.
5. Озвучивание созданных инструментальных средств, с ориентацией их на обучение пользователей,
имеющих физические ограничения, включая и лиц с проблемами зрения.
1. Кон П. Универсальная алгебра. – М.: Мир, 1968. – 348 с.
2. Курош А.Г. Лекции по общей алгебре. – М.: Физматгиз. – 1962. – 396с.
3. Post E.L. The two-valued iterative systems of mathematical logic // Ann. Math. Studies. – 1941. – Vol. 5. – P. 147.
4. Яблонский С.В. Функциональные построения в k-значной логике // Труды МИАН СССР. – 1958. – Т.51. – С. 5-142.
5. Мальцев А.И. Итеративные алгебры и многообразия Поста // Избр. тр. А.И.Мальцева. – 1976. – Т.2. – С. 316-330.
6. Цейтлин Г.Е. Алгебраическая алгоритмика: теория и приложения // Кибернетика и системный анализ. – 2003. – №1. – С. 8-18.
7. Цейтлин Г.Е. Алгебры Глушкова и теория клонов // Кибернетика и системный анализ. – 2003. – №4. – С. 48-58.
8. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. – К.: Наук. думка. – 1-е изд., 1974. – 327с.; 2-е изд.,
перераб., 1978. – 318 с.; 3-е изд., перераб. и доп, 1989. – 376 с. Gluschkow W.M., Zeitlin G.E., Justchenko J.L. Algebra. Sprachen. Pro-
grammierung. – Berlin: Akademie-Verlag, 1980. – 340 p.
9. Цейтлин Г.Е. О бесконечно порожденных подалгебрах модифицированной алгебры Поста // Кибернетика. – 1971. – №2. – С. 43-56.
10. Теория Галуа для алгебр Поста. – Ч. 1, 2 / В.Г. Бондарчук, Л.А. Калужнин, В.Н. Котов, Б.А. Ромов // Кибернетика. – 1969. – №3. – С. 1-
10; №5. – С. 1-9.
11. Цейтлин Г.Е. Введение в алгоритмику. – К.: Сфера, 1998. – 310 с.
12. Codd E.F. A Relational Model of Data for Large Shared Data Banks // Comm. ACM. – 1970. – Vol. 13. – №6. – P. 377-387.
13. Дейт К.Дж. Введение в системы баз данных. – КГ: Диалектика, 1999. – 784 с.
14. Tsejtlin G.E. The theory of modified Post algebras and multidimensional automata structures. – Lecture Note in Computer Science. – 1975. –
№32. – P. 418-424.
15. Боднарчук В.Г., Цейтлин Г.Е. Об алгебрах периодически определенных преобразований бесконечного регистра // Кибернетика. – 1969.
– №1. – С. 18-28.
16. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир, 1978. – Т. 3. – 843 с.
17. Лорин Г. Сортировка и системы сортировки. – М.: Наука, 1983. – 384 с.
18. Vladimir Estivill-Castro and Derick Wood. A Survey of Adaptive Sorting Algorithms. // ACM Computing Surveys, 1992. – Vol. 24. – №4,
December. – P. 441-476.
19. Цейтлин Г.Е. Формальная трансформация структурированных алгоритмов сортировки // Программирование. – 1985. – №2. – С. 79-91.
20. Цейтлин Г.Е. Проектирование алгоритмов параллельной сортировки // Программирование. – 1989. – №6. – С. 4-19.
21. Цейтлин Г.Е. Поиск и сортировка: классификация, трансформация, синтез. I, II // Автоматика и телемеханика. – 1992. – №4. – С. 147-
154; №5.– С. 156-165.
22. Цейтлин Г. Е. Проблема функциональной полноты для мета-алгебр регулярных событий // Кибернетика и системный анализ. – 2000. –
№6. – С. 14-27.
23. Цейтлин Г. Е. Проблема функциональной полноты в итеративных мета-алгебрах // Кибернетика и системный анализ. – 1998. – №2. –
С. 28-45.
24. Многоуровневое структурное проектирование программ: Теоретические основы, инструментарий / Е.Л. Ющенко, Г.Е. Цейтлин, В.П.
Грицай, Т.К. Терзян. – М.: Финансы и статистика, 1989. – 208 с.
25. Интегрированный инструментарий проектирования и синтеза классов алгоритмов и программ / Цейтлин Г.Е., Амонс А.А., Головин
О.В., Зубцов А.Ю. - Кибернетика и системный анализ. – 2000. – №3. – С. 165-170.
26. Цейтлин Г.Е., Теленик С.Ф., Амонс А.А. Алгебро-логическая формализация в объектно-ориентированных технологиях // Пробл. про-
граммирования. – 2002. – № 1-2. – С. 136-146.
Теоретичні і методологічні основи програмування
34
27. Цейтлин Г.Е., Яценко Е.А. Элементы алгебраической алгоритмики и объектно-ориентированный синтез параллельных программ //
Математические машины и системы. – 2003. – № 2. – С. 64-76.
28. Яценко Е.А., Мохница А.С. Инструментальные средства конструирования синтаксически правильных параллельных алгоритмов и
программ // Пробл. программирования. Спец. выпуск по материалам 4-й Междунар. науч.-практ. конф. по программированию
УкрПРОГ'2004. – 2004. – №2-3. – С. 444-450.
29. Яценко Е.А. Алгебры гиперсхем и интегрированный инструментарий синтеза программ в современных объектно-ориентированных
средах. // Кибернетика и системный анализ. – 2004. – №1. – С. 47-52.
30. Ноден П., Китте К. Алгебраическая алгоритмика (с упражнениями и решениями). – М.: Мир, 1999. – 720 с.
31. Капитонова Ю.В., Летичевский А.А. Парадигмы и идеи академика В.М.Глушкова. – К: Наук. думка, 2003. – 330 с.
|
| id | nasplib_isofts_kiev_ua-123456789-1516 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Russian |
| last_indexed | 2025-11-27T20:20:53Z |
| publishDate | 2006 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Захария, Л.М. Луценко, Т.В. Цейтлин, Г.Е. 2008-08-21T15:32:50Z 2008-08-21T15:32:50Z 2006 О построении клонов алгебр функциональных n-отношенеий / Л.М. Захария, Т.В. Луценко, Г.Е. Цейтлин // Проблеми програмування. — 2006. — N 2-3. — С. 25-34. — Бібліогр.: 31 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/1516 519.3 Рассматриваются клоны алгебр n-отношений. Данные клоны включают алгебры, равномощные алгебре Кодда. Особое внимание уделено распространению результатов, полученных ранее по полугрупповым (грамматическим и алгоритмическим) клонам на по- строенные клоны алгебр функциональных n-отношений; эти клоны определяются посредством соответствующих суперпозиций n- отношений и связанных с ними функций, соответственно. Очерчены одномерные и многомерные вычислительные структуры и ас- социированные с ними предметные области. Clones of algebras of n-relations are examined. The given clones include algebras, equipotent to Codd algebra. High emphasis is placed on distribution of the results received on semigroup (grammatical and algorithmic) clones to the clones of algebras of functional n-relations. Both one-dimensional and multivariate computing structures and the subject domains associated with them are outlined. ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування О построении клонов алгебр функциональных n-отношенеий On constructing clones of algebras of functional n-relations Article published earlier |
| spellingShingle | О построении клонов алгебр функциональных n-отношенеий Захария, Л.М. Луценко, Т.В. Цейтлин, Г.Е. Теоретичні та методологічні основи програмування |
| title | О построении клонов алгебр функциональных n-отношенеий |
| title_alt | On constructing clones of algebras of functional n-relations |
| title_full | О построении клонов алгебр функциональных n-отношенеий |
| title_fullStr | О построении клонов алгебр функциональных n-отношенеий |
| title_full_unstemmed | О построении клонов алгебр функциональных n-отношенеий |
| title_short | О построении клонов алгебр функциональных n-отношенеий |
| title_sort | о построении клонов алгебр функциональных n-отношенеий |
| topic | Теоретичні та методологічні основи програмування |
| topic_facet | Теоретичні та методологічні основи програмування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/1516 |
| work_keys_str_mv | AT zahariâlm opostroeniiklonovalgebrfunkcionalʹnyhnotnošeneii AT lucenkotv opostroeniiklonovalgebrfunkcionalʹnyhnotnošeneii AT ceitlinge opostroeniiklonovalgebrfunkcionalʹnyhnotnošeneii AT zahariâlm onconstructingclonesofalgebrasoffunctionalnrelations AT lucenkotv onconstructingclonesofalgebrasoffunctionalnrelations AT ceitlinge onconstructingclonesofalgebrasoffunctionalnrelations |