Lekciya 13. Saytlardı shetlep ótiw algoritmları Joba: Tolıq graftı shetlep ótiw algoritmi

out (token, k+1) through канал l
end
end

Algoritm qarar marker 2 n júkler keyin ámelge asıriladı, dep kórsetedi. P0 - iniciator hám pk - markerdi (júzimen, k) alǵan process. Hár qanday k < 2 n ushın pk hám pk + 1 belgileri 1 bitda parıq etedi, onıń indeksi l (k) dep ataladı, bul tómendegi shártni qandiradi:

Sebebi hár qanday i < n ushın teń muǵdarda k {0,.. ., 2 n} C l (k) = i, keyin p0 = p2 n hám qarar initiatorda qabıl etiledi. Bunı kórsetiw múmkin pa = pb 2 n| (b - a), bul erda hámme zat P0,.. ..p2 n-1 hár qıylı.
Tarri Algoritmı
Tarri tárepinen óz basımshalıq menen baylanısqan grafikalar ushın shetlep ótiw algoritmı berilgen. Algoritm tómendegi eki qaǵıydaǵa tiykarlanǵan.
1. Process hesh qashan markerdi birdey kanalda eki ret ótkermeydi.
2. 1 qaǵıydasına muwapıq, basqa kanallar arqalı uzatıw múmkin bolmasa, iniciator markerdi ózinden aldınǵı (birinshi ret markerdi alǵan qońsılasqa ) uzatadı.

Tómendegi tekstte jergilikli ózgeriwshiler isletiledi:

pre-ámeldegi processni ámelge asıratuǵın sayt, yaǵnıy marker kelgen sayt;
used [q]- markerdiń ol saytına jiberilganligi belgisi.


var used[q]: boolean init false для всех u  Out(this);
pre : site init udef ;
Iniciator ushın (bir ret ámelge asıriladı ):
begin pre := this ; выбор u  Out(this);
used[u] := true ; out token to u ;
end
S den token alıwda hár bir process ushın :
begin if pre = udef then pre := s;
if  u  Out(this) : used[u]
then return(OK)
else if  u  Out(this): (u  pre & used[u])
then begin выбор u  Out(this) \ {pre} с used[u] ;
used[u] := true ; out token to u
end
else begin used[pre] := true ;