Lectionc1 (1132950), страница 10
Текст из файла (страница 10)
Ïóñòüñõåìå = 1 , ðåàëèçóþùåé ôóíêöèþ f = f1 îò âõîäíûõïåðåìåííûõ x = (x1 ; : : : ; xn ), è èñòî÷íèêó íåèñïðàâíîñòåé Èñîîòâåòñòâóþò ¾íåèñïðàâíûå¿ ñîñòîÿíèÿ (ñõåìû) 2 ; : : : ; s ,ãäå ñõåìà i ; i = 2; : : : ; s, ðåàëèçóåò ôóíêöèþ fi îò ïåðåìåííûõx. Ïðè ýòîì âñå ñîñòîÿíèÿ (êàê èñïðàâíîå = 1 , òàê èíåèñïðàâíûå 2 ; : : : ; s ) ðàçáèâàþòñÿ íà êëàññû (ôóíêöèîíàëüíî)íåîòëè÷èìûõ ñîñòîÿíèé, òî åñòü êëàññû ýêâèâàëåíòíîñòè ïîîòíîøåíèþ ðàâåíñòâà ðåàëèçóåìûõ ôóíêöèé, è ðàññìàòðèâàþòñÿäàëåå ñ òî÷íîñòüþ äî íåîòëè÷èìîñòè.  äàëüíåéøåì, ãîâîðÿî íåíàäåæíîé ñõåìå , áóäåì èìåòü â âèäó ïàðó (; È) è(èëè) ñîîòâåòñòâóþùåå åé ìíîæåñòâî ñõåì âìåñòå ñ òåìèôóíêöèÿìè, êîòîðûå îíè ðåàëèçóþò. Äëÿ ïðîñòîòû ðàññìîòðåíèÿáóäåì ñ÷èòàòü, ÷òî âñå ïåðåìåííûå è ôóíêöèè ÿâëÿþòñÿáóëåâñêèìè, õîòÿ ìíîãèå èçëàãàåìûå äàëåå ðåçóëüòàòû áåçñóùåñòâåííûõ èçìåíåíèé ïåðåíîñÿòñÿ íà ñëó÷àé ìíîãîçíà÷íûõôóíêöèé, ñëó÷àé âåêòîð-ôóíêöèé è äðóãèå áîëåå îáùèå ñëó÷àè.Ïóñòü (; È) óêàçàííàÿ âûøå ìîäåëü íåíàäåæíîé ñõåìû ñ âîçìîæíûìè ñîñòîÿíèÿìè = 1 ; 2 ; : : : ; s , â êîòîðûõðåàëèçóþòñÿ ÔÀË f = f1 ; f2 ; : : : ; fs ñîîòâåòñòâåííî îò ÁÏX (n), îïðåäåëåííûå íà ìíîæåñòâå íàáîðîâ A == f1 ; : : : ; p g B n .
Ðàññìîòðèì ìàòðèöó M; M 2 B p;s ,ãäåM hi; j i = fj (i ) ;ñ÷èòàÿ, ÷òî i-é ñòðîêå (j -ìó ñòîëáöó) ýòîé òàáëèöû ñîîòâåòñòâóåòíàáîð i (ñîîòâåòñòâåííî ôóíêöèÿ fj è ñîñòîÿíèå j ). Ìàòðèöà,ñîñòîÿùàÿ èç ðàçëè÷íûõ ñòîëáöîâ (ñòðîê) íàçûâàåòñÿ(ñîîòâåòñòâåííî) ìàòðèöåé. Çàìåòèì,÷òî êàæäîìó êëàññó íåîòëè÷èìûõ ñîñòîÿíèé ìîäåëè (; È)ñîîòâåòñòâóåò ãðóïïà îäèíàêîâûõ ñòîëáöîâ ìàòðèöû M èc, ñîñòîÿùóþðàññìîòðèì îòäåëèìóþ ïî ñòîëáöàì ìàòðèöó Mèç âñåõ ðàçëè÷íûõ ñòîëáöîâ ìàòðèöû M . Ïðè ýòîì áóäåìc ñâÿçàí ñ ñîîòâåòñòâóþùèìñ÷èòàòü, ÷òî êàæäûé ñòîëáåö ìàòðèöû Mêëàññîì íåîòëè÷èìîñòè ñîñòîÿíèé ìîäåëè (; È), è áóäåìïî ñòîëáöàìñòðîêàìîòäåëèìîé9.65Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèöòàáëèöåé êîíòðîëÿcíàçûâàòü Mäàííîé ìîäåëè.
Äëÿ ïðîñòîòûáóäåì, êàê ïðàâèëî, ïðåäïîëàãàòü, ÷òî âñå ñîñòîÿíèÿ ìîäåëèc. Ýòî ïðåäïîëîæåíèå,(; È) ïîïàðíî îòëè÷èìû, òî åñòü, M = Mî÷åâèäíî, íå îãðàíè÷èâàåò îáùíîñòè ðàññóæäåíèé.Ïóñòü, äàëåå, ïîìèìî òàáëèöû êîíòðîëÿ M äëÿ ìîäåëè(; È) çàäàíà öåëü êîíòðîëÿ, òî åñòü óêàçàíî ìíîæåñòâî N,ñîñòîÿùåå èç òåõ íåóïîðÿäî÷åííûõ ïàð ðàçëè÷íûõ ÷èñåëîòðåçêà [1; s], äëÿ êîòîðûõ ïàðû ñîñòîÿíèé (ñòîëáöîâ ìàòðèöûM ) ñ ñîîòâåòñòâóþùèìè íîìåðàìè íåîáõîäèìî îòëè÷àòü äðóãîò äðóãà, ñðàâíèâàÿ çíà÷åíèÿ, ðàñïîëîæåííûå â òåõ èëèèíûõ ñòðîêàõ äàííîé ïàðû ñòîëáöîâ.
 ÷àñòíîñòè, åñëè Nñîñòîèò èç âñåõ ïàð óêàçàííîãî âèäà, òî öåëüþ êîíòðîëÿÿâëÿåòñÿ, à åñëè N = f(1; 2) ; : : : ; (1; t)g,òî . Ìíîæåñòâî ñòðîê ìàòðèöûM ñ íîìåðàìè èç T; T [1; p], íàçûâàåòñÿN, èëè, èíà÷å,(M; N), åñëè äëÿ ëþáîé ïàðû (i; j ) èç N ñóùåñòâóåòt; t 2 T , òàêîå, ÷òî M ht; ii 6= M ht; j i. Ìîùíîñòü òåñòàíàçûâàåòñÿ òàêæå åãî.Çàìåòèì, ÷òî ìíîæåñòâî, ñîñòîÿùåå èç âñåõ ñòðîêòàáëèöû êîíòðîëÿ, âñåãäà îáðàçóåò òåñò. Òåñò, êîòîðûéïåðåñòàåò áûòü òåñòîì ïðè óäàëåíèè ëþáîé ñâîåé ñòðîêè,íàçûâàåòñÿ, à òåñò, êîòîðûé èìååò ìèíèìàëüíóþ ìîùíîñòü, .
 òîì ñëó÷àå, êîãäàöåëüþ êîíòðîëÿ ÿâëÿåòñÿ äèàãíîñòèêà ñõåìû (ïðîâåðêàèñïðàâíîñòè ñõåìû), òåñò íàçûâàåòñÿ(ñîîòâåòñòâåííî).Áóäåì ãîâîðèòü, ÷òî ìíîæåñòâî íàáîðîâ ; A, îáðàçóåò(; È)N,èëè, èíà÷å,(; È; N), åñëè ñîîòâåòñòâóþùèå íàáîðàìèç ñòðîêè ìàòðèöû M îáðàçóþò òåñò äëÿ (M; N). Âñåââåäåííûå âûøå ïîíÿòèÿ, êîòîðûå êàñàþòñÿ òåñòîâ äëÿ òàáëèö,áåç èçìåíåíèé ïåðåíîñÿòñÿ íà ñëó÷àé òåñòîâ äëÿ íåíàäåæíûõñõåì.äèàãíîñòèêà ñõåìûïðîâåðêà èñïðàâíîñòè ñõåìûìàòðèöû M îòíîñèòåëüíî ìíîæåñòâàäëÿäëèíîéòåñòîì äëÿòåñòîìòóïèêîâûììèíèìàëüíûìïðîâåðÿþùèìòåñò äëÿ ìîäåëèòåñò äëÿäèàãíîñòè÷åñêèìîòíîñèòåëüíî öåëè êîíòðîëÿ66Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÄëÿ îïèñàíèÿ òåñòîâ ìîæíî ââåñòè ôóíêöèþ, àíàëîãè÷íóþôóíêöèè ïîêðûòèÿ èç 6. Ïóñòü M; M 2 B p;s , îòäåëèìàÿïî ñòîëáöàì ìàòðèöà, à N ñâÿçàííàÿ ñ íåé öåëü êîíòðîëÿ.Ñîïîñòàâèì i-é ñòðîêå, i 2 [1; p], ìàòðèöû M ÁÏ yi , à êàæäîìóíàáîðó ; 2 B p , çíà÷åíèé ýòèõ ïåðåìåííûõ y = (y1 ; : : : ; yp ) ìíîæåñòâî ñòðîê ìàòðèöû M ñ íîìåðàìè èç ìíîæåñòâàI = I ( ) [1; p], ãäå i 2 I ( ) òîãäà è òîëüêî òîãäà, êîãäà hii = 1.
