Об одном методе задания фрактальных множеств
В якості способу задання множин пропонується використовувати R-системи. Увага приділяється лінійним обмеженим R-системам і зв’язкам між R-системами та R*-перетворювачами. Зокрема показано, що лінійна обмежена R-система задає замкнену множину. A set generating system called an R-system is proposed fo...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2009 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/44366 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Об одном методе задания фрактальных множеств / Л.П. Лисовик, Т.А. Карнаух // Кибернетика и системный анализ. — 2009. — № 3. — С. 42-50. — Бібліогр.: 9 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859634735442034688 |
|---|---|
| author | Лисовик, Л.П. Карнаух, Т.А. |
| author_facet | Лисовик, Л.П. Карнаух, Т.А. |
| citation_txt | Об одном методе задания фрактальных множеств / Л.П. Лисовик, Т.А. Карнаух // Кибернетика и системный анализ. — 2009. — № 3. — С. 42-50. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | В якості способу задання множин пропонується використовувати R-системи. Увага приділяється лінійним обмеженим R-системам і зв’язкам між R-системами та R*-перетворювачами. Зокрема показано, що лінійна обмежена R-система задає замкнену множину.
A set generating system called an R-system is proposed for the specification of sets. Formal properties of the system are studied. The case of a bounded linear R-system is discussed and relations between R-systems and R*-transducers are established. In particular, it is shown that a bounded linear R-system specifies a bounded closed set.
|
| first_indexed | 2025-12-07T13:14:51Z |
| format | Article |
| fulltext |
ÓÄÊ 519.71
Ë.Ï. ËÈÑÎÂÈÊ, Ò.À. ÊÀÐÍÀÓÕ
ÎÁ ÎÄÍÎÌ ÌÅÒÎÄÅ ÇÀÄÀÍÈß ÔÐÀÊÒÀËÜÍÛÕ ÌÍÎÆÅÑÒÂ
Êëþ÷åâûå ñëîâà: ôðàêòàë, R-ïðåîáðàçîâàòåëü, R-ñèñòåìà.
ÂÂÅÄÅÍÈÅ
Ïðè çàäàíèè ôðàêòàëüíûõ ìíîæåñòâ èñïîëüçóþòñÿ ðàçëè÷íûå ïîäõîäû, áîëüøèíñòâî
èç êîòîðûõ îñíîâàíî íà èòåðàòèâíûõ ïðîöåäóðàõ [1–3]. Íàïðèìåð, â ðåçóëüòàòå ãåî-
ìåòðè÷åñêèõ ïðåîáðàçîâàíèé âîçíèêàþò òàêèå ôðàêòàëüíûå ìíîæåñòâà, êàê ñàëôåòêà
Ñåðïèíñêîãî è ñíåæèíêà Êîõ. Óíèâåðñàëüíûì ñðåäñòâîì ÿâëÿþòñÿ ñèñòåìû èòåðèðî-
âàííûõ ôóíêöèé (IFS), îïðåäåëÿþùèå ìíîæåñòâî êàê íåïîäâèæíóþ òî÷êó ïðåîáðàçî-
âàíèÿ: ñîãëàñíî òåîðåìå î êîëëàæå [1, ñ. 96, 97] êàæäîå îãðàíè÷åííîå ìíîæåñòâî
ìîæíî äîñòàòî÷íî õîðîøî ïðèáëèçèòü àòòðàêòîðîì IFS.
Êðîìå òîãî, äëÿ çàäàíèÿ ìíîæåñòâ ñ ðåãóëÿðíîé ñòðóêòóðîé ìîæíî
èñïîëüçîâàòü ðàçëè÷íûå ñõåìû: èåðàðõè÷åñêèå ñèñòåìû èòåðèðîâàííûõ ôóíêöèé
(HIFS) [2, ñ. 283–292], óïðàâëÿåìûå ãðàôàìè êîíñòðóêöèè [4], à òàêæå âçâåøåííûå
êîíå÷íûå àâòîìàòû [5]. Íà ïåðâûé âçãëÿä âñå ýòè êîíñòðóêöèè áëèçêè ê ïîíÿòèþ
êîíå÷íîãî àâòîìàòà, ïîñêîëüêó äëÿ èõ çàäàíèÿ ìîæíî èñïîëüçîâàòü äèàãðàììó
ïåðåõîäîâ êëàññè÷åñêîãî êîíå÷íîãî àâòîìàòà. Òåì íå ìåíåå ïðîöåññ èõ ðàáîòû áîëåå
ñîîòâåòñòâóåò êîíå÷íîé äèñêðåòíîé ñåòè, â êîòîðîé êàæäûé óçåë ñíà÷àëà ñóììèðóåò
ñâîè âõîäû, à ïîòîì îáðàáàòûâàåò ïîëó÷åííóþ ñóììó, ïåðåäàâàÿ ðåçóëüòàòû äðóãèì
óçëàì.  ñëó÷àå HIFS è óïðàâëÿåìûõ ãðàôàìè êîíñòðóêöèé ðåçóëüòèðóþùåå
ìíîæåñòâî îïðåäåëÿåòñÿ ñ èñïîëüçîâàíèåì íåïîäâèæíîé òî÷êè ñèñòåìû.
Ñ ïîìîùüþ ïîíÿòèÿ àäðåñà [2, ñ. 307–320] òî÷êè àòòðàêòîðà IFS åñòåñòâåííûì
îáðàçîì ñòðîèòñÿ ñþðúåêöèÿ èç [ ; ]0 1 íà àòòðàêòîð. Ýòîò ïîäõîä ê çàäàíèþ ìíîæåñ-
òâà êàê îáðàçà åäèíè÷íîãî îòðåçêà ìîæíî ñóùåñòâåííî óïðîñòèòü, èñêëþ÷èâ èç
äàííîé ñõåìû ïðîìåæóòî÷íîå çâåíî — IFS. Òàê, äàæå êîíå÷íûå R-ïðåîáðàçîâàòåëè
ïîçâîëÿþò çàäàâàòü íåïðåðûâíûå ñþðúåêöèè åäèíè÷íîãî îòðåçêà íà ôðàêòàëüíûå
ìíîæåñòâà [6] è ñòðîèòü àëãîðèòìû íåïðåðûâíîãî îáõîäà ìíîæåñòâà, íàïðèìåð,
êðèâàÿ Ïåàíî çàäàåòñÿ êîíå÷íûì R-ïðåîáðàçîâàòåëåì [7]. Óêàçàííûé òèï çàäà÷
èìååò ðÿä âàæíûõ ïðèëîæåíèé. R*-ïðåîáðàçîâàòåëü [8], ÿâëÿÿñü îáîáùåíèåì ïîíÿ-
òèÿ R-ïðåîáðàçîâàòåëÿ, åùå áîëåå ðàñøèðÿåò âîçìîæíîñòè êîíñòðóêòèâíîãî çàäà-
íèÿ ìíîæåñòâà êàê îáðàçà îòðåçêà [ ; ]0 1.
Ïðåäëàãàåìûé â äàííîé ðàáîòå ñïîñîá çàäàíèÿ ôðàêòàëüíûõ ìíîæåñòâ R-ñèñ-
òåìàìè èñïîëüçóåò èìåííî êîíöåïöèþ êîíå÷íîãî àâòîìàòà, à íå êîíå÷íîé ñåòè ïà-
ðàëëåëüíî ðàáîòàþùèõ àëãîðèòìè÷åñêèõ óñòðîéñòâ. Ôóíêöèîíèðîâàíèå R-ñèñòåìû
â åâêëèäîâîì ïðîñòðàíñòâå ñîñòîèò â òîì, ÷òî, íà÷èíàÿ èç íà÷àëà êîîðäèíàò, òåêó-
ùàÿ òî÷êà ïîñëåäîâàòåëüíî óòî÷íÿåòñÿ ñèñòåìîé: íà êàæäîì øàãå îñóùåñòâëÿåòñÿ
ïåðåíîñ òåêóùåé òî÷êè íà âåêòîð, îïðåäåëÿåìûé òåêóùèì ñîñòîÿíèåì-íåòåðìèíà-
ëîì è òåêóùèìè êîýôôèöèåíòàìè ñæàòèÿ, à òàêæå ïåðåñ÷åò ñàìèõ êîýôôèöèåíòîâ
ñæàòèÿ. Ïðè ýòîì ñàì ïðîöåññ óòî÷íåíèÿ óïðàâëÿåòñÿ êîíå÷íûì ìíîæåñòâîì ñî-
ñòîÿíèé è èìååò íåäåòåðìèíèðîâàííûé õàðàêòåð, ÷òî ïîçâîëÿåò ïîëó÷àòü ðàçëè÷-
íûå ðåçóëüòèðóþùèå òî÷êè. Òàêèì îáðàçîì, êîíñòðóêöèÿ R-ñèñòåìû ÿâëÿåòñÿ ñèì-
áèîçîì ãðàììàòèêè, êîòîðàÿ ïîñëåäîâàòåëüíî ïîðîæäàåò ñëîâà, ò.å. çàäàþùèå òî÷-
êè ïîñëåäîâàòåëüíîñòè âåêòîðîâ ïðîñòðàíñòâà, è R*-ïðåîáðàçîâàòåëÿ,
óïðàâëÿþùåãî êîýôôèöèåíòàìè ñæàòèÿ. Ïî ñðàâíåíèþ ñ R*-ïðåîáðàçîâàòåëÿìè
R-ñèñòåìû áîëåå óäîáíû â òåõ ñëó÷àÿõ, êîãäà ïðåäñòàâëÿåò èíòåðåñ òîëüêî çàäàíèå
òî÷åê ôðàêòàëüíîãî ìíîæåñòâà, à íå íåïðåðûâíûé îáõîä. Ñëåäóåò òàêæå îòìåòèòü,
÷òî ïðè âû÷èñëåíèè òî÷êè ìíîæåñòâà, çàäàâàåìîãî R-ñèñòåìîé, íà êàæäîé èòåðà-
42 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
� Ë.Ï. Ëèñîâèê, Ò.À. Êàðíàóõ, 2009
öèè äîñòàòî÷íî ïðîâîäèòü âû÷èñëåíèÿ òîëüêî äëÿ îäíîãî óçëà äèàãðàììû ïåðåõî-
äîâ, à íå äëÿ âñåõ îäíîâðåìåííî, êàê òîãî òðåáóþò ñèñòåìû, ñîñòîÿùèå èç êîíå÷-
íîé ñåòè ïàðàëëåëüíî ðàáîòàþùèõ óñòðîéñòâ.
ÎÏÐÅÄÅËÅÍÈÅ R-ÑÈÑÒÅÌÛ
R-ñèñòåìà — ýòî ïÿòåðêà G n V B P S� ( , , , , )0 , ãäå n n N, � � , — ðàçìåðíîñòü ñèñ-
òåìû; V — ìíîæåñòâî íåòåðìèíàëüíûõ ñèìâîëîâ (íåòåðìèíàëîâ); B, B R n� , —
êîíå÷íîå ìíîæåñòâî âåêòîðîâ n-ìåðíîãî åâêëèäîâîãî ïðîñòðàíñòâà (àíàëîã òåð-
ìèíàëîâ); P — êîíå÷íîå ìíîæåñòâî ïðîäóêöèé âèäà S � �, ãäå S V� ,
� � � �
�B V R n( ( ) ) , R� � � ( ; )0 (cîäåðæàòåëüíî, ïðàâàÿ ÷àñòü ïðîäóêöèè S �
� b S k S km m( , ) ( , )1 1 � ñîñòîèò èç âåêòîðà b, êîòîðûé ó÷àñòâóåò â ïåðåíîñå òåêó-
ùåé òî÷êè, à òàêæå èç êîíå÷íîé ïîñëåäîâàòåëüíîñòè ïàð — íåòåðìèíàë, âåêòîð
ñæàòèÿ; êàæäûé âåêòîð ñæàòèÿ ki ñîñòîèò èç êîýôôèöèåíòîâ ñæàòèÿ äëÿ êàæäîé
èç n êîîðäèíàòíûõ îñåé); S 0 , S V0 � , — íà÷àëüíûé ñèìâîë âûâîäà (àêñèîìà).
Çàïèñü S k� � � �1 2| | |� ÿâëÿåòñÿ ñîêðàùåíèåì çàïèñè S S� �� �1 2, ,�
� ,S k� � , êàê ýòî ïðèíÿòî äëÿ ãðàììàòèê. Îòíîøåíèå � âûâîäèìîñòè â R-ñèñòå-
ìå G îïðåäåëåíî íà ìíîæåñòâå R V Rn n� � �
�( ( ) ) ñëåäóþùèì îáðàçîì.
Ïóñòü â ñèñòåìå ïðîäóêöèé P èìååòñÿ ïðîäóêöèÿ p S b S k� �( ( , )1 1 �
� ( , ))S km m è x R n� , òîãäà âûïîëíÿåòñÿ ñîîòíîøåíèå
( , ( , ) ) ( , ( , ) ( , ) )x S c x c b S c k S c km m� � � �� �2 1 1 2� �
� ,
ãäå äëÿ âåêòîðîâ v v v vn� ( , , , )1 2 � , w w w w Rn
n� �( , , , )1 2 � ÷åðåç v w� îáîçíà÷å-
íà èõ âåêòîðíàÿ ñóììà, à v w v w v w v wn n
� ( , , , )1 1 2 2 � . Êàê îáû÷íî, âûâîäîì íà-
çûâàåì ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ ìíîæåñòâà R V Rn n� � �
�( ( ) ) , ïîñëåäîâà-
òåëüíî ñâÿçàííûõ îòíîøåíèåì âûâîäèìîñòè. Çàìåòèì, ÷òî äàëåå ðàññìàòðèâàþò-
ñÿ êàê êîíå÷íûå, òàê è áåñêîíå÷íûå âûâîäû.
Áóäåì ãîâîðèòü, ÷òî áåñêîíå÷íûé âûâîä ( , ) ( , )z z0 0 1 1� �� ��
� �� � �� �( , ) ( , )z zi i i i� �1 1 ñõîäèòñÿ ê òî÷êå z, åñëè ñóùåñòâóåò ïðåäåë (çäåñü
è äàëåå ðàññìàòðèâàþòñÿ òîëüêî êîíå÷íûå ïðåäåëû) ïîñëåäîâàòåëüíîñòè { }zi i N� è
îí ðàâåí z. Îáîçíà÷èì êàê a n( ) n-ìåðíûé âåêòîð ( , , , )a a a R n
� � . Ââåäåì S G( ) —
ìíîæåñòâî òî÷åê, ïîðîæäàåìûõ R-ñèñòåìîé G:
S G z R n( ) { |� � ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü { }zi i N� òî÷åê ìíîæåñòâà R n ,
ñõîäÿùàÿñÿ ê òî÷êå z, è ïîñëåäîâàòåëüíîñòü { }� i i N� òàêèå, ÷òî
( , ) ( , ( , ))( ) ( )z Sn n
0 0 00 1� � è äëÿ âñåõ íàòóðàëüíûõ i âûïîëíåíî
( , ) ( , )}z zi i i i� �� � �1 1 .
Åñëè M S G� ( ) , òî áóäåì ãîâîðèòü, ÷òî R-ñèñòåìà G ïîðîæäàåò, èëè çàäàåò,
ìíîæåñòâî M. Äâå R-ñèñòåìû ýêâèâàëåíòíû, åñëè îíè çàäàþò îäíî è òî æå ìíîæåñ-
òâî. R-ñèñòåìû, çàäàþùèå ïóñòîå ìíîæåñòâî, íàçîâåì òðèâèàëüíûìè. Òðèâèàëüíûå
R-ñèñòåìû îñîáîãî èíòåðåñà íå ïðåäñòàâëÿþò, ïîýòîìó â äàëüíåéøåì èõ ðàññìàò-
ðèâàòü íå áóäåì. Íåòðèâèàëüíóþ R-ñèñòåìó G, âñå ïðîäóêöèè êîòîðîé èìåþò âèä
S � �, ãäå S V� , � � � �B V R n( ( ) ), íàçîâåì ëèíåéíîé. Íåòðèâèàëüíûå R-ñèñòåìû,
âñå êîýôôèöèåíòû ñæàòèÿ êîòîðûõ ìåíüøå 1, íàçîâåì îãðàíè÷åííûìè.
Ïî àíàëîãèè ñ êîíòåêñòíî-ñâîáîäíûìè ãðàììàòèêàìè íåòåðìèíàëû åñòåñòâåííûì
îáðàçîì ìîæíî êëàññèôèöèðîâàòü êàê òóïèêîâûå, íåäîñòèæèìûå è ïðîäóêòèâíûå; ñî-
îòâåòñòâóþùèå ìíîæåñòâà íåòåðìèíàëîâ ýôôåêòèâíî ñòðîÿòñÿ ïî R-ñèñòåìå. Óäàëèâ
èç ìíîæåñòâà íåòåðìèíàëîâ ëèíåéíîé R-ñèñòåìû âñå íåïðîäóêòèâíûå íåòåðìèíàëû
(èç ìíîæåñòâà ïðîäóêöèé — âñå ïðîäóêöèè, èõ ñîäåðæàùèå), ïîëó÷èì ýêâèâàëåíòíóþ
ëèíåéíóþ R-ñèñòåìó. Ïîñêîëüêó óêàçàííîå ïðåîáðàçîâàíèå ñîõðàíÿåò ñâîéñòâî îãðà-
íè÷åííîñòè, áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî ðàññìàòðèâàåìûå äàëåå
ëèíåéíûå R-ñèñòåìû íå ñîäåðæàò íåïðîäóêòèâíûõ íåòåðìèíàëîâ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 43
 êà÷åñòâå ïðîñòåéøåãî ïðèìåðà ðàññìîòðèì ïîñòðîåíèå R-ñèñòåì, çàäàþùèõ
