bo’lib tashlava hukmronlik qilusuli algoritmlar

PPTX 42 sahifa 921,3 KB Bepul yuklash

42 sahifa

FaylHub.uz

Telegram orqali yuklab olish

Hajm 921,3 KB

Fayl turi PPTX

Sahifalar 42

Yangilangan Dek 2025

Sahifa ko'rinishi (5 sahifa)

Pastga aylantiring 👇

1 / 42

“bo’lib tashla va hukmronlik qil” toifasidagi algoritmlar “bo’lib tashla va hukmronlik qil” toifasidagi algoritmlar “bo’lib tashla va hukmronlik qil” toifasidagi algoritmlar reja: bo’lib tashla va hukmronlik qil usuli. kesh xotira bilan ishlash. qo’llanish muammolari. misollar 1. bo’lib tashla va hukmronlik qil usuli dasturlashda, bo’lib tashla va hukmronlik qil — bu algoritmik paradigma bo’lib, bu paradigmaning asosiy g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib tashlab, ularni rekursiv hal qilishdan iborat. bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos holat bo’lishi kerak. barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan iborat bo’ladi: bo’lib tashlash bosqichi. bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi. hukmronlik bosqichi. asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi. birlashtirish bosqichi. bu bosqichda yechilgan kichik qism masalalar qaytib birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi. …

2 / 42

key algoritmi (cooley-tukey algorithm) qiyin masalalarni osonlik bilan yechishga imkon beradi bo’lib tashla va hukmronlik qil paradigmasining afzalliklari bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq ishlaydi. masalan: oddiy saralash bo’lgan bubble sortning tezligi o(n²) bo’lsa, mergesortniki o(n*logn) bunday algoritmlarni parallel hisoblovchi sistemalarda hech qanday o’zgarishsiz ishlatish mumkin bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin. chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni keshni o’zida turib yechish mumkin bo’ladi. haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan, ko’paytirish algoritmlarida) bo’lib tashla va hukmronlik qil paradigmasi kamchiliklari bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va bu ularni ishlashini ma’lum miqdorga sekinlashtiradi. buning ustiga kichik bir xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin. asosiy shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik va ortiqcha xotira ishlatilishiga olib keladi 2. kesh xotira bilan ishlash kesh - bu shaxsiy kompyuter protsessoridan tez-tez …

3 / 42

an bo'lishi mumkin, chunki har safar kimdir besh yil oldin yillik hisobot ostida kerakli hujjatlarni yashirgan bo'lishi mumkin emas, chunki bu vaqt va kuch talab qiladi. aynan shu printsip asosida kesh-xotira ishlaydi. kompyuter darajasida bu nimani anglatadi? aslida shunga o'xshash jarayon. barcha ma'lumotlar shaxsiy kompyuterda ma'lum bir ierarxiyada mavjud. agar ba'zi ma'lumot boshqalarga qaraganda tez-tez talab qilinadigan bo'lsa, ular mos ravishda yaqinroqdir. kesh - bu yuqori tezlikda ishlaydigan xotira, bu sizga protsessorga kerakli ma'lumotlarni tezda olish imkonini beradi, buning natijasida shaxsiy kompyuterning ishlashi sifat jihatidan oshadi. kesh brauzerlar tomonidan ham qo'llaniladi va oddiy tozalash tartibini talab qiladi. kesh [yoki kesh (ingliz tilidagi kesh, fr. ref.rf-da joylashtirilgan cacher - yashirish; talaffuz qilingan - kesh) - tezkor xotira bilan talab qilinishi mumkin bo'lgan ma'lumotni o'z ichiga olgan tezkor kirish bilan, masalan, operatsion. keshdagi ma'lumotlarga kirish tashqi xotiradan ma'lumotni olish yoki uni qayta hisoblashdan ko'ra tezroq, bu esa kirishning o'rtacha vaqtini kamaytiradi. protsessor …

4 / 42

ori)dir. umumiy xotiradan biror narsa o‘qilayotganda yoki unga yozilayotganda ma’lumotlarning nusxa (копия)si kesh-xotiraga ham kiritiladi. agar shu ma’lumotlarning o‘zi yana zarur bo‘lib qolsa, ularni uzoqdan chaqirib olish zarur bo‘lmaydi – ularni buferdan olish ancha tezroq bo‘ladi. kesh-xotiradan foydalanish kompyuter tizimi unumdorligini sezilarli oshirish imkonini berdi. 486-protsessorlar uchun keshlash texnologiyasi birinchi marta qo‘llanilganda, kesh-xotira onalik platasida protsessorga mumkin qadar yaqinroq joylashar edi; bunda sig‘imi katta bo‘lmasa ham, lekin unumdorligi bo‘yicha eng «tez» mikrosxemalardan foydalanishar edi. bugungi kunda kesh-xotira «piramidali» o‘rnatiladi. tezligi bo‘yicha eng tezkor, lekin hajmi bo‘yicha eng kichik birinchi darajali kesh-xotira protsessor kristalli tarkibiga kiradi. ularni protsessor registrlari tayyorlanadigan texnologiya bo‘yicha tayyorlashadi, natijada u juda qimmat, lekin juda tezkor va eng asosiysi ishonchli bo‘lib qoldi. uning o‘lchami atigi bir necha o‘n kbayt bilan o‘lchanadi, lekin u tez ishlov berishda juda katta ahamiyatga ega. ikkinchi daraja kesh-xotirasi protsessorning o‘sha kristallining o‘zida joylashishi mumkin (bu holda u protsessori yadrosi chastotasida ishlaydi). odatda …

