Теормин (2012) (1133351), страница 8
Текст из файла (страница 8)
Îòêóäà è ïîëó÷èì òðåáóåìóþ îöåíêó. ~n ) ∼ 2n , LK (J~n ) ∼ 2n+1 .Ñëåäñòâèå. LK (QnËåììà. Äëÿ n = 1, 2, . . . âûïîëíÿþòñÿ íåðàâåíñòâà Lπ (µn ) ≤ 2 · 2n + O( 2n ), LC (µn ) ≤n2 · 2n + O( 2n ), D(µn ) ≤ n + 6, ïðè÷åì ñóùåñòâóåò òàêàÿ ðåàëèçàöèÿ ÔÀË µn è áåñïîâòîðíàÿ ïîèíôîðìàöèîííûì ÁÏ ôîðìóëà Fn ñ ïîäíÿòûìè îòðèöàíèÿìè, ãëóáèíà êîòîðîé óäîâëåòâîðÿåònïîñëåäíåìó èç íèõ, àëüòåðíèðîâàíèå íå áîëüøå 3, à ñëîæíîñòü íå ïðåâîñõîäèò 7 · 2 .Ýòàïû äîêàçàòåëüñòâà.
Èñêîìàÿ π -ñõåìà Σn ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèñîåäèíåíèÿ ê(&)êàæäîìó èç âûõîäîâ Σnñîîòâåòñòâóþùåé åìó èíôîðìàöèîííîé ÁÏ è îòîæäåñòâëåíèÿ êîíöåâûõ âåðøèí âñåõ òàêèõ êîíòàêòîâ â âûõîäíóþ âåðøèíó Σn . ÑÔÝ Sn ïîëó÷àåòñÿ èç ôîðìóëû, ìîäåëèðóþùåé Σn â ðåçóëüòàòå ïðèâåäåíèÿ âåðøèí, ñîîòâåòñòâóþùèõ ÔÝ ¬.Ôîðìóëó F̃n ïîñòðîèì ìîäåëèðîâàíèåì ÊÑ Σn . Ôîðìóëó Fn ïîëó÷èì èç íåå îïòèìèçàöèåéïî ãëóáèíå. Ïîëó÷èì ôîðìóëó, îáëàäàþùóþ âñåìè íåîáõîäèìûìè ñâîéñòâàìè. Ëåììà.
Åñëè äëÿ ÔÀË f, f ∈ P2 (n), è äëÿ ëþáîãî σ, σ ∈ B , ÔÀË fσ (x1 , . . . , xn−1 , σ) 6≡ 0, 1,CCCòî L&,∨ ≥ min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.CÝòàïû äîêàçàòåëüñòâà. Ïóñòü Σ ìèíèìàëüíàÿ ïî ÷èñëó ÔÝ & è ∨ ÑÔÝ èç êëàññà U ,êîòîðàÿ ðåàëèçóåò ÔÀË f è êîòîðàÿ íå ñîäåðæèò öåïî÷åê èç äâóõ ïîñëåäîâàòåëüíî ñîåäèíåííûõ ÔÝ ¬. Ïóñòü êîíñòàíòà σ, σ ∈ B ðàâíà 0 òîãäà è òîëüêî òîãäà, êîãäà ÁÏ xn ïîäàåòñÿ â Σëèáî íà âõîä ÔÝ &, ëèáî íà âõîä ÔÝ ¬, âûõîä êîòîðîãî ïîñòóïàåò íà âõîä ÔÝ ∨. Òîãäà ïðèïîäñòàíîâêå σ âìåñòî xn è ÝÏ íà îñíîâå òîæäåñòâ ïîäñòàíîâêè êîíñòàíò áóäóò óäàëåíû ïîêðàéíåé ìåðå äâà ÔÝ òèïà & èëè ∨.
Ñëåäñòâèå. LC (µn ) ≥ 2n+1 + n − 2.Ñëåäñòâèå. LC (µn ) ∼ 2n+1 .Ñëåäñòâèå. n + 1 ≤ D(µn ) ≤ n + 6.Ýòàïû äîêàçàòåëüñòâà. Âûáåðåì ïàðàìåòðû:q2241Ïóñòü (Σ, È) ìîäåëü íåíàäåæíîé ñõåìûΣ ñ âîçìîæíûìè ñîñòîÿíèÿìè Σ = Σ1 , Σ2 , . . . , Σs ,f = f1 , f2 , . . . , fs ñîîòâåòñòâåííî îò ÁÏ X(n), îïðåäåëåííûånp,síà ìíîæåñòâå íàáîðîâ A = {α1 , .
. . , αp } ⊆ B . Ðàññìîòðèì ìàòðèöó M , M ∈ B, ãäåM hi, ji = fj (αi ), ñ÷èòàÿ, ÷òî i-é ñòðîêå (j -ìó ñòîëáöó) ýòîé òàáëèöû ñîîòâåòñòâóåò íàáîðαi (ñîîòâåòñòâåííî ôóíêöèÿ fj è ñîñòîÿíèå Σj ). Ìàòðèöà, ñîñòîÿùàÿ èç ðàçëè÷íûõ ñòîëáöîââ êîòîðûõ ðåàëèçóþòñÿ ÔÀËîòäåëèìîé ïî ñòîëáöàì(ñòðîê) íàçûâàåòñÿñòðîêàì)(ñîîòâåòñòâåííîìàòðèöåé.Êàæäîìó êëàññó íåîòëè÷èìûõ ñîñòîÿíèé ìîäåëè (Σ, È) ñîîòâåòñòâóåò ãðóïïà îäèíàêîâûõñòîëáöîâ ìàòðèöûMè ðàññìîòðèì îòäåëèìóþ ïî ñòîëáöàìðàçëè÷íûõ ñòîëáöîâ ìàòðèöûM.M̂ìàòðèöó, ñîñòîÿùóþ èç âñåõÏðè ýòîì áóäåì ñ÷èòàòü, ÷òî êàæäûé ñòîëáåö ìàòðèöûM̂ñâÿçàí ñ ñîîòâåòñòâóþùèì êëàññîì íåîòëè÷èìîñòè ñîñòîÿíèé ìîäåëè (Σ, È), è áóäåì íàçûâàòüM̂ òàáëèöåé êîíòðîëÿ äàííîé ìîäåëè.Ìíîæåñòâî N , ñîñòîÿùåå èç òåõ íåóïîðÿäî÷åííûõ ïàð ðàçëè÷íûõ ÷èñåë îòðåçêà [1, s], äëÿêîòîðûõ ïàðû ñîñòîÿíèé (ñòîëáöîâ ìàòðèöû M ) ñ ñîîòâåòñòâóþùèìè íîìåðàìè íåîáõîäèìîîòëè÷àòü äðóã îò äðóãà, ñðàâíèâàÿ çíà÷åíèÿ, ðàñïîëîæåííûå â òåõ èëè èíûõ ñòðîêàõ äàííîéïàðû ñòîëáöîâ.
 ÷àñòíîñòè, åñëèÿâëÿåòñÿäèàãíîñòèêà ñõåìû,Nñîñòîèò èç âñåõ ïàð óêàçàííîãî âèäà, òî öåëüþ êîíòðîëÿà åñëèN = {(1, 2), . . . , (1, t)},òî ïðîâåðêà èñïðàâíîñòèñõåìû.Ìíîæåñòâî ñòðîê ìàòðèöûMñ íîìåðàìè èçðèöû M îòíîñèòåëüíî ìíîæåñòâà N ,ïàðû(i, j)òàêæå åãîèçNñóùåñòâóåòt, t ∈ T ,òàêîå, ÷òîíàçûâàåòñÿ òåñòîì äëÿ ìàòòåñòîì äëÿ (M, N ), åñëè äëÿ ëþáîéT , T ⊆ [1, p],èëè, èíà÷å,M ht, ii =6 M ht, ji.Ìîùíîñòü òåñòà íàçûâàåòñÿäëèíîé.Òåñò, êîòîðûé ïåðåñòàåò áûòü òåñòîì ïðè óäàëåíèè ëþáîé ñâîåé ñòðîêè, íàçûâàåòñÿïèêîâûì,à òåñò, êîòîðûé èìååò ìèíèìàëüíóþ ìîùíîñòü, ìèíèìàëüíûì.òó- òîì ñëó÷àå,êîãäà öåëüþ êîíòðîëÿ ÿâëÿåòñÿ äèàãíîñòèêà ñõåìû (ïðîâåðêà èñïðàâíîñòè ñõåìû), òåñò íàçûâàåòñÿäèàãíîñòè÷åñêèìêîíòðîëÿ N ,ïðîâåðÿþùèì).òåñò äëÿ ìîäåëè (Σ, È) îòíîñèòåëüíî öåëèòåñò äëÿ (Σ, È, N ), åñëè ñîîòâåòñòâóþùèå íàáîðàì èç τ ñòðîêè(ñîîòâåòñòâåííîτ, τ ⊆ A,Ìíîæåñòâî íàáîðîâèëè, èíà÷å,îáðàçóåòN ).i ∈ [1, p], ìàòðèöû M ÁÏ yi , à êàæäîìó íàáîðó β, β ∈ B p , çíà÷åíèéýòèõ ïåðåìåííûõ y = (y1 , .
. . , yp ) ìíîæåñòâî ñòðîê ìàòðèöû M ñ íîìåðàìè èç ìíîæåñòâàI = I(β) ⊆ [1, p], ãäå i ∈ I(β) òîãäà è òîëüêî òîãäà, êîãäà βhii = 1. Ðàññìîòðèì ÔÀË F (y),äëÿ êîòîðîé F (β) = 1 òîãäà è òîëüêî òîãäà, êîãäà ñèñòåìà ñòðîê ìàòðèöû M ñ íîìåðàìè èçI(β) îáðàçóåò òåñò äëÿ (M , N ), è áóäåì íàçûâàòü ýòó ÔÀË ôóíêöèåé òåñòà äëÿ (M , N ).p,sËåììà. Ôóíêöèÿ òåñòà f (y1 , . . . , yp ) äëÿ îòäåëèìîé ïî ñòîëáöàì ìàòðèöûè M , M ∈ B ,ìàòðèöûMîáðàçóþò òåñò äëÿ (M ,Ñîïîñòàâèì i-é ñòðîêå,öåëè êîíòðîëÿNìîæåò áûòü çàäàíà ñ ïîìîùüþ ÊÍÔf (y1 , .
. . , yp ) =V(i,j)∈NÝòàïû äîêàçàòåëüñòâà. ÔÀË òåñòàM èãëàâû. ïîêðûòèÿ äëÿ ìàòðèöûïàðàãðàôà ïåðâîéFäëÿ ïàðû(M, N )W1≤t≤pM ht,ii6=M ht,jiyt ÿâëÿåòñÿ îäíîâðåìåííî ÔÀËîáðàòíî. Òàê ÷òî ëåììà âåðíà ñîãëàñíî ïåðâîé ëåììå øåñòîãîÑëåäñòâèå.Êàæäàÿ ýëåìåíòàðíàÿ êîíúþíêöèÿ âèäà yt1 · · · ytr ñîêðàùåííîé ÄÍÔ ôóíêf (y1 , . . . , yp ), ïîëó÷àþùàÿñÿ èç ÊÍÔ ëåììû â ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿïîäîáíûõ, ñîîòâåòñòâóåò òóïèêîâîìó òåñòó, ñâÿçàííîìó ñ ìíîæåñòâîì T = {t1 , . .
. , tr } è îáöèèðàòíî.Ëåììà.Äëèíà ëþáîãî òóïèêîâîãî äèàãíîñòè÷åñêîãî òåñòà äëÿ îòäåëèìîé ïî ñòîëáöàìB p,sdlog se äî (s − 1).t ñòðîê ìàòðèöû M îáðàçóþò åå òóïèc - ìàòðèöà, ñîñòîÿùàÿ èç ïåðâûõ t ñòðîê ìàòðèöû M . ×èñëîêîâûé äèàãíîñòè÷åñêèé òåñò. Mttðàçëè÷íûõ áóëåâûõ ñòîëáöîâ âûñîòû t ðàâíî 2 . Ïîñêîëüêó âñå s ñòîëáöîâ ðàçëè÷íû, s ≤ 2 ,òî åñòü t ≥ dlog se.ìàòðèöû èç ìíîæåñòâàçàêëþ÷åíà â ïðåäåëàõ îòÝòàïû äîêàçàòåëüñòâà. ÏóñòüM ∈ B p,sè ïåðâûå23∀q, q ∈ [1, t]îïðåäåëèì îòíîøåíèå ýêâèâàëåíòíîñòè:m0 ∼ m00qòîãäà è òîëüêî òîãäà, êîãäàc ñîâïàäàþò â ñòðîêàõ ñ íîìåðàìè èç [1, q].
×èñëî êëàññîâ ýêâèâàm0 , m00 ìàòðèöû Mëåíòíîñòè θ(q). Ïîñêîëüêó òåñò òóïèêîâûé, θ(q) < θ(q +1). Ïîñêîëüêó òåñò äèàãíîñòè÷åñêèé,θ(t) = s. Ïîëó÷àåì 1 = θ(0) < θ(1) < · · · < θ(t) = s, òî åñòü t ≤ (s − 1). Ëåììà. Ïóñòü ϕ(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),s : 2t (2t − 1) . . .
(2t −(s−1)1s + 1) · 2= 2 (1 − 2t ) . . . (1 − 2t ). Èõ äîëÿ ñðåäè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö(s−1)s21−2ϕ(s)p,sps, ÷òî ñòðåìèòñÿ ê 1èç B(2 ) íå ìåíüøå, ÷åì (1 − t ) . . . (1 −22t ) ≥ 1 − 2t ≥ 1 − 2ïðè s ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè. Ýòàïû äîêàçàòåëüñòâà. Îöåíèì êîëè÷åñòâî çàäàííûõ ìàòðèö(p−t)spsÑëåäñòâèå.Äëÿ ëþáîé íåîòðèöàòåëüíîé è íåîãðàíè÷åííî âîçðàñòàþùåé ôóíêöèèó ïî÷òè âñåõ îòäåëèìûõ ïî ñòîëáöàì ìàòðèö èçòåñòà íå áîëüøå, ÷åìB p,sϕ(s)äëèíà ìèíèìàëüíîãî äèàãíîñòè÷åñêîãî2 log s + ϕ(s).2Êîíòàêòû ðàññìàòðèâàåìûõ ÊÑ ìîãóò âûõîäèòü èç ñòðîÿ, ïåðåõîäÿ â îäíî èç äâóõ âîçìîæíûõ íåèñïðàâíûõ ñîñòîÿíèé:çàìûêàíèÿ,ΣÁóäåì ãîâîðèòü, ÷òî ÊÑêîððåêòèðóåòñîñòîÿíèå îáðûâà,êîãäà êîíòàêò íå ïðîâîäèò, èñîñòîÿíèåêîãäà êîíòàêò ïðîâîäèò ïðè ëþáûõ çíà÷åíèÿõ óïðàâëÿþùåé èì ÁÏ.pîáðûâîâ èáûòü ïîëó÷åíà èç ÊÑΣq(p, q) - ñàìîêîððåêòèðóþùåéñÿ ÊÑ èëè,p ≥ 0 è q ≥ 0, åñëè ëþáàÿ ÊÑ Σ0 , êîòîðàÿîáðûâà íå áîëåå ÷åì p, è çàìûêàíèÿ íå áîëåå,ÿâëÿåòñÿçàìûêàíèé, ãäåâ ðåçóëüòàòåΣ.Ëåììà.
Äëÿ ëþáûõ p ≥ 0, q ≥ 0 è ëþáîé ÊÑ ΣK0U(p,q), äëÿ êîòîðîé L(Σ ) ≤ (p + 1)(q + 1)L(Σ).èíà÷å,ìîæåòq,÷åìêîíòàêòîâ, ýêâèâàëåíòíàñóùåñòâóåò ýêâèâàëåíòíàÿ åé ÊÑΣ0 , Σ0 ∈Ýòàïû äîêàçàòåëüñòâà. Ñõåìà ñòðîèòñÿ ïóòåì ïàðàëëåëüíîãî è (èëè) ïîñëåäîâàòåëüíîãîäóáëèðîâàíèÿ êîíòàêòîâ.Áóäåì íàçûâàòüîäíîðîäíîéëþáóþ ñâÿçíóþ ÊÑ ñ íåðàçäåëåííûìè ïîëþñàìè, ñîñòîÿ-ùóþ èç êîíòàêòîâ îäíîãî è òîãî æå òèïà. Ïðåäñòàâëåíèå ÊÑðîäíûõ ïîäñõåì áåç îáùèõ êîíòàêòîâ áóäåì íàçûâàòüΣâ âèäå îáúåäèíåíèÿ åå îäíî-îäíîðîäíûì ðàçáèåíèåììèíèìàëüíîå ÷èñëî ïîäñõåì â òàêèõ ðàçáèåíèÿõ áóäåì îáîçíà÷àòü ÷åðåçËåììà.ÄëÿëþáîéÊÑñàìîêîððåêòèðóþùèåñÿ ÊÑΣ0èΣΣ00ñóùåñòâóþòýêâèâàëåíòíûåñîîòâåòñòâåííî òàêèå, ÷òîåéÊÑΣ,àζ(Σ).(1,0)-è(0,1)-L(Σ0 ) ≤ L(Σ) + ζ(Σ), L(Σ00 ) ≤L(Σ) + ζ(Σ).Ýòàïû äîêàçàòåëüñòâà. Ñòðîèòñÿ çàìåíîé îäíîðîäíûõ ìåòåëîê íà öèêëû (çâåçäû).Ââåäåì ñîîòâåòñòâóþùóþ ôóíêöèþ ØåííîíàKL (f ) ≤KLK(p,q) (f ); L (n)≤f ∈P2 (n)Î÷åâèäíî, ÷òîLK(p,q) (n)Òåîðåìà Äëÿ n = 1, 2, .
. .LK(0,1) (n) ∼KLK(p,q) (n) = max L(p,q) (f ).èìåþò ìåñòî ñëåäóþùèå àñèìïòîòè÷åñêèå ðàâåíñòâà:LK(1,0) (n) ∼n2nÝòàïû äîêàçàòåëüñòâà. Íèæíèå îöåíêè ñëåäóþò èç ïåðâîé òåîðåìû âòîðîãî ïàðàãðàôàòðåòüåé ãëàâû. Âåðõíèå îöåíêè ñëåäóþò èç ïåðâîé òåîðåìû øåñòîãî ïàðàãðàôà òðåòüåé ãëàâûè çàìå÷àíèÿ ê íåé.nζ(Σf ) = o( n2√n ).Òàê ÷òî ñóùåñòâóþò ÊÑ, êîòîðûå ðåàëèçóþò ÔÀË2nñëîæíîñòüþ, àñèìïòîòè÷åñêè íå ïðåâîñõîäÿùåén . Ëåììà.
Äëÿ n = 1, 2, . . . èìåþò ìåñòî ðàâåíñòâà LK(0,1) (ln )ñî¯= LK(0,1) (ln ) = 4n.σ, σ ∈ B , èç âõîäà (âûõîäà) ýòîé ñõåìû, ïðîâåäåìxσn (xσ1 ) â âåðøèíó, ñîåäèíåííóþ êîíòàêòîì âèäà xσ̄n (xσ̄q ) ñ åå âûõîäîì (âõîäîì).Ýòàïû äîêàçàòåëüñòâà. Äëÿ êàæäîãîêîíòàêò âèäàf24.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
