• 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.
  • divide and conquer'den farkı sub problemlerin birbirinden bağımsız olmayışıdır. çözülen her sub problemin sonucu diğer bir sub problemde kullanılır. dac algoritmalarda aynı işlem bir kaç kez yapılabilir ancak dp'de sonuçlar bir tabloya kaydedilir ve gerekince yeniden kullanılır. genellikle optimizasyon problemlerinin çözümünde başvurulur.

    misal elimizde a1, a2, a3, a4 şeklinde dört adet matrix olsun ve amacımız bunları çarpmak olsun. bu çarpma işlemini hepsi aynı sonucu verse de pek çok farklı şekilde yapabiliriz:

    (a1 (a2 (a3 a4)))
    (a1 ((a2 a3) a4))
    ((a1 a2) (a3 a4))
    ((a1 (a2 a3)) a4)
    (((a1 a2) a3) a4)

    bu işlemlerin hepsinin sonucu aynı çıksa da işlemciye bindiricekleri yükler açısından dağlar kadar fark olabilir aralarında. bu ve benzeri optimizasyon problemlerinin çözümü için dp elzemdir...
  • 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)
  • ardinda gauss olmasa sasirirdim.

    (bkz: gauss cikabilir)

    (hay aklini sevdigim, ne uretken adammissin yahu.)
  • dinamik programlama, bir sorunu tek tek bileşenlere ayıran bir düşünme biçimidir.

    uzun süredir programlama ile uğraşıyorsanız, bu terimi illa duymuşsunuzdur. genellikle teknik görüşmelerde önemli olan bir konu olsa da, günlük hayatınızda da uygulayabileceğiniz alanlar olacaktır.

    dediğim gibi öncelikle bir düşünce biçimi bu. bu nedenle, uygulama söz konusu olduğunda, teknik birçok şekil alabilir. dinamik programlamanın ana fikri, önemli bir sorunu ele almak ve onu daha küçük bileşenlere ayırmaktır.

    "e peki bu divide and conquer yöntemi değil mi zaten?" diye sorabilirsiniz.

    divide and conquer kavramından farkı, alt problemlerin birbirinden bağımsız "olmayışıdır". çözülen her alt problemin sonucu, diğer bir alt problemde kullanılır.

    uygulama söz konusu olduğunda, algoritma verimliliğini artırmak için veri depolamaya ve yeniden kullanıma dayanır.

    en basit örnek olarak; fibonacci dizisi üzerinden gidelim. bildiğiniz gibi fibonacci dizisi 0 ve 1 ile başlayarak, diğer elemanları için kendisinden bir önce ve iki önceki elemanın toplamıdır.

    0, 1, 1, 2, 3, 5, 8 diye gider..

    bu dizininin rekürsif olarak hesaplanması şöyle: görsel

    peki mesela fibonacci(5)'in (yani 5. fibonacci sayısı) nasıl hesaplanabileceğini decision tree içerisinde gösterelim. mesela burada fibonacci(5)'i bulmak için 3 defa fibonacci(2)'yi hesaplamışım.

    neden aynı hesaplamayı 3 defa yapayım ki ben? gereksiz değil mi? görsel

    ve sayı büyüdükçe fibonacci method çağrısı inanılmaz sayıda artıyor.

    fibonacci(2) için 1, fibonacci(4) için 5, fibonacci(10) için 109, fibonacci(15) için 1219 fonksiyon çağrısı yapılıyor. yani input'a bağlı olarak bu algoritmanın performansı katlanarak azalır.

    işte burada dinamik programlamanın temelini anlıyoruz!

    aynı işlemi tekrar tekrar yapmak yerine, bir defa hesaplayıp, sonucunu bir yerde saklayıp, daha üst hesaplamalarda ihtiyacımız olduğunda o sakladığımız yerden almaya dayanır.

    her işlemin sonucunu bir dizide saklayabiliriz: görsel

    hatta bu fibonacci hesaplamasının hiç bir ekstra space* kullanmadan, bir kaç değişken ile halledebileceğiniz versiyonu da var ki bunun da aslında temeli dinamik programlama mantığına dayanıyor.

    önceki hesaplamamızı bir değişkende tutmak! görsel

    bu kodun artık rekürsif bir teknik gerektirmediğine dikkat edin. en eski iki değer, diziye eklenerek, sonraki tüm değerler o dizi üzerinden hesaplanır.

    algoritmanın performansı hala dizi boyutuna bağlı olsa da, bu yaklaşım verimliliği o(n)* zamana yükseltmiştir.

    şunu sorabilirsiniz, rekürsif yaklaşımda hiç ekstra space kullanmadık yani o(1) iken dinamik programlama ile bir dizi kullanarak o(n) space complexity elde ettik, bu kötü değil mi?

    hayır, çünkü rekürsif hesaplamalar da arka tarafta stack veri yapısı kullanırlar. yani o(1) space değildirler.

    dinamik programlamanın 2 yaklaşımı var:

    - top-down yaklaşımı
    - bottom-up yaklaşımı

    bunları genel olarak anlatan çok güzel bir stack overflow sorusu var, göz atabilirsiniz.

    peki memoization'ını da duyuyoruz, bu nedir?

    memoization da aslında yukarıda anlattıklarım, dediğim gibi dinamik programlamayı "düşünme şekli" olarak algılayabilirsiniz. biz programcılar olarak, memoization = dinamik programlama şeklinde düşünmek en güzeli bence.

    özetle;

    dinamik programlama, sürekli aynı hesaplamaları yapmak yerine, 1 defa hesaplayıp onu sakladıktan sonra, başka bir problemde o sonucu kullanmak istediğimizde o sakladığımız yerden alıp kullanmaktır.

    twitter thread
  • neden dinamik programlama diyecek olursanız, richard bellman'ın kelime oyunu yapmasından kaynaklı. o zamanın bürokrasisi, pratik şeyler dışındaki araştırmalara soğuktu hatta nefret ediyordu ve desteklemiyordu ve bellman'ın yaptığı bilimsel bir araştırmaydı; fakat zamanındaki bürokrasi engellerini aşmak için, konuya tamamen fayda amaçlı olduğunu uyandıracak bir başlık seçmesi gerekiyordu bu yüzden dynamic programming gibi bürokrasinin hoşuna giden bir başlık seçti. yani ismin altında derin anlamlar aramayın.))

    referans: erik demaine, ıntroduction to algorithms, dynamic programming ı.
  • (bkz: memoization)
  • 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.
  • bir problemi en küçük parçasından başlayarak daha büyük parçalarını çözerek yiyip bitirmek.
  • yüzde otuz ingilizce programıyla mezun olabilmek için ve bu yüzden bölümde tek açılan ingilizce ders olduğu için seçmek zorunda kaldığım, endüstri mühendisliğinin alt konularından biri olan optimum sonuca ulaşmayı hedefleyen ders.

    ama benim çok hoşuma gitmeyen ders çünkü alışmışız senelerdir doğrusal programlamaya... hani bu gelince olmadı yani tek tek deniyorsun her bir sonucu ve bir soruyu çözerken harcadığın düşünme ve işlem yapma eforu, lineer programlamaya göre kat ve kat fazla. tamam mantıklı olabilir ama bildiğin amele işi yani.

    dinamik programlama kesinlikle bilgisayarın halletmesi gereken bir husustur. bide tersten düşünüp soruyu başa doğru ilerliyorsunuz. mesela şöyle başlangıçta elinizde max 6 birimlik bir kapasiteniz var en sona geliyor ve diyorsunuz ki son adıma gelince elimde ya 0,ya 1 ya 2 ya 3, 4, 5 ya da max 6 tane kapasiteden kalmış olabilir. bu demektir ki son adıma kadar ya hepsini kullandın ya 1 kaldı ya 2 kaldı ya da hiç kullanmadın elinde hepsi kaldı... bu değerler için tek tek kar ya da zararları hesapla.buradan yola çıkıp bir önceki adımda en faydalı olan ile bir sonraki fonksiyon arasında (bu bir sonraki fonksiyon son adımdaki fonksiyon oluyor) bir ilişki kurup (genelde toplanılıyor) her bir kapasite değeri için olası kullanılabilecek tüm değerleri tek tek hesaplayıp ilgili her bir iterasyonun ayrı ayrı kapasite değerlerini hesaplıyorsunuz.

    işte iterasyon sayınız biraz fazlaysa çok terlersiniz... dediğim gibi mantık çok zor değil biraz tersten düşünüyorsun adımlar yorar sizi. en iyisi bilgisayar yapsın bu işi hehhehe.
hesabın var mı? giriş yap