OK-metodichka-2010-part4 (1132795), страница 2
Текст из файла (страница 2)
Âñå ââåäåííûå âûøå ïîíÿòèÿ, êîòîðûå êàñàþòñÿ òåñòîâ äëÿ òàáëèö, áåç èçìåíåíèé ïåðåíîñÿòñÿ íà ñëó÷àé òåñòîâ äëÿ íåíàäåæíûõ ñõåì.Äëÿ îïèñàíèÿ òåñòîâ ìîæíî ââåñòè ôóíêöèþ, àíàëîãè÷íóþ ôóíêöèè ïîêðûòèÿ èç 6 ãëàâû 1. Ïóñòü M, M ∈ B p,s , îòäåëèìàÿ ïî ñòîëáöàì ìàòðèöà, à N ñâÿçàííàÿ ñ íåéöåëü êîíòðîëÿ.
Ñîïîñòàâèì i-é ñòðîêå, i ∈ [1, p], ìàòðèöûM ÁÏ yi , à êàæäîìó íàáîðó β, β ∈ B p , çíà÷åíèé ýòèõ ïåðåìåííûõ y = (y1 , . . . , yp ) ìíîæåñòâî ñòðîê ìàòðèöû M ñíîìåðàìè èç ìíîæåñòâà I = I (β) ⊆ [1, p], ãäå i ∈ I (β) òîãäà è òîëüêî òîãäà, êîãäà β hii = 1. Ðàññìîòðèì ÔÀË F (y),1. Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö9äëÿ êîòîðîé F (β) = 1 òîãäà è òîëüêî òîãäà, êîãäà ñèñòåìà ñòðîê ìàòðèöû M ñ íîìåðàìè èç I (β) îáðàçóåò òåñò äëÿ(M, N), è áóäåì íàçûâàòü ýòó ÔÀË ôóíêöèåé òåñòà äëÿ(M, N).
Ñîïîñòàâèì ïàðå (M, N) ìàòðèöó M èç ìíîæåñòâàB p,S , S = |N|, ñòîëáöû êîòîðîé ïðîíóìåðîâàíû ïàðàìè èçN, à åå ñòîëáåö ñ íîìåðîì (i, j) ∈ N ïîëó÷àåòñÿ â ðåçóëüòàòåïîðàçðÿäíîãî ñëîæåíèÿ ïî ìîäóëþ 2 ñòîëáöîâ ñ íîìåðàìè i èj ìàòðèöû M . Çàìåòèì, ÷òî ñòðîêè ìàòðèöû M ñ íîìåðàìèèç ìíîæåñòâà T, T ⊆ [1, p], îáðàçóþò òåñò (òóïèêîâûé òåñò,ìèíèìàëüíûé òåñò) äëÿ ïàðû (M, N) òîãäà è òîëüêî òîãäà,êîãäà ñòðîêè ìàòðèöû M ñ íîìåðàìè èç T îáðàçóþò ïîêðûòèå (òóïèêîâîå ïîêðûòèå, ïîêðûòèå ìèíèìàëüíîé äëèíû)ìàòðèöû M. Îòñþäà âûòåêàåò, â ÷àñòíîñòè, ÷òî ÔÀË òåñòàF äëÿ ïàðû (M, N) ÿâëÿåòñÿ îäíîâðåìåííî ÔÀË ïîêðûòèÿäëÿ ìàòðèöû M è îáðàòíî, à çíà÷èò äëÿ íåå, â ñèëó ëåììû6.1 ãëàâû 1, ñïðàâåäëèâî ñëåäóþùåå óòâåðæäåíèå.Ëåììà 1.1.
Ôóíêöèÿ òåñòà f (y1 , . . . , yp ) äëÿ îòäåëèìîéïî ñòîëáöàì ìàòðèöû M, M ∈ B p,s , è öåëè êîíòðîëÿ Nìîæåò áûòü çàäàíà ñ ïîìîùüþ ÊÍÔ¶_^ µyt ,(1.1)f (y1 , . . . , yp ) =(i,j)∈N16t6pM ht,ii6=M ht,jiÑëåäñòâèå. Êàæäàÿ ýëåìåíòàðíàÿ êîíúþíêöèÿ âèäà yt1 · · · ytrñîêðàùåííîé ÄÍÔ ôóíêöèè f (y1 , . . . , yp ), ïîëó÷àþùàÿñÿ èçÊÍÔ (1.1) â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ, ñîîòâåòñòâóåò òóïèêîâîìó òåñòó, ñâÿçàííîìóñ ìíîæåñòâîì T = {t1 , . . . , tr } è îáðàòíî.Íà äàííîé ëåììå îñíîâàí ñëåäóþùèé àëãîðèòì ïîñòðîåíèÿ âñåõ òóïèêîâûõ òåñòîâ äëÿ ìàòðèöû M îòíîñèòåëüíîöåëè êîíòðîëÿ N:1. âûïèñûâàåì äëÿ ôóíêöèè òåñòà ÊÍÔ âèäà (1.1);10 Ãëàâà 4.
Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõ ñèñòåì2. ðàñêðûâàÿ â íåé ñêîáêè è ïðèâîäÿ ïîäîáíûå, ïîëó÷àåìñîêðàùåííóþ ÄÍÔ ôóíêöèè òåñòà;3. ñîïîñòàâëÿåì êàæäîé ýëåìåíòàðíîé êîíúþíêöèè ýòîéñîêðàùåííîé ÄÍÔ òóïèêîâûé òåñò.Òàê, íàïðèìåð, äëÿ ïîñòðîåíèÿ âñåõ òóïèêîâûõ äèàãíîñòè÷åñêèõ òåñòîâ ìàòðèöû M âèäà0 1 00 1 1M =1 0 11 1 0âûïèøåì ñîîòâåòñòâóþùóþ åé ÊÍÔ (1.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 ÿâëÿþòñÿ ìíîæåñòâà åå ñòðîê ñ íîìåðàìè{1, 2} , {1, 4} , {2, 3} , {2, 4} , {3, 4} .Äëÿ óïðîùåíèÿ ïðåîáðàçîâàíèé, ñâÿçàííûõ ñ ïðèìåíåíèåì îïèñàííîãî àëãîðèòìà, âìåñòî èñõîäíîé ìàòðèöû Mìîæíî ðàññìàòðèâàòü îòäåëèìóþ ïî ñòðîêàì ìàòðèöó M̌ ,ïîëó÷àþùóþñÿ èç M óäàëåíèåì ïîâòîðíûõ âõîæäåíèé îäèíàêîâûõ ñòðîê.
Ïðè ýòîì, î÷åâèäíî, ëþáîé òóïèêîâûé òåñòìàòðèöû M ïîëó÷àåòñÿ èç òóïèêîâîãî òåñòà òîé æå äëèíûìàòðèöû M̌ â ðåçóëüòàòå çàìåíû êàæäîé åãî ñòðîêè ðàâíîéåé ñòðîêîé ìàòðèöû M è îáðàòíî.Ðàññìîòðèì, äàëåå, íåêîòîðûå îöåíêè äëèíû äèàãíîñòè÷åñêèõ òåñòîâ äëÿ ìàòðèö ñ çàäàííûì ÷èñëîì ñòîëáöîâ.1. Çàäà÷à êîíòðîëÿ ñõåì è òåñòû äëÿ òàáëèö11Ëåììà 1.2. Äëèíà ëþáîãî òóïèêîâîãî äèàãíîñòè÷åñêîãîòåñòà äëÿ îòäåëèìîé ïî ñòîëáöàì ìàòðèöû èç ìíîæåñòâà B p,s çàêëþ÷åíà â ïðåäåëàõ îò dlog se äî (s − 1).Äîêàçàòåëüñòâî.
Ïóñòü M ∈ B p,s è ïóñòü, äëÿ îïðåäåëåííîñòè, ïåðâûå t ñòðîê ìàòðèöû M îáðàçóþò åå òóïèêîâûéäèàãíîñòè÷åñêèé òåñò. Î÷åâèäíî, ÷òî â ýòîì ñëó÷àå âñåc, ñîñòîÿùåé èç ïåðâûõ t ñòðîê ìàòðèöûñòîëáöû ìàòðèöû MM , ðàçëè÷íû è, ñëåäîâàòåëüíî, s 6 2t , òî åñòü t > dlog se,ïîñêîëüêó ÷èñëî ðàçëè÷íûõ áóëåâûõ ñòîëáöîâ âûñîòû t ðàâíî 2t . Òðåáóåìàÿ íèæíÿÿ îöåíêà äëèíû äèàãíîñòè÷åñêîãîòåñòà óñòàíîâëåíà.Äîêàæåì òåïåðü, ÷òî t 6 (s − 1). Äëÿ ýòîãî íà ìíîæåc ïðè ëþáîì q, q ∈ [1, t], îïðåäåñòâå ñòîëáöîâ ìàòðèöû Mëèì îòíîøåíèå ýêâèâàëåíòíîñòè ∼ òàê, ÷òî m0 ∼ m00 òîãäàq0m èqc ñîâïàè òîëüêî òîãäà, êîãäà ñòîëáöûìàòðèöû Mäàþò â ñòðîêàõ ñ íîìåðàìè èç îòðåçêà [1, q]. Áóäåì ñ÷èòàòü,ïî îïðåäåëåíèþ, ÷òî ∼ òðèâèàëüíîå îòíîøåíèå ñ îäíèì0êëàññîì ýêâèâàëåíòíîñòè, à ÷èñëî êëàññîâ ýêâèâàëåíòíîñòèïî îòíîøåíèþ ∼, ãäå q ∈ [1, t], áóäåì îáîçíà÷àòü ÷åðåç θ (q).m00qÈç îáùèõ ñâîéñòâ îòíîøåíèé ýêâèâàëåíòíîñòè (ñì.
??)âûòåêàåò, ÷òî ïðè ëþáîì q, q ∈ [1, t), êàæäûé êëàññ ýêâèâàëåíòíîñòè ïî îòíîøåíèþ ∼ ëèáî ÿâëÿåòñÿ êëàññîì ýêâèâàqëåíòíîñòè ïî îòíîøåíèþ ∼ , ëèáî ïðåäñòàâëÿåò ñîáîé îáúq+1åäèíåíèå äâóõ òàêèõ êëàññîâ è, ñëåäîâàòåëüíî, θ (q) 6 θ (q + 1). ñèëó òóïèêîâîñòè òåñòà ïîëó÷åííîå íåðàâåíñòâî ÿâëÿåòñÿñòðîãèì, òàê êàê ðàâåíñòâî θ (q) = θ (q + 1) âîçìîæíî òîãäàè òîëüêî òîãäà, êîãäà êàæäûé êëàññ ýêâèâàëåíòíîñòè îòíîøåíèÿ ∼ ÿâëÿåòñÿ êëàññîì ýêâèâàëåíòíîñòè îòíîøåíèÿ ∼qq+1è îáðàòíî, òî åñòü ñòðîêà ñ íîìåðîì (q + 1) ÿâëÿåòñÿ ¾ëèøíåé¿ â ðàññìàòðèâàåìîì òåñòå.Èç äèàãíîñòè÷íîñòè òåñòà âûòåêàåò, ÷òî θ (t) = s, è, òà-12 Ãëàâà 4.
Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõ ñèñòåìêèì îáðàçîì, âûïîëíÿþòñÿ ñîîòíîøåíèÿ1 = θ (0) < θ (1) < · · · < θ (t) = s,èç êîòîðûõ ñëåäóåò, ÷òî t 6 (s − 1).Ëåììà äîêàçàíà.Çàìå÷àíèå. Óêàçàííûå â ëåììå ãðàíèöû äîñòèãàþòñÿ: íèæíÿÿ íà ëþáîé îòäåëèìîé ïî ñòîëáöàì ìàòðèöå èç B p,s , ãäåp = dlog se, à âåðõíÿÿ íà ìàòðèöå èç B s−1,s , âñå ñòîëáöûêîòîðîé ðàçëè÷íû è ñîäåðæàò íå áîëåå îäíîé åäèíèöû (îáåìàòðèöû èìåþò åäèíñòâåííûé äèàãíîñòè÷åñêèé òåñò, ñîñòîÿùèé èç âñåõ ñòðîê).Ñëåäóþùåå óòâåðæäåíèå õàðàêòåðèçóåò ¾òèïè÷íîå¿ çíà÷åíèå äëèíû äèàãíîñòè÷åñêîãî òåñòà, òî åñòü äëèíó ìèíèìàëüíîãî äèàãíîñòè÷åñêîãî òåñòà ó ¾ïî÷òè âñåõ¿ òàáëèö êîíòðîëÿ.Ëåììà 1.3.
Ïóñòü ϕ (s) , t (s) è p (s) öåëî÷èñëåííûåíåîòðèöàòåëüíûå ôóíêöèè íàòóðàëüíîãî àðãóìåíòà s, äëÿêîòîðûõt (s) = d2 log se + ϕ (s) ,p (s) > t (s) ,ϕ (s) −−−→ ∞.s→∞Òîãäà ó ïî÷òè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçB p(s),s ïåðâûå t (s) ñòðîê îáðàçóþò äèàãíîñòè÷åñêèé òåñò.Äîêàçàòåëüñòâî. Çàìåòèì, ÷òî âñå ìàòðèöû èç B p,s , ãäåp = p (s), ó êîòîðûõ ïåðâûå t = t (s) ñòðîê îáðàçóþò äèàãíîñòè÷åñêèé òåñò, îòäåëèìû ïî ñòîëáöàì. Ëåãêî âèäåòü òàêæå,÷òî ÷èñëî òàêèõ ìàòðèö ðàâíî¡¢ ¡¢2t 2t − 1 · · · 2t − s + 1 · 2(p−t)s =µ¶ µ¶1(s − 1)ps=21 − t ··· 1 −,22t2.
Ñàìîêîððåêòèðóþùèåñÿ ÊÑ13à èõ äîëÿ ñðåäè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èç B p,síå ìåíüøå, ÷å쵶 µ¶1(s − 1)s21 − t ··· 1 −>1−> 1 − 2−2ϕ(s) ,22t2tè, ñëåäîâàòåëüíî, ñòðåìèòñÿ ê 1 ïðè s ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè.Ëåììà äîêàçàíà.Ñëåäñòâèå. Äëÿ ëþáîé íåîòðèöàòåëüíîé è íåîãðàíè÷åííîâîçðàñòàþùåé ôóíêöèè ϕ (s) ó ïî÷òè âñåõ îòäåëèìûõ ïîñòîëáöàì ìàòðèö èç B p,s äëèíà ìèíèìàëüíîãî äèàãíîñòè÷åñêîãî òåñòà íå áîëüøå, ÷åì 2 log s + ϕ (s).2 Ñàìîêîððåêòèðóþùèåñÿ êîíòàêòíûå ñõåìûè ìåòîäû èõ ïîñòîðîåíèÿ. Àñèìïòîòè÷åñêèíàèëó÷øèé ìåòîä ñèíòåçà êîíòàêòíûõ ñõåì,êîððåêòèðóþùèõ îäèí îáðûâ (îäíî çàìûêàíèå)Ðàññìîòðèì âîïðîñ ïîâûøåíèÿ íàäåæíîñòè ñõåì íà ïðèìåðåò.
í. ñàìîêîððåêòèðóþùèõñÿ ÊÑ. Áóäåì ñ÷èòàòü, ÷òî êîíòàêòû ðàññìàòðèâàåìûõ ÊÑ ìîãóò âûõîäèòü èç ñòðîÿ, ïåðåõîäÿ â îäíî èç äâóõ âîçìîæíûõ íåèñïðàâíûõ ñîñòîÿíèé:ñîñòîÿíèå îáðûâà, êîãäà êîíòàêò íå ïðîâîäèò, è ñîñòîÿíèåçàìûêàíèÿ, êîãäà êîíòàêò ïðîâîäèò ïðè ëþáûõ çíà÷åíèÿõóïðàâëÿþùåé èì ÁÏ.Áóäåì ãîâîðèòü, ÷òî ÊÑ Σ ÿâëÿåòñÿ (p, q) - ñàìîêîððåêòèðóþùåéñÿ ÊÑ èëè, èíà÷å, êîððåêòèðóåò p îáðûâîâ è qçàìûêàíèé, ãäå p > 0 è q > 0, åñëè ëþáàÿ ÊÑ Σ0 , êîòîðàÿìîæåò áûòü ïîëó÷åíà èç ÊÑ Σ â ðåçóëüòàòå îáðûâà íå áîëåå÷åì p, è çàìûêàíèÿ íå áîëåå, ÷åì q , êîíòàêòîâ, ýêâèâàëåíòíàΣ. Îáîçíà÷èì ÷åðåç UK(p,q) ìíîæåñòâî âñåõ (p, q) - ñàìîêîðKðåêòèðóþùõñÿ ÊÑ è çàìåòèì, ÷òî UK(0,0) = U .
Çàìåòèì,14 Ãëàâà 4. Íàäåæíîñòü è êîíòðîëü óïðàâëÿþùèõ ñèñòåìòàêæå, ÷òî äëÿ ëþáîé ÊÑ Σ ÊÑ Σ(p,q) , ïîëó÷àþùàÿñÿ èç Σâ ðåçóëüòàòå çàìåíû ëþáîãî åå êîíòàêòà âèäà xσi π -ñõåìîé,ñîñòîÿùåé èç (q + 1) ïîñëåäîâàòåëüíî ñîåäèíåííîãî ïó÷êà,êàæäûé èç êîòîðûõ, âêëþ÷àåò â ñåáÿ (p + 1) ïàðàëëåëüíîñîåäèíåííûé êîíòàêò âèäà xσi , ïðèíàäëåæèò UK(p,q) .Ïîñòðîåíèå ÊÑ Σ(p,q) , îñíîâàííîå íà ïîñëåäîâàòåëüíîì è(èëè) ïàðàëëåëüíîì äóáëèðîâàíèè êîíòàêòîâ ÊÑ Σ, ÿâëÿåòñÿ ïðîñòåéøèì ñïîñîáîì ïîëó÷åíèÿ ñàìîêîððåêòèðóþùèõñÿ ÊÑ, ýêâèâàëåíòíûõ çàäàííîé ÊÑ.
Îí äàåò ñëåäóþùóþòðèâèàëüíóþ âåðõíóþ îöåíêó ñëîæíîñòè ñàìîêîððåêòèðóþùèõñÿ ÊÑ, ýêâèâàëåíòíûõ äàííîé.Ëåììà 2.1. Äëÿ ëþáûõ p > 0, q > 0 è ëþáîé ÊÑ Σ ñóùåñòâóåò ýêâèâàëåíòíàÿ åé ÊÑ Σ0 , Σ0 ∈ UK(p,q) , äëÿ êîòîðîéL(Σ0 ) 6 (p + 1)(q + 1)L(Σ).Ðàññìîòðèì, äàëåå, íåòðèâèëüíûé ñïîñîá ïîñòðîåíèÿ (1, 0)èëè (0, 1)-ñàìîêîððåêòèðóþùèõñÿ ÊÑ, ñâÿçàííûé ñ êîððåêöèåé îäíîãî îáðûâà èëè îäíîãî çàìûêàíèÿ â ò.
í. îäíîðîäíûõ ïîäñõåìàõ. Áóäåì íàçûâàòü îäíîðîäíîé ëþáóþ ñâÿçíóþÊÑ ñ íåðàçäåëåííûìè ïîëþñàìè, ñîñòîÿùóþ èç êîíòàêòîâîäíîãî è òîãî æå òèïà. Çàìåòèì, ÷òî â ëþáîé òàêîé ÊÑ, ñîñòîÿùåé èç êîíòàêòîâ âèäà xσi , ÔÀË ïðîâîäèìîñòè ìåæäóëþáûìè äâóìÿ ïîëþñàìè ðàâíà xσi . Îòñþäà ñëåäóåò, â ÷àñòíîñòè, ÷òî ëþáûå äâå îäíîðîäíûå ÊÑ, ñîñòîÿùèå èç êîíòàêòîâ îäíîãî òèïà è èìåþùèå îäèí è òîò æå íàáîð ïîëþñîâ,ýêâèâàëåíòíû.Îáîçíà÷èì ÷åðåç Cm (xσi ) (Zm (xσi )) m-ïîëþñíóþ îäíîðîäíóþ ÊÑ, êîòîðàÿ ñîñòîèò èç m êîíòàêòîâ âèäà xσi è ïðåäñòàâëÿåò ñîáîé öèêë, ïðîõîäÿùèé ÷åðåç âñå ïîëþñà (ñîîòâåòñâåííî çâåçäó èç êîíòàêòîâ, ñîåäèíÿþùèõ åå öåíòð ñ ïîσKëþñàìè). Î÷åâèäíî, ÷òî Cm (xσi ) ∈ UK(1,0) è Zm (xi ) ∈ U(0,1) .Ïðåäñòàâëåíèå ÊÑ Σ â âèäå îáúåäèíåíèÿ åå îäíîðîäíûõïîäñõåì áåç îáùèõ êîíòàêòîâ áóäåì íàçûâàòü îäíîðîäíûì2.
Ñàìîêîððåêòèðóþùèåñÿ ÊÑ15ðàçáèåíèåì ÊÑ Σ, à ìèíèìàëüíîå ÷èñëî ïîäñõåì â òàêèõðàçáèåíèÿõ áóäåì îáîçíà÷àòü ÷åðåç ζ(Σ). Åñëè Σ1 , ..Σζ - îäíîðîäíîå ðàçáèåíèå ÊÑ Σ, à ýêâèâàëåíòíàÿ åé ÊÑ Σ0 (ÊÑΣ00 ) ïîëó÷àåòñÿ èç ÊÑ Σ â ðåçóëüòàòå çàìåíû êàæäîé ïîäñõåìû Σi ýêâèâàëåíòíîé åé ÊÑ Σ0i âèäà Cm (ñîîòâåòñòâåííî00KÊÑ Σ00i âèäà Zm ), òî Σ0 ∈ UK(1,0) (ñîîòâåòñòâåííî Σ ∈ U(0,1) ).Çàìåòèì, ÷òî ïðè ýòîìL(Σ0i ) 6 L(Σi ) + 1, L(Σ00i ) 6 L(Σi ) + 1è, ñëåäîâàòåëüíî,L(Σ0 ) 6 L(Σ) + ζ, L(Σ00 ) 6 L(Σ) + ζÓêàçàííûé íåòðèâèàëüíûé ñïîñîá ïîñòðîåíèÿ (0, 1)- èëè(1, 0)-ñàìîêîððåêòèðóþùèõñÿ ÊÑ, ýêâèâàëåíòíûõ çàäàííîé,äàåò ñëåäóþùóþ îöåíêó èõ ñëîæíîñòè.Ëåììà 2.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
