OK-metodichka-2010-part1 (1132792), страница 8
Текст из файла (страница 8)
Ýòî îçíà÷àåò, â ÷àñòíîñòè, ÷òî äëÿ ïî÷òè âñåõÔÀË f èç P2 (n), âûïîëíåíî ðàâåíñòâî|Nf | = 2n−1 1 ± O n · 2−n/2(7.5)òî åñòü äëèíà ñîâåðøåííîé ÄÍÔ ó ïî÷òè âñåõ ÔÀË èç P2 (n)àñèìïòîòè÷åñêè ðàâíà 2n−1 .Äëÿ ïî÷òè âñåõ ÔÀË f , f ∈ P2(n), âûïîëíÿþòñÿ íåðàâåíñòâàËåììà 7.2.3λ(f ) 6 2n−1 1 + O n · 2−n/2 ,43λ(f ) 6 n · 2n−1 1 + O n · 2−n/2 ,4(7.6)(7.7)Äîêàçàòåëüñòâî. Ïóñòü ÔÀË f , f ∈ P2(n), ÿâëÿåòñÿ ðåàëè-çàöèåé ñëó÷àéíîé âåëè÷èíû ξ .
Äëÿ êàæäîãî íàáîðà β , β ∈B n−1 , ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó ηβ = ξ(0,β) ∨ ξ(1,β) .Çàìåòèì, ÷òî ñëó÷àéíûå âåëè÷èíû ηβ , β ∈ B n−1 , íåçàâèñèìû, à ìàòåìàòè÷åñêîå îæèäàíèå è äèñïåðñèÿ ëþáîé èç íèõ3ðàâíû 34 è 16ñîîòâåòñòâåííî. Çàìåòèì òàêæå, ÷òî ðàâåíñòâîηβ = 1 âûïîëíÿåòñÿ òîãäà è òîëüêî òîãäà, êîãäà â ÄÍÔ Af ,ïîñòðîåííîé ïî ëåììå 7.1 äëÿ ÔÀË f , âõîäèò ñëàãàåìîå, ñîîòâåòñòâóþùåå íàáîðó β . Èç íåçàâèñèìîñòè ñëó÷àéíûõ âåëè÷èí ηβ , β ∈ B n−1 , ñëåäóåò, ÷òî äëÿ èõ ñóììû ηe = ηe(n)âûïîëíÿþòñÿ ñîîòíîøåíèÿ3Eeη (n) = 2n−1 ,4Deη (n) =3 n−12.16Ïîëàãàÿlt= n·2n2m,I=3 n−13 n−12− t, 2+t44(7.8)52Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûè ïðîâîäÿ íà îñíîâå (7.8) ðàññóæäåíèÿ àíàëîãè÷íûå òåì, ñïîìîùüþ êîòîðûõ èç ñîîòíîøåíèé (7.4) âûâîäèëîñü ðàâåí-nñòâî (7.5), ïîëó÷èì, ÷òî λ(Af ) ∈ I ó íå ìåíåå, ÷åì 22 1 − n12ÔÀË f èç P2 (n).
Ýòî îçíà÷àåò, ÷òî äëÿ ïî÷òè âñåõ ÔÀË f ,f ∈ P2 (n), äëèíà è ðàíã å¼ ÄÍÔ Af , ïîñòðîåííîé â ñîîòâåòñòâèè ñ ëåììîé 7.1, óäîâëåòâîðÿåò (7.6), (7.7).Ëåììà äîêàçàíà.8Àëãîðèòìè÷åñêèå òðóäíîñòè ìèíèìèçàöèèÄÍÔ è îöåíêè ìàêñèìàëüíûõ çíà÷åíèé íåêîòîðûõ ñâÿçàííûõ ñ íåé ïàðàìåòðîâ. ÒåîðåìàÞ. È.
Æóðàâëåâà î ÄÍÔ ñóììà ìèíèìàëüíûõÐåøåíèå çàäà÷ ìèíèìèçàöèè ÄÍÔ äëÿ çàäàííîé ÔÀË õàðàêòåðèçóåòñÿ ðàçëè÷íûìè ïàðàìåòðàìè ýòîé ÔÀË è, âïåðâóþ î÷åðåäü, çíà÷åíèÿìè èññëåäóåìûõ ôóíêöèîíàëîâ ååñëîæíîñòè (ñì. 7). Êðîìå òîãî, êàê îòìå÷àëîñü âûøå, ðÿäïàðàìåòðîâ (äëèíà ñîêðàùåííîé ÄÍÔ, ÷èñëî òóïèêîâûõ èëèìèíèìàëüíûõ ÄÍÔ è äð.) õàðàêòåðèçóþò òðóäîåìêîñòü çàäà÷è ìèíèìèçàöèè ÄÍÔ äëÿ ðàññìàòðèâàåìîé ÔÀË.  ñâÿçè ñ ýòèì ïðåäñòàâëÿåò èíòåðåñ ïîâåäåíèå ïðè n = 1, 2, . . .,ìàêñèìàëüíîãî çíà÷åíèÿ òîãî èëè èíîãî ïîäîáíîãî ïàðàìåòðà ψ äëÿ ÔÀË èç P2 (n):ψ(n) = max ψ(f ),f ∈P2 (n)êîòîðîå,êàê è â ñëó÷àå ôóíêöèîíàëîâ ñëîæíîñòè, íàçûâàþò,îáû÷íî, ôóíêöèåé Øåííîíà äëÿ ïàðàìåòðà ψ â êëàññå ÄÍÔ.Áóäåì îáîçíà÷àòü çíà÷åíèå ôóíêöèè Øåííîíà äëÿ ïàðàìåòðîâ, ðàâíûõ ÷èñëó1 òóïèêîâûõ ÄÍÔ, ÷èñëó ìèíèìàëü1Âñå ÄÍÔ ðàññìàòðèâàþòñÿ ñ òî÷íîñòüþ äî ïåðåñòàíîâêè ÝÊ è áóêââ íèõ.8.53Ìèíèìèçàöèÿ ÄÍÔíûõ ÄÍÔ è äëèíå ñîêðàùåííîé ÄÍÔ ó ÔÀË èç P2 (n), ÷åðåçτ (n), µ (n) è λñîêð.
(n) ñîîòâåòñòâåííî.Èç ìîíîòîííîñòè ôóíêöèîíàëà ψ äëÿ ñëîæíîñòè ÄÍÔ(ñì. 7) ñëåäóåò, ÷òî ψ -ìèíèìàëüíóþ ÄÍÔ âñåãäà ìîæíî âûáðàòü ñðåäè òóïèêîâûõ ÄÍÔ, àëãîðèòì ïîñòðîåíèÿ êîòîðûõîïèñàí â 6. Îäíàêî, êàê ïîêàçûâàåò ñëåäóþùåå óòâåðæäåíèå, ÔÀË ìîãóò èìåòü î÷åíü ìíîãî ðàçëè÷íûõ òóïèêîâûõÄÍÔ, è äàæå ÷èñëî ðàçëè÷íûõ ìèíèìàëüíûõ ÄÍÔ ó íèõìîæåò áûòü î÷åíü âåëèêî.×èñëî òóïèêîâûõ (ìèíèìàëüíûõ) ÄÍÔ ó ÔÀËf èç P2 (n) , n > 4, âèäàËåììà 8.1.f (x1 , . . . , xn ) = g(x1 , x2 , x3 ) · (x4 ⊕ · · · ⊕ xn ),ãäå N g = {(000), (111)}, ðàâíî 52 (ñîîòâåòñòâåííî 22 ).Äîêàçàòåëüñòâî.
Èç ñâîéñòâ ëèíåéíîé ÔÀË è ñâîéñòâ ÔÀËn−4n−4g âûòåêàåò, ÷òî (ñì. 1 è 4) ëþáàÿ ïðîñòàÿ èìïëèêàíòà KÔÀË f èìååò âèäK = Ki (x1 , x2 , x3 ) · xβ4 4 · · · xβnn ,ãäå Ki , i = 1, . . . , 6, ïðîñòàÿ èìïëèêàíòà ÔÀË g (ñì. ðèñ.2.2a è (2.10)) è β4 ⊕ · · · ⊕ βn = 1. Òàêèì îáðàçîì, ñîêðàùåííàÿ ÄÍÔ ÔÀË f ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ ñîñòîèòèç 2n−4 öèêëîâ äëèíû 6 (ñì. 4). Ñëåäîâàòåëüíî, ëþáàÿ òóïèêîâàÿ (ìèíèìàëüíàÿ) ÄÍÔ ÔÀË f âêëþ÷àåò â ñåáÿ îäíîèç ïÿòè (ñîîòâåòñòâåííî äâóõ) ðåáåðíûõ ïîêðûòèé, ñâÿçàííûõ ñ òóïèêîâûìè (ñîîòâåòñòâåííî ìèíèìàëüíûìè) ÄÍÔÔÀË g , ïðèâåäåííûìè â (4.1)(4.2) (ñîîòâåòñòâåííî (4.1)),äëÿ êàæäîãî èç 2n−4 óêàçàííûõ öèêëîâ. Ïîýòîìó ÷èñëî òón−4ïèêîâûõ (ìèíèìàëüíûõ) ÄÍÔ ÔÀË f ðàâíî 52(ñîîòâåòn−4ñòâåííî 22 ).Ëåììà äîêàçàíà.54Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÑëåäñòâèå.n−4τ (n) > 52n−4, µn (n) > 22.Âàæíûì ïàðàìåòðîì, âëèÿþùèì íà ðàçìåð òàáëèöû Êâàéíà è, ñëåäîâàòåëüíî, íà òðóäîåìêîñòü çàäà÷è ìèíèìèçàöèè,ÿâëÿåòñÿ äëèíà ñîêðàùåííîé ÄÍÔ.
Óñòàíîâèì íåêîòîðûåíèæíèå îöåíêè äëèíû ñîêðàùåííîé ÄÍÔ ó ÔÀË îò n ÁÏ,ïîêàçûâàþùèå, â ÷àñòíîñòè, ÷òî äëèíà ñîêðàùåííîé ÄÍÔìîæåò áûòü ñóùåñòâåííî áîëüøå äëèíû ñîâåðøåííîé ÄÍÔòîé æå ÔÀË.Äëÿ I ⊆ [0, n] ÷åðåç sIn (x1 , . . . , xn ) îáîçíà÷èì ÔÀË èçP2 (n), êîòîðàÿ ÿâëÿåòñÿ õàðàêòåðèñòè÷åñêîé ÔÀË îáúåäèíåíèÿ âñåõ ñëîåâ êóáà B n ñ íîìåðàìè èç I . Ïðè ýòîì ÷èñëà èç I ñ÷èòàþòñÿÔÀË sIn . Çàìåòèì, ÷òîIÔÀË sn ÿâëÿåòñÿ, òî åñòü íå èçìåíÿåò ñâîåçíà÷åíèå ïðè ëþáîé ïåðåñòàíîâêå àðãóìåíòîâ, è íàîáîðîò,ëþáàÿ ñèììåòðè÷åñêàÿ ôóíêöèÿ àëãåáðû ëîãèêè ñîâïàäàåò ñ îäíîé èç ÔÀË âèäà sIn . Çàìåòèì òàêæå, ÷òî îòëè÷íàÿîò êîíñòàíòû ñèììåòðè÷åñêàÿ ÔÀË ÿâëÿåòñÿ ñóùåñòâåííîéÔÀË. Ëåãêî âèäåòü, ÷òî ðàáî÷èìè ÷èñëàìè ñèììåòðè÷åñêèõÔÀË `n è `n ÿâëÿþòñÿ âñå íå÷åòíûå è âñå ÷åòíûå ÷èñëà îòðåçêà [0, n] ñîîòâåòñòâåííî.Ñèììåòðè÷åñêàÿ ÔÀË íàçûâàåòñÿ, åñëè åå ðàáî÷èå ÷èñëà îáðàçóþò îòðåçîê. Ïîÿñêîâîé ÔÀË ÿâëÿåòñÿ, â[2,3]÷àñòíîñòè, ÔÀË ãîëîñîâàíèÿ H (x1 , x2 , x3 ) = s3 , à òàê[1,2]æå ÔÀË g = s3 , ïîêàçàííàÿ íà ðèñ.
2.2a. Ëåãêî âèäåòü,[r,p]÷òî ñîêðàùåííàÿ ÄÍÔ ïîÿñêîâîé ÔÀË sn (x1 , . . . , xn ), ãäå0 6 r 6 p 6 n, ñîñòîèò èç âñåõ ÝÊ ðàíãà (n + r − p), êîòîðûå ñîäåðæàò r ÁÏ è (n − p) îòðèöàíèé ÁÏ, òî åñòü èìååòâèä_σn+r−p.(8.1)s[r,p](x1 , . . . , xn ) =xσi11 · · · xin+r−pnðàáî÷èìè ÷èñëàìèñèììåòðè÷åñêîéïîÿñêîâîé16i1 <···<in+r−p 6nσ1 +···+σn+r−p =r8.55Ìèíèìèçàöèÿ ÄÍÔÈç (8.1)÷òî äëèíà ñîêðàùåííîé ÄÍÔ ñëåäóåò, n ÔÀË snnn−pðàâíà r · n−r , è ïîýòîìó ïðè r = n − p = 3 îíà â ñîîònâåòñòâèè ñ ôîðìóëîé Ñòèðëèíãà (1.3) íå ìåíüøå, ÷åì e1 3n ,ãäå e1 íåêîòîðàÿ êîíñòàíòà. Òàêèì îáðàçîì, äîêàçàíî ñëåäóþùåå óòâåðæäåíèå:[r,p]Ëåììà 8.2.λñîêð.
(n) > e1ãäå e1 íåêîòîðàÿ êîíñòàíòà.3n,nÐàññìîòðåííûå ïðèìåðû ïîêàçûâàþò, ÷òî ñ àëãîðèòìè÷åñêîé òî÷êè çðåíèÿ çàäà÷à ìèíèìèçàöèè ÄÍÔ ÿâëÿåòñÿî÷åíü òðóäîåìêîé çàäà÷åé.  òåîðèè ñëîæíîñòè âû÷èñëåíèé,ãäå òðóäîåìêîñòü àëãîðèòìà îïðåäåëÿåòñÿ, îáû÷íî, ÷èñëîìáèòîâûõ îïåðàöèé, íåîáõîäèìûõ äëÿ åãî âûïîëíåíèÿ â ¾õóäøåì¿ ñëó÷àå, âûäåëåí öåëûé êëàññ òàê íàçûâàåìûõ NPïîëíûõ ïðîáëåì, êîòîðûå ñ÷èòàþòñÿ àëãîðèòìè÷åñêè òðóäíûìè (ñì., íàïðèìåð, [1, 22]). Ê NP-ïîëíûì ïðîáëåìàì îòíîñèòñÿ, â ÷àñòíîñòè, ïðîáëåìà âûïîëíèìîñòè ÊÍÔ, êîòîðàÿ ñîñòîèò â òîì, ÷òîáû ïî çàäàííîé ÊÍÔ âûÿñíèòü, ðàâíàòîæäåñòâåííî íóëþ ðåàëèçóåìàÿ åþ ÔÀË èëè íåò. Òàêèì îáðàçîì, äàæå ïîñòðîåíèå ñîêðàùåííîé ÄÍÔ èç ÊÍÔ (ñì.
3)ÿâëÿåòñÿ àëãîðèòìè÷åñêè òðóäíîé çàäà÷åé.Ñ äðóãîé ñòîðîíû, Þ.È. Æóðàâëåâ [9, 6] ïðåäëîæèë ïðèìåíèòåëüíî ê ÄÍÔ ìîäåëü òàê íàçûâàåìûõ ëîêàëüíûõ èëèîêðåñòíîñòíûõ àëãîðèòìîâ, êîãäà ïðåîáðàçîâàíèå ðàññìàòðèâàåìîé ãðàíè îäíîçíà÷íî îïðåäåëÿåòñÿ ¾ñîñòîÿíèåì¿ åå¾îêðåñòíîñòè¿ çàäàííîãî ïîðÿäêà (ñì. 4). Îí æå (ñì. òåîðåìó 8.1) äîêàçàë, ÷òî ïðè ïîñòðîåíèè ìèíèìàëüíîé ÄÍÔäëÿ ÔÀË èç P2 (n) , n > 3, ïðèõîäèòñÿ, â îáùåì ñëó÷àå, ðàññìàòðèâàòü îêðåñòíîñòè ïîðÿäêà (n − 3) åå ìàêñèìàëüíûõãðàíåé.
Ñëåäîâàòåëüíî, çàäà÷à ìèíèìèçàöèè ÄÍÔ ÿâëÿåòñÿòðóäíîé è ñ òî÷êè çðåíèÿ óðîâíÿ ëîêàëüíîñòè èñïîëüçóåìûõàëãîðèòìîâ.56Ãëàâà 1.N1α` 2Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûN2α1 `N1` α3α` 2N2α1 `` α3Ntαt+1 `Nta)`αt `Nt−1`b)Ðèñ. 8.1: ìíîæåñòâî Nf äëÿ öåïíîé è öèêëè÷åñêîé ÔÀË fÎïðåäåëèì ÄÍÔ ñóììà ìèíèìàëüíûõ ÔÀË f (ÄÍÔ ΣMÔÀË f ) êàê äèçúþíêöèþ âñåõ òåõ å¼ ïðîñòûõ èìïëèêàíò,êîòîðûå âõîäÿò õîòÿ áû â îäíó ìèíèìàëüíóþ ÄÍÔ ÔÀË f .Ôóíêöèÿ f (x1 , . . . , xn ) íàçûâàåòñÿ()t, åñëè åå ñîêðàùåííàÿ ÄÍÔ ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ ïðåäñòàâëÿåò ñîáîé öåïü (ñîîòâåòñòâåííî öèêë) èç t ïîñëåäîâàòåëüíî ñîåäèíåííûõ ðåáåð N1 , N2 , .
. . , Ntêóáà B n (ñì. ðèñ. 8.1a è 8.1b). Çàìåòèì, ÷òî öèêëè÷åñêàÿÔÀË äëèíû t ñóùåñòâóåò òîãäà è òîëüêî òîãäà, êîãäà t > 6 ÷åòíîå ÷èñëî, à öåïíàÿ ÔÀË äëèíû t ïðè ëþáîì t > 1.Ïðèìåð öåïíîé ÔÀË äëèíû 3 äàåò ÔÀË g 00 , ïîêàçàííàÿ íàðèñ. 4.1, à ÔÀË g (ñì. ðèñ. 2.1a) ÿâëÿåòñÿ öèêëè÷åñêîé ÔÀËäëèíû 6.Èç òåîðåìû 4.1 ñëåäóåò, â ÷àñòíîñòè, ÷òî äëÿ ëþáîé öåïíîé ÔÀË äëèíû íå ìåíüøå 4 è ëþáîé öèêëè÷åñêîé ÔÀËÄÍÔ ΣT ñîâïàäàåò ñ ñîêðàùåííîé ÄÍÔ. Ïðè ýòîì öåïíàÿÔÀË f íå÷åòíîé äëèíû t = 2k − 1 > 3 èìååò åäèíñòâåííóþìèíèìàëüíóþ ÄÍÔ, êîòîðàÿ ñîâïàäàåò ñ åå ÄÍÔ ΣM è ñîîòâåòñòâóåò ïîêðûòèþ (ñì. ðèñ. 8.1a) N1 ∪N3 ∪.
. .∪Nt äëèíûk . Äåéñòâèòåëüíî, ìíîæåñòâî Nf â äàííîì ñëó÷àå ñîñòîèò èç2k íàáîðîâ è íå ìîæåò áûòü ïîêðûòî (k − 1) ðåáðîì. Êðî-ôóíêöèåé äëèíûöåïíîé öèêëè÷åñêîé8.57Ìèíèìèçàöèÿ ÄÍÔNn−1αn `= e1αn−1`α2Nn`αn+1`N1```α1α2n−2N2n−2α2n−1`e0Ðèñ. 8.2: öåïíàÿ ÔÀË äëèíû (2n − 2) â êóáå B nìå òîãî, ïîêðûòèå ìíîæåñòâà Nf , ñîñòîÿùåå èç k ðåáåð, íåìîæåò âêëþ÷àòü â ñåáÿ ðåáðà ñ îáùèìè âåðøèíàìè è äîëæíî ñîäåðæàòü ÿäðîâûå ðåáðà N1 è Nt ÔÀË f . Ëåãêî âèäåòü,÷òî òîëüêî ïîêðûòèå N1 ∪ N3 ∪ . . . ∪ Nt îáëàäàåò âñåìè ýòèìè ñâîéñòâàìè.
Òàêèì îáðàçîì, äëÿ öåïíîé ÔÀË íå÷åòíîéäëèíû t, t > 5, ÄÍÔ ΣT íå ñîâïàäàåò ñ ÄÍÔ ΣM .Ïðè ëþáîì n ∈ N, n > 3, âñóùåñòâóþò ÔÀË è , èìåþùèå îáùóþ ïðîñòóþèìïëèêàíòó , êîòîðàÿ âõîäèò â ÄÍÔ ΣM îäíîé, íî íåâõîäèò â ÄÍÔäðóãîé èç ýòèõ ÔÀË è äëÿ êîòîðîé.Äîêàçàòåëüñòâî. Äîñòàòî÷íî ïîñòðîèòü â P2 (n) öåïíóþ ôóíê(ñð.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
