Dinamik dasturlash 2

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

277.1572265625 KB

Ko'chirib olish

MUNDARIJA
Kirish………………………………………………………………………… 2
1-bob. Dinamik dasturlash g’oyasi…………………………………………. 3
1.1 Yechim g‘oyasi: Rekursiv yondashuv………………………………3
1.2 Taqqoslash: Yodlash va Tabulyatsiya……………………………… 8
1.3 Dinamik dasturlash tarixi.....................................................................9
2-bob. Dinamik dasturlash va rekursiyani taqqoslash ...................................10
2.1 Rekursiya va dinamik dasturlashni kiritish ………………………….. 10
2.2 Dinamik dasturlash haqida…………………………………………..11
2.3 Rekursiya haqida ma’lumot………………………………………….1 2
Xulosa………………………………………………………………………….. 20
Foydalanilgan adabiyotlar…………………………………………………… .21
1

Kirish
Ushbu blogning g'oyasi dinamik dasturlash deb ataladigan yangi algoritmni loyihalash
texnikasini muhokama qilishdir. Bu kompyuter fanida muammolarni hal qilishda muhim
yondashuv bo'lib, biz samaradorlikni oshirish uchun vaqt-xotira almashinuvi g'oyasidan
foydalanamiz. Hatto ko'plab texnologiya kompaniyalari o'z intervyularida DP savollarini
berishni yaxshi ko'radilar. Ushbu blogda biz DP bilan bog'liq quyidagi tushunchalarni
o'rganamiz:
 n-Fibonachchini topishning rekursiv yechimi
 Vaqt xotirasi almashinuvidan foydalangan holda samaradorlikni oshirish
 Yuqoridan pastga amalga oshirish (yodlash)
 Pastdan yuqoriga amalga oshirish (jadval)
 Taqqoslash: Yuqoridan pastga va Tabulyatsiya
 Keyinchalik o'rganish uchun tanqidiy tushunchalar
 Yechish uchun tavsiya etilgan muammolar
 Keling, birinchi navbatda n-Fibonachchini topish muammosini muhokama qilaylik.
Rekursiya - bu asosiy holatlarga erishilgunga qadar funktsiya o'zini chaqiradigan jarayon. Va
jarayon davomida murakkab vaziyatlar rekursiv ravishda kuzatiladi va sodda va sodda
bo'ladi. Jarayonning butun tuzilishi daraxtga o'xshaydi. Rekursiya yakuniy bosqichga
etgunga qadar hech qanday qiymatni saqlamaydi (asosiy holat).
Va Dinamik dasturlash asosan oddiy rekursiya bilan solishtirganda optimallashtirishdir.
Asosiy g'oya - asl savolni takrorlanadigan naqshlarga ajratish va keyin natijalarni ko'p sub-
javoblarni saqlash. Shuning uchun, keyin kerak bo'lganda, biz bosqichdan oldingi javoblarni
qayta hisoblashimiz shart emas. Katta O nuqtai nazaridan, ushbu optimallashtirish usuli
odatda vaqt murakkabligini eksponensialdan polinomga qisqartiradi.
2

1-bob. Dinamik dasturlash g’oyasi
1.1 Yechim g‘oyasi: Rekursiv yondashuv
Yuqoridagi takrorlanish munosabati yordamida masalani rekursiv hal qilishimiz mumkin.
Bu erda biz n o'lchamdagi masalani o'lcham (n-1) va o'lcham (n-2) kichik masala yechimi
yordamida hal qilamiz, bu yerda F(0) va F(1) asosiy holatlardir .
Pseudo kod:
int fib (n)
{
if (n == 0 )
return 0
else if (n == 1 )
return 1
else
return fib(n- 1 ) + fib(n- 2 )
}
Murakkablik tahlili:
Yuqoridagi kod birinchi qarashda oddiy ko'rinadi, lekin u haqiqatan ham samarasiz.
Keling, uni tahlil qilamiz va samarasizligining sababini tushunamiz.
Mana rekursiya daraxti diagrammasi:
3

