10-Ma’ruza. Dinamik dasturlash algoritmlarini loyihalash va tahlil qilish Reja

Kombinatorikaning vazifalari, qoida tariqasida, ko’rilayotgan xususiyatlarga ega bo'lgan qancha ob'ekt mavjudligi yoki berilgan xususiyatlarga ega bo'lgan kombinatorial ob'ektlarning soni savoliga javob beradi.
Ya'ni, di amik dasturlash barcha muammolarni hal qilmaydi, faqat ba'zi birlari, ma'lum bir subtitrlar sinfidir. Ammo ushbu quyi sinflar ko'plab bilim sohalarida qo'llaniladi: dasturlash, matematika, tilshunoslik, statistika, o'yin nazariyasi, iqtisodiyot, informatika va boshqalar.
Dinamik dasturlash odatda muammolarni yechishda ikkita yondashuvga amal qiladi:
• Pastga qarab dinamik dasturlash: vazifa kichik quyi qismlarga bo'linadi, ular hal qilinadi va keyin asl muammoni hal qilish uchun birlashtiriladi. Xotiralash tez-tez uchraydigan quyi qismlarni yechish uchun ishlatiladi.
• Yuqori oqim dinamik dasturlash: keyinchalik dastlabki muammoni hal qilish uchun kerak bo'ladigan barcha quyi jadvallar oldindan hisoblab chiqiladi va keyin asl muammoning yechimini yaratishda foydalaniladi. Ushbu usul talab qilinadigan stek hajmi va funksional qo'ng'iroqlar soni nuqtai nazaridan yuqoridan-pastga dasturlashdan afzaldir, ammo ba'zida kelajakda qaysi quyi satrlarni hal qilishimiz kerakligini oldindan aniqlash oson emas.
Dinamik dasturlash yordamida hal qilingan vazifalar qo'shma optimallik xususiyatiga ega bo'lishi kerak.


2.Dinamik dasturlashning klassik muammolari.
Ko'pgina olimpiada dasturlash muammolarida rekursion yoki to'liq qidiruvdan foydalangan holda echish juda ko'p sonli operatsiyalarni talab qiladi. Bunday muammolarni, masalan, to'liq qidiruv orqali hal qilishga urinish, bajarilish vaqtining ortiqcha bo'lishiga olib keladi.
Biroq, sanab o'tilgan va boshqa ba'zi muammolar orasida bitta yaxshi xususiyatga ega bo'lgan muammolar sinfini ajratish mumkin: ba'zi kichik dasturlarga yechim (masalan, kichik raqam uchun n), asl muammoning yechimini deyarli hech qanday raqamlarsiz topish mumkin. Bunday muammolar dinamik dasturlash usuli bilan hal qilinadi.
Tarkiblar. Bir ketma-ketlikdagi klassik muammo quyidagilardan iborat.
Fibonachchi ketma-ketligi F_n quyidagi formulalar bilan belgilanadi:
F₁= 1, F₂= 1, F_n=F_{n– 1}+F_{n– 2} bunda n > 1.
Topish kerak - F_n n-element.
Mantiqiy va samarali bo'lib ko'rinishi mumkin bo'lgan yechim - bu rekursion asosli yechim.:
int F(int n) {
if (n < 2) return 1;
else return F(n-1) + F(n-2);
}
Bunday funksiyadan foydalanib, biz "oxiridan" muammoni hal qilamiz - ma'lum qiymatlarga erishgunimizcha n-ni asta-sekin kamaytiramiz.
Ko'rib turganingizdek, oddiy ko'rinadigan bunday dastur allaqachon n = 40 bilan sezilarli darajada ishlaydi. Buning sababi shundaki, bir xil oraliq ma'lumotlar bir necha bor hisoblab chiqiladi - operatsiyalar soni Fibonachchi raqamlari o'sishi bilan bir xil tezlikda o'sadi - eksponent bo'yicha.
Ushbu vaziyatdan chiqishning bir usuli bu qayta foydalanish uchun topilgan oraliq natijalarni saqlashdir:
int Fib(int n) {
if (Fib[n] != -1) return Fib[n];
if (n < 2) return 1;
else {
Fib[n] = Fib(n - 1) + Fib(n - 2);
return Fib[n];
}
}
Algoritmning murakkabligi bahosi- ;
Berilgan echim to'g'ri va samarali. Ammo bu vazifani bajarish uchun sodda echim qo'llaniladi: