Теормин (2012) (1133351), страница 2
Текст из файла (страница 2)
Ïó÷îê íåðåãóëÿðíîé òî÷êèβ ∈ Nf \NkαñòðîãîNKj ,β , èç ÷åãî ñëåäóåò íåðàâåíñòâî ïó÷êîâ), ãäå k ãðàíü, ñîäåðæàùàÿ α. Çíà÷èò,Nk óäàëèòü íåëüçÿ. Äëÿ êàæäîé ìàêñèìàëüíîé ãðàíè N ÔÀË f (x1 , . . . , xn ) ïîëîæèì S0 (N , f ) = {N }, à çàòåìèíäóêöèåé ïî r, r = 1, 2, . . . îïðåäåëèì ìíîæåñòâî Sr (N , f ) êàê ìíîæåñòâî âñåõ òåõ ìàêñè-ìåíüøå ïó÷êà ëþáîé òî÷êè(èç ýòîãî ñëåäóåò, ÷òî íàøëàñü òàêàÿ ãðàíüêîòîðàÿ ïîêðûëà4ìàëüíûõ ãðàíåé ÔÀËSr−1 (N , f ). Sr (N , f )f,êîòîðûå èìåþò íåïóñòîå ïåðåñå÷åíèå õîòÿ áû ñ îäíîé ãðàíüþ èçîêðåñòíîñòü ïîðÿäêà rãðàíèNÔÀËf.5f ëèíåéíî çàâèñèò îò ÁÏ xi (ÁÏ xi ÿâëÿåòñÿ ëèíåéíîé ÁÏ ÔÀË f ), åñëè f (α) 6=xi íàáîðîâ α è β êóáà B n .nÔÀË f íàçûâàåòñÿ ìîíîòîííîé, åñëè f (α) ≤ f (β) äëÿ ëþáûõ íàáîðîâ α è β êóáà Bòàêèõ, ÷òî α ≤ β .ÔÀË f ìîíîòîííî çàâèñèò îò ÁÏ xi (ÁÏ xi ÿâëÿåòñÿ ìîíîòîííîé ÁÏ ÔÀË f ), åñëèníåðàâåíñòâî f (α) ≤ f (β) âûïîëíÿåòñÿ äëÿ ëþáûõ ñîñåäíèõ ïî ÁÏ xi íàáîðîâ α è β êóáà Bòàêèõ, ÷òî α ≤ β .Óòâåðæäåíèå.
Åñëè ÔÀË f ìîíîòîííî çàâèñèò îò ÁÏ xi , òî íè îäíà èç åå ïðîñòûõèìïëèêàíò íå ìîæåò ñîäåðæàòü áóêâó x̄i .Ýòàïû äîêàçàòåëüñòâà. Ïóñòü åñòü èìïëèêàíòà x̄i K . Òîãäà íà íàáîðå, êîòîðûé îáðàùàåòK â 1, è xi = 0, èìïëèêàíòà ðàâíà 1, à íà íàáîðå, ãäå xi = 1 (áîëüøåì, ÷åì ïðåäûäóùèé)ÔÀËf (β)äëÿ ëþáûõ ñîñåäíèõ ïî ÁÏèìïëèêàíòà ðàâíà 0, ÷òî ïðîòèâîðå÷èò ìîíîòîííîñòè.f êîíúþíêòèâíî (äèçúþíêòèâíî) çàâèñèò îò ÁÏ xi , êîãäà f = xi · g (ñîîòâåòf = xi ∨ g ), ãäå ÔÀË g ïîëó÷àåòñÿ èç f ïîäñòàíîâêîé êîíñòàíòû 1 (ñîîòâåòñòâåííî 0)âìåñòî ÁÏ xi .ÔÀË f èíìîíîòîííî (èíêîíúþíêòèâíî, èíäèçúþíêòèâíî) çàâèñèò îò ÁÏ xi , åñëèÔÀË f (x1 , . .
. , xi−1 , x̄i , xi+1 , . . . , xn ) çàâèñèò îò xi ìîíîòîííî (ñîîòâåòñòâåííî, êîíúþíêòèâíî,ÔÀËñòâåííîäèçúþíêòèâíî).β ∈ Bn,Kβ+îò ÁÏ X(n), ñîñòîÿùóþ èç òåõxj , j ∈ [1, n], äëÿ êîòîðûõ βhji = 1.nÍàáîð α, α ∈ B , íàçûâàåòñÿ íèæíåé åäèíèöåé ìîíîòîííîé ÔÀË f, f ∈ P2 (n), åñëèα ∈ Nf è f (β) = 0 äëÿ ëþáîãî îòëè÷íîãî îò α íàáîðà β òàêîãî, ÷òî β ≤ α.
Ìíîæåñòâî âñåõ+íèæíèõ åäèíèö ìîíîòîííîé ÔÀË f Nf .Ëåììà. Ñîêðàùåííàÿ ÄÍÔ U ìîíîòîííîé ÔÀË f, f ∈ P2 (n), ÿâëÿåòñÿ åäèíñòâåííîé òóïèWêîâîé ÄÍÔ ýòîé ÔÀË è èìååò âèä U(x1 , . . . , xn ) =Kβ+ (x1 , . . . , xn ). Ïðè ýòîì âñå íàáîðûÑîïîñòàâèì êàæäîìó íàáîðóìîíîòîííóþ ÝÊè òîëüêî òåõ áóêâβ∈Nf++èç Nf ÿâëÿþòñÿ ÿäðîâûìè òî÷êàìè ÔÀË f .+Ýòàïû äîêàçàòåëüñòâà. Kβ (α) = 1 òîãäà è òîëüêî òîãäà, êîãäà α ≥ β . Ñëåäîâàòåëüíî,β åäèíñòâåííàÿ íèæíÿÿ åäèíèöà Kβ+ , Kβ+0 èìïëèöèðóåò Kβ+00 òîãäà è òîëüêî òîãäà, êîãäàβ 0 ≥ β 00 .
Ïîëó÷èì, ÷òî Kβ+ ïðîñòàÿ èìïëèêàíòà f â òîì è òîëüêî òîì ñëó÷àå, êîãäà β ∈ Nf+ .È β ÿäðîâàÿ òî÷êà f . Ñëåäñòâèå.Ìîíîòîííàÿ ÔÀË ÿâëÿåòñÿ ÿäðîâîé ÔÀË.N = {α1 , . . . , αs }R = (N1 , . . . , Np ) ñèñòåìà åãî ïîäìíîæåñòâ,(N , R) ìàòðèöó M, M ∈ B p,s , äëÿêîòîðîé M hi, ji = 1 òîãäà è òîëüêî òîãäà, êîãäà αj ∈ Ni . i-ÿ ñòðîêà ìàòðèöû M ïîêðûâàåòåå j -é ñòîëáåö, åñëè M hi, ji = 1. Ñèñòåìà ñòðîê ñ íîìåðàìè èç I, I ⊆ [1, p], îáðàçóåò ïîêðûòèåìàòðèöû M , åñëè êàæäûé åå ñòîëáåö ïîêðûâàåòñÿ õîòÿ áû îäíîé ñòðîêîé ñ íîìåðîì èç I ,òî åñòü ñèñòåìà ïîäìíîæåñòâ {Ni }i∈I çàäàåò ïîêðûòèå ìíîæåñòâà N .Ïîêðûòèå ìàòðèöû M , â êîòîðîì íè îäíà ñòðîêà íå ïîêðûâàåòñÿ äðóãîé ñòðîêîé, ñ÷èòà êîíå÷íîå ìíîæåñòâî, àîáðàçóþùèõ ïîêðûòèå ìíîæåñòâàåòñÿ íåïðèâîäèìûì,ïèêîâûì.N.Ñîïîñòàâèì ïàðåà ïîêðûòèå, íå èìåþùåå ñîáñòâåííûõ ïîäïîêðûòèé, íàçûâàåòñÿòó-M, M ∈ B p,s ìàòðèöà áåç íóëåâûõ ñòîëáöîâ.
Ñîïîñòàâèì i-é ñòðîêå, i ∈ [1, p], ìàòðèöû MpÁÏ yi , à êàæäîìó íàáîðó β, β ∈ B , çíà÷åíèé ýòèõ ïåðåìåííûõ y = (y1 , . . . , yp ), ìíîæåñòâîñòðîê ìàòðèöû M ñ íîìåðàìè èç ìíîæåñòâà I = I(β) ⊆ [1, p], ãäå i ∈ I(β) òîãäà è òîëüêîòîãäà, êîãäà βhii = 1. ÔÀË F (y), äëÿ êîòîðîé F (β) = 1 òîãäà è òîëüêî òîãäà, êîãäà ñèñòåìàñòðîê ìàòðèöû M ñ íîìåðàìè èç I(β) îáðàçóåò åå ïîêðûòèå, ôóíêöèÿ ïîêðûòèÿ ìàòðèöûM.Ëåììà.
Ôóíêöèÿ ïîêðûòèÿ F (y1 , . . . , yp ) ìàòðèöû M, M ∈ B p,s , áåç íóëåâûõ ñòîëáöîâ5sVF (y1 , . . . , yp ) =çàäàåòñÿ ÊÍÔ âèäà:j=1Ýòàïû äîêàçàòåëüñòâà. Ïóñòüìí-âî ñòðîê ñ íîìåðàìè èçòîëüêî òîãäà, êîãäàÑëåäñòâèå.I(β)I(β)JjW(yi ).1≤i≤pM <i,j>=1 òî, ÷òî â ñêîáêàõ.j ñòîëáåö ⇒ïîêðûòèå. ïîêðûâàþòîáðàçóþòJj (β) = 1äëÿ ïðîèçâîëüíîãîβ⇔âñÿ ÊÍÔ îáðàùàåòñÿ â 1 òîãäà è ðåçóëüòàòå ðàñêðûòèÿ ñêîáîê è ïðèâåäåíèÿ ïîäîáíûõ èç óïîìÿíóòîé ÊÍÔìîæíî ïîëó÷èòü ñîêðàùåííóþ ÄÍÔ ÔÀËF (y),ïðîñòûå èìïëèêàíòû êîòîðîé âçàèìíî îäíî-çíà÷íî ñîîòâåòñòâóþò òóïèêîâûì ïîêðûòèÿì ìàòðèöûM.6Òåîðåìà. Ïóñòü äëÿ äåéñòâèòåëüíîãî γ, 0 < γ ≤ 1, â êàæäîì ñòîëáöå ìàòðèöû M, M ∈B p,s , èìååòñÿ íå ìåíüøå, ÷åì γ·p, åäèíèö. Òîãäà ïîêðûòèå ìàòðèöû M , ïîëó÷àåìîå ñ ïîìîùüþ++11ãðàäèåíòíîãî àëãîðèòìà, èìååò äëèíó íå áîëüøå, ÷åì d ln (γs)e + .
ln x = ln x, åñëè x ≥ 1,γγln+ x = 0, 0 < x < 1.Ýòàïû äîêàçàòåëüñòâà. Ïóñòü ïîêðûòèå äëèíû q . Ðàññìîòðèì øàã t àëãîðèòìà. δt äîëÿ îñòàâøèõñÿ ñòîëáöîâ. Ïîñêîëüêó çà îäèí øàã ìû óäàëÿåì íå ìåíåå îäíîãî ñòîëáöà,ñïðàâåäëèâî íåðàâåíñòâî:γsδtq ≤ t + δt · s. ìàòðèöå íà øàãåtγpsδt åäèíèö, â ñðåäíåì,γsδt åäèíèö. Îòñþäàδt ≤ (1 − γ)t ≤ e−γt . Âçÿââñåãîâ ñòðîêå.
Òàêèì îáðàçîì, â ìàêñèìàëüíîé ñòðîêå íå ìåíüøå, ÷åìïîëó÷àåìïàðàìåòðsδt+1 = st+1 ≤ st − γsδt = sδt (1 − γ).t íóæíûì îáðàçîì, è ïîäñòàâèâ åãî âÑëåäîâàòåëüíî,ïåðâîå íåðàâåíñòâî, ïîëó÷èì íåîáõîäèìóþîöåíêó.Ëåììà.nÏðè ëþáûõ íàòóðàëüíûõìîùíîñòè íå áîëåå, ÷åìmn·2èm, m ≤ n,â êóáåBn, ïðîòûêàþùåå âñå ãðàíè ðàíãàâñåãäà íàéäåòñÿ ïîäìíîæåñòâîm.Ýòàïû äîêàçàòåëüñòâà.
Ðàññìîòðåòü ìíîæåñòâî ãðàíåé ðàíãàα.òåîðåìîé. æåñòâ, ïðîõîäÿùèõ ÷åðåç òî÷êóçîâàòüñÿ ïðåäûäóùåémè ñèñòåìó åãî ïîäìíî-Ðàññìîòðåòü ìàòðèöó, ñâÿçàííóþ ñ ýòîé ïàðîé è âîñïîëü-7Çàäà÷à ìèíèìèçàöèèÄÍÔ çàäà÷à ïîñòðîåíèå îïòèìàëüíîé â òîì èëè èíîì ñìûñëåÄÍÔ äëÿ çàäàííîé ÔÀË.Íåîòðèöàòåëüíûé ôóíêöèîíàë ñëîæíîñòè ψåñëèU0∀UÄÍÔîïðåäåëåíà ñëîæíîñòüîáëàäàåò ñâîéñòâîìψ(U), ψ(U) ≥ 0, ψ(U 0 ) > ψ(U 00 ),ìîíîòîííîñòè,U 00ïîëó÷àåòñÿ èçóäàëåíèåì áóêâ èëè ÝÊ.Çàäà÷à ìèíèìèçàöèè ÄÍÔ îòíîñèòåëüíî ôóíêöèîíàëà ψfåñëèU,òàêîé ÄÍÔ÷òîψ(U) = min ψ(U 0 ), ïîñòðîåíèå äëÿ ÔÀËãäå ìèíèìóì áåðåòñÿ ïî âñåì ÄÍÔU 0,ðåàëèçóþ-ìèíèìàëüíàÿ îòíîñèòåëüíî ôóíêöèîíàëà ψ , çíà÷åíèå ψ(U) ñëîæíîñòü f îòíîñèòåëüíî ψ èëè ψ -ñëîæíîñòü.Ôóíêöèÿ Øåííîíà äëÿ êëàññà ÄÍÔ îòíîñèòåëüíî ψ ýòî ψ(n) = max ψ(f ), õàðàêòåùèì ÔÀËf.ÒîãäàUf ∈P2 (n)ψ -ñëîæíîñòè ÔÀË èç P2 (n).n, n ∈ N èìåþò ìåñòî ñîîòíîøåíèÿ λ(n) = 2n−1ðèçóåò ìàêñèìàëüíîå çíà÷åíèåËåììà.n · 2n−1(ýòîÄëÿ ëþáîãî(ýòîäëèíà), R(n) =ðàíã).Ýòàïû äîêàçàòåëüñòâà. Íèæíèå îöåíêè èç ñîâåðøåííîé ÄÍÔ ëèíåéíîé.
Âåðõíèå èçðàçëîæåíèÿ Øåííîíà ïî âñåì ïåðåìåííûì, êðîìå ïåðâîé (òîãäà ïîëó÷èòñÿ íå áîëååñëàãàåìûõ ðàíãîì≤nóìíîæàåì íà 1 áóêâó)èç-çà òîãî, ÷òî ðàñêëàäûâàåì ïîÏóñòü òèïè÷íûå çíà÷åíèÿòè÷åñêè ðàâíûψ(n),ψ(n)ïðèíàäëåæàòòî ýòî íàçûâàåòñÿn−1Óòâåðæäåíèå.ïåðåìåííîé è åùå îïöèîíàëüíî[ψ 0 (n), ψ 00 (n)].ýôôåêòîì Øåííîíà.äàåòñÿ.Ïî÷òè äëÿ âñåõ ÔÀË èçP2 (n)âåðíî2n−1ψ 0 (n) è ψ 00 (n) àñèìïòîλ(n) è R(n) åãî íå íàáëþ-ÅñëèÓn|Nf | = 2n−1 · (1 ± O(n · 2− 2 )).Ýòàïû äîêàçàòåëüñòâà. Îöåíèòü ìàòîæèäàíèå è äèñïåðñèþ ñëó÷àéíîé âåëè÷èíû, ðàâíîé0 èëè 1 ñ ðàâíûìè âåðîÿòíîñòÿìè (E= 21 ; D =14 ), ïîòîì ïåðåéòè ê ñëó÷àþ ñóììû èç n òàêèõ6= 2n−1 ; D = 2n−2 ).
Çàòåì âîñïîëüçîâàòüñÿ íåðàâåíñòâîì ×åáûøåâà. Ëåììà. Äëÿ ïî÷òè âñåõ ÔÀË f èç P2 (n) âûïîëíåíû íåðàâåíñòâà: λ(f ) ≤ 43 · 2n−1 · (1 ±nnO(n · 2− 2 )) è R(f ) ≤ 34 · n · 2n−1 · (1 ± O(n · 2− 2 )).ñëó÷àéíûõ âåëè÷èí (EÝòàïû äîêàçàòåëüñòâà. Ðàññìîòðåòü ñëó÷àéíóþ âåëè÷èíó êàê äèçúþíêöèþ äâóõ, îöåíèòüåå äèñïåðñèþ è ìàòîæèäàíèå (Eñëó÷àéíûõ âåëè÷èí (E=3 n−1;D423), çàòåì âû÷èñëèòü èõ äëÿ ñóììû èç n òàêèõ= 43 ; D = 163 n−1= 16 2).
Äàëåå, àíàëîãè÷íî ïðåäûäóùåìó óòâåðæäåíèþ.8Áóäåì îáîçíà÷àòü çíà÷åíèå ôóíêöèè Øåííîíà äëÿ ïàðàìåòðîâ, ðàâíûõ ÷èñëó òóïèêîâûõÄÍÔ, ÷èñëó ìèíèìàëüíûõ ÄÍÔ è äëèíå ñîêðàùåííîé ÄÍÔ ÔÀË èçλñîêðP2 (n)êàêτ (n), µ(n)èñîîòâåòñòâåííî.Ëåììà. ×èñëî òóïèêîâûõ (ìèíèìàëüíûõ) ÄÍÔ ó ÔÀË f èç P2 (n), n ≥ 4, âèäàn−4f (x1 , . . . , xn ) = g(x1 , x2 , x3 )·(x4 ⊕. . .⊕xn ), ãäå N̄ = {(000), (111)}, ðàâíî 52(ñîîòâåòñòâåííî,n−422 ).Ýòàïû äîêàçàòåëüñòâà. Âûâåñòè âèä ïðîñòîé èìïëèêàíòû èç ñâîéñòâ f è g (Âñåãî â ñîêðàùåííîé ÄÍÔ f 6 ðàçíûõ ÝÊ, à ⊕ âñåõ ñòåïåíåé ÝÊ g ðàâíà 1, âåäü îíà ëèíåéíà). Ïîëó÷èòün−4ãåîìåòðè÷åñêîå ïðåäñòâàëåíèå (öèêëû äëèíû 6, âñåãî èõ 2).
Ëþáàÿ òóïèêîâàÿ (ìèíèìàëüíàÿ) âêëþ÷àåò îäíî èç 5 (2) ðåáåðíûõ ïîêðûòèé äëÿ êàæäîãî öèêëà, ïîýòîìó ïîëó÷àþòñÿîöåíêè èç óñëîâèÿ.2n−4, µn (n) ≥ 2.IÄëÿ I ⊆ [0, n] ÷åðåç sn (x1 , . . . , xn ) îáîçíà÷èì ÔÀË èç P2 (n), êîòîðàÿ ÿâëÿåòñÿ õàðàêòåðèñòè÷åñêîé ÔÀË îáúåäèíåíèÿ âñåõ ñëîåâ êóáà Bn ñ íîìåðàìè èç I . Ïðè ýòîì ÷èñëà èç IIIñ÷èòàþòñÿ ðàáî÷èìè ÷èñëàìè ÔÀË sn . Çàìåòèì, ÷òî ÔÀË sn ÿâëÿåòñÿ ñèììåòðè÷åñêîé,òî åñòü íå èçìåíÿåò ñâîå çíà÷åíèå ïðè ëþáîé ïåðåñòàíîâêå àðãóìåíòîâ, è íàîáîðîò, ëþáàÿIñèììåòðè÷åñêàÿ ôóíêöèÿ àëãåáðû ëîãèêè ñîâïàäàåò ñ îäíîé èç ÔÀË âèäà sn .Ñèììåòðè÷åñêàÿ ÔÀË íàçûâàåòñÿ ïîÿñêîâîé, åñëè åå ðàáî÷èå ÷èñëà îáðàçóþò îòðåçîê.nËåììà. λñîêð (n) ≥ e1 · 3n , ãäå e1 íåêîòîðàÿ êîíñòàíòà.Ýòàïû äîêàçàòåëüñòâà.
Ïîÿñêîâàÿ ÔÀË îò n ïåðìåííûõ ñ ðàáî÷èìè ÷èñëàìè [r, p]èìååòW. Òî åñòü ñíà÷àëà ìû âûáèðàåì ñðåäè n ïåðåìåííûõ rÄÍÔxσi11 · · · xin+r−pn+r−p1≤i1 <···<in+p−r ≤nσ1 +···+σn+p−r =rÑëåäñòâèå. τ (n) ≥ 52n−4ïåðåìåííûõ áåç îòðèöàíèÿ, à ïîòîì ñðåäèåå äëèíà ðàâíàëåììûn−rCrn · Cn−p.n−rïåðåìåííûõn−pñ îòðèöàíèåì. Òàê ÷òîÂîñïîëüçîâàâøèñü ôîðìóëîé Ñòèðëèíãà, ïîëó÷èì óòâåðæäåíèåÔóíêöèÿf (x1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