Rekursiya daraxti usulida rekursiv qo'ng'iroqlarning umumiy soni = Rekursiya daraxtidagi
tugunlarning umumiy soni.
Xuddi shunday, agar biz rekursiya daraxtida k darajaga ega bo'lsak, u holda rekursiya
bo'yicha bajariladigan operatsiyalarning umumiy soni = L1 + L2 + L3 ......Lk, bu erda har
qanday Li - i-darajadagi operatsiyalarning umumiy soni. rekursiya daraxti.
Agar diqqat bilan kuzatadigan bo'lsak, quyidagi narsalarni sanab o'tishimiz mumkin:
Biz har bir rekursiv chaqiruvda O (1) operatsiyasini bajaramiz.
Rekursiv qo'ng'iroqlarning umumiy soni eksponent ravishda o'sib bormoqda, chunki biz
daraxtda pastga qarab harakatlanamiz, ya'ni 2, 4, 8, 16 ... va hokazo.
Har bir barg tugunining balandligi (n/2, n) oralig'ida. Shunday qilib, rekursiya daraxtining
umumiy balandligi = O(n) = cn, deb aytishimiz mumkin, bu erda c qandaydir doimiydir.
(O'ylab ko'ring!)
Rekursiv qo'ng'iroqlarning umumiy soni = 1 + 2 + 4 + 8 ...+ 2^cn
= (2^cn - 1) / (2 - 1) (Geometrik qatorlarning yig'indisi formulasidan foydalanish)
= O(2^n)
Vaqt murakkabligi = O(2^n). Bu samarasiz algoritm, chunki vaqt murakkabligi kirish
hajmiga (n) nisbatan eksponent ravishda o'sib bormoqda. Umuman olganda, 30 yoki 50 yoki
70 kabi kichik n qiymati uchun mahsulot ishlab chiqarish juda uzoq vaqt talab etadi.
Keling, 5-Fibonachchini topish uchun rekursiya daraxti yordamida sababni o'rganamiz.
4

Yuqoridagi diagrammadan biz rekursiya davomida bir xil kichik masalalarni qayta-qayta
yechyapmiz, ya'ni Fib(3) 2 marta, Fib(2) 3 marta va hokazo. Agar n ning qiymatini yana
oshirsak, takrorlanuvchi kichik muammolar ham ortadi. Xuddi shu kichik muammoning
takroriy yechimi tufayli bizning vaqt murakkabligimiz n ning eksponensial tartibida.
Eslatma: Yuqoridagi rekursiyada faqat n+1 xil kichik muammolar mavjud. Dinamik
dasturlash g'oyasi
Xuddi shu kichik muammoni qayta-qayta hisoblash o'rniga, biz ushbu kichik muammoga
duch kelganimizda, ushbu kichik muammolarning echimini ba'zi xotirada saqlashimiz
mumkin. Boshqa kichik muammoni hal qilishda ushbu kichik muammo yana paydo
bo'lganda, biz allaqachon saqlangan yechimni xotiraga qaytaramiz. Bu Time-Memory Trade-
Off ning ajoyib g'oyasi bo'lib, biz vaqt murakkabligini yaxshilash uchun qo'shimcha joydan
foydalanamiz.
Keling, dinamik dasturlash yondashuvidan foydalangan holda samarali yechimni muhokama
qilaylik. Dinamik dasturlash masalalarini hal qilishning ikki xil usuli mavjud:
 Yodlash: Yuqoridan pastga
 Jadval: Pastdan yuqoriga
Keling, ushbu ikki atamani tushunaylik:
Yuqoridan pastga: Bu yuqoridagi rekursiv yondashuvning o'zgartirilgan versiyasi bo'lib, biz
qayta hisoblashdan qochish uchun qo'shimcha xotira yoki qidirish jadvalida kichik
muammolar yechimini saqlaymiz.
Pastdan yuqoriga: Bu kichik muammolar yechimini yaratish va yechimni qo'shimcha
xotirada saqlash uchun iterativ yondashuv.
Yechim g‘oyasi: Yuqoridan pastga yondashuv .
Yechim bosqichlari
Turli kichik muammolarning yechimini saqlash uchun biz global massiv yoki N+1
o'lchamdagi qidirish jadvalidan foydalanishimiz mumkin. deylik, F[N+1].
Massivdagi barcha qiymatlarni -1 ga boshlang (chunki Fibonachchi qiymati salbiy bo'lishi
mumkin emas). Bu bizga kichik muammoning yechimi allaqachon hisoblanganmi yoki
yo'qligini tekshirishga yordam beradi.
Rekursiv yechimda quyidagi o'zgartirishni amalga oshirishimiz mumkin:
Agar (F[N] < 0), bu N ning Fibonachchi qiymati hali hisoblanmaganligini anglatadi.
Yechimni rekursiv hisoblab, uni F[N] = fib(N-1) + fib(N-2) jadvalining N-indeksida
saqlashimiz kerak.
Agar (F[N] > 0), F[N] da saqlangan qiymatni qaytaring (chunki biz rekursiya davomida F[N]
ni allaqachon hisoblab chiqqanmiz).
N= 0 va N=1 asosiy holatlardir, chunki biz buning qiymatini allaqachon bilamiz va biz
to'g'ridan-to'g'ri echimni F[0] va F[1] da saqlashimiz mumkin.
5

Pseudo kod:
Initaize an array F[N+ 1 ] with negative values.
int fib (N)
{
if ( F[N] < 0 )
{
if ( N <= 1 )
F[N] = N
else
F[N] = fib(N- 1 ) + fib(N- 2 )
}
return F[N]
}
Murakkablik tahlili
Rekursiv qo'ng'iroqlarning umumiy soni = 2N-1, chunki biz qayta hisoblashlardan qochamiz
va N+1 kichik muammolarni faqat bir marta hal qilamiz.
Vaqt murakkabligi = O(N).
Kosmik murakkablik: kichik muammolar yechimini saqlash uchun qo'shimcha jadval uchun
O(N) .
Tanqidiy kuzatish
Rekursiya n o‘lchamli kattaroq masaladan 0 va 1 o‘lchamdagi asosiy rekursiyaga yuqoridan
pastga o‘tadi. Lekin u natijalarni pastdan yuqoriga qarab saqlaydi, bunda F[0] va F[1]
dastlabki ikkita qiymatdir. jadvalda saqlanadi.
Rekursiv chaqiruvlar tartibi: fib(n)-> fib(n-1)-> fib(n-2) ...-> fib(i)-> fib(i-1)-> fib(i-2) ...->
fib(2)-> fib(1)-> fib(0)
Natijalarni jadvalda saqlash tartibi: F[0]-> F[1]-> F[2] ...-> F[i]-> F[i-1]-> F[i-2] ...-> F[n-2]-
> F[n-1] ->F[n]
Agar siz n=5 uchun rekursiya daraxtini chizsangiz, u shunday ko'rinadi Murakkablik tahlili
Rekursiv qo'ng'iroqlarning umumiy soni = 2N-1, chunki biz qayta tiklanadigan hallardan
qochamiz va N+1 kichik faqat bir marta bajaramiz.
6

Tanqidiy savol: Shunday qilib, murakkab rekursiv yondashuvdan ko'ra, natijalarni jadvalda
saqlash uchun oddiy iterativ yondashuvdan foydalanishimiz mumkinmi? yoki 0 va 1
o'lchamdagi asosiy registrdan n o'lchamdagi kattaroq masalaga yechimni qura olamizmi?
Yechim g‘oyasi: pastdan yuqoriga yondashuv (jadval)Ushbu yondashuvda biz birinchi
navbatda kichikroq muammolarni hal qilamiz, so'ngra n o'lchamdagi kattaroq muammoni
hal qilish uchun kichikroq masalalar natijalarini birlashtiramiz.
Yechim bosqichlari
1. Jadval tuzilishi va hajmini aniqlang: kichikroq kichik muammolar yechimini pastdan
yuqoriga yondashuvda saqlash uchun jadval tuzilishi va uning hajmini aniqlashimiz
kerak.
2. Jadval tuzilishi: Jadval tuzilishi muammoli o'zgaruvchilar soni bilan aniqlanadi. Bu
erda muammoning holati bog'liq bo'lgan faqat bitta o'zgaruvchiga egamiz, ya'ni bu
erda n. (Har bir rekursiv chaqiruvdan keyin n qiymati kamayadi). Shunday qilib, biz
kichik muammolarning echimini saqlash uchun bir o'lchovli massivni qurishimiz
mumkin.
Jadval hajmi: Ushbu jadvalning o'lchami turli xil kichik muammolarning umumiy soni
bilan belgilanadi. Rekursiya daraxtini kuzatadigan bo'lsak, har xil o'lchamdagi jami (n+1)
kichik muammolar bo'lishi mumkin. (O'ylab ko'ring!)
2. Jadvalni asosiy registr bilan boshlang: Biz jadvalni asosiy registrlar yordamida ishga
tushirishimiz mumkin. Bu bizga jadvalni to'ldirishga va kattaroq kichik muammoning
echimini yaratishga yordam beradi. F[0] = 0 va F[1] = 1
3. Jadvalni to'ldirish uchun iterativ tuzilma: Rekursiv yechimning rekursiv tuzilishidan
foydalanib, jadvalni to'ldirish uchun iterativ tuzilmani aniqlashimiz kerak.
 Rekursiv tuzilma: fib(n) = fib(n-1) + fib(n-2)
7

 Iterativ tuzilma: F[i] = F[i-1] + F[i-2]
4. Tugatish va yakuniy yechimni qaytarish: Yechimni pastdan yuqoriga qarab saqlagandan
so'ng, bizning yakuniy yechimimiz massivning oxirgi indeksida saqlanadi, ya'ni F[N] ni
qaytaradi.
Taqqoslash: Yodlash va Tabulyatsiya.
Kodlash qulayligi - Memoizatsiyani kodlash oson, ya'ni natijalarni saqlash uchun massiv
yoki qidirish jadvalini qo'shsangiz kifoya va hech qachon bir xil muammoning natijasini
qayta hisoblamaydi. Ammo jadvalda siz jadvalni to'ldirish uchun tartib yoki iterativ
tuzilmani o'ylab topishingiz kerak.
Tezlik - Memoizatsiya katta rekursiv qo'ng'iroqlar tufayli jadvalga qaraganda sekinroq
bo'lishi mumkin.
Stack Space - Memoizatsiya bilan, agar rekursiya daraxti juda chuqur bo'lsa, sizda stek
maydoni tugaydi, bu esa dasturingizni buzadi.
Kichik muammolarni hal qilish - Jadvalda barcha kichik muammolar kamida bir marta
echilishi kerak, lekin Yodlashda barcha muammolarni umuman hal qilish shart emas,
yodlangan yechim aniq talab qilinadigan kichik muammolarni hal qilishning afzalligiga ega.
Dinamik dasturlash tili yoki Dinamik muammo bilan adashtirmaslik kerak.
Shakl 1. Optimal quyi tuzilma yordamida grafikdagi eng qisqa yo'lni topish; to'g'ri chiziq
bitta qirrani ko'rsatadi; to'lqinli chiziq u bog'laydigan ikkita cho'qqi orasidagi eng qisqa yo'lni
ko'rsatadi (boshqa yo'llar orasida, ko'rsatilmagan, bir xil ikkita cho'qqilarni baham ko'radi);
qalin chiziq boshidan maqsadgacha bo'lgan umumiy eng qisqa yo'ldir.
Dinamik dasturlash ham matematik optimallashtirish usuli, ham kompyuter dasturlash
usulidir. Usul 1950-yillarda Richard Bellman tomonidan ishlab chiqilgan va aerokosmik
muhandislikdan iqtisodiyotgacha bo'lgan ko'plab sohalarda qo'llanilishini topdi.
Ikkala kontekstda bu murakkab muammoni rekursiv usulda oddiy kichik muammolarga
bo'lish orqali soddalashtirishga ishora qiladi. Ba'zi qarorlar bilan bog'liq muammolarni bu
tarzda ajratib bo'lmasa-da, bir necha vaqt oralig'ida bo'lgan qarorlar ko'pincha rekursiv
ravishda ajralib chiqadi. Xuddi shunday, kompyuter fanida, agar muammoni kichik
muammolarga bo'lish va keyin kichik muammolarning optimal echimlarini rekursiv ravishda
topish yo'li bilan optimal tarzda echilishi mumkin bo'lsa, u optimal quyi tuzilishga ega
deyiladi.
Agar kichik muammolar kattaroq muammolar ichida rekursiv tarzda joylashtirilsa, dinamik
dasturlash usullari qo'llanilishi mumkin bo'lsa, u holda kattaroq muammoning qiymati va
kichik muammolarning qiymatlari o'rtasida bog'liqlik mavjud.[1] Optimallashtirish
adabiyotida bu munosabat Bellman tenglamasi deb ataladi.
Matematik optimallashtirish
8

Matematik optimallashtirish nuqtai nazaridan, dinamik dasturlash odatda qarorni vaqt o'tishi
bilan qaror qabul qilish bosqichlari ketma-ketligiga bo'lish orqali soddalashtirishni anglatadi.
Bu V1, V2, ..., Vn qiymat funksiyalari ketma-ketligini aniqlash orqali y ni 1 dan n gacha
bo‘lgan vaqtlarda tizim holatini ifodalovchi argument sifatida amalga oshiriladi. Vn (y) ning
ta'rifi oxirgi n vaqtida y holatida olingan qiymatdir. Oldingi Vi i = n -1, n - 2, ..., 2, 1
qiymatlarini Bellman tenglamasi deb ataladigan rekursiv munosabatdan foydalanib, orqaga
qarab ishlash orqali topish mumkin. i = 2, ..., n, Vi−1 uchun har qanday holatda y Vi dan i −
1 vaqtdagi qarordan olinadigan daromadning oddiy funksiyasini (odatda yig‘indisini) va
yangi vaqtda Vi funksiyasini maksimallashtirish yo‘li bilan hisoblanadi. agar ushbu qaror
qabul qilingan bo'lsa, tizimning holati. Kerakli holatlar uchun Vi allaqachon hisoblanganligi
sababli, yuqoridagi operatsiya ushbu holatlar uchun Vi-1 hosil qiladi. Nihoyat, tizimning
dastlabki holatidagi V1 optimal yechimning qiymati hisoblanadi. Qaror o'zgaruvchilarining
optimal qiymatlari allaqachon bajarilgan hisob-kitoblarni kuzatish orqali birma-bir tiklanishi
mumkin.
1.3 Dinamik dasturlash tarixi .
Dinamik dasturlash atamasi dastlab 1940-yillarda Richard Bellman tomonidan
birin-ketin eng yaxshi qarorlarni topish kerak bo'lgan muammolarni hal qilish
jarayonini tasvirlash uchun ishlatilgan. 1953 yilga kelib, u buni zamonaviy
ma'noga aylantirdi, xususan, kichikroq qarorlar muammolarini kattaroq qarorlar
ichiga joylashtirishga ishora qildi [16] va keyinchalik bu soha IEEE tomonidan
tizim tahlili va muhandislik mavzusi sifatida tan olindi. Bellmanning hissasi
Bellman tenglamasi nomi bilan esga olinadi, bu dinamik dasturlashning markaziy
natijasi bo'lib, optimallashtirish masalasini rekursiv shaklda qayta ko'rsatadi.
Bellman o‘zining “Bo‘ron ko‘zi: avtobiografiya” nomli avtobiografiyasida
dinamik dasturlash atamasining sabablarini tushuntiradi:
Men kuz choragini (1950 yil) RANDda o'tkazdim. Mening birinchi vazifam ko'p
bosqichli qaror qabul qilish jarayonlari uchun nom topish edi. Qiziqarli savol:
"Dinamik dasturlash nomi qaerdan paydo bo'lgan?" 1950-yillar matematik
tadqiqotlar uchun yaxshi yillar emas edi. Vashingtonda Uilson ismli juda qiziq
bir janobimiz bor edi. U Mudofaa vaziri edi va u aslida "tadqiqot" so'zidan
patologik qo'rquv va nafratga ega edi. Men bu atamani oddiy ishlatmayapman;
Men uni aniq ishlataman. Agar odamlar uning huzurida tadqiqot iborasini
ishlatsalar, uning yuzi to'lib-toshgan, qizarib ketgan va zo'ravon bo'lardi. U
matematika atamasi haqida qanday his qilganini tasavvur qilishingiz mumkin.
RAND korporatsiyasi Harbiy havo kuchlarida ishlagan va havo kuchlari Uilsonni
o'zining boshlig'i sifatida egallagan. Shunday qilib, men RAND korporatsiyasida
haqiqatan ham matematika bilan shug'ullanayotganimdan Uilson va havo
kuchlarini himoya qilish uchun nimadir qilishim kerakligini his qildim. Qanday
nom, qanday ismni tanlashim mumkin? Meni birinchi navbatda rejalashtirish,
9

qaror qabul qilish, fikrlash qiziqtirardi. Ammo rejalashtirish turli sabablarga ko'ra
yaxshi so'z emas. Shuning uchun men "dasturlash" so'zini ishlatishga qaror
qildim. Men bu dinamik, bu ko'p bosqichli, vaqt o'zgarib turadi, degan fikrni
qabul qilmoqchi edim. Bir tosh bilan ikkita qushni o‘ldiramiz, deb o‘yladim.
Keling, mutlaqo aniq ma'noga ega bo'lgan so'zni olaylik, ya'ni klassik jismoniy
ma'noda dinamik. Bundan tashqari, u sifat sifatida juda qiziq xususiyatga ega va
bu dinamik so'zni kamsituvchi ma'noda ishlatish mumkin emas. Birlashma
haqida o'ylab ko'ring, bu unga yomon ma'no berishi mumkin. Bu mumkin emas.
Shunday qilib, men dinamik dasturlashni yaxshi nom deb o'yladim. Bu hatto
kongressmen ham e'tiroz bildira olmaydigan narsa edi. Shuning uchun men uni
faoliyatim uchun soyabon sifatida ishlatardim.
10

2-bob.Rekursiya va dinamik dasturlashni taqqoslash .
2. 1 .Rekursiya va dinamik dasturlashni kiritish.
Rekursiya - bu asosiy holatlarga erishilgunga qadar funktsiya o'zini chaqiradigan jarayon.
Va jarayon davomida murakkab vaziyatlar rekursiv ravishda kuzatiladi va sodda va sodda
bo'ladi. Jarayonning butun tuzilishi daraxtga o'xshaydi. Rekursiya yakuniy bosqichga
etgunga qadar hech qanday qiymatni saqlamaydi (asosiy holat).
Va Dinamik dasturlash asosan oddiy rekursiya bilan solishtirganda optimallashtirishdir.
Asosiy g'oya - asl savolni takrorlanadigan naqshlarga ajratish va keyin natijalarni ko'p sub-
javoblarni saqlash. Shuning uchun, keyin kerak bo'lganda, biz bosqichdan oldingi javoblarni
qayta hisoblashimiz shart emas. Katta O nuqtai nazaridan, ushbu optimallashtirish usuli
odatda vaqt murakkabligini eksponensialdan polinomga qisqartiradi.
Rekursion/dinamik dasturlash skriptini qanday yozish kerak
Dinamik dasturlash va rekursiya juda o'xshash
Rekursiya ham, dinamik dasturlash ham boshlang'ichni ishga tushiradigan asosiy holatdan
boshlanadi.
2. Asosiy holatni yozganimizdan so'ng, muammoning mantiqiy oqimidan keyin har qanday
naqshlarni topishga harakat qilamiz. Uni topganimizdan so'ng, biz asosan tugatdik.
3. Asosiy farq shundaki, rekursiya uchun biz hech qanday oraliq qiymatlarni saqlamaymiz,
dinamik dasturlash esa undan foydalanadi.
Keling, Fibonachchi raqami bilan biroz chuqurroq tanishaylik. Odatda F(n) bilan belgilangan
Fibonachchi raqamlari Fibonachchi ketma-ketligi deb ataladigan ketma-ketlikni hosil qiladi,
shunday qilib har bir raqam 0 va 1 dan boshlab oldingi ikkitasining yig'indisidir. Ya'ni,
F[0] = 0 birinchi raqam sifatida
F[1] = 1 bizning ikkinchi raqamimiz sifatida
Va undan keyingi raqamni hisoblash oson:
F[n] = F[n-1] + F[n-2]
Berilgan n bilan F[n] ni qanday topish mumkin?
2.1 Misollar
Agar bu Fibonachchi raqami deb nomlangan narsani birinchi marta eshitayotgan bo'lsa,
tashvishlanmang, bu savolni tushunish uchun bir nechta oson misollar:
Berilgan n = 2, F[2] = F[1] + F[0] = 0 + 1 = 1
Berilgan n = 3, F[3] = F[2] + F[1] = 1+ 2= 3
11

 Ikki yondashuv
 Rekursion yondashuv
Rekursiya yondashuvidan boshlaylik.
Yuqoridagi koddan shuni ko'rishimiz mumkinki, biz qiladigan birinchi narsa har doim asosiy
holatni qidirishdir.
Bunday holda, asosiy holat F[0] = 0 va F[1] = 1 bo'ladi, effektga erishish uchun biz bu ikki
shartni if ostida aniq yozdik.
Va asosiy holatdan so'ng, keyingi qadam, F[n] keyinchalik qanday hosil bo'lishining umumiy
modeli haqida o'ylashdir. Yaxshiyamki, muammo so'rovi allaqachon bizga naqsh berdi:
F[n] = F[n-1] + F[n-2]
Shuning uchun biz shunchaki F(n) = F(n-1) + F(n-2) natijasini qaytarishimiz mumkin.
Yuqoridagi koddan shuni ko'rishimiz mumkinki, biz qiladigan birinchi ish yana asosiy
holatni qidirishdir.
Bunday holda, asosiy holat F[0] = 0 va F[1] = 1 bo'ladi, effektga erishish uchun biz bu ikki
shartni if ostida aniq yozdik.
Asosiy holatni tugatganimizdan so'ng, biz tezroq hisoblash uchun barcha oraliq va
vaqtinchalik natijalarni saqlash uchun bo'sh dinamik dasturlash massivini yaratamiz. n 0 dan
boshlangani uchun biz n+1 uzunlikdagi ro'yxat tuzamiz.
Keyingi qadam, keyinchalik F [n] qanday hosil bo'lishining umumiy modeli haqida
o'ylashdir. Yaxshiyamki, muammo so'rovi allaqachon bizga naqsh berdi:
F[n] = F[n-1] + F[n-2]
Shuning uchun biz shunchaki F(n) = F(n-1) + F(n-2) natijasini qaytarishimiz mumkin. Va
aniqroq bo'lish uchun:
dp[i] = dp[i-2] + dp[i-1]
Va bu aslida rekursiya bilan alohida dinamik dasturlashning asosiy farqidir. Rekursiyada biz
dinamik dasturlashda oraliq natijalarni saqlamaymiz, biz barcha oraliq bosqichlarni
saqlaymiz.
F[4] ni hisoblash uchun biz avval F[2], F[3] ni hisoblaymiz va ularning qiymatini oldindan
tuzilgan DP ro'yxatiga joylashtiramiz.
12

2.2.Dinamik dasturlash haqida .
Dinamik dasturlash algoritmlarning katta sinfi bo'lib, muammolarni echishni
optimallashtirish uchun ishlatiladi. Dinamik dasturlash - bu masalani hal qilish uchun
ehtimolliklarni raqamli tahlil qiladigan, keyin esa nomlangan muammoni hal qiladigan
usullar va usullar.
1905-yillarda Richard Bellman matematik optimallashtirish uchun dinamik dasturlashni
kiritdi; bundan tashqari, bu muammoni hal qilish uchun bir qancha sohalarda ishlab chiqilgan
va ishlatilgan. Ushbu usullarning asosi murakkab muammolarni hal qilishga qaratilgan sodda
kichik muammolarni hal qilish orqali muammolarni hal qilishdir. Ular kichik muammolar
uchun optimal echimlarni izlash orqali butun sahnani soddalashtirdilar, shuning uchun
yakuniy yechimni tushuntirish osonroq bo'ladi.
Dinamik dasturlashda har bir oddiy kichik muammoni hal qilish uchun turli xil algoritmlar
to'plami saqlanadi. Bu kichikroq muammolar murakkab muammo bilan yakunlanadi, degan
tushuncha ostida ishlaydi, shuning uchun kichik muammolar tuzatilgandan so'ng, yakuniy
sahna hal qilinadi. Shunday qilib, ushbu usullardan foydalanish xatolarni kamaytiradi,
chiziqli ishda samaradorlikni ta'minlaydi va yakuniy natija sifatini yaxshilaydi.
Dinamik dasturlash qanday ishlaydi?
Dinamik dasturlash - yakuniy murakkab masalani parchalash uchun kichik muammolarni hal
qilish uchun optimallashtirish usuli. Bu kichikroq muammolar kattaroq bo'lganiga
asoslanadi, shuning uchun kichik muammolar hal qilingandan so'ng, butun sahna
oydinlashadi. Shunday qilib, umumlashtirish uchun dinamik dasturlash kichik muammoni
tanib olish, uni hal qilish va echimlarni saqlash orqali ishlaydi; Shunday qilib, agar muammo
yana yuzaga kelsa, yechimni qayta hisoblashning hojati yo'q.
Turli xil kichik muammolarni hal qilish uchun turli xil algoritmlar to'plami mavjud bo'lsa-da,
lekin ularning ko'pchiligining ishlash usulida naqsh mavjud. Bu jarayonni oltita oddiy
bosqichda umumlashtirish mumkin; ammo, ba'zi kichik muammolar boshqalarga qaraganda
murakkabroq va sohaga ko'ra, ular o'zgarishi mumkin.
Biroq, bu erda har bir qadamning qisqacha tushuntirishi va ularning barchasida nima qilish
kerak: Butun sahna murakkab ko'rinsa, kichikroq muammolarni izlash vaqti keldi. Buni
qilish qiyin, ammo muammo qanday kichik muammolar bo'lishi mumkinligi haqida maslahat
beradi.
2.3.Rekursiya haqida .
Rekursiv usullar dasturchilarga samaraliroq dasturlar yaratish imkonini beradi. Oddiy
so'zlar bilan aytganda, rekursiya, asosan, funktsiya o'zini ma'lum bir buyruqni bajarish uchun
chaqirganda, lekin u biroz murakkabroq bo'lsa-da, chunki nomlangan funktsiya to'g'ri
shakllantirilmaganda, u cheksiz tsiklda ishlaydi va butun dasturiy ta'minot noto'g'ri ishlaydi
va u to'g'ri ishlamaydi.
Shunday qilib, rekursiya qanday ishlashini tushunish uchun, rekursiya qanday ishlashini
tushuntiradigan ba'zi atamalarga aniqlik kiritish kerak.
13

Rekursiv funksiya
Men allaqachon tushuntirdimki, rekursiv usullar o'zini bajarishga chaqiradigan funktsiyadir,
nomlangan funktsiya rekursiv funktsiya nomini oladi. Rekursiv funktsiyaning to'g'ri ishlashi
uchun uni kerak bo'lganda va qachon to'xtatish kerakligini o'zi tanib olish uchun
dasturlashtirilgan bo'lishi kerak.
Rekursiv funktsiya - bu umumiy ma'noda - uch bosqichda ishlaydigan algoritm: kerak
bo'lganda tanib olish, o'zini bajarish va keyin ishlashni to'xtatish. Demak, bu fazalarni
bajarish uchun rekursiv funksiya asosiy va rekursiv holatni aniqlashi kerak.
Rekursiv holat yoki tuzilma. Funktsiya zarur bo'lgan vaqt aniqlangandan so'ng, funktsiya
o'zini chaqiradi va u bajariladi; bu jarayon rekursiv holat sifatida tanilgan, xuddi shunday
oddiy. Endi, rekursiv holat ortidagi "murakkablik" funksiya o'zini chaqirgan momentni
dasturlashdir; keyin bu bajariladi va kichik muammoni to'g'ri hal qiladi.
Asosiy holat yoki holat. Oddiy so'zlar bilan aytganda, bu funktsiyaning tugash nuqtasi deb
aytish mumkin. Funktsiya muvaffaqiyatli bajarilgandan so'ng, buni to'xtatish kerak, aks
holda, funktsiya o'zini tsiklda chaqirish va bajarishda davom etadi va bu erda asosiy holat
yoki shart o'z o'rnini egallaydi. Funktsiya mukammal bajarilgan, shuning uchun bu
muammoni hal qiladi va natijani qaytaradi, keyin funktsiya tugadi.
Rekursiv holat yoki tuzilma. Funktsiya zarur bo'lgan vaqt aniqlangandan so'ng, funktsiya
o'zini chaqiradi va u bajariladi; bu jarayon rekursiv holat sifatida tanilgan, xuddi shunday
oddiy. Endi, rekursiv holat ortidagi "murakkablik" funksiya o'zini chaqirgan momentni
dasturlashdir; keyin bu bajariladi va kichik muammoni to'g'ri hal qiladi.
Asosiy holat yoki holat. Oddiy so'zlar bilan aytganda, bu funktsiyaning tugash nuqtasi deb
aytish mumkin. Funktsiya muvaffaqiyatli bajarilgandan so'ng, buni to'xtatish kerak, aks
holda, funktsiya o'zini tsiklda chaqirish va bajarishda davom etadi va bu erda asosiy holat
yoki shart o'z o'rnini egallaydi. Funktsiya mukammal bajarilgan, shuning uchun bu
muammoni hal qiladi va natijani qaytaradi, keyin funktsiya tugadi.
To'g'ridan-to'g'ri va bilvosita rekursiya
Bu rekursiya haqida gap ketganda e'tiborga olish kerak bo'lgan yana bir muhim holat.
Rekursiya har doim funktsiyaning o'zini chaqirishiga ishora qilsa-da, bu chaqirilish usulida
farq qilishi mumkin, shuning uchun rekursiyaning ikki turi o'rnatiladi: to'g'ridan-to'g'ri va
bilvosita rekursiya.
To'g'ridan-to'g'ri rekursiya. Agar funktsiya to'g'ridan-to'g'ri o'zini chaqirsa va funktsiya buni
amalga oshirish uchun mustaqil bo'lsa, bu to'g'ridan-to'g'ri rekursiyadir.
Bilvosita rekursiya. Agar funktsiya o'zini chaqirish uchun boshqa funktsiyaga (o'zaro
funktsiya chaqiruviga) bog'liq bo'lsa, u bilvosita rekursiya nomini oladi.
14

