Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов

Приведены оценки числа основных ребер при построении базовых GL-моделей, отображающих реакцию отказоустойчивой многомодульной системы на появление отказов, с минимальным числом теряемых ребер, а также граничные оценки числа дополнительных ребер при трансформации базовых GL-моделей к небазовым....

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2008
Hauptverfasser:	Романкевич, А.М., Романкевич, В.А., Майданюк, И.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2008
Schriftenreihe:	Электронное моделирование
Schlagworte:	Точность, надежность, диагностика
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/101552
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 59-70. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-101552
record_format	dspace
spelling	irk-123456789-1015522016-06-05T03:02:22Z Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов Романкевич, А.М. Романкевич, В.А. Майданюк, И.В. Точность, надежность, диагностика Приведены оценки числа основных ребер при построении базовых GL-моделей, отображающих реакцию отказоустойчивой многомодульной системы на появление отказов, с минимальным числом теряемых ребер, а также граничные оценки числа дополнительных ребер при трансформации базовых GL-моделей к небазовым. Наведено результати оцінки кількості основних ребер при побудові GL-моделей, що відображують реакцію відмовостійкої багатомодульної системи на появу відмов, з мінімальною кількістю втрачених ребер, а також граничні оцінки числа додаткових ребер при трансформації базових GL-моделей до небазових. The main edge number estimates are given for base GL-models construction with minimum failed edges number which reflect reaction of failure-resistance multi-module system for failure occurrence. The boundary estimates of additional edges number are given to transform base GL-models to non-base. 2008 Article Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 59-70. — Бібліогр.: 5 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/101552 519.718 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Точность, надежность, диагностика Точность, надежность, диагностика
spellingShingle	Точность, надежность, диагностика Точность, надежность, диагностика Романкевич, А.М. Романкевич, В.А. Майданюк, И.В. Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов Электронное моделирование
description	Приведены оценки числа основных ребер при построении базовых GL-моделей, отображающих реакцию отказоустойчивой многомодульной системы на появление отказов, с минимальным числом теряемых ребер, а также граничные оценки числа дополнительных ребер при трансформации базовых GL-моделей к небазовым.
format	Article
author	Романкевич, А.М. Романкевич, В.А. Майданюк, И.В.
author_facet	Романкевич, А.М. Романкевич, В.А. Майданюк, И.В.
author_sort	Романкевич, А.М.
title	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
title_short	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
title_full	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
title_fullStr	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
title_full_unstemmed	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
title_sort	граничные оценки числа ребер gl-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов
publisher	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
publishDate	2008
topic_facet	Точность, надежность, диагностика
url	http://dspace.nbuv.gov.ua/handle/123456789/101552
citation_txt	Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов / А.М. Романкевич, В.А. Романкевич, И.В. Майданюк // Электронное моделирование. — 2008. — Т. 30, № 1. — С. 59-70. — Бібліогр.: 5 назв. — рос.
series	Электронное моделирование
work_keys_str_mv	AT romankevičam graničnyeocenkičislareberglmodelejpovedeniâotkazoustojčivyhmnogoprocessornyhsistemvpotokeotkazov AT romankevičva graničnyeocenkičislareberglmodelejpovedeniâotkazoustojčivyhmnogoprocessornyhsistemvpotokeotkazov AT majdanûkiv graničnyeocenkičislareberglmodelejpovedeniâotkazoustojčivyhmnogoprocessornyhsistemvpotokeotkazov
first_indexed	2025-07-07T11:05:18Z
last_indexed	2025-07-07T11:05:18Z
_version_	1836985949242785792
fulltext	ÓÄÊ 519.718 À. Ì. Ðîìàíêåâè÷, ä-ð òåõí. íàóê, Â. À. Ðîìàíêåâè÷, êàíä. òåõí. íàóê, È. Â. Ìàéäàíþê, àñïèðàíò Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò Óêðàèíû «Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò» (Óêðàèíà, 03056, Êèåâ, ïð-ò Ïîáåäû, 37, òåë.: (044) 4549032, E-mail romankev@scs.ntu-kpi.kiev.ua) Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ îòêàçîóñòîé÷èâûõ ìíîãîïðîöåññîðíûõ ñèñòåì â ïîòîêå îòêàçîâ (Ñòàòüþ ïðåäñòàâèë ä-ð òåõí.íàóê Â. Ã. Òîöåíêî) Ïðèâåäåíû îöåíêè ÷èñëà îñíîâíûõ ðåáåð ïðè ïîñòðîåíèè áàçîâûõ GL-ìîäåëåé, îòîáðà- æàþùèõ ðåàêöèþ îòêàçîóñòîé÷èâîé ìíîãîìîäóëüíîé ñèñòåìû íà ïîÿâëåíèå îòêàçîâ, ñ ìèíèìàëüíûì ÷èñëîì òåðÿåìûõ ðåáåð, à òàêæå ãðàíè÷íûå îöåíêè ÷èñëà äîïîëíèòåëüíûõ ðåáåð ïðè òðàíñôîðìàöèè áàçîâûõ GL-ìîäåëåé ê íåáàçîâûì. Íàâåäåíî ðåçóëüòàòè îö³íêè ê³ëüêîñò³ îñíîâíèõ ðåáåð ïðè ïîáóäîâ³ GL-ìîäåëåé, ùî â³äîáðàæóþòü ðåàêö³þ â³äìîâîñò³éêî¿ áàãàòîìîäóëüíî¿ ñèñòåìè íà ïîÿâó â³äìîâ, ç ì³í³ìàëü- íîþ ê³ëüê³ñòþ âòðà÷åíèõ ðåáåð, à òàêîæ ãðàíè÷í³ îö³íêè ÷èñëà äîäàòêîâèõ ðåáåð ïðè òðàíñôîðìàö³¿ áàçîâèõ GL-ìîäåëåé äî íåáàçîâèõ. Ê ë þ ÷ å â û å ñ ë î â à: îòêàçîóñòîé÷èâûå ìíîãîïðîöåññîðíûå ñèñòåìû, ãðàôû, ìîäåëè. Øèðîêîå ðàñïðîñòðàíåíèå ñëîæíûõ ìíîãîìîäóëüíûõ ñèñòåì, óñòîé÷èâûõ ê îòêàçàì íåêîòîðûõ ìîäóëåé, òðåáóåò àíàëèçà ïîâåäåíèÿ ñèñòåìû â ïîòîêå îòêàçîâ ðàçëè÷íîé êðàòíîñòè (ò. å. îïðåäåëåíèÿ åå ðåàêöèè íà îòêàç íåêî- òîðîãî ÷èñëà ìîäóëåé), â ÷àñòíîñòè ïðè îöåíêå åå íàäåæíîñòè [1]. Ñðåäè ìíîæåñòâà ðàçëè÷íûõ ìîäåëåé, àäåêâàòíî îòîáðàæàþùèõ ýòó ðåàêöèþ, íàè- áîëüøåå ðàñïðîñòðàíåíèå ïîëó÷èëè GL-ìîäåëè [2], îòëè÷àþùèåñÿ îòíîñè- òåëüíîé ïðîñòîòîé ôîðìèðîâàíèÿ è óäîáñòâîì èñïîëüçîâàíèÿ. Ïðè ðàçðàáîòêå, àíàëèçå è òðàíñôîðìàöèè ðåêîíôèãóðèðóåìûõ îòêà- çîóñòîé÷èâûõ ìíîãîìîäóëüíûõ ñèñòåì (ÎÌÑ), â îñîáåííîñòè ñèñòåì óïðàâ- ëåíèÿ ñëîæíûìè îáúåêòàìè, GL-ìîäåëü, ñîîòâåòñòâóþùàÿ òàêîé ñèñòåìå, èíîãäà ïîëó÷àåòñÿ äîñòàòî÷íî ñëîæíîé. Â ñâÿçè ñ ýòèì ïðàêòè÷åñêèé èíòåðåñ ïðåäñòàâëÿåò ðàñ÷åò ïàðàìåòðîâ ìîäåëè íà ïåðâûõ ýòàïàõ ïðîåêòèðîâàíèÿ ÎÌÑ, à òàêæå îïðåäåëåíèå ñëîæíîñòè òðàíñôîðìàöèè óæå ñîçäàííîé ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 59 �� ìîäåëè ïðè ïðåîáðàçîâàíèè ñàìîé ñèñòåìû. Îò ñëîæíîñòè ìîäåëè çàâèñèò âðåìÿ âûïîëíåíèÿ ñòàòèñòè÷åñêèõ ýêñïåðèìåíòîâ ñ íåé è, ñëåäîâàòåëüíî, òî÷íîñòü ðàñ÷åòà íàäåæíîñòè ÎÌÑ. Áóäåì îïðåäåëÿòü ÷èñëî îñíîâíûõ ðåáåð â áàçîâîé GL-ìîäåëè, ïðåäëî- æåííîé â [3]. Ýòà ìîäåëü ñðàâíèòåëüíî ïðîñòà è òåðÿåò äâà ðåáðà ïðè ïîÿâ- ëåíèè «ëèøíåãî» îòêàçà. Çàòåì îïðåäåëèì ãðàíè÷íûå îöåíêè ÷èñëà äîïîëíè- òåëüíûõ ðåáåð ïðè ðåêîíôèãóðàöèè áàçîâîé GL-ìîäåëè ê íåáàçîâîé. ×èñëî îñíîâíûõ ðåáåð. Â GL-ìîäåëè [2] ïîâåäåíèÿ ÎÌÑ â ïîòîêå îòêàçîâ ðàáîòîñïîñîáíîñòè ñèñòåìû ïîñòàâëåíà â ñîîòâåòñòâèå ñâÿçíîñòü íåîðèåíòèðîâàííîãî öèêëè÷åñêîãî ãðàôà, íàëè÷èå (èëè îòñóòñòâèå) ðåáåð êîòîðîãî îïðåäåëÿåòñÿ çíà÷åíèÿìè áóëåâûõ ôóíêöèé, ïðèñâîåííûõ ðåá- ðàì ãðàôà. Àðãóìåíòû ôóíêöèé îòîáðàæàþò ñîñòîÿíèå ìîäóëåé (îòêàç — «0», èñïðàâåí — «1») ñèñòåìû. ÎÌÑ, ñîñòîÿùóþ èç n ýëåìåíòîâ (ìîäóëåé) è ñîõðàíÿþùóþ ðàáîòîñïîñîáíîñòü â ñëó÷àå îòêàçà íå áîëåå, ÷åì m ëþáûõ åå ìîäóëåé (0 � m � n), îáîçíà÷èì K m n( , ) è íàçîâåì áàçîâîé. Åé ñîîò- âåòñòâóåò áàçîâàÿ GL-ìîäåëü, êîòîðóþ äëÿ ïðîñòîòû âîñïðèÿòèÿ â äàëü- íåéøåì áóäåì òàêæå îáîçíà÷àòü K m n( , ). Ðåáåðíûå ôóíêöèè ôîðìèðóþòñÿ òàêèì îáðàçîì, ÷òî äëÿ áàçîâîé ìîäåëè K m n( , ) ïîÿâëåíèå âåêòîðîâ ñ ÷èñëîì íóëåé (îòêàçîâ â ñèñòåìå), íå ïðåâûøàþùåì âåëè÷èíû m, ïðèâî- äèò ê èñ÷åçíîâåíèþ íå áîëåå, ÷åì îäíîãî ðåáðà. Â äðóãèõ ñëó÷àÿõ â ãðàôå èñ÷åçàþò äâà è áîëåå ðåáåð, è îí òåðÿåò ñâÿçíîñòü. Ìîäåëü, ïðåäëîæåííàÿ â [3], òåðÿåò ìèíèìàëüíîå ÷èñëî ðåáåð ïðè ïîÿâëåíèè âåêòîðîâ ñ ÷èñëîì íóëåâûõ êîìïîíåíò, ïðåâûøàþùèì m, à ïðè ïîÿâëåíèè âåêòîðà ñ m + 1 íóëåâîé êîìïîíåíòîé èç ìîäåëè èñêëþ÷àþòñÿ ðîâíî äâà ðåáðà. Ðàññìîòðèì çàäà÷ó îïðåäåëåíèÿ ÷èñëà r ðåáåð GL-ìîäåëè, ïîñòðîåí- íîé ïî ýòîìó ìåòîäó. Àëãîðèòì ôîðìèðîâàíèÿ ðåáåðíûõ ôóíêöèé ìîäåëè ÎÌÑ îñíîâàí íà îïåðàöèè ñêëåèâàíèÿ. Ïðèâåäåì íåñêîëüêî îñíîâíûõ åãî ïîëîæåíèé, íåîáõîäèìûõ äëÿ ðåøåíèÿ ïîñòàâëåííîé çàäà÷è. Îáîçíà÷èì ÷åðåç �K m n( , ) ìíîæåñòâî ðåáåðíûõ ôóíêöèé GL-ìîäåëè K m n( , ). Êàæäûé ýëåìåíò èç �K m n( , ) ïðèñâîåí òîëüêî îäíîìó ðåáðó ìîäå- ëè. Ïðîöåññ ïîëó÷åíèÿ ýëåìåíòîâ �K m n( , ) ìîæíî ïðåäñòàâèòü â âèäå ðåêóðñèâíîãî ñîîòíîøåíèÿ: � �� K m n K m i n K i n( , ) ( ,[ / ]) ( , ] / [) 1 1 1 1 1 2 2 , (1) ãäå i = 0 ... m1, n1 > m1, m i n 1 1 2� � [ / ], i n�] / [ 1 2 ; [ ]x — öåëàÿ ÷àñòü îò õ; ] x [— îêðóãëåíèå äî áëèæàéøåãî áîëüøåãî öåëîãî. Íà ïåðâîì øàãå àëãîðèòìà âìåñòî ïåðåìåííûõ m1 è n1 ïîäñòàâëÿåì ðåàëüíûå çíà÷åíèÿ m è n, íà ïîñëåäóþùèõ, åñëè ýòî âîçìîæíî, — ñîîòâåòñòâóþùèå çíà÷åíèÿ ïðåäû- äóùåãî øàãà èç ïðàâîé ÷àñòè ñîîòíîøåíèÿ (1). Â [3] äîêàçàíî, ÷òî äèçúþíêòèâíîå âûðàæåíèå âèäà � � � �K m p n K p n( ,[ / ]) ( , ] / [) 1 1 1 2 2 , (2) À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê 60 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1 ãäå 0 < p < m1; n1 > m1; m p n 1 1 2� � [ / ]; p n�] / [ 1 2 , ïîääàåòñÿ ñïåöèàëüíûì ïðåîáðàçîâàíèÿì è â êîíå÷íîì èòîãå ìîæåò áûòü çàïèñàíî â âèäå îäíîé áóëåâîé ðåáåðíîé ôóíêöèè, ò.å. ñîîòâåòñòâóþùåå ìíîæåñòâî �K áóäåò ñîñòîÿòü èç îäíîãî ýëåìåíòà. Çàìåòèì, ÷òî â âûðàæåíèÿõ (1) è (2) îïåðà- öèþ äèçúþíêöèè ñëåäóåò îòíîñèòü íå ê ñàìèì ìíîæåñòâàì, à ê ïàðàì ýëåìåíòîâ (ôóíêöèé) ðàçíûõ ìíîæåñòâ âèäà �K . Ìíîæåñòâî �K m n( , ) 1 1 , ãäå m n 1 1 � , íå òðåáóåò ïðåäñòàâëåíèÿ â âèäå (2) è äàëüíåéøåãî ïðåîáðàçîâàíèÿ: îíî ñîñòîèò òîëüêî èç îäíîé ôóíêöèè. Ïîíÿò- íî, ÷òî ðàññìàòðèâàòü äâèæåíèå â ãëóáèíó íà ñëåäóþùåì øàãå ðåêóðñèè ïî (1) öåëåñîîáðàçíî òîëüêî äëÿ äèçúþíêöèé âèäà � � �K m n K n( ,[ / ]) ( , ] / [) 1 1 1 2 0 2 èëè � � �K n K m n( ,[ / ]) ( , ] / [)0 2 2 1 1 1 , ò. å. ïðè ãðàíè÷íûõ çíà÷åíèÿõ ïåðåìåí- íîé i, èáî òîëüêî â ýòîì ñëó÷àå íåîáõîäèì äàëüíåéøèé ðåêóðñèâíûé ñïóñê äëÿ îïðåäåëåíèÿ �K m n( , ). Ñëåäóåò çàìåòèòü, ÷òî ìíîæåñòâî �K m n( , ) 1 1 ïóñòî ïðè m1 = 0, è ïðè ïîñëåäóþùèõ âûêëàäêàõ óïîìèíàíèå î íåì áóäåì îïóñêàòü. Ïîñëå âûïîëíåíèÿ âñåõ ïðåîáðàçîâàíèé âèäà (1) è (2) áóäóò ïîëó÷åíû âñå ìíîæåñòâà òèïà �K , äëÿ êîòîðûõ íå íóæíû èëè íåâîçìîæíû äàëü- íåéøèå ïðåîáðàçîâàíèÿ. Äëÿ ïîëó÷åíèÿ èñêîìîãî �K m n( , ) âûïîëíÿåì îáúåäèíåíèå ýëåìåíòîâ ýòèõ ìíîæåñòâ. Òåïåðü âîçâðàòèìñÿ ê ðåøåíèþ ïîñòàâëåííîé çàäà÷è. Äîêàæåì ñëå- äóþùåå óòâåðæäåíèå. Óòâåðæäåíèå. r = n – m + 1. Äëÿ óïðîùåíèÿ äîêàçàòåëüñòâà ïðîöåññ ïîëó÷åíèÿ ýëåìåíòîâ �K m n( , ) ïî (1) ïðåäñòàâèì â âèäå äåðåâà. Äëÿ óäîáñòâà ïîìåñòèì â óçëû äåðåâà ìíîæåñòâà �K m n( , ) 1 1 , äëÿ êîòîðûõ ïðèìåíèìà îïåðàöèÿ (1) è êîòîðûå íå âõîäÿò â ñîñòàâ äèçúþíêöèé òèïà (2), ãäå n m 1 1 � . Âåðøèíû äåðåâà ñîîò- âåòñòâóþò ýëåìåíòàì ìíîæåñòâà �K m n( , ), ò. å. ðåáðaì èñõîäíîé GL-ìîäåëè ñ èõ ôóíêöèÿìè, ñëåäîâàòåëüíî, ÷èñëî âåðøèí äåðåâa â òî÷íîñòè ðàâíî ÷èñëó ðåáåð ìîäåëè. Äèçúþíêöèè (2) ïðèïèøåì âåðøèíàì (âåðøèíà íå èìååò èñõîäÿùèõ äóã). Ïîìåñòèì â âåðøèíû äåðåâà òàêæå ìíîæåñòâà �K m n( , ) 1 1 , ãäå m n 1 1 � , íå âõîäÿùèå â ñîñòàâ äèçúþíêöèè (2). Ïðèìåð òàêîãî äåðåâà ïðèâåäåí íà ðèñ. 1. Â äàííîì ïðèìåðå �K ( , )3 9 , �K ( , )3 5 , �K ( , )3 4 ïîìåùåíû â óçëàõ, âñå äèçúþíêòèâíûå âûðàæåíèÿ òèïà (2) ïðèñâîåíû âåðøèíàì è �K ( , )3 3 òàêæå îòîáðàæàåòñÿ êàê âåðøèíà. Íàïîìíèì, ÷òî êàæäàÿ âåðøèíà ñîäåðæèò ìíî- æåñòâî �K , ìîùíîñòü êîòîðîãî ðàâíà åäèíèöå. Äåðåâî ïîçâîëÿåò óïðîñòèòü ïðîöåäóðó îïðåäåëåíèÿ ÷èñëà r. Ñëåäóÿ îïåðàöèè (1) â ãëóáèíó, ïîñëåäîâàòåëüíî íà êàæäîì ýòàïå äåëèì âåëè÷èíó n íà äâà, ïîëó÷àÿ çíà÷åíèÿ ïåðåìåííûõ n1 íà ñîîòâåòñò- Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 61 âóþùåì ýòàïå. Òàêèì îáðàçîì, n ni i 1 2� [ / ]ëèáî n ni i 1 2�] / [, ãäå i — íîìåð ýòàïà (óðîâíÿ). Ïóñòü (k + 1) = max (i), ò. å. íà óðîâíå (k + 1) óçëû îòñóòñòâóþò. Ïîñêîëüêó k-é óðîâåíü ýòî ìàêñèìàëüíûé óðîâåíü, èìåþ- ùèé óçëû, ìîæíî çàïèñàòü m n mk � �/2 2 . Ðàçäåëèâ ýòî íåðàâåíñòâî íà m è óìíîæèâ íà 2 k , ïîëó÷èì 2 2 1k kn m� � � / , èëè 2 2 22 1k n m k � � �log ( / ) , îòêóäà k n m� [log ( / )] 2 . Èñõîäÿ èç (1), ìîæíî çàìåòèòü, ÷òî èç êàæäîãî óçëà, íàõî- äÿùåãîñÿ íà óðîâíå ãëóáèíîé i < k, âûõîäèò m + 1 âåòâü, è êàæäûé òàêîé óçåë èìååò ðîâíî m – 1 èíöèäåíòíóþ âåðøèíó. Íà êàæäîì òàêîì óðîâíå áóäåò 2 i óçëîâ. Ëåãêî îïðåäåëèòü îáùåå ÷èñëî âåðøèí r* íà óðîâíÿõ ãëóáèíîé ìåíüøåé k: r mi i k * ( )� � � � 2 1 1 1 . Ïîíÿòíî, ÷òî íà îäíîì è òîì æå óðîâíå â ðàçëè÷íûõ óçëàõ (îáîçíà- ÷åííûõ �K m n( , ) 1 1 ), çíà÷åíèÿ âåëè÷èí n1 îòëè÷àþòñÿ íå áîëåå ÷åì íà åäèíèöó. Îáîçíà÷èì ÷åðåç nm ìåíüøåå èç çíà÷åíèé n1 íà k-ì óðîâíå, à ÷åðåç nx — áîëüøåå. Î÷åâèäíî, ÷òî n nm k � [ / ]2 , à n nx k �] / [2 . Ïóñòü � � �{ / }n nk 2 � � �[ / ]n n nk k m k 2 2 2 , ãäå {x/y} — îñòàòîê îò öåëî÷èñëåííîãî äåëåíèÿ. ßñíî, ÷òî ðàâíî ÷èñëó óçëîâ �K m n( , ) 1 1 , â êîòîðûõ n nx1 � , à ( )2 k � — ÷èñëó óçëîâ �K m n( , ) 1 1 , â êîòîðûõ n nm1 � . Ïîñêîëüêó óçåë k-ãî óðîâíÿ ìîæåò áûòü èíöèäåíòåí òîëüêî âåðøèíàì (k + 1)-ãî óðîâíÿ, àíàëèçèðóÿ (1), ìîæíî çàìåòèòü, ÷òî ÷èñëî òàêèõ âåðøèí îïðåäåëÿåòñÿ êàê (n m 1 1 1� � ). Ñëåäîâà- òåëüíî, îáùåå ÷èñëî âåðøèí, èíöèäåíòíûõ âñåì óçëàì �K m nx( , ) 1 , ðàâíî ( )n mx � � 1 1 . Àíàëîãè÷íî îáùåå ÷èñëî âåðøèí, èíöèäåíòíûõ âñåì óçëàì �K m nm( , ) 1 , ðàâíî ( ) ( )2 1 k mn m� � � . Ñëåäîâàòåëüíî, îáùåå ÷èñëî âåðøèí âî âñåì äåðåâå: r m n m n mi x k m i k � � � � � � � � � � � � 2 1 1 2 1 1 1 ( ) ( ) ( ) ( ) � � � � � � � � � � �( )( ) ( ) ( ) ( )2 1 1 1 2 1 k x k mm n m n m À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê 62 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1 K�(3,9) K�(3,4) K�(3,5) K�(2,3)� �K (1,2) K�(2,2)� �K (1,2) K�(1,2)� K’(2,2) K�(3,3) K�(1,3)� �K (2,2) K�(1,4) � K’ (2,5) K�(2,4) K� ’ (1,5) Íóëåâîé óðîâåíü Âòîðîé óðîâåíüÏåðâûé óðîâåíü Ðèñ. 1. Äåðåâî äëÿ �K ( , )3 9 � � � � � � � � � � � � � �2 2 1 2 2 2 k k x k m k k mm m n m n m n m � � � � � n n n mx k m m2 1. (3) Ïîñêîëüêó n nx k �] / [2 , à n nm k � [ / ]2 , n nx m� ëèøü â ñëó÷àå, êîãäà n k /2 — öåëîå ÷èñëî, èíà÷å n nx m� �1. Â óðàâíåíèè (3) nx óìíîæàåòñÿ íà êîýôôè- öèåíò , ðàâíûé íóëþ, êîãäà n k /2 — öåëîå. Íà îñíîâàíèè èçëîæåííîãî ìîæíî âûïîëíèòü çàìåíó n nx m� �1: r n m n n n n n mx k m m m k m m� � � � � � � � � � � � 1 2 2 1 � � � � 2 1 k mn m . Ïîäñòàâèâ � �n nm k 2 , ïîëó÷èì r n n n m n mk m k m� � � � � � � �2 2 1 1. Óòâåðæ- äåíèå äîêàçàíî. Îöåíêà ÷èñëà äîïîëíèòåëüíûõ ðåáåð ïðè ïðåîáðàçîâàíèè GL- ìîäåëè. Áàçîâàÿ ÎÌÑ ïðîäîëæàåò ôóíêöèîíèðîâàòü ïðè ïîÿâëåíèè îòêà- çîâ, êðàòíîñòü êîòîðûõ íå ïðåâûøàåò çàäàííóþ. Îäíàêî ðåàëüíî ÎÌÑ ìîæåò ïðîäîëæàòü ôóíêöèîíèðîâàòü è ïðè ïîÿâëåíèè îòêàçîâ áîëåå âûñî- êîé êðàòíîñòè, ÷òî äîëæíî áûòü àäåêâàòíî îòîáðàæåíî íà GL-ìîäåëè. Â ïîäîáíûõ ñëó÷àÿõ íåîáõîäèìî ðåøàòü çàäà÷ó ïðåîáðàçîâàíèÿ ìîäåëè áàçîâîé ÎÌÑ ê ìîäåëè íåáàçîâîé ÎÌÑ. Ïîÿâëåíèå ñîîòâåòñòâóþùèõ âåêòîðîâ ñîñòîÿíèÿ ñèñòåìû ïðèâåäåò ê èñ÷åçíîâåíèþ êàêèõ-òî îñíîâíûõ ðåáåð áàçîâîé GL-ìîäåëè. Áóäåì ðàññìàòðèâàòü ñëó÷àé èñ÷åçíîâåíèÿ òîëüêî ïàðû îñíîâíûõ ðåáåð (â ñîîòâåòñòâèè ñ ðàññóæäåíèÿìè, èçëîæåí- íûìè âûøå) ïðè ïîÿâëåíèè îäíîãî òàêîãî âåêòîðà, õîòÿ ðåàëüíî èñ÷åçíóòü ìîæåò áîëüøåå ÷èñëî îñíîâíûõ ðåáåð (ýòî çàâèñèò îò àëãîðèòìà ôîðìèðî- âàíèÿ ðåáåðíûõ ôóíêöèé äëÿ ìîäåëè). Ïîíÿòíî, ÷òî èñ÷åçíîâåíèå ïàðû ðåáåð âåäåò ê ïîòåðå ñâÿçíîñòè ãðàôà áàçîâîé ìîäåëè. Îäíèì èç ïóòåé îáåñïå÷åíèÿ àäåêâàòíîñòè ìîäåëè (ò.å. ñîõðàíåíèÿ ñâÿçíîñòè ãðàôà) äëÿ óêàçàííûõ ñëó÷àåâ ÿâëÿåòñÿ ïðîâåäåíèå äîïîëíèòåëüíûõ ðåáåð ñî ñâîèìè ôóíêöèÿìè [4]. Îáîçíà÷èì L ìíîæåñòâî ïàð ðåáåð, ïðè èñêëþ÷åíèè êîòîðûõ íåîáõî- äèìî îáåñïå÷èòü ñâÿçíîñòü ãðàôà, à åãî ìîùíîñòü îáîçíà÷èì l. Êàæäàÿ ïàðà ñîîòâåòñòâóåò îäíîìó èç âåêòîðîâ ñîñòîÿíèÿ ñèñòåìû. Â äàëüíåéøåì äëÿ êðàòêîñòè ñîõðàíåíèå ñâÿçíîñòè ãðàôà ïðè èñ÷åçíîâåíèè ïàð ðåáåð (èç ìíîæåñòâà L) áóäåì íàçûâàòü áëîêèðîâêîé ìíîæåñòâà L, èëè ïðîñòî áëîêèðîâêîé. Â ñîîòâåòñòâèè ñ àëãîðèòìîì, îïèñàííûì â [4], ðåáðà ãðàôà èñõîäíîé GL-ìîäåëè ðàçáèâàåì íà äâà èëè áîëåå íåïóñòûõ, íåïåðåñåêàþùèõñÿ S-ïîäìíîæåñòâà: â îäíîì S-ïîäìíîæåñòâå ïðèñóòñòâóþò òîëüêî òàêèå ðåáðà, âûáîðêà ïî äâà êîòîðûõ íå ñîâïàäàåò íè ñ îäíèì ýëåìåíòîì èç Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 63 ìíîæåñòâà L. Îäíèì èç âàæíûõ êðèòåðèåâ ðàçáèåíèÿ ãðàôà íà S-ïîäìíî- æåñòâà ÿâëÿåòñÿ èõ ìèíèìàëüíîå ÷èñëî. Çàòåì ïðîâîäèì äîïîëíèòåëüíûå ðåáðà â ñîîòâåòñòâèè ñ ðàçáèåíèåì ãðàôà íà S-ïîäìíîæåñòâà. Ôàêòè÷åñêè ðàçáèåíèå ìíîæåñòâà ðåáåð ãðàôà íà S-ïîäìíîæåñòâà îïðåäåëÿåò ÷èñëî è ïðîâåäåíèå äîïîëíèòåëüíûõ ðåáåð, êîòîðûå îáåñïå÷èâàþò ñîõðàíåíèå ñâÿçíîñòè ãðàôà ïðè èñ÷åçíîâåíèè îïðåäåëåííûõ ïàð ðåáåð. Ïîñêîëüêó ïðîâåäåíèå äîïîëíèòåëüíûõ ðåáåð ôàêòè÷åñêè îïðåäåëÿåòñÿ ðàçáèåíèåì ãðàôà íà S-ïîäìíîæåñòâà, áóäåì ñ÷èòàòü, ÷òî S-ïîäìíîæåñòâà áëîêèðóþò ïàðû ðåáåð èç ìíîæåñòâà L. Ïóñòü p — ÷èñëî S-ïîäìíîæåñòâ, à èõ ìîù- íîñòè îáîçíà÷èì ñîîòâåòñòâåííî s1, s2, ..., sp. Ñîãëàñíî ìåòîäó, ïðåäëîæåí- íîìó â [4], ÷èñëî äîïîëíèòåëüíûõ ðåáåð n = ] p/2 [. Íà ýòàïå ïðîåêòèðîâàíèÿ ìîäåëè è âíåñåíèÿ â íåå èçìåíåíèé ðàç- ðàáîò÷èêó íåîáõîäèìî çíàòü ãðàíè÷íûå çíà÷åíèÿ ÷èñëà ââîäèìûõ äëÿ îáåñïå÷åíèÿ àäåêâàòíîñòè ìîäåëè äîïîëíèòåëüíûõ ðåáåð. Èíòåðåñ òàêæå ïðåäñòàâëÿåò ïðåäåëüíîå ÷èñëî âåêòîðîâ, áëîêèðóåìûõ ñ ïîìîùüþ çàäàí- íîãî ÷èñëà äîïîëíèòåëüíûõ ðåáåð. Ñôîðìóëèðóåì ñëåäóþùóþ çàäà÷ó: îïðåäåëèòü ãðàíèöû p (÷èñëî S-ïîäìíîæåñòâ), èñõîäÿ èç çàäàííûõ çíà÷åíèé r è l ; îïðåäåëèòü ãðàíèöû äëÿ l ïðè çàäàííûõ p è r . Ïîíÿòíî, ÷òî çíà÷åíèå l ìîæåò êîëåáàòüñÿ â ïðåäåëàõ îò åäèíèöû (íå ïóñòîå ìíîæåñòâî L) äî C r 2 (êàê ïåðåáîð âñåâîçìîæíûõ ïàð ðåáåð), à çíà÷åíèå p — â ïðåäåëàõ îò åäèíèöû (ïðè ïóñòîì ìíîæåñòâå L) äî r, êîãäà êàæäîå ðåáðî çàäàeò îäíî S-ïîäìíîæåñòâî (â ýòîì ñëó÷àå l = C r 2 ). Îñíîâíûå îïðåäåëåíèÿ. Ïóñòü ñóùåñòâóþò âñå âîçìîæíûå êîìáèíàöèè ïî l ïàð ðåáåð 1 2 � �l C r èñõîäíîé GL-ìîäåëè: k1, k2, …, kCr 2 . Êàæäàÿ êîìáè- íàöèÿ ki ïîòðåáóåò äëÿ ðåøåíèÿ çàäà÷è áëîêèðîâêè ñâîåãî îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâà ðåáåð GL-ìîäåëè íà pi S-ïîäìíîæåñòâ. Îïðåäåëåíèå 1. Âåëè÷èíà pmax (l) åñòü ìàêñèìàëüíîå çíà÷åíèå èç pi, pmin(l) — ìèíèìàëüíîå èç pi, ò. å. âåðõíÿÿ ãðàíèöà pmax(l) — ýòî òàêîå ÷èñëî S-ïîäìíîæåñòâ, êîòîðîå ñïîñîáíî áëîêèðîâàòü ëþáîé íàáîð ýëåìåíòîâ ìíîæåñòâà L ìîùíîñòüþ l, âûïîëíÿÿ óñëîâèå ìèíèìàëüíîñòè ÷èñëà S-ïîä- ìíîæåñòâ. Ïóñòü pmin (l) — ìèíèìàëüíîå ÷èñëî S-ïîäìíîæåñòâ, îáåñïå÷è- âàþùåå âîçìîæíîñòü áëîêèðîâêè õîòÿ áû îäíîãî íàáîðà èç l ïàð ðåáåð, ïðè÷åì äîáàâëåíèå õîòÿ áû îäíîãî ýëåìåíòà â ìíîæåñòâî L îäíîçíà÷íî ïîòðåáîâàëî áû ðàçáèåíèÿ íà áîëüøåå, ÷åì pmin (l), ÷èñëî S-ïîäìíîæåñòâ. Ñóùåñòâóþò âñå âîçìîæíûå ðàçáèåíèÿ 1 2 , ,..., t ðåáåð èñõîäíîé GL-ìîäåëè íà p S-ïîäìíîæåñòâ. Êàæäîå ðàçáèåíèå i ÿâëÿåòñÿ îïòèìàëü- íûì äëÿ îñóùåñòâëåíèÿ áëîêèðîâàíèÿ ðàçëè÷íûõ ìíîæåñòâ ïàð ðåáåð, ñðåäè êîòîðûõ èìååòñÿ íàèáîëüøåå ïî ìîùíîñòè, âêëþ÷àþùåå �li ïàð, è íàèìåíüøåå, âêëþ÷àþùåå ��li ïàð. À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê 64 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1 Îïðåäåëåíèå 2. Ìàêñèìàëüíîå èç �li îáîçíà÷èì lmax (p), à ìèíèìàëüíîå èç ��li — lmin (p), ò. å. lmax (p) — ýòî ìàêñèìàëüíîå ÷èñëî ïàð ðåáåð, äëÿ áëîêèðîâêè êîòîðûõ äîñòàòî÷íî ðàçáèåíèÿ ãðàôà íà p S-ïîäìíîæåñòâ; lmin (p) — òàêîå ìèíèìàëüíîå çíà÷åíèå ìîùíîñòè ìíîæåñòâà L, äëÿ áëîêè- ðîâêè êîòîðîãî òðåáóåòñÿ ðàçáèåíèå ðåáåð ãðàôà íà p S-ïîäìíîæåñòâ. Ýòî òàêàÿ êîìáèíàöèÿ èç l ïàð, ÷òî óäàëåíèå õîòÿ áû îäíîãî ýëåìåíòà èç ìíîæåñòâà L ïîòðåáîâàëî áû ìåíåå ÷åì p S-ïîäìíîæåñòâ (ñ ó÷åòîì òðåáî- âàíèÿ ìèíèìàëüíîñòè ê èõ ÷èñëó). Âçàèìíàÿ îáðàòèìîñòü ãðàíè÷íûõ ôóíêöèé. Ïîêàæåì, ÷òî ïðè îñóùåñòâëåíèè îïòèìàëüíîãî ðàçáèåíèÿ ìíîæåñòâà ðåáåð GL-ìîäåëè íà S-ïîäìíîæåñòâà [4] ãðàíè÷íûå ôóíêöèè pmin(l) è lmax(p) ÿâëÿþòñÿ âçàèìíî îáðàòíûìè. Ïóñòü l l p* max * ( )� , ò.å. ñðåäè âñåõ îïòèìàëüíûõ ðàçáèåíèé ðåáåð ãðà- ôà íà p* S-ïîäìíîæåñòâ ñóùåñòâóåò òàêîå, êîòîðîå áëîêèðóåò ìíîæåñòâî ïàð ðåáåð, èìåþùåå íàèáîëüøóþ ìîùíîñòü, ðàâíóþ l* . Ïîíÿòíî, ÷òî åñëè çàäàíî êàêîå-òî ìíîæåñòâî ïàð ðåáåð L, âêëþ÷àþùåå l* ïàð, òî äëÿ åãî áëîêèðîâàíèÿ ïîíàäîáèòñÿ íå ìåíåå ÷åì p* S-ïîäìíîæåñòâ. Â òî æå âðåìÿ ñóùåñòâóåò òàêîå ìíîæåñòâî p l min * ( ) ìîùíîñòüþ l* ïàð, äëÿ êîòîðîãî ðàç- áèåíèå íà p* S-ïîäìíîæåñòâ îêàçûâàåòñÿ äîñòàòî÷íûì. Ñëåäîâàòåëüíî, â òî÷êàõ ïðîñòðàíñòâà (p* , l* ) çíà÷åíèÿ ôóíêöèé p l min * ( ) è l p max * ( ) ñîâ- ïàäàþò. Ïîäîáíûå ðàññóæäåíèÿ ñïðàâåäëèâû äëÿ ëþáûõ çíà÷åíèé l è p, à çíà÷èò, ýòè ôóíêöèè ÿâëÿþòñÿ âçàèìíî îáðàòíûìè. Ïðîâåäÿ àíàëîãè÷íûå ðàññóæäåíèÿ îòíîñèòåëüíî äðóãîé ïàðû ãðàíè÷íûõ ôóíêöèé, ïðèõîäèì ê âûâîäó, ÷òî ôóíêöèè l p min ( ) è p l max ( ) òàêæå âçàèìíî îáðàòíû. Íà îñíîâàíèè èçëîæåííîãî ìîæíî ñäåëàòü âûâîä î òîì, ÷òî äëÿ ïîèñ- êà ãðàíè÷íûõ ôóíêöèé äîñòàòî÷íî íàéòè òîëüêî äâå èç íèõ, îïðåäåëÿÿ äðóãèå êàê âçàèìíî îáðàòíûå. Íèæíÿÿ ãðàíèöà l. Ââåäåì ïîíÿòèå V-ãðàôà [4]. Ýòî íåîãðàô, â êîòî- ðîì âåðøèíàì ñîîòâåòñòâóþò ðåáðà èñõîäíîãî ãðàôà GL-ìîäåëè, à ðåáðà ïðîâîäÿòñÿ â ñîîòâåòñòâèè ñ ïàðàìè ìíîæåñòâà L. Ñëåäóåò çàìåòèòü, ÷òî ïðàâèëüíàÿ ðàñêðàñêà âåðøèí V-ãðàôà, êàê ïîêàçàíî â [4], îïðåäåëÿåò ðàçáèåíèå èñõîäíîãî ãðàôà íà S-ïîäìíîæåñòâà, ïðè÷åì ðåáðà, èìåþùèå îäèí öâåò, âõîäÿò â îäíî S-ïîäìíîæåñòâî. Íà ðèñ. 2 ïðèâåäåí ïðèìåð V-ãðàôà, åãî ðàñêðàñêè è ñîîòâåòñòâóþùåãî ðàçáèåíèÿ ìíîæåñòâà ðåáåð èñõîäíîãî ãðàôà ìîäåëè íà S-ïîäìíîæåñòâà äëÿ r = 8. Äîïóñòèì, p — õðîìàòè÷åñêîå ÷èñëî V-ãðàôà, êîòîðûé áóäåì ñòðîèòü, èñõîäÿ èç GL-ìîäåëè ÎÌÑ. Ïîñêîëüêó l ðàâíî ÷èñëó ðåáåð V-ãðàôà, äëÿ ðåøåíèÿ ïîñòàâëåííîé çàäà÷è äîñòàòî÷íî îïðåäåëèòü ìèíèìàëüíîå ÷èñëî ðåáåð, ôîðìèðóþùèõ V-ãðàô, òðåáóþùèé p êðàñîê äëÿ ïðàâèëüíîé ðàñ- êðàñêè ñâîèõ âåðøèí. Èçâåñòíî, ÷òî õðîìàòè÷åñêîå ÷èñëî íå ìåíüøå Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 65 ÷èñëà âåðøèí â êëèêå ãðàôà, ò. å. â ìàêñèìàëüíî ïîëíîì ïîäãðàôå. Ñëåäî- âàòåëüíî, äîñòàòî÷íî âûáðàòü òàêîå ÷èñëî ðåáåð, êîòîðîå â îïòèìàëüíîì ñëó÷àå çàäàâàëî áû ïîëíûé ïîäãðàô, ñîñòîÿùèé èç p âåðøèí. Òàêèì îáðàçîì, çàäà÷à ñâåäåíà ê îïðåäåëåíèþ ÷èñëà ðåáåð ïîëíîãî ãðàôà, èìåþ- ùåãî p âåðøèí, à çíà÷èò, èñêîìàÿ ãðàíèöà èìååò âèä l p p p min ( ) ( ) � �1 2 . Ïîñêîëüêó l p min ( )è p l max ( )— âçàèìíî îáðàòíûå ôóíêöèè, ïðåäñòàâèâ l êàê àðãóìåíò ôóíêöèè p, ðåøèâ êâàäðàòíîå óðàâíåíèå, ëåãêî îïðåäåëÿåì, âåðõíþþ ãðàíèöó ÷èñëà S-ïîäìíîæåñòâ: p l l max ( ) � � �1 1 8 2 . (4) Âåðõíÿÿ ãðàíèöà l. Äëÿ ïîèñêà ãðàíèöû l p max ( ) âíîâü îáðàòèìñÿ ê V-ãðàôó, ðåáðà êîòîðîãî ñîîòâåòñòâóþò ýëåìåíòàì ìíîæåñòâà L. Îïðå- äåëèì, êàêîâà äîëæíà áûòü ñòðóêòóðà V-ãðàôà ñ ìàêñèìàëüíûì ÷èñëîì ðåáåð, ÷òîáû îí ïðè ýòîì îñòàâàëñÿ p-ðàñêðàøèâàåìûì. Ðàçîáüåì âåð- øèíû èñêîìîãî V-ãðàôà (îíè ñîîòâåòñòâóþò ðåáðàì GL-ìîäåëè) íà p ãðóïï è ïðîâåäåì âñå âîçìîæíûå ðåáðà ìåæäó âåðøèíàìè èç ðàçëè÷íûõ ãðóïï. Ïîíÿòíî, ÷òî òàêîé ãðàô ÿâëÿåòñÿ p-ðàñêðàøèâàåìûì, ïîñêîëüêó âåðøèíû, âõîäÿùèå â îäíó ãðóïïó, îïðåäåëÿþò âíóòðåííå óñòîé÷èâîå ìíîæåñòâî. Îäíàêî ïðè ýòîì, â çàâèñèìîñòè îò ñïîñîáà ðàçáèåíèÿ, âîç- ìîæíîå ÷èñëî ðåáåð, ñîõðàíÿÿ ñâîéñòâî p-ðàñêðàøèâàåìîñòè, áóäåò ðàç- ëè÷íûì. Äëÿ ðåøåíèÿ çàäà÷è äîñòàòî÷íî âûáðàòü ìîùíîñòè ãðóïï òàêè- ìè, ÷òîáû ÷èñëî ðåáåð V-ãðàôà áûëî ìàêñèìàëüíûì. Ïîñêîëüêó âñå âåðøèíû, âõîäÿùèå â îäíó ãðóïïó, èìåþò îäèí öâåò, ñîîòâåòñòâóþùèå èì ðåáðà â GL-ìîäåëè, áóäóò ïðèíàäëåæàòü îäíîìó S-ïîäìíîæåñòâó. Èñõîäÿ èç ýòîãî, ìíîæåñòâî L ñëåäóåò ôîðìèðîâàòü êàê ìíîæåñòâî ïàð { , }R RS w S q i j , ãäå w = 1 .. si , q = 1 .. sj , i = 1 .. p – 1, j = (i + 1) .. p; RS w i — ðåáðî èç Si-ïîäìíî- À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê 66 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1 S 5 1,2 4 3 S2 S 3 S 4 1 5 4 3 2 L =({1, 3},{1, 4} , {1, 5},{3, 4}, {3,5},{4, 5}) Ðèñ. 2. Ïîñòðîåíèå V-ãðàôà è ñîîòâåòñòâóþùèõ S-ïîäìíîæåñòâ æåñòâà. Íàéäåì òàêèå çíà÷åíèÿ s1, s2, …, sp, ïðè êîòîðûõ ìîùíîñòü ìíî- æåñòâà L áóäåò ìàêñèìàëüíîé. Î÷åâèäíî, ÷òî1 1� � � �s r pi , ãäå i = 1 ... p. Ïóñòü èìåþòñÿ S1, S2, … ..., Sp-ïîäìíîæåñòâà è ñîîòâåòñòâóþùèå ìîùíîñòè s1, s2, ..., sp. Èñõîäÿ èç ñêàçàííîãî âûøå, ìîæíî çàïèñàòü ñëåäóþùåå: l s s s C C C C C Cp S S S S Spmax ( , ,..., ) ( ... ) ( 1 2 1 1 1 1 1 1 2 3 2 � � � � � S SC p3 1 1 � � �... ) ... ... ( ... ) ... ( ) � � � � � � � � � � C C s s s s s s s sS S p P P i j i p p1 1 1 1 2 3 1 , j j i p � � 1 . (5) Çàìåòèì, ÷òî s s s s rP i i p 1 2 1 � � � � � � ... . Îïðåäåëèì çíà÷åíèÿ àðãóìåíòîâ si, ïðè êîòîðûõ ôóíêöèÿ lmax(s1, s2, ... ..., sp) ïðèìåò ìàêñèìàëüíîå çíà÷åíèå. Ýòî ïðîèçîéäåò ïðè s s s 1 2 3 � � � ... ... /� �s r pP . Äåéñòâèòåëüíî, l s s s s s s p i j i j j i p i i p max , ( , ,..., ) 1 2 1 1 2 � � � � � � � � � � � � � si i p 2 1 2 . Îòñþäà ñëåäóåò, ÷òî l s s spmax ( , , ..., ) 1 2 äîñòèãàåò ìàêñèìóìà, êîãäà çíà- ÷åíèå si i p 2 1� ìèíèìàëüíî. Ïóñòü � �s r p/ , òîãäà si ìîæíî ïðåäñòàâèòü êàê s si i� � �( )� , ãäå � i i p � � 1 0, � i is� , i = 1, ..., p. Âûïîëíèì ïðåîáðàçîâàíèÿ: s s s si i p i p i i p i p i i p 2 1 1 2 1 2 1 1 2 � � � � � � �� ( ) ( )� � � �i i p ip s2 2 1 2 � � � � ( ) . Ïîñêîëüêó� i 2 0� , ñóììà si i p 2 1� ïðèìåò ìèíèìàëüíîå çíà÷åíèå ïðè� i 2 0� , ò. å. êîãäà s s r pi � � � / , ÷òî è òðåáîâàëîñü äîêàçàòü. Ïîäñòàâèâ â (4) çíà÷åíèå s r pi � / , i = 1, 2, …, p , ïîëó÷èì l r p r p pmax ( , ) ( ) � � 2 2 1 . Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 67 Ñëåäóåò çàìåòèòü, ÷òî çíà÷åíèÿ ýòîé ôóíêöèè ÿâëÿþòñÿ äåéñòâèòåëü- íûìè ÷èñëàìè, íî íà ñàìîì äåëå ôóíêöèÿ lmax äîëæíà ïðèíèìàòü íàòó- ðàëüíûå çíà÷åíèÿ. Ïîñêîëüêó s s sp1 2 , ,..., òàêæå ìîãóò ïðèíèìàòü òîëüêî íàòóðàëüíûå çíà÷åíèÿ, s r p i � � � � � � � ëèáî s r p i � � � � � � � �1. Ïóñòü s r p 1 � � � � � � � , à îñòàëü- íûå s sp2 , ..., ðàâíû ëèáî r p � � � � � � �1, ëèáî r p � � � � � � , ÷òî îïðåäåëÿåòñÿ îñòàòêîì r p � � � � � � , êîòîðûé îáîçíà÷èì .Ó÷èòûâàÿ, ÷òî s ri i p � � 1 , à òàêæå òîò ôàêò, ÷òî âçàèì- íîå ðàñïîëîæåíèå S-ïîäìíîæåñòâ îäíî îòíîñèòåëüíî äðóãîãî íå èìååò çíà÷åíèÿ, ìîæíî ñ÷èòàòü, ÷òî s s s r p p1 2 , , ..., � � � � � � � � , s s r p p p� � � � � � � � � � , ..., 1. Ïîäñòàâèâ íîâûå çíà÷åíèÿ àðãóìåíòîâ â ôîðìóëó (5) è óïðîñòèâ åå, ïîëó÷èì � � � � � � � � � � � � � � � � � � � � � � � l r p C r p C r p Cpmax ( , ) 2 2 2 2 1 1 C r p r p p� � � � � � � � � � � � � � � � � � � � 1 1 � � � � � � � � � � � � � � � � � � p p r p r p p ( ) ( ) 1 2 1 2 1 2 2 . Ñ ïîìîùüþ ýòîé ôîðìóëû íàõîäèì òî÷íûå çíà÷åíèÿ. Â ðåçóëüòàòå äîñ- òàòî÷íî áîëüøîãî ÷èñëà ýêñïåðèìåíòîâ óñòàíîâëåíî, ÷òî ñðåäíåå çíà÷å- íèå àáñîëþòíîé ïîãðåøíîñòè çàâèñèò îò çíà÷åíèÿ r: � � !l r p l r p r max max ( , ) ( , ) ,00386 . À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê 68 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1 l P min (l) 1 3 5 7 9 11 13 15 17 19 21 23 25 27 Pmax (l) 7 5 3 1 0 p Ðèñ. 3. Ãðàíèöû P l min ( ) è P l max ( ) äëÿ ñëó÷àÿ r� 8 Äàëåå â ðàñ÷åòàõ áóäåì èñïîëüçîâàòü ôóíêöèþ l r p max ( , ), òàê êàê îíà íå ñîäåðæèò öåëî÷èñëåííîãî äåëåíèÿ è, ñëåäîâàòåëüíî, áîëåå ïðîñòà â ïðèìåíåíèè. Ïîñêîëüêó l p max ( ) è p l min ( ) — ôóíêöèè âçàèìíî îáðàòíûå, ïðåäñòàâèâ l êàê àðãóìåíò ôóíêöèè p, ëåãêî îïðåäåëèì íèæíþþ ãðàíèöó ÷èñëà S-ïîäìíîæåñòâ: p l r r r l min ( , ) � � 2 2 2 . (6) Ïîëó÷åííûå âûøå ðåçóëüòàòû ìîæíî ïðåäñòàâèòü â âèäå íåðàâåíñòâ: r r l p r l l2 2 2 1 1 8 2� � � � � ( , ) ; p p l p r p p r p r p p ( ) ( , ) ( ) ( ) � � � � � � � � � � � � � � � � � � � � 1 2 1 2 1 2 12 2 . Ãðàíèöû ÷èñëà S-ïîäìíîæåñòâ, âû÷èñëåííûå äëÿ êîíêðåòíîãî ïðè- ìåðà ïî ôîðìóëàì (4) è (6), ïîêàçàíû íà ðèñ. 3. Íàéäåííûå ãðàíèöû íå ÿâëÿþòñÿ íàòóðàëüíûìè ÷èñëàìè, ïîýòîìó îêðóãëèì íèæíþþ ãðàíèöó â ñòîðîíó ìåíüøåãî öåëîãî ÷èñëà, à âåðõíþþ — â ñòîðîíó áîëüøåãî, ÷òîáû íå ïîòåðÿòü èõ âîçìîæíûå çíà÷åíèÿ: r r l p r l l2 2 2 1 1 8 2� � � � � � � � � � �� ( , ) . Ñëåäóåò çàìåòèòü, ÷òî ïîëó÷åííàÿ ôîðìóëà (6) äëÿ íèæíåé ãðàíèöû ÷èñëà S-ïîäìíîæåñòâ ñîâïàäàåò ñ ðåçóëüòàòàìè, ïðèâåäåííûìè â ðàáîòå [5] äëÿ íèæíåé ãðàíèöû õðîìàòè÷åñêîãî ÷èñëà ïðîèçâîëüíîãî ãðàôà, ÷òî ïîäòâåðæäàåò ïðàâèëüíîñòü äàííûõ ðàññóæäåíèé. Âûâîäû. Ïîëó÷åííûå ðåçóëüòàòû äàþò âîçìîæíîñòü îöåíèòü ñëîæ- íîñòü GL-ìîäåëè ðàçðàáàòûâàåìîé ÎÌÑ íà ðàííèõ ñòàäèÿõ ïðîåêòèðî- âàíèÿ. Åå ñëîæíîñòü çàâèñèò îò ÷èñëà ìîäóëåé ñèñòåìû, ñòåïåíè îòêàçî- óñòîé÷èâîñòè, à òàêæå îò ìíîæåñòâà âåêòîðîâ ñîñòîÿíèÿ ÎÌÑ, êîòîðûå îòëè÷àþò ìîäåëü ïðîåêòèðóåìîé ñèñòåìû îò áàçîâîé. Ïîëó÷åííûå îöåíêè ìîãóò ïîìî÷ü ðàçðàáîò÷èêó çàðàíåå îïðåäåëèòü ðåñóðñû (âû÷èñëèòåëüíûå è âðåìåííûå), íåîáõîäèìûå äëÿ ðàñ÷åòà íàäåæíîñòè ÎÌÑ ñ òðåáóåìîé òî÷íîñòüþ. The main edge number estimates are given for base GL-models construction with minimum failed edges number which reflect reaction of failure-resistance multi-module system for failure occurrence. The boundary estimates of additional edges number are given to transform base GL-models to non-base. Ãðàíè÷íûå îöåíêè ÷èñëà ðåáåð GL-ìîäåëåé ïîâåäåíèÿ ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 1 69 1. Õàð÷åíêî Â. Ñ., Æèõàðåâ Â. ß., Èëþøêî Â. Ì., Íå÷èïîðóê Í. Â. Ìíîãîâåðñèîííûå ñèñòåìû, òåõíîëîãèè, ïðîåêòû. — Õàðüêîâ : Íàöèîíàëüíûé àýðîêîñìè÷åñêèé óí-ò «Õàðüêîâñêèé àâèàöèîííûé èí-ò», 2003. — 486 ñ. 2. Ðîìàíêåâè÷ À. Ì., Êàðà÷óí Ë. Ô., Ðîìàíêåâè÷ Â. À. Ãðàôî-ëîãè÷åñêèå ìîäåëè äëÿ àíàëèçà ñëîæíûõ îòêàçîóñòîé÷èâûõ âû÷èñëèòåëüíûõ ñèñòåì//Ýëåêòðîí. ìîäåëèðîâà- íèå. — 2001. — 23, ¹ 1. — Ñ. 102—111. 3. Ðîìàíêåâè÷ Â. À., Ïîòàïîâà Å. Ð., Áàõòàðè Õåäàÿòîëëàõ, Íàçàðåíêî Â. Â. GL-ìîäåëü ïîâåäåíèÿ îòêàçîóñòîé÷èâûõ ìíîãîïðîöåññîðíûõ ñèñòåì ñ ìèíèìàëüíûì ÷èñëîì òåðÿåìûõ ðåáåð // Â³ñíèê ÍÒÓÓ «ÊÏ²». ²íôîðìàòèêà, óïðàâë³ííÿ òà îá÷èñëþâàëüíà òåõí³êà. — 2006. — ¹ 45. — Ñ. 93—100. 4. Ðîìàíêåâè÷ À. Ì., Èâàíîâ Â.Â., Ðîìàíêåâè÷ Â.À. Àíàëèç ÎÌÑ ñî ñëîæíûì ðàñïðå- äåëåíèåì îòêàçîâ íà îñíîâå öèêëè÷åñêîé GL-ìîäåëè// Ýëåêòðîí. ìîäåëèðîâàíèå. — 2004. — 26, ¹ 5. — Ñ. 67—81. 5. Geller D. P. Problem 5713// American Mathematical Monthly. — 1970. —Vol. 77, ¹ 1. — Ð. 85. Ïîñòóïèëà 19.04.07 ÐÎÌÀÍÊÅÂÈ× Àëåêñåé Ìèõàéëîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð êàô. ñïåöèàëèçèðîâàííûõ êîìïüþòåðíûõ ñèñòåì ÍÒÓÓ «ÊÏÈ». Â1961 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ñàìîïðîâåðÿåìûå ñõåìû, ïñåâäîñëó÷àéíîå òåñòèðîâàíèå öèôðîâîé àïïàðàòóðû, îòêàçîóñòîé÷èâûå ìíîãîïðîöåññîðíûå ñèñòåìû. ÐÎÌÀÍÊÅÂÈ× Âèòàëèé Àëåêñååâè÷, êàíä. òåõí. íàóê, äîöåíò êàô. ñïåöèàëèçèðîâàííûõ êîìïüþòåðíûõ ñèñòåì ÍÒÓÓ «ÊÏÈ». â 1996 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìîäåëè ïîâåäåíèÿ îòêàçîóñòîé÷èâûõ ìíîãîïðîöåññîðíûõ ñèñòåì, ðàñ÷åò íàäåæíîñòè. ÌÀÉÄÀÍÞÊ Èâàí Âèêòîðîâè÷, àñïèðàíò êàô. ñïåöèàëèçèðîâàííûõ êîìïüþòåðíûõ ñèñòåì ÍÒÓÓ «ÊÏÈ». Â 2007 ã. îêîí÷èë Êèåâñêèé ïîëèòåõíè÷åñêèé èí-ò. Îáëàñòü íàó÷íûõ èññëåäî- âàíèé — îòêàçîóñòîé÷èâûå ìíîãîïðîöåññîðíûå ñèñòåìû. À. Ì. Ðîìàíêåâè÷, Â. À. Ðîìàíêåâè÷, È. Â. Ìàéäàíþê 70 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 1

Граничные оценки числа ребер GL-моделей поведения отказоустойчивых многопроцессорных систем в потоке отказов

Institution

Ähnliche Einträge