В.Б. Алексеев - Введение в теорию сложности алгоритмов (1114532), страница 5
Текст из файла (страница 5)
Òåîðåìà äîêàçàíà.Çàìå÷àíèå. Åùå áîëåå áûñòðûì ÿâëÿåòñÿ àëãîðèòì óìíîæåíèÿ÷èñåë Øåíõàãå è Øòðàññåíà, áèòîâàÿ ñëîæíîñòü êîòîðîãî ðàâíàO(n log n log log n) [16].2.5. Àëãîðèòì Øòðàññåíà äëÿ óìíîæåíèÿ ìàòðèöÐàññìîòðèì çàäà÷ó óìíîæåíèÿ äâóõ êâàäðàòíûõ ìàòðèö A = kaij kè B = kbkl k ïîðÿäêà n. Ïóñòü A · B = C = kcrs k. Òîãäà ïî îïðåäåëåPníèþ crs =p=1 arp bps .  êà÷åñòâå âõîäà ìû áóäåì ðàññìàòðèâàòü âñåçíà÷åíèÿ aij è bkl , ñ÷èòàÿ èõ íåäåëèìûìè, òî åñòü ìû âîñïðèíèìàåìèõ êàê åäèíîå öåëîå è íå ìîæåì ðàáîòàòü ñ êàêèìè-ëèáî èõ ÷àñòÿìè. êà÷åñòâå îïåðàöèé áóäåì ðàññìàòðèâàòü 4 àðèôìåòè÷åñêèå îïåðàöèè,êîòîðûå ìîãóò ïðèìåíÿòüñÿ êàê ê èñõîäíûì ïåðåìåííûì aij , bkl , òàêè ê óæå ïîñòðîåííûì âûðàæåíèÿì. Íàøà çàäà÷à ñîñòîèò â ïîëó÷åíèèâñåõ âûðàæåíèé äëÿ crs .
Ñëîæíîñòüþ àëãîðèòìà áóäåò ñ÷èòàòüñÿ ÷èñëîàðèôìåòè÷åñêèõ îïåðàöèé.Îáû÷íûé àëãîðèòì óìíîæåíèÿ ìàòðèö (ñòðî÷êà íà ñòîëáåö) òðåáóåò n3 óìíîæåíèé è n2 (n − 1) ñëîæåíèé, òî åñòü ïîðÿäêà n3 îïåðàöèé.Áîëåå áûñòðûé ïî ïîðÿäêó àëãîðèòì òèïà ðàçäåëÿé è âëàñòâóé ïðåäëîæèë Øòðàññåí [17].Òåîðåìà 2.7 (Â. Øòðàññåí). Äëÿ óìíîæåíèÿ äâóõ ìàòðèö ïîðÿäêà n ñóùåñòâóåò àëãîðèòì ñ ÷èñëîì àðèôìåòè÷åñêèõ îïåðàöèélog2 7O(n).Îïèøåì òàêîé àëãîðèòì. Åñëè n íå ñòåïåíüäâîéêè è áëèæàéøàÿ ê n ñâåðõó ñòåïåíü äâîéêè åñòü 2k , òî ðàñøèðèìäàííûå ìàòðèöû A è B äî ìàòðèö A0 è B 0 ïîðÿäêà 2k òàê, ÷òîáû â ëåâûõâåðõíèõ óãëàõ ìàòðèö A0 è B 0 ñòîÿëè, ñîîòâåòñòâåííî, A è B , à îñòàëüíûåýëåìåíòû áûëè ðàâíû 0. Òîãäà, åñëè A0 · B 0 = C 0 , òî ëåãêî âèäåòü, ÷òî âC 0 â ëåâîì âåðõíåì óãëó ñòîèò ìàòðèöà C = A · B , à îñòàëüíûå ýëåìåíòûðàâíû 0. Ïîýòîìó äëÿ âû÷èñëåíèÿ C = A · B äîñòàòî÷íî ïåðåìíîæèòüìàòðèöû A0 è B 0 ïîðÿäêà 2k . Ïóñòü äàëåå n = 2k ñòåïåíü äâîéêè èA, B ìàòðèöû ïîðÿäêà n = 2k .
Ðàçðåæåì êàæäóþ èç ìàòðèö A è B ,à òàêæå èñêîìóþ ìàòðèöó C = A · B , íà 4 êâàäðàòíûõ áëîêà ðàçìåðàÄîêàçàòåëüñòâî.20n2× n2 : A11 A12A= A21 A22 , B = B11 B12 B21 B22 , C = C11 C12 C21 C22.Èç àëãåáðû èçâåñòíî, ÷òî â ýòîì ñëó÷àåC11 = A11 B11 + A12 B21 ,C12 = A11 B12 + A12 B22 ,C21 = A21 B11 + A22 B21 ,C22 = A21 B12 + A22 B22 .Òàêèì îáðàçîì, âû÷èñëåíèå ìàòðèöû C ñâîäèòñÿ ê 8 óìíîæåíèÿì ìàòðèö ïîðÿäêà n2 (è íåñêîëüêèì ñëîæåíèÿì). Èäåÿ Øòðàññåíà ñîñòîèò âçàìåíå 8 óìíîæåíèé íà 7 (ñðàâíèòå ñ àëãîðèòìîì Êàðàöóáû). Ðàññìîòðèì ñëåäóþùèå 7 ïðîèçâåäåíèé:D1D2D3D4= (A11 + A22 )(B11 + B22 ),D5 = (A11 + A12 )B22 ,= (−A11 + A21 )(B11 + B12 ), D6 = A22 (−B11 + B21 ),= (A12 − A22 )(B21 + B22 ),D7 = (A21 + A22 )B11 .= A11 (B12 − B22 ),Ðàñêðûâàÿ ñêîáêè è ïðèâîäÿ ïîäîáíûå ÷ëåíû, ìîæíî ïðîâåðèòü, ÷òîC11 = D1 + D3 − D5 + D6 , C12 = D4 + D5 ,C21 = D6 + D7 ,C22 = D1 + D2 + D4 − D7 .Òàêèì îáðàçîì, óìíîæåíèå ìàòðèö ïîðÿäêà n ñâîäèòñÿ ê 7 óìíîæåíèÿììàòðèö ïîðÿäêà n2 è íåñêîëüêèì ñëîæåíèÿì ìàòðèö ïîðÿäêà n2 .
Åñëè n =2k , òî ýòîò ïðîöåññ ìîæíî ïðîäîëæèòü ðåêóðñèâíî. Åñëè æå n = 1, òî äëÿóìíîæåíèÿ ìàòðèö ïîðÿäêà 1 òðåáóåòñÿ âñåãî 1 óìíîæåíèå ýëåìåíòîâ.Ïóñòü L(n) ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé â îïèñàííîì àëãîðèòìå.Òàê êàê ñëîæåíèå äâóõ ìàòðèö ïîðÿäêà n2 òðåáóåò O(n2 ) îïåðàöèé, òîäëÿ n = 2k (k = 1, 2, 3, . . .) ïîëó÷àåì ðåêóððåíòíîå íåðàâåíñòâînL(n) 6 7L( ) + O(n2 ).2Ïî òåîðåìå 2.4 î ðåêóððåíòíîì íåðàâåíñòâå îòñþäà ïîëó÷àåì L(n) =O(nlog2 7 ). Òåîðåìà äîêàçàíà.Çàìå÷àíèå.
Îæèäàåòñÿ, ÷òî äëÿ óìíîæåíèÿ ìàòðèö ïîðÿäêà nñóùåñòâóåò àëãîðèòì ñ ÷èñëîì àðèôìåòè÷åñêèõ îïåðàöèé O(n2+ε ) äëÿëþáîãî ôèêñèðîâàííîãî ε > 0 (ñðàâíèòå ñ àëãîðèòìîì Òîîìà), îäíàêîïîêà (ñåðåäèíà 2002 ãîäà) íàèëó÷øåé îöåíêîé ÿâëÿåòñÿ O(n2.38 ) [2].213. Ìåòîä ðàñøèðåíèÿ ìîäåëèÎ÷åíü âàæíûì ìåòîäîì â ìàòåìàòèêå ÿâëÿåòñÿ ìåòîä ðàñøèðåíèÿìîäåëè. Ïåðåõîä â áîëåå øèðîêóþ ìîäåëü îáû÷íî íå óïðîùàåò çàäà÷ó,íî ðàñøèðÿÿ âîçìîæíîñòè, óïðîùàåò ïîèñê ðåøåíèÿ çàäà÷è. Âàæíûìïðèìåðîì ðàñøèðåíèÿ ìîäåëè ÿâëÿåòñÿ ðàçâèòèå ïîíÿòèÿ ÷èñëà: íàòóðàëüíûå äðîáíûå öåëûå ðàöèîíàëüíûå äåéñòâèòåëüíûå êîìïëåêñíûå. Âûõîä â áîëåå øèðîêóþ ìîäåëü ïîçâîëÿåò áîëåå êîìïàêòíîîïèñûâàòü àëãîðèòìû è çà ñ÷åò ýòîãî íàõîäèòü áîëåå áûñòðûå àëãîðèòìûäëÿ èñõîäíîé ìîäåëè.
Ïðèìåðîì ìîæåò ñëóæèòü àëãîðèòì Òîîìà, ãäå îòóìíîæåíèÿ ÷èñåë ìû ïåðåõîäèì ê óìíîæåíèþ ìíîãî÷ëåíîâ è èñïîëüçóåìâîçìîæíîñòü èíòåðïîëÿöèè ìíîãî÷ëåíîâ.  ðàçäåëàõ 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