Dinamik dasturlash yordamida Fibonachchi seriyasi
Faqat yuqoridagi rasmga qarang. Rekursiyada ko'pgina qiymatlar fib (4) kabi qayta-qayta
hisoblab chiqiladi.
Bu 4 uchun Fibonachchi qiymatini hisoblash uchun qo'shimcha ishlov berish xarajatlarini
beradi.
Agar fib(4) uchun hisoblangan qiymatni saqlasak va keyingi safar undan foydalansak nima
bo'ladi?
Bu yerda dinamik dasturlash keladi:
1
2
3
4
5
6
7
8
9
1
0
1
1
1
2 include<stdio.h>
int fib ( int n) {
arrFib[100] = {0};
arrFib[0] = 1;
arrFib[1] = 1;
for ( int i = 2; i<n; i++)
arrFib[i] = arrFib[i-1] + arrFib[i-2];
return arrFib[n-1]
}
void main() {
printf ( "The Fibonacci number for index 6 = %d" ,fib(6));
}
Chiqish:
6 = 8 indeks uchun Fibonachchi raqami
Funktsiyani rekursiv chaqirish o'rniga, biz Fibonachchi seriyasining qiymatini hisoblaymiz
va uni ma'lumotlar bazasi massivida saqlaymiz (memoizatsiya texnikasi).
Bu yerda Dinamik dasturlashda biz xotira maydonini ishlov berish vaqtiga almashtiramiz.
Rekursiya va dinamik dasturlash o'rtasidagi farq
Ushbu ikkita dasturlash atamasi o'rtasidagi farq nima?
Agar siz Fibonachchi dasturining yakuniy natijasiga qarasangiz, rekursiya ham, dinamik
dasturlash ham bir xil ishlarni bajaradi.
Ammo mantiqan ikkalasi ham dasturning amalda bajarilishida farq qiladi.
Rekursiyaga nisbatan dinamik dasturlashning afzalliklari
 Bu rekursiv dasturlash texnikasi bo'lgani uchun u chiziq kodini kamaytiradi.
