В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 7
Текст из файла (страница 7)
Äîêàæåì, ÷òîL(N ) = O(N log N ).Ïóñòü α̃ = (γ̃, αn ), β̃ = (δ̃, βn ). Òîãäà__Rn (α̃, β̃)uα̃ vβ̃ =Rn−1 (γ̃, δ̃)R(αn , βn )u(γ̃,αn ) v(δ̃,βn ) =α̃,β̃α̃=(γ̃,αn ),β̃=(δ̃,βn )=_ _=_Rn−1 (γ̃, δ̃)R(αn , βn )u(γ̃,αn ) v(δ̃,βn ) =γ̃,δ̃ αn ,βnRn−1(γ̃, δ̃)R(αn , βn )u(γ̃,αn ) v(δ̃,βn ) =αn ,βnγ̃,δ̃=__Rn−1(γ̃, δ̃)_u(γ̃,αn )αnγ̃,δ̃=_v(δ̃,βn ) =βn :R(αn ,βn )__( Rn−1 (γ̃, δ̃)u(γ̃,αn ) w(δ̃,αn ) ),αn γ̃,δ̃ãäå w(δ̃,αn ) = βn :R(αn ,βn ) v(δ̃,βn ) .Îòñþäà L0 (n) 6 kL0 (n − 1) + k n (k − 1) + k − 1, ïîñêîëüêó çàäà÷à äëÿn ñâîäèòñÿ ê k òàêèì æå çàäà÷àì äëÿ n − 1, ïðè ýòîì äëÿ âû÷èñëåíèÿêàæäîé èç k n ïåðåìåííûõ w òðåáóåòñÿ íå áîëåå k −1 äèçúþíêöèé è ïîñëåðåøåíèÿ âñåõ k ïîäçàäà÷ òðåáóåòñÿ k − 1 äèçúþíêöèé äëÿ âû÷èñëåíèÿäèçúþíêöèè ïî αn .
Ïåðåõîäÿ ê L(N ), ïîëó÷àåì L(N ) 6 kL( Nk ) + O(N ),îòêóäà, ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå, L(N ) = O(N log N ).Òåîðåìà äîêàçàíà.W3.5. ÊëàññûFmÏóñòü òåïåðü R(y1 , . . . , ym ) m-ìåñòíûé ïðåäèêàò íà ìíîæåñòâåEk = {0, 1, . . . , k−1}. Åñëè α̃j = (α1j , α2j , . . . , αnj ), j = 1, 2, .
. . , m íàáîðûñ ýëåìåíòàìè èç Ek , òî îïðåäåëèìRn (α̃1 , α̃2 , . . . , α̃m ) ≡ ∀iR(αi1 , αi2 , . . . , αim ).29Áóäåì ãîâîðèòü, ÷òî ôóíêöèÿ f (x1 , . . . , xn ) èç Pkñîõðàíÿåò R, åñëè äëÿ ëþáûõ m íàáîðîâ α̃1 , α̃2 , . . . , α̃m âûïîëíÿåòñÿèìïëèêàöèÿÎïðåäåëåíèå.Rn (α̃1 , α̃2 , . . . , α̃m ) =⇒ R(f (α̃1 ), f (α̃2 ), . . . , f (α̃m )).(3.1)Ðàññìîòðèì ñëåäóþùèé ïðåäèêàò Rm íà E2 = {0, 1}:(èñòèíà ⇐⇒ ∃i(yi = 0),Rm (y1 , . . . , ym ) =ëîæü⇐⇒ ỹ = (1, .
. . , 1).Êëàññ âñåõ ôóíêöèé àëãåáðû ëîãèêè, ñîõðàíÿþùèõ ïðåäèêàò Rm ,îáîçíà÷èì F m . Êëàññû F m ïðè m = 2, 3, 4, . . . îáðàçóþò îäíó èç 8áåñêîíå÷íûõ öåïî÷åê çàìêíóòûõ êëàññîâ â àëãåáðå ëîãèêè. Ðàññìîòðèìñëåäóþùóþ çàäà÷ó.Çàäà÷à. Ïóñòü m > 2 ôèêñèðîâàííîå íàòóðàëüíîå ÷èñëî. Òðåáóåòñÿ ïîñòðîèòü àëãîðèòì äëÿ îòâåòà íà âîïðîñ f (x1 , .
. . , xn ) ∈ F m ?ïðè óñëîâèè, ÷òî ôóíêöèÿ ïîñòóïàåò íà âõîä â âèäå âåêòîðà çíà÷åíèéf (x1 , . . . , xn ) = (a0 , a1 , . . . , a2n −1 ) äëèíû N = 2n .Çàìåòèì, ÷òî òðèâèàëüíûé àëãîðèòì, îñíîâàííûé íà ïðîñìîòðåâñåõ âûáîðîê ïî m çíà÷åíèé ôóíêöèè è ïðîâåðêå èìïëèêàöèè (3.1)òðåáóåò ïî ïîðÿäêó íå ìåíåå N m îïåðàöèé. Îäíàêî çäåñü îïÿòü ìîæíî ïðèìåíèòü ìåòîä ïåðåõîäà îò çàäà÷è ðàñïîçíàâàíèÿ ê âû÷èñëåíèþàëãåáðàè÷åñêîãî âûðàæåíèÿ, ÷òîáû èñïîëüçîâàòü ñèëó àëãåáðû [1].Òåîðåìà 3.6. Äëÿ ëþáîãî ôèêñèðîâàííîãîàëãîðèòì äëÿ îòâåòà íà âîïðîñ3ñëîæíîñòüþ O(N log N ).m > 2 ñóùåñòâóåò f (x1 .
. . xn ) ∈ U (Rm )? ñ áèòîâîéÊîíñòàíòà çàâèñèò îò m (ðàñòåò ñ ðîñòîì m).Äîêàçàòåëüñòâî. Ïóñòü α̃1 , α̃2 , . . . , α̃m ïðîèçâîëüíûå íàáîðû, ãäåα̃j = (α1j , α2j , . . . , αnj ), è ïóñòü qα̃ äëÿ ïðîèçâîëüíîãî íàáîðà α̃ îáîçíà÷àåòòàêóþ ëîãè÷åñêóþ ïåðåìåííóþ, ÷òî qα̃ = èñòèíà òîãäà è òîëüêî òîãäà,êîãäà f (α̃) = 1. Òîãäà ïî îïðåäåëåíèþÇàìå÷àíèå.f (x1 , . . . , xn ) ∈/ Fm ⇐⇒n⇐⇒ ∃α̃1 , .
. . , α̃m (Rm(α̃1 , . . . , α̃m )&(f (α̃1 ) = 1)& . . . &(f (α̃m ) = 1)) ⇐⇒_n⇐⇒Rm(α̃1 , . . . , α̃m )qα̃1 · . . . · qα̃m =α̃1 ,...,α̃m=_Rm (α11 . . . α1m ) · Rm (α21 . . . α2m ) · . . . · Rm (αn1 . . . αnm )qα̃1 · . . . · qα̃m .α̃1 ,...,α̃m30Îïðåäåëèì ôóíêöèþ tm (α1 , . . . , αm ), ãäå αj ∈ {0, 1}, è ïåðåìåííûå uαñëåäóþùèì îáðàçîì:tm (α1 , . .
. , αm ) =(0,åñëè R̄m (α1 , . . . , αm ),1,åñëè Rm (α1 , . . . , αm ).(0,uα =1,åñëè qα = ëîæü,åñëè qα = èñòèíà.Ëåãêî âèäåòü, ÷òî_Rm (α11 , . . . , α1m ) · . . . · Rm (αn1 , . . . , αnm )qα̃1 · . . . · qα̃m = èñòèíà ⇐⇒α̃1 ,...,α̃mXTn =tm (α11 , . . . , α1m ) · . .
. · tm (αn1 , . . . , αnm )uα̃1 · . . . · uα̃m > 0.α̃1 ,...,α̃mÏóñòü L0ap (n) = Lap (N ) íàèìåíüøåå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé, íåîáõîäèìûõ äëÿ âû÷èñëåíèÿ Tn . Îáîçíà÷èì β̃j =j(α1j , α2j , . . . , αn−1), γj = αnj è1m1mtn−1m (β̃1 , . . . , β̃m ) = tm (α1 , . . . , α1 ) · . . . · tm (αn−1 , . . . , αn−1 ).ÒîãäàTn =XXtm (α11 , . . . , α1m ) · .
. . · tm (αn1 , . . . , αnm ) · uβ̃1 ,γ1 · . . . · uβ̃m ,γm =β̃1 ,...,β̃m γ1 ,...,γm=XX=Xtn−1m (β̃1 , . . . , β̃m )uβ̃1 ,γ1 · . . . · uβ̃m ,γm =(γ1 ,...,γm )6=(1,...,1)β̃1 ,...,β̃mXtm (γ1 , . . . , γm )uβ̃1 ,γ1 · . . . · uβ̃m ,γm =(γ1 ,...,γm )∈E2mβ̃1 ,...,β̃m=Xtn−1m (β̃1 , . . . , β̃m )tn−1m (β̃1 , .
. . , β̃m )((uβ̃1 ,0 + uβ̃1 ,1 )(uβ̃2 ,0 + uβ̃2 ,1 ) · . . . · (uβ̃m ,0 + uβ̃m ,1 )−β̃1 ,...,β̃m−uβ̃1 ,1 uβ̃2 ,1 · . . . · uβ̃m ,1 ) =Xtn−1m (β̃1 , . . . , β̃m )vβ̃1 vβ̃2 · . . . · vβ̃m −β̃1 ,...,β̃m−Xn−1tm(β̃1 , . . . , β̃m )wβ̃1 wβ̃2 · . . . · wβ̃m ,β̃1 ,...,β̃mãäå vβ̃ = uβ̃,0 + uβ̃,1 , à wβ̃ = uβ̃,1 .Ñâåëè çàäà÷ó ñ ïàðàìåòðîì n ê 2 òàêèì æå ïîäçàäà÷àì ñ ïàðàìåòðîì n − 1. Îòñþäà L0ap (n) 6 2L0ap (n − 1) + 2n−1 + 1, ïîñêîëüêóäëÿ âû÷èñëåíèÿ âñåõ vβ̃ äîñòàòî÷íî 2n−1 ñëîæåíèé è îäíîãî âû÷èòàíèÿ31äîñòàòî÷íî äëÿ âû÷èñëåíèÿ Tn ïîñëå ðåøåíèÿ äâóõ ïîäçàäà÷.
Ïåðåõîäÿê N , èìååì L0ap (N ) = 2Lap ( N2 ) + O(N ). Îòñþäà ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå ïîëó÷àåì Lap (N ) = O(N log N ) (â ýòîé òåîðåìåèìååì a = 2, c = 2, α = 1). Îòìåòèì, ÷òî èñõîäíàÿ çàäà÷à áûëà äëÿuα̃ ∈ {0, 1}. Îäíàêî â ïîäçàäà÷àõ ïåðåìåííûå ìîãóò áûòü ïðîèçâîëüíûìè íàòóðàëüíûìè ÷èñëàìè. Ïåðåõîä ê ïîäçàäà÷àì äåëàåòñÿ n − 1 ðàç.Ïðè êàæäîì ïåðåõîäå ðàçðÿäíîñòü ïåðåìåííûõ óâåëè÷èâàåòñÿ íå áîëåå,÷åì íà 1, ïîýòîìó â ïîäçàäà÷àõ âñå ÷èñëà èìåþò äëèíó íå áîëåå n+1.
Ïðèn = 0 ïîëó÷àþòñÿ ïîäçàäà÷è âû÷èñëåíèÿ T0 âèäà T0 = z·z·z·z·. . .·z = z m ,â êîòîðûõ îáðàçóþòñÿ ÷èñëà äëèíû 6 m(n + 1). Ïðè ïåðåõîäå ê çàäà÷åèç ïîäçàäà÷ äëèíà ÷èñåë óâåëè÷èâàåòñÿ íå áîëåå, ÷åì íà 1, ïîýòîìó âñå÷èñëà â àëãîðèòìå èìåþò äëèíó íå áîëåå m(n + 1) + n 6 const · n. Ñëåäîâàòåëüíî, êàæäàÿ àðèôìåòè÷åñêàÿ îïåðàöèÿ òðåáóåò O(n2 ) = O(log2 N )áèòîâûõ îïåðàöèé, îòêóäà L(N ) = Lap (N ) · O(log2 N ) = O(N log3 N ).Òåîðåìà äîêàçàíà.324. Îáùàÿ òåîðèÿ ñëîæíîñòè çàäà÷Åñëè ìû õîòèì ïîëó÷àòü óòâåðæäåíèÿ òèïà äëÿ ëþáûõ àëãîðèòìîâ, òî ìû äîëæíû ïðèíÿòü êàêóþ-íèáóäü óíèâåðñàëüíóþ ìîäåëüàëãîðèòìîâ.
Îäíîé èç òàêèõ ìîäåëåé ÿâëÿåòñÿ ìàøèíà Òüþðèíãà.4.1. Ìàøèíû ÒüþðèíãàÌàøèíà Òüþðèíãà M èìååò ïîòåíöèàëüíî áåñêîíå÷íóþ ëåíòó, ðàçäåëåííóþ íà ÿ÷åéêè, è ãîëîâêó, êîòîðàÿ â êàæäûé (äèñêðåòíûé) ìîìåíòâðåìåíè t = 0, 1, 2, . . . îáîçðåâàåò ðîâíî îäíó ÿ÷åéêó. Çàäàíî íåêîòîðîåêîíå÷íîå ìíîæåñòâî ñîñòîÿíèé Q = {q0 , q1 , . . . , ql }, è ìàøèíà â êàæäûéìîìåíò âðåìåíè íàõîäèòñÿ ðîâíî â 1 èç ýòèõ ñîñòîÿíèé. Çàäàí êîíå÷íûéëåíòî÷íûé (ðàáî÷èé) àëôàâèò C = {c0 , c1 , . . . , cm }, ãäå c0 = Λ ïóñòîéñèìâîë, è â êàæäûé ìîìåíò âðåìåíè â êàæäîé ÿ÷åéêå íàõîäèòñÿ ðîâíî 1ñèìâîë èç àëôàâèòà C , ïðè÷åì áóäåì ñ÷èòàòü, ÷òî ñèìâîëû, îòëè÷íûå îòΛ, íàõîäÿòñÿ ëèøü â êîíå÷íîì ÷èñëå ÿ÷ååê.
Ìàøèíà M õàðàêòåðèçóåòñÿåå ïðîãðàììîé, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé êîíå÷íûé íàáîð êîìàíäâèäà: ci qj → ck qr T , ãäå ci ∈ C , ck ∈ C , qj ∈ Q, qr ∈ Q, T ∈ {L, R, S}. Íàêàæäîì òàêòå ìàøèíà M ðàáîòàåò ñëåäóþùèì îáðàçîì. Åñëè ãîëîâêàîáîçðåâàåò ÿ÷åéêó, â êîòîðîé íàõîäèòñÿ ñèìâîë ci , M íàõîäèòñÿ â ñîñòîÿíèè qj è â ïðîãðàììå ìàøèíû M åñòü êîìàíäà ci qj → ck qr T , òî ñèìâîëâ îáîçðåâàåìîé ÿ÷åéêå çàìåíÿåòñÿ íà ck , ìàøèíà ïåðåõîäèò â ñîñòîÿíèåqr è ãîëîâêà îñòàåòñÿ íà ìåñòå, åñëè T = S , èëè ñäâèãàåòñÿ íà 1 ÿ÷åéêóâïðàâî èëè âëåâî, åñëè T = R èëè T = L. Äàëåå ìàøèíà ïåðåõîäèòê ñëåäóþùåìó òàêòó è ïîâòîðÿåò ýòîò ïðîöåññ.
Åñëè æå â ïðîãðàììåìàøèíû íåò êîìàíäû, â ëåâîé ÷àñòè êîòîðîé ñòîèò ïàðà ci qj , òî ìàøèíàîñòàíàâëèâàåòñÿ.Ìû áóäåì ðàññìàòðèâàòü òîëüêî äåòåðìèíèðîâàííûå ìàøèíû Òüþðèíãà, òî åñòü òàêèå, ó êîòîðûõ â ïðîãðàììå êàæäàÿ ïàðà ci qj âñòðå÷àåòñÿ â ëåâûõ ÷àñòÿõ êîìàíä íå áîëåå îäíîãî ðàçà.  ýòîì ñëó÷àå êàæäûéøàã ìàøèíû îïðåäåëÿåòñÿ îäíîçíà÷íî.Îïðåäåëåíèå.
Åñëè A àëôàâèò, òî ÷åðåç A∗ áóäåì îáîçíà÷àòüìíîæåñòâî âñåõ (êîíå÷íûõ) ñëîâ â àëôàâèòå A. Ïóñòü C ëåíòî÷íûéàëôàâèò ìàøèíû M , C0 = C \ {Λ} è ïóñòü çàäàí íåêîòîðûé âõîäíîéàëôàâèò A, òàêîé, ÷òî A ⊆ C0 . Òîãäà ìû áóäåì ñ÷èòàòü, ÷òî ìàøèíà Mîñóùåñòâëÿåò ïðåîáðàçîâàíèå ϕM : A∗ → C0∗ ∪ {∗}, êîòîðîå îïðåäåëÿåòñÿñëåäóþùèì îáðàçîì (çäåñü ∗ â {∗} òðàêòóåòñÿ êàê íåîïðåäåëåííîñòü).Ïóñòü çàäàíî íåêîòîðîå ñëîâî ā = a1 a2 . . . an ∈ A∗ . Ðàçìåñòèì ñèìâîëûýòîãî ñëîâà â ïîñëåäîâàòåëüíûå ÿ÷åéêè ëåíòû, à â îñòàëüíûå ÿ÷åéêè33ïîìåñòèì Λ, ïîìåñòèì ãîëîâêó íà ÿ÷åéêó, â êîòîðîé ñòîèò a1 , óñòàíîâèì ìàøèíó â íà÷àëüíîå ñîñòîÿíèå q1 è íà÷íåì ðàáîòó ìàøèíû.
Åñëèïîñëå ýòîãî ìàøèíà M áóäåò ðàáîòàòü áåñêîíå÷íî äîëãî, òî ñ÷èòàåì,÷òî ϕM (a1 a2 . . . an ) = ∗. Åñëè ìàøèíà M îñòàíîâèòñÿ è íà ëåíòå âñåñèìâîëû ðàâíû Λ èëè ìåæäó ñèìâîëàìè àëôàâèòà C0 áóäåò âñòðå÷àòüñÿΛ, òî òàêæå ϕM (a1 a2 . . . an ) = ∗. Åñëè æå ïîñëå îñòàíîâêè ìàøèíû Mâñå ñèìâîëû àëôàâèòà C0 íà ëåíòå ñòîÿò ïîäðÿä, îáðàçóÿ ñëîâî b̄, òîϕM (ā) = b̄.Òåçèñ Òüþðèíãà. Äëÿ ëþáîãî àëãîðèòìè÷åñêîãî ïðåîáðàçîâàíèÿ∗ϕ : A → C0∗ ∪ {∗} ñóùåñòâóåòïðåîáðàçîâàíèå ϕ.ìàøèíà ÒüþðèíãàM,îñóùåñòâëÿþùàÿ4.2.
Ñóùåñòâîâàíèå ñëîæíûõ çàäà÷Ðàññìîòðèì âñå ìàøèíû Òüþðèíãà, èìåþùèå â ëåíòî÷íîì àëôàâèòå ñèìâîëû Λ è |. Ïóñòü Z + = {0} ∪ N , ãäå N ìíîæåñòâî íàòóðàëüíûõ÷èñåë. Áóäåì ïðåäñòàâëÿòü ÷èñëî k ∈ Z + íà ëåíòå ìàøèíû â âèäå êîäàΛ || . . . | Λ, ãäå êîëè÷åñòâî | ðàâíî k + 1 (îñòàëüíûå ñèìâîëû íà ëåíòå Λ).Íàáîð (k1 , k2 , . . . , kn ) áóäåì ïðåäñòàâëÿòü â âèäå êîäà Λ || . . . | Λ || . . . |Λ . .
. Λ || . . . | Λ,ãäå â ïåðâîì ìàññèâå k1 + 1 ñèìâîëîâ |, âî âòîðîì k2 + 1è ò.ä. Ïðèìåíÿÿ ìàøèíó M ê êîäó ÷èñëà èëè íàáîðà, áóäåì ïîìåùàòüãîëîâêó íà ñàìûé ïåðâûé ñèìâîë | è óñòàíàâëèâàòü ìàøèíó M â ååíà÷àëüíîå ñîñòîÿíèå q1 .Îïðåäåëåíèå. Äëÿ ëþáîé ìàøèíû Òüþðèíãà M è ëþáîãî íàòóðàëüíîãî ÷èñëà n áóäåì ñ÷èòàòü, ÷òî ìàøèíà M âû÷èñëÿåò ôóíêöèþf (x1 , x2 , . . . , xn ) : (Z + )n → Z + ∪ {∗} êîòîðàÿ îïðåäåëÿåòñÿ ñëåäóþùèìîáðàçîì. Ïðèìåíèì ìàøèíó M ê êîäó íàáîðà (a1 , a2 , . . .
, an ). Åñëè Mîñòàíîâèòñÿ è ïîñëå îñòàíîâêè íà ëåíòå áóäåò òîëüêî êîä íåêîòîðîãî÷èñëà b ∈ Z + , òî f (a1 , a2 , . . . , an ) = b. Âî âñåõ îñòàëüíûõ ñëó÷àÿõf (a1 , a2 , . . . , an ) = ∗ (íåîïðåäåëåííîñòü).Îïðåäåëåíèå. Ôóíêöèÿ f (x1 , x2 , . . . , xn ) : (Z + )n → Z + ∪ {∗}íàçûâàåòñÿ âû÷èñëèìîé, åñëè ñóùåñòâóåò ìàøèíà Òüþðèíãà M , êîòîðàÿåå âû÷èñëÿåò.Îïðåäåëåíèå. Ãîâîðÿò, ÷òî ìàøèíà M ïðàâèëüíî âû÷èñëÿåò ôóíêöèþ f (x1 , x2 , . . . , xn ), åñëè, íà÷èíàÿ ðàáîòó ñ êîäà íàáîðà(a1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
