В.Б. Алексеев - Введение в теорию сложности алгоритмов, страница 5

Âàæíûìïðèìåðîì ðàñøèðåíèÿ ìîäåëè ÿâëÿåòñÿ ðàçâèòèå ïîíÿòèÿ ÷èñëà: íàòóðàëüíûå äðîáíûå öåëûå ðàöèîíàëüíûå äåéñòâèòåëüíûå êîìïëåêñíûå. Âûõîä â áîëåå øèðîêóþ ìîäåëü ïîçâîëÿåò áîëåå êîìïàêòíîîïèñûâàòü àëãîðèòìû è çà ñ÷åò ýòîãî íàõîäèòü áîëåå áûñòðûå àëãîðèòìûäëÿ èñõîäíîé ìîäåëè. Ïðèìåðîì ìîæåò ñëóæèòü àëãîðèòì Òîîìà, ãäå îòóìíîæåíèÿ ÷èñåë ìû ïåðåõîäèì ê óìíîæåíèþ ìíîãî÷ëåíîâ è èñïîëüçóåìâîçìîæíîñòü èíòåðïîëÿöèè ìíîãî÷ëåíîâ.  ðàçäåëàõ 3.1-3.2 è 3.4-3.5 ìûðàññìîòðèì äðóãèå ïðèìåðû ïðèìåíåíèÿ èäåè ðàñøèðåíèÿ ìîäåëè.3.1. Àëãîðèòìû óìíîæåíèÿ 0-1-ìàòðèöÏóñòü ìàòðèöû A è B ñîñòîÿò òîëüêî èç 0 è 1 è òðåáóåòñÿ âû÷èñëèòüC = A · B, ãäå âñå ýëåìåíòû crs äîëæíû áûòü ïðåäñòàâëåíû â äâîè÷íîéñèñòåìå.

 êà÷åñòâå îïåðàöèé ðàçðåøèì òîëüêî ëþáûå áèòîâûå îïåðàöèèíàä äâóìÿ ïåðåìåííûìè.Òåîðåìà3.1. Äëÿ âû÷èñëåíèÿ (îáû÷íîãî) ïðîèçâåäåíèÿ äâóõ0-1-ìàòðèö ïîðÿäêà n ñóùåñòâóåò àëãîðèòì ñ ÷èñëîì áèòîâûõ îïå2log 7ðàöèé O(n 2 log n).Ëåììà 3.1. Åñëè â èñõîäíûõ ìàòðèöàõýëåìåíòû èìåþò äâîè÷íóþ äëèíó íå áîëååkAèBïîðÿäêànâñå(âêëþ÷àÿ çíàê), òî â àëãî-AB âñå âîçíèêàþùèå ÷èñëà èìåþòäâîè÷íóþ äëèíó íå áîëåå 2k + 4dlog2 ne.Äîêàçàòåëüñòâî ëåììû. Ïðè ôîðìèðîâàíèè ïîäçàäà÷ âû÷èñëåíèÿD1 − D7 â àëãîðèòìå Øòðàññåíà ïðîèñõîäèò ñëîæåíèå (èëè âû÷èòàíèå)íå áîëåå ÷åì äâóõ ìàòðèö. Ïîýòîìó ìîäóëè âñåõ ÷èñåë íå áîëåå ÷åìóäâàèâàþòñÿ, òî åñòü äîáàâëÿåòñÿ íå áîëåå îäíîãî ðàçðÿäà.

Ïðè ïåðåõîäåîò ðàçìåðíîñòè n ê ðàçìåðíîñòè 1 ïîäçàäà÷è ôîðìèðóþòñÿ dlog2 ne ðàç.Ñëåäîâàòåëüíî, â ïîäçàäà÷àõ ðàçìåðíîñòè 1 âñå ÷èñëà èìåþò äëèíó íåáîëåå k + dlog2 ne. Äëÿ ïîäçàäà÷ ðàçìåðíîñòè 1 àëãîðèòì Øòðàññåíàïðîèçâîäèò îáû÷íîå óìíîæåíèå. Ïðè ýòîì äëèíà ïîëó÷àþùèõñÿ ÷èñåë íåïðåâîñõîäèò 2k +2dlog2 ne. Ïðè âû÷èñëåíèè Crs ïî ðåçóëüòàòàì ïîäçàäà÷D1 − D7 ñêëàäûâàþòñÿ (âû÷èòàþòñÿ) íå áîëåå ÷åì ïî 4 ìàòðèöû. Ïðèýòîì ìàêñèìàëüíûå ìîäóëè ÷èñåë âîçðàñòàþò íå áîëåå ÷åì â 4 ðàçà,òî åñòü äîáàâëÿåòñÿ íå áîëåå ÷åì ïî 2 ðàçðÿäà. Ïîñêîëüêó îáðàòíûõøàãîâ òàêæå dlog2 ne, òî âñå ïîëó÷àåìûå ÷èñëà èìåþò äëèíó íå áîëåå2k + 2dlog2 ne + 2dlog2 ne = 2k + 4dlog2 ne.