15

 Dinamik dasturlashdan foydalanishning asosiy afzalliklaridan biri bu biz ilgari
hisoblangan havolalardan foydalanganimiz sababli ishlov berishni tezlashtiradi.
Rekursiyaga nisbatan dinamik dasturlashning kamchiliklari
Bu ma'lum kamchiliklar bilan birga keladi.
 Saqlangan qiymatdan foydalaniladimi yoki yo'qmi, har bir kichik muammoning
hisoblangan natijasini saqlash uchun juda ko'p xotira kerak bo'ladi.
 Ko'pincha, chiqish qiymati saqlanadi va bajarilayotganda keyingi kichik
muammolarda foydalanilmaydi. Bu xotiradan keraksiz foydalanishga olib keladi.
 DPda funksiyalar rekursiv chaqiriladi. Stak xotirasi tobora ortib bormoqda.
Qachon qaysi birini ishlatish kerak?
Birinchidan, DP ortidagi g'oyani tushuning.
Muammoni bir nechta kichik muammolarga ajrating va har bir kichik muammoning
natijasini saqlang.
Agar xuddi shu kichik muammo yuzaga kelsa, uni qayta hisoblash o'rniga, biz ilgari
hisoblangan kichik muammoning eski havolasidan foydalanishimiz mumkin.
Barcha kichik muammolar uchun natijani hisoblab chiqqanimizdan so'ng, yakuniy chiqish
uchun natijani qo'lga kiriting.
Endi dasturingizda nimani ishlatishingiz kerakligini hal qiling.
 Agar kodni bajarish uchun xotirangiz cheklangan bo'lsa va ishlov berish tezligi haqida
