9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja

9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari.


Reja:

1. 
   To`liq graf aylanishining algoritmi
   
2. 
   Torning aylanish algoritmi.
   
3. 
   Giperkub aylanishi algoritmi.
   
4. 
   Tarri algoritmi.
   
5. 
   Tanlash algoritmini aniqlash. Siljitish algoritimi va uni ishlashini misolda ko’rsatish.
   
6. 
   Halqa topologiyali kompyuter tarmoqlarida algoritimlar (Chang-Roberts algoritmi).
   

Tayanch iboralar. Aylanish algoritmi, marker, to’liq graf, so’roq algoritmi, aylanish tartibi, Tarri algoritmi, Chang-Roberts algoritmi, tanlash algoritmi, siljitish algoritmi, koordinator veb-sayt, algoritm, o’z-o’zini tashkil qilish, axborotni baholash, qiymati, qayta ishga tushurish, muvofiqlashtirish, daraxt jarayon, ID Boolean span.

1. 
   To`liq graf aylanishining algoritmi
   

Aylanish algoritmi deb, quyidagi uch xususiyatga ega bo`lgan algoritmga aytiladi.

1. 
   Har bir hisoblashda bitta sayt – initsiator bitta xabar yuborib, algoritm bajarilishini boshlaydi.
   
2. 
   Sayt jarayoni xabar qabul qilgach yo keyingilarga xabar yuboradi yoki return (OK) jarayonini bajaradi.
   
3. 
   Algoritm initsiatorda tugatiladi va bu vaqtda har bir sayt jarayoni hech bo`lmaganda bir marta xabar yuboradi.
   

Birinchi ikki xususiyatdan ko`rinib turibdiki, har bir hisoblashda bitta jarayon qaror qabul qiladi. Aytishlaricha algoritm bu jarayonda tugaydi.
Aylanish algoritmida har bir erishilgan konfiguratsiyada bitta xabar yuboriladi yoki biron jarayon qaror qabul qilib, hali yubormagan bo`ladi. Abstrakt nuqtai nazaridan xabar va hisoblash birgalikda olinganda yaxlit obyekt (marker) deb qarash mumkin, shuningdek u jarayondan jarayonga ko`chadi, bu bilan uni butun jarayonlarni kezib chiqadi deyish mumkin. Keyingi ma`ruzada aylanish algoritmlari tanlov algoritmlari qurilishida foydalaniladi va buning uchun nafaqat bir to`lqindagi markerlarning otishining umumiy sonini bilish kerak, balki birinchi k jarayonga nechta jarayondan o`tish kerakligini ham bilish kerak.
To`liq graf uchlar o`rtasidagi barcha mumkin bo`lgan aloqalarni o`zida mujassamlashtirgan. n to`liq grafda tugunlar soni bo`lsin. This – initsiator tuguniga bog`liq ravishda to`liq grafning qolgan ko`plab uchlarini biriktiramiz: {u<sub>1</sub>, u<sub>2</sub>, .., u<sub>n – 1</sub>}.
To`liq grafdan so`roqlar ketma – ketligi yo`li bilan o`tish mumkin. Algoritm oldingi ma`ruzadagi algoritmga o`xshash bo`lishi mumkin, lekin bunda bir harakatda faqat bitta initsiator qo`shni so`ralishi mumkin. Qachonki bir qo`shnidan javob qabul qilinsa keyingisiga o`tiladi. Bu ko`rinishda (2i – 1) raqamli xabar - bu u<sub>i</sub> , а sayti uchun so`roqdir, 2iraqamli xabar esa bu saytning javobidir. Butun vaqt davomida (2i – 1) xabarlar almashinuvi amalga oshiriladi.
Ketma – ket so`roq algoritmi.
Initsiator – saytning jarayoni.