Генерация комбинаторных множеств с заданными свойствами

Генерация комбинаторных множеств с заданными свойствами

Аналізуються спеціальні класи комбінаторних множин — k-множини. Запропоновано алгоритм генерації k-множин, оснований на використанні єдиного алгоритму для генерації базових комбінаторних множин, розглянуто перспективи його використання для генерації різних базових множин. Оцінено складність наведени...

Full description

Saved in:
Bibliographic Details
Published in:Кибернетика и системный анализ
Date:2012
Main Authors: Гребенник, И.В., Литвиненко, А.С.
Format: Article
Language:Russian
Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2012
Subjects:
Системный анализ
Online Access:https://nasplib.isofts.kiev.ua/handle/123456789/84164
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:Генерация комбинаторных множеств с заданными свойствами / И.В. Гребенник, А.С. Литвиненко // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 96-105. — Бібліогр.: 15 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-84164
record_format dspace
spelling Гребенник, И.В.
Литвиненко, А.С.
2015-07-03T11:09:41Z
2015-07-03T11:09:41Z
2012
Генерация комбинаторных множеств с заданными свойствами / И.В. Гребенник, А.С. Литвиненко // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 96-105. — Бібліогр.: 15 назв. — рос.
0023-1274
https://nasplib.isofts.kiev.ua/handle/123456789/84164
519.85
Аналізуються спеціальні класи комбінаторних множин — k-множини. Запропоновано алгоритм генерації k-множин, оснований на використанні єдиного алгоритму для генерації базових комбінаторних множин, розглянуто перспективи його використання для генерації різних базових множин. Оцінено складність наведених алгоритмів, проаналізовано результати обчислювальних експериментів.
Special classes of combinatorial sets called k-sets are analyzed. An algorithm for the generation of k-sets is proposed. It is based on a single algorithm for generating base combinatorial sets. Possibilities of using it to generate various base sets are considered. The complexity of the algorithms is assessed. The results of computational experiments are analyzed.
ru
Інститут кібернетики ім. В.М. Глушкова НАН України
Кибернетика и системный анализ
Системный анализ
Генерация комбинаторных множеств с заданными свойствами
Генерація комбінаторних множин із заданими властивостями
Generation of combinatorial sets with prescribed characteristics
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Генерация комбинаторных множеств с заданными свойствами
spellingShingle Генерация комбинаторных множеств с заданными свойствами
Гребенник, И.В.
Литвиненко, А.С.
Системный анализ
title_short Генерация комбинаторных множеств с заданными свойствами
title_full Генерация комбинаторных множеств с заданными свойствами
title_fullStr Генерация комбинаторных множеств с заданными свойствами
title_full_unstemmed Генерация комбинаторных множеств с заданными свойствами
title_sort генерация комбинаторных множеств с заданными свойствами
author Гребенник, И.В.
Литвиненко, А.С.
author_facet Гребенник, И.В.
Литвиненко, А.С.
topic Системный анализ
topic_facet Системный анализ
publishDate 2012
language Russian
container_title Кибернетика и системный анализ
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
format Article
title_alt Генерація комбінаторних множин із заданими властивостями
Generation of combinatorial sets with prescribed characteristics
description Аналізуються спеціальні класи комбінаторних множин — k-множини. Запропоновано алгоритм генерації k-множин, оснований на використанні єдиного алгоритму для генерації базових комбінаторних множин, розглянуто перспективи його використання для генерації різних базових множин. Оцінено складність наведених алгоритмів, проаналізовано результати обчислювальних експериментів. Special classes of combinatorial sets called k-sets are analyzed. An algorithm for the generation of k-sets is proposed. It is based on a single algorithm for generating base combinatorial sets. Possibilities of using it to generate various base sets are considered. The complexity of the algorithms is assessed. The results of computational experiments are analyzed.
issn 0023-1274
url https://nasplib.isofts.kiev.ua/handle/123456789/84164
citation_txt Генерация комбинаторных множеств с заданными свойствами / И.В. Гребенник, А.С. Литвиненко // Кибернетика и системный анализ. — 2012. — Т. 48, № 6. — С. 96-105. — Бібліогр.: 15 назв. — рос.
work_keys_str_mv AT grebennikiv generaciâkombinatornyhmnožestvszadannymisvoistvami
AT litvinenkoas generaciâkombinatornyhmnožestvszadannymisvoistvami
AT grebennikiv generacíâkombínatornihmnožinízzadanimivlastivostâmi
AT litvinenkoas generacíâkombínatornihmnožinízzadanimivlastivostâmi
AT grebennikiv generationofcombinatorialsetswithprescribedcharacteristics
AT litvinenkoas generationofcombinatorialsetswithprescribedcharacteristics
first_indexed 2025-11-24T03:48:01Z
last_indexed 2025-11-24T03:48:01Z
_version_ 1850837708304285696
fulltext ÓÄÊ 519.85 È.Â. ÃÐÅÁÅÍÍÈÊ, À.Ñ. ËÈÒÂÈÍÅÍÊÎ ÃÅÍÅÐÀÖÈß ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÌÍÎÆÅÑÒÂ Ñ ÇÀÄÀÍÍÛÌÈ ÑÂÎÉÑÒÂÀÌÈ ÂÂÅÄÅÍÈÅ Ãåíåðàöèÿ ðàçíîîáðàçíûõ êîìáèíàòîðíûõ îáúåêòîâ èñïîëüçóåòñÿ ïðè ðàçðà- áîòêå è ðåàëèçàöèè ìåòîäîâ è àëãîðèòìîâ ðåøåíèÿ ìíîãèõ íàó÷íûõ è ïðè- êëàäíûõ çàäà÷ [1–6]. Ïîä ãåíåðàöèåé â íèõ ïîíèìàåòñÿ ïîñòðîåíèå âñåõ êîì- áèíàòîðíûõ ñòðóêòóð îïðåäåëåííîãî òèïà [3].  óêàçàííûõ èñòî÷íèêàõ ãëàâ- íûì îáðàçîì ðåøàþòñÿ çàäà÷è ãåíåðàöèè äîñòàòî÷íî ïðîñòûõ êîìáèíàòîðíûõ îáúåêòîâ — ïåðåñòàíîâîê, ñî÷åòàíèé, ðàçáèåíèé, äåðåâüåâ, äâîè÷íûõ ïîñëåäî- âàòåëüíîñòåé. Ðåçóëüòàòû ãåíåðàöèè êîìáèíàòîðíûõ îáúåêòîâ èñïîëüçóþòñÿ ïðè ðåøåíèè çàäà÷ ìîäåëèðîâàíèÿ, êîìáèíàòîðíîé îïòèìèçàöèè è â äðóãèõ îáëàñòÿõ [7–10]. Ðåøåíèå ïðîáëåìû ãåíåðàöèè áîëåå ñëîæíûõ êîìáèíàòîðíûõ îáúåêòîâ çàòðóäíÿåòñÿ îòñóòñòâèåì ñïåöèàëüíûõ êîíñòðóêòèâíûõ ñðåäñòâ è íå- îáõîäèìîñòüþ çíà÷èòåëüíûõ âû÷èñëèòåëüíûõ çàòðàò, ñâÿçàííûõ ñ èçáûòî÷íîñ- òüþ ðåçóëüòàòîâ ïðèìåíåíèÿ èçâåñòíûõ ìåòîäîâ è àëãîðèòìîâ ãåíåðàöèè. Äîñòàòî÷íî ñëîæíûå êîìáèíàòîðíûå êîíôèãóðàöèè ìîãóò áûòü ôîðìàëüíî îïèñàíû è ñãåíåðèðîâàíû ñ ïîìîùüþ êîíñòðóêòèâíûõ ñðåäñòâ îïèñàíèÿ êîìïî- çèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ ( k-ìíîæåñòâ), ïðåäëîæåííûõ â [11, 12]. Ïðè ýòîì ïîä êîìáèíàòîðíûì ìíîæåñòâîì ïîíèìàåòñÿ ìíîæåñòâî êîðòåæåé, ïîñòðîåííûõ èç êîíå÷íîãî ìíîæåñòâà ïðîèçâîëüíûõ ýëåìåíòîâ (òàê íàçûâàåìûõ ïîðîæäàþùèõ ýëåìåíòîâ) â ñîîòâåòñòâèè ñ îïðåäåëåííûìè ïðàâè- ëàìè [13]. Ïðèìåðàìè êëàññè÷åñêèõ êîìáèíàòîðíûõ ìíîæåñòâ ìîãóò ñëóæèòü ïåðåñòàíîâêè, ñî÷åòàíèÿ, ðàçìåùåíèÿ, äâîè÷íûå ïîñëåäîâàòåëüíîñòè. Àïïàðàò k-ìíîæåñòâ äîñòàòî÷íî ïîäðîáíî èññëåäîâàí â [11–13], îáùèå ïðèí- öèïû èõ ãåíåðàöèè ðàññìîòðåíû â [13]; îäíàêî ñàìà çàäà÷à ãåíåðàöèè k-ìíî- æåñòâ â îáùåì ñëó÷àå îñòàëàñü íåðåøåííîé, èññëåäîâàí ëèøü îäèí èç åå ÷àñò- íûõ ñëó÷àåâ [14]. Çàäà÷à ãåíåðàöèè k-ìíîæåñòâ, â ñâîþ î÷åðåäü, òðåáóåò ðåøåíèÿ çàäà÷ ãåíå- ðàöèè áàçîâûõ êîìáèíàòîðíûõ ìíîæåñòâ, èñïîëüçóåìûõ ïðè ïîñòðîåíèè k-ìíî- æåñòâ. Áàçîâûìè ìîãóò áûòü êîìáèíàòîðíûå ìíîæåñòâà ñ èçâåñòíûìè îïèñàíèÿìè è àëãîðèòìàìè ãåíåðàöèè: êàê êëàññè÷åñêèå êîìáèíàòîðíûå ìíîæåñòâà (ïåðåñòà- íîâêè, ñî÷åòàíèÿ, ðàçìåùåíèÿ, êîðòåæè), òàê è íåêëàññè÷åñêèå: ïåðåñòàíîâêè êîð- òåæåé, êîìïîçèöèè ïåðåñòàíîâîê, ïåðåñòàíîâêè ñ çàäàííûì êîëè÷åñòâîì öèêëîâ è äð. [12–14]. Äëÿ ìíîãèõ áàçîâûõ êîìáèíàòîðíûõ ìíîæåñòâ îïèñàíû àëãîðèòìû èõ ãåíåðàöèè [1–3, 5, 15], îäíàêî â áîëüøèíñòâå ñëó÷àåâ êàæäûé àëãîðèòì ãåíå- ðàöèè îñíîâàí íà ñïåöèôè÷åñêèõ ñâîéñòâàõ êîìáèíàòîðíûõ ìíîæåñòâ.  äàííîé ðàáîòå ïðåäëàãàåòñÿ îáùèé ïîäõîä ê ãåíåðàöèè êîìïîçèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ ( k-ìíîæåñòâ) íà îñíîâå åäèíîãî ïîäõîäà ê ãåíåðàöèè ðàçëè÷íûõ áàçîâûõ êîìáèíàòîðíûõ ìíîæåñòâ. Öåëü íàñòîÿùåé ðàáîòû — ðåøåíèå çàäà÷è ãåíåðàöèè êîìïîçèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ. 96 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 © È.Â. Ãðåáåííèê, À.Ñ. Ëèòâèíåíêî, 2012 1. ÊÎÌÏÎÇÈÖÈÎÍÍÛÅ k-ÎÁÐÀÇÛ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÌÍÎÆÅÑÒ (k-ÌÍÎÆÅÑÒÂÀ) Ïóñòü z z z z n i � � � � � � �{ } 1 2 , , Z � , Z � i — ìíîæåñòâà ïðîèçâîëüíûõ ýëåìåíòîâ, � � � i , i J k k � � 0 0 1 2{ , , , , }� , ãäå � 0 � {0}, � i j ij� �{ }� �, , ...,1 2 , � � � �j i� � �( , )1 2 � , �1 � Jn , � � � � �2 1 1 1 � � � � � J Jn i n i � � , �1 � n , � 2 1 � � � n j j n , � � � � � �i n n n i i i n� � � � � � � � � � 1 2 1 1 1 2 1 1 1 1 1 � � � , i k� 3 4, , ..., . (1) Ðàññìîòðèì îòîáðàæåíèÿ [12, 13] �� �0 0 : Z Y i , �� �i i i i : Y Z Y � 1 , ãäå Y 0 00 � �{ }Y z� �( ), � � , Y i iY Y z i i � � � { }� � �( , ), 1 � � , i J k� , J tt �{ }1 2, ,... , , Y Y F Y i i i i i i i � � � � � � � � � � � �( , ) ( , ~ ))z (z 1 , i Jk� , F Y i i i( , ~ ))� � �1 �� (z — îòîáðà- æåíèå, ðåàëèçóþùåå îïåðàöèþ n -çàìåùåíèÿ, êîòîðàÿ ñîñòîèò â çàìåíå êàæäîãî ïîðîæäàþùåãî ýëåìåíòà ìíîæåñòâà Y i� �1 ýëåìåíòàìè áàçîâûõ êîìáèíàòîðíûõ ìíîæåñòâ Y � � � � ~ ( )� z , � � � i , ñîîòâåòñòâåííî ~ ( ) ( ~ ( ), )� �� � � i i iz z� �� � � , z z � �i i� �( , ) � � , ~ ( )�� � z — áàçîâûå îòîáðàæåíèÿ [12, 13]. Ýòî îçíà÷àåò, ÷òî ( , )z z z Y l l l1 2 � � � � � � � �� , z Y lt � �� , l Jt l� � , � � � � i 1, � � � i , i Jk� . Îáîçíà÷èì � �i i � { }� , i Jk� . (2) Îïðåäåëåíèå. Êîìïîçèöèîííûì k -îáðàçîì êîìáèíàòîðíûõ ìíîæåñòâ Y0 , Y1, Y Yn2 , ,� , Y Y Y Y Yn nn n k k11 12 1 1 11 1 1 , , , , , , ,� � � � ��� � � (k -ìíîæåñòâîì), ïîðîæäåííûì ìíîæåñòâàìè z k� , � k k� � , íàçûâàåòñÿ êîìáèíàòîðíîå ìíîæåñòâî âèäà [12, 13] W zz k k� � � � �� �� �1 0 ( ) , (3) ãäå îòîáðàæåíèÿ �i i�� , i Jk� , îïðåäåëÿþòñÿ ñîîòíîøåíèåì (2). Ìîùíîñòü ìíîæåñòâà (3) îïðåäåëÿåòñÿ ñîîòíîøåíèåì [12, 13] Card Wz J i k r n r i ( ) , , ( � � � � � � � � � � { }� � � � � � � � � � 1 2 1 2 1 21� � �� � i i Card Y ) . (4) Ïîñêîëüêó ãåíåðàöèÿ k-ìíîæåñòâ îñíîâûâàåòñÿ íà ãåíåðàöèè áàçîâûõ êîìáè- íàòîðíûõ ìíîæåñòâ, íåîáõîäèì àëãîðèòì äëÿ ãåíåðàöèè ýòèõ ìíîæåñòâ. 2. ÃÅÍÅÐÀÖÈß ÁÀÇÎÂÛÕ ÊÎÌÁÈÍÀÒÎÐÍÛÕ ÌÍÎÆÅÑÒÂ Ñ êàæäûì áàçîâûì êîìáèíàòîðíûì ìíîæåñòâîì T ñâÿæåì ìíîæåñòâî p T( ) � �{ }A m S, , , ãäå A a a an� � �{ }1 2, � , a a an1 2� � �� , — ìíîæåñòâî ïîðîæäàþ- ùèõ ýëåìåíòîâ, m — äëèíà êîðòåæà t T� (ïîëàãàåì, ÷òî âñå êîðòåæè ìíî- æåñòâà èìåþò ðàâíóþ äëèíó), S — íàáîð ïàðàìåòðîâ, õàðàêòåðèçóþùèõ ìíî- æåñòâî T , íàïðèìåð, ïàðàìåòðû n n nk1 2, � �� äëÿ ïåðåñòàíîâîê ñ ïîâòîðåíèÿìè è äðóãèå ïàðàìåòðû, õàðàêòåðíûå äëÿ ðàçíûõ êëàññîâ êîìáèíàòîðíûõ ìíî- æåñòâ. Ïîä êëàññîì êîìáèíàòîðíîãî ìíîæåñòâà áóäåì ïîíèìàòü åãî ïðèíàä- ëåæíîñòü ïåðåñòàíîâêàì, ñî÷åòàíèÿì è ò.ä. ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 97 Ïóñòü çàäàíû áàçîâîå êîìáèíàòîðíîå ìíîæåñòâî T è åãî ïàðàìåòðû p T( ) . Íå- îáõîäèìî ñãåíåðèðîâàòü âñå ýëåìåíòû t T� , êàæäûé èç êîòîðûõ ÿâëÿåòñÿ êîðòåæåì äëèíû m . Ââåäåì îáîçíà÷åíèå t t t t i i� � �( , )1 2 � � �t Ai , A p T� ( ) , i Jn� . Òîãäà t 0 � ( ) — ïóñòîé êîðòåæ, t t T m � � . Ðåçóëüòàòîì ãåíåðàöèè ÿâëÿåòñÿ ìíîæåñòâî T . Èçëîæèì âíà÷àëå èäåþ àëãîðèòìà ãåíåðàöèè áàçîâûõ ìíîæåñòâ. Àëãîðèòì ðàáîòàåò ðåêóðñèâíî, íà êàæäîì óðîâíå ðåêóðñèè i J m � �1 0 äîáàâëÿÿ â òåêóùèé êîðòåæ t t t t i i� � �( , )1 2 � ñëåäóþùèé ýëåìåíò ti�1, ïîëó÷àÿ íà óðîâíå i �1 êîð- òåæ t t t t i i � � � � � 1 1 2 1( , )� . Íà óðîâíå m n� àëãîðèòì äîáàâëÿåò êîðòåæ t t m � âî ìíîæåñòâî T . Ïðèíàäëåæíîñòü ìíîæåñòâà T ê îïðåäåëåííîìó êëàññó êîìáèíàòîðíûõ ìíî- æåñòâ óñòàíàâëèâàåò íåêîòîðûå îãðàíè÷åíèÿ íà ýëåìåíò t Ai� �1 . Íà êàæäîì óðîâíå i J m � �1 0 îáîçíà÷èì F f f f A i k� � � �{ }1 2, � ìíîæåñòâî âñåõ ïîðîæäà- þùèõ ýëåìåíòîâ, óäîâëåòâîðÿþùèõ ýòèì îãðàíè÷åíèÿì. Òîãäà âî âõîäíîé êîð- òåæ t t t t i i� � �( , )1 2 � àëãîðèòì äîáàâëÿåò ýëåìåíò t fi j� �1 äëÿ êàæäîãî j Jk� è ðåêóðñèâíî âûçûâàåò ñåáÿ ñ ïàðàìåòðîì t t t f i j � � � � 1 1 2( , )� . Ðàññìîòðèì îñîáåííîñòè ïîñòðîåíèÿ ìíîæåñòâà F i äëÿ íåêîòîðûõ êëàññîâ êîìáèíàòîðíûõ ìíîæåñòâ. Äëÿ ðàçìåùåíèé ñ ïîâòîðåíèÿìè âî ìíîæåñòâî F i âõîäÿò âñå ïîðîæäàþùèå ýëåìåíòû: F A i � . Äëÿ ðàçìåùåíèé áåç ïîâòîðåíèé è ïåðåñòàíîâîê (êàê ÷àñòíûé ñëó÷àé) âî ìíîæåñòâî F i âõîäèò n i� ïîðîæäàþùèõ ýëåìåíòîâ, íåçàäåéñòâîâàííûõ â t i : F f f f A f t j J l J i n i l j i n i� � � � � � � � � � � { }1 2, : ,� . Ïîñêîëüêó â ñî÷åòàíèÿõ ïîðÿäîê ýëåìåíòîâ íå èãðàåò ðîëè, áóäåì ãåíåðèðî- âàòü èõ â âèäå óïîðÿäî÷åííûõ íàáîðîâ, äëÿ êîòîðûõ t t ti1 2� �� â ñëó÷àå ñî- ÷åòàíèé áåç ïîâòîðåíèé è t t ti1 2� � �� äëÿ ñî÷åòàíèé ñ ïîâòîðåíèÿìè. Òîã- äà äëÿ ñî÷åòàíèé áåç ïîâòîðåíèé âî ìíîæåñòâî F i âõîäÿò ïîðîæäàþùèå ýëå- ìåíòû, íåçàäåéñòâîâàííûå â t i è áîëüøèå ti : F f f f A f t f t l J j J i k l j l i k i� � � � � � � � � � � { }1 2 1, : , ,� .  ñëó÷àå ñî÷åòàíèé ñ ïîâòîðåíèÿìè â F i òàêæå âõîäÿò ïîðîæäàþùèå ýëåìåí- òû, ðàâíûå ti : F f f f A f t f t l J j J i k l j l i k i� � � � � � � � � � � { }1 2 1, : , ,� . Îïèøåì àëãîðèòì GenBase, ðåàëèçóþùèé îïèñàííûå äåéñòâèÿ. Âõîäíûå äàííûå GenBase — ìíîæåñòâî T , íàáîð ïàðàìåòðîâ p T( ) , à òàêæå êîðòåæ t i . Íà êàæäîì óðîâíå ðåêóðñèè i J m � �1 0 àëãîðèòì ôîðìèðóåò ìíîæåñòâî F i , çàòåì â t i ïîñëåäîâàòåëüíî äîáàâëÿåò êàæäûé ýëåìåíò F i , íà÷èíàÿ ñ ïåðâîãî, è ðåêóðñèâíî âûçûâàåò ñåáÿ. Äëÿ ãåíåðàöèè âñåõ íåîáõîäèìûõ ýëåìåíòîâ ìíîæåñòâà GenBase âûçûâàåò- ñÿ ñ ïàðàìåòðàìè T , ( ) , p T( ) . Îòìåòèì, ÷òî áàçîâîå êîìáèíàòîðíîå ìíîæåñòâî ìîæåò ñîñòîÿòü èç åäèíñòâåííîãî çàäàííîãî êîðòåæà. Òîãäà GenBase íè÷åãî íå äîáàâëÿåò ê çàäàííîìó êîðòåæó è ïðåêðàùàåò ðàáîòó: function GenBase(T t i , p T( )); local F i ; if i m� , then T T t i : � � ; exit; end if; 98 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 case T of An m : F A i � ; An m : F f f f A f t j J l J i n i l j i n i� � � � � � � � � � � { }1 2, : , ,� ; Cn m : F f f f A f t f t l J j J i k l j l i k i� � � � � � � � � � � { }1 2 1, : , , ,� ; Cn m : F f f f A f t f t l J j J i k l j l i k i� � � � � � � � � � � { }1 2 1, : , , ,� ; Tn : exit; end case; for j F i �1 2, , ..., | | do GenBase(t t t t f i i j � � � � 1 1 2( , , )� ); end for; end function; Äëÿ ãåíåðàöèè êîìáèíàòîðíûõ ìíîæåñòâ äðóãèõ êëàññîâ ñ ïîìîùüþ äàííî- ãî àëãîðèòìà äîñòàòî÷íî îïðåäåëèòü ñîîòâåòñòâóþùèå ïðàâèëà ôîðìèðîâàíèÿ ìíîæåñòâà F i . 3. ÃÅÍÅÐÀÖÈß k-ÌÍÎÆÅÑÒ Ïóñòü äàíû êîìáèíàòîðíûå ìíîæåñòâà Y Y Y Y Y Y Yn n0 1 2 11 12 1 1 , , , , , , ,� � � � � � ��� � , , ,Y Y k knn n1 1 1 1� , à òàêæå ïàðàìåòðû p Y p Y p Ynn nk ( ), ( ), ..., ( )...0 1 1 1� . Íåîá- õîäèìî ïîëó÷èòü k-ìíîæåñòâî W zz k k� � � � �� �� �1 0 ( ) , z A p Y� �0 0( ) . Ââå- äåì íåêîòîðûå îáîçíà÷åíèÿ. Ìíîæåñòâî Yi i in1 2, ,..., áóäåì íàçûâàòü ðîäèòåëüñêèì ìíîæåñòâîì ìíîæåñòâà Y j j j jn n1 2 1... � , åñëè i j i j i jn n1 1 2 2� � � � �, � . Ìíîæåñòâî Y j j j jn n1 2 1... � áóäåì íàçû- âàòü äî÷åðíèì ìíîæåñòâîì ìíîæåñòâà Yi i in1 2... . Äëÿ óäîáñòâà ïðåäñòàâëåíèÿ àëãî- ðèòìà ðåøåíèÿ çàäà÷è èçìåíèì ñèñòåìó èíäåêñàöèè áàçîâûõ ìíîæåñòâ, ïåðåéäÿ îò èíäåêñîâ ïåðåìåííîé äëèíû ê èíäåêñàì ôèêñèðîâàí- íîé äëèíû. Êàæäîå áàçîâîå ìíîæåñòâî íà óðîâíå i J k � �1 0 áóäåì îáîçíà÷àòü êàê Yij , ãäå j J i � � — ïîðÿä- êîâûé íîìåð áàçîâîãî ìíîæåñòâà, à � i îïðåäåëÿåòñÿ ôîð- ìóëîé (1). Ïðè ýòîì äëÿ ìíîæåñòâà Y0 â ôîðìóëàõ áóäåì ïðèìåíÿòü îáîçíà÷åíèå Y01. Ïðèìåð 1. Ïóñòü çàäàíû áàçîâûå ìíîæåñòâà Y0 , Y1, Y2 , Y11, Y21, Y22 , Y111, Y Y211 221, , ñâÿçü ìåæäó êîòîðû- ìè ìîæíî ñõåìàòè÷åñêè ïðåäñòàâèòü â âèäå äåðåâà (ðèñ. 1). Íà ïåðâîì óðîâíå òàêîãî äåðåâà íàõîäÿòñÿ ìíîæå- ñòâà Y1 è Y2 , íà âòîðîì — Y11, Y21 è Y22 , íà òðåòüåì — Y111, Y211 è Y221.  ñîîòâåòñòâèè ñ íîâîé èíäåêñàöèåé ìíîæåñòâà ïåðâîãî óðîâíÿ îáîçíà÷èì Y11 è Y12 , âòîðîãî — Y21, Y22 è Y23 , òðåòüåãî — Y31, Y32 è Y33 . Òîãäà ñõå- ìà ñâÿçè áàçîâûõ ìíîæåñòâ ïðè èçìåíåííîé èíäåêñàöèè ïðèíèìàåò âèä, ïðåäñòàâëåííûé íà (ðèñ. 2). Ïðåäëîæåííûé ñïîñîá èíäåêñàöèè ïîçâîëÿåò íåÿâ- íî çàäàòü ñâÿçü ìåæäó äî÷åðíèì è ðîäèòåëüñêèì ìíî- æåñòâàìè. Ïóñòü ìíîæåñòâî Yij ïîðîæäåíî ýëåìåíòàìè ìíîæåñòâà A p Yij ij� ( ), ìîùíîñòü êîòîðîãî n Aij ij� | | . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 99 Y2 Y0 Y1 Y11 Y22Y21 Y211 Y221Y111 Ðèñ. 1 Y12 Y0 Y11 Y21 Y23Y22 Y32 Y33Y31 Ðèñ. 2 Òîãäà èç ñïîñîáà ïîñòðîåíèÿ k-ìíîæåñòâà ñëåäóåò, ÷òî íà óðîâíå i �1 èìååòñÿ nij äî÷åðíèõ ìíîæåñòâ ìíîæåñòâà Yij . Ïîëîæèì, ÷òî ïåðâûå ni1 ìíîæåñòâ íà óðîâíå i �1 ÿâëÿþòñÿ äî÷åðíèìè ìíîæåñòâàìè Yi1, ñëåäóþùèå ni2 ìíîæåñòâ — äî÷åðíè- ìè äëÿ Yi2 è ò.ä. äëÿ âñåõ Yij , j J i � � . Òîãäà äëÿ êàæäîãî áàçîâîãî ìíîæåñòâà ìîæíî îäíîçíà÷íî óñòàíîâèòü âñå åãî ðîäèòåëüñêèå è äî÷åðíèå ìíîæåñòâà. Ïðè ýòîì ïîëîæèì, ÷òî ïðè âûïîëíåíèè îïåðàöèè n-çàìåùåíèÿ ïîðîæäàþùèé ýëå- ìåíò a Al ij� ðîäèòåëüñêîãî ìíîæåñòâà Yij áóäåò çàìåùåí ýëåìåíòàìè l-ãî åãî äî÷åðíåãî ìíîæåñòâà. Ïðèìåð 2. Ïóñòü k-ìíî- æåñòâî ïðåäñòàâëåíî äåðåâîì (ðèñ. 3), ãäå Ð a b( , ) — ìíî- æåñòâî ïåðåñòàíîâîê ýëåìåí- òîâ à è b, Ñ c d e 3 2 ( , , ) — ìíî- æåñòâî ñî÷åòàíèé èç òðåõ ýëåìåíòîâ ïî äâà, T ( , , )1 2 3 — êîðòåæ ( )123 è ò.ä. Ìíîæåñòâî Y11 ïîðîæäå- íî òðåìÿ ýëåìåíòàìè: c d e, , , êîòîðûå ïðè âûïîëíåíèè îïåðàöèè n-çàìåùåíèÿ áóäóò çàìåíåíû ýëåìåíòàìè ìíîæåñòâ Y21, Y22 è Y23 ñî- îòâåòñòâåííî. Ïîðîæäàþùèå ýëåìåíòû f è g ìíîæåñòâà Y12 áóäóò çàìåíåíû ýëå- ìåíòàìè ìíîæåñòâ Y24 è Y25 ñîîòâåòñòâåííî. 4. ÀËÃÎÐÈÒÌ ÃÅÍÅÐÀÖÈÈ k-ÌÍÎÆÅÑÒ Îïèøåì àëãîðèòì ãåíåðàöèè k-ìíîæåñòâ.  íà÷àëå åãî ðàáîòû ñ ïîìîùüþ àëãîðèòìà GenBase ãåíåðèðóþòñÿ ýëåìåíòû êàæäîãî áàçîâîãî ìíîæåñòâà Yij , çàòåì ïîñëåäîâàòåëüíî ðåàëèçóþòñÿ îòîáðàæåíèÿ � � �i i z �1 0� �� � ( ), z A p Y� �0 0( ) , äëÿ êàæäîãî i J k � �1 0 , ò.å. ïðîèçâîäèòñÿ îïåðàöèÿ n-êîìïîçèöèè, ãäå ïîðîæäàþùèå ýëåìåíòû ðîäèòåëüñêîãî ìíîæåñòâà çàìåíÿþòñÿ ýëåìåíòà- ìè-êîðòåæàìè åãî äî÷åðíèõ ìíîæåñòâ. Íà óðîâíå i � 0 ðîäèòåëüñêèì ìíîæåñòâîì ÿâëÿåòñÿ ìíîæåñòâî Y0 , äî÷åðíè- ìè — ìíîæåñòâà Y11, Y Y12 1 1 � �� � . Íà óðîâíå i �1 ðîäèòåëüñêîå ìíîæåñòâî — ðå- çóëüòàò êîìïîçèöèè îòîáðàæåíèé � �1 0� ( )z , ïîëó÷åííûé íà íóëåâîì óðîâíå, äî÷åðíèìè ìíîæåñòâàìè ÿâëÿþòñÿ Y21, Y Y22 2 2 , ,� � . Íà óðîâíå i ðîäèòåëücêîå ìíîæåñòâî — ðåçóëüòàò êîìïîçèöèè îòîáðàæåíèé � � �i i z� �� � �1 0 ( ), äî÷åðíèå ìíîæåñòâà — Y i( )�1 1, Y Yi i i( ) ( ), , � � � 1 2 1 1 � � . Ââåäåì ìíîæåñòâî P i , êîòîðîå ïðåäñòàâëÿåò ñîáîé ðåçóëüòàò ïðèìåíåíèÿ êîìïîçèöèè îòîáðàæåíèé � � �i i� �� � �1 0 ê èñõîäíîìó ìíîæåñòâó z A p Y� �0 0( ) . Îáîçíà÷èì P z i i i� � � � �� �� �1 0 ( ), ìíîæåñòâî åãî ïîðîæäàþ- ùèõ ýëåìåíòîâ — A i , äëèíó êàæäîãî åãî ýëåìåíòà-êîðòåæà — m i . Òàê êàê íà óðîâíå i ìíîæåñòâî P i ñîñòîèò èç ýëåìåíòîâ-êîðòåæåé ìíîæåñòâ Y Yi i i1� �� � , òî åãî ïîðîæäàþùåå ìíîæåñòâî èìååò âèä A A i j ij i � �1 � � , A p Yij ij� ( ) , (5) à äëèíà êàæäîãî åãî ýëåìåíòà-êîðòåæà ðàâíà m m i j ij i � �1 � � , m p Yij ij� ( ) , (6) 100 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 Ð(a, b) P( f, g) Ò(1, 2, 3) Ò(4, 5, 6) T(7, 8, 9) T(x, y) T(w, z) Y12 Y0 Y11 Y21 Y22 Y23 Y24 Y25 Ðèñ. 3 Ñ ñ d e 3 2 ( , , ) ãäå Aij — ìíîæåñòâî ïîðîæäàþùèõ ýëåìåíòîâ, mij — äëèíà êàæäîãî ýëåìåí- òà-êîðòåæà áàçîâîãî ìíîæåñòâà Yij . Äëÿ íóëåâîãî óðîâíÿ P Y 0 0� , A A p Y 0 0 0� � ( ) , m m p Y 0 0 0� � ( ) . Äëÿ âû÷èñëåíèÿ � i ïðè íîâîé èíäåêñàöèè ìîæíî èñïîëüçîâàòü ôîðìóëó � � i i j j i j i jA A p Y i � � � � � � � � | | , ( )( ) ( ) ( )1 1 1 1 1 , (7) àíàëîãè÷íóþ (1).  îïåðàöèè n -çàìåùåíèÿ ýëåìåíòàðíîé îïåðàöèåé ÿâëÿåòñÿ çàìåíà îäíîãî êîðòåæà äðóãèì. Îïèøåì ôóíêöèþ replace, âûïîëíÿþùóþ òàêóþ çàìåíó. Âõî- äîì ôóíêöèè ÿâëÿåòñÿ êîðòåæ x x x xm� � �( , )1 2 � , åãî äëèíà m , ìíîæåñòâî ýëå- ìåíòîâ A ai� { }, êîòîðûìè ïîðîæäåí êîðòåæ x , è ìíîæåñòâî R ri� { }, i Jn� , n A� | | òàêîå, ÷òî êàæäûé ýëåìåíò a Ai � íåîáõîäèìî çàìåíèòü íà r Ri � . Âûõî- äîì ôóíêöèè ÿâëÿåòñÿ êîðòåæ x, ãäå âûïîëíåíû âñå çàìåíû. Ôóíêöèÿ replace ïðèâåäåíà íèæå: function replace(x , m , A , R ); for i A: , , ..., | |�1 2 for j m: , , ...,�1 2 if x aj i� then x rj i: � , ; end if; end for; end for; return x ; end function; Âõîäíûìè äàííûìè àëãîðèòìà Gen_ k-set ãåíåðàöèè k -ìíîæåñòâà ÿâëÿþòñÿ ÷èñëî k (÷èñëî óðîâíåé äåðåâà ðàâíî k �1), êëàññû áàçîâûõ ìíîæåñòâ Yij è èõ ïà- ðàìåòðû p Yij( ) , i J k � 0 , j J i � � . Âûõîäîì àëãîðèòìà ÿâëÿåòñÿ ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ ãåíåðèðóåìîãî k -ìíîæåñòâà. Àëãîðèòì Gen_ k-set ãåíåðàöèè k-ìíîæåñòâà ïðèâåäåí íèæå: procedure Gen_ k-set; � 0 1: � ; for i k: , , ...,� 0 1 do if i � 0 then � � i i j j A i : | |( )� � � � � 1 1 1 ; for j i: , , ...,�1 2 � do Y Yij ij: (( ),� Gen_ Base , p Yij( )); end for; end for; P Y 0 0: � ; A A p Y 0 0: ( )� � ; m m p Y 0 0: ( )� � ; for i k: , , ...,� �0 1 1 do P i� � � 1 : ; A A i j ij i � �1 � � ; ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 101 m m i j ij i � �1 � � ; foreach x P i � do foreach p Y i1 1 1� �( ) foreach p Y i2 1 2� �( ) �� foreach p Y i ii� � � � � �1 11( ) P P i i� � � � 1 1 : replace(x , m i , A i , { })p p p i1 2 1 , � � � � � ; end for; �� end for; end for; end for; if i k� �1 then print P i�1 ; end for; end procedure; Íà êàæäîì óðîâíå i J k � �1 0 â êàæäîì êîðòåæå òåêóùåãî ðîäèòåëüñêîãî ìíî- æåñòâà P i åãî ýëåìåíòû-êîðòåæè çàìåíÿþòñÿ âñåìè âîçìîæíûìè êîìáèíàöèÿìè ýëåìåíòîâ-êîðòåæåé äî÷åðíèõ ìíîæåñòâ Y Y Yi i i i( ) ( ) ( ), , .., � � � � 1 1 1 2 1 1� . Ïðîõîäÿ â öèêëå ïî âñåì ýëåìåíòàì-êîðòåæàì òåêóùåãî äî÷åðíåãî ìíîæåñòâà, êàæäûé ðàç ïîëó÷àåì íàáîð êîðòåæåé { }p p p i1 2 1 , , ..., � � , ãäå p Yj i j� �( )1 — òåêóùèé êîð- òåæ j-ãî äî÷åðíåãî ìíîæåñòâà, è ñ ïîìîùüþ ôóíêöèè replace â êîðòåæå x P i � çàìåíÿåì êàæäûé ïîðîæäàþùèé ýëåìåíò a Aj i � íà p Yj i j� �( )1 . Ñóùåñòâåííûì ïðåèìóùåñòâîì àëãîðèòìà ÿâëÿåòñÿ âîçìîæíîñòü ïîëó÷åíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ, ò.å. ìíîæåñòâ P i íà êàæäîì óðîâíå i Jk� �1, êîòî- ðûå ìîæíî ðàññìàòðèâàòü êàê k-ìíîæåñòâà, ãäå k i� . Ïðèìåð 3. Ïóñòü íåîáõîäèìî ñãåíåðèðîâàòü ìíîæåñòâî ïåðåñòàíîâîê äâóõ çàäàííûõ êîðòåæåé: T1 1 2� ( , ), T2 3 4� ( , ) . Òîãäà k �1 è ìíîæåñòâî Y0 — ýòî ìíî- æåñòâî ïåðåñòàíîâîê äâóõ ýëåìåíòîâ èëè ðàçìåùåíèé èç äâóõ ýëåìåíòîâ ïî äâà, à m0 2� . Ïîðîæäàþùèå ýëåìåíòû Y0 ìîãóò áûòü ëþáûìè, ïîýòîìó ïîëîæèì A a b0 � { }, . Òîã- äà Y a b b a0 � { }( , ), ( , ) . Ìíîæåñòâà Y11 1 2� { }( , ) , Y12 3 4� { }( , ) , ò.å. çàäàííûå êîðòåæè T1 è T2 , èìåþò ïàðà- ìåòðû A11 1 2� { }, , A12 3 4� { }, , m m11 12 2� � . Ïðåäñòàâèì ñòðóêòóðó k -ìíîæåñòâà äëÿ ïðèìåðà 3 (ðèñ. 4).  îïåðàöèè n-çàìåùåíèÿ â ðîäèòåëüñêîì ìíîæåñòâå Y0 ïåðâûé ïîðîæäàþ- ùèé ýëåìåíò a áóäåò çàìåíåí åäèíñòâåííûì ýëåìåíòîì ìíîæåñòâà Y11, ò.å. êîð- òåæåì (1, 2), à ýëåìåíò b — êîðòåæåì (3, 4). Ðàññìîòðèì ïðîöåññ ïîëó÷åíèÿ ìíîæåñòâà W z Pz � �� �1 0 1 � ( ) : 1. x ab� ( ) 1.1. p1 1 2� ( , ) 1.1.1. p2 34� ( ) P 1 :� � � replace(( ) , ,ab a b2 { }, { }( ), ( )12 34 ); // P 1 1234� { }( ) 102 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 P(a, b) T(1, 2) T(3, 4) Ðèñ. 4 2. x ba� ( ) 2.1. p1 12� ( ) 2.1.1. p2 34� ( ) P 1 1234: ( )� �{ } replace(( ), , ,ba a b2 { }, { }( ), ( )12 34 ); // P 1 1234 3412� { }( ), ( )  ðåçóëüòàòå ïîëó÷èì W z Pz � � �� �1 0 1 1234 3412� ( ) ( ), ( ){ }. 4. ÎÖÅÍÊÀ ÑËÎÆÍÎÑÒÈ ÀËÃÎÐÈÒÌÀ Gen_ k-set Ñëîæíîñòü äàííîãî àëãîðèòìà ïðåäåëÿåòñÿ ñëîæíîñòüþ ãåíåðàöèè áàçîâûõ ìíî- æåñòâ, à òàêæå ñëîæíîñòüþ âûïîëíåíèÿ îïåðàöèé n-çàìåùåíèÿ è êîëè÷åñòâîì óðîâíåé k-ìíîæåñòâà. Äëÿ ãåíåðàöèè áàçîâûõ ìíîæåñòâ ìîãóò èñïîëüçîâàòüñÿ êàê èçâåñòíûå àëãî- ðèòìû ñ èçâåñòíûìè îöåíêàìè ñëîæíîñòè (íàïðèìåð, [1–3, 15]), òàê è îïèñàííûé â äàííîé ðàáîòå àëãîðèòì GenBase.  ëþáîì ñëó÷àå êàæäîå áàçîâîå ìíîæåñòâî Yij , i J k � 0 , j J i � � , äîëæíî áûòü ñãåíåðèðîâàíî îäíèì èç àëãîðèòìîâ. Òîãäà ñëîæíîñòü ãåíåðàöèè áàçîâûõ ìíîæåñòâ îïðåäåëÿåòñÿ êàê O Yij ji k i ( ) �� �� 10 � , (8) ãäå O Yij( ) — ñëîæíîñòü ãåíåðàöèè áàçîâîãî ìíîæåñòâà Yij , çàâèñÿùàÿ îò èñ- ïîëüçóåìîãî àëãîðèòìà. Îöåíèì O Yij( ) äëÿ àëãîðèòìà GenBase. Èñõîäÿ èç ñïîñîáîâ îöåíêè ñëîæíîñòè ðåêóðñèâíîãî àëãîðèòìà, ñëåäóÿ [5], ïîä ñëîæíîñòüþ àëãîðèòìà áóäåì ïîäðàçóìåâàòü êîëè÷åñòâî èçìåíåíèé ïðîìå- æóòî÷íûõ äàííûõ, ïðîâåäåííûõ ñ ìîìåíòà âûçîâà àëãîðèòìà äî îêîí÷àíèÿ åãî ðàáîòû.  àëãîðèòìå GenBase êî âõîäíîìó êîðòåæó t i íà êàæäîì óðîâíå ðåêóð- ñèè i J m � �1 0 äîáàâëÿþòñÿ ýëåìåíòû ìíîæåñòâà F i è ïðîèñõîäèò ðåêóðñèâíûé âûçîâ GenBase, ò.å èçìåíÿþòñÿ ïðîìåæóòî÷íûå äàííûå (êîðòåæè t i ), è ïîýòîìó ñëîæíîñòü ìîæåò áûòü îöåíåíà êàê êîëè÷åñòâî ðåêóðñèâíûõ âûçîâîâ GenBase íà óðîâíÿõ i J m � �1 0 . Ïîñêîëüêó íà êàæäîì óðîâíå ðåêóðñèè â êîðòåæ t i äîáàâëÿåòñÿ îäèí ýëå- ìåíò, äëÿ ãåíåðàöèè êàæäîãî èç N êîðòåæåé t t T m � � GenBase âûçûâàåòñÿ íå áîëåå m ðàç. Òîãäà ñëîæíîñòü ãåíåðàöèè ýëåìåíòîâ îäíîãî áàçîâîãî ìíîæåñòâà íå ïðåâûøàåò mN , N Card T� ( ) . Òàêèì îáðàçîì, åñëè àëãîðèòì GenBase èñïîëüçóåòñÿ äëÿ ãåíåðàöèè âñåõ áà- çîâûõ ìíîæåñòâ, ôîðìóëà (8) ïðèíèìàåò âèä m Card Yij ij ji k i ( ) �� �� 10 � , m p Yij ij� ( ) . (9) Ñëåäóÿ âûáðàííîìó ñïîñîáó îöåíêè ñëîæíîñòè, ñëîæíîñòü âûïîëíåíèÿ îïå- ðàöèé n -çàìåùåíèÿ â àëãîðèòìå Gen_ k-set áóäåì îïðåäåëÿòü êîëè÷åñòâîì âûçî- âîâ ôóíêöèè replace, èçìåíÿþùåé ïðîìåæóòî÷íûå äàííûå àëãîðèòìà, à èìåííî êîðòåæè x P i � . Èç àëãîðèòìà Gen_ k-set ñëåäóåò, ÷òî íà êàæäîì óðîâíå k-ìíî- æåñòâà i J k � � 0 1 ôóíêöèÿ replace âûçûâàåòñÿ M Card P Card Y Card Y Card Y i i i i i � � � � ( ) ( ) ( ) (( ) ( ) ( )1 1 1 2 1� � � 1 ) (10) ðàç. Âåëè÷èíà Card P i ( ) ìîæåò áûòü ïîëó÷åíà èç (4) ïðè ïîäñòàíîâêå k i� . ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 103 Âåëè÷èíû Card Y i j( )�1 , j J i � � � 1 — ýòî ìîùíîñòè áàçîâûõ ìíîæåñòâ, îïðåäåëÿ- åìûå ïî èçâåñòíûì äëÿ êàæäîãî êëàññà êîìáèíàòîðíûõ ìíîæåñòâ ôîðìóëàì. Íà âñåõ óðîâíÿõ i J k � � 0 1 êîëè÷åñòâî âûçîâîâ ôóíêöèè replace ðàâíî Card P Card Y i j i j i k i ( ) ( )( ) � � � � � � � � � � � � � � 1 1 0 1 1� . (11) Çàìåòèì, ÷òî ñëîæíîñòü àëãîðèòìà ïîñòðîåíèÿ k-ìíîæåñòâà íå çàâèñèò îò ñëîæíîñòè àëãîðèòìîâ, èñïîëüçóåìûõ äëÿ ãåíåðàöèè áàçîâûõ ìíîæåñòâ. Òàêèì îáðàçîì, ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå. Òåîðåìà. Âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà ãåíåðàöèè k-ìíîæåñòâ Gen_ k-set îïðåäåëÿåòñÿ êàê O Y Card P Card Yij ji k i j i j i i ( ) ( ) ( )( ) �� � ��� � � � � � 10 1 1 1� � � � � � � � � � i k 0 1 . (12) Ñëó÷àé, êîãäà âñå áàçîâûå ìíîæåñòâà ÿâëÿþòñÿ ïåðåñòàíîâêàìè, îïðåäåëåí â [13] êàê k-êîìïîçèöèÿ ïåðåñòàíîâîê, ïîëó÷åíà ôîðìóëà äëÿ êîëè÷åñòâà ýëå- ìåíòîâ â k-ìíîæåñòâå. Èç [13] ìîæíî ïîëó÷èòü ôîðìóëó äëÿ âåëè÷èíû Card P i ( ) . Åñëè âñå ìíîæåñòâà Yij ÿâëÿþòñÿ ïåðåñòàíîâêàìè nij ýëåìåíòîâ, òî Card Y nij ij( ) !� è Card P n i u i j uj i ( ) ( )!� � � 0 1 � . (13) Òîãäà äëÿ k-êîìïîçèöèè ïåðåñòàíîâîê ôîðìóëà (10) ïðèíèìàåò âèä u i j uj i i k i i n n � � � � � � � � � � � � � � � � 0 1 1 1 0 1 1� � � �( )! ( )!( )� . (14) Ñëåäñòâèå. Âû÷èñëèòåëüíàÿ ñëîæíîñòü àëãîðèòìà ãåíåðàöèè k-êîìïîçèöèè ïåðåñòàíîâîê ñîñòàâëÿåò O Y n nij ji k u i j uj i i i i ( ) ( )! ( ( �� � � � ��� � � � 10 0 1 1 1 1� � � � ) )!� � � � � � � � � � � � i k 0 1 , (15) ãäå nij — êîëè÷åñòâî ïîðîæäàþùèõ ýëåìåíòîâ ìíîæåñòâà Yij . 5. ÂÛ×ÈÑËÈÒÅËÜÍÛÅ ÝÊÑÏÅÐÈÌÅÍÒÛ Íà îñíîâå ïðåäëîæåííîãî àëãîðèòìà ðåøåíèÿ çàäà÷è ðàçðàáîòàíî ïðîãðàì- ìíîå îáåñïå÷åíèå, ñ ïîìîùüþ êîòîðîãî ìîæíî ãåíåðèðîâàòü k-ìíîæåñòâà ðàç- ëè÷íîé ñòðóêòóðû è ñëîæíîñòè. Ïðîäåìîíñòðèðóåì ðåçóëüòàò ðàáîòû ïðî- ãðàììû äëÿ k-ìíîæåñòâà èç ïðèìåðà 2.  êîíöå íóëåâîé èòåðàöèè àëãîðèòìà Gen_ k-set ïîëó÷èì P cdfg cdgf cefg cegf defg degf fgc 1 � {( ), ( ), ( ), ( ), ( ), ( ), ( d gfcd fgce gfce fgde gfde ), ( ), ( ), ( ), ( ), ( ) .} . Çäåñü ïîñëåäíèå øåñòü êîðòåæåé ÿâëÿþòñÿ ïåðåñòàíîâêàìè ïàð â ïåðâûõ øåñòè êîðòåæàõ, ÷òî ñîîòâåòñòâóåò ïåðåñòàíîâêàì ýëåìåíòîâ a è b âî ìíîæåñòâå Y0 .  êîíöå ïåðâîé èòåðàöèè Gen_ k-set ïîëó÷èì P W xywz wzxy xywzz 2 123456 123456 123789 123� � {( ), ( ), ( ), ( 789 456789 456789 123456 wzxy xywz wzxy xywz w ), ( ), ( ), ( ), ( zxy xywz wzxy xywz 123456 123789 123789 456789 ), ( ), ( ), ( ), ( )wzxy456789 }. Èç (8) ñëåäóåò, ÷òî äëÿ ãåíåðàöèè áàçîâûõ ìíîæåñòâ íóæíî ( ) (2 2 2 3� � � � � � � � � � � � � � � � �2 2 3 1 3 1 3 1 3 1 3 1 29) ( ) âûçîâîâ ôóíêöèè GenBase. Ïî ôîðìó- 104 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 ëå (10) âûçîâ ôóíêöèè replace ïðîèçâîäèëñÿ ( ( )) ( ( ))2 3 2 12 1 1 1 1 1 24� � � � � � � � � ðàçà. Ïîëó÷åííîå k-ìíîæåñòâî ñîäåðæèò 12 ýëåìåíòîâ, ÷òî ñîâïàäàåò ñ ðàñ÷åòàìè ïî ôîðìóëå (4). ÇÀÊËÞ×ÅÍÈÅ Â íàñòîÿùåé ðàáîòå ïðåäëîæåí îáùèé ïîäõîä ê ãåíåðàöèè êîìïîçèöèîííûõ k-îáðàçîâ êîìáèíàòîðíûõ ìíîæåñòâ (k-ìíîæåñòâ) íà îñíîâå åäèíîãî ïîäõîäà ê ãåíåðàöèè áàçîâûõ êîìáèíàòîðíûõ ìíîæåñòâ. Àëãîðèòì ãåíåðàöèè áàçîâûõ ìíîæåñòâ ïîçâîëÿåò ãåíåðèðîâàòü âñåâîçìîæ- íûå êîìáèíàòîðíûå ìíîæåñòâà, äëÿ êîòîðûõ ìîãóò áûòü çàäàíû ïðàâèëà ôîðìè- ðîâàíèÿ ìíîæåñòâà F i . Åñëè òàêèå ïðàâèëà çàäàòü íå óäàåòñÿ, àëãîðèòì ãåíåðà- öèè k-ìíîæåñòâ äîïóñêàåò ïðèìåíåíèå äðóãèõ èçâåñòíûõ àëãîðèòìîâ äëÿ ãåíåðà- öèè áàçîâûõ ìíîæåñòâ. Ïðåèìóùåñòâîì ïðåäëîæåííîãî àëãîðèòìà äëÿ ãåíåðàöèè k-ìíîæåñòâ ÿâëÿ- åòñÿ âîçìîæíîñòü ïîëó÷åíèÿ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ ãåíåðàöèè, ò.å. ìíî- æåñòâ P i íà óðîâíÿõ, ìåíüøèõ k. Äîâîëüíî òðóäíî îïðåäåëèòü ÿâíóþ çàâèñèìîñòü âðåìåíè âûïîëíåíèÿ àëãîðèò- ìà ãåíåðàöèè îò âõîäíûõ äàííûõ, òàê êàê áàçîâûå ìíîæåñòâà ìîãóò ïðèíàäëåæàòü ê ðàçëè÷íûì êëàññàì, èìåþùèì ðàçëè÷íûå ñâîéñòâà è çàâèñèìîñòè ðàçìåðíîñòè îò âõîäíûõ äàííûõ. Îäíàêî äëÿ õàðàêòåðíûõ ñëó÷àåâ, òàêèõ êàê êîìïîçèöèÿ ïåðåñòà- íîâîê, òàêàÿ çàâèñèìîñòü ìîæåò áûòü ïîëó÷åíà. Ðàçðàáîòàííîå ïðîãðàììíîå îáåñ- ïå÷åíèå ïîçâîëÿåò ãåíåðèðîâàòü k-ìíîæåñòâà ðàçëè÷íîé ñëîæíîñòè. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. K n u t h D . The art of computer programming. Vol. 4. Fascicle 2: Generating all tuples and permu- tations. — Boston: Addison-Wesley, 2005. — 144 p. 2. K n u t h D .The art of computer programming. Vol. 4. Fascicle 3: Generating all combinations and partitions. — Boston: Addison-Wesley, 2005. — 160 ð. 3. K r e h e r D . L . , S t i n s o n D . R . Combinatorial algorithms: Generation enumeration and search. — CRC Press, 1999. — 329 p. 4. B o n a M . Combinatorics of permutations. — Boston: Chapman Hall-CRC, 2004. — 383 p. 5. R u s k e y F . Combinatorial generation, Dept. of Comput. Sci. Univ. of Victoria, Canada, 1j-CSC 425/20. — 2003. — 289 p. 6. K o r s h J . F . , L a F o l l e t t e P . S . Loopless array generation of multiset permutations // The Comput. Journ. — 2004. — 47, N 5. — P. 612–621. 7. Ñ å ì å í î â à Í .  . , Ê î ë å ÷ ê è í à Ë . Í . Ìíîãîêðèòåðèàëüíûå çàäà÷è êîìáèíàòîðíîé îï- òèìèçàöèè íà ìíîæåñòâå ïîëèðàçìåùåíèé: ïîëèýäðàëüíûé ïîäõîä ê ðåøåíèþ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 3. — Ñ. 118–126. 8. Å ì å ö Î . À . , Å ì å ö Å . Ì . Ìîäèôèêàöèÿ ìåòîäà êîìáèíàòîðíîãî îòñå÷åíèÿ â çàäà÷àõ îïòè- ìèçàöèè íà âåðøèííî ðàñïîëîæåííûõ ìíîæåñòâàõ // Òàì æå. — 2009. — ¹ 5. — Ñ. 129–136. 9. Ä î í å ö à . À . , Ê î ë å ÷ ê è í à Ë . Í . Ìåòîä óïîðÿäî÷åíèÿ çíà÷åíèé ëèíåéíîé ôóíêöèè íà ìíîæåñòâå ïåðåñòàíîâîê // Òàì æå. — 2009. — ¹ 2. — Ñ. 50–61. 10. à ð å á å í í è ê È .  . , Ï à í ê ð à ò î â À .  . , × ó ã à é À . Ì . , Á à ð à í î â À .  . Óïàêîâêà n-ìåðíûõ ïàðàëëåëåïèïåäîâ ñ âîçìîæíîñòüþ èçìåíåíèÿ èõ îðòîãîíàëüíîé îðèåíòàöèè â n-ìåðíîì ïàðàëëåëåïèïåäå // Òàì æå. — 2010. — ¹ 5. — Ñ. 122–131. 11. Ñ ò î ÿ í Þ . à . , à ð å á å í í è ê È .  . Êîìïîçèöèîííûå îáðàçû êîìáèíàòîðíûõ ìíîæåñòâ è íåêîòîðûå èõ ñâîéñòâà // Ïðîáëåìû ìàøèíîñòðîåíèÿ. — 2005. — 8, ¹ 3. — Ñ. 56–62. 12. Ñ ò î ÿ í Þ . à . , à ð å á å í í è ê È .  . Îïèñàíèå êëàññîâ êîìáèíàòîðíûõ êîíôèãóðàöèé íà îñíîâå îòîáðàæåíèé // Äîï. ÍÀÍ Óêðà¿íè. — 2008. — ¹ 10. — Ñ. 28 –31. 13. S t o y a n Y u . G . , G r e b e n n i k I . V . Description and generation of combinatorial sets having special characteristics // Intern. J. of Biomed. Soft Comput. and Human Sci., Spec. Vol. «Bilevel Pro- gramming, Optimization Methods, and Applications to Economics». — 2011. — 18, N 1. — P. 85–90. 14. à ð å á å í í è ê È .  . Îïèñàíèå è ãåíåðàöèÿ ïåðåñòàíîâîê, ñîäåðæàùèõ öèêëû // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2010. — ¹ 6. — Ñ. 97–105. 15. Ë è ï ñ ê è é  . Êîìáèíàòîðèêà äëÿ ïðîãðàììèñòîâ. — Ì.: Ìèð, 1988. — 213 ñ. Ïîñòóïèëà 29.03.2011 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2012, ¹ 6 105 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Gray Gamma 2.2) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.3 /CompressObjects /Off /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages false /CreateJDFFile false /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /LeaveColorUnchanged /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams true /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts false /TransferFunctionInfo /Apply /UCRandBGInfo /Remove /UsePrologue false /ColorSettingsFile (Color Management Off) /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 290 /ColorImageMinResolutionPolicy /Warning /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 600 /ColorImageDepth 8 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.01667 /EncodeColorImages true /ColorImageFilter /FlateEncode /AutoFilterColorImages false /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 290 /GrayImageMinResolutionPolicy /Warning /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 600 /GrayImageDepth 8 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 2.03333 /EncodeGrayImages true /GrayImageFilter /FlateEncode /AutoFilterGrayImages false /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 800 /MonoImageMinResolutionPolicy /Warning /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 2400 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /PDFX3:2003 ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError false /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox false /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile (None) /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /Description << /CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000500044004600206587686353ef901a8fc7684c976262535370673a548c002000700072006f006f00660065007200208fdb884c9ad88d2891cf62535370300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002> /CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef653ef5728684c9762537088686a5f548c002000700072006f006f00660065007200204e0a73725f979ad854c18cea7684521753706548679c300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002> /DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002000740069006c0020006b00760061006c00690074006500740073007500640073006b007200690076006e0069006e006700200065006c006c006500720020006b006f007200720065006b007400750072006c00e60073006e0069006e0067002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e> /ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f0073002000640065002000410064006f0062006500200050004400460020007000610072006100200063006f006e00730065006700750069007200200069006d0070007200650073006900f3006e002000640065002000630061006c006900640061006400200065006e00200069006d0070007200650073006f0072006100730020006400650020006500730063007200690074006f00720069006f00200079002000680065007200720061006d00690065006e00740061007300200064006500200063006f00720072006500630063006900f3006e002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e> /FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f007500720020006400650073002000e90070007200650075007600650073002000650074002000640065007300200069006d007000720065007300730069006f006e00730020006400650020006800610075007400650020007100750061006c0069007400e90020007300750072002000640065007300200069006d007000720069006d0061006e0074006500730020006400650020006200750072006500610075002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e> /ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f006200650020005000440046002000700065007200200075006e00610020007300740061006d007000610020006400690020007100750061006c0069007400e00020007300750020007300740061006d00700061006e0074006900200065002000700072006f006f0066006500720020006400650073006b0074006f0070002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e> /JPN <FEFF9ad854c18cea51fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e30593002537052376642306e753b8cea3092670059279650306b4fdd306430533068304c3067304d307e3059300230c730b930af30c830c330d730d730ea30f330bf3067306e53705237307e305f306f30d730eb30fc30d57528306b9069305730663044307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e30593002> /KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020b370c2a4d06cd0d10020d504b9b0d1300020bc0f0020ad50c815ae30c5d0c11c0020ace0d488c9c8b85c0020c778c1c4d560002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e> /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken voor kwaliteitsafdrukken op desktopprinters en proofers. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200066006f00720020007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c00690074006500740020007000e500200062006f007200640073006b0072006900760065007200200065006c006c00650072002000700072006f006f006600650072002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e> /PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020007000610072006100200069006d0070007200650073007300f5006500730020006400650020007100750061006c0069006400610064006500200065006d00200069006d00700072006500730073006f0072006100730020006400650073006b0074006f00700020006500200064006900730070006f00730069007400690076006f0073002000640065002000700072006f00760061002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e> /SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f0074002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a00610020006c0061006100640075006b006100730074006100200074007900f6007000f60079007400e400740075006c006f0073007400750073007400610020006a00610020007600650064006f007300740075007300740061002000760061007200740065006e002e00200020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e> /SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740020006600f600720020006b00760061006c00690074006500740073007500740073006b0072006900660074006500720020007000e5002000760061006e006c00690067006100200073006b0072006900760061007200650020006f006300680020006600f600720020006b006f007200720065006b007400750072002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e> /DEU <FEFF004a006f0062006f007000740069006f006e007300200066006f00720020004100630072006f006200610074002000440069007300740069006c006c0065007200200037002e000d00500072006f006400750063006500730020005000440046002000660069006c0065007300200077006800690063006800200061007200650020007500730065006400200066006f0072002000680069006700680020007100750061006c0069007400790020007000720069006e00740069006e0067002e000d0028006300290020003200300031003000200053007000720069006e006700650072002d005600650072006c0061006700200047006d006200480020> /ENU (Use these settings to create Adobe PDF documents for quality printing on desktop printers and proofers. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /NoConversion /DestinationProfileName () /DestinationProfileSelector /NA /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure true /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles true /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /NA /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /LeaveUntagged /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [2834.646 2834.646] >> setpagedevice

Similar Items