ñàëôåòêó Ñåðïèíñêîãî S A A A( , , )1 2 3 , îñíîâàííóþ íà òðåóãîëüíèêå � A A A1 2 3, , ,
ãäå A x yi i i� ( , ) , i � 1 2 3, , . Ìíîæåñòâî S A A A( , , )1 2 3 ìîæåò áûòü çàäàíî ñëåäóþ-
ùèì îáðàçîì. Ñíà÷àëà èç � A A A1 2 3, , óäàëèì âíóòðåííèé òðåóãîëüíèê, îáðàçîâàí-
íûé ñåðåäèíàìè ñòîðîí; äàëåå àíàëîãè÷íóþ ïðîöåäóðó ïðèìåíèì ê êàæäîìó èç òðåõ
îáðàçîâàâøèõñÿ òðåóãîëüíèêîâ è ò.ä. Ìíîæåñòâî S A A A( , , )1 2 3 — ýòî ìíîæåñòâî
òî÷åê òðåóãîëüíèêà � A A A1 2 3, , , êîòîðûå íå áóäóò óäàëåíû óêàçàííîé ïðîöåäóðîé.
Ñóùåñòâóþò ðàçëè÷íûå ñòðàòåãèè ïîñòðîåíèÿ R-ñèñòåìû äëÿ S A A A( , , )1 2 3 . Íàïðè-
ìåð, ïåðåéäÿ íà ïåðâîì øàãå âûâîäà â îäíó èç âåðøèí òðåóãîëüíèêà, äàëåå ìîæíî
ïîñòåïåííî óòî÷íÿòü êîîðäèíàòû, äâèãàÿñü ê îäíîé èç âåðøèí ìåíüøèõ òðåóãîëüíè-
êîâ, èëè, èíà÷å, â ïðîöåññå âûâîäà äâèãàòüñÿ ïî öåíòðàì ìàññ òðåóãîëüíèêîâ. Îïè-
ñàííûå ïîäõîäû ðåàëèçîâàíû â R-ñèñòåìàõ G1 è G2 , êîòîðûå çàäàþò ñàëôåòêó
S A A A( , , )1 2 3 :
�
G S S b b b b P S1 0 0 1 2 3 1 02� ,{ , },{ , , , }, , ,
ãäå
b x y b x x y yi i i0 1 1 1 1� � � �( , ), ( , ), i � 1 2 3, , ,
� � � �P S b S k S b S k i ki1 0 0 1 2 3 1 2 1 2� � � � � �( , ) ( , ) | , , , ( / , / );
G S S b b b b P S2 0 0 1 2 3 2 02� ( ,{ , },{ , , , }, , ),
ãäå
b x x x y y y0 1 2 3 1 2 33 3� � � � �(( ) / , ( ) / ),
b x x x x y y y y
i i i� � � � � � �( ( ) / , ( ) / )1 2 3 1 2 33 3 , i � 1 2 3, , ,
� � � �P S b S k S b S k i ki2 0 0 1 2 3 1 2 1 2� � � � � �( , ) ( , ) | , , , ( / , / ).
Àíàëîãè÷íî ìîãóò áûòü ïîñòðîåíû R-ñèñòåìû äëÿ êîâðà Ñåðïèíñêîãî è ãóáêè
Ìåíãåðà.
Ðàññìîòðèì åùå îäèí ïðèìåð, êîòîðûé áîëåå ïîëíî ðàñêðûâàåò ñóòü è âîç-
ìîæíîñòè R-ñèñòåì. Ïðåäâàðèòåëüíî ââåäåì ïðåîáðàçîâàíèÿ w w w3 4 5, , îòðåçêîâ;
ïðåîáðàçîâàíèå wi (i � 3 4 5, , ) äåëèò îòðåçîê íà i ðàâíûõ ÷àñòåé è óäàëÿåò èíòåðâàë,
ñîñòîÿùèé èç (i � 2) ñðåäíèõ ÷àñòåé, ò.å. îñòàþòñÿ òîëüêî äâà êðàéíèõ îòðåçêà ðàç-
áèåíèÿ. Òåïåðü ïîñòðîèì ìíîæåñòâî C1: ñíà÷àëà ê îòðåçêó [ ; ]0 1 ïðèìåíèì ïðåîáðà-
çîâàíèå w3 (ýòîò øàã àíàëîãè÷åí ïîñòðîåíèþ ìíîæåñòâà Êàíòîðà); äàëåå ê ëåâîìó
îñòàâøåìóñÿ îòðåçêó ïðèìåíèì ïðåîáðàçîâàíèå w4 , à ê ïðàâîìó — w5 . Íà êàæäîì
ñëåäóþùåì øàãå ê ëåâîìó îòðåçêó, ïîëó÷åííîìó â ðåçóëüòàòå ïðåîáðàçîâàíèÿ wi ,
ïðèìåíÿåì ïðåîáðàçîâàíèå w i3 1 3� �(( ) mod ) , à ê ïðàâîìó — ïðåîáðàçîâàíèå
w i3 2 3� �(( ) mod ) . Ìíîæåñòâî C1 ñîñòîèò èç òåõ è òîëüêî òåõ òî÷åê îòðåçêà [ ; ]0 1, êîòî-
ðûå íå áóäóò óäàëåíû óêàçàííîé ïðîöåäóðîé, è ìîæåò áûòü çàäàíî R-ñèñòåìîé G3 :
G S S S b b b b P S3 3 4 5 0 3 4 5 3 31� ( ,{ , , },{ , , , }, , ),
ãäå
b b i ii0 0 1 3 4 5� � �, / , , , ;
�P S b S b S
3 3 0 4 3 51 3 1 3� � ( , / ) | ( , / ) ,
�S b S b S S b S b S4 0 5 4 3 5 0 3 5 41 4 1 4 1 5 1 5� �( , / ) | ( , / ), ( , / ) | ( , / ) .
ÄÅÐÅÂÎ ÂÛ×ÈÑËÅÍÈÉ ËÈÍÅÉÍÎÉ R-ÑÈÑÒÅÌÛ
Ðàññìîòðèì ëèíåéíóþ R-ñèñòåìó G n V B P S� ( , , , , )0 . Ïóñòü S b S ki i i� ( , ),
i k�0, , — âñå ïðîäóêöèè ìíîæåñòâà P, ñîäåðæàùèå íåòåðìèíàë S â ëåâîé ÷àñòè.
Òàêèì îáðàçîì, ïðîíóìåðîâàíû âñå ïðîäóêöèè íåòåðìèíàëà S . Ïóñòü pS i,
—
ïðîäóêöèÿ íåòåðìèíàëà S ñ íîìåðîì i. Àíàëîãè÷íóþ îïåðàöèþ ïðîâåäåì äëÿ
âñåõ íåòåðìèíàëîâ R-ñèñòåìû. Ïóñòü m — ìàêñèìàëüíîå êîëè÷åñòâî ïðîäóêöèé
44 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
ñ îäèíàêîâîé ëåâîé ÷àñòüþ. Äåðåâîì âû÷èñëåíèé ëèíåéíîé R-ñèñòåìû íàçîâåì
ðàçìåòêó � äåðåâà T mm � �{ , , , } ,*0 1 1� óäîâëåòâîðÿþùóþ ñëåäóþùèì óñëîâèÿì:
1) � ÿâëÿåòñÿ îòîáðàæåíèåì èç Tm â { } ( ( ))� � � �R V Rn n , ãäå ñèìâîë � ñîîò-
âåòñòâóåò ïóñòîé ìåòêå;
2) ���
�� � n nS, ( , )( )
0 1 ;
3) åñëè � �( )w � , òî � �( )wi � äëÿ âñåõ i m w Tm� � �0 1, , ;
4) åñëè �( ) ( , ( , ))w x S k� è pS i,
— ïðîäóêöèÿ íåòåðìèíàëà S ñ íîìåðîì i, òî
�( )wi ÿâëÿåòñÿ ðåçóëüòàòîì ïðèìåíåíèÿ ê ( , ( , ))x S k ïðîäóêöèè pS i,
, ò.å.
� �( ) ( )
,
w wi
p
S i
� ;
5) åñëè �( ) ( , ( , ))w x S k� è ïðîäóêöèè pS i,
ñ íîìåðîì i m� �0 1, äëÿ íåòåðìè-
íàëà S íå ñóùåñòâóåò, òî � �( )wi � , w Tm� .
 äàëüíåéøåì, ãîâîðÿ î âåòâÿõ â äåðåâå âû÷èñëåíèé, áóäåì èìåòü â âèäó ïóòè
