Lectionc1 (1132950), страница 8
Текст из файла (страница 8)
Ïðèìåíÿÿ óêàçàííûé âûøå ïîäõîä, ðàññìîòðèìËåììà 6.2 ([18]).ìíîæåñòâîN, ñîñòîÿùåå èç âñåõ ãðàíåé ðàíãà m êóáà B n ,jNj = mn 2m, à òàêæå ñèñòåìó N = fNg2Bn åãî ïîäìíîæåñòâ,ãäå N ìíîæåñòâî òåõ ãðàíåé èç N, êîòîðûå ïðîõîäÿò÷åðåç òî÷êó . Î÷åâèäíî, ÷òî êàæäàÿ ãðàíü èç N ñîäåðæèòñÿâ òåõ 2n m ïîäìíîæåñòâàõ N , äëÿ êîòîðûõ òî÷êà ïðèíàäëåæèòýòîé ãðàíè. Ñëåäîâàòåëüíî, ìàòðèöà M , ñâÿçàííàÿñ ïàðîénnm(N; N), ñîñòîèò èç p = 2 ñòðîê è s = m 2 ñòîëáöîâ,â êàæäîì èç êîòîðûõ èìååòñÿ p , ãäå = 2 m , åäèíèö.Èñêîìîå ìíîæåñòâî íàáîðîâ ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèìåíåíèÿê ìàòðèöå M òåîðåìû 6.1 è ïîñòðîåíèÿ ïîêðûòèÿ äëèíû q ,ãäåq62m ln+ nmËåììà äîêàçàíà.+ 2m n6+ 2m 6m6 2m (n 1) + 2m = n 2m:2m log7.51Îöåíêè ïàðàìåòðîâ ÄÍÔ7Çàäà÷à ìèíèìèçàöèè ÄÍÔ.
Ïîâåäåíèå ôóíêöèéØåííîíà è îöåíêè òèïè÷íûõ çíà÷åíèé äëÿðàíãà è äëèíû ÄÍÔÊàê óæå îòìå÷àëîñü, ÄÍÔ ïðåäñòàâëÿåò ñîáîé óäîáíóþ èíàãëÿäíóþ (ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ) ôîðìó çàäàíèÿÔÀË. Ñ äðóãîé ñòîðîíû, ÄÍÔ ìîæíî ðàññìàòðèâàòü êàêïðîñòåéøóþ ìîäåëü, ïðåäíàçíà÷åííóþ äëÿ ñòðóêòóðíîé ðåàëèçàöèèÔÀË (ñì. ãë. 3).Çàìåòèì, ÷òî ðàçëè÷íûå ïàðàìåòðû ÄÍÔ(ðàíã, äëèíà è ò. ï) õàðàêòåðèçóþò ðàçëè÷íûå ¾ìåðû¿ ñëîæíîñòèóêàçàííîãî ïðåäñòàâëåíèÿ èëè ñòðóêòóðíîé ðåàëèçàöèè.
Âñâÿçè ñ ýòèì ÷àñòî âîçíèêàåò íåîáõîäèìîñòü ïîñòðîåíèÿ îïòèìàëüíîéâ òîì èëè èíîì ñìûñëå ÄÍÔ äëÿ çàäàííîé ÔÀË, òî åñòüíåîáõîäèìîñòü ðåøåíèÿ ñîîòâåòñòâóþùåé çàäà÷è, êîòîðàÿ ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì çàäà÷è ñèíòåçàóïðàâëÿþùèõ ñèñòåì (ñì. ãë. 3). îáùåì âèäå çàäà÷à ìèíèìèçàöèè ÄÍÔ ìîæåò áûòüñôîðìóëèðîâàíà ñëåäóþùèì îáðàçîì. Ïóñòü äëÿ êàæäîéÄÍÔ A îïðåäåëåíà åå ¾ñëîæíîñòü¿ (A), (A) > 0, äëÿêîòîðîé (A0 ) > (A00 ), åñëè ÄÍÔ A00 ïîëó÷àåòñÿ èç ÄÍÔA0 óäàëåíèåì áóêâ èëè ÝÊ.  ýòîì ñëó÷àå áóäåì ãîâîðèòü,÷òî íà ìíîæåñòâå ÄÍÔ çàäàí íåîòðèöàòåëüíûé, îáëàäàþùèé ñâîéñòâîì.
Ïðèìåðàìèòàêèõ ôóíêöèîíàëîâ ìîãóò ñëóæèòü äëèíà (A), ðàíã R (A)èëè ¾ôîðìóëüíàÿ¿ ñëîæíîñòü L (A) ÄÍÔ A, à òàêæå ÷èñëîâõîæäåíèé ÁÏ ñ îòðèöàíèÿìè è äðóãèå ïàðàìåòðû ÄÍÔ.Çàäà÷à ìèíèìèçàöèè ÄÍÔ îòíîñèòåëüíî ôóíêöèîíàëà ñëîæíîñòèñîñòîèò â òîì, ÷òîáû ïî çàäàííîé ÔÀË f ïîñòðîèòü ðåàëèçóþùóþåå ÄÍÔ A òàêóþ, ÷òîìèíèìèçàöèèÄÍÔôóíêöèîíàëìîíîòîííîñòèñëîæíîñòèA0 ;ãäå ìèíèìóì áåðåòñÿ ïî âñåì ÄÍÔ A0 , ðåàëèçóþùèì ÔÀË f .Ïðè ýòîì ÄÍÔ A ñ÷èòàåòñÿ ìèíèìàëüíîé îòíîñèòåëüíî(A) = minôóíêöèîíàëà, èëè, èíà÷å,-ìèíèìàëüíîé ÄÍÔ, à çíà÷åíèå52Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû(A) íàçûâàåòñÿ ñëîæíîñòüþ ÔÀË f îòíîñèòåëüíî ôóíêöèîíàëà, èëè, èíà÷å, -ñëîæíîñòüþ ÔÀË f â êëàññå ÄÍÔ. Âñîîòâåòñòâèè ñ ââåäåííûìè ðàíåå îïðåäåëåíèÿìè, -ìèíèìàëüíóþÄÍÔ, òî åñòü ÄÍÔ ìèíèìàëüíóþ ïî äëèíå, áóäåì íàçûâàòüêðàò÷àéøåé, à R-ìèíèìàëüíóþ ÄÍÔ, òî åñòü ÄÍÔ ìèíèìàëüíóþ ïî ðàíãó, ïðîñòî ìèíèìàëüíîé.
Ôóíêöèþ(n) = max (f ) ;f 2P2 (n)êîòîðàÿ õàðàêòåðèçóåò ìàêñèìàëüíîå çíà÷åíèå -ñëîæíîñòèÔÀË èç P2 (n), íàçûâàþò, îáû÷íî,äëÿêëàññà ÄÍÔ îòíîñèòåëüíî ôóíêöèîíàëà .Óñòàíîâèì ïîâåäåíèå ôóíêöèé Øåííîíà (n) è R(n) äëÿäëèíû è ðàíãà ÄÍÔ ÔÀË èç P2 (n) ñîîòâåòñòâåííî.ôóíêöèåé ØåííîíàËåììà 7.1.Äëÿ ëþáîãî n; n 2 N, èìåþò ìåñòî ñîîòíîøåíèÿ(n) = 2n 1 ; R(n) = n 2n 1 :(7.1)Äîêàçàòåëüñòâî. Íèæíèå îöåíêè (7.1) ñëåäóþò èç òîãî,÷òî(ln ) = 2n 1è R(ln ) = n 2n 1 , òàê êàê åäèíñòâåííîé ÄÍÔëèíåéíîé ÔÀË ln = x1 xn ÿâëÿåòñÿ åå ñîâåðøåííàÿÄÍÔ. Äëÿ ïîëó÷åíèÿ òðåáóåìûõ â (7.1) âåðõíèõ îöåíîê âîçüìåìïðîèçâîëüíóþ ÔÀË f èç P2 (n) è, â ñîîòâåòñòâèè ñ (2.5),ðàçëîæèì åå ïî ÁÏ x2 ; : : : ; xn ñëåäóþùèì îáðàçîì:f (x1 ; : : : ; xn ) =_00 =(2 ;:::;n )x2 2 xnn f x1 ; 00(7.2)Ëåãêî âèäåòü, ÷òî ïîñëå çàìåíû â ðàçëîæåíèè (7.2) êàæäîéÔÀË f (x1 ; 00 ) ðàâíîé åé ÔÀË èç ìíîæåñòâà f0; 1; x1 ; x1 g èïðèâåäåíèÿ ïîäîáíûõ ìû ïîëó÷èì ÄÍÔ Af äëèíû íå áîëüøå,÷åì 2n 1 , ÷òî äîêàçûâàåò âåðõíèå îöåíêè â (7.1).Ëåììà äîêàçàíà.7.53Îöåíêè ïàðàìåòðîâ ÄÍÔÏðè èçó÷åíèè òîãî èëè èíîãî ñâÿçàííîãî ñ ÄÍÔ ôóíêöèîíàëàíàðÿäó ñ åãî ìàêñèìàëüíûì çíà÷åíèåì, òî åñòü ôóíêöèåéØåííîíà (n), ïðåäñòàâëÿåò èíòåðåñ ñîîòâåòñòâóþùèé îòðåçîê"òèïè÷íûõ" çíà÷åíèé, òî åñòü îòðåçîê [ 0 (n) ; 00 (n)], â êîòîðûéïîïàäàþò çíà÷åíèÿ (f ) äëÿ ïî÷òè âñåõ ÔÀË f èç P2 (n).Åñëè ïðè ýòîì ãðàíèöû 0 (n) è 00 (n), ãäå n = 1; 2; : : :,àñèìïòîòè÷åñêè ðàâíû (n), òî ãîâîðÿò, ÷òî äëÿ ïàðàìåòðàèìååò ìåñòî.
Âûÿñíèì íåêîòîðûå îñîáåííîñòèñòðîåíèÿ ÄÍÔ ó ïî÷òè âñåõ ÔÀË è óñòàíîâèì, â ÷àñòíîñòè,îòñóòñòâèå ýôôåêòà Øåííîíà äëÿ ïàðàìåòðîâ è R - äëèíûè ðàíãà ÄÍÔ ñîîòâåòñòâåííî.Ââåäåì äèñêðåòíóþ âåêòîðíóþ ñëó÷àéíóþ âåëè÷èíó (n) =e0 ; : : : ; e1 , ñîñòîÿùóþ èç 2n íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí ; 2 B n , ïðèíèìàþùèõ çíà÷åíèÿ 0 è 1 ñ âåðîÿòíîñòüþ1n2 .
Ïðè ýòîì, î÷åâèäíî, äëÿ ëþáîãî ; 2 B , âûïîëíÿþòñÿðàâåíñòâàýôôåêò ØåííîíàE = 21 ;D = 14 ;(7.3)ãäå E è D - ìàòåìàòè÷åñêîå îæèäàíèå è äèñïåðñèÿ ñëó÷àéíîéâåëè÷èíû (ñì., íàïðèìåð, [4]).Áóäåì ñ÷èòàòü, ÷òî ëþáàÿ ÔÀË f èç P2 (n) ÿâëÿåòñÿðåàëèçàöèåé âåëè÷èíû , ïðè êîòîðîé = f () äëÿ ëþáîãî; 2 B n , è ÷òî âåðîÿòíîñòü òàêîé ðåàëèçàöèè ðàâíà 2 2n .Îòñþäà ñëåäóåò, ÷òî äëÿ ëþáîãî ìíîæåñòâà Q; Q P2 (n),nîòíîøåíèå jQj =22 , òî åñòü äîëÿ òåõ ÔÀË f èç P2 (n), êîòîðûåïðèíàäëåæàò Q, ðàâíà âåðîÿòíîñòè òîãî, ÷òî ðåàëèçàöèÿñëó÷àéíîé âåëè÷èíû ïðèíàäëåæèò Q.Èç íåçàâèñèìîñòè ñëó÷àéíûõ âåëè÷èí ; 2 B n , âûòåêàåò,÷òî äëÿ èõ ñóììû e(n) = e, êîòîðàÿ ðàâíà ìîùíîñòè ìíîæåñòâàNf äëÿ ÔÀË f , ÿâëÿþùåéñÿ ðåàëèçàöèåé ñëó÷àéíîé âåëè÷èíû (n) = , â ñèëó (7.3) ñïðàâåäëèâû ðàâåíñòâà (ñì., íàïðèìåð,[4])Ee(n) = 2n 1;De(n) = 2n 2;(7.4)54Ãëàâà 1.ÏîëàãàÿlÄèçúþíêòèâíûå íîðìàëüíûå ôîðìûmI = 2n 1 t; 2n 1 + tt = n 22 ;nè ïðèìåíÿÿ ê ñëó÷àéíîé âåëè÷èíå e ñ ó÷åòîì (7.4) íåðàâåíñòâî×åáûøåâà [4], ïîëó÷èì, ÷òî âåðîÿòíîñòü ñîáûòèÿ e 2= I , òîåñòü äîëÿ òåõ ÔÀË f èç P2 (n), äëÿ êîòîðûõ jNf j 2= I , íåáîëüøå, ÷åìD 6 1t24n2è, ñëåäîâàòåëüíî, ñòðåìèòñÿ ê 0 ïðè n ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè.Ýòî îçíà÷àåò, â ÷àñòíîñòè, ÷òî äëÿ ïî÷òè âñåõ ÔÀË f èçP2 (n), âûïîëíåíî ðàâåíñòâîjNf j = 2n 1 1 O n 2 n=2(7.5)òî åñòü äëèíà ñîâåðøåííîé ÄÍÔ ó ïî÷òè âñåõ ÔÀË èç P2 (n)àñèìïòîòè÷åñêè ðàâíà 2n 1 .Ëåììà 7.2.íåðàâåíñòâàÄëÿ ïî÷òè âñåõ ÔÀË f , f 2 P2(n), âûïîëíÿþòñÿ3(f ) 6 2n 1 1 + O n 2 n=2 ;(7.6)43(f ) 6 n 2n 1 1 + O n 2 n=2 ;(7.7)4Äîêàçàòåëüñòâî.
Ïóñòü ÔÀË f , f 2 P2(n), ÿâëÿåòñÿ ðåàëèçàöèåéñëó÷àéíîé âåëè÷èíû . Äëÿ êàæäîãî íàáîðà , 2 B n 1 ,ðàññìîòðèì ñëó÷àéíóþ âåëè÷èíó = (0; ) _(1; ) . Çàìåòèì,÷òî ñëó÷àéíûå âåëè÷èíû , 2 B n 1 , íåçàâèñèìû, à ìàòåìàòè÷åñêîå3 ñîîòâåòñòâåííî.îæèäàíèå è äèñïåðñèÿ ëþáîé èç íèõ ðàâíû 43 è 16Çàìåòèì òàêæå, ÷òî ðàâåíñòâî = 1 âûïîëíÿåòñÿ òîãäà èòîëüêî òîãäà, êîãäà â ÄÍÔ Af , ïîñòðîåííîé ïî ëåììå 7.1äëÿ ÔÀË f , âõîäèò ñëàãàåìîå, ñîîòâåòñòâóþùåå íàáîðó .8.55Ìèíèìèçàöèÿ ÄÍÔÈç íåçàâèñèìîñòè ñëó÷àéíûõ âåëè÷èí , 2 B n 1 , ñëåäóåò,÷òî äëÿ èõ ñóììû e = e(n) âûïîëíÿþòñÿ ñîîòíîøåíèÿEe(n) = 43 2n 1;Ïîëàãàÿlt= nn22m;De(n) = 163 2n 1:3I = 2n 14(7.8)3t; 2n 1 + t4è ïðîâîäÿ íà îñíîâå (7.8) ðàññóæäåíèÿ àíàëîãè÷íûå òåì, ñïîìîùüþ êîòîðûõ èç ñîîòíîøåíèé (7.4) âûâîäèëîñü ðàâåíñòâîn(7.5), ïîëó÷èì, ÷òî (Af ) 2 I ó íå ìåíåå, ÷åì 22 1 n12ÔÀË f èç P2 (n).
Ýòî îçíà÷àåò, ÷òî äëÿ ïî÷òè âñåõ ÔÀË f ,f 2 P2 (n), äëèíà è ðàíã å¼ ÄÍÔ Af , ïîñòðîåííîé â ñîîòâåòñòâèèñ ëåììîé 7.1, óäîâëåòâîðÿåò (7.6), (7.7).Ëåììà äîêàçàíà.8Àëãîðèòìè÷åñêèå òðóäíîñòè ìèíèìèçàöèè ÄÍÔè îöåíêè ìàêñèìàëüíûõ çíà÷åíèé íåêîòîðûõñâÿçàííûõ ñ íåé ïàðàìåòðîâÈç ìîíîòîííîñòè ôóíêöèîíàëà äëÿ ñëîæíîñòè ÄÍÔ (ñì.7) ñëåäóåò, ÷òî -ìèíèìàëüíóþ ÄÍÔ âñåãäà ìîæíî âûáðàòüñðåäè òóïèêîâûõ ÄÍÔ, àëãîðèòì ïîñòðîåíèÿ êîòîðûõ îïèñàíâ 6. Îäíàêî, êàê ïîêàçûâàåò ñëåäóþùåå óòâåðæäåíèå, ÔÀËìîãóò èìåòü î÷åíü ìíîãî ðàçëè÷íûõ1 òóïèêîâûõ ÄÍÔ, èäàæå ÷èñëî ðàçëè÷íûõ ìèíèìàëüíûõ ÄÍÔ ó íèõ ìîæåòáûòü î÷åíü âåëèêî.×èñëî òóïèêîâûõ (ìèíèìàëüíûõ) ÄÍÔ ó ÔÀËèç P2 (n) ; n > 4, âèäàËåììà 8.1.ff (x1 ; : : : ; xn ) = g(x1 ; x2 ; x3 ) (x4 xn );1Âñå ÄÍÔ ðàññìàòðèâàþòñÿ ñ òî÷íîñòüþ äî ïåðåñòàíîâêè ÝÊ è áóêââ íèõ.56Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûãäå N g = f(000); (111)g, ðàâíî 52n 4 (ñîîòâåòñòâåííî 22n 4 ).Äîêàçàòåëüñòâî.
Èç ñâîéñòâ ëèíåéíîé ÔÀË è ñâîéñòâ ÔÀËg âûòåêàåò, ÷òî (ñì. 5) ëþáàÿ ïðîñòàÿ èìïëèêàíòà K ÔÀËf èìååò âèäK = Ki (x1 ; x2 ; x3 ) x4 4 xnn ;ãäå Ki , i = 1; : : : ; 6, ïðîñòàÿ èìïëèêàíòà ÔÀË g (ñì. ðèñ.2.1a è (3.5)) è 4 n = 1. Òàêèì îáðàçîì, ñîêðàùåííàÿÄÍÔ ÔÀË f ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ ñîñòîèò èç2n 4 öèêëîâ äëèíû 6 (ñì. 5).
Ñëåäîâàòåëüíî, ëþáàÿ òóïèêîâàÿ(ìèíèìàëüíàÿ) ÄÍÔ ÔÀË f âêëþ÷àåò â ñåáÿ îäíî èç ïÿòè(ñîîòâåòñòâåííî äâóõ) ðåáåðíûõ ïîêðûòèé, ñâÿçàííûõ ñ òóïèêîâûìè(ñîîòâåòñòâåííî ìèíèìàëüíûìè) ÄÍÔ ÔÀË g , ïðèâåäåííûìèâ (4.1)(4.2) (ñîîòâåòñòâåííî (4.1)), äëÿ êàæäîãî èç 2n 4óêàçàííûõ öèêëîâ. Ïîýòîìó ÷èñëî òóïèêîâûõ (ìèíèìàëüíûõ)n 4n 4ÄÍÔ ÔÀË f ðàâíî 52(ñîîòâåòñòâåííî 22 ).Ëåììà äîêàçàíà.Âàæíûì ïàðàìåòðîì, âëèÿþùèì íà ðàçìåð òàáëèöû Êâàéíàè, ñëåäîâàòåëüíî, íà òðóäîåìêîñòü çàäà÷è ìèíèìèçàöèè, ÿâëÿåòñÿäëèíà ñîêðàùåííîé ÄÍÔ. Óñòàíîâèì íåêîòîðûå íèæíèå îöåíêèäëèíû ñîêðàùåííîé ÄÍÔ ó ÔÀË îò n ÁÏ, ïîêàçûâàþùèå, â÷àñòíîñòè, ÷òî äëèíà ñîêðàùåííîé ÄÍÔ ìîæåò áûòü ñóùåñòâåííîáîëüøå äëèíû ñîâåðøåííîé ÄÍÔ òîé æå ÔÀË.Äëÿ I [0; n] ÷åðåç sIn (x1 ; : : : ; xn ) îáîçíà÷èì ÔÀË èçP2 (n), êîòîðàÿ ÿâëÿåòñÿ õàðàêòåðèñòè÷åñêîé ÔÀË îáúåäèíåíèÿâñåõ ñëîåâ êóáà B n ñ íîìåðàìè èç I .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
