Dinamik Programlama Nedir ?

Bu yazımızda programlamanın önemli konularından birisi olan dinamik programlama konusunu açıklayacağız. Dinamik programlama nedir ? Dinamik programlama ve memoization çalışma mantığı nasıldır ? gibi soruları yanıtlayacağız. Hadi başlayalım.

Dinamik programlama, daha büyük bir problemi daha küçük problemlere (sub-problems) ayırma işlemidir. Bu, genel çözümü daha verimli bir şekilde bulmamıza yardımcı olur.

Dinamik Programlama Neden Önemli ?

Yukarıda da bahsettiğimiz gibi dinamik programlama, büyük problemleri daha küçük problemlere bölme işlemidir. Küçük problemlerin cevaplarını kullanarak genel problemi çözebiliriz. Bu sayede çözüme ulaşmak her konuda çok daha az maliyetli olur.

Dinamik Programlama Nasıl Çalışır ?

Dinamik programlamanın nasıl çalıştığını bir örnek üzerinde görmek çok daha mantıklı olacaktır. Bunun için verilebilecek en iyi örneklerden birisi fibonacci dizisidir. Fibonacci dizisi üzerinden dinamik programlamayı anlamaya çalışalım.

Öncelikle bilmeyenler için, her sayının kendinden önceki ile toplanması sonucu oluşan bir sayı dizisine fibonacci dizisi denir. Örneğin;

0, 1, 1, 2, 3, 5, 8, 13, 21 ....

Sizden dizideki 6. sayıyı (yukarıda gösterildiği gibi 8 olan) kod yazarak hesaplamanızı istediğimde bunu bir döngü veya rekürsif fonkisyon ile çözebilirsiniz. Hemen bu çözümü Javascript dili ile yazalım.

function f(n) {
    if (n == 1 || n == 2)
        return 1;

    return f(n - 1) + f(n - 2)
} 

let cevap= f(6)

Bu kod çalışacaktır. Fakat 6. sayıyı değilde çok daha yüksek bir sayıyı bulmak istediğimizde yavaş olması çok muhtemel. Bunun sebebi altıncı fibonacci sayısını hesaplamak için önce dördüncü ve beşinci fibonacci sayılarını hesaplamamız gerekiyor. Bunların her biri daha sonra önceki sayılarını hesaplamak zorundadır ve bu dizinin başına kadar tekrarlanır yani 1’e kadar.

Bunu grafik olarak çizersek;

Burada çok fazla tekrar olduğunu görebilirsiniz. Örneğin f(2) 5 defa hesaplandı. Bu küçük hesaplamalar için çok fazla sorun olmayacaktır. Fakat hesaplanmak istenen sayı 6 değilde çok daha büyük bir sayı olursa, modern bilgisayarların bile zorlanacağı bir çözüm şekli olabilir.

Peki daha iyi bir sonuç almak için ne yapabiliriz ?

Dinamik Programlama ve Memoization

Yukarıdaki gibi bir durumda dinamik programlama ve memoization yönetemini kullanmak en doğru seçim olacaktır. Peki bu memoization nedir ?

Memoization’u Türkçe’ye not alma olarak çevirebiliriz. Memoization kullanarak işlemler devam ederken önceki hesaplamalarımızın sonuçlarını hafızada tutarız. Bu şekilde, her sayıyı yalnızca bir kez hesaplarız.

Şimdi Javascript ile tekrar kodumuzu yazalım. Fakat bu sefer dinamik programlama ve memoization kullanarak.

function f(n) {

    if (n == 1 || n == 2)
        return 1

    let result = 0

    let lastButOneValue = 1
    let lastValue = 1

    for (let i = 3; i <= n; i++) {
        result = lastValue + lastButOneValue
        lastButOneValue = lastValue
        lastValue = result
    } 
    return result
} 

let answer = f(6)

Yine graf üzerinde bu işlemlerin nasıl gözüktüğüne bir bakalım.

Bir önceki, yani verimsiz olan grafla aynı gösterim fakat bu bu kodda sadece koyu renkli olanlar hesaplandı. Diğerleri zaten hafızada olduğu için hesaplanmadı. Bu sayede iki katından daha fazla işlemi yapmaktan kurtulduk ve sadece ihitcayıcımız olan işlemleri yaptık.

Bu yazımızda dinamik programlama nedir ? Dinamik programlama ve memoization kavramları nasıl çalışır ? gibi soruları yanıtladık. Diğer yazılım konulu yazılarımızı okumak isterseniz buraya tıklayarak tümüne ulaşabilirsiniz.