Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 56
Текст из файла (страница 56)
Îäíàêî, ìû ìîæåì óòâåðæäàòü, ÷òî èñòèííîå ÷èñëî îïåðàöèé íåïðåâûøàåò O(nlog2 7 ). Èìåííî ñòîëüêî îïåðàöèé äàåò àëãîðèòì Øòðàññåíà, êîòîðûé ìûîáñóæäàëè â ñàìîé ïåðâîé ëåêöèè íàøåãî êóðñà.Îòêóäà æå áåðåòñÿ îðèãèíàëüíûé ñïîñîá óìíîæåíèÿ 2×2-ìàòðèö, íà êîòîðîì òàì âñåîñíîâàíî? Òåïåðü, â çàêëþ÷èòåëüíîé ëåêöèè, ìû èìååì âîçìîæíîñòü ðàñêðûòü òàéíóàëãîðèòìà Øòðàññåíà.Èòàê, ïóñòüu1 u3 v 1 v 3w1 w3=.u2 u4 v 2 v 4w2 w4Ðàâåíñòâà, âûðàæàþùèå wk ÷åðåç ui è vj , ìîæíî, î÷åâèäíî, çàïèñàòü â òàêîé ôîðìå:w1 = u1 v1 + u3 v2 ,4 X4Xw2 = u2 v1 + u4 v2 ,⇔ wk =xijk ui vj , k = 1, 2, 3, 4.w3 = u1 v3 + u3 v4 ,i=1 j=1w4 = u2 v3 + u4 v4 .Âîçíèêøèé çäåñü òðåõìåðíûé ìàññèâ X = [xijk ] èìååò ðàçìåðû 4 × 4 × 4, åãî ýëåìåíòûÅ. Å. Òûðòûøíèêîâ269xijk ðàâíû 0 ëèáî 1.
Âîò ñå÷åíèÿ X ïî îñè k :" 1 0 0 0#" 0 0 0 0#Xk=1 =000010000000100, Xk=2 =001000000"0, Xk=3 =000000010000010"0#, Xk=4 =000000010000001#. äàííîì ñëó÷àå ÿñíî, ÷òî òåíçîðíûé ðàíã ìàññèâà X íå áîëüøå 8 (äîêàæèòå!).Ïóñòü îí ðàâåí r. Òîãäà èìååòñÿ òðèëèíåéíîå ðàçëîæåíèå!!rr44XXXXxijk =ais bjs cks ⇒ wk =cksais uibjs vj , k = 1, 2, 3, 4.s=1s=1i=1j=1Êàê âèäèì, òðèëèíåéíîå ðàçëîæåíèå ðàíãà r ïîðîæäàåò ñïåöèàëüíûé àëãîðèòì âû÷èñëåíèÿ âåëè÷èí wk , â êîòîðîì âñåãî r àêòèâíûõ óìíîæåíèé òàê íàçûâàþòñÿ óìíîæåíèÿ, â êîòîðûõ îáà ìíîæèòåëÿ ñóùåñòâåííî çàâèñÿò îò âõîäíûõ ïåðåìåííûõ uiè vj (÷èñëà ais , bjs , cks íå çàâèñÿò îò ui , vj ; èõ íàçûâàþò êîíñòàíòàìè àëãîðèòìà óìíîæåíèå íà êîíñòàíòó íå ñ÷èòàåòñÿ àêòèâíûì óìíîæåíèåì).×òîáû ïîëó÷èòü îòêðûòèå Øòðàññåíà, äîñòàòî÷íî ðåøèòü çàäà÷ó î âû÷èñëåíèè òåíçîðíîãî ðàíãà äàííîãî êîíêðåòíîãî ìàññèâà X .
Ìîæíî îãðàíè÷èòüñÿ è áîëåå ñêðîìíîéçàäà÷åé: íàéòè êàêîå-íèáóäü òðèëèíåéíîå ðàçëîæåíèå ðàíãà 7 (ðàçëîæåíèå ðàíãà 8 ñâÿçàíî ñ ïðàâèëîì ñòðîêà íà ñòîëáåö). Íåñìîòðÿ íà îòñóòñòâèå êîíå÷íûõ àëãîðèòìîâòî÷íîãî âû÷èñëåíèÿ òåíçîðíîãî ðàíãà, ðàçðàáîòêà àëãîðèòìîâ òðèëèíåéíîé àïïðîêñèìàöèè çàäàííîãî ðàíãà ÿâëÿåòñÿ ïîñèëüíîé çàäà÷åé.Ýôôåêòèâíûå ìåòîäû äëÿ äàííîé çàäà÷è ÿâëÿþòñÿ îäíîé èç êðóïíûõ èññëåäîâàòåëüñêèõ ïðîáëåì. Îäíàêî, â îòäåëüíûõ ñëó÷àÿõ ìîæíî äîáèòüñÿ íóæíîãî ðåçóëüòàòàè ñ ïîìîùüþ êàêèõ-ëèáî ýâðèñòè÷åñêèõ è, âîçìîæíî, ìåäëåííûõ âû÷èñëåíèé: ÷òîáûïîñòðîèòü áûñòðûé àëãîðèòì óìíîæåíèÿ ìàòðèö, ìû âïîëíå ãîòîâû ïîòðàòèòü î÷åíüìíîãî âðåìåíè íà ïîèñê òåíçîðíîãî ðàíãà ìàññèâà X . Âîò êàê âûãëÿäèò òðèëèíåéíîåðàçëîæåíèå X = (A, B, C) ðàíãà 7 â íàøåì ñëó÷àå: 1" 1 1 0 −1 0 1 0 #" 1 0 1 0 1 −1 0 #A=001101000001010100"C=100101−1011−1, B=00111100−10100010001000−100001−1100001010101,#.Äàííîå ðàçëîæåíèå íàéäåíî ñ ïîìîùüþ êîìïüþòåðà.
Òàêèì îáðàçîì, êîìïüþòåðìîæåò èñïîëüçîâàòüñÿ íå òîëüêî êàê èíñòðóìåíò ðåøåíèÿ âû÷èñëèòåëüíûõ çàäà÷, íîòàêæå è êàê èíñòðóìåíò ïîëó÷åíèÿ àëãîðèòìîâ äëÿ ðåøåíèÿ ýòèõ çàäà÷.1 Óñëîâèÿ äîêàçàííîé íàìè òåîðåìû åäèíñòâåííîñòè â äàííîì ñëó÷àå íå âûïîëíåíû. Ïîýòîìó ìîæíîíàéòè è äðóãîå, íåýêâèâàëåíòíîå äàííîìó, ðàçëîæåíèå.270Ëåêöèÿ 40Äîïîëíåíèå ê ëåêöèè 141.1Ïàðàëëåëüíàÿ ôîðìà àëãîðèòìàÀðèôìåòè÷åñêàÿ ñëîæíîñòü àëãîðèòìà âåùü, êîíå÷íî, âàæíàÿ â ëþáîì ñëó÷àå.
Íîñ ðàçâèòèåì êîìïüþòåðîâ âðåìÿ ñòàíîâèòñÿ âñå ìåíåå ïðîïîðöèîíàëüíûì îáùåìó÷èñëó îïåðàöèé. Äåëî â òîì, ÷òî ìíîãèå îïåðàöèè âûïîëíÿþòñÿ ïàðàëëåëüíî (îäíîâðåìåííî).×òîáû ïîíÿòü õîòü ÷òî-òî, íóæíî è òåïåðü îòáðîñèòü î÷åíü ìíîãî äåòàëåé. Ðàññìîòðèì ìîäåëü áåñêîíå÷íîãî ïàðàëëåëèçìà: èìååòñÿ áåñêîíå÷íî ìíîãî ïðîöåññîðîâ ñíåîãðàíè÷åííîé ïàìÿòüþ, êàæäûé ìîæåò â ëþáóþ åäèíèöó âðåìåíè âûïîëíèòü îäíóàðèôìåòè÷åñêóþ îïåðàöèþ è ìãíîâåííî îáìåíèâàåòñÿ èíôîðìàöèåé ñ ëþáûì äðóãèìïðîöåññîðîì.×òîáû ðåàëèçîâàòü àëãîðèòì íà òàêîì èäåàëèçèðîâàííîì êîìïüþòåðå, äîñòàòî÷íîçàïèñàòü åãî â âèäå ïîñëåäîâàòåëüíîñòè ÿðóñîâ íàáîðîâ èíôîðìàöèîííî íåñâÿçàííûõîïåðàöèé (èõ ìîæíî âûïîëíÿòü ïàðàëëåëüíî).
Òàêîå ïðåäñòàâëåíèå àëãîðèòìà íàçûâàåòñÿ åãî ïàðàëëåëüíîé ôîðìîé, ÷èñëî ÿðóñîâ íàçûâàåòñÿ âûñîòîé, à ìàêñèìàëüíîå ÷èñëîîïåðàöèé â îäíîì ÿðóñå øèðèíîé ïàðàëëåëüíîé ôîðìû.Äëÿ ëþáîãî àëãîðèòìà ñóùåñòâóåò, î÷åâèäíî, ïàðàëëåëüíàÿ ôîðìà ñ ìèíèìàëüíûì÷èñëîì ÿðóñîâ. Ýòî ìèíèìàëüíîå ÷èñëî ÿðóñîâ íàçûâàåòñÿ âûñîòîé àëãîðèòìà.  ìîäåëè áåñêîíå÷íîãî ïàðàëëåëèçìà ìèíèìàëüíîå âðåìÿ ðåàëèçàöèè àëãîðèòìà ïðîïîðöèîíàëüíî åãî âûñîòå.41.2Ñõåìà ñäâàèâàíèÿ è ïàðàëëåëüíîå óìíîæåíèå ìàòðèöÂûñîòà êëàññè÷åñêîãî àëãîðèòìà óìíîæåíèÿ ìàòðèö èìååò âèä O (n). Äîêàæèòå!Ëåãêî ïîëó÷èòü è àëãîðèòì âûñîòû O (log2 n). Äëÿ ýòîãî äîñòàòî÷íî ïîñòðîèòü àëãîðèòì ñëîæåíèÿ n ÷èñåë, èìåþùèé âûñîòó O (log2 n). Òàêîé àëãîðèòì íàçûâàåòñÿ ñõåìîéñäâàèâàíèÿ: íóæíî ðàçáèòü ÷èñëà íà ïàðû, íàéòè ñóììû äëÿ êàæäîé ïàðû, çàòåì ðàçáèòü ðåçóëüòàòû íà ïàðû, íàéòè ñóììû, è òàê äàëåå.41.3Ìàòðèöû è ðåêóððåíòíûå âû÷èñëåíèÿÐàññìîòðèì ïîñëåäîâàòåëüíîñòü âåëè÷èí x−1 , x0 , x1 , .
. . , â êîòîðîé x−1 , x0 çàäàíû, àîñòàëüíûå âåëè÷èíû âû÷èñëÿþòñÿ ðåêóððåíòíî:xk = ak xk−1 + bk xk−2 ,k = 1, 2, . . . , n.(∗)Êîýôôèöèåíòû ak , bk ñ÷èòàþòñÿ çàäàííûìè. ×òîáû âû÷èñëèòü xn , â ñèëó (∗) òðåáóåòñÿ âûïîëíèòü O(n) àðèôìåòè÷åñêèõ îïåðàöèé. ×èñëî ïàðàëëåëüíûõ øàãîâ òàêæå271272Ëåêöèÿ 41O(n). Âîçíèêàåò âïå÷àòëåíèå, ÷òî àëãîðèòìïîëó÷èòü íåëüçÿ.Íî ýòî âïå÷àòëåíèå îáìàí÷èâî. Çàïèøåì xkak=1xk−1ñ ìåíüøåé âûñîòîé ïàðàëëåëüíîé ôîðìûñîîòíîøåíèÿ (∗) â ìàòðè÷íîé ôîðìå:bkxk−1,0xk−2èëè,zk =xkxk−1,zk = Ak zk−1 ,xk−1zk−1 =,xk−2Ak =ak b k1 0.Îòñþäàzn = Az0 ,A = An (An−1 (· · · (A3 (A2 A1 )) · · · ).×òîáû îïðåäåëèòü ïðîèçâåäåíèå ìàòðèö An An−1 · · · A1 , íóæíî ñâåñòè åãî ê âû÷èñëåíèþ ïðîèçâåäåíèé äâóõ ìàòðèö.
Ýòî äåëàåòñÿ ðàññòàíîâêîé ñêîáîê. Èñïîëüçóÿ àññîöèàòèâíîñòü îïåðàöèè óìíîæåíèÿ ìàòðèö, ìîæíî äîêàçàòü, ÷òî ðåçóëüòàò íå áóäåòçàâèñèòü îò ïîðÿäêà ðàññòàíîâêè ñêîáîê; ïîýòîìó ìîæíî ïèñàòü áåç ñêîáîê:A = An An−1 · · · A1 .×òîáû íàéòè zn (à çíà÷èò, è xn ), ñíà÷àëà âû÷èñëèì ìàòðèöó A. Äëÿ ýòîãî ìîæíîèñïîëüçîâàòü òó æå ñõåìó ñäâàèâàíèÿ: íàõîäèì ïðîèçâåäåíèÿAn An−1 , An−2 An−3 , .
. . , A2 A1 ,çàòåì ïîïàðíûå ïðîèçâåäåíèÿ ïîëó÷åííûõ ðåçóëüòàòîâ, è òàê äàëåå. Ïîòðåáóåòñÿ âñåãîëèøü O(log2 n) ïàðàëëåëüíûõ øàãîâ!41.4Ìîäåëè è ðåàëüíîñòü ìîäåëè áåñêîíå÷íîãî ïàðàëëåëèçìà ìû îòáðàñûâàåì, óâû, ñëèøêîì ìíîãî äåòàëåé,êîòîðûå ñëåäóåò ó÷èòûâàòü. ß äóìàþ, ìîæíî ïî÷óâñòâîâàòü ïðîáëåìû ïàðàëëåëüíûõâû÷èñëåíèé, ðàçìûøëÿÿ íàä ñëåäóþùåé çàäà÷åé-øóòêîé: Îäèí çåìëåêîï âûêàïûâàåòÿìó ãëóáèíîé 1 ìåòð çà 1 ÷àñ.
Çà êàêîå âðåìÿ ýòó ÿìó âûêîïàþò 100 çåìëåêîïîâ? ×òîáû âûïîëíÿòü êàêóþ-òî ðàáîòó ïàðàëëåëüíî, íåîáõîäèìî òàêóþ ðàáîòó èìåòü. ñóùåñòâóþùèõ àëãîðèòìàõ ðàáîòû äëÿ ïàðàëëåëüíîãî (îäíîâðåìåííîãî) èñïîëíåíèÿìîæåò áûòü íåäîñòàòî÷íî.
Îïåðèðóÿ íàä îáùèìè äàííûìè, ïðîöåññîðû ìîãóò ìåøàòüäðóã äðóãó. Êàê ó÷åñòü âñå ýòî â áîëåå àäåêâàòíûõ è âñå æå ïîääàþùèõñÿ àíàëèçóìîäåëÿõ ýòî òðóäíûé âîïðîñ.Äîïîëíåíèå ê ëåêöèè 242.1Êîíå÷íûå ãðóïïûÃðóïïà íàçûâàåòñÿ êîíå÷íîé, åñëè â íåé èìååòñÿ êîíå÷íîå ÷èñëî ýëåìåíòîâ.  ýòîìñëó÷àå ÷èñëî ýëåìåíòîâ íàçûâàåòñÿ ïîðÿäêîì ãðóïïû.Òåîðåìà Ëàãðàíæà.  ëþáîé êîíå÷íîé ãðóïïå ïîðÿäîê ëþáîé ïîäãðóïïû ÿâëÿåòñÿäåëèòåëåì ïîðÿäêà ãðóïïû.Äîêàçàòåëüñòâî.
Ïóñòü H = {a1 , . . . , am } ïîäãðóïïà ãðóïïû G. Âîçüìåì ýëåìåíòa ∈ G\H è ðàññìîòðèì ìíîæåñòâîaH = {aa1 , . . . , aam }.Îíî ñîäåðæèò m ðàçëè÷íûõ ýëåìåíòîâ: åñëè aai = aaj , òî ai = aj . Êðîìå òîãî, aH ∩H = ∅: åñëè ai = aaj , òî a ∈ H .Åñëè H ∪ aH = G, òî âñå äîêàçàíî. Åñëè íåò, òî ñóùåñòâóåò b ∈ G\(H ∪ aH). ÌíîæåñòâîbH = {ba1 , . . . , bam }òàêæå ñîäåðæèò m ðàçëè÷íûõ ýëåìåíòîâ è ïðè ýòîìH ∩ aH = ∅,H ∩ bH = ∅,aH ∩ bH = ∅.Åñëè H ∪aH ∪bH = G, òî âñå äîêàçàíî. Åñëè íåò, äåéñòâóåì êàê è ðàíüøå. Ïîñêîëüêó÷èñëî ýëåìåíòîâ â G êîíå÷íî, íà êàêîì-òî øàãå ìû ïîëó÷èì ðàçëîæåíèåH ∪ aH ∪ bH ∪ .
. . ∪ cH = Gñ êîíå÷íûì ÷èñëîì ïîïàðíî íåïåðåñåêàþùèõñÿ ìíîæåñòâ H, aH, bH, . . . , cH .Çàäà÷à.Çàäà÷à.Äîêàæèòå, ÷òî â ëþáîé áåñêîíå÷íîé ãðóïïå ÷èñëî ðàçëè÷íûõ ïîäãðóïï áåñêîíå÷íî.42.2ãäådH1 è H2 ïîðÿäêà n1 è n2 , ñîîòâåòñòâåííî.â ìíîæåñòâå H1 H2 = {g ∈ G : g = h1 h2 , h1 ∈ H1 , h2 ∈ H2 } ðàâíîâ ïåðåñå÷åíèè H1 ∩ H2 . êîíå÷íîé ãðóïïåÄîêàæèòå, ÷òî ÷èñëî ýëåìåíòîân1 n2 /d,2 ÷èñëî ýëåìåíòîâGâûáðàíû ïîäãðóïïûÑìåæíûå êëàññû, íîðìàëüíûå äåëèòåëè, ôàêòîð-ãðóïïûÏóñòü H ïîäãðóïïà ãðóïïû G è a ∈ G. ÌíîæåñòâàaH = {x : x = ah, h ∈ H}èHa = {y : y = ha, h ∈ H}íàçûâàþòñÿ ëåâûì ñìåæíûì êëàññîì è ïðàâûì ñìåæíûì êëàññîì ãðóïïû G ïî ïîäãðóïïå H .273274Ëåêöèÿ 42Åñëè b ∈ aH , òî bH = aH (äîêàæèòå!) îòñþäà âûòåêàåò, ÷òî ëåâûå (ïðàâûå)ñìåæíûå êëàññû ëèáî ñîâïàäàþò, ëèáî íå ïåðåñåêàþòñÿ (íà ýòîì ôàêòå è áûëî îñíîâàíîäîêàçàòåëüñòâî òåîðåìû Ëàãðàíæà).Ïîäãðóïïà H íàçûâàåòñÿ íîðìàëüíîé ïîäãðóïïîé èëè íîðìàëüíûì äåëèòåëåìãðóïïû G, åñëèaH = Ha ∀ a ∈ G.⇔aha−1 ∈ H∀ a ∈ G ∀ h ∈ H.Ýëåìåíò eh íàçûâàåòñÿ ñîïðÿæåííûì ê h, åñëè eh = aha−1 äëÿ íåêîòîðîãî a ∈ G.
Òàêèìîáðàçîì, ïîäãðóïïà H ⊂ G ÿâëÿåòñÿ íîðìàëüíîé òîãäà è òîëüêî òîãäà, êîãäà H âìåñòåñ ëþáûì ýëåìåíòîì ñîäåðæèò âñå ñîïðÿæåííûå ê íåìó ýëåìåíòû.Ïóñòü K ìíîæåñòâî ðàçëè÷íûõ ñìåæíûõ êëàññîâ äëÿ íîðìàëüíîãî äåëèòåëÿ H ⊂G. Îïðåäåëèì ïðîèçâåäåíèå ñìåæíûõ êëàññîâ ñëåäóþùèì îáðàçîì:(aH)(bH) ≡ (ab)H.Ïðåæäå âñåãî, íóæíî óáåäèòüñÿ â òîì, ÷òî åñëè a1 ∈ aH, b1 ∈ bH , òî (a1 b1 )H = (ab)H(òî åñòü, îïðåäåëåíèå êîððåêòíî). Ïóñòü a1 = ah1 , b1 = bh2 , h1 , h2 ∈ H . Çíà÷èò, åñëèh ∈ H , òî(a1 b1 )h = ah1 bh2 h = (ab)(b−1 h1 b)(h2 h) ∈ (ab)H. 2Íåòðóäíî ïðîâåðèòü, ÷òî îïåðàöèÿ óìíîæåíèÿ ñìåæíûõ êëàññîâ ïðåâðàùàåò ìíîæåñòâî K â ãðóïïó. Ýòà ãðóïïà íàçûâàåòñÿ ôàêòîð-ãðóïïîé ãðóïïû G ïî íîðìàëüíîìóäåëèòåëþ H .
Îáîçíà÷åíèå: K = G/H .Çàäà÷à.Êàêèå ñìåæíûå êëàññû ÿâëÿþòñÿ ïîäãðóïïàìè?Çàäà÷à.Äîêàæèòå, ÷òî ëþáàÿ àáåëåâà ãðóïïà ïîðÿäêàpq ,ãäåpèq ðàçëè÷íûå ïðîñòûå ÷èñëà,ÿâëÿåòñÿ öèêëè÷åñêîé.42.3Èçîìîðôèçìû ãðóïïÐàññìîòðèì ãðóïïó H ñ îïåðàöèåé ∗ è ãðóïïó G ñ îïåðàöèåé ◦. Îáðàòèìîå îòîáðàæåíèåf : H → G íàçûâàåòñÿ èçîìîðôèçìîì, åñëèf (a ∗ b) = f (a) ◦ f (b) ∀ a, b ∈ H.(#)Ñâîéñòâî (#) íàçûâàåòñÿ ñâîéñòâîì ñîõðàíåíèÿ îïåðàöèé. Ëåãêî âèäåòü, ÷òî îáðàòíîåîòîáðàæåíèå f −1 : G → H òàêæå ÿâëÿåòñÿ èçîìîðôèçìîì. Ãðóïïû H è G íàçûâàþòñÿèçîìîðôíûìè.
Îáîçíà÷åíèå: H ' G. Íåñìîòðÿ íà ôîðìàëüíûå ðàçëè÷èÿ â îïðåäåëåíèèýëåìåíòîâ è îïåðàöèé, èçîìîðôíûå ãðóïïû ìîæíî ñ÷èòàòü îäèíàêîâûìè ñ òî÷êè çðåíèÿñâîéñòâ èõ îïåðàöèé.Íàïðèìåð, ëþáûå äâå êîíå÷íûå öèêëè÷åñêèå ãðóïïû îäíîãî ïîðÿäêà n áóäóò èçîìîðôíûìè. Åñëè a0 , a1 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
