Лекция 8. Волновые алгоритмы - фазовый_ Финна. Распред. алгоритмы обхода - Тарри_ в глубину_ Авербаха и Сидона (1185658), страница 3
Текст из файла (страница 3)
Ò.ê. p ∈ Incp , äëÿ êàæäîãî ïðîöåññà p âêîíôèãóðàöèè γ âûïîëíÿåòñÿ Incp = P .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.2) Àíàëîãè÷íûì îáðàçîì ìîæíî ïîêàçàòü, ÷òî äëÿ êàæäîéïàðû ïðîöåññîâ p è q âûïîëíÿåòñÿ NIncp = NIncq .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.2) Àíàëîãè÷íûì îáðàçîì ìîæíî ïîêàçàòü, ÷òî äëÿ êàæäîéïàðû ïðîöåññîâ p è q âûïîëíÿåòñÿ NIncp = NIncq .Ïîñêîëüêó êàæäûé ïðîöåññ óñïåë îòïðàâèòü õîòÿ áû îäíîñîîáùåíèå ïî êàæäîìó êàíàëó, äëÿ ëþáîãî ïðîöåññà pâûïîëíÿåòñÿ òðåáîâàíèå ∀q ∈ Inp : recp [q] . Ñëåäîâàòåëüíî,p ∈ NIncp äëÿ êàæäîãî p .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.2) Àíàëîãè÷íûì îáðàçîì ìîæíî ïîêàçàòü, ÷òî äëÿ êàæäîéïàðû ïðîöåññîâ p è q âûïîëíÿåòñÿ NIncp = NIncq .Ïîñêîëüêó êàæäûé ïðîöåññ óñïåë îòïðàâèòü õîòÿ áû îäíîñîîáùåíèå ïî êàæäîìó êàíàëó, äëÿ ëþáîãî ïðîöåññà pâûïîëíÿåòñÿ òðåáîâàíèå ∀q ∈ Inp : recp [q] . Ñëåäîâàòåëüíî,p ∈ NIncp äëÿ êàæäîãî p .Îòñþäà ñëåäóåò, ÷òî NIncp = P äëÿ êàæäîãî ïðîöåññà p .Èç Incp = P è NIncp = P âûòåêàåò, ÷òî Incp = NIncp , è ýòîîçíà÷àåò, ÷òî â êîíôèãóðàöèè γ êàæäûé ïðîöåññ p ïðèíÿëðåøåíèå.Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî ðåøåíèþ dp â ïðîöåññå p ïðåäøåñòâóåòêàêîå-íèáóäü ñîáûòèå â êàæäîì èç ïðîöåññîâ.Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî ðåøåíèþ dp â ïðîöåññå p ïðåäøåñòâóåòêàêîå-íèáóäü ñîáûòèå â êàæäîì èç ïðîöåññîâ.Äëÿ âñÿêîãî ñîáûòèÿ e â ïðîöåññå p îáîçíà÷èì Inc (e) (NInc (e) )çíà÷åíèå Incp (NIncp , ñîîòâåòñòâåííî) ñðàçó ïîñëåîñóùåñòâëåíèÿ e .
Ñëåäóþùèå äâà óòâåðæäåíèÿ îáîñíîâûâàþòñîäåðæàòåëüíûé ñìûñë ìíîæåñòâ Incp è NIncp .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïîêàæåì, ÷òî ðåøåíèþ dp â ïðîöåññå p ïðåäøåñòâóåòêàêîå-íèáóäü ñîáûòèå â êàæäîì èç ïðîöåññîâ.Äëÿ âñÿêîãî ñîáûòèÿ e â ïðîöåññå p îáîçíà÷èì Inc (e) (NInc (e) )çíà÷åíèå Incp (NIncp , ñîîòâåòñòâåííî) ñðàçó ïîñëåîñóùåñòâëåíèÿ e . Ñëåäóþùèå äâà óòâåðæäåíèÿ îáîñíîâûâàþòñîäåðæàòåëüíûé ñìûñë ìíîæåñòâ Incp è NIncp .Óòâåðæäåíèå 1.Åñëè ñóùåñòâóåò ñîáûòèå e ∈ Cq : e f , òî q ∈ Inc (f ) .Óòâåðæäåíèå 2.Åñëè q ∈ NInc (f ) , òî äëÿ âñåõ r ∈ Inq ñóùåñòâóåò ñîáûòèåe ∈ Cr : e f .Àëãîðèòì ÔèííàÓòâåðæäåíèå 1.Åñëè ñóùåñòâóåò ñîáûòèå e ∈ Cq : e f , òî q ∈ Inc (f ) .Îáîñíîâàíèå.Ñàìîñòîÿòåëüíî èíäóêöèåé ïî äëèíå ïðè÷èííî-ñëåäñòâåííîéöåïî÷êè ìåæäó ñîáûòèÿìè e è f .Àëãîðèòì ÔèííàÓòâåðæäåíèå 2.Åñëè q ∈ NInc (f ) , òî äëÿ âñåõ r ∈ Inq ñóùåñòâóåò ñîáûòèåe ∈ Cr : e f .Îáîñíîâàíèå.Ïóñòü aq îáîçíà÷àåò âíóòðåííåå ñîáûòèå â ïðîöåññå q ,ñâÿçàííîå ñ ïåðâûì âûïîëíåíèåì îïåðàòîðàNIncq := NIncq ∪ {q} ïðîöåññîì q .
Ñîáûòèå aq ýòîåäèíñòâåííîå ñîáûòèå, äëÿ êîòîðîãî âûïîëíÿåòñÿ q ∈ NInc (aq ) ,è êîòîðîìó íå ïðåäøåñòâóåò äðóãîå ñîáûòèå a0 ,0óäîâëåòâîðÿþùåå óñëîâèþ q ∈ NInc (a ) . Çíà÷èò,q ∈ NInc (f ) =⇒ aq f .Èç îïèñàíèÿ àëãîðèòìà âèäíî, ÷òî äëÿ êàæäîãî r ∈ Inqíàéäåòñÿ ñîáûòèå e ∈ Cr , ïðåäøåñòâóþùåå aq . Îòñþäàñëåäóåò äîêàçûâàåìîå óòâåðæäåíèå.Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïðîöåññ p ïðèíèìàåò ðåøåíèå òîëüêî òîãäà, êîãäà Incp = NIncp. Ïóñòü dp ýòî ñîáûòèå ðåøåíèÿ â ïðîöåññå p ; òîãäàInc (dp ) = NInc (dp ) .Àëãîðèòì ÔèííàÄîêàçàòåëüñòâî.Ïðîöåññ p ïðèíèìàåò ðåøåíèå òîëüêî òîãäà, êîãäà Incp = NIncp. Ïóñòü dp ýòî ñîáûòèå ðåøåíèÿ â ïðîöåññå p ; òîãäàInc (dp ) = NInc (dp ) .Òåïåðü ìû âèäèì, ÷òî1.
p ∈ Inc (dp ) ;2. èç q ∈ Inc (dp ) ñëåäóåò q ∈ NInc (dp ) , è îòñþäà ïîëó÷àåìInq ⊆ Inc (dp ) .Ïîñêîëüêó ñåòü ñèëüíî ñâÿçíàÿ, ìû ïîëó÷àåì èñêîìîåðàâåíñòâî Inc (dp ) = P .Àëãîðèòìû îáõîäàÎñîáûé èíòåðåñ ïðåäñòàâëÿþò öåíòðàëèçîâàííûå âîëíîâûåàëãîðèòìû, â êîòîðûõ âñå ñîáûòèÿ ëèíåéíî óïîðÿäî÷åíû ïîîòíîøåíèþ ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè, è ðåøåíèåïðèíèìàåò èíèöèàòîð. Âîëíîâûå àëãîðèòìû òàêîãî ðîäàíàçûâàþòñÿ àëãîðèòìàìè îáõîäà .Àëãîðèòìû îáõîäàÎñîáûé èíòåðåñ ïðåäñòàâëÿþò öåíòðàëèçîâàííûå âîëíîâûåàëãîðèòìû, â êîòîðûõ âñå ñîáûòèÿ ëèíåéíî óïîðÿäî÷åíû ïîîòíîøåíèþ ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè, è ðåøåíèåïðèíèìàåò èíèöèàòîð. Âîëíîâûå àëãîðèòìû òàêîãî ðîäàíàçûâàþòñÿ àëãîðèòìàìè îáõîäà .Àëãîðèòìîì îáõîäà íàçûâàåòñÿ àëãîðèòì, îáëàäàþùèéñëåäóþùèìè òðåìÿ ñâîéñòâàìè.Àëãîðèòìû îáõîäàÎñîáûé èíòåðåñ ïðåäñòàâëÿþò öåíòðàëèçîâàííûå âîëíîâûåàëãîðèòìû, â êîòîðûõ âñå ñîáûòèÿ ëèíåéíî óïîðÿäî÷åíû ïîîòíîøåíèþ ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè, è ðåøåíèåïðèíèìàåò èíèöèàòîð.
Âîëíîâûå àëãîðèòìû òàêîãî ðîäàíàçûâàþòñÿ àëãîðèòìàìè îáõîäà .Àëãîðèòìîì îáõîäà íàçûâàåòñÿ àëãîðèòì, îáëàäàþùèéñëåäóþùèìè òðåìÿ ñâîéñòâàìè.1.  êàæäîì âû÷èñëåíèè åäèíñòâåííûé èíèöèàòîð çàïóñêàåòàëãîðèòì, îòïðàâëÿÿ îäíî-åäèíñòâåííîå ñîîáùåíèå.Àëãîðèòìû îáõîäàÎñîáûé èíòåðåñ ïðåäñòàâëÿþò öåíòðàëèçîâàííûå âîëíîâûåàëãîðèòìû, â êîòîðûõ âñå ñîáûòèÿ ëèíåéíî óïîðÿäî÷åíû ïîîòíîøåíèþ ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè, è ðåøåíèåïðèíèìàåò èíèöèàòîð.
Âîëíîâûå àëãîðèòìû òàêîãî ðîäàíàçûâàþòñÿ àëãîðèòìàìè îáõîäà .Àëãîðèòìîì îáõîäà íàçûâàåòñÿ àëãîðèòì, îáëàäàþùèéñëåäóþùèìè òðåìÿ ñâîéñòâàìè.1.  êàæäîì âû÷èñëåíèè åäèíñòâåííûé èíèöèàòîð çàïóñêàåòàëãîðèòì, îòïðàâëÿÿ îäíî-åäèíñòâåííîå ñîîáùåíèå.2. Âñÿêèé ïðîöåññ ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ ëèáîîòïðàâëÿåò ðîâíî îäíî ñîîáùåíèå, ëèáî ïðèíèìàåòðåøåíèå.Àëãîðèòìû îáõîäàÎñîáûé èíòåðåñ ïðåäñòàâëÿþò öåíòðàëèçîâàííûå âîëíîâûåàëãîðèòìû, â êîòîðûõ âñå ñîáûòèÿ ëèíåéíî óïîðÿäî÷åíû ïîîòíîøåíèþ ïðè÷èííî-ñëåäñòâåííîé çàâèñèìîñòè, è ðåøåíèåïðèíèìàåò èíèöèàòîð. Âîëíîâûå àëãîðèòìû òàêîãî ðîäàíàçûâàþòñÿ àëãîðèòìàìè îáõîäà .Àëãîðèòìîì îáõîäà íàçûâàåòñÿ àëãîðèòì, îáëàäàþùèéñëåäóþùèìè òðåìÿ ñâîéñòâàìè.1.
 êàæäîì âû÷èñëåíèè åäèíñòâåííûé èíèöèàòîð çàïóñêàåòàëãîðèòì, îòïðàâëÿÿ îäíî-åäèíñòâåííîå ñîîáùåíèå.2. Âñÿêèé ïðîöåññ ïîñëå ïîëó÷åíèÿ ñîîáùåíèÿ ëèáîîòïðàâëÿåò ðîâíî îäíî ñîîáùåíèå, ëèáî ïðèíèìàåòðåøåíèå.3. Àëãîðèòì çàâåðøàåò ðàáîòó â èíèöèàòîðå, è ê òîìóìîìåíòó, êîãäà ýòî ïðîèñõîäèò, êàæäîìó ïðîöåññó õîòÿ áûîäèí ðàç óäàëîñü îòïðàâèòü ñîîáùåíèå.Àëãîðèòì îáõîäà ïðîèçâîëüíûõ ñåòåéÀëãîðèòì îáõîäà ïðîèçâîëüíûõ ñâÿçíûõ ñåòåéáûë ïðåäëîæåí Òàððè â 1895. Ýòîò àëãîðèòìîïðåäåëÿåòñÿ äâóìÿ ñëåäóþùèìè ïðàâèëàìè.Àëãîðèòì îáõîäà ïðîèçâîëüíûõ ñåòåéÀëãîðèòì îáõîäà ïðîèçâîëüíûõ ñâÿçíûõ ñåòåéáûë ïðåäëîæåí Òàððè â 1895.