â äåðåâå, èäóùèå â íàïðàâëåíèè óäàëåíèÿ îò êîðíÿ è íå ñîäåðæàùèå âåðøèí ñ ïóñ-
òûìè ìåòêàìè. Òàêèì îáðàçîì, êàæäàÿ êîíå÷íàÿ èëè áåñêîíå÷íàÿ âåòâü çàäàåò íå-
êîòîðûé âûâîä. Ïîä êîðíåâîé âåòâüþ ïîíèìàåì âåòâü, èñõîäÿùóþ íåïîñðåäñòâåí-
íî èç êîðíÿ.
Îòìåòèì, ÷òî ìåæäó áåñêîíå÷íûìè êîðíåâûìè âåòâÿìè äåðåâà è áåñêîíå÷íû-
ìè âûâîäàìè èç íà÷àëüíîãî íåòåðìèíàëà â R-ñèñòåìå ñóùåñòâóåò âçàèìíî îäíî-
çíà÷íîå ñîîòâåòñòâèå. Ïîñêîëüêó âñå òî÷êè ìíîæåñòâà S G( ) ñîîòâåòñòâóþò áåñêî-
íå÷íûì âûâîäàì (íî, âîçìîæíî, íå êàæäûé áåñêîíå÷íûé âûâîä ñîîòâåòñòâóåò òî÷-
êå!), êàæäîé òî÷êå z S G� ( ) ìîæíî ïîñòàâèòü â ñîîòâåòñòâèå íåêîòîðóþ
áåñêîíå÷íóþ êîðíåâóþ âåòâü � � � �0 1 1, , , , ,� �i i� òàêóþ, ÷òî z
i
i�
�
lim Pr ( )1 � � .
 òî æå âðåìÿ, åñëè z
