|
Mustaqil ish bajardi: Jaxonqulov Xumoyun. Tekshirdi: Amirsaidov Ulug’bek
|
| Sana | 20.05.2024 | | Hajmi | 89,98 Kb. | | #246761 |
Bog'liq 5 baho 5
O‘ZBEKISTON RESPUBLIKASI RAQAMLI TEXNOLOGIYALARI VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
“Radio va mobil aloqa tizimlari “ fakulteti
“Kompyuter tarmoqlari” fani bo’yicha
MUSTAQIL ISH
Bajardi:Jaxonqulov Xumoyun.
Tekshirdi:Amirsaidov Ulug’bek.
Toshkent 2023
MUSTAQIL ISH
Router-bu ikki yoki undan ortiq tarmoq interfeysiga ega bo'lgan va tarmoqning turli segmentlari o'rtasida ma'lumotlar paketlarini yuboradigan ixtisoslashgan tarmoq kompyuteri. Router turli xil arxitekturalarning heterojen tarmoqlarini ulashi mumkin. Paketlarni yo'naltirish to'g'risida qaror qabul qilish uchun tarmoq topologiyasi to'g'risidagi ma'lumotlar va ma'mur tomonidan belgilangan ba'zi qoidalar qo'llaniladi. Odatda, yo'riqnoma paket sarlavhasida ko'rsatilgan qabul qiluvchining manzilidan foydalanadi va marshrutlash jadvalidan ma'lumotlarni uzatish yo'lini belgilaydi. Agar manzil uchun marshrutlash jadvalida tavsiflangan marshrut bo'lmasa, paket tashlanadi.
Masalan, jo'natuvchining manzili, ishlatilgan yuqori darajadagi protokollar va tarmoq darajasidagi paket sarlavhalarida mavjud bo'lgan boshqa ma'lumotlar ishlatilganda paketlarni yo'naltirish yo'nalishini aniqlashning boshqa usullari mavjud. Ko'pincha marshrutizatorlar jo'natuvchi va qabul qiluvchining manzillarini tarjima qilishlari, kirishni cheklash uchun ma'lum qoidalar asosida tranzit ma'lumotlar oqimini filtrlashlari, uzatilgan ma'lumotlarni shifrlash/parolini ochishlari va h. k.
Deykstra algoritmi-1959 yilda niderlandiyalik olim E. Deykstroy tomonidan ixtiro qilingan graflardagi algoritm. Algoritm grafning eng qisqa yo'llaridan biridan qolganlariga qadar eng qisqa yo'llarni topadi. Algoritm faqat salbiy og'irlikdagi qirralarsiz grafikalar uchun ishlaydi. Dasturlash va texnologiyalarda keng qo'llaniladi, masalan, OSPF va IS-IS marshrutlash protokollari undan foydalanadi.
Algoritm bosqichma - bosqich ishlaydi-har bir qadamda u bitta tepalikka "tashrif buyuradi" va teglarni kamaytirishga harakat qiladi. Algoritmning ishlashi barcha cho'qqilarga tashrif buyurilganda tugaydi. A cho'qqisining o'zi 0 ga, qolgan cho'qqilarning belgisi cheksizlikka to'g'ri keladi. Bu a dan boshqa cho'qqilargacha bo'lgan masofalar hali noma'lum ekanligini aks ettiradi. Grafaning barcha tepalari tashrif buyurilmagan deb belgilanadi.
Agar barcha tepaliklar tashrif buyurilsa, algoritm tugaydi. Aks holda, hali tashrif buyurilmagan cho'qqilardan minimal yorliqli cho'qqi tanlanadi. Qovurg'alar olib boradigan cho'qqilar bu cho'qqining "qo'shnilari" deb ataladi. Har bir tepalik qo'shnisi uchun, tashrif buyurilganlardan tashqari, joriy yorliq qiymatlari yig'indisiga teng bo'lgan yangi yo'l uzunligini va cho'qqini shu qo'shni bilan bog'laydigan chekka uzunligini ko'rib chiqing. Agar olingan uzunlik qiymati qo'shni belgisi qiymatidan kam bo'lsa, biz yorliq qiymatini olingan uzunlik qiymati bilan almashtiramiz. Barcha qo'shnilarni ko'rib chiqqandan so'ng, p, biz tepani quyidagicha belgilaymiz
Eng oddiy dasturda d[i] raqamlarini saqlash uchun siz raqamlar qatoridan foydalanishingiz mumkin va elementning u to'plamiga tegishli ekanligini saqlash uchun - mantiqiy o'zgaruvchilar qatori. Algoritm boshida boshlang'ich tepalik uchun masofa nolga teng bo'lishi kerak, qolgan barcha masofalar esa katta musbat son bilan to'ldiriladi (grafadagi maksimal mumkin bo'lgan yo'ldan katta). Bayroqlar qatori nol bilan to'ldirilgan. Keyin asosiy tsikl boshlanadi. Tsiklning har bir bosqichida biz minimal masofa va bayroq nolga teng bo'lgan tepalikni qidiramiz. Keyin biz unga 1-bayroqni o'rnatamiz va unga qo'shni barcha tepaliklarni tekshiramiz. Agar ularda (C) masofa hozirgi cho'qqiga va chekka uzunligiga bo'lgan masofa yig'indisidan katta bo'lsa, unda biz uni kamaytiramiz. Tsikl barcha cho'qqilarning bayroqlari 1 ga teng bo'lganda yoki barcha cho'qqilar 0 ga teng bo'lganda tugaydi. Oxirgi holat, agar g grafigi bog'lanmagan bo'lsa, mumkin.
Dijkstra algoritmi dasturlashda keng qo'llaniladi, chunki u optimal yo'lni topish bilan bog'liq bir qator muammolarni hal qilishga imkon beradi.
15- VARIANT
|
| |
