algoritmlarni ishlab chiqish metodlari

PPTX 47 sahifa 438,3 KB Bepul yuklash

47 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 438,3 KB

Fayl turi PPTX

Sahifalar 47

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 47

методы разработки алгоритмов mavzu: algoritmlarni ishlab chiqish metodlari qo'pol kuch usuli ("boshqa") parchalanish usuli muammo hajmini kamaytirish usuli konversiya usuli dinamik dasturlash ochko'z usullar qidiruvni qisqartirish usullari ... © pavlovskaya t.a. (spb nru itmo) 1 misol: tanlash va qabariq turlari © pavlovskaya t.a. (spb nru itmo) 2 28 16 0 29 3 -4 56 -5 to'liq qidiruv to'liq qidiruv - bu kombinatsion muammolarga qo'pol kuch usuli. u taxmin qiladi: muammoni aniqlash sohasidan barcha mumkin bo'lgan elementlarni yaratish muammoli shartlar tomonidan qo'yilgan cheklovlarni qondiradiganlarni tanlash kerakli elementni qidirish (masalan, masalaning maqsad funktsiyasi qiymatini optimallashtirish). misollar: sayohatchi sotuvchi muammosi : berilgan n shahar orqali eng qisqa yo'lni toping , shunda har bir shaharga faqat bir marta tashrif buyuriladi va yakuniy manzil boshlang'ich nuqtasi bo'ladi. ryukzak muammosi : ma'lum og'irlik va narxdagi n dona berilgan, og'irlikni ko'tara oladigan ryukzak w. maksimal xarajat bilan xalta yuklang. bular np-qiyin muammolardir (ularni polinom vaqtida hal qiladigan …

2 / 47

ni ko'rib chiqishni , bunday narsalar to'plamini amalga oshirish mumkin yoki yo'qligini (ya'ni, uning umumiy og'irligidan oshib ketishini) bilish uchun ularning har birining umumiy og'irligini hisoblashni o'z ichiga oladi. ryukzakning imkoniyatlari ) va tegishlilardan tanlash maksimal og'irlikdagi kichik to'plamlar. to'liq qidiruv barcha muammolar uchun amaliy emas, lekin uni qo'llash mumkin bo'lgan juda kichik muammolar. 3 parchalanish usuli bu, shuningdek, "bo'l va zabt et" usuli: vazifa namunasi bir xil vazifaning, ideal darajada bir xil o'lchamdagi bir nechta kichikroq nusxalariga bo'linadi. muammoning kichikroq holatlari hal qilinadi (odatda rekursiv, lekin ba'zida kichikroq misollar uchun boshqa algoritm qo'llaniladi). agar kerak bo'lsa, dastlabki muammoning echimi kichikroq misollarning echimlarini birlashtirish orqali topiladi. parchalanish usuli parallel hisoblash uchun ideal. © pavlovskaya t.a. (spb nru itmo) 4 algoritmlarni ishlab chiqishning eng mashhur usuli. bir qator juda samarali algoritmlar ushbu umumiy strategiyani amalga oshirishdir. har bir parchalanishga asoslangan algoritm qo'pol kuchga asoslangan algoritmdan ko'ra samaraliroq emas. 4 takroriy parchalanish …

3 / 47

lanish ). shubhasiz, uning eritmasining o'sish tartibi t ( n ) a va b konstantalarining qiymatlariga va f ( n ) funktsiyasining o'sish tartibiga bog'liq. parchalanishga asoslangan ko'plab algoritmlarning samaradorligini tahlil qilish quyidagi teorema bilan sezilarli darajada soddalashtirilgan. 5 asosiy parchalanish teoremasi takrorlanish tenglamasining o'zini yechmasdan algoritmning samaradorlik sinfini belgilashingiz mumkin. ushbu yondashuv bizga noma'lum omillarni aniqlamasdan, eritmaning o'sish tartibini o'rnatishga imkon beradi. © pavlovskaya t.a. (spb nru itmo) 6 (1) birlashtirish tartibi berilgan massivni ikkiga bo‘lish, har bir yarmini rekursiv tartiblash va ikkita tartiblangan yarmini bitta tartiblangan massivga birlashtirish orqali tartiblaydi: birlashtirish ( a) agar n>1 bo'lsa birinchi yarmi a - > b massiviga a - > ning ikkinchi yarmi c massivga birlashtirish(b) birlashtirish (c) me rg e(b,c,a) // birlashtirish © pavlovskaya t.a. (spb nru itmo) 7 7 © pavlovskaya t.a. (spb nru itmo) 8 birlashtirish ( a) agar n>1 bo'lsa birinchi yarmi a - > b massiviga a …