i
i�
�
lim Pr ( )1 � � , òî z S G� ( ) ïî îïðåäåëåíèþ. Ïðè ýòîì, âîç-
ìîæíî, ðàçëè÷íûå âåòâè ñîîòâåòñòâóþò îäíîé è òîé æå òî÷êå.
Çàìåòèì, ÷òî ðàçëè÷íûå ïîðÿäêè íà ìíîæåñòâàõ ïðîäóêöèé íåòåðìèíàëîâ ïî-
çâîëÿþò ïîëó÷àòü ðàçëè÷íûå, íî èçîìîðôíûå äåðåâüÿ âû÷èñëåíèé.
ÑÂÎÉÑÒÂÀ ÎÃÐÀÍÈ×ÅÍÍÛÕ ËÈÍÅÉÍÛÕ R-ÑÈÑÒÅÌ
Ïðèâåäåííûå â äàííîì ðàçäåëå òåîðåìû ÿâëÿþòñÿ àíàëîãàìè òåîðåì îá îãðàíè-
÷åííîñòè è çàìêíóòîñòè àòòðàêòîðà IFS [1]. Ñíà÷àëà äîêàæåì âñïîìîãàòåëüíóþ
ëåììó.
Ëåììà 1. Äëÿ îãðàíè÷åííîé ëèíåéíîé R-ñèñòåìû ñóùåñòâóþò äåéñòâèòåëüíûå
÷èñëà c lb, òàêèå, ÷òî äëÿ êàæäîé áåñêîíå÷íîé êîðíåâîé âåòâè � � � �0 1 1, , , , ,� �i i�
äåðåâà âû÷èñëåíèé ñóùåñòâóåò ïðåäåë z S G
i
i� �
�
lim Pr ( ) ( )1 � � , ïðè÷åì
� �(Pr ( ) , )1
1
i
i
bz
c
c
l�
�
äëÿ âñåõ i N� .
Äîêàçàòåëüñòâî. Ïóñòü c — ìàêñèìàëüíûé êîýôôèöèåíò ñæàòèÿ R-ñèñòåìû,
à lb — ìàêñèìàëüíàÿ äëèíà âåêòîðîâ ìíîæåñòâà B. Èñõîäÿ èç êîíå÷íîé îïðåäåëåí-
íîñòè è îãðàíè÷åííîñòè R-ñèñòåìû, âåëè÷èíû c è lb îïðåäåëåíû êîððåêòíî, ïðè÷åì
c � ( ; )0 1 .
Ïåðåéäåì íåïîñðåäñòâåííî ê ðàññìîòðåíèþ âåòâè äåðåâà. Ïóñòü
� �( ) ( , ( , ( , , , ))), , ,i i i i i i nx S k k k� 1 2 � , i N� . Ñíà÷àëà îöåíèì âåêòîð êîýôôèöèåíòîâ
( , , , ), , ,k k ki i i n1 2 � . Ïîñêîëüêó ( , , , ), , ,
( )k k k n
n
0 1 0 2 0 1� � è êîýôôèöèåíòû ñæàòèÿ íå
ïðåâûøàþò c, äëÿ âñåõ êîýôôèöèåíòîâ ki j, , i N� , j n�1, , âûïîëíåíà îöåíêà
0 � �k ci j
i
, .
Îöåíèì ðàññòîÿíèå
( , )x xi i�1 ìåæäó òî÷êàìè x x x xi i i i n� ( , , , ), , ,1 2 � è
x x x xi i i i n� � � ��1 1 1 1 2 1( , , , ), , ,� . Ïóñòü ïðè ïåðåõîäå îò âåðøèíû äåðåâà � i ê âåðøè-
íå � i�1 ïðèìåíÿëàñü ïðîäóêöèÿ S b b b S k k ki n i n� �( , , , )( , ( , , , ))1 2 1 1 2� � . Ñîãëàñ-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 45
íî ââåäåííûì îïðåäåëåíèÿì âûïîëíÿåòñÿ ñîîòíîøåíèå x x k bi j i j i j j� � �1, , , ,
j n�1, . Òîãäà ðàññòîÿíèå ìîæíî îöåíèòü ñëåäóþùèì îáðàçîì:
( , ) ( ) ( ) ( ),x x k b c b c bi i i j j
j
n
i
j
j
n
i
j
j
n
�
� � �
� � �� �1
2
1
2
1
2
1
� � c li
b .
Ñ ó÷åòîì íåðàâåíñòâà òðåóãîëüíèêà äëÿ t N� âûïîëíåíî
( , ) ( , ) ( , ) ( ,x x x x x x x xi i t i i i i i t i t� � � � � � �� � � �1 1 2 1� ) �
� � � � �
�
� � �( )c c c l
c
c
li i i t
b
i
b
1 1
1
� .
(1)
Ïîñêîëüêó âåëè÷èíà
c
c
l
i
b
1�
ñ ðîñòîì i ñòðåìèòñÿ ê íóëþ, ïîñëåäîâàòåëüíîñòü
{ }xi i N� ÿâëÿåòñÿ ôóíäàìåíòàëüíîé, à çíà÷èò, ñõîäÿùåéñÿ. Ñëåäîâàòåëüíî, ñóùåñ-
òâóåò êîíå÷íûé ïðåäåë z S G
i
i� �
�
lim Pr ( ) ( )1 � � . Ïåðåõîäÿ â îöåíêå (1) ê ïðåäå-
ëó ïðè t � , ïîëó÷àåì
� �
(Pr ( ), ) ( , )1
1
i i
i
bz x z
c
c
l� �
�
. Ëåììà äîêàçàíà.
Òåîðåìà 1. Äëÿ îãðàíè÷åííîé ëèíåéíîé R-ñèñòåìû G n V B P S� ( , , , , )0 ìíîæåñ-
òâî S G( ) îãðàíè÷åíî.
Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ äëÿ êîðíÿ �0 äåðåâà âû÷èñëåíèé
Pr ( ) ( )
1 0 0� � � n . Òîãäà ïî ëåììå 1 ñëåäóåò, ÷òî ñóùåñòâóþò äåéñòâèòåëüíûå ÷èñëà
c, lb òàêèå, ÷òî äëÿ êàæäîé òî÷êè z S G� ( ) âûïîëíåíî
( , )( )0
1
1
n
bz
c
l�
�
, ò.å. ìíî-
æåñòâî S G( ) îãðàíè÷åíî.
Òåîðåìà äîêàçàíà.
Ñëåäóåò îòìåòèòü, ÷òî R-ñèñòåìû, íå ÿâëÿþùèåñÿ îãðàíè÷åííûìè, ìîãóò çàäà-
âàòü êàê îãðàíè÷åííûå, òàê è íåîãðàíè÷åííûå ìíîæåñòâà.
Òåîðåìà 2. Äëÿ îãðàíè÷åííîé ëèíåéíîé R-ñèñòåìû G n V B P S� ( , , , , )0 ìíî-
æåñòâî S G( ) çàìêíóòî.
Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèçâîëüíóþ ïðåäåëüíóþ òî÷êó z ìíîæåñòâà
S G( ). Ïóñòü ïîñëåäîâàòåëüíîñòü òî÷åê { }z j j N� , z S Gj � ( ), ñõîäèòñÿ ê òî÷êå z, ò.å.
z z
j
j�
�
lim . Ïîêàæåì, ÷òî â ñëó÷àå îãðàíè÷åííîé ëèíåéíîé ñèñòåìû z S G� ( ).
Åñëè òî÷êà z âõîäèò â äàííóþ ïîñëåäîâàòåëüíîñòü, òî z S G� ( ). Ðàññìîòðèì
òîò ñëó÷àé, êîãäà òî÷êà z íå âõîäèò â ïîñëåäîâàòåëüíîñòü.
 äåðåâå âû÷èñëåíèé � äàííîé R-ñèñòåìû êàæäîé òî÷êå z j ïîñòàâèì â ñîîò-
