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

10-Ma’ruza. Dinamik dasturlash algoritmlarini loyihalash va tahlil qilish
Reja:
1. Dinamik dasturlash tushunchasi
2. Dinamik dasturlashning klassik muammolari
3. Dinamik dasturlashning umumiy g'oyasi
4. Dinamik dasturlash quyi qismlarining maqbulligini norasmiy tushuntirish.
5. Dinamik dasturlash yordamida muammolarni yechishga misol
Tayanch tushunchalar: dinamik dasturlash, koeffitsientlik, quyi, pastga qarab dinamik dasturlash, yuqoriga qarab dinamik dasturlash, ro'yxatlash
1.Dinamik dasturlash tushunchasi.
"Dinamik dasturlash" tushunchasi birinchi marta 1940 yillarda Richard Bellman tomonidan muammoning yechimini topish jarayonini tasvirlash uchun ishlatilgan bo'lib, unda bitta muammoga javobni undan oldin paydo bo'lgan boshqa muammoni hal qilganidan so'ng olish mumkin.
Shunday qilib, amerikalik matematik va matematik va kompyuter muhandisligi sohasidagi yetakchi mutaxassislardan biri Richard Ernst Bellman dinamik dasturlash asoschisi bo'ldi.
Keyinchalik konseptsiyaning ta'rifi yakunlandi va Bellmanning o'zi tomonidan zamonaviy ko'rinishga keltirildi.
"Dasturlash" so'zi "dinamik dasturlash" kontekstida dasturlashning klassik tushunchasi (dasturlash tilida yozish kodi) bilan deyarli hech qanday aloqasi yo'q. "Dasturlash" so'zi "optimallashtirish" so'zi bilan sinonim bo'lgan "matematik dasturlash" iborasi bilan bir xil ma'noga ega.
Shuning uchun dasturlar muammoning yechimini topish uchun maqbul harakatlar ketma-ketligi sifatida ishlatiladi.
Umuman olganda, yangi boshlanuvchilar uchun dinamik dasturlash tushunchasining norasmiy ta'rifi quyidagicha ko'rinishi mumkin:
Dinamik dasturlash bu ma'lum bir xususiyatga ega bo'lgan kombinatorika, optimallashtirish va boshqa muammolarni (subkastrlarning qo'shma optimalligi xususiyati) ba'zi muammolarini hal qilishga imkon beradigan usul yoki uslubdir.
Optimallashtirish muammolari, qoida tariqasida, ma'lum bir ob'ektiv funksiyani maksimal darajada oshirish yoki minimallashtirish vazifasi bilan bog'liq (masalan, tizim buzilmasligi ehtimolini maksimal darajada oshirish, matni maksimal darajada oshirish. Foyda kutish va boshqalar).