Ýòîò àëãîðèòìîïðåäåëÿåòñÿ äâóìÿ ñëåäóþùèìè ïðàâèëàìè.R1. Ïðîöåññ íå ïåðåäàåò ìàðêåð ïî îäíîìó è òîìóæå êàíàëó äâàæäû.Àëãîðèòì îáõîäà ïðîèçâîëüíûõ ñåòåéÀëãîðèòì îáõîäà ïðîèçâîëüíûõ ñâÿçíûõ ñåòåéáûë ïðåäëîæåí Òàððè â 1895. Ýòîò àëãîðèòìîïðåäåëÿåòñÿ äâóìÿ ñëåäóþùèìè ïðàâèëàìè.R1. Ïðîöåññ íå ïåðåäàåò ìàðêåð ïî îäíîìó è òîìóæå êàíàëó äâàæäû.R2. Íå-èíèöèàòîð ïåðåäàåò ìàðêåð ñâîåéðîäèòåëüñêîé âåðøèíå (ñîñåäó, îò êîòîðîãî îíâïåðâûå ïîëó÷èë ìàðêåð) òîëüêî â òîì ñëó÷àå,êîãäà åãî íåâîçìîæíî ïåðåäàòü ïî äðóãèìêàíàëàì ñîãëàñíî ïðàâèëó R1.Àëãîðèòì ÒàððèÈíèöèàòîðHHHHHHHH@@@@@ @@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~HHHHHHHH@@@@@ @@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * HHHHtoc HHH@@@@@ @@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * HHHHHHHtoc~*@@@@@@@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * HHtoc HHHHH*~*~@@@@@@@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*toc~*~@@@@@@@@@@ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@@@@@@@@@@@@toc ~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@@@toc@@@@@@@@@* ~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@*@@@@@@@@@toc@@* ~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@@*@@@@@@@@@@@* * ~~toc~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*@@@ toc@*@@@@@@@@@*@@* * ~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@@*@@@@@@@@toc@*@@* * ~~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@@*@@@@@@@@@*@@* * ~~*~~~ tocÀëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@@*@@toc@@@@@@*@*@@* * ~~*~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@*@*@@@@@@@@*toc@*@@* * ~~*~~~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**@@@*@*@@@@@@@@*@*@@* * ~~*~~*~ tocÀëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*toc*@@@*@*@@@@@@@@**@*@@* * ~~*~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~*toc**@@@*@*@@@@@@@@**@*@@* * ~~*~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~***@* @@*@*@@@@@@@@**@*@@*toc* ~~*~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~***@* @@*@*@@@@@@@@**@*@@* * ~~* * ~~*~toc Àëãîðèòì ÒàððèÈíèöèàòîð~H * *HHHHHHH*~*~**toc* * @@@*@*@@@@@@@@***@*@@** ~~* * ~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~tocH * *HHHHHHH**~*~***@* @@*@*@@@@@@@@***@*@@** ~~* * ~~*~ Àëãîðèòì ÒàððèÈíèöèàòîð~ DECIDE!H * *HHHHHHH**~*~***@* @@*@*@@@@@@@@***@*@@** ~~* * ~~*~ Àëãîðèòì Òàððèusedp [q] : boolinit false for each q ∈ Neighp ;fatherp : process init udef ;Òîëüêî äëÿ èíèöèàòîðà, âûïîëíèòü îäèí ðàç:begin fatherp := p ; choose q ∈ Neighp ;usedp [q] := true ; send tok to q endÄëÿ êàæäîãî ïðîöåññà ïîñëå ïðèåìà tok îò q0 :begin if fatherp = udef then fatherp := q0 ;if ∀q ∈ Neighp : usedp [q] then decideelse if ∃q ∈ Neighp : (q 6= fatherp ∧ ¬usedp [q])then begin choose q ∈ Neighp \ {fatherp } with ¬usedp [q] ;usedp [q] := true ; send tok to qvarendelse beginendendusedp [fatherp ] := true ; sendtokto fatherpÀëãîðèòì ÒàððèÒåîðåìà îá àëãîðèòìå ÒàððèÀëãîðèòì Òàððè ýòî àëãîðèòì îáõîäà.Äîêàçàòåëüñòâî.Òàê êàê ìàðêåð ïåðåäàåòñÿ íå áîëåå ÷åì ïî îäíîìó ðàçó âêàæäîì èç äâóõ íàïðàâëåíèè ïî ëþáîìó êàíàëó, îí ñîâåðøàåòíå áîëåå 2|E | ïåðåõîäîâ, ïîêà àëãîðèòì íå çàâåðøèòñÿ.Àëãîðèòì ÒàððèÒåîðåìà îá àëãîðèòìå ÒàððèÀëãîðèòì Òàððè ýòî àëãîðèòì îáõîäà.Äîêàçàòåëüñòâî.Òàê êàê ìàðêåð ïåðåäàåòñÿ íå áîëåå ÷åì ïî îäíîìó ðàçó âêàæäîì èç äâóõ íàïðàâëåíèè ïî ëþáîìó êàíàëó, îí ñîâåðøàåòíå áîëåå 2|E | ïåðåõîäîâ, ïîêà àëãîðèòì íå çàâåðøèòñÿ.Ò.ê.
êàæäûé ïðîöåññ îòïðàâëÿåò ìàðêåð ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà, òî îí åãî è ïîëó÷àåò ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà.Àëãîðèòì ÒàððèÒåîðåìà îá àëãîðèòìå ÒàððèÀëãîðèòì Òàððè ýòî àëãîðèòì îáõîäà.Äîêàçàòåëüñòâî.Òàê êàê ìàðêåð ïåðåäàåòñÿ íå áîëåå ÷åì ïî îäíîìó ðàçó âêàæäîì èç äâóõ íàïðàâëåíèè ïî ëþáîìó êàíàëó, îí ñîâåðøàåòíå áîëåå 2|E | ïåðåõîäîâ, ïîêà àëãîðèòì íå çàâåðøèòñÿ.Ò.ê. êàæäûé ïðîöåññ îòïðàâëÿåò ìàðêåð ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà, òî îí åãî è ïîëó÷àåò ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà.Åñëè ìàðêåðîì âëàäååò íå-èíèöèàòîð p , òî ïðîöåññó pïðèøëîñü ïîëó÷àòü ìàðêåð íà îäèí ðàç áîëüøå, ÷åì îòïðàâëÿòüåãî. Çíà÷èò, ÷èñëî êàíàëîâ, èíöèäåíòíûõ p , ïðåâîñõîäèò ÷èñëîêàíàëîâ, èñïîëüçîâàííûõ ýòèì ïðîöåññîì, ïî êðàéíåé ìåðå íà1, è ïîýòîìó p íå ïðèíèìàåò ðåøåíèÿ, à ïåðåäàåò ìàðêåð.Àëãîðèòì ÒàððèÒåîðåìà îá àëãîðèòìå ÒàððèÀëãîðèòì Òàððè ýòî àëãîðèòì îáõîäà.Äîêàçàòåëüñòâî.Òàê êàê ìàðêåð ïåðåäàåòñÿ íå áîëåå ÷åì ïî îäíîìó ðàçó âêàæäîì èç äâóõ íàïðàâëåíèè ïî ëþáîìó êàíàëó, îí ñîâåðøàåòíå áîëåå 2|E | ïåðåõîäîâ, ïîêà àëãîðèòì íå çàâåðøèòñÿ.Ò.ê.
êàæäûé ïðîöåññ îòïðàâëÿåò ìàðêåð ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà, òî îí åãî è ïîëó÷àåò ïî êàæäîìó êàíàëó íåáîëåå îäíîãî ðàçà.Åñëè ìàðêåðîì âëàäååò íå-èíèöèàòîð p , òî ïðîöåññó pïðèøëîñü ïîëó÷àòü ìàðêåð íà îäèí ðàç áîëüøå, ÷åì îòïðàâëÿòüåãî. Çíà÷èò, ÷èñëî êàíàëîâ, èíöèäåíòíûõ p , ïðåâîñõîäèò ÷èñëîêàíàëîâ, èñïîëüçîâàííûõ ýòèì ïðîöåññîì, ïî êðàéíåé ìåðå íà1, è ïîýòîìó p íå ïðèíèìàåò ðåøåíèÿ, à ïåðåäàåò ìàðêåð.Çíà÷èò ðåøåíèå ìîæåò ïðèíÿòü òîëüêî èíèöèàòîð.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Âñå êàíàëû, èíöèäåíòíûå èíèöèàòîðó áûëèèñïîëüçîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Âñå êàíàëû, èíöèäåíòíûå èíèöèàòîðó áûëèèñïîëüçîâàíû ïî îäíîìó ðàçó â êàæäîì íàïðàâëåíèè.Êàæäûé êàíàë áûë èñïîëüçîâàí èíèöèàòîðîì äëÿ ïåðåäà÷èìàðêåðà, èáî â ïðîòèâíîì ñëó÷àå àëãîðèòì íå çàâåðøàåòñÿ.Èíèöèàòîðó ïðèøëîñü ïîëó÷àòü ìàðêåð ñòîëüêî æå ðàç,ñêîëüêî è îòïðàâëÿòü åãî.À ïîñêîëüêó ïîëó÷àòü åãî ïðèõîäèëîñü ïî ðàçíûì êàíàëàì, òîìàðêåð áûë ïîëó÷åí ïî îäíîìó ðàçó ñ èñïîëüçîâàíèåì êàæäîãîêàíàëà.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Äëÿ êàæäîãî ïîñåùåííîãî ìàðêåðîì ïðîöåññàêàíàëû, èíöèäåíòíûåppâñå, èñïîëüçîâàëèñü äëÿ ïåðåäà÷èìàðêåðà â êàæäîì íàïðàâëåíèè ïî îäíîìó ðàçó.Àëãîðèòì ÒàððèÄîêàçàòåëüñòâî.Äëÿ êàæäîãî ïîñåùåííîãî ìàðêåðîì ïðîöåññàêàíàëû, èíöèäåíòíûåppâñå, èñïîëüçîâàëèñü äëÿ ïåðåäà÷èìàðêåðà â êàæäîì íàïðàâëåíèè ïî îäíîìó ðàçó.Äîïóñòèì ïðîòèâíîå.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