tashvishlanmasangiz, rekursiyadan foydalanishingiz mumkin. Masalan. agar siz mobil
ilovani ishlab chiqayotgan bo'lsangiz, ilovangizni bajarish uchun xotira juda
cheklangan.
 Agar siz dasturni tezroq bajarishni istasangiz va xotirada hech qanday cheklovlar
bo'lmasa, dinamik dasturlashdan foydalaning.
Har qanday dasturlash tillarini o'zlashtirmoqchi bo'lsangiz, rekursiya va dinamik dasturlash
juda muhim tushunchalardir.
Bu umumiy tushunchalar va siz deyarli barcha umumiy dasturlash tillarida ko'rishingiz
mumkin. Turli dasturlash tillarida rekursiv funktsiyani belgilash va chaqirishda sintaktik farq
bo'lishi mumkin.
DPni qanday o'rganish va o'zlashtirish kerak?
16

Dinamik dasturlash muammosini hal qilish uchun siz rekursiyani bilishingiz kerak. Rekursiv
muammolarni hal qilishda yaxshi tushuning. Fibonachchi seriyasi rekursiv muammolarning
asosiy misollaridan biridir.
Muammoni kichik muammolarga bo'lish nazariyasi tushunish uchun juda muhimdir. Oraliq
natijalarni massivda saqlashni o'rganing.
Amaliyot uchun dinamik dasturlash rekursiyasiga misollar:
Bular DPning eng asosiy muammolari.
Fibonachchi seriyasi
 Sayohatchi sotuvchi muammosi
 Barcha juftlik eng qisqa yo'l (Floyd-Uorshall algoritmi)
 Dinamik dasturlash yordamida 0/1 sumka muammosi
 Dinamik dasturlash yordamida matritsa zanjiri mahsuloti/ko‘paytirish
 Dinamik dasturlash yordamida eng uzun umumiy ketma-ketlik (LCS).
 Dinamik muammolarning katta ro'yxati mavjud. Muntazam ravishda hal qiling.