âåòñòâèå áåñêîíå÷íóþ êîðíåâóþ âåòâü � � � �j j j i j i, , , ,, , , , ,0 1 1� �� òàêóþ, ÷òî
z j
i
j i
�
�
lim Pr ( )
,1 � � . Òàêèå âåòâè íàçîâåì îòìå÷åííûìè. Çàìåòèì, ÷òî ìíîæåñòâî
îòìå÷åííûõ âåòâåé áåñêîíå÷íî, ïîñêîëüêó áåñêîíå÷íî ìíîæåñòâî ðàçëè÷íûõ òî÷åê
ïîñëåäîâàòåëüíîñòè { }z j j N� .
Ðàññìîòðèì ìíîæåñòâî BR âñåõ êîðíåâûõ âåòâåé (êîíå÷íûõ è áåñêîíå÷íûõ),
÷åðåç êàæäóþ âåðøèíó êîòîðûõ ïðîõîäèò áåñêîíå÷íîå ìíîæåñòâî îòìå÷åííûõ âåò-
âåé, è ïîêàæåì, ÷òî îíî ñîäåðæèò õîòÿ áû îäíó áåñêîíå÷íóþ âåòâü.
Îòìå÷åííûõ âåòâåé áåñêîíå÷íî ìíîãî, è âñå îíè âûõîäÿò èç êîðíÿ, ïîýòîìó
âåòâü, ñîñòîÿùàÿ èç åäèíñòâåííîé âåðøèíû � �0 � , ïðèíàäëåæèò ìíîæåñòâó BR.
Òàêèì îáðàçîì, ìíîæåñòâî BR íå ïóñòî. Ïóñòü îíî ñîäåðæèò íåêîòîðóþ âåòâü
� � �0 1, , ,� t . Âåðøèíà � t èìååò êîíå÷íîå âåòâëåíèå è ÷åðåç íåå ïðîõîäèò áåñêî-
íå÷íî ìíîãî îòìå÷åííûõ âåòâåé. Ïîýòîìó äëÿ íåêîòîðîãî a mt� � �1 0 1, ÷åðåç âåð-
øèíó � t ta �1 òàêæå ïðîõîäèò áåñêîíå÷íî ìíîãî îòìå÷åííûõ âåòâåé. Ïîñëåäíåå
îçíà÷àåò, ÷òî â ìíîæåñòâå BR äëÿ êàæäîé êîíå÷íîé âåòâè ñóùåñòâóåò áîëåå äëèí-
íàÿ, ñòðîãî ñîäåðæàùàÿ äàííóþ. Ñëåäîâàòåëüíî, ìíîæåñòâî BR ñîäåðæèò õîòÿ áû
îäíó áåñêîíå÷íóþ âåòâü, íàïðèìåð � � � � �� �( , , , , , )0 1 1� �i i .
46 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
Äëÿ äîêàçàòåëüñòâà òîãî, ÷òî z S G� ( ), äîñòàòî÷íî ïîêàçàòü, ÷òî
z
i
i�
�
lim Pr ( )
1
� � . Ïîëîæèì i0 0� . Äëÿ âåðøèíû �0 çàôèêñèðóåì ïðîõîäÿùóþ ÷å-
ðåç íåå îòìå÷åííóþ âåòâü, îòëè÷íóþ îò âåòâè �. Ïóñòü äàííîé âåòâè ñîîòâåòñòâóåò
òî÷êà z j0
. Äàëåå, äëÿ êàæäîé âåðøèíû � i�1 çàôèêñèðóåì îòìå÷åííóþ âåòâü, êîòî-
ðàÿ ïðîõîäèò ÷åðåç � i�1 è ñîîòâåòñòâóåò òî÷êå z ji� 1
, ïðè÷åì j ji i� �1. Ïîñêîëüêó
÷èñëî ji êîíå÷íî è ÷åðåç êàæäóþ âåðøèíó � i�1 ïðîõîäèò áåñêîíå÷íî ìíîãî îòìå-
÷åííûõ âåòâåé, äàííûé âûáîð îñóùåñòâèì.  ðåçóëüòàòå ïîëó÷èì áåñêîíå÷íóþ
ïîäïîñëåäîâàòåëüíîñòü { }z j i Ni � èñõîäíîé ñõîäÿùåéñÿ ïîñëåäîâàòåëüíîñòè, ïîýòî-
ìó lim lim
i j j
jz z z
i� �
� � .
Èç ëåììû 1 ñëåäóåò, ÷òî ñóùåñòâóåò êîíå÷íûé ïðåäåë lim Pr ( )
i
i
�
1 � � è äåéñòâè-
òåëüíûå ÷èñëà c � ( ; )0 1 , lb òàêèå, ÷òî
� ��( Pr ( ), )1
1
z
c
c
lj
i
bi
�
�
. Ïåðåõîäÿ â ïîñëåä-
íåì íåðàâåíñòâå ê ïðåäåëó ïðè i � , ïîëó÷àåì, ÷òî lim Pr ( )
i
i
�
�1 � � lim
i j
z z
i�
� è
z S G� ( ) ïî îïðåäåëåíèþ.
Òåîðåìà äîêàçàíà.
Èç äîêàçàííîé òåîðåìû, â ÷àñòíîñòè, ñëåäóåò, ÷òî ìíîæåñòâî äâîè÷íî-ðàöèî-
íàëüíûõ ÷èñåë îòðåçêà [ ; ]0 1 è ìíîæåñòâî ðàöèîíàëüíûõ ÷èñåë îòðåçêà [ ; ]0 1 íå ìî-
ãóò áûòü çàäàíû îãðàíè÷åííûìè ëèíåéíûìè R-ñèñòåìàìè, ïîñêîëüêó ñîäåðæàò íå
âñå ñâîè ïðåäåëüíûå òî÷êè.
Ìíîæåñòâî, çàäàâàåìîå R-ñèñòåìîé, ìîæåò áûòü êîíå÷íûì, ñ÷åòíûì èëè êîí-
òèíóàëüíûì.  îáùåì ñëó÷àå ìíîæåñòâî, çàäàâàåìîå R-ñèñòåìîé, ìîæåò íå áûòü
îãðàíè÷åííûì è/èëè ñâÿçíûì.
R-ÑÈÑÒÅÌÛ È R
*-ÏÐÅÎÁÐÀÇÎÂÀÒÅËÈ
Íàðÿäó ñ R-ïðåîáðàçîâàòåëÿìè â [8] ðàññìîòðåíû R*-ïðåîáðàçîâàòåëè, ÿâëÿþùè-
åñÿ îáîáùåíèåì ïåðâûõ. Îñíîâíîå îòëè÷èå R*-ïðåîáðàçîâàòåëÿ çàêëþ÷àåòñÿ â
òîì, ÷òî, ïîëó÷èâ íà âõîä çàïèñü ÷èñëà â ïîçèöèîííîé ñèñòåìå ñ÷èñëåíèÿ, ãäå
âåñ êàæäîé öèôðû îïðåäåëÿåòñÿ åå ðàñïîëîæåíèåì îòíîñèòåëüíî òî÷êè, íà
âûõîä îí âûäàåò íåêîòîðóþ «çàïèñü» ÷èñëà, â êîòîðîé êàæäîé «öèôðå» ñîîò-
âåòñòâóåò ñîáñòâåííûé «âåñ». Ïðè ýòîì â êà÷åñòâå öèôð è âåñîâ ðàçðåøàåòñÿ
èñïîëüçîâàòü íå òîëüêî öåëûå è ðàöèîíàëüíûå, íî è âñå äåéñòâèòåëüíûå ÷èñëà.
Åäèíñòâåííîå îãðàíè÷åíèå — âñå âåñà äîëæíû áûòü ïîëîæèòåëüíû.
Íàïîìíèì, ÷òî íà âõîä R n( )* -ïðåîáðàçîâàòåëü ïîëó÷àåò �-ñëîâî
w a a a a am m� �� � �1 0 1 2� � èç ìíîæåñòâà D � � � � �({ } { , } ) { , } ({ }*0 1 01 0 1 0�
� �1 0 1 0 1{ , } ) { , }* � , ïðåäñòàâëÿþùåå ñîáîé äâîè÷íóþ çàïèñü ÷èñëà
a a a a a am m i
i
i
m
� � �
��
� �
�1 0 1 2 2� � . R n( )* -ïðåîáðàçîâàòåëü A çàäàåò ôóíêöèþ
fA òèïà D R n� , êîòîðîé ñòàâèòñÿ â ñîîòâåòñòâèå ôóíêöèÿ äåéñòâèòåëüíîãî àðãó-
ìåíòà
~
fA òèïà R R n� , ãäå
~
( ) ( )f x f wA A x� ïðè w Dx � � �\ ({ , , , } ({ } { } ))*0 1 1 1 1� � ,
w xx � . Äëÿ ÷èñåë èç [ ; ]0 1 îäíîâðåìåííî ñ ïðåäñòàâëåíèÿìè èç ìíîæåñòâà D ðàñ-
ñìîòðèì ïðåäñòàâëåíèÿ èç ìíîæåñòâà �{ , }0 1 � è åñòåñòâåííûì îáðàçîì ïðîäîëæèì
ôóíêöèþ f
A
íà ìíîæåñòâî �{ , }0 1 � . Ôóíêöèè f
A
äîïîëíèòåëüíî ïîñòàâèì â ñîîò-
âåòñòâèå ôóíêöèþ
�
fA òèïà [ ; ]0 1 � R n , ãäå
�
f x f wA A x( ) ( )� ïðè wx �� �{ }1 �
� � �( { , } \ ( { , } { } ))*0 1 01 1� � , w xx � . Íàçîâåì R n( )* -ïðåîáðàçîâàòåëü A òðèâèàëüíûì,
åñëè íà �{ , }0 1 � ôóíêöèÿ fA âñþäó íå îïðåäåëåíà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 47
Êàê áóäåò äîêàçàíî â ñëåäóþùåé òåîðåìå, êàæäîå ìíîæåñòâî, çàäàâàåìîå ëè-
íåéíîé R-ñèñòåìîé, ñîâïàäàåò ñî ìíîæåñòâîì äåéñòâèòåëüíûõ âåêòîðîâ, êîòîðûå
ÿâëÿþòñÿ ýëåìåíòàìè èç îáëàñòè çíà÷åíèé ôóíêöèè f
A
ïðè àðãóìåíòàõ èç ìíîæåñ-
òâà �{ , }0 1 � äëÿ íåêîòîðîãî íåòðèâèàëüíîãî R n( )* -ïðåîáðàçîâàòåëÿ A.
Òåîðåìà 3. Ïî ëèíåéíîé R-ñèñòåìå G n V B P S� ( , , , , )0 ìîæíî ïîñòðîèòü êîíå÷-
íûé íåòðèâèàëüíûé R n( )* -ïðåîáðàçîâàòåëü A K H q� ( , , )0 òàêîé, ÷òî
S G f fA A( ) ( { , } ) ([ ; ])� � �0 1 0 1� �
è ôóíêöèÿ f
A
âñþäó îïðåäåëåíà íà �{ , }0 1 � .
Äîêàçàòåëüñòâî. Áåç îãðàíè÷åíèÿ îáùíîñòè ìîæíî ñ÷èòàòü, ÷òî âñå íåòåðìè-
íàëû R-ñèñòåìû G ïðîäóêòèâíû è q V0 � . Ïóñòü S b S ki i i� ( , ), i k�0, , — âñå ïðî-
äóêöèè ìíîæåñòâà P, ñîäåðæàùèå íåòåðìèíàë S â ëåâîé ÷àñòè, è pS i, — ïðîäóêöèÿ
íåòåðìèíàëà S ñ íîìåðîì i.
Ïóñòü m — ìàêñèìàëüíîå êîëè÷åñòâî ïðîäóêöèé ñ îäèíàêîâîé ëåâîé ÷àñòüþ è
÷èñëî t N� òàêîâî, ÷òî t � 2 è m t� �2 2.
Ìíîæåñòâî êîìàíä HS ïðåîáðàçîâàòåëÿ îïðåäåëèì òàê, ÷òîáû â ñîñòîÿíèè S
ïðåîáðàçîâàòåëü ñíà÷àëà ñ÷èòûâàë t ñèìâîëîâ äðîáíîé ÷àñòè, ïóñòü ýòî ñëîâî
� �{ , }0 1 t , à çàòåì ìîäåëèðîâàë ïðèìåíåíèå ïðîäóêöèè p
S , � (åñëè êîëè÷åñòâî ïðî-
äóêöèé ñ íåòåðìèíàëîì S â ëåâîé ÷àñòè ìåíüøå � � 1, ïðèìåì p p
S S, ,� � 0 ):
H S a S a S V aS
n n t� � � � ��
�
�
�� �( , ) ( , ) | , { , }, { , }( )� � �0 1 01 0 1 2
�
�
�
� ( , ) | { , }, { , } , ( )S a a p St
a
� � � �
�
� � � � ��
�
�
�
�
�
�01 0 1 1 ,
K q V t� � � � �{ } ( { , } )0
10 1 ,
H q S Hn n
S
S V
� � �� �
�
{ }( ) ( )
0 0 1 � ,
ãäå ��t îáîçíà÷àåò ìíîæåñòâî ñëîâ â àëôàâèòå � äëèíû íå áîëåå t.
Èñõîäÿ èç ñïîñîáà ïîñòðîåíèÿ, êàæäûé áåñêîíå÷íûé âûâîä òî÷êè z S G� ( )
ñîîòâåòñòâóåò ðàáîòå ïîñòðîåííîãî R n( )* -ïðåîáðàçîâàòåëÿ íà íåêîòîðîì �-ñëîâå èç
�{ , }0 1 � , êîòîðîå îäíîçíà÷íî âîññòàíàâëèâàåòñÿ ïî ïîñëåäîâàòåëüíîñòè
ïðèìåíÿåìûõ ïðîäóêöèé. Êðîìå òîãî, êàæäîìó áåñêîíå÷íîìó âû÷èñëåíèþ
R n( )* -ïðåîáðàçîâàòåëÿ íàä �-ñëîâîì èç �{ , }0 1 � ñîîòâåòñòâóåò íåêîòîðûé
áåñêîíå÷íûé âûâîä â R-ñèñòåìå, ïðè÷åì åñëè ðåçóëüòàò ðàáîòû ïðåîáðàçîâàòåëÿ
ÿâëÿåòñÿ ïðåäñòàâëåíèåì äåéñòâèòåëüíîãî âåêòîðà z (èìååòñÿ â âèäó, ÷òî âñå
êîîðäèíàòû âåêòîðà êîíå÷íû), òî ýòîò æå âåêòîð ÿâëÿåòñÿ ðåçóëüòàòîì âûâîäà
â R-ñèñòåìå. Òàêèì îáðàçîì, óêàçàííûå â ôîðìóëèðîâêå òåîðåìû ìíîæåñòâà
ñîâïàäàþò. Ïîñêîëüêó âñå íåòåðìèíàëû ïðîäóêòèâíû, êàæäûé êîíå÷íûé âûâîä
â R-ñèñòåìå ìîæåò áûòü ïðîäîëæåí äî áåñêîíå÷íîãî, à çíà÷èò, ôóíêöèÿ f
A
âñþäó
îïðåäåëåíà íà �{ , }0 1 � .
Òåîðåìà äîêàçàíà.
Èìååò ìåñòî è îáðàòíàÿ òåîðåìà.
Òåîðåìà 4. Ïî êîíå÷íîìó íåòðèâèàëüíîìó R n( )* -ïðåîáðàçîâàòåëþ
A K H q� ( , , )0 , åäèíñòâåííîé êîìàíäîé ïåðåõîäà êîòîðîãî èç ñîñòîÿíèÿ q0 ÿâëÿåò-
ñÿ êîìàíäà q q kn
0 1 0� � � ( ) , ìîæíî ïîñòðîèòü ëèíåéíóþ R-ñèñòåìó
G n V B P S� ( , , , , )0 òàêóþ, ÷òî S G fA( ) ( { , } )� � 0 1 � .
Äîêàçàòåëüñòâî. Ìíîæåñòâî áåñêîíå÷íûõ âûâîäîâ èñêîìîé R-ñèñòåìû äîë-
æíî ñîîòâåòñòâîâàòü ìíîæåñòâó áåñêîíå÷íûõ âû÷èñëåíèé ïðåîáðàçîâàòåëÿ íàä
48 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3
�-ñëîâàìè èç �{ , }0 1 � . Ïîýòîìó ïîñòðîèì ìíîæåñòâî ïðîäóêöèé òàê, ÷òîáû â R-ñèñ-
òåìå ìîãëî áûòü ïðîìîäåëèðîâàíî êàæäîå áåñêîíå÷íîå âû÷èñëåíèå. Ïîëîæèì
V K S q� �, 0 0 ,
B b qa bpk Hn� � � �{ } { |( ) }( )0 ,
� �P q b p k qa bpk H a q q kn� � � � � � �( , ) | ( ) , { , } { ( , )}( )0 1 00 1 0 .
Èç ñïîñîáà ïîñòðîåíèÿ ñëåäóåò, ÷òî óêàçàííàÿ R-ñèñòåìà ÿâëÿåòñÿ èñêîìîé.
Ïî îïðåäåëåíèþ R n( )* -ïðåîáðàçîâàòåëü ïîíèìàåòñÿ êàê äåòåðìèíèðîâàííûé.
Íåäåòåðìèíèðîâàííûé àíàëîã ýòîãî óñòðîéñòâà íàçîâåì V n( )* -ïðåîáðàçîâàòåëåì,
åñëè äîïîëíèòåëüíî âûïîëíåíî óñëîâèå: îòîáðàæåíèå fA ÿâëÿåòñÿ îäíîçíà÷íûì.
Èç äîêàçàòåëüñòâà òåîðåìû 4 ïîëó÷àåì cëåäñòâèå.
Ñëåäñòâèå 1. Ïî êîíå÷íîìó íåòðèâèàëüíîìó íåäåòåðìèíèðîâàííîìó
V n( )* -ïðåîáðàçîâàòåëþ (V n( )* -ïðåîáðàçîâàòåëþ) A K H q� ( , , )0 , åäèíñòâåííîé êî-
ìàíäîé ïåðåõîäà êîòîðîãî èç ñîñòîÿíèÿ q0 ÿâëÿåòñÿ êîìàíäà q q kn
0 1 0� � � ( ) ,
ìîæíî ïîñòðîèòü ëèíåéíóþ R-ñèñòåìó G n V B P S� ( , , , , )0 òàêóþ, ÷òî
S G fA( ) ( { , } )� � 0 1 � .
 ðåçóëüòàòå èìååì ñëåäóþùóþ òåîðåìó.