Ëåììà äîêàçàíà.ðèòìå Øòðàññåíà äëÿ âû÷èñëåíèÿ22Ïðèìåíèì äëÿ âû÷èñëåíèÿ AB àëãîðèòì Øòðàññåíà. Ïî óñëîâèþ â èñõîäíûõ ìàòðèöàõ A è B âñå ýëåìåíòûèìåþò äëèíó 2 (âêëþ÷àÿ çíàê). Òîãäà ïî ëåììå âñå âîçíèêàþùèå âàëãîðèòìå ÷èñëà áóäóò èìåòü äëèíó íå áîëåå 4+4dlog2 ne = O(log n). Òàêêàê â àëãîðèòìå Øòðàññåíà èñïîëüçóþòñÿ òîëüêî ñëîæåíèå, âû÷èòàíèå èóìíîæåíèå, òî ëþáàÿ àðèôìåòè÷åñêàÿ îïåðàöèÿ â àëãîðèòìå Øòðàññåíàòðåáóåò O(log2 n) áèòîâûõ îïåðàöèé.

Ïîñêîëüêó àëãîðèòì Øòðàññåíàèñïîëüçóåò O(nlog2 7 ) àðèôìåòè÷åñêèõ îïåðàöèé, òî âñå îíè ïîòðåáóþòO(nlog2 7 log2 n) áèòîâûõ îïåðàöèé. Òåîðåìà äîêàçàíà.Çàìå÷àíèå 1. Îöåíêó ìîæíî óëó÷øèòü, åñëè èñïîëüçîâàòü áûñòðûå àëãîðèòìû äëÿ óìíîæåíèÿ ÷èñåë.Çàìå÷àíèå 2.  ýòîé òåîðåìå ìîæíî ïîëó÷èòü îöåíêó O(n2.38 ), åñëè èñïîëüçîâàòü èçâåñòíûé áîëåå áûñòðûé àëãîðèòì óìíîæåíèÿ ìàòðèö.Ðàññìîòðèì òåïåðü îïåðàöèþ áóëåâñêîãî óìíîæåíèÿ 0-1-ìàòðèö.Äîêàçàòåëüñòâî òåîðåìû.A = kaij k è B = kbkl k äâå 0-1-ìàòðèöûïðîèçâåäåíèåì A ◦ B íàçûâàåòñÿ ìàòðèöà D =Îïðåäåëåíèå.

Ïóñòüïîðÿäêàkdrs kn.Áóëåâñêèìòàêàÿ, ÷òîdrs =n_arp · bpsp=1r è s.Äëÿ áóëåâñêîãî óìíîæåíèÿ ìàòðèö íåëüçÿ íåïîñðåäñòâåííî ïðèìåíèòü èäåþ Øòðàññåíà, òàê êàê â àëãîðèòìå Øòðàññåíà åñòü âû÷èòàíèå,à ó äèçúþíêöèè íåò îáðàòíîé îïåðàöèè. Íåñìîòðÿ íà ýòî, ñïðàâåäëèâàñëåäóþùàÿ òåîðåìà.Òåîðåìà 3.2. Áóëåâñêîå ïðîèçâåäåíèå D = A ◦ B äâóõ 0-1-ìàòðèöA è B ïîðÿäêà n ìîæíî âû÷èñëèòü ñ ÷èñëîì áèòîâûõ îïåðàöèéO(nlog2 7 log2 n).Äîêàçàòåëüñòâî. Ìû îïèøåì ñîîòâåòñòâóþùèé àëãîðèòì, êîòîðûé îñíîâàí íà èäåå ðàñøèðåíèÿ ìîäåëè. Âìåñòî âû÷èñëåíèÿ D = A◦Bìû âû÷èñëèì ñíà÷àëà îáû÷íîå ïðîèçâåäåíèå C = AB .

