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

Lekciya 13. Saytlardı shetlep ótiw algoritmları
Joba:

1. 
   Tolıq graftı shetlep ótiw algoritmi
   
2. 
   Tordı shetlep ótiw algoritmi
   

Shetlep ótiw algoritmı tómendegi ush ózgeshelikke iye bolǵan algoritm bolıp tabıladı.
1) hár bir esaplawda algoritmdı ámelge asırıwdı baslaytuǵın bir iniciator- sayt anıq bir xabardı jiberedi.
2) sayt procesi, xabardı qabıllaǵannan keyin yamasa bir xabardı ilgeri jiberedi yamasa return (OK) procedurasın orınlaydı.
3) algoritm iniciator menen juwmaqlanadı jáne bul júz bergende, hár bir sayt procesi keminde bir ret xabar jiberedi.
Birinshi eki ózgeshelikten kelip shıqqan halda, hár bir juwmaqlawshı esaplawda qarar anıq bir processga tuwrı keledi. Algoritm bul processda tawsılǵanlıǵı aytıladı.
Shetlep ótiw algoritmınıń hár qanday múmkin bolǵan konfiguratsiyasida anıq bir xabar uzatıladı yamasa anıq bir process xabar aldı hám ele juwap xabarın jibermadi. Kóbirek abstrakt kózqarastan, esap -kitap daǵı xabarlar bir processdan processga uzatılatuǵın hám sol sebepli barlıq processlerge " keladigan" birden-bir ob'ekt (marker) retinde qaralıwı múmkin. Keyingi bayanatta shetlep ótiw algoritmları tańlaw algoritmların jaratıw ushın isletiledi hám onıń ushın tek bir tolqında markerdiń ulıwma sanın emes, bálki birinshi k processlerine keliw ushın qansha ótiwdi biliw zárúrli bolıp tabıladı.
Tolıq graftı shetlep ótiw algoritmı
Tolıq qanada tóbelikler arasındaǵı barlıq múmkin bolǵan baylanıslar bar. N-túyinlerdiń sanı tolıq ústinde bolsın. Bul túyinge salıstırǵanda bul - iniciator tolıq ústindiń kóplegen basqa vertikalarini ańlatadı : {u1, u2,.., un - 1}.
Tolıq graf izbe-iz soraw arqalı shetlep ótiwi múmkin. Algoritm aldınǵı lekciyaǵa tiyisli algoritmǵa uqsaydı, biraq iniciatorning tek bir qońsılassı bir waqtıniń ózinde juwap beredi. Tek bir qońsılastan juwap alınǵanında, keyingi soraw soraladı. Sonday etip, nomer menen xabar (2 i-1) ui veb - saytı ushın soraw hám 2 i nomeri menen xabar bul sayttıń juwabı bolıp tabıladı. Hámmesi bolıp, atqarıw waqtında 2 (i - 1) xabarları bar.
Izbe-iz izertlew algoritmı :
Iniciator sayt procesi: