Raqamli texnologiyalar

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI
SAMARQAND DAVLAT UNIVERSITETI
AMALIY MATEMATIKA VA INFORMATAK YO’NALISHI
“RAQAMLI TEXNOLOGIYALAR“ FAKULTETI


ALGORITM VA MA’LUMOTLAR STRUKTURASI FANIDAN
Eng qisqa masofa(yo`li) ni topish. Deykstra algoritimi va uni tahlil qilish mavzusida
KURS ISHI

Bajardi: Raqamli texnologiyalar fakulteti

203-guruh talabasi Diyorbek Ismoilov.
Himoya bali: _____________________
Ilmiy rahbar: Nurmamatov Mehriddin
Sana___________________________

Samarqand 2022

Mundarija:
Kurs ishi uchun qo`yilgan mavzu……………….... 3
Reja………………………………………………...3
Kirish………………………………………………4
Algoritm tushinchalari………………………………………….6
Eng qisqa eng uzun yo’l…………….……………..8
Eng qisqa yo’llar masalalarning turlari……………10
Tegishli muammolar………………………………11
Daraxt va unga ekvivalent tushinchalar…………...12
Deykistra algoritmi……………………………….14
Deykistra algoritimi dasturi………………………20
Xulosa…………………………………………….25
Foydalanilgan manba va adabiyotlar ro`yxati…....26
Mavzu: Eng qisqa masofani(yo`lini) topish. Deykstra algoritimi va uni tahlil qilish.
Reja:

1. 
   Kirish
   
2. 
   Eng qisqa va eng uzun yo’l.
   
3. 
   Eng qisqa yo’llar masalalarining turlari.
   
4. 
   Tegishli muammolari va algoritmlar.
   
5. 
   Deykstra algoritimi.
   
6. 
   Xulosa.
   
7. 
   Foydalanilgan adabiyotlar.
   

Kirish
Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma-ketligi algoritm deb ataymiz.
Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o’rganadigan maxsus “Algoritmlar nazariyasi” bo’limi xam mavjud.
Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o’rganish bilan shug'ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo’llanilish sohasini aniqlash mumkin.
Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu shahargacha sayohat qilishning eng qisqa yo'li nima? Bu yigirma daqiqada mo'ljallangan eng qisqa yo'l uchun algoritm. Bir kuni ertalab men yosh yigitlar bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe terastasiga o'tirdik va men buni qila olamanmi yoki yo'qmi deb o'ylagandim va keyinchalik eng qisqa yo'l uchun algoritmni yaratdim. Men aytganimdek, yigirma daqiqalik ixtiro bo'ldi. Darhaqiqat, u 59 yil ichida, uch yil o'tib nashr etildi. Bu kitob hali ham o'qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi bo'lgan sabablardan biri men uni qalam va qog'ozsiz tasvirladim. Keyinchalik bilib oldimki, qalam va qog'ozsiz loyihalashtirishning afzalliklaridan biri deyarli barcha oldini olish mumkin bo'lgan murakkabliklardan qochishingiz kerak. Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan.
- Edzger Deykstra, ACM bilan aloqa, Philip L. Frana, 2001.
Deykstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida eng qisqa yo'l muammosini o'ylab topdi. Uning maqsadi ham hisoblanmaydigan odamlar tushunishi mumkin bo'lgan muammoni va echimni (kompyuter tomonidan ishlab chiqariladigan) tanlash edi. U eng qisqa yo'l algoritmini ishlab chiqdi va undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan transport xaritasi uchun ARMAC uchun amalga oshirdi (64, ya'ni 6 bit shahar raqamini kodlash uchun etarli bo'ladi). Bir yil o'tgach, u institutning navbatdagi kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo'lgan simni kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi deb nomlanadigan algoritmni (avvalroq Jarnikka ma'lum va shuningdek, Primni qayta kashf qilgan) kashf etdi. Deykstra 1959 yilda, Primdan ikki yil keyin va Jarnikdan 29 yil o'tgach algoritmi nashr etdi.