5 / 42

bga olmagan holda asimptotik ma'noda keshni optimal ravishda ishlatadigan cache-oblivious algoritmdir. bunday algoritmlar turli xil xotira darajalaridagi kesh hajmidan qat'iy nazar har xil mashinalarda samarali va modifikatsiyasiz ishlaydi. oddiy cache-oblivious algoritmlar: matritsani ko'paytirish, tashqi tartiblash, matritsani transpozitsiyasi va boshqa ba'zi vazifalar. odatda, cache-oblivious algoritmlar “bo’lib tashla va hukmronlik qil” usulidan foydalanadi, bunda vazifa kichik vazifalar va quyi qismlarga bo'linadi. ajratish jarayonida biz kichik vazifalarga ega bo’lamiz. bir muncha vaqt o'tganda, ushbu kichik vazifalar kesh hajmiga moslasha boshlaydi, biz ularning qachon moslashishini bilmaymiz, lekin eng kichik asos o'lchamlarga bo'lishda davom etamiz. keyin kichik vazifa uchun samarali algoritmni qo'llaymiz. shundan so’ng natijalarni asosiy vazifaning mohiyatiga qarab birlashtiramiz. masalan, matritsani ko’paytirishning cache-oblivious algoritmi har bir matritsani to'rtta kichik matritsaga rekursiv ravishda bo'lish orqali hosil bo’ladi. matritsa to’liq holda keshga joylashganda kichik masalalarga mo’ljallangan optimallashtirilgan algoritmdan foydalanamiz, keyinchalik funktsiyalar natijasini matritsaga qo'shamiz. 3. qo’llanish muammolari rekursiya rekursiya deb shundаy kоnstruktsiyagа аytilаdiki, funktsiya o‘zini o‘zi …

Ko'proq o'qimoqchimisiz?

Barcha 42 sahifani Telegram orqali bepul yuklab oling.

To'liq faylni yuklab olish

"bo’lib tashlava hukmronlik qilusuli algoritmlar" haqida

“bo’lib tashla va hukmronlik qil” toifasidagi algoritmlar “bo’lib tashla va hukmronlik qil” toifasidagi algoritmlar “bo’lib tashla va hukmronlik qil” toifasidagi algoritmlar reja: bo’lib tashla va hukmronlik qil usuli. kesh xotira bilan ishlash. qo’llanish muammolari. misollar 1. bo’lib tashla va hukmronlik qil usuli dasturlashda, bo’lib tashla va hukmronlik qil — bu algoritmik paradigma bo’lib, bu paradigmaning asosiy g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib tashlab, ularni rekursiv hal qilishdan iborat. bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos holat bo’lishi kerak. barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan ibor...

Bu fayl PPTX formatida 42 sahifadan iborat (921,3 KB). "bo’lib tashlava hukmronlik qilusuli algoritmlar"ni yuklab olish uchun chap tomondagi Telegram tugmasini bosing.

Teglar: bo’lib tashlava hukmronlik qilu… PPTX 42 sahifa Bepul yuklash Telegram