Jadvalingizga ko'ra, siz kuniga bitta DP muammosini hal qilishni rejalashtirishingiz mumkin.
Agar ko'proq vaqtingiz bo'lsa, kuniga bir nechta DP muammosini hal qilishga o'tishingiz
mumkin.
Dinamik dasturlash algoritmi va rekursiya o'rtasidagi farq nima?
Dinamik dasturlashda masalalar kattaroqlarini yechish uchun ularni kichikroqlarga
bo‘lish yo‘li bilan yechiladi, rekursiya esa funksiya o‘z-o‘zidan chaqiriladi va bajariladi.
Dinamik dasturlash rekursiya usullaridan foydalanmasdan ishlashi mumkin bo'lsa-da,
dinamik dasturlashning maqsadi jarayonni optimallashtirish va tezlashtirish bo'lganligi
sababli, dasturchilar odatda jarayonni tezlashtirish va samarali aylantirish uchun rekursiya
usullaridan foydalanadilar.
Agar funktsiya o'zini chaqirish orqali ma'lum bir vazifani bajara olsa, rekursiv
funktsiya nomini oling. Ishni bajarish va bajarish uchun bu funktsiya bajarilishi kerak
bo'lganda o'zini chaqiradi.
Dinamik dasturlashdan foydalanib, muammoni hal qilish uchun uni kichikroq
qismlarga ajratishingiz mumkin, ular kichik muammolar deb ataladi. Dinamik dasturlash
muammoni birinchi marta hal qilishni, so'ngra yechimlarni saqlash uchun xotiradan
foydalanishni o'z ichiga oladi.
Shuning uchun, ikkala texnika o'rtasidagi asosiy farq ularning maqsadli qo'llanilishidir;
Rekursiya funktsiyani avtomatlashtirish uchun ishlatiladi, dinamik dasturlash esa
muammolarni hal qilishda qo'llaniladigan optimallashtirish usulidir.
Rekursiv funktsiyalar kerak bo'lganda tan oladi, o'zini bajaradi va keyin ishlashni
to'xtatadi. Funksiya zarur bo'lgan momentni aniqlaganda, u o'zini chaqiradi va bajariladi; bu
rekursiv holat deb ataladi. Natijada, vazifa bajarilgandan so'ng funktsiya to'xtashi kerak, bu
asosiy holat deb nomlanadi.
17

Davlatlarni o'rnatish orqali dinamik dasturlash muammoni tan oladi va butun sahnani
hal qilish uchun uni kichik muammolarga ajratadi. Ushbu kichik muammolarni yoki
o'zgaruvchilarni echgandan so'ng, dasturchi ular o'rtasida matematik aloqani o'rnatishi kerak.
Va nihoyat, bu yechimlar va natijalar algoritmlar sifatida saqlanadi, shuning uchun ularga
kelajakda butun muammoni qayta hal qilmasdan kirish mumkin.
Dinamik dasturlash masalalarini hal qilish usullari:
1. Yuqoridan pastga (Yodda saqlash):
Berilgan muammoni hal qilishni boshlash uchun uni ajratib oling. Muammo allaqachon hal
qilinganligini ko'rsangiz, saqlangan javobni qaytaring. Agar u hal qilinmagan bo'lsa, uni hal
qiling va saqlang. Bu odatda o'ylash oson va juda intuitivdir, bu Yodlash deb ataladi.
2. Pastdan yuqoriga (Dinamik dasturlash):
Muammoni tahlil qiling va kichik muammolar qanday tartibda hal qilinishini ko'ring va
ahamiyatsiz kichik muammodan berilgan masalaga o'ting. Bu jarayon asosiy muammodan
oldin kichik muammolarni hal qilishni ta'minlaydi. Bu dinamik dasturlash deb ataladi.
18

Jadval (dinamik dasturlash) va eslab qolish:
Kichik muammoning qiymatlarini qayta ishlatish uchun qiymatlarni saqlashning ikki xil
usuli mavjud. Bu erda dinamik dasturlash (DP) muammolarini hal qilishning ikkita usuli
muhokama qilinadi:
1-versiya: Men GeeksforGeeks-dan DP nazariyasini o'rganaman, keyin klassik DP bo'yicha
ba'zi muammolarni mashq qilaman va shuning uchun men DPni o'zlashtiraman.
2-versiya: DPni o'zlashtirish uchun men dinamik muammolar va muammolarni mashq
qilishim kerak edi - Birinchidan, GeeksforGeeks-dan DPning ba'zi nazariyalarini o'rganishim
kerak edi.
Ikkala versiya ham bir xil narsani aytadi, farq shunchaki xabarni etkazish usulida yotadi va
bu pastdan yuqoriga va yuqoridan pastga DP aynan shunday qiladi. 1-versiya pastdan
yuqoriga DP bilan bog'liq bo'lishi mumkin va Versiya-2 yuqoridan pastga DP bilan bog'liq
bo'lishi mumkin.
Dinamik dasturlash muammosini qanday hal qilish mumkin?
Muammoni dinamik ravishda hal qilish uchun biz ikkita zarur shartni tekshirishimiz kerak:
Bir-biriga o'xshash kichik muammolar: haqiqiy muammoni hal qilish uchun bir xil kichik
muammolarning echimlari takroran kerak bo'lganda. Muammoning bir-biriga o'xshash kichik
muammolar xususiyati borligi aytiladi.

N-chi Fibonachchi seriyasi bir-biriga mos keladigan kichik muammolar sifatida
N-chi Fibonachchi seriyasi bir-biriga mos keladigan kichik muammolar sifatida
Optimal quyi tuzilma xossasi: Agar berilgan muammoning optimal yechimi uning kichik
muammolarining optimal yechimlari yordamida olinishi mumkin bo'lsa, muammo optimal
quyi tuzilma xossasiga ega deyiladi.
Dinamik dasturlash muammosini hal qilish bosqichlari:
Bu Dinamik dasturlash muammosi ekanligini aniqlang.
Eng kichik parametrlari bilan holat ifodasini aniqlang.
Holat va o'tish munosabatlarini shakllantirish.
Jadval tuzing (yoki yodlash).
1) Muammoni dinamik dasturlash algoritmi muammosi sifatida qanday tasniflash mumkin?
Odatda, ma'lum miqdorlarni ko'paytirish yoki minimallashtirishni talab qiladigan barcha
muammolarni yoki ma'lum sharoitlarda tartiblarni hisoblashni aytadigan hisoblash
masalalarini yoki muayyan ehtimollik muammolarini Dinamik dasturlash yordamida hal
qilish mumkin.
Dinamik dasturlashning barcha muammolari bir-biriga mos keladigan kichik muammolar
xususiyatini va klassik Dinamik dasturlash muammolarining aksariyati optimal quyi tuzilma
xususiyatini ham qondiradi. Berilgan muammoda ushbu xususiyatlarni kuzatganimizdan
so'ng, uni Dinamik dasturlash yordamida hal qilish mumkinligiga ishonch hosil qiling.
19

