8 Фазовый алгоритм. Алгоритм Финна. Алгоритмы обхода. Распределенный обход в глубину. Алгоритмы обхода Авербаха и Сидон (1185645)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

ÐàñïðåäåëåííûåàëãîðèòìûËÅÊÒÎÐ: Â.À. ÇàõàðîâËåêöèÿ 7.Âîëíîâûå àëãîðèòìû.Ôàçîâûé àëãîðèòì.Àëãîðèòì Ôèííà.Ðàñïðåäåëåííûå àëãîðèòìû îáõîäà:îñíîâíûå ñâîéñòâà.Àëãîðèòì îáõîäà Òàððè.Ðàñïðåäåëåííûé îáõîä â ãëóáèíó.Àëãîðèòìû Àâåðáàõà è Ñèäîíà.Âîëíîâûå àëãîðèòìûÎïðåäåëåíèå.Âîëíîâûì àëãîðèòìîì íàçûâàåòñÿ ðàñïðåäåëåííûé àëãîðèòì,êîòîðûé óäîâëåòâîðÿåò ñëåäóþùèì òðåì òðåáîâàíèÿì.1.Çàâåðøåíèå.Êàæäîå âû÷èñëåíèå êîíå÷íî:∀C : |C | < ∞.2.Êàæäîå âû÷èñëåíèå ñîäåðæèò õîòÿ áû îäíîñîáûòèå ðåøåíèÿ:Ðåøåíèå.∀C : ∃e ∈ C : e ÿâëÿåòñÿ ñîáûòèåì ðåøåíèÿ decide.3. ëþáîì âû÷èñëåíèè âñÿêîìó ñîáûòèþðåøåíèÿ ïðåäøåñòâóåò â ïðè÷èííî-ñëåäñòâåííîìîòíîøåíèè õîòÿ áû îäíî ñîáûòèå â êàæäîì èç ïðîöåññîâ:Çàâèñèìîñòü.Âîëíîâûå àëãîðèòìûÂîëíîâûå àëãîðèòìû ïðèãîäíû äëÿ ðåøåíèÿ ñëåäóþùèõ çàäà÷:1.Øèðîêîâåùàòåëüíîå ðàñïðîñòðàíåíèå èíôîðìàöèè ñïîäòâåðæäåíèåì.2.Ñèíõðîíèçàöèè ïðîöåññîâ ñèñòåìû.3.Âû÷èñëåíèÿ ãëîáàëüíîé ôóíêöèè òî÷íîé íèæíåéãðàíè.4.

è ìíîãèõ äðóãèõ (èçáðàíèÿ ëèäåðà, îáíàðóæåíèÿçàâåðøåíèÿ è äð.)Âîëíîâûå àëãîðèòìûÎñíîâíûå âîëíîâûå àëãîðèòìû:1.Âîëíîâûå àëãîðèòìû â êîëüöàõ.2.Äðåâåñíûé âîëíîâîé àëãîðèòì.3.Àëãîðèòì ýõà.Íî ýòè àëãîðèòìû ðàáîòàþò òîëüêî â ñåòÿõ ñ äâóñòîðîííèìèêàíàëàìè ñâÿçè (íåîðèåíòèðîâàííûìè ãðàôàìè).Ðàññìîòðèì åùå íåñêîëüêî áîëåå îáùèõ àëãîðèòìîâ: ôàçîâûéàëãîðèòì è àëãîðèòì Ôèííà.Ôàçîâûé àëãîðèòìÔàçîâûé àëãîðèòì ÿâëÿåòñÿ äåöåíòðàëèçîâàííûì àëãîðèòìîì,ïðèãîäíûì äëÿ ñåòåé ñ ïðîèçâîëüíîé òîïîëîãèåé. Îí ïðèãîäåíäëÿ îðèåíòèðîâàííûõ ñåòåé. ýòîì àëãîðèòìå òðåáóåòñÿ, ÷òîáû âñå ïðîöåññû ðàñïîëàãàëèñâåäåíèÿìè î äèàìåòðå ñåòè D .

