|
Algoritmlar va berilganlar strukturasi
|
| Sana | 25.05.2023 | | Hajmi | 1.46 Mb. | | #64804 |
Bog'liq 4 modul struktura Axborot xati konf. ADU, Mayers- Briggs qo\'shimcha, 36-qo\'shma qaror, 27.04.2022, Oila tushunchasi, uning turlari va shakillari, fHy1I56Pj1m1Sqci4f9q3e28B9S0AiBM, dars ishlanma, 11-21-ALGORITMIK TILLAR VA DASTURLASH, Мустақил ишни ташкиллаштириш, Иқтибослик учун, Документ Microsoft Word, Calendar plan-RAQAMLI VA AXBOROT TEXNOLOGIYALARI (2), статья, Исмаилова Н С , Шагазатов У У Жахон иқтисодиёти ва халқаро (1), A5
O‘ZBEKISTON RESPUBLIKASI OLIY VA O‘RTA MAXSUS TA’LIM VAZIRLIGI
MIRZO ULUG‘BEK NOMIDAGI MILLIY UNIVERSITETININIG
JIZZAX FILIALI
AMALIY MATEMATIKA FAKULTETI
«KOMPYUTER ILMLARI VA DASTURLASHTIRISH» kafedrasi
“ALGORITMLAR VA BERILGANLAR STRUKTURASI” FANIDAN
4-Amaliy ish
Bajardi: “Kompyuter ilmlari va dasturlash texnologiyalari” yo‘nalishi
2-kurs 10-21-guruh talabasi Norpulatov Aziz
Tekshirdi: Ulug`murodov SH.B.
TOPSHIRIQ 10
19-VARIANT
SAVOL:
Quyida berilgan graflardan har bir talaba jurnaldagi tartib raqamiga mos bolgan
grafni tanlab olib, G graf boyicha BFS va DFS algoritmlarini qo’llab,
dastur Samaradorligi(Time and Space complexity ga ko’ra)ni Big O notation
bo’yicha baholab bersin!
BFS Algoritmi
Bu kodda, "graph" argumenti ko'rsatilgan ko'plik yoki grafikni ifodalaydi. "start" argumenti esa boshlang'ich elementni ko'rsatadi.
"visited" seti, ko'rsatilgan elementlarni saqlash uchun yordam beradi, "queue" yordamida esa "visited" seti bilan bog'liq bo'lmagan elementlarni saqlash uchun ishlatiladi.
Birinchi navbatda, boshlang'ich element "visited" setiga qo'shiladi va "queue" yordamida saqlanadi. Keyin esa, "while" sikli yordamida "queue" yordamidagi elementlar ko'rsatiladi. Elementning grafning to'g'ri yo'nalishiga bo'lgan kirishlari "visited" yordamida saqlanadi va "queue" yordamida saqlanadi.
"while" siklidan chiqib keta olmaganligi uchun, algoritm har bir ko'plik (grafik) elementini bitta marta ko'rib chiqish mumkin.
Shu bilan birga, BFS algoritmi vaqt va xotira complexity si O(V) ga tengdir.Yani vertekslar soniga teng.
DFS Algoritmi
Bu kodda "graph" argumenti ko'rsatilgan ko'plik yoki grafikni ifodalaydi. start" argumenti esa boshlang'ich elementni ko'rsatadi. "visited" seti, ko'rsatilgan elementlarni saqlash uchun yordam beradi. Agar "visited" yordamiga qiymat berilmagan bo'lsa, u yerini "None" qo'ymoq mumkin. Bu, "visited" yordamining birinchi marta chaqirilganda bo'sh bo'lib qolmasligi uchun kerakli bo'ladi.
"dfs" funksiyasi rekursiv shaklda yozilgan. Boshlang'ich element "visited" setiga qo'shiladi va print() yordamida konsolga chiqariladi. Keyin esa, elementning barcha kirishlariga bo'lgan yo'nalishlarida yuriladi. Bunday ko'plik kirishlaridan har biri "visited" yordamida bor yo'qligiga qarab tekshiriladi. Agar kirish "visited" yordamida bo'lmasa, "dfs" funksiyasi kirishga qarab yuriladi.
"dfs" funksiyasining qirqovulning to'g'ri yo'nalishiga bo'lgan kirishlarini tekshirish uchun ishlatilgan "if" yordami va bitta kirish uchun yurilgan rekursiv qismi ko'rib chiqishni amalga oshirish uchun, DFS algoritmi har bir ko'plik elementini bitta marta ko'rib chiqish mumkin.
BFS algoritmi kabi, DFS algoritmi ham har bir kirishni bitta marta ko'rib chiqadi, shuning uchun vaqt va xotira complexity si ham O(V) ga tengdir. Bundaham vertekslar soniga bogliq.
Natija
11- Topshiriq
Savol:
10-topshiriq. Berilgan misollarni o’z tartib raqamingizdagini tanlab olasizla. Hisoblash ketma-ketligini Li algoritmiga ko’ra amalga oshiring va yo’lingizni ham istalgan dasturlash muhitida ko’rsating?
19-variant
Excel:
12- Topshiriq
Savol:
Berilgan misollarni Dijkstra, Floyd-Uorshell va Ford-Bellman
algoritmiga koʻra hisoblang.
19-variant
Dijkstra algaritmi:
Natija:
|
| |