2) Davlatni aniqlash:
Dinamik dasturlash bilan bog'liq muammolar asosan davlat va uning o'tishi bilan bog'liq. Eng
asosiy bosqich juda ehtiyotkorlik bilan amalga oshirilishi kerak, chunki davlatga o'tish siz
tanlagan davlat ta'rifiga bog'liq.
Davlat:
Shtat - bu ma'lum bir pozitsiyani yoki ma'lum bir qiyinchilikda turishni tavsiflash uchun
ishlatilishi mumkin bo'lgan xususiyatlar to'plami. Davlat maydonini minimallashtirish uchun
ushbu parametrlar to'plami imkon qadar ixcham bo'lishi kerak.
3) Davlatlar o'rtasidagi munosabatlarni shakllantirish:
Dinamik dasturlashning eng qiyin qismi bu juda ko'p sezgi, kuzatish va mashg'ulotlarni talab
qiladigan qadamdir.
Misol:
2 ta raqam {1, 3, 5} berilgan bo lsa, topshiriq berilgan uchta sonning yig indisidanʻ ʻ
foydalanib N sonni qanday qilib hosil qilishimiz mumkinligini aytishdan iborat.
(takrorlash va turli tartibga solishga ruxsat berish).
1+1+1+1+1+1
1+1+1+3
1+1+3+1
1+3+1+1
3+1+1+1
3+3
1+5
5+1
Muammoni hal qilish uchun quyidagi qadamlar mavjud:
 Berilgan muammo uchun holatni tanlaymiz.
 N holat uchun hal qiluvchi omil sifatida ishlatiladi, chunki u har qanday kichik
muammoni aniqlash uchun ishlatilishi mumkin.
 DP holati (N) holatga o'xshaydi, bunda holat (N) 1, 3 va 5 elementlari yordamida N ni
yaratish uchun zarur bo'lgan tartiblarning umumiy sonidir. Har qanday ikki holat
o'rtasidagi o'tish munosabatini aniqlang.
 Endi biz holatni (N) hisoblashimiz kerak.
20

Xulosa.
Dinamik dasturlashda har bir oddiy kichik muammoni hal qilish uchun turli xil
algoritmlar to'plami saqlanadi. Bu kichikroq muammolar murakkab muammo bilan
yakunlanadi, degan tushuncha ostida ishlaydi, shuning uchun kichik muammolar
tuzatilgandan so'ng, yakuniy sahna hal qilinadi. Shunday qilib, ushbu usullardan foydalanish
xatolarni kamaytiradi, chiziqli ishda samaradorlikni ta'minlaydi va yakuniy natija sifatini
yaxshilaydi Dinamik dasturlashda masalalar kattaroqlarini yechish uchun ularni
kichikroqlarga bo‘lish yo‘li bilan yechiladi, rekursiya esa funksiya o‘z-o‘zidan chaqiriladi va
bajariladi. Dinamik dasturlash rekursiya usullaridan foydalanmasdan ishlashi mumkin bo'lsa-
da, dinamik dasturlashning maqsadi jarayonni optimallashtirish va tezlashtirish bo'lganligi
sababli, dasturchilar odatda jarayonni tezlashtirish va samarali aylantirish uchun rekursiya
usullaridan foydalanadilar.
Agar funktsiya o'zini chaqirish orqali ma'lum bir vazifani bajara olsa, rekursiv
funktsiya nomini oling. Ishni bajarish va bajarish uchun bu funktsiya bajarilishi kerak
bo'lganda o'zini chaqiradi.
Dinamik dasturlashdan foydalanib, muammoni hal qilish uchun uni kichikroq
qismlarga ajratishingiz mumkin, ular kichik muammolar deb ataladi. Dinamik dasturlash
muammoni birinchi marta hal qilishni, so'ngra yechimlarni saqlash uchun xotiradan
foydalanishni o'z ichiga oladi.
Rekursiv funktsiyalar kerak bo'lganda tan oladi, o'zini bajaradi va keyin ishlashni
to'xtatadi. Funksiya zarur bo'lgan momentni aniqlaganda, u o'zini chaqiradi va bajariladi; bu
rekursiv holat deb ataladi. Natijada, vazifa bajarilgandan so'ng funktsiya to'xtashi kerak, bu
asosiy holat deb nomlanadi.
21

Foydalanilgan adabiyotlar va
Foydalanilgan internet saytlari
1. Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2001),
Introduction
to Algorithms (2nd ed.), MIT Press & McGraw–Hill, ISBN 0-
262-03293-7 .
pp. 344.
2. ^ Kamien, M. I. ; Schwartz, N. L. (1991). Dynamic Optimization: The
Calculus of Variations and Optimal Control in Economics and
Management (Second ed.). New York: Elsevier. p. 261. ISBN 978-0-
444-01609-6 .
3. ^ Kirk, Donald E. (1970). Optimal Control Theory: An Introduction .
Englewood Cliffs, NJ: Prentice-Hall. pp. 94–95. ISBN 978-0-13-638098-
6 .
4. ^ "M. Memo" . J Vocabulary. J Software . Retrieved 28 October 2011 .
5. ^ DeLisi,
Biopolymers, 1974, Volume 13, Issue 7, pages 1511–1512,
July
1974
6. ^ Gurskiĭ
GV, Zasedatelev AS, Biofizika, 1978 Sep-Oct;23(5):932-46
7. ^ Sniedovich, M. (2006), "Dijkstra's algorithm revisited: the dynamic
programming connexion" (PDF) , Journal of Control and
Cybernetics, 35 (3): 599–620. Online
version of the paper with
interactive
computational modules.
8. ^ Denardo, E.V. (2003), Dynamic Programming: Models and
Applications, Mineola, NY: Dover Publications , ISBN 978-0-486-42810-
9
9. ^ Sniedovich, M. (2010), Dynamic Programming: Foundations and
Principles, Taylor & Francis , ISBN 978-0-8247-4099-3
 https://www.geeksforgeeks.org/introduction-to-dynamic-programming-data-structures-
and-algorithm-tutorials/
 https://towardsdatascience.com/dynamic-programming-i-python-8b20387870f5/
 https://medium.com/swlh/understanding-recursion-memoization-and-dynamic-
programming-3-sides-of-the-same-coin-8c1f57ee5604/
 https://whatsabyte.com/dynamic-programming-vs-recursion-difference/
 https://towardsdatascience.com/dynamic-programming-i-python-
8b20387870f5#:~:text=Recursion%20does%20not%20store%20any,results%20as
%20many%20sub%2Danswers./
22

MUNDARIJA Kirish………………………………………………………………………… 2 1-bob. Dinamik dasturlash g’oyasi…………………………………………. 3 1.1 Yechim g‘oyasi: Rekursiv yondashuv………………………………3 1.2 Taqqoslash: Yodlash va Tabulyatsiya……………………………… 8 1.3 Dinamik dasturlash tarixi.....................................................................9 2-bob. Dinamik dasturlash va rekursiyani taqqoslash ...................................10 2.1 Rekursiya va dinamik dasturlashni kiritish ………………………….. 10 2.2 Dinamik dasturlash haqida…………………………………………..11 2.3 Rekursiya haqida ma’lumot………………………………………….1 2 Xulosa………………………………………………………………………….. 20 Foydalanilgan adabiyotlar…………………………………………………… .21 1

