dinamik programlama

• bir problemi en küçük parçasından başlayarak daha büyük parçalarını çözerek yiyip bitirmek.
• (bkz: bellman denklemi)
• 1954'de richard bellman tarafından bulunmuştur.
• modern makroekonomi'nin vazgecilmezi.
• problemi dinamik programlamayla iki türlü çözebilirsiniz.
  forward recursion: baştan sona doğru.
  backward recursion: sondan başa doğru.
  her bir adımın optimum çözümü bir sonraki adıma taşınarak sonuca ulaşılır.
• recursive cozulebilen problemlere uygulanabilir. problemin kucuk parcalarinin optimal cozumlerinin daha buyuk parcalari cozerken ise yaramasi gerekir.
• richard bellman tarafindan calinip cirpilmi$ olan algoritmadir. bir tarihte channel coding konulu bir ieee konferansinda konu$maci kimse "kullandigimiz yontem olan viterbi algoritmasi aslinda yeni bir $ey degil. bunun gerisine gidersek dynamic programming cikar kar$imiza. o da aslinda isim vermeden hep kulanilagelmi$ bir $eydir. kimbilir belki de gauss bulmu$tur.." diye bir laf etmi$tir. aslinda gauss'u laf olsun diye sallamistir cok eskiden bile bilindigini anlatmak icin. dinleyicilerden biri hararetle neden gauss, gauss nerden cikti diye sormaya baslar.doktorasini henuz almi$ cicegi burnunda konu$maci ki$i iyice tirsmi$tir, "bilmem ki yani.. ehhm.. oylesine soyledim. bilmiyorum. yani aslinda cok eskiden beri kullaniliyor, onu belirtmek icin ben.. gauss. cok onceden yani.." diye kem kum etmeye ba$lar. defalarca "neden gauss" sorusu sorulur hararetli dinleyici tarafindan ve "bilmiyorum, salladim, booggghh" cevabi alinir. konusmacimiz "lutfen emin olmadigin bilgileri burda dile getirme genc adam!" seklinde lafi yer ve " hyskiim bu dalyarak nerden cikti" diye icerleyerek konusmasina devam eder. o konferanstaki dellenen dinleyici richard bellman dir ve biz bugun tarihin tozlu sayfalarini kari$tirdigimizda goruyoruz ki gauss hayvani gercekten de dynamic programmingi ilk kullanan ki$idir.
• bilgisayar bilimlerinin hemen her kosesinde kullanilan bir algoritma paradigmasidir. yani spesifik bir algoritma degil, bir algoritmalar sinifidir. nasil ki oop bir programlama paradigmasidir ve icinde java, csharp, smalltalk gibi ornekler bulundurur. iste bu da oyle bir konsept.
  bir kac ornek icin (bkz: cyk parsing) (bkz: knapsack problem)
  
  benim bildigim en komik ve gercek hayata uygulamasi en fazla olan ornek icin ise (bkz: #8550854)
• en önemli prinsibinin adı "principle of optimality "olup bu prensip türkçeye çevrildiğinde kısaca şunu özetler:şu anki bulunduğun durumda geçmişte izlediğin politikalardan bağımsız olarak gelecekteki aşamaları optimizie edecek bir politikaya sahip olman gerekmektedir.
• (bkz: dinamit programlama)