Àëãîðèòì áóäåò îñòàâàòüñÿêîððåêòíûì (õîòÿ è ìåíåå ýôôåêòèâíûì), åñëè âñå ïðîöåññûáóäóò èñïîëüçîâàòü âìåñòî D êîíñòàíòó D 0 , ïðåâûøàþùóþäèàìåòð ñåòè.Ôàçîâûé àëãîðèòì ïðèìåíèì äëÿ âñÿêîé îðèåíòèðîâàííîéñåòè, ïî êàíàëàì êîòîðîé îñóùåñòâëÿåòñÿ îäíîñòîðîííÿÿïåðåäà÷à ñîîáùåíèé.  ýòîì ñëó÷àå ñîñåäÿìè âåðøèíû p áóäóòñîñåäè íà âõîäå (ïðîöåññû, êîòîðûå ìîãóò îòïðàâëÿòüñîîáùåíèÿ ïðîöåññó p ) è ñîñåäè íà âûõîäå (ïðîöåññû, êîòîðûìp ìîæåò îòïðàâëÿòü ñîîáùåíèÿ). Ñîñåäè p íà âõîäå îáðàçóþòìíîæåñòâî Inp , à ñîñåäè íà âûõîäå ìíîæåñòâî Outp .Ôàçîâûé àëãîðèòìÎñíîâíàÿ èäåÿ.1.

