--- title: 'Dinamik Programlama' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/dinamik-programlama' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:26+00:00' license: 'CC BY-SA 4.0' --- # Dinamik Programlama Not almanın iki koşulu ve ikisinin de sayılması: örtüşen alt problemde çağrı 21.891'den 39'a inerken örtüşmeyende ikisi de 39 kalıyor ve defter 19 girişi boşa tutuyor, defterin anahtarı durumun tamamını taşımadığında ise kalıp 40 girdinin 39'unda kâhinden ayrılıyor. Açgözlü yordam, aldığı en büyük parayı bir daha sorgulamadığı için geriye pahalı bir kalan bırakıyordu. Çare belliydi ve önceki derste zaten kullanıldı: kalanı da çözmek, yani her alt problemin en iyi çözümünü hesaplayıp saklamak. O yordamın adı **dinamik programlama (dynamic programming)**. Kalıbın çekiciliği, üstel bir aramayı sayılabilir bir tabloya indirmesidir. Bedeli ise iki ayrı ön koşuldur ve ikisi de sessizce bozulabilir. Birincisi **optimal alt yapı**: en iyi çözümün, alt problemlerin en iyi çözümlerinden kurulabilmesi. İkincisi **örtüşen alt problem**: aynı alt problemin birden çok kez sorulması. Birincisi bozulunca yanıt yanlış çıkar; ikincisi bozulunca yanıt doğru kalır ama saklamak hiçbir şey kazandırmaz. Bu ders ikisini de sayar. - **TY29.** Ölçülen problem: bir dizide **bitişik olmayan** en çok üç eleman seçerek elde edilebilecek en büyük toplam. Boş seçim serbesttir, yani yanıt hiçbir zaman sıfırın altında olmaz. - **TY30.** Kâhin bütün alt kümeleri görür: 12 elemanlı bir dizide **4096 alt küme**. - **TY31.** Bir **adım**, not almada bir özyineleme çağrısı, alttan yukarıda bir hücrenin hesaplanması, kâhinde bir alt kümenin denenmesidir. - **TY32.** **Not alma (memoization)** özyinelemeli çözüme bir defter ekler; **alttan yukarı** çözüm aynı bağıntıyı özyinelemesiz kurar. - **TY33.** Kalıbın **ön koşulu**: defterin anahtarı, alt problemi tek anlamlı belirleyen durumun **tamamını** taşımalıdır. Eksik anahtar yalnız bu ön koşulu bozar. - **TY34.** İkinci ön koşul **optimal alt yapıdır** ve bu derste bozulmadan tutulur; onun bozulduğu durum klasik problemler konusuna aittir. - **TY35.** Örtüşme ölçümü ortak tanımdan aynen alınır ve yeniden tanımlanmaz. - **TY36.** Defter boyu **giriş sayısıyla**, tablo boyu **hücre sayısıyla** ölçülür. - **TY37.** Her ölçüm **20260219** tohumlu ikinci dağarcıkta da koşturulur. ## Örtüşme Sayılır Not almanın kazancı, alt problemlerin kaç kez tekrarlandığına eşittir. Bu, tahmin edilecek bir şey değil sayılacak bir şeydir. Aşağıdaki iki yordam aynı $n$ için çalışır; birinde her alt problem iki kez sorulur, ötekinde her çağrı yeni bir alt problem üretir. ```python # Ortak tanimin ortusme olcumu: ayni n, iki farkli alt problem yapisi. class Sayac: def __init__(self): self.adim = 0 def say(self, n=1): self.adim += n def ortusen(n, notlu=True): """Ortusen alt problem: her deger iki kez cagriliyor.""" s = Sayac() defter = {} def f(k): s.say() if k < 2: return k if notlu and k in defter: return defter[k] d = f(k - 1) + f(k - 2) defter[k] = d return d f(n) return {"cagri": s.adim, "deger": len(defter)} def ortusmeyen(n, notlu=True): """Ortusmeyen alt problem: her cagri farkli bir alt problem.""" s = Sayac() defter = {} def f(bas, son): s.say() if son - bas <= 1: return son - bas if notlu and (bas, son) in defter: return defter[(bas, son)] orta = (bas + son) // 2 d = f(bas, orta) + f(orta, son) defter[(bas, son)] = d return d f(0, n) return {"cagri": s.adim, "deger": len(defter)} print(" n ortusen notlu ortusen notsuz ortusmeyen notlu ortusmeyen notsuz defter") for n in (10, 15, 20): a, b = ortusen(n, True), ortusen(n, False) c, d = ortusmeyen(n, True), ortusmeyen(n, False) print(f"{n:2d} {a['cagri']:14d} {b['cagri']:15d} {c['cagri']:17d}" f" {d['cagri']:18d} {c['deger']:7d}") ``` ``` n ortusen notlu ortusen notsuz ortusmeyen notlu ortusmeyen notsuz defter 10 19 177 19 19 9 15 29 1973 29 29 14 20 39 21891 39 39 19 ``` Örtüşen yapıda $n = 20$ için çağrı sayısı **21.891'den 39'a** iniyor; kazanç 561 kat. Örtüşmeyen yapıda aynı $n$ için notlu ve notsuz sürüm **ikisi de 39** çağrı yapıyor — defter bir kez bile isabet vermiyor — ama yine de **19 giriş** tutuyor. İkinci satırın söylediği şey açıktır: **not almanın koşulu örtüşmedir.** Örtüşme yoksa defter yalnız yer tutar; yanıt doğru kalır, kazanç sıfırdır ve bellek boşa gider. İki yapı arasındaki fark, bağıntının biçimindedir. Örtüşen yapıda iki dal aynı değerlere iniyor ve alt problem uzayı $n$ büyüklüğünde; örtüşmeyende her dal kendi aralığına iniyor ve alt problem uzayı çağrı sayısı kadar. Bir kalıbı seçmeden önce sorulacak soru budur: **alt problem uzayı, çağrı sayısından küçük mü.** ## Defterin Anahtarı Durumun Tamamını Taşımalı Not almanın ikinci ve daha sessiz ön koşulu deftere ilişkindir. Aşağıdaki problem iki değişkenli bir duruma sahiptir: hangi konumdayız ve kaç seçim hakkımız kaldı. Aynı yordam iki anahtarla koşturulur. ```python # Onceki blogun uzerine: Sayac oradan gelir. TOHUM = 20260218 SECIM = 3 # en cok kac eleman secilebilir def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=TOHUM, n=40, uzunluk=12): r = uretec(tohum) return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]} for i in range(n)] def kahin_secim(dizi, k, s): """Butun alt kumeleri gorur; bitisik olmayan ve en cok k elemanlilari deger.""" en_iyi = 0 for maske in range(1 << len(dizi)): s.say() if maske & (maske << 1): # bitisik iki secim var continue if bin(maske).count("1") > k: continue en_iyi = max(en_iyi, sum(dizi[i] for i in range(len(dizi)) if maske >> i & 1)) return en_iyi def not_alan(dizi, k, s, anahtar="tam"): """anahtar='tam' -> defter (konum, kalan) ile; 'eksik' -> yalniz konum ile.""" defter = {} def f(i, kalan): s.say() if i >= len(dizi) or kalan == 0: return 0 ad = (i, kalan) if anahtar == "tam" else i if ad in defter: return defter[ad] d = max(f(i + 1, kalan), dizi[i] + f(i + 2, kalan - 1)) defter[ad] = d return d sonuc = f(0, k) return sonuc, len(defter) def olc(anahtar, kume): ayrilan, ak, ah, giris = [], 0, 0, 0 for k in kume: s1, s2 = Sayac(), Sayac() deger, boy = not_alan(k["dizi"], SECIM, s1, anahtar) if deger != kahin_secim(k["dizi"], SECIM, s2): ayrilan.append(k["no"]) ak += s1.adim ah += s2.adim giris += boy return {"ayrilan": len(ayrilan), "ayrilan_no": ayrilan[:6], "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2), "defter_girisi": giris} K = dagarcik() print("kahin: dizi basina", 2 ** 12, "alt kume") for anahtar in ("tam", "eksik"): print(f"defter anahtari {anahtar:6s}:", olc(anahtar, K)) ``` ``` kahin: dizi basina 4096 alt kume defter anahtari tam : {'ayrilan': 0, 'ayrilan_no': [], 'kalip_adim': 2440, 'kahin_adim': 163840, 'oran': 67.15, 'defter_girisi': 1200} defter anahtari eksik : {'ayrilan': 39, 'ayrilan_no': [1, 2, 3, 5, 6, 7], 'kalip_adim': 1000, 'kahin_adim': 163840, 'oran': 163.84, 'defter_girisi': 480} ``` Üç sayı yan yana. **Kâhin** 40 girdide **163.840 adım** harcıyor. **Tam anahtarlı not alma** 2440 adım harcıyor — kâhinin **67,15 katı** azı — ve 40 girdinin hiçbirinde ayrılmıyor. **Eksik anahtarlı not alma** 1000 adım harcıyor, kâhinin **163,84 katı** azı, ve 40 girdinin **39'unda** kâhinden ayrılıyor. Yanılgının mekanizması, önceki iki dersinkinden farklıdır ve daha tehlikelidir. Burada atlanan bir bölge yok; yordam bütün dalları geziyor. Sorun, deftere yazılan değerin **yanlış soruya ait olmasıdır.** Beşinci konumda üç seçim hakkıyla hesaplanan en iyi değer, aynı konuma bir seçim hakkıyla gelindiğinde geri veriliyor. Defter isabet ediyor, hesap atlanıyor, adım sayısı düşüyor — ve yanıt bozuluyor. Adım sayısının düşmesi burada bir hızlanma değil, **yanlışın belirtisidir**: 2440 yerine 1000 adım, defterin 1200 yerine 480 giriş tutması, hesaplanması gereken alt problemlerin **yarıdan çoğunun hiç hesaplanmadığı** anlamına gelir. ## Not Alma ile Alttan Yukarı Aynı bağıntı özyinelemesiz de kurulabilir. Bu, dinamik programlamanın ikinci biçimidir ve farkı ölçülebilir. ```python # Onceki bloklarin uzerine: dagarcik, Sayac, not_alan, kahin_secim ve K oradan gelir. def alttan_yukari(dizi, k, s): """Ayni bagintiyi ozyinelemesiz kurar; butun (konum, kalan) hucreleri dolar.""" n = len(dizi) tablo = [[0] * (k + 1) for _ in range(n + 2)] for i in range(n - 1, -1, -1): for kalan in range(1, k + 1): s.say() tablo[i][kalan] = max(tablo[i + 1][kalan], dizi[i] + tablo[i + 2][kalan - 1]) return tablo[0][k], n * k s1, s2, s3 = Sayac(), Sayac(), Sayac() ayrilan, not_giris, tablo_hucre = 0, 0, 0 for k in K: a, boy = not_alan(k["dizi"], SECIM, s1, "tam") b, hucre = alttan_yukari(k["dizi"], SECIM, s2) kahin_secim(k["dizi"], SECIM, s3) if a != b: ayrilan += 1 not_giris += boy tablo_hucre += hucre print("kahin adim :", s3.adim) print("not alma adim :", s1.adim, "| defter girisi:", not_giris) print("alttan yukari :", s2.adim, "| tablo hucresi:", tablo_hucre) print("ikisinin ayrildigi girdi:", ayrilan, "/ 40") ``` ``` kahin adim : 163840 not alma adim : 2440 | defter girisi: 1200 alttan yukari : 1440 | tablo hucresi: 1440 ikisinin ayrildigi girdi: 0 / 40 ``` İki biçim 40 girdide de aynı yanıtı veriyor, ama sayıları farklı. Alttan yukarı çözüm **1440 adım** harcıyor, not alma **2440**; aradaki fark özyineleme çağrılarının kendisidir. Buna karşılık not alma **1200 giriş** tutuyor, alttan yukarı **1440 hücre**. Yani dizi başına not alma 30 giriş, tablo 36 hücre. Ödünleşim tam olarak buradadır. Alttan yukarı çözüm bütün hücreleri doldurur — erişilemeyecek olanları da — ve karşılığında çağrı yükü ödemez. Not alma yalnız gerçekten sorulan alt problemleri hesaplar, bu problemde 36 hücrenin 30'unu, ve karşılığında her alt problem için bir çağrı ödemesi yapar. Hangisinin kazandığı **alt problem uzayının ne kadarının erişilebilir olduğuna** bağlıdır; bu problemde uzayın altıda beşi erişilebilir olduğu için alttan yukarı öne geçiyor. Erişilebilir oran düştükçe not alma öne geçer. ## Optimal Alt Yapı Sınanabilir Bir İddiadır Yukarıdaki iki biçim de aynı bağıntıyı kullanıyor: bir konumdaki en iyi değer, ya o konumu atlayıp bir sonrakine geçmenin ya da o konumu seçip iki sonrakine geçmenin en iyisidir. Bu bağıntının doğruluğu **optimal alt yapı** varsayımına dayanır ve varsayım sınanabilir — bağıntının her hücresi ayrı ayrı kâhine sorulur. ```python # Onceki bloklarin uzerine: dagarcik, Sayac, kahin_secim, SECIM ve K oradan gelir. def kahin_sonek(dizi, bas, kalan, s): """Sonekin en iyisini kaba kuvvetle bulur.""" return kahin_secim(dizi[bas:], kalan, s) hucre, uyusan, s = 0, 0, Sayac() for k in K: dizi = k["dizi"] for i in range(len(dizi)): for kalan in range(1, SECIM + 1): hucre += 1 atla = kahin_sonek(dizi, i + 1, kalan, s) # i secilmiyor sec = dizi[i] + kahin_sonek(dizi, i + 2, kalan - 1, s) # i seciliyor if max(atla, sec, 0) == kahin_sonek(dizi, i, kalan, s): uyusan += 1 print("sinanan hucre:", hucre, "| bagintinin kahinle uyustugu hucre:", uyusan) print("kahin adimi :", s.adim) ``` ``` sinanan hucre: 1440 | bagintinin kahinle uyustugu hucre: 1440 kahin adimi : 1719960 ``` **1440 hücrenin 1440'ında** bağıntı kâhinle uyuşuyor. Sınamanın bedeli görülmelidir: 1.719.960 adım, yani çözümün kendisinin bin katından fazlası. Optimal alt yapıyı sınamak, problemi çözmekten pahalıdır ve bu şaşırtıcı değildir — her hücre için soneki baştan kaba kuvvetle çözmek gerekir. Buradan iki şey çıkar. Birincisi, **optimal alt yapı bir sezgi değil, sınanabilir bir iddiadır**; bir bağıntı yazıldığında onun geçerliliği kâhine hücre hücre sorulabilir. İkincisi, bu sınama üretimde değil **tasarım sırasında ve küçük girdide** yapılır. Bağıntı bir kez doğrulandıktan sonra 40 girdide 1440 adımla çalışan bir çözüm kalır geriye; bir buçuk milyon adımlık sınama, o çözümün doğruluğunun bir defalık bedelidir. ## İkinci Dağarcık ```python # Onceki bloklarin uzerine: dagarcik, olc oradan gelir. for ad, tohum in (("birinci dagarcik (20260218)", 20260218), ("ikinci dagarcik (20260219)", 20260219)): kume = dagarcik(tohum) print(ad) for anahtar in ("tam", "eksik"): o = olc(anahtar, kume) print(f" anahtar {anahtar:6s} ayrilan {o['ayrilan']:2d} / 40 | oran", round(o["ayrilan"] / 40, 4), "| kalip adim", o["kalip_adim"], "| defter girisi", o["defter_girisi"]) ``` ``` birinci dagarcik (20260218) anahtar tam ayrilan 0 / 40 | oran 0.0 | kalip adim 2440 | defter girisi 1200 anahtar eksik ayrilan 39 / 40 | oran 0.975 | kalip adim 1000 | defter girisi 480 ikinci dagarcik (20260219) anahtar tam ayrilan 0 / 40 | oran 0.0 | kalip adim 2440 | defter girisi 1200 anahtar eksik ayrilan 37 / 40 | oran 0.925 | kalip adim 1000 | defter girisi 480 ``` Adım ve defter sayıları iki dağarcıkta **birebir aynı**: 2440 ile 1200, 1000 ile 480. Beklenen sonuçtur, çünkü bu yordamların adımı dizinin değerlerine değil yalnız uzunluğuna ve seçim hakkına bağlıdır. Eksik anahtarın ayrılan girdisi 39'dan 37'ye iniyor; oran 0,9750'den 0,9250'ye. İki girdilik fark, çözünürlüğün anlamlı saydığı üç girdinin altındadır ve **ölçülmemiş sayılır**. Okuma iki dağarcıkta da aynıdır: eksik anahtar neredeyse her girdide yanlış yanıt verir. ## Özet - Dinamik programlamanın iki ön koşulu vardır: **optimal alt yapı** ve **örtüşen alt problem**; birincisi bozulunca yanıt, ikincisi bozulunca kazanç yok olur. - Örtüşen yapıda $n = 20$ için çağrı **21.891'den 39'a** iniyor; örtüşmeyen yapıda notlu ve notsuz sürüm **ikisi de 39** çağrı yapıyor ve defter **19 girişi boşa** tutuyor. - Tam anahtarlı not alma kâhinin 67,15 katı az adım harcıyor ve **0 girdide** ayrılıyor; eksik anahtarlı sürüm 163,84 katı az harcıyor ve **39 girdide** ayrılıyor. - Eksik anahtarda adım sayısının düşmesi bir hızlanma değil **yanlışın belirtisidir**; defter 1200 yerine 480 giriş tutuyor, yani alt problemlerin yarıdan çoğu hiç hesaplanmıyor. - Alttan yukarı çözüm 1440 adımla not almanın 2440 adımından az harcıyor ama 1440 hücre tutuyor; not alma 1200 giriş tutuyor. Kazananı, alt problem uzayının erişilebilir oranı belirler. - İkinci dağarcıkta adım ve defter sayıları birebir aynı; eksik anahtarın ayrılan girdisi 39 yerine 37 ve bu iki girdilik fark ölçülmemiş sayılır. ## Sonraki Adım Dinamik programlama, alt problem uzayını **tümüyle** dolaşıp saklıyordu. Bazı problemlerde uzay o kadar büyüktür ki tümünü dolaşmak seçenek değildir; orada tek yol, uzayın büyük bölümünün **çözüm içermediğini kanıtlayıp kesmektir**. Sonraki ders bu kesmeyi ölçer: budamalı arama yedi vezirlik tahtada 552 düğüm gezerken budamasız arama 960.800 düğüm geziyor, ve iki sayının oranı $n$ büyüdükçe artıyor.