Составители:
Рубрика:
46
ïðîèçâîäñòâîì (â ïðîöåññàõ ïðîåêòèðîâàíèÿ, ðàçðàáîòêè è èñïûòà-
íèé) è ñîñòàâëÿþò äîñòóïíûé è ÷óâñòâèòåëüíûé ýòàëîí ãîòîâîé ïðî-
äóêöèè, êîíòðîëü êîòîðîãî íåîáõîäèìî ðåãóëÿðíî îñóùåñòâëÿòü â
ïåðèîä åå ýêñïëóàòàöèè.
Ïåðâîé òîïîëîãè÷åñêîé ìåðîé ñëîæíîñòè ÿâëÿåòñÿ öèêëîìàòè-
÷åñêàÿ ìåðà Ìàê-Êåéáà.  åå îñíîâå ëåæèò èäåÿ îöåíêè ñëîæíîñòè
ÏÑ ïî ÷èñëó áàçèñíûõ ïóòåé â åãî óïðàâëÿþùåì ãðàôå, ò. å. òàêèõ
ïóòåé, êîìïîíóÿ êîòîðûå ìîæíî ïîëó÷èòü âñåâîçìîæíûå ïóòè èç
âõîäà ãðàôà â âûõîäû. Öèêëîìàòè÷åñêîå ÷èñëî λ
(G) îðãðàôà G ñ
n-âåðøèíàìè, m-äóãàìè è p-êîìïîíåíòàìè ñâÿçíîñòè åñòü âåëè÷èíà
λ
(G) = m – n + p.
Èìååò ìåñòî òåîðåìà î òîì, ÷òî ÷èñëî áàçèñíûõ ïóòåé â îðãðàôå
ðàâíî åãî öèêëîìàòè÷åñêîìó ÷èñëó, óâåëè÷åííîìó íà åäèíèöó. Ïðè
ýòîì öèêëîìàòè÷åñêîé ñëîæíîñòüþ ÏÑ Ð ñ óïðàâëÿþùèì ãðàôîì G
íàçûâàåòñÿ âåëè÷èíà ν(G) = λ(G) +1 = m – n + 2. Ïðàêòè÷åñêè
öèêëîìàòè÷åñêàÿ ñëîæíîñòü ÏÑ ðàâíà ÷èñëó ïðåäèêàòîâ ïëþñ åäè-
íèöà, ÷òî ïîçâîëÿåò âû÷èñëÿòü åå áåç ïîñòðîåíèÿ óïðàâëÿþùåãî
ãðàôà ïðîñòûì ïîäñ÷åòîì ïðåäèêàòîâ. Äàííàÿ ìåðà îòðàæàåò “ïñè-
õîëîãè÷åñêóþ” ñëîæíîñòü ÏÑ.
Ê äîñòîèíñòâàì ìåðû îòíîñÿò ïðîñòîòó åå âû÷èñëåíèÿ è ïîâòîðÿ-
åìîñòü ðåçóëüòàòà, à òàêæå íàãëÿäíîñòü è ñîäåðæàòåëüíîñòü èíòåð-
ïðåòàöèè.  êà÷åñòâå íåäîñòàòêîâ ìîæíî îòìåòèòü: íå÷óâñòâèòåëü-
íîñòü ê ðàçìåðó ÏÑ, íå÷óâñòâèòåëüíîñòü ê èçìåíåíèþ åãî ñòðóêòó-
ðû, îòñóòñòâèå êîððåëÿöèè ñî ñòðóêòóðèðîâàííîñòüþ ÏÑ, îòñóòñòâèå
ðàçëè÷èÿ ìåæäó êîíñòðóêöèÿìè Ðàçâèëêà è Öèêë, îòñóòñòâèå ÷óâ-
ñòâèòåëüíîñòè ê âëîæåííîñòè öèêëîâ. Íåäîñòàòêè öèêëîìàòè÷åñêîé
ìåðû ïðèâåëè ê ïîÿâëåíèþ åå ìîäèôèêàöèé, à òàêæå ïðèíöèïèàëü-
íî èíûõ ìåð ñëîæíîñòè.
Äæ. Ìàéåðñ ïðåäëîæèë â êà÷åñòâå ìåðû ñëîæíîñòè èíòåðâàë
[ν
1
– ν
2
], ãäå ν
1
– öèêëîìàòè÷åñêàÿ ìåðà, à ν
2
– ÷èñëî îòäåëüíûõ
óñëîâèé ïëþñ åäèíèöà. Ïðè ýòîì îïåðàòîð DO ñ÷èòàåòñÿ çà îäíî
óñëîâèå, à CASE c n-èñõîäàìè çà n–1-óñëîâèé. Ââåäåííàÿ ìåðà ïî-
ëó÷èëà íàçâàíèå èíòåðâàëüíîé ìåðîé.
Ó. Õàíñåíó ïðèíàäëåæèò èäåÿ áðàòü â êà÷åñòâå ìåðû ñëîæíîñòè
ÏÑ ïàðó (öèêëîìàòè÷åñêîå ÷èñëî, ÷èñëî îïåðàòîðîâ). Èçâåñòíà òî-
ïîëîãè÷åñêàÿ ìåðà Z(G), ÷óâñòâèòåëüíàÿ ê ñòðóêòóðèðîâàííîñòè ÏÑ.
Ïðè ýòîì îíà Z(G) = V(G) (ðàâíà öèêëîìàòè÷åñêîé ñëîæíîñòè) äëÿ
ñòðóêòóðèðîâàííûõ ïðîãðàìì è Z(G) > V(G) äëÿ íåñòðóêòóðèðîâàí-
íûõ. Ê âàðèàíòàì öèêëîìàòè÷åñêîé ìåðû ñëîæíîñòè îòíîñÿò òàêæå
ìåðó Ì(G) = (V(G), C, Q), ãäå Ñ – êîëè÷åñòâî óñëîâèé, íåîáõîäèìûõ
äëÿ ïîêðûòèÿ óïðàâëÿþùåãî ãðàôà ìèíèìàëüíûì ÷èñëîì ìàðøðó-
Страницы
- « первая
- ‹ предыдущая
- …
- 44
- 45
- 46
- 47
- 48
- …
- следующая ›
- последняя »