Òåîðåìà 5. Äëÿ êîíå÷íîãî íåòðèâèàëüíîãî íåäåòåðìèíèðîâàííîãî
R n( )*-ïðåîáðàçîâàòåëÿ (V n( )* -ïðåîáðàçîâàòåëÿ) A K H q� ( , , )0 , åäèíñòâåííîé êî-
ìàíäîé ïåðåõîäà êîòîðîãî èç ñîñòîÿíèÿ q0 ÿâëÿåòñÿ êîìàíäà q q kn
0 1 0� � � ( ) , ñó-
ùåñòâóåò êîíå÷íûé íåòðèâèàëüíûé R n( )* -ïðåîáðàçîâàòåëü B òàêîé, ÷òî
fA ( { , } )� �0 1 � fB ( { , } )� 0 1 � .
Äëÿ äîêàçàòåëüñòâà òåîðåìû äîñòàòî÷íî ïî ïðåîáðàçîâàòåëþ A ñ ïîìîùüþ
ñëåäñòâèÿ 1 ïîñòðîèòü R-ñèñòåìó, à çàòåì, âîñïîëüçîâàâøèñü òåîðåìîé 4, ïî R-ñèñ-
òåìå ïîñòðîèòü R n( )* -ïðåîáðàçîâàòåëü B.
 îáùåì ñëó÷àå äëÿ R*-ïðåîáðàçîâàòåëÿ A èìååò ìåñòî ëèøü âêëþ÷åíèå
