Поиск максимальных интервалов области признакового пространства в лексикографическом порядке
В статье изучаются свойства индикаторных векторов интервалов признакового пространства, рассматриваются алгоритмы поиска замкнутых индикаторных векторов и индикаторных векторов, порождающих максимальные интервалы заданной области признакового пространства....
Збережено в:
| Дата: | 2010 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Кримський науковий центр НАН України і МОН України
2010
|
| Назва видання: | Таврический вестник информатики и математики |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/18198 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Поиск максимальных интервалов области признакового пространства в лексикографическом порядке / А.В. Ильченко // Таврический вестник информатики и математики. — 2010. — № 2. — С. 57-69. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-18198 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-181982011-03-19T12:04:10Z Поиск максимальных интервалов области признакового пространства в лексикографическом порядке Ильченко, А.В. В статье изучаются свойства индикаторных векторов интервалов признакового пространства, рассматриваются алгоритмы поиска замкнутых индикаторных векторов и индикаторных векторов, порождающих максимальные интервалы заданной области признакового пространства. У статті вивчаються властивості індикаторних векторів інтервалів ознакового простору, розглядаються алгоритми пошуку замкнутих індикаторних векторів і індикаторних векторів, що породжують максимальні інтервали заданої області простору ознак. The properties of characteristic vector families for intervals of the feature space are under investigation. The search algorithms for the closed characteristic vectors and vectors generating the maximum intervals of the specified feature space region are considered in the paper. 2010 Article Поиск максимальных интервалов области признакового пространства в лексикографическом порядке / А.В. Ильченко // Таврический вестник информатики и математики. — 2010. — № 2. — С. 57-69. — Бібліогр.: 6 назв. — рос. 1729-3901 http://dspace.nbuv.gov.ua/handle/123456789/18198 517.9 ru Таврический вестник информатики и математики Кримський науковий центр НАН України і МОН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| description |
В статье изучаются свойства индикаторных векторов интервалов признакового пространства, рассматриваются алгоритмы поиска замкнутых индикаторных векторов и индикаторных векторов, порождающих максимальные интервалы заданной области признакового пространства. |
| format |
Article |
| author |
Ильченко, А.В. |
| spellingShingle |
Ильченко, А.В. Поиск максимальных интервалов области признакового пространства в лексикографическом порядке Таврический вестник информатики и математики |
| author_facet |
Ильченко, А.В. |
| author_sort |
Ильченко, А.В. |
| title |
Поиск максимальных интервалов области признакового пространства в лексикографическом порядке |
| title_short |
Поиск максимальных интервалов области признакового пространства в лексикографическом порядке |
| title_full |
Поиск максимальных интервалов области признакового пространства в лексикографическом порядке |
| title_fullStr |
Поиск максимальных интервалов области признакового пространства в лексикографическом порядке |
| title_full_unstemmed |
Поиск максимальных интервалов области признакового пространства в лексикографическом порядке |
| title_sort |
поиск максимальных интервалов области признакового пространства в лексикографическом порядке |
| publisher |
Кримський науковий центр НАН України і МОН України |
| publishDate |
2010 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/18198 |
| citation_txt |
Поиск максимальных интервалов области признакового пространства в лексикографическом порядке / А.В. Ильченко // Таврический вестник информатики и математики. — 2010. — № 2. — С. 57-69. — Бібліогр.: 6 назв. — рос. |
| series |
Таврический вестник информатики и математики |
| work_keys_str_mv |
AT ilʹčenkoav poiskmaksimalʹnyhintervalovoblastipriznakovogoprostranstvavleksikografičeskomporâdke |
| first_indexed |
2025-07-02T19:18:11Z |
| last_indexed |
2025-07-02T19:18:11Z |
| _version_ |
1836563972833148928 |
| fulltext |
ÓÄÊ 517.9ÏÎÈÑÊ ÌÀÊÑÈÌÀËÜÍÛÕ ÈÍÒÅ�ÂÀËΠÎÁËÀÑÒÈÏ�ÈÇÍÀÊÎÂÎ�Î Ï�ÎÑÒ�ÀÍÑÒÂÀ  ËÅÊÑÈÊÎ��ÀÔÈ×ÅÑÊÎÌÏÎ�ßÄÊÅ
Èëü÷åíêî À.Â.Òàâðè÷åñêèé íàöèîíàëüíûé óíèâåðñèòåò èì. Â.È. Âåðíàäñêîãî�àêóëüòåò ìàòåìàòèêè è èí�îðìàòèêèïð-ò Âåðíàäñêîãî, 4, ã. Ñèì�åðîïîëü, 95007, Óêðàèíàe-mail: il
h�
rimea.eduAbstra
t. The properties of
hara
teristi
ve
tor families for intervals of the feature spa
e areunder investigation. The sear
h algorithms for the
losed
hara
teristi
ve
tors and ve
tors generatingthe maximum intervals of the spe
i�ed feature spa
e region are
onsidered in the paper.ÂâåäåíèåÀëãîðèòìû è ìåòîäû êëàñòåðíîãî àíàëèçà âî ìíîãîì ñîñòàâëÿþò îñíîâó ïðèëî-æåíèé àíàëèçà äàííûõ. �îñò îáú¼ìà äàííûõ, ïîäëåæàùèõ îáðàáîòêå, ïðåäúÿâëÿåòðÿä òðåáîâàíèé ê èñïîëüçóåìûì àëãîðèòìàì êëàñòåðèçàöèè: âîçìîæíîñòü íàõîäèòüêëàñòåðû â ïðîñòðàíñòâàõ áîëüøîé ðàçìåðíîñòè, íàãëÿäíîñòü, ë¼ãêîñòü èíòåðïðåòà-öèè ïîëó÷åííûõ ðåçóëüòàòîâ, îòñóòñòâèå íåîáõîäèìîñòè ïðèâåäåíèÿ èñõîäíûõ äàí-íûõ ê êàêîìó-ëèáî êàíîíè÷åñêîìó âèäó è òàê äàëåå. íåêîòîðûõ ñëó÷àÿõ âûïîëíåíèå ìíîãèõ èç ýòèõ òðåáîâàíèé ìîãóò îáåñïå÷èòüàëãîðèòìû è ìåòîäû àíàëèçà �îðìàëüíûõ ïîíÿòèé [1, 2, 6℄, ñåòî÷íûå ìåòîäû.Öåëüþ ñòàòüè ÿâëÿåòñÿ ðàññìîòðåíèå ïîíÿòèÿ èíäèêàòîðíîãî âåêòîðà èíòåðâà-ëà ïðèçíàêîâîãî ïðîñòðàíñòâà, èçó÷åíèå ñâîéñòâ ñåìåéñòâà òàêèõ âåêòîðîâ, ïîñòðî-åíèå è îáîñíîâàíèå àëãîðèòìà ïîèñêà çàìêíóòûõ èíäèêàòîðíûõ âåêòîðîâ è èíäè-êàòîðíûõ âåêòîðîâ, ïîðîæäàþùèõ ìàêñèìàëüíûå èíòåðâàëû çàäàííîé îáëàñòè ïðè-çíàêîâîãî ïðîñòðàíñòâà.1. Ìàêñèìàëüíûå èíòåðâàëû îáëàñòè ïðèçíàêîâîãîïðîñòðàíñòâàfA0; A1; : : : ; An�1; g � ñåìåéñòâî ìíîæåñòâ, êàæäîå èç êîòîðûõ êîíå÷íî è ëèíåé-íî óïîðÿäî÷åííî. Ïðÿìîå ïðîèçâåäåíèå ìíîæåñòâ ñåìåéñòâà A îïðåäåëÿåò n-ìåðíîåïðèçíàêîâîå ïðîñòðàíñòâî S:S = A0 � A1 � � � � � An�1:Èíîãäà íà îáîçíà÷åíèå Aj ññûëàþòñÿ êàê íà èçìåðåíèå (àòðèáóò, äîìåí) ïðè-çíàêîâîãî ïðîñòðàíñòâà. Ïîñêîëüêó ìíîæåñòâî çíà÷åíèé ïî êàæäîìó Aj ëèíåéíîóïîðÿäî÷åííî, ìîæíî ãîâîðèòü î ïîëîæèòåëüíîì è îòðèöàòåëüíîì íàïðàâëåíèÿõ ïîñîîòâåòñòâóþùåìó èçìåðåíèþ.ni = jAij, i = 0; 1; : : : ; n� 1 � ìîùíîñòü äîìåíà Ai.
58 Èëü÷åíêî À.Â.Ýëåìåíòû äîìåíà Ai ìîæíî ïåðåíóìåðîâàòü è, â äàëüíåéøåì, âñåãäà ñ÷èòàòü,÷òî Ai = f0; 1; : : : ; n� 1g.Ïóñòü H � S � íåêîòîðàÿ îáëàñòü ïðèçíàêîâîãî ïðîñòðàíñòâà S. Èíòåðâàë I,ñîäåðæàùèéñÿ â îáëàñòè H, íàçûâàåòñÿ ìàêñèìàëüíûì èíòåðâàëîì îáëàñòè H, åñëèíå ñóùåñòâóåò åãî ñîáñòâåííîãî íàäèíòåðâàëà, ñîäåðæàùåãîñÿ â îáëàñòè H.Ìíîæåñòâî âñåõ ìàêñèìàëüíûõ èíòåðâàëîâ îáëàñòè H íàçûâàåòñÿ ñîêðàùåííîéèíòåðâàëüíîé ñòðóêòóðîé ýòîé îáëàñòè [4℄. Êàæäóþ îáëàñòü H ïðèçíàêîâîãî ïðî-ñòðàíñòâà S ìîæíî ïðåäñòàâèòü â âèäå îáúåäèíåíèÿ èíòåðâàëîâ åå ñîêðàùåííîé èí-òåðâàëüíîé ñòðóêòóðû.Óäîáíî òî÷êè îáëàñòè H íàçûâàòü åäèíè÷íûìè òî÷êàìè (1-òî÷êè) òàê, êàê åñëèáû áûëà çàäàíà èíäèêàòîðíàÿ �óíêöèÿ ýòîé îáëàñòè, à èíòåðâàëû îáëàñòè H íàçû-âàòü 1-èíòåðâàëàìè. Òå òî÷êè ïðèçíàêîâîãî ïðîñòðàíñòâà, êîòîðûå íå ñîäåðæàòñÿ âîáëàñòè H, áóäåì íàçûâàòü 0-òî÷êàìè ïðèçíàêîâîãî ïðîñòðàíñòâà.2. Âåêòîðíîå ïðåäñòàâëåíèå èíòåðâàëîâÓ ïðîñòðàíñòâà S, ðàçìåðíîñòü êîòîðîãî n, èìååòñÿ 2n íàïðàâëåíèé.  êàæ-äîì èçìåðåíèè ïî äâà íàïðàâëåíèÿ: îòðèöàòåëüíîå è ïîëîæèòåëüíîå. Ëþáîé èíòåð-âàë ìîæåò áûòü ïîëó÷åí èç èíòåðâàëà, ïðåäñòàâëÿþùåãî ïðîñòðàíñòâî S, óäàëåíèåìíåêîòîðîãî ÷èñëà çíà÷åíèé èç äîìåíîâ, ïî ñîîòâåòñòâóþùèì íàïðàâëåíèÿì.Äëÿ îïèñàíèÿ èíòåðâàëà áóäåò èñïîëüçîâàòüñÿ âåêòîð äëèíû 2n:A = (a0; a1; : : : ; a2i; a2i+1; : : : ; a2n�2; a2n�1) (1)Êîìïîíåíòû òàêîãî âåêòîðà ðàññìàòðèâàþòñÿ ïàðàìè. Êàæäàÿ ïàðà ñîîòâåòñòâó-åò îäíîìó èç èçìåðåíèé ïðèçíàêîâîãî ïðîñòðàíñòâà. Êàæäàÿ êîìïîíåíòà òàêîé ïàðûîòâå÷àåò îäíîìó èç íàïðàâëåíèé ñîîòâåòñòâóþùåãî èçìåðåíèÿ.Ïàðà a2i; a2i+1 ñîîòâåòñòâóåò i-ìó èçìåðåíèþ.Êîìïîíåíòà a2i îòâå÷àåò îòðèöàòåëüíîìó íàïðàâëåíèþ i-ãî èçìåðåíèÿ.Êîìïîíåíòà a2i+1 - ïîëîæèòåëüíîìó íàïðàâëåíèþ.Çíà÷åíèå êàæäîé êîìïîíåíòû òàêîé ïàðû - ÷èñëî çíà÷åíèé, óäàë¼ííûõ èç äîìå-íà Ai ïî ñîîòâåòñòâóþùåìó íàïðàâëåíèþ.Òàêîé âåêòîð áóäåì íàçûâàòü èíäèêàòîðíûì âåêòîðîì èíòåðâàëà èëè âåêòîðíûìîïèñàíèåì èíòåðâàëà.Åñëè âåêòîð A ÿâëÿåòñÿ èíäèêàòîðíûì âåêòîðîì èíòåðâàëà I, òî óäîáíî ãîâî-ðèòü, ÷òî âåêòîð A ïîðîæäàåò èíòåðâàë I (îáîçíà÷åíèå A(I)), à èíòåðâàë I ïîðîæ-äàåòñÿ âåêòîðîì A (îáîçíà÷åíèå I(A)).Êîãäà âåêòîð A ÿâëÿåòñÿ îïèñàíèåì íåïóñòîãî èíòåðâàëà, òî äëÿ êàæäîãî èç-ìåðåíèÿ ïðèçíàêîâîãî ïðîñòðàíñòâà ñóììà êîìïîíåíò ïî ýòîìó èçìåðåíèþ ìåíüøåìîùíîñòè äîìåíà çíà÷åíèé ýòîãî èçìåðåíèÿ:a2i + a2i+1 < ni; i = 0; 1; : : : ; n� 1: (2)Åñëè äëÿ êàêîãî-ëèáî èç èçìåðåíèé a2i+a2i+1 � ni, ýòî îçíà÷àåò, ÷òî òàêîé âåêòîðÿâëÿåòñÿ îïèñàíèåì ïóñòîãî ïîäìíîæåñòâà.Ïðèìå÷àíèå 1. Äëÿ íàñ ïðåäñòàâëÿþò èíòåðåñ íåïóñòûå èíòåðâàëû. Ïîýòîìóâåêòîðà-îïèñàíèÿ, â êîòîðûõ õîòÿ áû äëÿ îäíîãî èçìåðåíèÿ âûïîëíÿåòñÿ óñëîâèå¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2010
Ïîèñê ìàêñèìàëüíûõ èíòåðâàëîâ... 59a2i + a2i+1 � ni, èñêëþ÷àþòñÿ èç ðàññìîòðåíèÿ. Åñëè âñ¼ æå ïîòðåáóåòñÿ èñïîëü-çîâàòü ïóñòîå ïîäìíîæåñòâî, òî â êà÷åñòâå èíäèêàòîðíîãî âåêòîðà áóäåò èñïîëüçî-âàòüñÿ âåêòîð, â êîòîðîì çíà÷åíèå êàæäîé êîìïîíåíòû ðàâíî ìîùíîñòè äîìåíà ïîñîîòâåòñòâóþùåìó èçìåðåíèþ ïðèçíàêîâîãî ïðîñòðàíñòâà, òî åñòü âåêòîð, â êîòîðîìa2i = a2i+1 = ni; i = 0; 1; : : : ; n� 1: (3)
3. Ëåêñèêîãðà�è÷åñêèé ïîðÿäîê íà ìíîæåñòâå èíäèêàòîðíûõâåêòîðîâÎïðåäåëåíèå 1. Ïóñòü A;B � èíäèêàòîðíûå âåêòîðà. Âåêòîð A ëåêñè÷åñêè ïðåä-øåñòâóåò âåêòîðó B, åñëè ñóùåñòâóåò íàïðàâëåíèå k òàêîå, ÷òî ak < bk, à ïî âñåìíàïðàâëåíèÿì, ïðåäøåñòâóþùèì íàïðàâëåíèþ k, çíà÷åíèÿ êîìïîíåíò âåêòîðîâ Aè B ñîâïàäàþò: A . B , 9k(ak < bk; 8j < k(aj = bj)): (4)Äëÿ ñîêðàùåíèÿ çàïèñè áóäåò èñïîëüçîâàòüñÿ ñëåäóþùåå îáîçíà÷åíèå:A .k B , ak < bk; 8j < k(aj = bj): (5)Òîãäà, îïðåäåëåíèå ëåêñè÷åñêîãî ïîðÿäêà çàïèøåòñÿ â âèäåA . B , 9k(A .k B): (6)Óäîáíî èíäèêàòîðíûå âåêòîðà ïåðåáèðàòü â ëåêñè÷åñêîì ïîðÿäêå, íà÷èíàÿ ñ âåê-òîðà (0; 0; : : : ; 0; 0), êîòîðûé ÿâëÿåòñÿ èíäèêàòîðíûì âåêòîðîì ïðèçíàêîâîãî ïðî-ñòðàíñòâà S.Àëãîðèòì âû÷èñëåíèÿ âåêòîðà, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèì çà òåêó-ùèì âåêòîðîì, îñíîâàí íà ñëåäóþùèõ ñîîáðàæåíèÿõ.Ëåêñè÷åñêèé ïîðÿäîê � ïîðÿäîê ëèíåéíûé. Ïîýòîìó âåêòîðà, ðàñïîëîæåííûåâ ëåêñè÷åñêîì ïîðÿäêå, ìîæíî ïðîíóìåðîâàòü ÷èñëàìè 0; 1; : : : ; íà÷èíàÿ ñ âåêòî-ðà (0; 0; : : : ; 0; 0). Òîãäà ïåðåõîä îò òåêóùåãî âåêòîðà, ê âåêòîðó íåïîñðåäñòâåííîëåêñè÷åñêè ñëåäóþùèì çà òåêóùèì, îñóùåñòâëÿåòñÿ ïðèáàâëåíèåì åäèíèöû ê íî-ìåðó òåêóùåãî âåêòîðà è çàïèñè âåêòîðíîãî ïðåäñòàâëåíèÿ ïîëó÷åííîãî ÷èñëà. Òîåñòü, èíäèêàòîðíûé âåêòîð ìîæíî ðàññìàòðèâàòü êàê ïîçèöèîííóþ çàïèñü íåîòðè-öàòåëüíîãî öåëîãî ÷èñëà.Îòëè÷èÿ îò îáû÷íîãî ïîçèöèîííîãî ïðåäñòàâëåíèÿ ÷èñåë çàêëþ÷àþòñÿ â ñëåäó-þùåì:1. Äëÿ êàæäîé ïàðû ïîçèöèé, ñîîòâåòñòâóþùèõ îäíîìó èç èçìåðåíèé, èñïîëüçó-åòñÿ ñâî¼ îñíîâàíèå, êîòîðîå ñîâïàäàåò ñ ìîùíîñòüþ äîìåíà ýòîãî èçìåðåíèÿ.2. Äëÿ êàæäîé ïàðû ïîçèöèé, ñîîòâåòñòâóþùèõ îäíîìó èç èçìåðåíèé, äîëæíîâûïîëíÿòüñÿ îãðàíè÷åíèå (2), ÷òî ïîçâîëÿåò èñêëþ÷èòü èç ðàññìîòðåíèÿ ïó-ñòûå èíòåðâàëû. ¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2010
60 Èëü÷åíêî À.Â.4. Âû÷èñëåíèå íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùåãîèíäèêàòîðíîãî âåêòîðàÏñåâäîêîä àëãîðèòìà.Âõîä. A � òåêóùèé èíäèêàòîðíûé âåêòîð;Âûõîä. A+ 1 � èíäèêàòîðíûé âåêòîð, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèéçà âåêòîðîì A.Ìåòîä.1) i = n� 12) while i � 03) a2i+1 = a2i+1 + 14) if a2i + a2i+1 < ni then return A5) a2i+1 = 06) a2i = a2i + 17) if a2i < ni then return A8) a2i = 09) i = i� 110) end while11) return AÏðèâåäåííûé ïñåâäîêîä îñíîâàí íà ñîîáðàæåíèÿõ ïðåäøåñòâóþùåãî ðàçäåëà. äàëüíåéøåì, âû÷èñëåíèå âåêòîðà, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùåãî çàòåêóùèì âåêòîðîì A, áóäåò îáîçíà÷àòüñÿ A+ 1.5. Çàìêíóòûå èíòåðâàëû ïðèçíàêîâîãî ïðîñòðàíñòâàÏóñòü A � S � íåêîòîðîå ïîäìíîæåñòâî òî÷åê ïðèçíàêîâîãî ïðîñòðàíñòâà.Îáîçíà÷èì [A℄ íàèìåíüøèé èíòåðâàë ïðîñòðàíñòâà S, ñîäåðæàùèé ïîäìíîæåñòâîòî÷åê A (èíòåðâàëüíîå çàìûêàíèå, èíòåðâàëüíàÿ îáîëî÷êà ìíîæåñòâà A).Îïåðàöèÿ èíòåðâàëüíîãî çàìûêàíèÿ îáëàäàåò îáû÷íûìè ñâîéñòâàìè îïåðàöèèçàìûêàíèÿ [5℄: A � B ) [A℄ � [B℄; (7)A � [A℄; (8)[[A℄℄ = [A℄: (9)Îáîçíà÷èì I(S) � ñåìåéñòâî âñåõ èíòåðâàëîâ ïðèçíàêîâîãî ïðîñòðàíñòâà S.I 2 I(S) � �èêñèðîâàííûé èíòåðâàë èç ýòîãî ñåìåéñòâà.I \ H � ïîäìíîæåñòâî òî÷åê îáëàñòè H, ñîäåðæàùèõñÿ â èíòåðâàëå I (1-òî÷êèïðîñòðàíñòâà S, ñîäåðæàùèåñÿ â èíòåðâàëå I).[I \H℄ � íàèìåíüøèé èíòåðâàë ïðîñòðàíñòâà S, ñîäåðæàùèé ïîäìíîæåñòâî I\H(èíòåðâàëüíîå çàìûêàíèå ïîäìíîæåñòâà 1-òî÷åê ïðîñòðàíñòâà S, ñîäåðæàùèõñÿ âèíòåðâàëå I).Îïðåäåëåíèå 2. Èíòåðâàë I 2 I(S) íàçûâàåòñÿ çàìêíóòûì (îòíîñèòåëüíî îáëàñòèH)), åñëè [I \H℄ = I. ¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2010
Ïîèñê ìàêñèìàëüíûõ èíòåðâàëîâ... 61Óòâåðæäåíèå 1. Êàæäûé 1-èíòåðâàë ÿâëÿåòñÿ çàìêíóòûì èíòåðâàëîì.Äîêàçàòåëüñòâî. Ïóñòü I 2 I(S) è I � H.Òàê êàê I � H, òî I \H = I è, ñëåäîâàòåëüíî, [I \H℄ = [I℄.Ýòî, ñ ó÷¼òîì î÷åâèäíîãî ðàâåíñòâà [I℄ = I, ïîçâîëÿåò ñäåëàòü âûâîä,÷òî [I \H℄ = I. �Ïðèìå÷àíèå 2.  ñèëó óòâåðæäåíèÿ 1, ìàêñèìàëüíûå 1-èíòåðâàëû èìååò ñìûñëèñêàòü ñðåäè çàìêíóòûõ èíòåðâàëîâ.Ïðèìå÷àíèå 3. Çàìêíóòûå èíòåðâàëû èíòåðåñíû è ñàìè ïî ñåáå. Íàïðèìåð, â àíà-ëèçå �îðìàëüíûõ ïîíÿòèé [1℄, [2℄ èõ ìîæíî ðàññìàòðèâàòüñÿ êàê ñîäåðæàíèÿ ¾èí-òåðâàëüíûõ¿ �îðìàëüíûõ ïîíÿòèé.  çàäà÷àõ ðàñïîçíàâàíèÿ îáðàçîâ çàìêíóòûå èí-òåðâàëû ìîãóò áûòü èñïîëüçîâàíû äëÿ ïîñòðîåíèÿ ðàçëè÷íûõ ãèïîòåç [6℄.6. �åø¼òêà èíòåðâàëîâ è ðåø¼òêà èíäèêàòîðíûõ âåêòîðîâÄëÿ ñåìåéñòâà I(S) âûïîëíÿåòñÿ ñâîéñòâî çàìûêàíèÿ [3℄ îòíîñèòåëüíî îïåðàöèèïåðåñå÷åíèÿ. Ïîýòîìó I(S), óïîðÿäî÷åííîå îòíîøåíèåì âêëþ÷åíèÿ �, ÿâëÿåòñÿ ïîë-íîé ðåø¼òêîé.Îáîçíà÷èì A(S) ñåìåéñòâî âñåõ èíäèêàòîðíûõ âåêòîðîâ ïðèçíàêîâîãî ïðîñòðàí-ñòâà S.Ìåæäó ìíîæåñòâàìè I(S) è A(S) ñóùåñòâóåò âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå(ñ ó÷¼òîì ïðèìå÷àíèÿ 1):I(A)$ A(I).Íà âåêòîðàõ ñåìåéñòâà A(S) ñëåäóþùèì îáðàçîì îïðåäåëÿåòñÿ îòíîøåíèå ïðåä-øåñòâîâàíèå �: A � B , I(B) � I(A): (10)Òàê îïðåäåë¼ííîå îòíîøåíèå ïðåäøåñòâîâàíèÿ ÿâëÿåòñÿ îòíîøåíèåì ïîðÿäêà, äâîé-ñòâåííûì ê ïîðÿäêó, îïðåäåëÿåìîìó îòíîøåíèåì âêëþ÷åíèÿ � íà ìíîæåñòâå I(S).Ïîýòîìó, ìíîæåñòâî A(S), óïîðÿäî÷åííîå îòíîøåíèåì �, ÿâëÿåòñÿ äâîéñòâåííûì êðåø¼òêå hI(S);�i è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ ïîëíîé ðåø¼òêîé.Ñ èñïîëüçîâàíèåì ââåäåííîãî îòíîøåíèÿ ïðåäøåñòâîâàíèÿ, îïðåäåëÿþòñÿ îòíî-øåíèÿ ñòðîãîãî < è íåïîñðåäñòâåííîãî � ïðåäøåñòâîâàíèÿ.A < B , A � B è A 6= B.A � B , A < B è �9C 2 A(S) : A < C < B.Óòâåðæäåíèå 2. Ïóñòü A;B 2 A(S).A � B , aj � bj; j = 0; 1; : : : ; 2n� 1: (11)Äîêàçàòåëüñòâî. A � B , I(B) � I(A), ïî êàæäîìó èç 2n íàïðàâëåíèé ïðèçíàêîâîãî ïðîñòðàíñòâà, â èíòåðâàëå I(A)óäàëåíî íå áîëüøå çíà÷åíèé, ÷åì óäàëåíî ïî ñîîòâåòñòâóþùèì íàïðàâëåíèÿì â èí-òåðâàëå I(B), aj � bj; j = 0; 1; : : : ; 2n� 1. �¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2010
62 Èëü÷åíêî À.Â.Èç óòâåðæäåíèÿ 2 ñëåäóåòÓòâåðæäåíèå 3. �åø¼òî÷íûé ïîðÿäîê � íà ìíîæåñòâå èíäèêàòîðíûõ âåêòîðîâñ ñîõðàíåíèåì ïîðÿäêà âëîæåí â ëåêñè÷åñêèé ïîðÿäîê .:A � B ) A . B: (12)Òàê æå, èç óòâåðæäåíèÿ 2 ñëåäóåòÓòâåðæäåíèå 4. A � B , 9 !k(ak + 1 = bk; 8j 6= k(aj = bj)): (13)7. Îïåðàòîð çàìûêàíèÿ íà ðåøåòêå èíäèêàòîðíûõ âåêòîðîâÏóñòü H � S � îáëàñòü ïðîñòðàíñòâà S. Íà ìíîæåñòâå A(S) îïðåäåëèì îïåðà-òîð 00, êîòîðûé êàæäîìó èíäèêàòîðíîìó âåêòîðó A ñòàâèò â ñîîòâåòñòâèå èíäèêàòîð-íûé âåêòîð A00, ïîðîæäàþùèé íàèìåíüøèé èíòåðâàë, ñîäåðæàùèé òå æå 1-òî÷êè, ÷òîè èíòåðâàë, ïîðîæäàåìûé èñõîäíîé âåêòîðîì A.�åçóëüòàò äåéñòâèÿ îïåðàòîðà 00, óäîáíî ïðåäñòàâèòü â âèäå ñëåäóþùåé ïîñëåäî-âàòåëüíîñòè øàãîâ:A) I(A)) I(A) \H ) [I(A) \H℄) A00: ñèëó ñâîåãî îïðåäåëåíèÿ, îïåðàòîð 00' îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè, àíà-ëîãè÷íûìè ñâîéñòâàì (7)� (9): A � B ) A00 � B00; (14)A � A00; (15)(A00)00 = A00; (16)è, ñëåäîâàòåëüíî, ÿâëÿåòñÿ îïåðàòîðîì çàìûêàíèÿ [3℄ íà ìíîæåñòâå A(S).Âåêòîð A00 íàçûâàåòñÿ çàìûêàíèåì âåêòîðà A.Îïðåäåëåíèå 3. Èíäèêàòîðíûé âåêòîð A íàçûâàåòñÿ çàìêíóòûì, åñëè îí ñîâïàäàåòñî ñâîèì çàìûêàíèåì, òî åñòü, åñëè A00 = A. ñèëó îïðåäåëåíèÿ îïåðàòîðà çàìûêàíèÿ, èìåííî çàìêíóòûå èíäèêàòîðíûå âåê-òîðà ïîðîæäàþò èíòåðåñóþùèå íàñ çàìêíóòûå èíòåðâàëû.Åñëè ó âåêòîðà A åãî êîìïîíåíòû îáîçíà÷åíû êàê aj; j = 0; 1; : : : ; 2n � 1, òîñîîòâåòñòâóþùèå êîìïîíåíòû âåêòîðà A00 áóäóò îáîçíà÷àòüñÿ a00j ; j = 0; 1; : : : ; 2n� 1. ñèëó ìîíîòîííîñòè îïåðàòîðà çàìûêàíèÿ (14) è óòâåðæäåíèÿ 2, êîìïîíåíòûâåêòîðîâ A è A00 óäîâëåòâîðÿþò óñëîâèþaj � a00j ; j = 0; 1; : : : ; 2n� 1: (17)Ïóñòü A 2 A(S) è A .m A+ 1.  ýòîì ñëó÷àåA = (a0; : : : ; am; am+1; : : : ; a2n�1) è A+ 1 = (a0; : : : ; am + 1; 0; : : : ; 0), ãäåm = maxfj : aj 6= 0; j = 0; 1; : : : ; 2n� 1; g (18)òî åñòü, m � íàèáîëüøåå íàïðàâëåíèå ïðèçíàêîâîãî ïðîñòðàíñòâà, ïî êîòîðîìó êîì-ïîíåíòà aj âåêòîðà A+ 1 îòëè÷íà îò íóëÿ.¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2010
Ïîèñê ìàêñèìàëüíûõ èíòåðâàëîâ... 63Îáîçíà÷èì M � ïîäìíîæåñòâî âñåõ âåêòîðîâ, êîòîðûì âåêòîð A ïðåäøåñòâóåòïî êîìïîíåíòå m: M = fD 2 A(S) j A .m Dg: (19)Ëþáîé âåêòîð C 2 A(S) òàêîé, ÷òî A .k C è k < m íàõîäèòñÿ ëåêñè÷åñêè äàëüøå îòâåêòîðà A, ÷åì êàæäûé èç âåêòîðîâ ïîäìíîæåñòâà M . Ïîýòîìó, èìåííî ñðåäè âåê-òîðîâ ïîäìíîæåñòâà M ñëåäóåò èñêàòü çàìêíóòûé âåêòîð, ëåêñè÷åñêè áëèæàéøèé êâåêòîðó A. È òîëüêî, åñëè â ïîäìíîæåñòâå M èñêîìîãî âåêòîðà íå îêàæåòñÿ, ïåðå-õîäèòü ê âåêòîðàì, êîòîðûì âåêòîð A ëåêñè÷åñêè ïðåäøåñòâóåò ïî íàïðàâëåíèÿì,ìåíüøèì íàïðàâëåíèÿ m. ìíîæåñòâå A(S), óïîðÿäî÷åííîì îòíîøåíèåì ëåêñè÷åñêîãî ïîðÿäêà, ïîäìíîæå-ñòâî M ÿâëÿåòñÿ èíòåðâàëîì. Îáîçíà÷èì ýòîò èíòåðâàë [B;B++℄. Íèæíÿÿ ãðàíèöàýòîãî èíòåðâàëà B - âåêòîð, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèé çà âåêòîðîì A,òî åñòü, B = A+1. Âåêòîð B++ îïðåäåëÿåòñÿ ïî âåêòîðó A+1 è ñîîòâåòñòâóþùåìóèçìåðåíèþ m (18).Óòâåðæäåíèå 5. 8A 2 A(S) : A . (A+ 1)00:Óòâåðæäåíèå 6. Ïóñòü A 2 A(S). Åñëè A .m A + 1; D - çàìêíóòûé âåêòîðòàêîé, ÷òî A .m D, òî (A + 1)00 � D è, ñëåäîâàòåëüíî, (A+ 1)00 . D.Óòâåðæäåíèå 7. Ïóñòü A 2 A(S). Åñëè A .m A + 1; D - çàìêíóòûé âåêòîðòàêîé, ÷òî A .m D, òî A .m (A+ 1)00.Èç óòâåðäæåíèé 6 è 7 âûòåêàþò ñëåäóþùèå óòâåðæäåíèÿ.Óòâåðæäåíèå 8. Åñëè A .m A + 1 è A .m (A + 1)00, òî (A+ 1)00 - ëåêñè÷åñêè íàè-ìåíüøèé çàìêíóòûé âåêòîð ñðåäè çàìêíóòûõ èíäèêàòîðíûõ âåêòîðîâ, ëåêñè÷åñêèñëåäóþùèõ çà âåêòîðîì A.Óòâåðæäåíèå 9. Åñëè (A + 1)00 íå ÿâëÿåòñÿ ëåêñè÷åñêè íàèìåíüøèì çàìêíóòûìâåêòîðîì ñðåäè çàìêíóòûõ èíäèêàòîðíûõ âåêòîðîâ, ëåêñè÷åñêè ñëåäóþùèõ çà âåê-òîðîì A, òî íå âûïîëíÿåòñÿ óñëîâèå A .m (A+ 1)00.Ïîñëåäíåå óòâåðæäåíèå ïîçâîëÿåò ñ�îðìóëèðîâàòü óñëîâèå ïðîâåðêè, ÿâëÿåòñÿëè âåêòîð (A + 1)00 èñêîìûì èíäèêàòîðíûì âåêòîðîì.Óòâåðæäåíèå 10. Ïóñòük = minfj j a00j 6= aj; j = 0; 1; : : : ; 2n� 1g; (20)òî åñòü, k � íàèìåíüøåå íàïðàâëåíèå ïðèçíàêîâîãî ïðîñòðàíñòâà, ïî êîòîðîìóêîìïîíåíòû âåêòîðîâ A è (A + 1)00 íå ñîâïàäàþò. Òîãäà, åñëè k < m, òî (A + 1)00íå ÿâëÿåòñÿ èñêîìûì âåêòîðîì.Òàêèì îáðàçîì, åñëè âûïîëíÿþòñÿ óñëîâèÿ óòâåðæäåíèÿ 10, èíòåðâàë [B;B++℄,ãäå B = A+1, íå ñîäåðæèò çàìêíóòûõ âåêòîðîâ è åãî ýëåìåíòû ñëåäóåò ïðîïóñòèòü.Äëÿ ýòîãî ñëåäóåò ïåðåéòè ê âåêòîðó, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùåìó çàâåêòîðîì B ++.Èíòåðâàë [B;B + +℄ óäîáíî íàçûâàòü èñêëþ÷àåìûì èíòåðâàëîì íåçàìêíóòûõâåêòîðîâ. ¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2010
64 Èëü÷åíêî À.Â.8. Àëãîðèòì ïîèñêà ëåêñè÷åñêè ñëåäóþùåãî çàìêíóòîãîèíäèêàòîðíîãî âåêòîðàÀëãîðèòì lexi
alNextClose(A) � àëãîðèòì ïîèñêà ëåêñè÷åñêè íàèìåíüøåãî çà-ìêíóòîãî èíäèêàòîðíîãî âåêòîðà, ñëåäóþùåãî çà âåêòîðîì A.Ïñåâäîêîä àëãîðèòìà lexi
alNextClose(A).Âõîä. A � òåêóùèé çàìêíóòûé èíäèêàòîðíûé âåêòîð;Âûõîä. C � ëåêñè÷åñêè íàèìåíüøèé çàìêíóòûé èíäèêàòîðíûé âåêòîð,ñëåäóþùèé çà âåêòîðîì A.Ìåòîä.1) B = A+ 12) C = A003) repeat4) m = maxfj j bj 6= 0; j = 0; 1; : : : ; 2n� 1g5) k = minfj j bj 6=
j; j = 0; 1; : : : ; 2n� 1g6) if k < m then begin7) B = B ++8) B = B + 19) C = B0010) end11) until k < m12) return CÏîÿñíåíèÿ ê ïñåâäîêîäó àëãîðèòìà lexi
alNextClose(A).Øàã 1. B � âåêòîð, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèé çà A.Øàã 2. C � çàìûêàíèå âåêòîðà B.Øàãè 3 - 11. Öèêë, îñóùåñòâëÿþùèé âû÷èñëåíèå èñêîìîãî âåêòîðà.Øàã 4. m � íàèáîëüøåå èçìåðåíèå ïðèçíàêîâîãî ïðîñòðàíñòâà, ïîêîòîðîìó êîìïîíåíòà âåêòîðà B îòëè÷íà îò íóëÿ.Øàã 5. k � íàèìåíüøåå èçìåðåíèå ïðèçíàêîâîãî ïðîñòðàíñòâà, ïîêîòîðîìó êîìïîíåíòû âåêòîðîâ B è C íå ñîâïàäàþò.Øàã 6. Ïðîâåðêà, ÿâëÿåòñÿ ëè âû÷èñëåííîå C èñêîìûì âåêòîðîì.Åñëè óñëîâèå âûïîëíÿåòñÿ, òî � íå ÿâëÿåòñÿ.Øàã 7. Ïðîïóñê ëåêñè÷åñêîãî èíòåðâàëà íåçàìêíóòûõ âåêòîðîâ,ñëåäóþùèõ çà òåêóùèì âåêòîðîì B.Øàã 8. Çàìåíà òåêóùåãî çíà÷åíèÿ âåêòîðà B íà âåêòîð,íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèé çà âåêòîðîì B ++.Øàã 9. C � çàìûêàíèå âåêòîðà B.Øàã 11. Ïðîâåðêà, íàéäåí ëè èñêîìûé âåêòîð.Øàã 12. Âîçâðàò íàéäåííîãî âåêòîðà C.¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2010
Ïîèñê ìàêñèìàëüíûõ èíòåðâàëîâ... 659. Èñêëþ÷àåìûé èíòåðâàëÏóñòü A 2 A(S) � 1-âåêòîð, I(A) � ïîðîæäàåìûé èì èíòåðâàë.A4� = fD 2 A(S) j A � Dg: (21)Ýëåìåíòû ïîäìíîæåñòâà A4� � ýòî 1-âåêòîðà, ïîðîæäàþùèå ïîäèíòåðâàëû èíòåðâà-ëà I(A). A4. = fD 2 A(S) j A . Dg: (22)Ýëåìåíòû ïîäìíîæåñòâà A4. � âñå âåêòîðà, ëåêñè÷åñêè ñëåäóþùèå çà âåêòîðîì A. ñèëó ëèíåéíîñòè ëåêñè÷åñêîãî ïîðÿäêà ., ïîäìíîæåñòâî A4. � öåïü â óïîðÿäî-÷åííîì ìíîæåñòâå hA(S);.i, íà÷èíàþùàÿñÿ ñ âåêòîðà A.�àññìîòðèì íà ïîäìíîæåñòâå A4. ïîäöåïî÷êó ìàêñèìàëüíîé äëèíû, íà÷àëüíûéýëåìåíò êîòîðîé âåêòîð A, è ñîñòîÿùóþ èç ýëåìåíòîâ ïîäìíîæåñòâà A4� , íåïîñðåä-ñòâåííî ëåêñè÷åñêè ñëåäóþùèõ äðóã çà äðóãîì.Òàêàÿ ïîäöåïî÷êà îáðàçóåò íåêîòîðûé èíòåðâàë [A;B℄ ïîäìíîæåñòâà A4. . Âåê-òîð A � íèæíÿÿ ãðàíü ýòîãî èíòåðâàëà. Âåêòîð B - ýòî âåêòîð èç ïîäìíîæåñòâà A4�òàêîé, ÷òî íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèé çà íèì âåêòîð (âåêòîð B+1) óæåíå ÿâëÿåòñÿ ýëåìåíòîì ïîäìíîæåñòâà A4� .1-èíòåðâàëû, ïîðîæäàåìûå âåêòîðàìè èç èíòåðâàëà [A;B℄, íå ÿâëÿþòñÿ ìàêñè-ìàëüíûìè (çà èñêëþ÷åíèåì, ìîæåò áûòü, âåêòîðà A), è, ñëåäîâàòåëüíî, ìîãóò áûòüèñêëþ÷åíû èç ðàññìîòðåíèÿ (ïðîïóùåíû). Òàêèì îáðàçîì, îò âåêòîðà A ìîæíî ñðàçóïåðåéòè ê âåêòîðó B.Èíòåðâàë [A;B℄ áóäåì íàçûâàòü èñêëþ÷àåìûì èíòåðâàëîì 1-âåêòîðîâ.Âû÷èñëåíèå âåêòîðà B ïî çàäàííîìó âåêòîðó A îñóùåñòâëÿåòñÿ ñëåäóþùèì îá-ðàçîì.Ïóñòü A = (a0; : : : ; a2n�1) èm = maxfi j a2i 6= 0 _ a2i+1 6= 0; i = 0; 1; : : : ; n� 1g: (23)òî åñòü, m - íàèáîëüøåå èçìåðåíèå ïðèçíàêîâîãî ïðîñòðàíñòâà S, â êîòîðîì õîòÿ áûïî îäíîìó èç íàïðàâëåíèé åñòü îòëè÷íàÿ îò íóëÿ êîìïîíåíòà.�àçëè÷àþòñÿ äâà ñëó÷àÿ: a2m+1 = 0 è a2m+1 6= 0.Êàæäûé èç ýòèõ ñëó÷àåâ ðàññìîòðèì îòäåëüíî.Ñëó÷àé 1). a2m+1 = 0.Çäåñü âåêòîðà A è B èìåþò ñëåäóþùèé âèä:A = (a0; : : : ; a2m�1; a2m; 0; : : : ; 0); (24)B = (a0; : : : ; a2m�1; b2m; b2m+1; : : : ; b2n�1); (25)ãäå b2m = (nm � 1); b2m+1 = 0;b2m+2 = (nm+1 � 1); b2m+3 = 0;: : :b2n�2 = (nn�1 � 1); b2n�1 = 0: (26)¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2010
66 Èëü÷åíêî À.Â.Äëÿ êîìïîíåíò âåêòîðîâ A è B âûïîëíÿþòñÿ óñëîâèÿ ïîêîìïîíåíòíîãî ïðåäøåñòâî-âàíèÿ:a0 = b0; : : : ; a2m�1 = b2m�1; a2m � b2m; : : : ; a2n�1 � b2n�1:Îòñþäà, â ñèëó (11), A � B è, ñëåäîâàòåëüíî, B 2 A4� .Êðîìå òîãî, òàê êàê A � B, òî A . B, à çíà÷èò, [A;B℄ � èíòåðâàë â A4. .Êàæäûé âåêòîð D 2 [A;B℄ èìååò âèä:D = (a0; : : : ; a2m�1; d2m; d2m+1; : : : ; d2n�1);è äëÿ åãî êîìïîíåíò âûïîëíÿþòñÿ óñëîâèÿaj � dj; j = 0; 1; : : : ; 2n� 1:Ïîýòîìó A � D è, ñëåäîâàòåëüíî, D 2 A4� .Òàêèì îáðàçîì, [A;B℄ � A4� .Ïîêàæåì, ÷òî âåêòîð, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèé çà âåêòîðîì B, íåïðèíàäëåæèò ïîäìíîæåñòâó A4� .Ïóñòü C = B+1 � âåêòîð, íåïîñðåäñòâåííî ëåêñè÷åñêè ñëåäóþùèé çà âåêòîðîì B. âåêòîðå C êîìïîíåíòà
2m = 0. Òàê êàê a2m 6= 0, òî
2m 66 a2m è, ñëåäîâàòåëüíî,A 66 C, òî åñòü, C 62 A4� .Ñëó÷àé 2). a2m+1 6= 0.Çäåñü âåêòîðà A è B èìåþò ñëåäóþùèé âèä:A = (a0; : : : ; a2m�1; a2m; a2m+1; 0; : : : ; 0); (27)B = (a0; : : : ; a2m�1; a2m; b2m+1; : : : ; b2n�1); (28)ãäå b2m = a2m; b2m+1 = (nm � 1)� a2m;b2m+2 = (nm+1 � 1); b2m+3 = 0;: : :b2n�2 = (nn�1 � 1); b2n�1 = 0: (26)Äëÿ ýòîãî ñëó÷àÿ îáîñíîâàíèå ïî÷òè ïîëíîñòüþ ïîâòîðÿåò ïðåäûäóùèé âàðèàíò, çàèñêëþ÷åíèåì òîãî, ÷òî â âåêòîðå C òåïåðü êîìïîíåíòà
2m+1 = 0.Òàêèì îáðàçîì, ïî çàäàííîìó 1-âåêòîðó A, èñïîëüçóÿ (26) èëè (29), ìîæíî âû-÷èñëèòü èñêëþ÷àåìûé èíòåðâàë 1-âåêòîðîâ [A;B℄.10. �àñøèðåíèå èñêëþ÷àåìîãî èíòåðâàëàA� � âåêòîð, íåïîñðåäñòâåííî ïðåäøåñòâóþùèé âåêòîðó A ïî íàïðàâëå-íèþ 2m+ 1.Òàê êàêA = (a0; : : : ; a2m�1; a2m; a2m+1; 0; : : : ; 0), òî, ñ ó÷¼òîì (13),A� = (a0; : : : ; a2m�1; a2m; a2m+1 � 1; 0; : : : ; 0):A� � A è, ñëåäîâàòåëüíî, I(A) � I(A�) è A� . A.Âåêòîð A� � ýòî íå 1-âåêòîð. Åñëè áû âåêòîð A� ïîðîæäàë 1-èíòåðâàë, òî [A�; B℄áûë áû èñêëþ÷àåìûì èíòåðâàëîì 1-âåêòîðîâ, A 2 [A�; B℄ è, ïîýòîìó, âåêòîð A áûëáû èñêëþ÷¼í èç ðàññìîòðåíèÿ. ¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2010
Ïîèñê ìàêñèìàëüíûõ èíòåðâàëîâ... 67�àññìîòðèì èíòåðâàë J , îïðåäåëÿåìûé ñëåäóþùèì îáðàçîì:J = I(A�) n I(A): (30)Òàê êàê, I\I(A) = � è I(A�) = J[I(A), òî èíòåðâàëû J è I(A) ïîðîæäàþò ðàçáèåíèåèíòåðâàëà A�.I(A) � 1-èíòåðâàë, I(A�) � íå 1-èíòåðâàë. Ñëåäîâàòåëüíî, èìåííî èíòåðâàë J ,ÿâëÿåòñÿ èíòåðâàëîì, ñîäåðæàùèì õîòÿ áû îäíó 0-òî÷êó ïðèçíàêîâîãî ïðîñòðàíñòâà.Ïîýòîìó, ëþáîé èíòåðâàë, ñîäåðæàùèé èíòåðâàë J , � íå 1-èíòåðâàë.Èíäèêàòîðíûé âåêòîð èíòåðâàëà J :A(J) = (a0; : : : ; a2m�1; (nm � 1)� (a2m+1 � 1); a2m+1 � 1; 0; : : : ; 0): (31)Ïóñòü [A;B℄ � èñêëþ÷àåìûé èíòåðâàë 1-âåêòîðîâ, ïîðîæäàåìûé âåêòîðîì A.�àññìîòðèì ñëåäóþùèå äâà øàãà.Øàã 1). B + 1 = (a0; : : : ; a2m�1; a2m + 1; 0; : : : ; 0): (32)Òàê êàê, B+1 � A(J), òî I(A(J)) � I(B+1) è, ñëåäîâàòåëüíî, B+1 � íå 1-èíòåðâàë.C = (a0; : : : ; a2m�1; a2m + 1; a2m+1 � 1; (nm+1 � 1); 0; : : : ; (nn�1 � 1); 0): (33)Òàê êàê, C � A(J), òî I(A(J)) � I(C) è, ñëåäîâàòåëüíî, C � íå 1-èíòåðâàë.Äàëåå, B + 1 . C è 8D 2 [B + 1; C℄ : D � C. Ñëåäîâàòåëüíî, I(C) � I(D)è D � íå 1-âåêòîð. Ïîýòîìó, [B+1; C℄ ìîæíî èñêëþ÷èòü èç ðàññìîòðåíèÿ, òåì ñàìûìðàñøèðèâ èíòåðâàë [A;B℄ äî èíòåðâàëà [A;C℄.Øàã 2). C + 1 = (a0; : : : ; a2m�1; a2m + 1; a2m+1; 0; 0; : : : ; 0; 0): (34)Òàê êàê, A � C + 1, òî I(C + 1) � I(A) è, ñëåäîâàòåëüíî, [C + 1; (C + 1) + +℄ � A4� .Ïîýòîìó, èíòåðâàë [C+1; (C+1)++℄ ìîæíî èñêëþ÷èòü èç ðàññìîòðåíèÿ, ðàñøèðèâèíòåðâàë [A;C℄ äî èíòåðâàëà [A; (C + 1) + +℄.Îáîçíà÷èì B = (C+1)++ è ðàñøèðåííûé òàêèì îáðàçîì èñêëþ÷àåìûé èíòåðâàëñíîâà çàïèøåì â âèäå [A;B℄.Øàãè 1) è 2) ïîâòîðÿòü äî òåõ ïîð, ïîêà êîìïîíåíòû âåêòîðà B ñòàíóò ðàâíûìèb2m = (nm � 1)� a2m+1; b2m+1 = a2m+1: (35)Ïðèìå÷àíèå 4. �àñøèðåíèå èñõîäíîãî èíòåðâàëà [A;B℄ ïðîâîäèëîñü òîëüêî äëÿñëó÷àÿ a2m+1 6= 0. Åñëè a2m+1 = 0, òî âûðàæåíèÿ (29) è (35) ñîâïàäóò. Ïîýòîìóâûðàæåíèå (35) ðàññìàòðèâàåòñÿ êàê îáîáùåíèå âûðàæåíèé (29) è (35).Ïðèìå÷àíèå 5. Âåêòîð B, ïîëó÷åííûé â ðåçóëüòàòå óêàçàííûõ âû÷èñëåíèé áóäåìîáîçíà÷àòü A + +m, òåì ñàìûì ïîä÷¼ðêèâàÿ, ÷òî äëÿ åãî âû÷èñëåíèÿ èñïîëüçîâàíâåêòîð A è èí�îðìàöèÿ ïî èçìåðåíèþ m ýòîãî âåêòîðà (23).¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2010
68 Èëü÷åíêî À.Â.11. Àëãîðèòì ïîèñêà 1-âåêòîðîâ, ïîðîæäàþùèõìàêñèìàëüíûå 1-èíòåðâàëûÀëãîðèòì listMinAnti
hains � àëãîðèòì ïîèñêà âñåõ 1-âåêòîðîâ, ïîðîæäàþùèõìàêñèìàëüíûå 1-èíòåðâàëû.Ïñåâäîêîä àëãîðèòìà listMinAnti
hains.Âõîä. Íåò;Âûõîä. B � ñïèñîê âñåõ 1-âåêòîðîâ, ïîðîæäàþùèõ ìàêñèìàëüíûå 1-èíòåðâàëû.Ìåòîä.1) if (0; : : : ; 0) � 1-âåêòîð return f(0; : : : ; 0)g2) B = �3) A = (0; : : : ; 0)004) repeat5) if (A� 1) � 1-âåêòîð then begin6) if �9D 2 B : D < A then B = B [ fAg7) m = maxfi j a2i 6= 0 _ a2i+1 6= 0; i = 0; 1; : : : ; n� 1g8) A = A ++m9) end10) A = lexi
alNextClose(A)11) until A 6= (0; : : : ; 0)0012) return BÏîÿñíåíèÿ ê ïñåâäîêîäó àëãîðèòìà listMinAnti
hains.Øàã 1. Åñëè âåêòîð, ïîðîæäàþùèé ïðèçíàêîâîå ïðîñòðàíñòâî, � 1-âåêòîð,òî îí ïîðîæäàåò åäèíñòâåííûé ìàêñèìàëüíûé 1-èíòåðâàë.Øàã 2. Èçíà÷àëüíî ìíîæåñòâî B èñêîìûõ 1-âåêòîðîâ ïóñòî.Øàã 3. A � òåêóùèé çàìêíóòûé âåêòîð � çàìûêàíèå âåêòîðà,ïîðîæäàþùåãî ïðèçíàêîâîå ïðîñòðàíñòâî.Øàãè 4 - 11. Öèêë, îñóùåñòâëÿþùèé âû÷èñëåíèå èñêîìîãî ìíîæåñòâà âåêòîðîâ.Øàã 6. Åñëè òåêóùèé 1-âåêòîð A � ýòî ìàêñèìàëüíûé 1-âåêòîð, òîâêëþ÷èòü åãî â ìíîæåñòâî B.Øàã 7. m � íàèáîëüøåå èçìåðåíèå ïðèçíàêîâîãî ïðîñòðàíñòâà S,ïî êîòîðîìó õîòÿ áû ïî îäíîìó èç íàïðàâëåíèé åñòü îòëè÷íàÿ îò íóëÿêîìïîíåíòà.Øàã 8. Ïåðåéòè ê ïðàâîé ãðàíèöå èñêëþ÷àåìîãî èíòåðâàëà.Øàã 10. Íàéòè çàìêíóòûé âåêòîð, ëåêñè÷åñêè ñëåäóþùèé çà òåêóùèìâåêòîðîì A. ¾Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêè è ìàòåìàòèêè¿, �2' 2010
Ïîèñê ìàêñèìàëüíûõ èíòåðâàëîâ... 69Çàêëþ÷åíèå ðàáîòå ïîëó÷åíû ñëåäóþùèå ðåçóëüòàòû: Îïðåäåëåíî ïîíÿòèå èíòåðâàëà, çà-ìêíóòîãî îòíîñèòåëüíî çàäàííîé îáëàñòè ïðèçíàêîâîãî ïðîñòðàíñòâà è ïîêàçàíî,÷òî èñêîìûå ìàêñèìàëüíûå èíòåðâàëû ÿâëÿþòñÿ çàìêíóòûìè. Âåäåíî ïîíÿòèå èí-äèêàòîðíîãî âåêòîðà èíòåðâàëà, êàê ñïîñîáà ïðåäñòàâëåíèÿ èíòåðâàëîâ ïðèçíàêî-âîãî ïðîñòðàíñòâà. Íà ìíîæåñòâå òàêèõ âåêòîðîâ îïðåäåë¼í îïåðàòîð çàìûêàíèÿ,ïîðîæäàþùèé çàìêíóòûå èíäèêàòîðíûå âåêòîðà, ðåàëèçóþùèå çàìêíóòûå èíòåð-âàëû. Ïðåäëîæåí àëãîðèòì ïîèñêà â ëåêñèêîãðà�è÷åñêîì ïîðÿäêå âñåõ çàìêíóòûõèíäèêàòîðíûõ âåêòîðîâ. Ïðåäëîæåí àëãîðèòì ïîèñêà â ëåêñèêîãðà�è÷åñêîì ïîðÿä-êå âñåõ èíäèêàòîðíûõ âåêòîðîâ, ïîðîæäàþùèõ ìàêñèìàëüíûå èíòåðâàëû îáëàñòèïðèçíàêîâîãî ïðîñòðàíñòâà. Ñïèñîê ëèòåðàòóðû1. Ganter, B., Wille, R. Formal Con
ept Analysis � Mathemati
al Foundations. Springer-Verlag, Berlin.,1999.2. Gugis
h, R. Latti
e Contexts � a Generalization in Formal Con
ept Analisys. Handuot to ICCS 2000,Darmstadt(2000) http://www.mathe2.uni-bayreuth.de/ralfg/papers/diplom.ps.gz.3. Áèðêãî� �. Òåîðèÿ ðåø¼òîê: Ïåð. ñ àíãë. � Ì.: Íàóêà, 1984. � 568 ñ.4. Èëü÷åíêî À.Â. Êîìïàêòíàÿ êîìïîíåíòíàÿ è ñîêðàù¼ííàÿ èíòåðâàëüíàÿ ñòðóêòóðû ïðèçíàêîâîãîïðîñòðàíñòâà, ïîðîæäàåìûå ýìïèðè÷åñêèìè äàííûìè // Ñá.Òàâðè÷åñêèé âåñòíèê èí�îðìàòèêèè ìàòåìàòèêè. � 2005. � �2. � C. 126-142.5. Êîëìîãîðîâ À.Ê., Ôîìèí Ñ.Â. Ýëåìåíòû òåîðèè �óíêöèÿ è �óíêöèîíàëüíîãî àíàëèçà. � Ì.:Íàóêà. �ë. ðåä. �èç.-ìàò. Ëèò., 1989. � 624 ñ.6. Êóçíåöîâ Ñ.Î. Àâòîìàòè÷åñêîå îáó÷åíèå íà îñíîâà àíàëèçà �îðìàëüíûõ ïîíÿòèé // Àâòîìàòèêàè òåëåìåõàíèêà. � 2001. � �10. � Ñ. 3-27. Ñòàòüÿ ïîñòóïèëà â ðåäàêöèþ 10.12.2010
¾Òàâðiéñüêèé âiñíèê ií�îðìàòèêè òà ìàòåìàòèêè¿, �2' 2010
|