Kirish Ushbu blogning g'oyasi dinamik dasturlash deb ataladigan yangi algoritmni loyihalash texnikasini muhokama qilishdir. Bu kompyuter fanida muammolarni hal qilishda muhim yondashuv bo'lib, biz samaradorlikni oshirish uchun vaqt-xotira almashinuvi g'oyasidan foydalanamiz. Hatto ko'plab texnologiya kompaniyalari o'z intervyularida DP savollarini berishni yaxshi ko'radilar. Ushbu blogda biz DP bilan bog'liq quyidagi tushunchalarni o'rganamiz:  n-Fibonachchini topishning rekursiv yechimi  Vaqt xotirasi almashinuvidan foydalangan holda samaradorlikni oshirish  Yuqoridan pastga amalga oshirish (yodlash)  Pastdan yuqoriga amalga oshirish (jadval)  Taqqoslash: Yuqoridan pastga va Tabulyatsiya  Keyinchalik o'rganish uchun tanqidiy tushunchalar  Yechish uchun tavsiya etilgan muammolar  Keling, birinchi navbatda n-Fibonachchini topish muammosini muhokama qilaylik. Rekursiya - bu asosiy holatlarga erishilgunga qadar funktsiya o'zini chaqiradigan jarayon. Va jarayon davomida murakkab vaziyatlar rekursiv ravishda kuzatiladi va sodda va sodda bo'ladi. Jarayonning butun tuzilishi daraxtga o'xshaydi. Rekursiya yakuniy bosqichga etgunga qadar hech qanday qiymatni saqlamaydi (asosiy holat). Va Dinamik dasturlash asosan oddiy rekursiya bilan solishtirganda optimallashtirishdir. Asosiy g'oya - asl savolni takrorlanadigan naqshlarga ajratish va keyin natijalarni ko'p sub- javoblarni saqlash. Shuning uchun, keyin kerak bo'lganda, biz bosqichdan oldingi javoblarni qayta hisoblashimiz shart emas. Katta O nuqtai nazaridan, ushbu optimallashtirish usuli odatda vaqt murakkabligini eksponensialdan polinomga qisqartiradi. 2

1-bob. Dinamik dasturlash g’oyasi 1.1 Yechim g‘oyasi: Rekursiv yondashuv Yuqoridagi takrorlanish munosabati yordamida masalani rekursiv hal qilishimiz mumkin. Bu erda biz n o'lchamdagi masalani o'lcham (n-1) va o'lcham (n-2) kichik masala yechimi yordamida hal qilamiz, bu yerda F(0) va F(1) asosiy holatlardir . Pseudo kod: int fib (n) { if (n == 0 ) return 0 else if (n == 1 ) return 1 else return fib(n- 1 ) + fib(n- 2 ) } Murakkablik tahlili: Yuqoridagi kod birinchi qarashda oddiy ko'rinadi, lekin u haqiqatan ham samarasiz. Keling, uni tahlil qilamiz va samarasizligining sababini tushunamiz. Mana rekursiya daraxti diagrammasi: 3

Rekursiya daraxti usulida rekursiv qo'ng'iroqlarning umumiy soni = Rekursiya daraxtidagi tugunlarning umumiy soni. Xuddi shunday, agar biz rekursiya daraxtida k darajaga ega bo'lsak, u holda rekursiya bo'yicha bajariladigan operatsiyalarning umumiy soni = L1 + L2 + L3 ......Lk, bu erda har qanday Li - i-darajadagi operatsiyalarning umumiy soni. rekursiya daraxti. Agar diqqat bilan kuzatadigan bo'lsak, quyidagi narsalarni sanab o'tishimiz mumkin: Biz har bir rekursiv chaqiruvda O (1) operatsiyasini bajaramiz. Rekursiv qo'ng'iroqlarning umumiy soni eksponent ravishda o'sib bormoqda, chunki biz daraxtda pastga qarab harakatlanamiz, ya'ni 2, 4, 8, 16 ... va hokazo. Har bir barg tugunining balandligi (n/2, n) oralig'ida. Shunday qilib, rekursiya daraxtining umumiy balandligi = O(n) = cn, deb aytishimiz mumkin, bu erda c qandaydir doimiydir. (O'ylab ko'ring!) Rekursiv qo'ng'iroqlarning umumiy soni = 1 + 2 + 4 + 8 ...+ 2^cn = (2^cn - 1) / (2 - 1) (Geometrik qatorlarning yig'indisi formulasidan foydalanish) = O(2^n) Vaqt murakkabligi = O(2^n). Bu samarasiz algoritm, chunki vaqt murakkabligi kirish hajmiga (n) nisbatan eksponent ravishda o'sib bormoqda. Umuman olganda, 30 yoki 50 yoki 70 kabi kichik n qiymati uchun mahsulot ishlab chiqarish juda uzoq vaqt talab etadi. Keling, 5-Fibonachchini topish uchun rekursiya daraxti yordamida sababni o'rganamiz. 4

Yuqoridagi diagrammadan biz rekursiya davomida bir xil kichik masalalarni qayta-qayta yechyapmiz, ya'ni Fib(3) 2 marta, Fib(2) 3 marta va hokazo. Agar n ning qiymatini yana oshirsak, takrorlanuvchi kichik muammolar ham ortadi. Xuddi shu kichik muammoning takroriy yechimi tufayli bizning vaqt murakkabligimiz n ning eksponensial tartibida. Eslatma: Yuqoridagi rekursiyada faqat n+1 xil kichik muammolar mavjud. Dinamik dasturlash g'oyasi Xuddi shu kichik muammoni qayta-qayta hisoblash o'rniga, biz ushbu kichik muammoga duch kelganimizda, ushbu kichik muammolarning echimini ba'zi xotirada saqlashimiz mumkin. Boshqa kichik muammoni hal qilishda ushbu kichik muammo yana paydo bo'lganda, biz allaqachon saqlangan yechimni xotiraga qaytaramiz. Bu Time-Memory Trade- Off ning ajoyib g'oyasi bo'lib, biz vaqt murakkabligini yaxshilash uchun qo'shimcha joydan foydalanamiz. Keling, dinamik dasturlash yondashuvidan foydalangan holda samarali yechimni muhokama qilaylik. Dinamik dasturlash masalalarini hal qilishning ikki xil usuli mavjud:  Yodlash: Yuqoridan pastga  Jadval: Pastdan yuqoriga Keling, ushbu ikki atamani tushunaylik: Yuqoridan pastga: Bu yuqoridagi rekursiv yondashuvning o'zgartirilgan versiyasi bo'lib, biz qayta hisoblashdan qochish uchun qo'shimcha xotira yoki qidirish jadvalida kichik muammolar yechimini saqlaymiz. Pastdan yuqoriga: Bu kichik muammolar yechimini yaratish va yechimni qo'shimcha xotirada saqlash uchun iterativ yondashuv. Yechim g‘oyasi: Yuqoridan pastga yondashuv . Yechim bosqichlari Turli kichik muammolarning yechimini saqlash uchun biz global massiv yoki N+1 o'lchamdagi qidirish jadvalidan foydalanishimiz mumkin. deylik, F[N+1]. Massivdagi barcha qiymatlarni -1 ga boshlang (chunki Fibonachchi qiymati salbiy bo'lishi mumkin emas). Bu bizga kichik muammoning yechimi allaqachon hisoblanganmi yoki yo'qligini tekshirishga yordam beradi. Rekursiv yechimda quyidagi o'zgartirishni amalga oshirishimiz mumkin: Agar (F[N] < 0), bu N ning Fibonachchi qiymati hali hisoblanmaganligini anglatadi. Yechimni rekursiv hisoblab, uni F[N] = fib(N-1) + fib(N-2) jadvalining N-indeksida saqlashimiz kerak. Agar (F[N] > 0), F[N] da saqlangan qiymatni qaytaring (chunki biz rekursiya davomida F[N] ni allaqachon hisoblab chiqqanmiz). N= 0 va N=1 asosiy holatlardir, chunki biz buning qiymatini allaqachon bilamiz va biz to'g'ridan-to'g'ri echimni F[0] va F[1] da saqlashimiz mumkin. 5

O'xshashlar

DINAMIK DASTURLASH METODLARINI OPTIMALLASHTIRISH USULLARI

Dinamik dasturlash usuli bilan yechiladigan masalalar

Dinamik massivlarni yaratish asoslari

Dinamik massivlar va ulardan foydalanish

Strukturali dasturlash