�
f fA A([ , ]) ( { , } )0 1 0 1� � � , ïîýòîìó ïðè âûïîëíåíèè óñëîâèÿ S G fA( ) ( { , } )� � 0 1 � ðà-
âåíñòâî S G fA( ) ([ ; ])�
�
0 1 ìîæåò íå èìåòü ìåñòà.  êà÷åñòâå ïðèìåðà ðàññìîòðèì
R-ñèñòåìó G è R*-ïðåîáðàçîâàòåëü A:
G S S S S S S S� � � �1 0 1 2 0 1 2 2 1 20 1 0 1 0 1 1,{ , },{ , , },{ ( , / ), ( , / ),�
1 1 21 0( , / )},S S ,
�
A q q q H q� { , , }, ,0 1 2 0 ,
ãäå
H q q q q q q q q q q� � � � � � � �0 1 0 2 1 2 2 2 21 0 0 1 2 1 2 1 2 0 0 1 2 1 1, / , / , / ,� �2 1 2/ .
Íåòðóäíî âèäåòü, ÷òî S G fA( ) ( { , } ) [ ; ] [ ; ]� � � �0 1 0 1 2 3� , à ôóíêöèÿ
�
fA çíà÷å-
íèå 1 íå ïðèíèìàåò.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå [9] ïîêàçàíî, ÷òî ñóùåñòâóåò íåïðåðûâíàÿ íèãäå íå äèôôåðåíöèðóåìàÿ
íà îòðåçêå [ ; ]0 1 ôóíêöèÿ, çàäàâàåìàÿ êîíå÷íûì R-ïðåîáðàçîâàòåëåì. Ïîñêîëüêó
R-ïðåîáðàçîâàòåëü ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì R*-ïðåîáðàçîâàòåëÿ, èç äîêàçàííûõ
òåîðåì ñëåäóåò, ÷òî åå ãðàôèê ìîæåò áûòü çàäàí ëèíåéíîé R-ñèñòåìîé. Êðîìå
òîãî, ñ ïîìîùüþ R-ñèñòåì ìîæíî çàäàòü ìíîæåñòâî Êàíòîðà, ñíåæèíêó Êîõ,
à òàêæå öåëûé ðÿä ãåîìåòðè÷åñêèõ ôðàêòàëîâ.
Ñ ïðîãðàììèñòñêîé òî÷êè çðåíèÿ R-ñèñòåìû ïðåäñòàâëÿþò óäîáíûé àïïàðàò ïðî-
ãðàììèðîâàíèÿ ïðèáëèæåíèé ôðàêòàëüíûõ ìíîæåñòâ. Îäíàêî, íåñìîòðÿ íà âíåø-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 3 49
íþþ ïðîñòîòó, äàæå ëèíåéíûå R-ñèñòåìû îñòàâëÿþò ðÿä íåðåøåííûõ âîïðîñîâ,
íàïðèìåð: 1) ÿâëÿåòñÿ ëè ìíîæåñòâî, çàäàâàåìîå ëèíåéíîé R-ñèñòåìîé, ñâÿçíûì;
2) êàêîâ êîýôôèöèåíò ïåðåêðûòèÿ çàäàâàåìîãî ìíîæåñòâà? Òàêæå ïðåäñòàâëÿåò èí-
òåðåñ èññëåäîâàíèå íåëèíåéíûõ R-ñèñòåì.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B a r n s l e y M . Fractals everywhere. — Boston: Acad. Press, 1988. — 394 p.
2. P e i t g e n H . - J . , J u r g e n s H . , S a u p e D . Chaos and fractals: New frontiers of science. — New
York: Springer-Verlag, 1997. — 900 p.
3. M a u l d i n D . , U r b a n s k i M . Dimensions and measures in infinite iterated function systems // Proc.
London Math. Soc. — 1996. — 73, N 3. — Ð. 105–154.
4. M a u l d i n R . D . , W i l l i a m s S . C . Hausdorff dimension in graph directed constructions // Trans.
Amer. Math. Soc. — 1988. — 309, N 2. — P. 811–829.
5. C u l i k I I K . , K a r h u m a k i J . Finite automata, computing real functions // Siam J. Comput. — 1994.
— 23, N 4. — P. 789–814.
6. Ë è ñ î â è ê Ë . Ï . Ïðèìåíåíèÿ êîíå÷íûõ ïðåîáðàçîâàòåëåé äëÿ çàäàíèÿ ôðàêòàëüíûõ êðèâûõ //
Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 1994. — ¹ 3. — C. 11–22.
7. Ë è ñ î â è ê Ë . Ï . , Ø ê à ð à â ñ ê à ÿ Î . Þ . Î âåùåñòâåííûõ ôóíêöèÿõ, çàäàâàåìûõ ïðåîáðàçîâàòå-
ëÿìè // Òàì æå. — 1998. — ¹ 1. — C. 82–93.
8. Ë è ñ î â è ê Ë . Ï . , Ê î â à ë ü Ä . À . , Ì à ð ò è í å ñ Ñ . Â . R-ïðåîáðàçîâàòåëè è ôðàêòàëüíûå êðèâûå
// Òàì æå. — 1999. — ¹ 3. — C. 95–105.
9. Ë è ñ î â è ê Ë . Ï . Îïåðàöèè íàä ðåàëüíûìè ÷èñëàìè // Êèáåðíåòèêà. — 1990. — ¹ 2. — C. 1–7, 25.
Ïîñòóïèëà 05.04.2007
|
| id | nasplib_isofts_kiev_ua-123456789-44366 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T13:14:51Z |
| publishDate | 2009 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Лисовик, Л.П. Карнаух, Т.А. 2013-05-31T16:09:40Z 2013-05-31T16:09:40Z 2009 Об одном методе задания фрактальных множеств / Л.П. Лисовик, Т.А. Карнаух // Кибернетика и системный анализ. — 2009. — № 3. — С. 42-50. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44366 519.71 В якості способу задання множин пропонується використовувати R-системи. Увага приділяється лінійним обмеженим R-системам і зв’язкам між R-системами та R*-перетворювачами. Зокрема показано, що лінійна обмежена R-система задає замкнену множину. A set generating system called an R-system is proposed for the specification of sets. Formal properties of the system are studied. The case of a bounded linear R-system is discussed and relations between R-systems and R*-transducers are established. In particular, it is shown that a bounded linear R-system specifies a bounded closed set. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Об одном методе задания фрактальных множеств Про один метод задання фрактальних множин A method of specification of fractal sets Article published earlier |
| spellingShingle | Об одном методе задания фрактальных множеств Лисовик, Л.П. Карнаух, Т.А. Кибернетика |
| title | Об одном методе задания фрактальных множеств |
| title_alt | Про один метод задання фрактальних множин A method of specification of fractal sets |
| title_full | Об одном методе задания фрактальных множеств |
| title_fullStr | Об одном методе задания фрактальных множеств |
| title_full_unstemmed | Об одном методе задания фрактальных множеств |
| title_short | Об одном методе задания фрактальных множеств |
| title_sort | об одном методе задания фрактальных множеств |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/44366 |
| work_keys_str_mv | AT lisoviklp obodnommetodezadaniâfraktalʹnyhmnožestv AT karnauhta obodnommetodezadaniâfraktalʹnyhmnožestv AT lisoviklp proodinmetodzadannâfraktalʹnihmnožin AT karnauhta proodinmetodzadannâfraktalʹnihmnožin AT lisoviklp amethodofspecificationoffractalsets AT karnauhta amethodofspecificationoffractalsets |