Ïðè ýòîì îòìåòèìñëåäóþùóþ ñâÿçü ìåæäó D è C :äëÿ âñåõdrs = 1 ⇐⇒ crs > 0.Ïî ïðåäûäóùåé òåîðåìå äëÿ âû÷èñëåíèÿ C = kcrs k ñóùåñòâóåò àëãîðèòì ñ ÷èñëîì áèòîâûõ îïåðàöèé O(nlog2 7 log2 n). Ïîñëå ýòîãî â êàæäîì crs äîñòàòî÷íî âçÿòü äèçúþíêöèþ âñåõ ðàçðÿäîâ (èñêëþ÷àÿ çíàê),÷òîáû âû÷èñëèòü drs . Ïîñêîëüêó 0 6 crs 6 n, òî äëèíà êàæäîãî crsíå ïðåâîñõîäèò O(log n) è íà âû÷èñëåíèå âñåõ drs èç crs ïîòðåáóåòñÿO(n2 log n) áèòîâûõ îïåðàöèé. Îáùåå ÷èñëî áèòîâûõ îïåðàöèé áóäåò23O(nlog2 7 log2 n) + O(n2 log n) = O(nlog2 7 log2 n).

Òåîðåìà äîêàçàíà.Çàìå÷àíèå. Ñì. çàìå÷àíèÿ ê ïðåäûäóùåé òåîðåìå.3.2. Òðàíçèòèâíîå çàìûêàíèå ãðàôîâîðèåíòèðîâàííûé ãðàô G â âèäå ìàòðèöû A = kaij k, ãäåaij = 1, åñëè â G åñòü äóãà èç vi â vj , è aij = 0, åñëè òàêîé äóãè íåò(aii = 0 äëÿ âñåõ i).Òðåáóåòñÿ: ïîñòðîèòü ìàòðèöó B = kbij k, òàêóþ, ÷òî bij = 1, åñëèåñòü îðèåíòèðîâàííûé ïóòü èç vi â vj , è bij = 0, åñëè òàêîãî ïóòè íåò (â÷àñòíîñòè, bii = 1 äëÿ âñåõ i).Îïðåäåëåíèå. Îðèåíòèðîâàííûé ãðàô ñ ìàòðèöåé ñìåæíîñòè Bíàçûâàåòñÿ òðàíçèòèâíûì çàìûêàíèåì ãðàôà G.Äàíî:Òåîðåìà 3.3. Òðàíçèòèâíîå çàìûêàíèå îðèåíòèðîâàííîãî ãðàôàñnâåðøèíàìè ìîæíî ïîñòðîèòü, èñïîëüçóÿO(nlog2 7 log3 n)áèòîâûõîïåðàöèé.Ïóñòü A ìàòðèöà ñìåæíîñòè îðãðàôà G èìàòðèöà Ā = kāij k ïîëó÷àåòñÿ èç A çàìåíîé âñåõ äèàãîíàëüíûõ ýëåìåíòîâ íà 1. Òîãäà āij = 1 â òîì è òîëüêî â òîì ñëó÷àå, åñëè èç vi â vjñóùåñòâóåò îðèåíòèðîâàííûé ïóòü äëèíû (ò.å. ñ ÷èñëîì äóã) íå áîëåå 1.Ïóñòü Ā◦k = Ā ◦ Ā ◦ . .

. Ā, ãäå ÷èñëî ñîìíîæèòåëåé ðàâíî k è óìíîæåíèåìàòðèö áóëåâñêîå.Äîêàçàòåëüñòâî.Ëåììà 3.2. Åñëèñëó÷àå, åñëè âíå áîëååGĀ◦k = kakij k,òîakij = 1â òîì è òîëüêî â òîìñóùåñòâóåò îðèåíòèðîâàííûé ïóòü èçviâvjäëèíûk.(èíäóêöèåé ïî k ). Ïðè k = 1 óòâåðæäåíèå âåðíî.pÏóñòü îíî âåðíî ïðè k = p, òî åñòü aij = 1 òîãäà è òîëüêî òîãäà, êîãäàñóùåñòâóåò ïóòü èç vi â vj äëèíû íå áîëåå p. Ïî îïðåäåëåíèþ ïîëó÷àåìW pp+1Ā◦(p+1) = Ā◦p ◦ Ā è ap+1== 1 òîãäà è òîëüêîijq aiq ◦ āqj . Îòñþäà aijòîãäà, êîãäà ñóùåñòâóåò âåðøèíà vq òàêàÿ, ÷òî èç vi â vq ñóùåñòâóåò ïóòüäëèíû íå áîëåå p, è èç vq â vj ñóùåñòâóåò ïóòü äëèíû íå áîëåå 1.