4 / 47

avlovskaya t.a. (spb nru itmo) 10 (1) d=1 a=2 b=2 n = 2 k uchun olamiz: cw (n) = n log 2 n - n + 1 d – funksiyaning o‘sish tartibini belgilovchi funksiya darajasi f. d=1 a – hal qilinishi kerak bo‘lgan kichik vazifalar soni a=2 b - dastlabki vazifa bo'lingan kichik vazifalar soni. b=2 10 birlashtirish tartibida amalga oshiriladigan asosiy taqqoslashlar soni, eng yomon holatda, har qanday taqqoslashga asoslangan tartiblash algoritmi uchun taqqoslashlarning nazariy minimal soniga juda yaqin. birlashtirishning asosiy kamchiligi qo'shimcha xotiraga bo'lgan ehtiyojdir, uning miqdori kiritilgan ma'lumotlarning hajmiga chiziqli proportsionaldir. © pavlovskaya t.a. (spb nru itmo) 11 tez tartiblash massiv elementlarini massivdagi joylashuviga ko‘ra ajratuvchi birlashma tartiblashdan farqli o‘laroq, tezkor tartiblash massiv elementlarini qiymatlariga ko‘ra ajratadi. © pavlovskaya t.a. (spb nru itmo) 12 28 1 0 29 3 -4 16 56 parchalanish usuliga asoslangan yana bir muhim saralash algoritmi. young hoare ruscha lug'atdagi so'zlarni saralashga urinayotganda …

5 / 47

tlarni o'tkazib yuboradi va havoladan kichik bo'lmagan birinchi elementda to'xtaydi. o'ngdan chapga o'tish (j) havoladan kattaroq elementlarni o'tkazib yuboradi va havoladan katta bo'lmagan birinchi elementda to'xtaydi. agar skanerlash indekslari kesishmasa, biz topilgan elementlarni almashtiramiz va o'tishlarni davom ettiramiz. agar indekslar kesishsa, qo'llab-quvvatlash elementini aj bilan almashtiring © pavlovskaya t.a. (spb nru itmo) 14 14 algoritmni yaxshilash takomillashtirilgan qo'llab-quvvatlash elementini tanlash usullari pastki qatorlar rekursiyani olib tashlash birgalikda bu yaxshilanishlar algoritmning ishlash vaqtini 20-25% ga qisqartirishi mumkin (r. sedgwick ) © pavlovskaya t.a. (spb nru itmo) 15 tez saralashning muhimligiga asoslanib, ko'p yillar davomida urinishlar qilingan asosiy algoritmni takomillashtirish. boshqa yaxshilanishlar qatorida turli tadqiqotchilar tomonidan - qo'llab-quvvatlash elementlarini tanlashning takomillashtirilgan usullari (masalan, uchta elementning medianasiga asoslangan bo'linish, qachonki kabi mos yozuvlar elementi eng chap, eng o'ng va o'rta elementlarning medianasidan foydalanadi pastki qatorlar uchun oddiyroq saralashga o'tish , rekursiv bo'lmagan tez tartiblash deb ataladigan ). ga binoan tez saralash sohasida yetakchi …

Ko'proq o'qimoqchimisiz?

Barcha 47 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"algoritmlarni ishlab chiqish metodlari" haqida

методы разработки алгоритмов mavzu: algoritmlarni ishlab chiqish metodlari qo'pol kuch usuli ("boshqa") parchalanish usuli muammo hajmini kamaytirish usuli konversiya usuli dinamik dasturlash ochko'z usullar qidiruvni qisqartirish usullari ... © pavlovskaya t.a. (spb nru itmo) 1 misol: tanlash va qabariq turlari © pavlovskaya t.a. (spb nru itmo) 2 28 16 0 29 3 -4 56 -5 to'liq qidiruv to'liq qidiruv - bu kombinatsion muammolarga qo'pol kuch usuli. u taxmin qiladi: muammoni aniqlash sohasidan barcha mumkin bo'lgan elementlarni yaratish muammoli shartlar tomonidan qo'yilgan cheklovlarni qondiradiganlarni tanlash kerakli elementni qidirish (masalan, masalaning maqsad funktsiyasi qiymatini optimallashtirish). misollar: sayohatchi sotuvchi muammosi : berilgan n shahar orqali eng qisqa yo'lni top...

Bu fayl PPTX formatida 47 sahifadan iborat (438,3 KB). "algoritmlarni ishlab chiqish metodlari"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: algoritmlarni ishlab chiqish me… PPTX 47 sahifa Bepul yuklash Telegram