Êàæäûé ïðîöåññ îòïðàâëÿåò â òî÷íîñòè Dñîîáùåíèé êàæäîìó ñîñåäó íà âûõîäå.2. Êàæäîìó ñîñåäó íà âûõîäå áóäåò îòïðàâëåíî(i + 1) -îå ñîîáùåíèå ïîñëå òîãî, êàê îò êàæäîãîñîñåäà íà âõîäå áûëè ïîëó÷åíû i ñîîáùåíèé.3. Êàê òîëüêî îò êàæäîãî ñîñåäà áóäåò ïîëó÷åíî âòî÷íîñòè D ñîîáùåíèé, ïðîöåññ çàâåðøàåòàëãîðèòì è ïðèíèìàåò ðåøåíèå.Ôàçîâûé àëãîðèòìD: integer= äèàìåòð ñåòè ;var Recp [q]: 0..Dinit 0 äëÿ êàæäîãî q ∈ Inp ;(* ×èñëî ñîîáùåíèé, ïîëó÷åííûõ îò q *)Sentp: 0..Dinit 0 ;(* ×èñëî ñîîáùåíèé, îòïðàâëåííûõ êàæäîìó ñîñåäó íà âûõîäå *begin if p is initiator thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 end;while minq Recp [q] < D dobegin receive htoki (from neighbor q0 ) ;Recp [q0 ] := Recp [q0 ] + 1 ;if minq Recp [q] ≥ Sentp and Sentp < D thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 endend;decideconsendÔàçîâûé àëãîðèòìD=3p2Rec2 = (0)Sent = 02@@@@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @@Sent1 = 0@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2tokRec2 = (0)Sent = 02@@@@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 02@@@@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 12@@@tok@@ Rec4 = (0, 0)R@p1 p4Sent = 04@Rec1 = (0) @tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 12@@@@@ Rec4 = (1, 0)R@p1 p4Sent = 04@Rec1 = (0) @tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (1)Sent = 12@@@@p1 @ Rec4 = (1, 0)R@p4tokSent = 14@Rec1 = (0) @tok@Sent1 = 1@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2tokRec2 = (1)Sent = 12@@@@@ Rec4 = (1, 0)R@p1 p4Sent = 14@Rec1 = (1) @tok@tokSent1 = 2@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@tok@@ Rec4 = (1, 0)R@p1 p4Sent = 14@Rec1 = (1) @tok@tokSent1 = 2@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@@ Rec4 = (2, 0)R@p1 p4Sent = 14@Rec1 = (1) @tok@tokSent1 = 2@@ Rec3 = (0)R@p3Sent = 03Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@@ Rec4 = (2, 0)R@p1 p4Sent = 14@Rec1 = (1) @toktok@Sent1 = 2@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìD=3p2Rec2 = (2)Sent = 22@@@@p1 @ Rec4 = (2, 1)R@p4tokSent = 24@Rec1 = (1) @tok@Sent1 = 2@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìD=3p2tokRec2 = (2)Sent = 22@@@@@ Rec4 = (2, 1)R@p1 p4Sent = 24@Rec1 = (2) @tok@tokSent1 = 3@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìdecideD=3p2Rec2 = (3)Sent = 32@@@tok@@ Rec4 = (2, 1)R@p1 p4Sent = 24@Rec1 = (2) @tok@tokSent1 = 3@@ Rec3 = (1)R@p3Sent = 13Ôàçîâûé àëãîðèòìÏî êàæäîìó êàíàëó ïåðåäàåòñÿ íå áîëåå D ñîîáùåíèé.Äëÿ êàæäîãî ðåáðà pq âûðàæåíèå(i)fpq îáîçíà÷àåò i -å ñîáûòèå îòïðàâëåíèÿ ïðîöåññîì pñîîáùåíèÿ ïðîöåññó q ,(i)gpq îáîçíà÷àåò i -å ñîáûòèå ïðèåìà ïðîöåññîì qñîîáùåíèÿ îò ïðîöåññà p .Åñëè â êàíàëàõ ïîääåðæèâàåòñÿ î÷åðåäíîñòü ñîîáùåíèé, òî(i)(i)fpq gpq î÷åâèäíî âûïîëíÿåòñÿ.(i)(i)Îäíàêî îòíîøåíèå fpq gpq ñîáëþäàåòñÿ è â òåõ ñëó÷àÿõ,êîãäà êàíàë íå ÿâëÿåòñÿ î÷åðåäüþ.Ôàçîâûé àëãîðèòìËåììà 7.1.(i)(i)Ñîîòíîøåíèå fpq gpq ñîáëþäàåòñÿ è òîãäà, êîãäà êàíàë íåÿâëÿåòñÿ î÷åðåäüþ.Äîêàçàòåëüñòâî.(m )Ïóñòü m` òàêîâî, ÷òî fpq ` ýòî ñîáûòèå îòïðàâëåíèÿ ñîîá(`)ùåíèÿ, êîòîðîå ñîîòâåòñòâóåò gpq , ò.å.

ïðè âûïîëíåíèè ` -ãîñîáûòèÿ ïðèåìà ïðîöåññ q ïîëó÷àåò m` -å ñîîáùåíèå îò p .(m` )Ïî îïðåäåëåíèþ îòíîøåíèÿ èìååì fpq(`) gpq .Êàæäîå ñîîáùåíèå ïðèíèìàåòñÿ îäíîêðàòíî, ïîýòîìó âñå m`ðàçëè÷íû. Ñëåäîâàòåëüíî, õîòÿ áû îäíî èç ÷èñåë m1 , . . . , miáóäåò íå ìåíüøå, ÷åì i .Âûáåðåì j ≤ i òàêîå, ÷òî mj ≥ i .(i)(mj )Òîãäà fpq fpq(j)(i) gpq gpq .Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå D ñîîáùåíèé.Çíà÷èò, âñå âû÷èñëåíèÿ àëãîðèòìà çàâåðøàþòñÿ.Ïóñòü γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ âû÷èñëåíèÿ C .Ñíà÷àëà ïîêàæåì, ÷òî êàæäûé ïðîöåññ îòïðàâèë õîòü îäíîñîîáùåíèå.Ò.ê. â êîíôèãóðàöèè γ â êàíàëàõ íåò ñîîáùåíèé,Recp [q] = Sentq äëÿ êàæäîãî êàíàëà qp .Ôàçîâûé àëãîðèòìp is initiator thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 end;while minq Recp [q] < D dobegin receive htoki (from neighbor q0 ) ;Recp [q0 ] := Recp [q0 ] + 1 ;if minq Recp [q] ≥ Sentp and Sentp < D thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 endend;decidebegin ifendÊàæäûé èíèöèàòîð îòïðàâèë ñîîáùåíèå.Ôàçîâûé àëãîðèòìp is initiator thenr ∈ Outp do send htoki to r ;Sentp := Sentp + 1 end;while minq Recp [q] < D dobegin receive htoki (from neighbor q0 ) ;Recp [q0 ] := Recp [q0 ] + 1 ;if minq Recp [q] ≥ Sentp and Sentp < D thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 endend;decidebegin ifbegin forallendÊàæäûé íå-èíèöèàòîð îòïðàâëÿåò ïåðâîå ñîîáùåíèå âñåìñîñåäÿì ñðàçó ïîñëå ïîëó÷åíèÿ ïåðâîãî ñîîáùåíèÿ îòêàêîãî-íèáóäü ñîñåäà.Ôàçîâûé àëãîðèòìÒåîðåìà î ôàçîâîì àëãîðèòìåÔàçîâûé àëãîðèòì ýòî âîëíîâîé àëãîðèòì.Äîêàçàòåëüñòâî.Ïî êàæäîìó êàíàëó îòïðàâëÿåòñÿ íå áîëåå D ñîîáùåíèé.Çíà÷èò, âñå âû÷èñëåíèÿ àëãîðèòìà çàâåðøàþòñÿ.Ïóñòü γ çàêëþ÷èòåëüíàÿ êîíôèãóðàöèÿ âû÷èñëåíèÿ C .Ñíà÷àëà ïîêàæåì, ÷òî êàæäûé ïðîöåññ îòïðàâèë õîòü îäíîñîîáùåíèå.Ò.ê.

â êîíôèãóðàöèè γ â êàíàëàõ íåò ñîîáùåíèé,Recp [q] = Sentq äëÿ êàæäîãî êàíàëà qp .Êàæäûé èíèöèàòîð îòïðàâèë ñîîáùåíèå.Êàæäûé íå-èíèöèàòîð îòïðàâëÿåò ïåðâîå ñîîáùåíèå âñåìñîñåäÿì ñðàçó ïîñëå ïîëó÷åíèÿ ïåðâîãî ñîîáùåíèÿ.Çíà÷èò, åñëè ñèëüíî ñâÿçíàÿ ñåòü èìååò õîòü îäíîãîèíèöèàòîðà, òî Sentp > 0 äëÿ êàæäîãî óçëà p .Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Äîïóñòèì, ÷òî ó ïðîöåññà p â êîíôèãóðàöèè γ ïåðåìåííàÿ Sentèìååò íàèìåíüøåå çíà÷åíèå, ò.å. Sentq ≥ Sentp äëÿ âñåõ q . ÷àñòíîñòè, ýòî âåðíî äëÿ âñåõ ïðîöåññîâ q , ÿâëÿþùèõñÿñîñåäÿìè p íà âõîäå.Òîãäà èç ðàâåíñòâà Recp [q] = Sentq ñëåäóåòminq Recp [q] ≥ Sentp .Ôàçîâûé àëãîðèòìp is initiator thenr ∈ Outp do send htoki to r ;Sentp := Sentp + 1 end;while minq Recp [q] < D dobegin receive htoki (from neighbor q0 ) ;Recp [q0 ] := Recp [q0 ] + 1 ;if minq Recp [q] ≥ Sentp and Sentp < D thenbegin forall r ∈ Outp do send htoki to r ;Sentp := Sentp + 1 endend;decidebegin ifbegin forallendÇíà÷èò, Sentp = D , ò.ê.

â ïðîòèâíîì ñëó÷àå p ïðèøëîñü áûîòïðàâëÿòü äîïîëíèòåëüíîå ñîîáùåíèå, êàê òîëüêî îí âïîñëåäíèé ðàç ïîëó÷èë íåêîòîðîå ñîîáùåíèå.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Äîïóñòèì, ÷òî ó ïðîöåññà p â êîíôèãóðàöèè γ ïåðåìåííàÿ Sentèìååò íàèìåíüøåå çíà÷åíèå, ò.å. Sentq ≥ Sentp äëÿ âñåõ q . ÷àñòíîñòè, ýòî âåðíî äëÿ âñåõ ïðîöåññîâ q , ÿâëÿþùèõñÿñîñåäÿìè p íà âõîäå.Òîãäà èç ðàâåíñòâà Recp [q] = Sentq ñëåäóåòminq Recp [q] ≥ Sentp .Çíà÷èò, Sentp = D ; â ïðîòèâíîì ñëó÷àå p ïðèøëîñü áûîòïðàâëÿòü äîïîëíèòåëüíîå ñîîáùåíèå, êàê òîëüêî îí âïîñëåäíèé ðàç ïîëó÷èë íåêîòîðîå ñîîáùåíèå.Çíà÷èò, Sentp = D äëÿ âñåõ p , è, ñëåäîâàòåëüíî, äëÿ âñåõêàíàëîâ qp èìååò ìåñòî ðàâåíñòâî Recp [q] = D .Îòñþäà çàêëþ÷àåì, ÷òî êàæäûé ïðîöåññ ïðèíÿë ðåøåíèå.Ôàçîâûé àëãîðèòìÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî âñÿêîìó ðåøåíèþ ïðåäøåñòâóåò õîòü îäíîñîáûòèå â êàæäîì èç ïðîöåññîâ.Ðàññìîòðèì ïóòü â ñåòè P = p0 , p1 , .

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов лекций