Ðàññìîòðèì ÔÀË F (y), äëÿ êîòîðîé F ( ) = 1òîãäà è òîëüêî òîãäà, êîãäà ñèñòåìà ñòðîê ìàòðèöû M ñíîìåðàìè èç I ( ) îáðàçóåò òåñò äëÿ (M; N), è áóäåì íàçûâàòüýòó ÔÀËäëÿ (M; N). Ñîïîñòàâèì ïàðå(M; N) ìàòðèöó M èç ìíîæåñòâà B p;S ; S = jNj, ñòîëáöûêîòîðîé ïðîíóìåðîâàíû ïàðàìè èç N, à åå ñòîëáåö ñ íîìåðîì(i; j ) 2 N ïîëó÷àåòñÿ â ðåçóëüòàòå ïîðàçðÿäíîãî ñëîæåíèÿïî ìîäóëþ 2 ñòîëáöîâ ñ íîìåðàìè i è j ìàòðèöû M . Çàìåòèì,÷òî ñòðîêè ìàòðèöû M ñ íîìåðàìè èç ìíîæåñòâà T; T [1; p], îáðàçóþò òåñò (òóïèêîâûé òåñò, ìèíèìàëüíûé òåñò)äëÿ ïàðû (M; N) òîãäà è òîëüêî òîãäà, êîãäà ñòðîêè ìàòðèöûM ñ íîìåðàìè èç T îáðàçóþò ïîêðûòèå (òóïèêîâîå ïîêðûòèå,ïîêðûòèå ìèíèìàëüíîé äëèíû) ìàòðèöû M.
Îòñþäà âûòåêàåò,â ÷àñòíîñòè, ÷òî ÔÀË òåñòà F äëÿ ïàðû (M; N) ÿâëÿåòñÿîäíîâðåìåííî ÔÀË ïîêðûòèÿ äëÿ ìàòðèöû M è îáðàòíî, àçíà÷èò äëÿ íåå, â ñèëó ëåììû 6.1, ñïðàâåäëèâî ñëåäóþùååóòâåðæäåíèå.ôóíêöèåé òåñòàÔóíêöèÿ òåñòà f (y1; : : : ; yp) äëÿ îòäåëèìîéïî ñòîëáöàì ìàòðèöû M; M 2 Bp;s, è öåëè êîíòðîëÿ Nìîæåò áûòü çàäàíà ñ ïîìîùüþ ÊÍÔËåììà 9.1.f (y 1 ; : : : ; y p ) =^(i;j )2N_16t6pM ht;ii6=M ht;j iyt ;(9.1)Êàæäàÿ ýëåìåíòàðíàÿ êîíúþíêöèÿ âèäà yt1 ytrñîêðàùåííîé ÄÍÔ ôóíêöèè f (y1; : : : ; yp), ïîëó÷àþùàÿñÿ èçÑëåäñòâèå.9.Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö67ÊÍÔ (9.1) â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ, ñîîòâåòñòâóåò òóïèêîâîìó òåñòó, ñâÿçàííîìóñ ìíîæåñòâîì T = ft1; : : : ; tr g è îáðàòíî.Íà äàííîé ëåììå îñíîâàí ñëåäóþùèé àëãîðèòì ïîñòðîåíèÿâñåõ òóïèêîâûõ òåñòîâ äëÿ ìàòðèöû M îòíîñèòåëüíî öåëèêîíòðîëÿ N:1. âûïèñûâàåì äëÿ ôóíêöèè òåñòà ÊÍÔ âèäà (9.1);2.
ðàñêðûâàÿ â íåé ñêîáêè è ïðèâîäÿ ïîäîáíûå, ïîëó÷àåìñîêðàùåííóþ ÄÍÔ ôóíêöèè òåñòà;3. ñîïîñòàâëÿåì êàæäîé ýëåìåíòàðíîé êîíúþíêöèè ýòîéñîêðàùåííîé ÄÍÔ òóïèêîâûé òåñò.Òàê, íàïðèìåð, äëÿ ïîñòðîåíèÿ âñåõ òóïèêîâûõ äèàãíîñòè÷åñêèõòåñòîâ ìàòðèöû M âèäà00B0M =B@111101101CC1A0âûïèøåì ñîîòâåòñòâóþùóþ åé ÊÍÔ (9.1):F (y1 ; y2 ; y3 ; y4 ) = (y1 _ y2 _ y3 ) (y2 _ y4 ) (y1 _ y3 _ y4 ) :Ðàñêðûâàÿ â ýòîé ÊÍÔ ñêîáêè è ïðèâîäÿ ïîäîáíûå, ïîëó÷èìñîêðàùåííóþ ÄÍÔ äëÿ ôóíêöèè òåñòà:F (y1 ; y2 ; y3 ; y4 ) = y1 y2 _ y1 y4 _ y2 y3 _ y2 y4 _ y3 y4 :Ñëåäîâàòåëüíî, òóïèêîâûìè äèàãíîñòè÷åñêèìè òåñòàìè ìàòðèöûM ÿâëÿþòñÿ ìíîæåñòâà åå ñòðîê ñ íîìåðàìèf 1; 2g ; f1 ; 4 g ; f 2 ; 3 g ; f 2; 4g ; f 3 ; 4 g :Äëÿ óïðîùåíèÿ ïðåîáðàçîâàíèé, ñâÿçàííûõ ñ ïðèìåíåíèåìîïèñàííîãî àëãîðèòìà, âìåñòî èñõîäíîé ìàòðèöû M ìîæíî68Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû , ïîëó÷àþùóþñÿðàññìàòðèâàòü îòäåëèìóþ ïî ñòðîêàì ìàòðèöó Mèç M óäàëåíèåì ïîâòîðíûõ âõîæäåíèé îäèíàêîâûõ ñòðîê.Ïðè ýòîì, î÷åâèäíî, ëþáîé òóïèêîâûé òåñò ìàòðèöû M ïîëó÷àåòñÿ â ðåçóëüòàòåèç òóïèêîâîãî òåñòà òîé æå äëèíû ìàòðèöû Mçàìåíû êàæäîé åãî ñòðîêè ðàâíîé åé ñòðîêîé ìàòðèöû M èîáðàòíî.Ðàññìîòðèì, äàëåå, íåêîòîðûå îöåíêè äëèíû äèàãíîñòè÷åñêèõòåñòîâ äëÿ ìàòðèö ñ çàäàííûì ÷èñëîì ñòîëáöîâ.Äëèíà ëþáîãî òóïèêîâîãî äèàãíîñòè÷åñêîãîòåñòà äëÿ îòäåëèìîé ïî ñòîëáöàì ìàòðèöû èç ìíîæåñòâàB p;s çàêëþ÷åíà â ïðåäåëàõ îò dlog se äî (s 1).Äîêàçàòåëüñòâî.
Ïóñòü M 2 Bp;s è ïóñòü, äëÿËåììà 9.2.îïðåäåëåííîñòè, ïåðâûå t ñòðîê ìàòðèöû M îáðàçóþòåå òóïèêîâûé äèàãíîñòè÷åñêèé òåñò. Î÷åâèäíî, ÷òî â ýòîìc, ñîñòîÿùåé èç ïåðâûõ tñëó÷àå âñå ñòîëáöû ìàòðèöû Mñòðîê ìàòðèöû M , ðàçëè÷íû è, ñëåäîâàòåëüíî, s 6 2t ,òî åñòü t > dlog se, ïîñêîëüêó ÷èñëî ðàçëè÷íûõ áóëåâûõñòîëáöîâ âûñîòû t ðàâíî 2t . Òðåáóåìàÿ íèæíÿÿ îöåíêàäëèíû äèàãíîñòè÷åñêîãî òåñòà óñòàíîâëåíà.Äîêàæåì òåïåðü, ÷òî t 6 (s 1). Äëÿ ýòîãî íà ìíîæåñòâåc ïðè ëþáîì q; q 2 [1; t], îïðåäåëèìñòîëáöîâ ìàòðèöû Mîòíîøåíèå ýêâèâàëåíòíîñòè òàê, ÷òî m0 m00 òîãäà èqq000c ñîâïàäàþòòîëüêî òîãäà, êîãäà ñòîëáöû m è m ìàòðèöû Mâ ñòðîêàõ ñ íîìåðàìè èç îòðåçêà [1; q ]. Áóäåì ñ÷èòàòü, ïîîïðåäåëåíèþ, ÷òî òðèâèàëüíîå îòíîøåíèå ñ îäíèì êëàññîì0ýêâèâàëåíòíîñòè, à ÷èñëî êëàññîâ ýêâèâàëåíòíîñòè ïî îòíîøåíèþq , ãäå q 2 [1; t], áóäåì îáîçíà÷àòü ÷åðåç (q).Èç îáùèõ ñâîéñòâ îòíîøåíèé ýêâèâàëåíòíîñòè (ñì.
1)âûòåêàåò, ÷òî ïðè ëþáîì q; q 2 [1; t), êàæäûé êëàññ ýêâèâàëåíòíîñòèïî îòíîøåíèþ ëèáî ÿâëÿåòñÿ êëàññîì ýêâèâàëåíòíîñòèqïî îòíîøåíèþ , ëèáî ïðåäñòàâëÿåò ñîáîé îáúåäèíåíèåq+19.Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö69äâóõ òàêèõ êëàññîâ è, ñëåäîâàòåëüíî, (q ) 6 (q + 1). Âñèëó òóïèêîâîñòè òåñòà ïîëó÷åííîå íåðàâåíñòâî ÿâëÿåòñÿñòðîãèì, òàê êàê ðàâåíñòâî (q ) = (q + 1) âîçìîæíî òîãäàè òîëüêî òîãäà, êîãäà êàæäûé êëàññ ýêâèâàëåíòíîñòè îòíîøåíèÿq ÿâëÿåòñÿ êëàññîì ýêâèâàëåíòíîñòè îòíîøåíèÿ q+1 è îáðàòíî,òî åñòü ñòðîêà ñ íîìåðîì (q +1) ÿâëÿåòñÿ ¾ëèøíåé¿ â ðàññìàòðèâàåìîìòåñòå.Èç äèàãíîñòè÷íîñòè òåñòà âûòåêàåò, ÷òî (t) = s, è,òàêèì îáðàçîì, âûïîëíÿþòñÿ ñîîòíîøåíèÿ1 = (0) < (1) < < (t) = s;èç êîòîðûõ ñëåäóåò, ÷òîËåììà äîêàçàíà.t 6 (s 1).Çàìå÷àíèå. Óêàçàííûå â ëåììå ãðàíèöû äîñòèãàþòñÿ: íèæíÿÿ íà ëþáîé îòäåëèìîé ïî ñòîëáöàì ìàòðèöå èç B p;s , ãäåp = dlog se, à âåðõíÿÿ íà ìàòðèöå èç B s 1;s , âñå ñòîëáöûêîòîðîé ðàçëè÷íû è ñîäåðæàò íå áîëåå îäíîé åäèíèöû (îáåìàòðèöû èìåþò åäèíñòâåííûé äèàãíîñòè÷åñêèé òåñò, ñîñòîÿùèéèç âñåõ ñòðîê).Ñëåäóþùåå óòâåðæäåíèå õàðàêòåðèçóåò ¾òèïè÷íîå¿ çíà÷åíèåäëèíû äèàãíîñòè÷åñêîãî òåñòà, òî åñòü äëèíó ìèíèìàëüíîãîäèàãíîñòè÷åñêîãî òåñòà ó ¾ïî÷òè âñåõ¿ òàáëèö êîíòðîëÿ.Ïóñòü ' (s) ; t (s) è p (s) öåëî÷èñëåííûåíåîòðèöàòåëüíûå ôóíêöèè íàòóðàëüíîãî àðãóìåíòà s, äëÿêîòîðûõËåììà 9.3.t (s) = d2 log se + ' (s) ; p (s) > t (s) ; ' (s) s!1! 1:Òîãäà ó ïî÷òè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçB p(s);s ïåðâûå t (s) ñòðîê îáðàçóþò äèàãíîñòè÷åñêèé òåñò.70Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÄîêàçàòåëüñòâî.
Çàìåòèì, ÷òî âñå ìàòðèöû èç Bp;s, ãäå p =p (s), ó êîòîðûõ ïåðâûå t = t (s) ñòðîê îáðàçóþò äèàãíîñòè÷åñêèéòåñò, îòäåëèìû ïî ñòîëáöàì. Ëåãêî âèäåòü òàêæå, ÷òî ÷èñëîòàêèõ ìàòðèö ðàâíî2t 2 t1 2t s + 1 2(p t)s == 2ps112t 1(s 1);2tà èõ äîëÿ ñðåäè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èç B p;síå ìåíüøå, ÷åì112t 1(s 1)2t2> 1 s2t > 1 2 2'(s);è, ñëåäîâàòåëüíî, ñòðåìèòñÿ ê 1 ïðè s ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè.Ëåììà äîêàçàíà.Äëÿ ëþáîé íåîòðèöàòåëüíîé è íåîãðàíè÷åííîâîçðàñòàþùåé ôóíêöèè ' (s) ó ïî÷òè âñåõ îòäåëèìûõ ïîñòîëáöàì ìàòðèö èç Bp;s äëèíà ìèíèìàëüíîãî äèàãíîñòè÷åñêîãîòåñòà íå áîëüøå, ÷åì 2 log s + ' (s).Ñëåäñòâèå.Ëèòåðàòóðà[1]Àëåêñååâ Â. Á.[2]Àëåêñååâ Â.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