Íî ýòîóñëîâèå ðàâíîñèëüíî òîìó, ÷òî èç vi â vj ñóùåñòâóåò ïóòü äëèíû íå áîëååp + 1. Òàêèì îáðàçîì, óòâåðæäåíèå ëåììû âåðíî è ïðè k = p + 1. Ëåììàäîêàçàíà.Åñëè â îðãðàôå G èç vi â vj ñóùåñòâóåò õîòÿ áû îäèí îðèåíòèðîâàííûé ïóòü, òî ñóùåñòâóåò òàêîé ïóòü áåç ïîâòîðåíèÿ âåðøèí è,ñëåäîâàòåëüíî, äëèíû íå áîëåå n−1, ãäå n ÷èñëî âåðøèí â G. Ïîýòîìóèç ëåììû ñëåäóåò, ÷òî Ā◦k = B ïðè ëþáîì k > n − 1. Áóäåì âû÷èñëÿòümïîñëåäîâàòåëüíî Ā, Ā◦2 , Ā◦4 , Ā◦8 , . .

. Ā◦2 , ãäå m = dlog2 (n − 1)e. Òàêmêàê 2m > n − 1, òî Ā◦2 = B . Ïî òåîðåìå 3.2 ñóùåñòâóåò àëãîðèòìÄîêàçàòåëüñòâî24äëÿ âû÷èñëåíèÿ âñåõ ýòèõ ìàòðèö, è â ÷àñòíîñòè B , ñ ÷èñëîì áèòîâûõîïåðàöèé m · O(nlog2 7 · log2 n) = O(nlog2 7 log3 n). Òåîðåìà äîêàçàíà.Çàìå÷àíèå. Ñì. çàìå÷àíèÿ ê òåîðåìå 3.1.3.3. Ðàñïîçíàâàíèå ïðèíàäëåæíîñòè áóëåâûõôóíêöèé ïðåäïîëíûì êëàññàì ÏîñòàÐàññìîòðèì çàäà÷ó ðàñïîçíàâàíèÿ ñâîéñòâ áóëåâûõ ôóíêöèé, ïðè÷åì ñåé÷àñ áóäåì ñ÷èòàòü, ÷òî áóëåâû ôóíêöèè ïîñòóïàþò íà âõîä àëãîðèòìà â âåêòîðíîì ïðåäñòàâëåíèè.

À èìåííî, ïóñòü âñå íàáîðû äëèíûn èç 0 è 1 óïîðÿäî÷åíû åñòåñòâåííûì îáðàçîì (êàê ñîîòâåòñòâóþùèåèì äâîè÷íûå ÷èñëà). Òîãäà áóëåâñêóþ ôóíêöèþ f (x1 , . . . , xn ) îò n ïåðåìåííûõ ìîæíî çàäàòü âåêòîðîì (a0 , a1 , . . . , a2n −1 ) åå çíà÷åíèé íà âñåõ 2níàáîðàõ.  êà÷åñòâå àëãîðèòìîâ ìû ðàññìîòðèì àëãîðèòìû ñ áèòîâûìèîïåðàöèÿìè. Ëþáîé òàêîé àëãîðèòì ìîæíî ðàññìàòðèâàòü êàê ñõåìó èçôóíêöèîíàëüíûõ ýëåìåíòîâ (ÑÔÝ), ýëåìåíòàìè â êîòîðîé ìîãóò áûòüëþáûå ôóíêöèè îò 2 ïåðåìåííûõ (èëè îò 1 ïåðåìåííîé).

