Конструктивное представление множественных объектов и их свойства

На основе конструктивной структуры предложено унифицированное представление гибридных множественных объектов. Рассмотрены алгебраические свойства и операции над этими объектами....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2014
Hauptverfasser:	Ильман, В.М., Шинкаренко, В.И.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут програмних систем НАН України 2014
Schriftenreihe:	Проблеми програмування
Schlagworte:	Теоретичні та методологічні основи програмування
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/86735
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:	Конструктивное представление множественных объектов и их свойства / В.М. Ильман, В.И. Шинкаренко // Проблеми програмування. — 2014. — № 1. — С. 3-17. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-86735
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-867352025-02-23T19:46:36Z Конструктивное представление множественных объектов и их свойства The constructional knowledge of sets and their properties Ильман, В.М. Шинкаренко, В.И. Теоретичні та методологічні основи програмування На основе конструктивной структуры предложено унифицированное представление гибридных множественных объектов. Рассмотрены алгебраические свойства и операции над этими объектами. 2014 Article Конструктивное представление множественных объектов и их свойства / В.М. Ильман, В.И. Шинкаренко // Проблеми програмування. — 2014. — № 1. — С. 3-17. — Бібліогр.: 15 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/86735 517. 519.2, 004:512 ru Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування
spellingShingle	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування Ильман, В.М. Шинкаренко, В.И. Конструктивное представление множественных объектов и их свойства Проблеми програмування
description	На основе конструктивной структуры предложено унифицированное представление гибридных множественных объектов. Рассмотрены алгебраические свойства и операции над этими объектами.
format	Article
author	Ильман, В.М. Шинкаренко, В.И.
author_facet	Ильман, В.М. Шинкаренко, В.И.
author_sort	Ильман, В.М.
title	Конструктивное представление множественных объектов и их свойства
title_short	Конструктивное представление множественных объектов и их свойства
title_full	Конструктивное представление множественных объектов и их свойства
title_fullStr	Конструктивное представление множественных объектов и их свойства
title_full_unstemmed	Конструктивное представление множественных объектов и их свойства
title_sort	конструктивное представление множественных объектов и их свойства
publisher	Інститут програмних систем НАН України
publishDate	2014
topic_facet	Теоретичні та методологічні основи програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/86735
citation_txt	Конструктивное представление множественных объектов и их свойства / В.М. Ильман, В.И. Шинкаренко // Проблеми програмування. — 2014. — № 1. — С. 3-17. — Бібліогр.: 15 назв. — рос.
series	Проблеми програмування
work_keys_str_mv	AT ilʹmanvm konstruktivnoepredstavleniemnožestvennyhobʺektoviihsvojstva AT šinkarenkovi konstruktivnoepredstavleniemnožestvennyhobʺektoviihsvojstva AT ilʹmanvm theconstructionalknowledgeofsetsandtheirproperties AT šinkarenkovi theconstructionalknowledgeofsetsandtheirproperties
first_indexed	2025-11-24T20:02:28Z
last_indexed	2025-11-24T20:02:28Z
_version_	1849703319003463680
fulltext	Теоретичні та методологічні основи програмування © В.М. Ильман, В.И. Шинкаренко, 2014 ISSN 1727-4907. Проблеми програмування. 2014. № 1 3 УДК 517. 519.2, 004:512 В.М. Ильман, В.И. Шинкаренко КОНСТРУКТИВНОЕ ПРЕДСТАВЛЕНИЕ МНОЖЕСТВЕННЫХ ОБЪЕКТОВ И ИХ СВОЙСТВА На основе конструктивной структуры предложено унифицированное представление гибридных мно- жественных объектов. Рассмотрены алгебраические свойства и операции над этими объектами. Введение Множественные структуры играют важную роль не только в классической математике, но и во многих приложениях [1]. Так множественные структуры интер- претируют и отражают технологические процессы предметных областей, являют- ся атрибутами структур данных, языков программирования, используются в сетях Петри, базах данных, в языках запросов и др. И, следовательно, для этих струк- тур во многих прикладных пакетах преду- смотрены способы их задания [2], над ними предусмотрены некоторые операции, например, в [3, 4] операции объединения (union), пересечения (intersect), разности (minus) и пр. Обычно, классические множества принято считать абстрактными не имею- щими семантики, т. е. их элементы лише- ны смыслового признака кроме возмож- ного смысла определяющего универсума. Используя прием именования элементов нетрадиционных множеств последние мо- жно представить в классическом виде. Од- нако, тогда элементы поименованных пре- дставлений множеств приобретают опре- деленный семантический признак, кото- рый, как правило в искусственных систе- мах закрепляется синтаксическими прави- лами или иначе. Например, в языках прог- раммирования это типы, структуры дан- ных и др. Еще одно последствие имено- вания проявляется в том, что при «работе» с такими множествами часто необходимо иметь значения элементов (имен-знаков) или их составных частей. Решение этого вопроса возможно с помощью номинатив- ных отношений [5] или более общо – функций множеств [1]. Существует большое разнообразие подходов для задания множеств. Это ли- нейные подходы на основе правил пере- числения, функциональные на основе характеристических и других функций, геометрические и алгебраические подходы на основе преобразований, конструктив- ные на основе формальных грамматик, ав- томатов, сетей, алгоритмические и иные подходы. Среди множественных объектов по структурному признаку можно выде- лить классические множества, множества- списки, мультимножества, нечеткие мно- жества, множества с предопределенными свойствами и прочие. В прикладных областях среди не- традиционных множественных структур встречаются конструкции с повторяющи- мися свободными элементами – мульти- множества и закрепленными элементами – списки. Достаточно широкий обзор при- ложений этих структур в компьютерных и других науках дан в работе [6] и частично в материалах конференции [7]. В своей ра- боте Д. Кнут [8] обратил внимание на то, что строки программ следует трактовать как мультимножества. Однако в реально- сти строки программ представляют более сложные множественные структуры, кото- рые в приложениях необходимо применять на «полную силу». Исследованию сложных (гибрид- ных) множественных структур на основе мультимножеств и списков посвящена настоящая работа. Подход к представле- нию технологических процессов, а также программированию на основе гибридных множественных моделей более полно от- ражает специфику процессов и техноло- Теоретичні та методологічні основи програмування 4 гию программирования. Известно, что предметные области и соответственно их множественные модели существенно вли- яют на представления объектов исследова- ний. Поэтому важен вопрос унификации представления множеств и задание алгеб- ры над унифицированными множествен- ными объектами. В работе рассмотрены некоторые подходы к заданию множеств и показано, что конструктивные модели построения множественных объектов, их анализ, и «работа напрямую» с такими объектами предпочтительнее. Алгебраический ана- лиз множеств, классов множеств и слож- ных множеств выполняется на мно- жественных объектах порожденных, пред- ложенной в работе, унифицированной конструктивной моделью. Рассмотрены некоторые операции над множественны- ми объектами. Представления множественных объектов Пусть E некоторый (символьный) универсум. Для представления множе- ственных объектов введем нейтральный (пустой) символ  , такой, что E  и { } { }  [1] и предположим, что K  пусть { }K K  . Множество A на универсуме E можно задать перечислением его элемен- тов, т. е. { },iA a i I   , ia E  & ,k ja a A  k ja a , тогда A E или функционально, посредством характери- стической функции 1, ; ( ) 0, ; A a A a a A       (1) или иным известным способом. Можно использовать и конструк- тивный подход к формированию множеств (set) на универсуме E . Так схема- генератор построения любого перечисли- мого множества A E при начальном множестве 1 \{ }E E  на основе подста- новок может быть такой: 1 { }; , ; ; .a E                 (2) Здесь { }  – начальная подста- новка, а подстановка 1a E   для любо- го выбранного a применяется один раз в процессе построения множества A , что можно осуществить подстановкой с логи- ческим выводом 1 1 1 \{ }a E E E a     . Следует отметить, что схема (2) задает как множество { } , так и любое другое, со- держащее пустой элемент  . Нетрудно убедиться в том, что представления множества { },iA a i I  , в виде (1) и (2) взаимнооднозначно. Рассмотрим другую множествен- ную конструкцию – мультимножество. Используем термин мультимножество, введенный Кнутом [9] при рассмотрении элементов комбинаторной математики. Мультимножество M по Кнуту – множе- ство { };iA a i I   с повторяющимися элементами кратности k . Если на обыч- ном множестве B E задать отношение повторяемости элементов 2 : B   ( , )b k , получим мультимножество M . Очевидно, отношение  не рефлексивно, не симметрично, не транзитивно, но упо- рядочено по представлению пар ( , )b k . По- этому, его поименованная структура в скобочной форме имеет вид {( , ); , , }i i i iM a k a E i I k    . (3) Нетрудно видеть, что из мультим- ножества (3) как частный случай получа- ется обычное множество {( , ); 1, }i i iM a k k i I     {( ,1); }ia i I A   . При функциональном подходе – ес- ли :f A , то мультимножеству M можно сопоставить характеристическую функцию Теоретичні та методологічні основи програмування 5 ( ), , ( ) 0, , f f a a M a a M       (4) которая при значениях ( ) 1f a  , a A  является характеристикой (1) для множе- ства A . Если снять ограничения по четвер- той подстановке в схеме (2), то предыду- щая схема (2) порождает мультимно- жество M на универсуме E с про- извольной (заранее неопределенной) крат- ностью элемента. Устранить этот недо- статок можно, введя логический вывод и номинативное отношение ( ) [5] над вто- рым местом пары ( , )  . Так, если принять 0E E за начальное множество в рекур- сивном правиле из (2), то получим иную схему-генератор построения мультимно- жества 0 0 0 0 { }; ( , ), ; ; ; & : \{ }; . a E a E E E a k                        (5) Здесь замечания относительно ак- сиомы и четвертой продукции остаются теми же, что и в схеме (2). Так же как предыдущая схема (2), схема (5) генерирует пустое муль- тимножество и любое другое множество с нейтральным символом. Кроме того, меж- ду представлением мультимножества в ви- де (3) и заданием генератором (5) взаимно- однозначное. На множестве M может быть зада- на, посредством указателей (связыванием элементов), как в программировании, или закреплением мест, неявная списочная структура {[ , ]}i iM a k . Явную структуру списка определим, задав отношение на де- картовом произведении M K  так, что 3 : ( , \| , )M K a m k     или за- дав отношение связывания элементов 2 : ( , )M M a b   , позволяющие пред- ставить список скобочными формами: {(( , ), ); , ,N i ij i i ijM a m k a M m K   1 2, , , , } ii kk j j j j  (6) {( , )}Z i jM a a ; ,i ja a M . (6’) В списочном представлении (6) ijm – порядковый номер элемента ia в по- следовательности или нейтральный сим- вол, а ik – кратность этого элемента во множестве NM . Представление (6’) ука- зывает на связь элемента ja с предше- ственником ia . Представления (6) и (6’) могут задавать связанные и не связанные списки, однорядные и многорядные и дру- гие списки. Пусть однорядные связанные списки образуют списочный базис. Тогда с помощью операций над базисом можно построить другие списочные конструкции. Базисная структура (6) переопределена, так как кратность элемента ia может быть подсчитана через количество мест этого элемента в списке, однако для дальнейше- го удобно использовать это представление. Если в базисной структуре (6) воспользо- ваться условием { } { }E E E E      , (7) то a E  имеем ( , )a a  . Тогда муль- тимножество является частным случаем списка M . Заметим, что отношение  является отношением частичного порядка по вто- рому месту. Отношение  , вообще говоря, также обладает свойством частичного по- рядка. Характеристическая функция ба- зисного списка (6) имеет вид (4), в котором :f A K  . При условии { }   эта характеристика f определяет муль- тимножество M . Для базисного списка со связыванием (6’) характеристическую функцию простого вида построить сложно. Конструктивно список можно по- строить на некотором заданном множестве с помощью операций переименования по второму (и третьему) месту. Теоретичні та методологічні основи програмування 6 Определение 1. Операцией пере- именования tf по параметру t на множе- стве K назовем унарное отображение :t K K  . Операцией переименования t по двухместному параметру t на мно- жестве M назовем бинарное отображение :t M M M M   . Из определения следует, что опера- ции tf и t неоднозначные, однако, если указать конкретные образы отображений, тогда неоднозначность операций устраня- ется, и в этом случае обозначим эти опера- ции так t rf и , t a b . Для списков NM справедлива тео- рема. Теорема 1. Если для списков NM  {(( , ), )}i ij ia m k и {(( , ),N q qlM a m   )}qk имеют место условия: # #N NM M  & ( ,i qa M a M     ) и наоборот; если i qa a & i qk k , то t rf NM M , t rf N NM M  . Здесь символ # обозначает мощ- ность множества. Доказательство теоремы основано на условии (7) и операциях переименова- ния. Аналогичная теорема имеет место и для списков со связыванием элементов ZM . Другие конструктивные схемы ге- нерирования списков (6) и (6’) могут быть следующие { }; (( , ), ), ; ; ; ; . a E m K k                           { }; ( , ), ; ; ; . a E b E                      (8) В схемах (8) –  начальный символ и правило a E   применяется как для различных элементов универсума, так и одинаковых элементов – причем места элементов в списке должны быть различ- ными. Пропущенные места в сформиро- ванном списке по первой схеме из (8) заполняются нейтральным элементом. Во второй схеме, чтобы список был базовым, должно выполняться условие, по которому в смежных парах первый элемент второй пары обязательно равнялся второму эле- менту первой пары. Такое задание кон- структивных схем списков является упрощенным и частично формальным. Бо- лее полной формализации первой схемы из (8) можно достичь с помощью логических выводов на подстановках и последующей операции морфизма  по схеме (9). В схеме-генераторе (9) введены обозначения: \| \|a – значение имени a , \| – символ «или». Отметим, что символ a в правилах 5p повторяется k раз, если это имя в цепочке l образует подцепочку 1 kl a .       1 2 3 4 1 1 5 : { } 0; : ; : 0 & ; ), & : \| \| \| \| \| \| 1& & \| \| 1 & \| \| \| & \| \| \| \| ), ), ), ; (9) ), ), : ( ) ( ), ) ( ), ); ( ), ) ( ) E p i p p m m k m m p m m m i i i m m l S p l                                                                            ( ) ()) (, ); ( ) ( ,; , ( ) \| \|; ()) ); (, ) ,; (, ) . a a E                                                После конструирования множества в схеме (9) к его элементам применяется Теоретичні та методологічні основи програмування 7 свойство поглощения нейтрального сим- вола [10], т. е. x x x   . (10) Отметим, что рекурсивное правило 3p частично определяет структурный уро- вень, конструируемого множества. Предложенный генератор является унифицированной в том смысле, что он обобщает построения множеств по схемам (2), (5) и больше того, может конструиро- вать гибридные множества, составленные из списков и мультимножеств. Так слож- ное множество 1 { ,( ,2),( ,3), , }M a b b c на части { , , , }a b c E  может быть получено по схеме (9) – (10) в результате примене- ния последовательности правил: 1 1 3 3 3 3 2 4,1 4,2 5 4,1 4,1 4,2 5 4,1 4,2 5 4,1 4,2 5 ( , , , , , , (1), , ( ), (2), (3), , ( ), (4), , ( ), (5), , ( )). P p p p p p p p p p a p p p p b p p p p p p c   Последовательность 1P по правилу 3p яв- ляется четырех уровневой, а по правилу 4,1p – двух уровневой и образует конст- рукцию {( , ) ,( ,2),( ,3) ,( , ) ,( , ) }a b b c        . Теперь используя свойство поглощения пустого символа (10) и учитывая условие (7), получаем множество 1M . В получен- ном множестве свободные элементы a , c и  образуют мультимножество ограни- ченное первым, четвертым и пятым места- ми их возможного расположения. Поэтому множество 1M можно записать и так { , , ,( ,3),( ,2)}c a b b или иначе. Представле- ние сложного множества 1M в виде { ,( ,2),( ,3), , }a b b c назовем его нормальной формой. Сложное множество 1M можно также построить на мультимножестве { , , , , }M a b c b , используя операции пе- реименования и результаты теоремы 1, так имеем: { , , , , } {( , ), ( , ), ( , ), ( , ), ( , )} { , ( ,2), ( ,3), , }. t rf a b c b a b c b b b a c           Таким образом, унифицированное представление сложных множеств осу- ществляется через наборы списков (муль- тимножеств) rM . Например, в языковых средах программирования, языках баз дан- ных и др. можно сконструировать слож- ные множественные структуры: на множествах множеств, множества списков и пр. Эти сложные структуры можно пред- ставить единообразно с представлением (6) и (6’) {(( , ), )}r rj rM M m k или {( , )}r iM M M . (11) Выражения (11) несмотря на свою компактность, могут иметь довольно сложные структуры, в них могут разнооб- разно сочетаться списочные и мультимно- жественные конструкции и даже незанятые места – «дыры». Для устране- ния дыр, как и в схемах (8) на свободных местах следует использовать нейтральный элемент. Например, комбинация схемы мультимножества типа (2) со второй спи- сочной схемой (8) дает конструктивную схему-генератор { }; ( , ), ; ( , ), ( , ), ( , ), ; , ; ; ( , ), ( , ), ( , ); ; ), ( ), ( ; ; ; ; ( ( ; ; ) ), ; , E l l h h G c c E a E b b E d d E                                                                       , порождающую сложные множества. Мож- но также воспользоваться при конструиро- вании сложных множеств приемом многоуровневого проектирования, как в программировании [11], используя схему- генератор (9). Множества множеств (11) могут иметь еще более сложные представления Теоретичні та методологічні основи програмування 8 через структуры объектов. Так, например, элементами множеств могут быть объекты связанных элементов (концов) универсума с бинарными связями типа интервалов [12], с n -арными связями типа графовых и др., атрибутивные множественные струк- туры и прочее. Однако, используя прием именования объектов множеств в (11) все- гда можно перейти к представлению мно- жеств в виде (6) или (6’). Утверждение 1. Конструктивные схемы-генераторы (2), (5) и ,E ES G по- рождают перечислимые множества. Дадим несколько необходимых по- нятий и определений. Определение 2. Множественным объектом (МО) M назовем конструктив- ное множество, которое сгенерировано схемой ES или EG (теоремой 1) и пред- ставленное в нормальной форме. Так как элементы мультимножеств этих гибридных объектов могут распола- гаться на различных свободных местах, то представление множественных объектов генератором (9) являются многоэкземпляр- ным. Так для рассмотренного выше объек- та 1M в схеме ES , имеем шесть экземпляров форм представления { ,( ,2),( ,3), , }a b b c , { ,( ,2),( ,3), , }a b b c  , { ,( ,2),( ,3), , }c b b a , { ,( ,2),( ,3), , }c b b a  , { ,( ,2),( ,3), , }b b a c и { ,( ,2),( ,3), , }b b c a . Очевидно, количество экземпляров m представления МО определяется парамет- рами входящего в него мультимножества M . Если #M n и jk , 1,2, ,j s крат- ности элементов множества M такие что, их сумма 1 s j j k n   , то m – полиномиаль- ный коэффициент равный 1 ! ! s j j n k   . В дальнейшем примем 1{ }m i iM M  . При значении 1m  множественный объект вырождается в список или мультимноже- ство. Определение 3. Множество всех МО объектов, порожденных генератором ES ( )EG , образуют класс – E ( GE ). Утверждение 2. Классы E и GE не совпадают. В дальнейшем уделим основное внимание гибридным множествам, порож- даемым генератором ES . К порождаемому МО объекту применяются правила (7) и (10), которые не порождают объект, а только трансформирует его, поэтому мож- но говорить об объекте, порожденном ге- нератором S . Задать класс МО объектов E мож- но также с помощью формального индук- тивного правила: 0M E – МО нулевого уровня; 1 { }, 0ES n nM E M n    ; ES nE M – конечное отображение по схеме (9) – (10) до 1n -го уровня; nM – МО n -го уровня, n  , max{ } 1i ij i j k m   (использованы обозна- чения формулы (6)). Если nM – класс объектов n -го уровня, тогда класс МО строится на клас- сах объектов различного уровня * * 0 i i E M   . Рассмотрим некоторые алгебраиче- ские свойства класса E . Над классом E , как над обычным множеством объектов можно ввести ал- гебру подклассов ( ,{ , , \, , })E E  A A . Так как множество { } E  и, если из класса E исключить пустое множе- ство, то получим подкласс \{ }E E   . Определение 4. Пусть подмноже- ство A E , тогда схема AS – подсхема схемы ES , т.е. A ES S , а множество A по отношению к схеме AS назовем определя- ющим. Теоретичні та методологічні основи програмування 9 Утверждение 3. На определяющем множестве A в схеме AS порождается класс A такой, что A . Из определений 3 и 4 и утвержде- ний 1 и 3 имеем результат. Теорема 2. Если ; ,A E B C E  , то * A E и * B C E , и B C  E , и * * \B C E . Если класс A E , тогда * \E A A есть дополнение класса A до класса E . Для дополнения A справедли- вы свойства. Свойство 1. * A A  . Свойство 2. * A A E . Теорема 3. На любом определяю- щем множестве A E с помощью опера- ции переименования строится тот же класс A , что и по схеме AS . Следствие 1. Алгебра EA – уни- версальная. Следствие 2. Класс E является кольцом по включению его подклассов. Так как из теоремы 2 имеем, что * ,A B E   * * * * & \A B E A B E   . Утверждение 4. По любому под- классу класса E однозначно восстанавли- вается определяющее множество соот- ветствующей схемы. Утверждение 5. Пустое множество – верхний предел последовательностей подклассов класса E . Рассмотрим некоторые операции и отношения над множественными объекта- ми класса E . Операции и отношения над множественными объектами В предыдущем параграфе уже рас- смотрены две операции переименования и их свойства. Эти операции можно приме- нять и ко всем МО объектам. Для коррект- ного задания других операций над слож- ными множествами необходимо ввести некоторые предварительные сведения, ка- сающиеся структуры множеств. Структуру МО объектов удобно задавать через пути их порождения генератором S . Пусть МО M E , тогда он по определению 3 порождается генератором ES . Определение 5. Последовательность (кортеж) правил ip схемы ES P  1 2 ( , , , ) ni i ip p p необходимых для по- строения МО M E назовем путем по- рожденного объекта или его структурой. Отношение между путем P и по- рожденным им объектом M однозначное, но не взаимнооднозначное. Определение 6. Два пути iP и jP эквивалентны ~i jP P , если они порождают один и тот же множественный объект. Отношение ~ является отношением эквивалентности. Обозначим P класс эк- вивалентности по отношению к объекту M его путей. Путь порождения объекта может быть конечным или бесконечным. Ограни- чимся рассмотрением конечных путей. Определение 7. Количество элемен- тов кортежа пути P назовем его длиной \| \|P . Допущение 1. Примем правило 1 1ip p за начало пути, а заключительное правило ni p ограниченного пути – за ко- нец пути. Концом пути в схеме ES может быть любое правило схемы, в том числе и правила 2p или 5p . Определение 8. Два пути iP  1 2 ( , , , ) ni i ip p p и 1 2 ( , , , ) mj j j jP p p p считаются равными i jP P , если имеют место два условия: 1) \| \| \| \|i jP P или n m , 2) имена их правил в схеме ES на одина- ковых местах совпадают. Теоретичні та методологічні основи програмування 10 Равенство путей ( ) является от- ношением эквивалентности, но не задает эквивалентность этих путей. Пусть на некотором определяющем множестве A E в схеме AS порожден МО объект M , структура порождения ко- торого i M P P имеет вид 1 2 ( , , , ) ni i ip p p . Определение 9. Структура jP  1 2 ( , , , ) mj j jp p p в схеме S называется подструктурой пути iP и записывается как j iP P , если m n и , 1 k ki jp p k m   . Путь jP назовем префиксом (префиксным путем) пути iP . Очевидно, что отношение на пу- тях МО объекта задает частичный поря- док. Из допущения 1 и определения 9 имеем, что любой путь подструктуры начинается из правила 1p схемы (9) и мо- жет оканчиваться любым из правил этой схемы, т. е. подструктура jP может по- рождать или не порождать МО. Путь, по- рождающий МО в некоторой схеме S обозначим P . Утверждение 6. Если для опреде- ляющего множества A в схеме AS порож- дены некоторые объекты со структурой iP и jP , причем порождающая структура jP в схеме BS ( B A ) всегда такая, что j iP P в схеме AS , то BS является под- схемой схемы AS , т. е. B AS S . Определение 10. Подмножествен- ным объектом (подмножеством, префикс- ным множеством) iM генерируемым в схеме BS объекта M ( iM M ) в схе- ме AS ( B AS S ) назовем такое под- множество, порожденное путем iM P , что iM M P P . Множество всех подмножеств объекта M назовем классом подмно- жеств (классом префиксных множеств) * { }iM M . Пусть два МО объекта ,iM M E сгенерированы в соответственных схемах BS и AS установим критерий, при кото- ром объект iM будет подмножеством объ- екта M . Теорема 4. Объект iM является подмножеством объекта M тогда и только тогда, когда B A и для их любых по- рождающих путей 1 2 ( , , , ) mi i i iM P p p p , 1 2 ( , , , ) nj j jM P p p p имеет место m n , , 1 k ki jp p k m   , и при этом совпадаю- щие правила порождают, точность до эк- земпляров объекта M , одинаковые пары ( , )sa z ; sa B , z K . Для рассмотренного выше примера путь порождения 1P множественного объ- екта 1 { ,( ,2),( ,3), , }M a b b c позволяет выделить в нем подструктуры 1 2( , )p p , 1 3 2 4,1 4,2 5( , , , ( ), , ( ))p p p p p p a , 1 3 3 2 4,1 4,2 5 4,1 4,2 5 ( , , , , ( ), , ( \| \| ), (2), , ( )), p p p p p p p a c p p p b   Тогда множество подмножеств – для объекта 1M в нормальной форме, со- ставленное из их экземпляров является 1 { },{ , ( ,1)}, { , ( ,1), ( , 2)}, { , ( ,1), ( , 2), },{ , ( ,1), ( , 2), , } a a c c b a c b b M a c b b a c a c b b a c c a                                                                       , (12) где скобками a c       обозначены альтернатив- Теоретичні та методологічні основи програмування 11 ные элементы подмножеств, которые мо- гут располагаться на соответствующих ме- стах без повторений (кратность символов , ,a c равна единице). Замечание 1. Для класса M объ- екта M справедливо: 1) M E ; 2) если iM M и * ji M M  , 1,2, ,j k ; 1 2i i iM M M , то для множественного объекта iM имеет место иерархия по отношению ( ) ; 3) объект * 1M M есть минималь- ный префикс, если jM в классе M , чтобы 1jM M ; 4) в классе M минимальный пре- фикс, в общем, не единственен; так для класса (12) их три { }a , { }c и { } . Так как МО объекты не однородны по составу, то для дальнейшего из них удобно выделить «однородные» части. Для этого введем две операции. 1q – операция извлечения приве- денного списка NM из множественного объекта M , является одноуровневым морфизмом, действующим по правилу: 1 1 1 1 1 1 1 1 1 1 1 ( ) ({ , , ( , ), , }) ({) (, ) ( ) (, ) (( , )) (, ) ( ) (, ) (}); q M q a b q q q a q q q q b q q       1 1 1 1 1 ({) {; (}) }; (, ) ,; (( , )) ( , ); ( ) ; ; q q q q q a a E            2q – операция извлечения муль- тимножества M из МО объекта M , яв- ляется двухуровневым морфизмом с ме- журовневым преобразованием, действую- щая по правилам: на первом уровне 2 2 2 2 2 2 2 2 2 2 2 ( ) ({ , ( , ), ( , ), , ( , ), ( , )}) ({) ( ) (, ) (( , ), ) (( , ), ) ( ) (, ) (( , ), ) (( , )}); q M q a b q q a q q q q b q q q                    2 2 2 2 2 ({) {; (( , )}) ( , )}; (, ) ,; (( , ), ) ; ( ) ; ; q q q q q a a a E              после преобразований поглощения (10) в полученном множестве, имеем 2{ , ,( , )}a b M   ; на втором уровне 2 2 2 2 2 2 2( ) ({) ( ) (,) ( ) (,( , )});q M q q a q q b q   2 2 2 2 ({) {; (, ) ,; (, ( , )}) }; ( ) ; . q q q q a a a E         Утверждение 7. M E  с помо- щью операций 1q и 2q однозначно выде- ляются такой приведенный список NM и мультимножество M , что ,NM M E и вообще говоря ,NM M M . Например, операции 1q и 2q , изв- лекают из объекта 1 { ,( ,2),( ,3)M a b b , 1 { ,( ,2),( ,3), , }M a b b c приведенный спи- сок {[ ,( ,1),( ,2), , ]}b b   и множество { , , }a c . Эти множества не являются под- множествами объекта 1M , хотя список имеет такую же структуру порождения, как и МО, а мультимножество имеет дру- гую структуру – 1 3 3 3 2 4,1 4,2, , , , , , ,p p p p p p p 5 4,1 4,2 5 4,1 4,2 5, , , , , ,p p p p p p p . Здесь, для отличия обычного списка от приведенного, введены скобки ([, ]) . Таким образом, операции 1q и 2q осуществляют однозначную декомпози- цию МО объектов, кроме того, они позво- ляют выполнить декомпозицию и пре- фиксных классов. Например, для класса (12) имеем декомпозицию объектов { } { , } { }, { , } ,{ , , } { } { , } a a M c a c a c c                     и * [ , ( , 2)],[ , ( , 2), ( ,3)], [ , ( , 2), ( ,3), ], [ , ( , 2), ( ,3), , ] N b b b M b b b b                   . Теоретичні та методологічні основи програмування 12 Утверждение 8. Если декомпози- ции M и NM класса M , то справедли- во замечание 1. Для преобразования приведенного списка в обычный, вообще несвязанный список, рассмотрим морфизм g рекурсив- ного парного группирования элементов приведенного списка с последующим при- менением свойств (7) и (10). Пусть приведенный список NM не- которого множественного объекта M E такого, что 3{[ , , , , , , ]}N k kM c c     , где ( , ),ic a i a E  , i ; тогда 3 3 ( ) ({[ , , , , , , ]}) ({[) ( , ), ( , ), ( , ), ( ])}; N k k k k g M g c c g g c g g c g                ({[) {, ( , ) ( , ) , ( , ) ( , ) ; k k kg g c c c g             3 3 3( , ) ( , ) , ( ]) ] ], (]}) }; k k kg c c c g g            1 1 ({ , , , ]}) ({ \| ) ( , ), ( , ])}; k k j k k g c c g c g c g c       1 1({ ) { , ({ ) { {, ( ,])j j k kg c c g g c c       ; Модифицированный с помощью парного группирования g приведенный список NM обозначим, как g NM . Список g NM обладает свойством частичной при- надлежности к классу E . Устранить ча- стичность можно с помощью операции переименования t rf . Очевидно, всякий МО объект мож- но представить через его компоненты де- композиции, если будет задана процедура восстановления объекта. Для этого введем операцию композиции ( )w в определенном смысле противоположную процедуре де- композиции. Пусть для МО объекта M компо- нентами декомпозиции является приве- денный список NM и мультимножество .M Если вначале принять ,T M тогда операцию ( )w определим через последова- тельную подстановку и присвоение , & \{ } : \{ } a a T T T T a         (13) ко всем нейтральным символам приведен- ного списка NM . Отметим, что композицию МО объ- екта M можно частично осуществить и над модифицированным списком g NM , до- полняя его элементами мультимножества до связанного объекта. Лемма 1. Для приведенного списка NM количество подстановок (13) совпада- ет с порядком нейтрального элемента и мощностью мультимножества M , и по ним восстанавливается объект M . Из леммы и определения операции ( )w имеем, что ( , )NM w M M , NM  ( , )Nw M  , ( , )M w M  и ( , )w   . В общем случае операция ( )w не коммута- тивна и не ассоциативна. Кроме того, из леммы 1 также имеем. Теорема 5. Если M и * NM компо- ненты композиции класса M , то N NM M  , M M  , ( , )Nw M M M . Рассмотрим подобие теоретико- множественных операций над компонен- тами классов E и M , при этом учитыва- ем, что для любой из этих операций ( ) имеет место свойство 1 2 1 2 1 2 1 2 1 2 ( , ) ( , ) ( , ). N N N N M M w M M w M M w M M M M        (14) Известно [8, 9, 13 – 15], что к муль- тимножествам применимы операции обычного объединения ( ) и объединения со сложением ( ) , обычного пересечения ( ) и пересечения с умножением ( ) , раз- Теоретичні та методологічні основи програмування 13 ности (\) и др., которые ,i jM M E  вы- полняются по правилам: { ; \| , ( ) max{ ( ), ( )}, ( ) }. i j i j i j M M M M x x M M m x m x m x m x     { ; \| , ( ) ( ) ( ), ( ) }. i j i j i j M M M M x x M M m x m x m x m x      { ; & , ( ) min{ ( ), ( )}, ( ) }. i j i j i j M M M M x x M M m x m x m x m x     { ; & , ( ) ( ) ( ), ( ) }. i j i j i j M M M M x x M M m x m x m x m x       , \ { ; & , ( ) ( ) ( ), ( ) }. i i j i j i j i j M M M M M M M x x M x M m x m x m x m x        Из приведенных правил следует, что операции ( ) , ( ) и (\) – обобщения операции с обычных множеств на муль- тимножества, а операции ( ) и ( ) отсут- ствует в классических множествах. Операция ( ) порождает новое множество присоединением к множеству iM множе- ства jM и поэтому она не коммутативна. Операция ( ) предполагает суммирование порядков общих элементов операндов- множеств. Распространим эти операции на ба- зисные списки ,i jM M E . Пусть имен- ными носителями, для списков iM и jM будут множества ,i jA A E и носителями мест списков ,i jN N  . 2 {( , ); \| , \| , ( ) max{ ( ), ( )}, ( ) } i j i j i j i j M M M M x r x A A r N N m x m x m x m x M       – в общем случае двухкомпонентный (не- связанный) списочный класс такой, что 2 M E . При этом возможны случаи: 1) если ( , )i i ia r M , ( , )j j ja r M и i ja a , i jr r , то в классе 2M имеем об- щую пару \| \|( , )i j i ja r и 2M имеет связное двухрядное представление; 2) если ( , )i i ia r M , ( , )j j ja r M и i ja a , i jr r r  , то в двухкомпонентном классе 2M имеем именную альтернатив- ную пару ( \| , )i ja a r ; 3) если i jM M , то 2 jM M . Класс 2M для первого и второго случаев является двухрядным по пред- ставлению, а в третьем случае вырождает- ся в список класса E . Например, объединение ( ) базисных списков класса E , 1 {( ,1),( ,2),( ,3),( ,4),( ,5)}M a b b c c и 2 {( ,1), ( ,2), ( ,3), ( ,4)}M a c b b является двухрядным списком {( \| ,1),( \| ,2),( \| ,3),( \| ,4),( ,5)}a a b c b b c b c . Следующую операцию присоеди- нения списка jM к списку iM с последу- ющим переименованием по второму параметру элементов – jM зададим так, чтобы результирующий список 1M был связным, т. е. 1M E и     1 1 {( , ); \| , \| , ( ) ( ) ( ), ( ) , ( , ) ( , ) }. i j t s j i j i j i j M M f j j s j M M M x r x A A r N N m x m x m x m x x r M x r M            Так объединением ( ) списков из предыдущего примера будет следующим: {( ,1), ( ,2), ( ,3), ( ,4), ( ,5), ( ,6), ( ,7), ( ,8), ( ,9)}. a b b c c a c b b Анализ операций ( ) и ( ) над мультимножествами и списками показыва- ет, что первая операция, в общем, может Теоретичні та методологічні основи програмування 14 применяться только над множественными объектами префиксного класса M . Дру- гая операция может применяться без огра- ничений на всем классе E . При этом по операции ( ) выполняется свойство за- мыкания на классе M , а по операции ( ) – на классе E . На основе операций объединения ( ) и ( ) рассмотрим комбинированную операцию частичного покрытия ( ) , для которой на мультимножествах –  , а на списках справедливо частичное равен- ство  , по которому имеет место пра- вило: 1 1 11 1 1 ( ) ( ) . i j i j i j M M M M M M M M      Здесь, в списках 1M и 11M совпа- дают имена элементов и их порядок следо- вания. Операция частичного покрытия предполагает использование операции пе- реименования по месту для связности ре- зультата. Операция ( ) обобщает операцию ( ) на классе M , ибо для подмножества i jM M справедливо i j i jM M M M  . Поэтому класс M частично замкнут по операции ( ) . Операция разности над списками имеет смысл тогда, когда они частично имеют одинаковые имена элементов. Рас- смотрим четыре модификации этой опера- ции. Операция естественной разности ( \) объектов. \ {( , ); ( , ) &( , ) , ( , ) ( , )}. t s i i j i j f i s i M M x r x r M x r M x r x r      Операция разности по имени и ме- сту 0( \ ) – (сильная разность). 0 ( , ), ( , ) &( , ) ; \ , ( , ) &( , ) . i j i j i j x r x r M x r M M M x r M x r M        Операция разности по имени 1( \ ) – (обобщенная разность) [1]. 1 ( , ), & , ; \ , & . i j i i j i j x r x A x A r N M M x A x A        Результатом рассмотренных опера- ций разности является приведенный спи- сок, который можно свести к обычному списку, используя операции g и t rf , такой оператор назовем разностью с переимено- ванием \\ \t rf g . Операции разности легко перено- сятся на множественные объекты. Напри- мер, для множественного объекта 1 { ,( ,2), , ( ,4), , ( ,6)}M a a d b c c и объекта 2 {( ,1), , , ( ,4),( ,5)}M c a c e d разность их мультимножеств – 1 2\ { }M M d следова- тельно, 1 2\ {( ,1), , ( ,3),( ,4)}M M a d b c , а обобщенная разность приведенных мно- жеств соответственно является 1 1\NM 2 1\ {[ ,( ,2), , ( ,4), , ]}NM a b    , поэтому 1 1 2\ { ,( ,2), , ( ,4), , }M M d a b   – четы- рехэкземплярный МО. Разность же (\\) на МО объектах неоднозначна, так раз- ность 1M \\ 2M определяет три различных множества { ,( ,2),( ,3)}d a b , {( ,1), ,( ,3)}a d b и {( ,1),( ,2), }a b d . Введенные разности ( \) , 0( \ ) и 1( \ ) позволяют рассмотреть три модифи- кации симметрической разности объектов 1 2 1 2 2 1( \ ) ( \ )M M M M M M  , где под символом ( \) понимается любая из трех операций разности. Теперь рассмотрим операцию пере- сечения списков в модификациях. Сильная операция пересечения по имени и месту ( ) . {( , ); ( , ) & , ( ) min{ ( ), ( )}, ( ) }, i j i j i j M M M M x r x r M M m x m x m x m x     Теоретичні та методологічні основи програмування 15 при этом, если список i jM M не связ- ный, то он дополняется до связного нейтральным символом необходимой кратности или переименовывается его нормальная форма по второму параметру элементов. Отметим, что условие min{ ( ), ( )} i jM M m x m x является лишним при сравнении пар объектов iM и jM , однако необходимо для сравнения поряд- ков нейтрального символа в приведенных списках. Из введенного правила операции ( ) следует, что, если i jM M , то i j iM M M и если в списках нет общих элементов, тогда \{ }i jM M  . Операция пересечения по имени 1( ) объектов. 1 {( , ); & , min{ , }, i j i j i i j j M M x r x A x A r r N r N       ( ) min{ ( ), ( )}, ( ) , ( , ) ( , )}. i j t s j M M f j s j m x m x m x m x x r x r     Операция 1( ) обобщает предыду- щую операцию пересечения. Другая операция пересечения с суммированием ( ) над списками выпол- няется в три этапа    2 ( , ); . i j i j i j M M M M x x A A     Операции первого и второго этапов рассмотрены выше, а правило выполнения операции 2( ) приведено далее [1]. Пусть ( , ) , 1,2i i ix r M i  , тогда 1 2 1 2 2 1 1 1 2 , ; ( , ), . x x M M x r x x      В этой операции, как и в предыду- щих операциях пересечения, может ис- пользоваться операция естественной раз- ности для исключения элементов, не по- павших в пересечение мультимножеств. Продемонстрируем это на МО объ- ектах 1 { ,( ,2), , ( ,4), , ( ,6)}M a a d b c c и 2 {( ,1), , , ( ,4), ( ,5)}M c a c a d при нахожде- нии пересечения с суммированием. Так как элемент d отсутствует в пересечении мультимножеств 1M и 2M , т. е. 2 2 1 2 { , }M M a c M   , то исключим его из первого множественного объекта 1 3\{ } { ,( ,2),( ,3), , ( ,5)}M d a a b c c M  и рассмотрим 1 2 3 2M M M M M    . Операция ( ) над приведенными списками 3 NM и 2 NM определяет приве- денный списочный объект { ,( ,2),( ,3), ,( ,5),( ,6), , ,( ,9),( ,10)}a b c c a d    и пересечение их носителей 3 2 { , , }A A a c . Тогда после применения операции 2( ) получим следующий при- веденный список: { ,( ,2), , , ( ,5),( ,6), , , ( ,9), }NM a c c a      и операция композиции ( , )Nw M M даст результирующий множественный объект { ,( ,2), , , ( ,5),( ,6), , , ( ,9), }M a a a c c c c a  . Анализ применения операции ( ) к множественным объектам 1M и 2M поз- воляет заключить, что для кратности 1 2 1 2 ( ) min{ ( ), ( )} M M M M m m m   спра- ведливо Утверждение 9. 1 2 1 2( ) # M M m M M  . Поэтому часть нейтральных симво- лов  , не превышающих кратности 1 2 ( ) M M m  , используется для получения связности списка 1 2 N NM M и оставшаяся располагается в этом списке за элементом с наибольшим местом. Над множественными объектами 1M и 2M может выполняться комбиниро- ванная операция 1( , ) – на декомпози- Теоретичні та методологічні основи програмування 16 циях 1M и 2M операция ( ) и на приве- денных списках 1 2 1N NM M . Для комби- нированной операции справедливо утверждение 9 и правило использования нейтрального символа. Результаты, рассмотренных опера- ций дают возможность привести следую- щие группы свойств. Для префиксного класса M при множествах 1 2 3, ,M M M M имеем: 1 1M M , 1M  , 1 2 2 1M M M M , 1 1 1M M M , 1 2 2 1M M M M , 1 1 1M M M , 1 2 3 1 2 3( ) ( )M M M M M M , 1 2 3 1 2 3( ) ( )M M M M M M , 1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M , 1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M ; 1 2 1 2 1 2 2 1 ( ) ( ) ( ) \| ( ). M M M M M M M M   В классе E для множественных объектов 1 2 3, ,M M M E справедливо: 1 1 1( \{ }) ( \{ })M M M     , 1 2 2 1M M M M , 1 1 1M M M , 1 2 3 1 2 3 1 2 3 ( ) ( ) , M M M M M M M M M    1 1\| ( )M A B M A B , 1 1\| ( )M A B M A B , * *,A B M E  ; 1 2 2 1M M M M   , 1 2 3 1 2 3 1 2 3 ( ) ( ) , M M M M M M M M M          1 2 2 1M M M M   , 1 2 3 1 2 3 1 2 3 ( ) ( ) , M M M M M M M M M          1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M      , 1 2 3 1 2 1 3( ) ( ) ( )M M M M M M M      , 1 2 3 1 3 2 3( ) \ ( \ ) ( \ )M M M M M M M , 1 2 3 1 3 2 3( ) \ ( \ ) ( \ )M M M M M M M   , 1 2 3 1 3 2 3( ) \ ( \ ) ( \ )M M M M M M M   . Последние три свойства имеют ме- сто и для разностей 0( \ ) и 1( \ ) . Выводы Для задания множественных объек- тов предложена универсальная конструк- тивная схема-генератор, которая может порождать множества, мультимножества, списки или гибридные объекты на основе этих множеств. Кроме того, с помощью введенной схемы определяется структура множественного объекта, выделяются префиксные классы объектов и др. Исследованы алгебраические свой- ства класса множественных объектов и префиксных подклассов. Установлено, что по любому подклассу класса множествен- ных объектов восстанавливается опреде- ляющее множество соответствующей схемы-генератора. Рассмотрены важные для приложе- ний операции декомпозиции и композиции множественных объектов. Дано расшире- ние теоретико-множественных операций с мультимножеств на гибридные множе- ственные объекты их классы и подклассы. Установлены свойства расширенных опе- раций. Предложенная модель конструиро- вания множественных объектов может быть использована при проектировании абстрактных структур данных в програм- мировании, разнообразных технологиче- ских процессов и др. 1. Босов А.А. Функции множества и их при- менение. – Днепродзержинск: Изд. дом „Андрей”, 2007. – 182 с. 2. Левин Д.Я. Язык сверхвысокого уровня СЕТЛ и его реализация. – Новосибирск: Наука, Сибирское отделение, 1983. – 160 с. 3. Прохоров Г.В., Лебедев М.А., Колбеев В.В. Пакет символьных вычислений Maple V. – М.: „Петит”, 1997. – 200 с. Теоретичні та методологічні основи програмування 17 4. Гарсиа-Молина Г., Ульман Дж., Уидом Дж.. Системы баз данных. – М.: Вильямс, 2004. – 1088 с. 5. Никитченко Н.С. Композиционно- номинативный подход к уточнению поня- тия программы // Проблемы программиро- вания. – 1999. – № 1. – С. 16 – 31. 6. Blizard W. The Development of Multiset Theory // Notre Dame Journal of Formal Log- ic. – 1989. – Vol. 30, N 1. – P. 36 – 66. 7. Богатырёва Ю.А. Мультимножества: биб- лиография, решетка мультимножеств // Те- зи доповідей VI Міжнародної конференції „Теоретичні та прикладні аспекти побудо- ви програмних систем”. – TAAPSD’2009. – К., 2009. – С. 13 – 20. 8. Knuth D. Context-Free Multilanguages // Theoretical Studies in Computer Science. – Academic Press, 1992. – P. 1 – 13. 9. Кнут Д. Искусство программирования для ЭВМ. – М.: Мир, Т 2. – 1977. – 727 с. 10. Ільман В.М., Скалозуб В.В., Шинкаренко В.І. Формальні структури та їх застосуван- ня.– Дніпропетровськ: Вид-во Дніпропетр. нац. ун-ту залізн. трансп., 2009. – 205 с. 11. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е., Яценко Е.А. Алгебро-алгоритми- ческие модели и методы параллельного программирования. – Киев: Академпери- одика, 2007. – 634 с. 12. Ільман В.М., Скалозуб В.В. Інтервальні об’єкти та їх граматичні структури // Вісник Дніпропетровського національно- го університету – 2010. – Вип. 29. – С. 131–144. 13. Albert J. Algebraic properties of bag data types // Severenteenth International Confer- ence on Very Large Data Bases. – Barcelona, Spain, 1991. – P. 211–219. 14. Singh D., Ibrahim A.M., Yohanna T., Singh J. An Overview of the Applications of Multiset // Novi Sad Journal of Mathematics. – 2007. – Vol. 37, N 2. – P. 73–92. 15. Syropoulos A. Mathematic of Multisets // Multiset Processing: Mathematical, Computer Science and Molecular Computing Points of View, Number 2235 in Lecture Notes in Co- muting Since. – Berlin: Springer-Verlag, 2001. – P. 347 – 358. Получено 13.06.2013 Об авторах: Ильман Валерий Михайлович, кандидат физико-математических наук, доцент, Шинкаренко Виктор Иванович, доктор технических наук, профессор. Место работы авторов: Днепропетровский национальный университет железнодорожного транспорта, кафедра «Компьютерные информационные технологии», 49010, г. Днепропетровск, ул. академика Лазаряна, 2. Каф. КИТ, ДНУЗТ. Тел.: (056) 373 1535. E-mail: shink@diit.edu.ua, ccp@diit-70.dp.ua mailto:ccp@diit-70.dp.ua

Конструктивное представление множественных объектов и их свойства

Institution

Ähnliche Einträge