OK-metodichka-2010-part1 (1132792), страница 7
Текст из файла (страница 7)
Ê ÷èñëó òàêèõ àëãîðèòìîâ îòíîñèòñÿ è ãðàäèåíòíûé àëãîðèòì, îðèåíòèðîâàííûé íà âûäåëåíèå èç çàäàííîãî ïîêðûòèÿ äîñòàòî÷íî ¾êîðîòêèõ¿ ïîäïîêðûòèé, èëè,èíà÷å, íà ïîñòðîåíèå äîñòàòî÷íî ¾êîðîòêèõ¿ ïîêðûòèé äëÿçàäàííîé ìàòðèöû. Íà êàæäîì øàãå ãðàäèåíòíîãî àëãîðèòìà â ìàòðèöå âûáèðàåòñÿ è âêëþ÷àåòñÿ â ïîêðûòèå òàêàÿñòðîêà, êîòîðàÿ ïîêðûâàåò íàèáîëüøåå ÷èñëî åùå íå ïîêðûòûõ ñòîëáöîâ (åñëè òàêèõ ñòðîê íåñêîëüêî, èç íèõ âûáèðàåòñÿ ñòðîêà ñ íàèìåíüøèì íîìåðîì).
Àëãîðèòì çàêàí÷èâàåòñâîþ ðàáîòó ïîñëå òîãî øàãà, íà êîòîðîì ïîëó÷èëîñü ïîêðûòèå.Ñëåäóþùåå óòâåðæäåíèå äàåò âåðõíþþ îöåíêó äëèíû6.45Ãðàäèåíòíûé àëãîðèòìïîêðûòèÿ, ïîëó÷àåìîãî ñ ïîìîùüþ ãðàäèåíòíîãî àëãîðèòìà äëÿ ìàòðèö ñ çàäàííîé ¾ãóñòîòîé¿.([6]) Ïóñòü äëÿ äåéñòâèòåëüíîãî γ, 0<γ 61,â êàæäîì ñòîëáöå ìàòðèöû M, M ∈ Bp,s, èìååòñÿ íåìåíüøå, ÷åì γ · p, åäèíèö. Òîãäà ïîêðûòèå ìàòðèöû M , ïîëó÷àåìîå ñ ïîìîùüþl ãðàäèåíòíîãîàëãîðèòìà, èìååò äëèm+11íó íå áîëüøå, ÷åì γ ln (γs) + γ .Äîêàçàòåëüñòâî. Ïóñòü äëÿ ïîñòðîåíèÿ ïîêðûòèÿ ìàòðèÒåîðåìà 6.1.1öû M ñ ïîìîùüþ ãðàäèåíòíîãî àëãîðèòìà ïîòðåáîâàëîñüñäåëàòü q øàãîâ, ïðè÷åì íà øàãå ñ íîìåðîì t, t ∈ [1, q], áûëà âûáðàíà ñòðîêà ñ íîìåðîì it .
Äëÿ êàæäîãî t, t ∈ [1, q),ðàññìîòðèì ìàòðèöó Mt , êîòîðàÿ ïîëó÷àåòñÿ èç ìàòðèöû Mâ ðåçóëüòàòå óäàëåíèÿ ñòðîê ñ íîìåðàìè {i1 , . . . , it }, à òàêæåïîêðûâàåìûõ èìè ñòîëáöîâ, è êîòîðàÿ ïðèíàäëåæèò ìíîæåñòâó B pt ,st , ãäå pt = p − t è st = s · δt , 0 6 δt 6 1. Äëÿ îïðåäåëåííîñòè áóäåì ñ÷èòàòü, ÷òî M0 = M, p0 = p, s0 = s, δ0 = 1è pq = p−q, sq = δq = 0.
Çàìåòèì, ÷òî ïðè ëþáîì t, t ∈ [0, q],ñïðàâåäëèâî íåðàâåíñòâî(6.1)q 6 t + δt · s,òàê êàê ïîñëå âûïîëíåíèÿ ïåðâûõ t øàãîâ àëãîðèòìà îñòàþòñÿ íå ïîêðûòûìè δt · s ñòîëáöîâ ìàòðèöû M , à íà êàæäîìñëåäóþùåì øàãå ïîêðûâàåòñÿ íå ìåíåå îäíîãî ñòîëáöà.Çàìåòèì, äàëåå, ÷òî â êàæäîì ñòîëáöå ìàòðèöû Mt , t ∈ [0, q),èìååòñÿ íå ìåíåå, ÷åì γ · p, åäèíèö è ïîýòîìó îáùåå ÷èñëîåäèíèö â ìàòðèöå Mt íå ìåíüøå, ÷åì γpsδt , à çíà÷èò ñðåäíåå ÷èñëî åäèíèö â åå ñòðîêàõ íå ìåíüøå, ÷åì γsδt . Îòñþäàâûòåêàåò, ÷òî ñòðîêà ìàòðèöû M ñ íîìåðîì it+1 , êîòîðàÿâûáèðàåòñÿ íà (t + 1)-ì øàãå àëãîðèòìà è ÿâëÿåòñÿ ñòðîêîé ìàòðèöû Mt ñ íàèáîëüøèì ÷èñëîì åäèíèö, ñîäåðæèò íå1Ïîëàãàåì, ÷òîln+ x = ln x,åñëèx > 1,èln+ x = 0,åñëè0 < x < 1.46Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûìåíüøå, ÷åì γsδt , åäèíèö, òî åñòü ïîêðûâàåò íå ìåíüøå, ÷åìγsδt , åùå íå ïîêðûòûõ ñòîëáöîâ ìàòðèöû M .
Òàêèì îáðàçîì, äëÿ ëþáîãî t, t ∈ [0, q), âûïîëíÿþòñÿ ñîîòíîøåíèÿsδt+1 = st+1 6 st − γsδt = sδt (1 − γ) ,èç êîòîðûõ, ñ ó÷åòîì δ0 = 1, ñëåäóåò, ÷òîδt 6 (1 − γ)t 6 e−γt(6.2)ïðè ëþáîì t, t ∈ [0, q).Âûáèðàÿ çíà÷åíèå ïàðàìåòðà t òàê, ÷òî1 +t=ln (γs) ,γïîäñòàâëÿÿ åãî â (6.2) è ó÷èòûâàÿ (6.2), ïîëó÷èìq6+1 +1 +1ln (γs) + s · e− ln (γs) 6ln (γs) + .γγγÒåîðåìà äîêàçàíà. êà÷åñòâå ïðèìåðà ïðèìåíåíèÿ ãðàäèåíòíîãî àëãîðèòìàðàññìîòðèì çàäà÷ó î ¾ïðîòûêàíèè¿ ãðàíåé êóáà åãî òî÷êàìè.
Çàäà÷à î ¾ïðîòûêàíèè¿ ñèñòåìû N, ñîñòîÿùåé èç ïîäìíîæåñòâ N1 , N2 , . . . , Np ìíîæåñòâà N = {α1 , . . . , αs }, çàêëþ÷àåòñÿ â íàõîæäåíèè òàêîãî ïîäìíîæåñòâà ìíîæåñòâàN, â êîòîðîì ïðè ëþáîì i, i ∈ [1, p], èìååòñÿ õîòÿ áû îäèíýëåìåíò èç Ni . Ýòà çàäà÷à ñâîäèòñÿ ê çàäà÷å î âûäåëåíèèïîäïîêðûòèÿ èç ïîêðûòèÿ îòðåçêà [1, p] åãî ïîäìíîæåñòâàìè I1 , . . . , Is , ãäå Ii = {j : αi ∈ Nj } ïðè âñåõ i, i ∈ [1, s].Çàìåòèì, ÷òî ìàòðèöà ïîñòðîåííîé òàêèì îáðàçîì ñèñòåìûïîäìíîæåñòâ îòðåçêà [1, p] ïîëó÷àåòñÿ èç ìàòðèöû ñèñòåìû(N, N) â ðåçóëüòàòå òðàíñïîíèðîâàíèÿ.7.Îöåíêè ïàðàìåòðîâ ÄÍÔ47Ïðè ëþáûõ íàòóðàëüíûõ n è m, m 6 n,â êóáå âñåãäà íàéäåòñÿ ïîäìíîæåñòâî ìîùíîñòè íå áîëåå, ÷åì n · 2m, ïðîòûêàþùåå âñå ãðàíè ðàíãà m.Äîêàçàòåëüñòâî.
Ïðèìåíÿÿ óêàçàííûé âûøå ïîäõîä, ðàñËåììà 6.1([18]).Bnñìîòðèì ìíîæåñòâî, ñîñòîÿùåå èç âñåõ ãðàíåé ðàíãà m Nn· 2m , à òàêæå ñèñòåìó N = {Nα }α∈B n åãîêóáà B n , |N| = mïîäìíîæåñòâ, ãäå Nα ìíîæåñòâî òåõ ãðàíåé èç N, êîòîðûå ïðîõîäÿò ÷åðåç òî÷êó α. Î÷åâèäíî, ÷òî êàæäàÿ ãðàíüèç N ñîäåðæèòñÿ â òåõ 2n−m ïîäìíîæåñòâàõ Nα , äëÿ êîòîðûõ òî÷êà α ïðèíàäëåæèò ýòîé ãðàíè. Ñëåäîâàòåëüíî, ìàòðèöà M ,ñâÿçàííàÿ ñ ïàðîé (N, N), ñîñòîèò èç p = 2n ñòðîênès= m· 2m ñòîëáöîâ, â êàæäîì èç êîòîðûõ èìååòñÿ p · γ ,−mãäå γ = 2 , åäèíèö. Èñêîìîå ìíîæåñòâî íàáîðîâ ïîëó÷àåòñÿ â ðåçóëüòàòå ïðèìåíåíèÿ ê ìàòðèöå M òåîðåìû 6.1 èïîñòðîåíèÿ ïîêðûòèÿ äëèíû q , ãäå nnmm+ 2 6 2 log+ 2m 6q 6 2 lnmm6 2m (n − 1) + 2m = n · 2m .m+Ëåììà äîêàçàíà.7Çàäà÷à ìèíèìèçàöèè ÄÍÔ.
Ïîâåäåíèå ôóíêöèé Øåííîíà è îöåíêè òèïè÷íûõ çíà÷åíèéäëÿ ðàíãà è äëèíû ÄÍÔÊàê óæå îòìå÷àëîñü, ÄÍÔ ïðåäñòàâëÿåò ñîáîé óäîáíóþ èíàãëÿäíóþ (ñ ¾ãåîìåòðè÷åñêîé¿ òî÷êè çðåíèÿ) ôîðìó çàäàíèÿ ÔÀË. Ñ äðóãîé ñòîðîíû, ÄÍÔ ìîæíî ðàññìàòðèâàòüêàê ïðîñòåéøóþ ìîäåëü, ïðåäíàçíà÷åííóþ äëÿ ñòðóêòóðíîéðåàëèçàöèè ÔÀË (ñì. ãë. 3).Çàìåòèì, ÷òî ðàçëè÷íûå ïàðàìåòðû ÄÍÔ (ðàíã, äëèíà è ò.
ï) õàðàêòåðèçóþò ðàçëè÷íûå48Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìû¾ìåðû¿ ñëîæíîñòè óêàçàííîãî ïðåäñòàâëåíèÿ èëè ñòðóêòóðíîé ðåàëèçàöèè.  ñâÿçè ñ ýòèì ÷àñòî âîçíèêàåò íåîáõîäèìîñòü ïîñòðîåíèÿ îïòèìàëüíîé â òîì èëè èíîì ñìûñëå ÄÍÔäëÿ çàäàííîé ÔÀË, òî åñòü íåîáõîäèìîñòü ðåøåíèÿ ñîîòâåòñòâóþùåé çàäà÷è, êîòîðàÿ ÿâëÿåòñÿ÷àñòíûì ñëó÷àåì çàäà÷è ñèíòåçà óïðàâëÿþùèõ ñèñòåì (ñì.ãë. 3). îáùåì âèäå çàäà÷à ìèíèìèçàöèè ÄÍÔ ìîæåò áûòüñôîðìóëèðîâàíà ñëåäóþùèì îáðàçîì. Ïóñòü äëÿ êàæäîéÄÍÔ A îïðåäåëåíà åå ¾ñëîæíîñòü¿ ψ (A), ψ (A) > 0, äëÿêîòîðîé ψ (A0 ) > ψ (A00 ), åñëè ÄÍÔ A00 ïîëó÷àåòñÿ èç ÄÍÔA0 óäàëåíèåì áóêâ èëè ÝÊ.  ýòîì ñëó÷àå áóäåì ãîâîðèòü,÷òî íà ìíîæåñòâå ÄÍÔ çàäàí íåîòðèöàòåëüíûéψ , îáëàäàþùèé ñâîéñòâîì.
Ïðèìåðàìè òàêèõ ôóíêöèîíàëîâ ìîãóò ñëóæèòü äëèíà λ (A),ðàíã R (A) èëè ¾ôîðìóëüíàÿ¿ ñëîæíîñòü L (A) ÄÍÔ A, àòàêæå ÷èñëî âõîæäåíèé ÁÏ ñ îòðèöàíèÿìè è äðóãèå ïàðàìåòðû ÄÍÔ. Çàäà÷à ìèíèìèçàöèè ÄÍÔ îòíîñèòåëüíî ôóíêöèîíàëà ñëîæíîñòè ψ ñîñòîèò â òîì, ÷òîáû ïî çàäàííîéÔÀË f ïîñòðîèòü ðåàëèçóþùóþ åå ÄÍÔ A òàêóþ, ÷òîψ (A) = min ψ A0 ,ìèíèìèçàöèè ÄÍÔôóíêöèîíàëìîíîòîííîñòèñëîæíîñòèãäå ìèíèìóì áåðåòñÿ ïî âñåì ÄÍÔ A0 , ðåàëèçóþùèì ÔÀË f .Ïðè ýòîì ÄÍÔ A ñ÷èòàåòñÿψ , èëè, èíà÷å, ψÄÍÔ, à çíà÷åíèå ψ (A) íàçûâàåòñÿfψ , èëè, èíà÷å, ψf â êëàññåÄÍÔ.  ñîîòâåòñòâèè ñ ââåäåííûìè ðàíåå îïðåäåëåíèÿìè,λ-ìèíèìàëüíóþ ÄÍÔ, òî åñòü ÄÍÔ ìèíèìàëüíóþ ïî äëèíå,áóäåì íàçûâàòü êðàò÷àéøåé, à R-ìèíèìàëüíóþ ÄÍÔ, òîåñòü ÄÍÔ ìèíèìàëüíóþ ïî ðàíãó, ïðîñòî ìèíèìàëüíîé.Ôóíêöèþψ (n) = max ψ (f ) ,ôóíêöèîíàëàôóíêöèîíàëàìèíèìàëüíîé îòíîñèòåëüíî-ìèíèìàëüíîéñëîæíîñòüþ ÔÀË îòíîñèòåëüíî-ñëîæíîñòüþ ÔÀËf ∈P2 (n)7.49Îöåíêè ïàðàìåòðîâ ÄÍÔêîòîðàÿ õàðàêòåðèçóåò ìàêñèìàëüíîå çíà÷åíèå ψ -ñëîæíîñòèÔÀË èç P2 (n), íàçûâàþò, îáû÷íî,äëÿêëàññà ÄÍÔ îòíîñèòåëüíî ôóíêöèîíàëà ψ .Óñòàíîâèì ïîâåäåíèå ôóíêöèé Øåííîíà λ(n) è R(n) äëÿäëèíû è ðàíãà ÄÍÔ ÔÀË èç P2 (n) ñîîòâåòñòâåííî.ôóíêöèåé ØåííîíàËåììà 7.1.íèÿÄëÿ ëþáîãî n, n ∈ 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 ) =xσ2 2 · · · xσnn · f x1 , σ 00(7.2)σ 00 =(σ2 ,...,σn )Ëåãêî âèäåòü, ÷òî ïîñëå çàìåíû â ðàçëîæåíèè (7.2) êàæäîéÔÀË f (x1 , σ 00 ) ðàâíîé åé ÔÀË èç ìíîæåñòâà {0, 1, x1 , x1 } èïðèâåäåíèÿ ïîäîáíûõ ìû ïîëó÷èì ÄÍÔ Af äëèíû íå áîëüøå, ÷åì 2n−1 , ÷òî äîêàçûâàåò âåðõíèå îöåíêè â (7.1).Ëåììà äîêàçàíà.Ïðè èçó÷åíèè òîãî èëè èíîãî ñâÿçàííîãî ñ ÄÍÔ ôóíêöèîíàëà ψ íàðÿäó ñ åãî ìàêñèìàëüíûì çíà÷åíèåì, òî åñòüôóíêöèåé Øåííîíà ψ (n), ïðåäñòàâëÿåò èíòåðåñ ñîîòâåòñòâóþùèé îòðåçîê "òèïè÷íûõ" çíà÷åíèé, òî åñòü îòðåçîê [ψ 0 (n) , ψ 00 (n)],â êîòîðûé ïîïàäàþò çíà÷åíèÿ ψ (f ) äëÿ ïî÷òè âñåõ ÔÀË fèç P2 (n). Åñëè ïðè ýòîì ãðàíèöû ψ 0 (n) è ψ 00 (n), ãäå n =1, 2, . .
., àñèìïòîòè÷åñêè ðàâíû ψ (n), òî ãîâîðÿò, ÷òî äëÿïàðàìåòðà ψ èìååò ìåñòî. Âûÿñíèì íåêîòîðûå îñîáåííîñòè ñòðîåíèÿ ÄÍÔ ó ïî÷òè âñåõ ÔÀË è óñòàíîâèì, â ÷àñòíîñòè, îòñóòñòâèå ýôôåêòà Øåííîíà äëÿ ïàðàìåòðîâ λ è R - äëèíû è ðàíãà ÄÍÔ ñîîòâåòñòâåííî.ýôôåêò Øåííîíà50Ãëàâà 1.Äèçúþíêòèâíûå íîðìàëüíûå ôîðìûÂâåäåì äèñêðåòíóþ âåêòîðíóþ ñëó÷àéíóþ âåëè÷èíó ξ (n) =ξe0 , . . . , ξe1 , ñîñòîÿùóþ èç 2n íåçàâèñèìûõ ñëó÷àéíûõ âåëè÷èí ξα , α ∈ B n , ïðèíèìàþùèõ çíà÷åíèÿ 0 è 1 ñ âåðîÿòíîñòüþ 12 . Ïðè ýòîì, î÷åâèäíî, äëÿ ëþáîãî α, α ∈ B n , âûïîëíÿþòñÿ ðàâåíñòâà1Eξα = ,21Dξα = ,4(7.3)ãäå Eθ è Dθ - ìàòåìàòè÷åñêîå îæèäàíèå è äèñïåðñèÿ ñëó÷àéíîé âåëè÷èíû θ (ñì., íàïðèìåð, [24]).Áóäåì ñ÷èòàòü, ÷òî ëþáàÿ ÔÀË f èç P2 (n) ÿâëÿåòñÿ ðåàëèçàöèåé âåëè÷èíû ξ , ïðè êîòîðîé ξα = f (α) äëÿ ëþáîãînα, α ∈ B n , è ÷òî âåðîÿòíîñòü òàêîé ðåàëèçàöèè ðàâíà 2−2 .Îòñþäà ñëåäóåò, ÷òî äëÿ ëþáîãî ìíîæåñòâà Q, Q ⊆ P2 (n),nîòíîøåíèå |Q| /22 , òî åñòü äîëÿ òåõ ÔÀË f èç P2 (n), êîòîðûå ïðèíàäëåæàò Q, ðàâíà âåðîÿòíîñòè òîãî, ÷òî ðåàëèçàöèÿ ñëó÷àéíîé âåëè÷èíû ξ ïðèíàäëåæèò Q.Èç íåçàâèñèìîñòè ñëó÷àéíûõ âåëè÷èí ξα , α ∈ B n , âûòåêàåò, ÷òî äëÿ èõ ñóììû ξe(n) = ξe, êîòîðàÿ ðàâíà ìîùíîñòèìíîæåñòâà Nf äëÿ ÔÀË f , ÿâëÿþùåéñÿ ðåàëèçàöèåé ñëó÷àéíîé âåëè÷èíû ξ (n) = ξ , â ñèëó (7.3) ñïðàâåäëèâû ðàâåíñòâà(ñì., íàïðèìåð, [4])Eξe(n) = 2n−1 ,(7.4)Dξe(n) = 2n−2 ,Ïîëàãàÿlmnt = n · 22 ,I = 2n−1 − t, 2n−1 + tè ïðèìåíÿÿ ê ñëó÷àéíîé âåëè÷èíå ξe ñ ó÷åòîì (7.4) íåðàâåíñòâî ×åáûøåâà [4], ïîëó÷èì, ÷òî âåðîÿòíîñòü ñîáûòèÿ ξe ∈/ I,òî åñòü äîëÿ òåõ ÔÀË f èç P2 (n), äëÿ êîòîðûõ |Nf | ∈/ I , íåáîëüøå, ÷åìDη16 22t4n7.51Îöåíêè ïàðàìåòðîâ ÄÍÔè, ñëåäîâàòåëüíî, ñòðåìèòñÿ ê 0 ïðè n ñòðåìÿùåìñÿ ê áåñêîíå÷íîñòè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