Åñëè îòâåò âçàäà÷å äëÿ äàííîãî âõîäà äà, òî íà âûõîäå äîëæíà áûòü 1, èíà÷å 0. Ïîäñëîæíîñòüþ àëãîðèòìà áóäåì ïîíèìàòü ÷èñëî áèòîâûõ îïåðàöèé (÷èñëîýëåìåíòîâ â ÑÔÝ).Òåîðåìà Ïîñòà î ïîëíîòå ñèñòåìû áóëåâûõ ôóíêöèé ñâîäèò âîïðîñî ïîëíîòå ê âîïðîñó î ïðèíàäëåæíîñòè ôóíêöèé 5 ïðåäïîëíûì êëàññàìT0 , T1 , S, L, M (ñì. [18]). Ìû ðàññìîòðèì âîïðîñ î ñëîæíîñòè ðàñïîçíàâàíèÿ ýòèõ ñâîéñòâ.

Íàïîìíèì, ÷òîf ∈ T0 ⇐⇒ f (0, . . . , 0) = 0, f ∈ T1 ⇐⇒ f (1, . . . , 1) = 1,f ∈ S ⇐⇒ f (x̄1 , . . . , x̄n ) = f¯(x1 , . . . , xn ),f ∈ L ⇐⇒ f (x1 , . . . , xn ) = c0 ⊕ c1 x1 ⊕ . . . ⊕ cn xn ,f ∈ M ⇐⇒ äëÿ âñåõ α̃ = (α1 , . . . , αn ) è β̃ = (β1 , . . . , βn )òàêèõ, ÷òî ∀i(αi 6 βi ), âûïîëíÿåòñÿ f (α̃) 6 f (β̃).Óòâåðæäåíèå 3.1. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , .

. . , xn )∈ T0 ?ñóùåñòâóåò àëãîðèòì(ÑÔÝ) ñî ñëîæíîñòüþ 1. ýòîì ñëó÷àå âûõîä z çàäàåòñÿ ôîðìóëîé z = ᾱ0 .Óòâåðæäåíèå 3.2. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , . . . , xn )∈ T1 ?ñóùåñòâóåò àëãîðèòì(ÑÔÝ) ñî ñëîæíîñòüþ 0. ýòîì ñëó÷àå âûõîä z çàäàåòñÿ ôîðìóëîé z = a2n −1 .Óòâåðæäåíèå 3.3. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿ∈ S? ñóùåñòâóåòN = 2n äëèíà âõîäà.ðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , . . . , xn )(ÑÔÝ) ñî ñëîæíîñòüþO(N ),ãäå25àëãîðèòìÏî îïðåäåëåíèþ ñàìîäâîéñòâåííûõ ôóíêöèéf (x1 , . . .

, xn ) ∈ S òîãäà è òîëüêî òîãäà, êîãäà äëÿ ëþáîãî α̃ = (α1 , . . . , αn )âûïîëíÿåòñÿ f (α1 , . . . , αn ) 6= f (ᾱ1 , . . . , ᾱn ), òî åñòü êîãäà äëÿ âñåõ i =0, 1, . . . , 2n−1 − 1 âûïîëíÿåòñÿ ai 6= a2n −1−i . Òàêèì îáðàçîì, äëÿ ðàñïîçíàâàíèÿ ñâîéñòâà f ∈ S? äîñòàòî÷íî èñïîëüçîâàòü 2n−1 áóëåâûõîïåðàöèé ai ⊕ a2n −1−i è çàòåì âçÿòü êîíúþíêöèþ ïîëó÷åííûõ çíà÷åíèé.Îáùåå ÷èñëî áèòîâûõ îïåðàöèé áóäåò 2n−1 + 2n−1 − 1 = N − 1.Äîêàçàòåëüñòâî.Óòâåðæäåíèå 3.4. Ïðè âåêòîðíîì ïðåäñòàâëåíèè ôóíêöèé äëÿ∈ L? ñóùåñòâóåòN = 2n äëèíà âõîäà.ðàñïîçíàâàíèÿ ñâîéñòâà f (x1 , . . .

, xn )(ÑÔÝ) ñî ñëîæíîñòüþO(N ),ãäåàëãîðèòìËåììà 3.3.(f (0, x2 , . . . , xn ) ∈ L,f (x1 , . . . , xn ) ∈ L ⇐⇒f (1, x2 , . . . , xn ) ≡ f (0, x2 , . . . , xn ) ⊕ d, d ∈ {0, 1}.Åñëè f (x1 , . . . , xn ) = c1 x1 ⊕ c2 x2 ⊕ . . . ⊕ cn xn + c0 ,òî, î÷åâèäíî, f (0, x2 , . . .