Texnologiyalari va kommunikatsiyalarinirivojlantirish vazirligi muhammad al-xorazmiy nomidagi
Download 37.31 Kb. Pdf ko'rish
|
Muborak
|
O’ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINIRIVOJLANTIRISH VAZIRLIGI MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI Fan: “ Algoritmlarni loyihalash ” Guruh:21-15 Talaba: Omonturdiyeva M Rahbar: Bobonazarov A Reja: Nazariy savollar. 1-Amaliy mashg’ulot topshiriqlari. 2-Amaliy mashg’ulot topshiriqlari 3-amaliy mashg’ulot topshiriqlari Javoblar 1 Ketma-ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari. 2 Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi 3 “Ajrat va hukmronlik qil” tipidagi algoritmlar. 1.1-Ketma-ketliklar, to’plamlar, daraxtlar, graflarni ifodalash usullari. Ketma-ketliklar: Ketma-ketlik, matematikda bir nechta sonlarni bir-biriga qo'shish orqali olingan jamlanmalar bo'lib, ularni ko'rsatish uchun quyidagi usullar ishlatiladi: Tegishli ketma-ketliklar: Odatda, ketma-ketliklarni ifodalash uchun, birinchi had bilan oxirgi hadning o'rtasidan chiqqan yuqori chiziq ko'rsatiladi. Misol uchun, {1, 2, 3,...10} deb ifodalangan ketma-ketlikning o'rta chiziqlari quyidagidek ko'rsatiladi: {1, 2, 3,...|5|...10}. Sintaksisli ketma-ketliklar: Bu usulda ketma-ketlikning har bir a'zosi qavs ichida joylashgan bo'ladi. Masalan: {x | x>0}, bu yerda x>0 sharti bilan barcha musbat sonlar ketma-ketligini bildiradi. To’plamlar: Matematikdagi to’plam – bu sonlarning yig’indisi bo’lib uning ko’rsatish usullari quyidagilar: Sigma notatsiyasi: Sigma notatsiyasi matematikdagi to’plamni ifodalash uchun ishlatiladi. Bu notatsiya quyidagi ko'rinishda bo'ladi ∑(ai), bu yerda i qiymatlari 1 dan n gacha bo'lgan ai sonlarining yig'indisini ifodalaydi. Daraja yoki eksponenta: Daraja yoki eksponenta ham to’plamlarni ko’rsatish uchun ishlatiladi. Misol uchun, ∑(2^i) quyidagi ko'rinishda bo'ladi 2^1 + 2^2 + 2^3 + ... + 2^n. Daraxtlar: Daraxt, matematikada o‘zaro bog‘lanishli elementlarning to‘plami ko‘rinishida ifodalana oladigan struktura sifatida tanimlanadi. Daraxtning tarkibiy elementlari to‘plamlar, ketma-ketliklar va boshqa strukturalar bo‘lishi mumkin. Graf – bu bir nechta ob’ektlarning aloqalarini ko'rsatish uchun ishlatiladigan matematik modellaridir. Ushbu modellarda ob’ektlar (masalan, shaharlar yoki insonlar) nuqtalar bilan nishonlanadi, ularga aloqalar esa chizg‘ichlarni bilan bildiriladi. Grafni turlari quyidagilar: Undirected graph: Bu grafda aloqalar ikki nuqta orasida o'rnatilgan chizgi bilan bildirilishi mumkin va bu chizgilar biron bir xususiyati yo'q. Directed graph: Bu grafda esa aloqalar nusxalari yo'q, ya'ni aloqa bitta nuqta bilan boshlanadi va boshqa nuqtaga yo'naltiriladi. Weighted graph: Bu grafda aloqalar orasida chizgilar bo'lib, ularning uzunligi (yoki og'irligi) mavjud. Bu uzunliklar odatda aloqaning kuchini yoki masofasini bildirish uchun ishlatiladi. 1.2-Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi Kruskal algoritmi, bir grafi dag'ildan keyin uchragan holda eng arzon tayanch daraxtni topish uchun ishlatiladi. Algoritmda, grafdagi barcha birlashmalarni (edge) uzunliklari bo'yicha tartiblash va undan kichikdan kattaga qarab har bir birlashmani qo'shishga urinib chiqiladi. Bu bilan grafdagi barcha tugunlar orasida tarmoqli bosqichlarni yaratish mumkin. Algoritmning asosiy qadamalari quyidagicha ko'rinishga ega: Grafdagi barcha birlashmalarni uzunliklari bo'yicha tartiblash. Birlashmalar ro'yxatidan eng arzonini tanlash. Tanlangan birlashmani grafdan olib tashlang va shu bilan bog'liq tugunlar orasidagi tarmoqli bosqichni yaratish. 2-3 qadamlarni grafdagi tugunlar soni qadar takrorlash. Kruskal algoritmi, eng arzon tayanch daraxtini topish uchun juda samarali va ishonchli hisoblanadi. Shuningdek, u haqiqiy hayotda aks etkazib beruvchi masalalarda ham foydali bo'ladi, masalan telekomunikatsiya tarmoqlarini optimallashtirishda yoki transport sohasida yo'l qurilishi loyihasida. 1.3-“Ajrat va hukmronlik qil” tipidagi algoritmlar. “Ajrat va hukmronlik qil” tipidagi algoritmlar, bir to'plamning yoki ro'yxatning har bir elementini alohida ajratish va har bir elementni boshqa ro'yxatga yoki to'plamga joylashtirish uchun ishlatiladi. Bu algoritm, avvalgi elementni keyinroq keluvchi elementlarga nisbatan saralashda juda foydali bo'ladi. Bu algoritm kuchli va oson hisoblanadi va ko'p qo'llaniladi. Misol uchun, bir ro'yhatdagi sonlar orasida eng katta yoki eng kichik sonni topish uchun "Ajrat va hukmronlik qil" algoritmi ishlatilishi mumkin. Algoritmda ikki asosiy qism mavjud: ajratish (sorting) va hukmronlik (ordering). Ajratish qismi, ro'yhatning barcha elementlarini alohida ajratishga yordam beradi. Hukmronlik qismi esa saralash jarayonini olib boradi. "Ajrat va hukmronlik qil" algoritmi, quyidagi shaklda amalga oshiriladi: Ro'yhatdagi barcha elementlar alohida ajralib chiqariladi. Ajralib chiqarilgan elementlarning ilk ikkisi taqqoslanib, ular orasida eng katta/kichik belgilanadi. Keyinchalik keyingi element taqqoslanib, eng katta/kichiklik belgilangan element bilan taqqoslanadi va ular o'z o'rnida almashtiriladi. Taqqoslanish jarayoni birinchi elementga yetib tugatilguncha to'xtatiladi. So'ngra, ikkinchi elementdan boshlab yana ajratish jarayoni boshlanadi va yuqoridagi jarayon takrorlanadi. "Ajrat va hukmronlik qil" algortimi, ro'yhatlarni saralash uchun juda foydali bo'ladi. Shuningdek, shu algoritm ishlatilarak ro'yhatning uzunligi va elementlarining turiga qarab bir nechta tuzatmalarni bajara olasiz. 1-Amaliy mashg’ulot topshiriqlari Belgilardan iborat massiv berilgan. Massivni Quick sort algoritmi bo’yicha saralang. def quicksort(arr): """ This function implements the Quick sort algorithm to sort a given array in ascending order. """ if len(arr) <= 1: return arr else: pivot = arr[0] left = [] right = [] for i in range(1, len(arr)): if arr[i] < pivot: left.append(arr[i]) else: right.append(arr[i]) return quicksort(left) + pivot + quicksort(right) # Test the function arr = [5, 3, 8, 6, 7, 2] print("Original array:", arr) sortedarr = quicksort(arr) print("Sorted array:", sortedarr) 2-amaliy mashg’ulot topshiriqlari. {a,b,c,d,e} shaharlar berilgan bo’lsa, kommivoyajer masalasini yechish uchun yo’nalishlarning barcha ko’rinishlarini aniqlash dasturini tuzing N = 5 shaharlar = ['a', 'b', 'c', 'd','e'] yo'l = [] for i in range(N): for j in range(i+1, N): for k in range(j+1, N): for l in range(k+1, N): for m in range(l+1, N): yo'l.append([shaharlar[i], shaharlar[j], shaharlar[k], shaharlar[l], shaharlar[m], shaharlar[i]]) for y in yo'l: print(y) 3-amaliy mashg’ulot topshiriqlari Pitsa tarqatuvchi ishchiga shaharning 6 ta nuqtasidan buyurtma tushdi. Pitsa tarqatuvchi hodimga shu buyurtma berilgan nuqtalar orasidagi masofalar ma’lum. U iqtisodiy tomondan va vaqt bo’yicha yutishga harakat qilmoqchi. Unga eng kam masofa bosib o’tgan holda pitsalarni tarqatib chiqishiga yordam bering. Grafning minimal narxli daraxt skletini Prim algoritmi yordamida quring. Kiritilgan ma’lumotlarga ko'ra, bizda shaharning 6 ta nuqtasi bor va ular orasidagi masofalar quyidagicha: | Nuqta | 1 | 2 | 3 | 4 | 5 | 6 | |-------|-----|-----|-----|-----|-----|-----| | Masofa | 7 | 9 | 14 | 15 | 20 | 30 | Biz Prim algoritmini ishlatish orqali minimal narxli daraxt skletini topishimiz mumkin. Algoritmning umumiy qadam-qadamli tavsifi quyidagicha: Bitta boshlang'ich nuqta tanlagan holda, undan boshqa barcha nuqtalarga bo'lgan masofalarni hisoblang. Masofalarning ichidan eng kam (minimal) bo'lganini tanlab, u orqali yangi bir nuqtaga yurish qo'yin. Yangi qo'shilgan nuqtaga yana o'tirib, undan boshqa barcha nuqtalarga bo'lgan masofalarni hisoblang. Qadam-2 va qadam-3 ni takrorlang, toki hamma nuqtalar qo'shilgandan so'ng daraxt skletini hosil qiling. Shu algoritmni kiritishingiz mumkin: Boshlang'ich nuqta sifatida shaharning birinchi nuqtasini tanlaymiz. Barcha masofalarni distances degan ro'yxatga yozamiz. visited degan bo'sh ro'yxat va tree degan bo'sh lug'at yaratamiz. Amalni bajarish funksiyasini yaratamiz. U qadam-1 ni bajaradi, keyin esa qadam-2 va qadam-3 ni takrorlaydi, toki barcha nuqtalar qo'shilib qolgan holda hammasi bir- biriga bog'lanagan daraxt hosil bo'lishini ta'minlaydi: def prim_algorithm(start): distances = [(start, 0)] visited = [] tree = {} while distances: current, weight = distances.pop(0) if current in visited: continue visited.append(current) tree[current] = weight for neighbor, distance in graph[current].items(): if neighbor not in visited: distances.append((neighbor, distance)) distances.sort(key=lambda x: x[1]) return tree 5. Ishni sinab ko'ramiz. Bizda quyidagi daraxt hosil bo'ladi: graph = { 1: {2: 7}, 2: {1: 7, 3: 9}, 3: {2: 9, 4: 14}, 4: {3: 14, 5: 15}, 5: {4: 15,6 :20}, 6 :{5 :20} } print(prim_algorithm(1)) # Natija {(1):0,(2):7,(3):9,(4):14,(5):15,(6):20} Shu yerda tree lug'atida har bir nuqta uchun undan boshqa eng kam masofaga ega bo'lgan nuqta va uning masofasi ko'rsatilgan. Bunda 1-va 6-nuqtalar orasidagi masofa 20 ga teng, chunki ular ikkala uchun ham eng yaxshi hal buyurtma berish bo'lgan. Ishni sinab ko'ring! Download 37.31 Kb. Do'stlaringiz bilan baham: 
|