Alıştırma Ortamlarını Kullanma

Önceki iki ders tek bir çözümle ilgiliydi: hangi kalıp seçilir, seçilen kalıp nasıl sınanır. Bu ders soruyu tek çözümün dışına taşır. Alıştırma tekrarlı bir iştir ve tekrarlı işin bir ilerleme ölçütü olmak zorundadır, yoksa çalışma sürer ama nereye gittiği bilinmez.

Ortamlar türleriyle anılır, çünkü ölçülen şey ortamın kendisi değil, ürettiği problem akışının biçimidir. Sonuç iki adımda çıkar: çözülen problem sayısı bir ilerleme ölçütü değildir, kaç ayrı kalıp görüldüğü de değildir.

Üç Ortam Türü

Havuz tabanlı alıştırma ortamında çok sayıda problem durur ve seçimi çalışan yapar. Seçim serbest olduğu için tanıdık olana kayar; kalıp dağılımı çalışanın alışkanlığını yansıtır. Zamanlı yarışma ortamında kümeyi ortam belirler ve çalışan hepsini görmek zorundadır; küme küçüktür. Şirket içi değerlendirmede problem sayısı en azdır, dağılımı yine çalışan seçmez, girdiler hazırlanmamıştır.

• AD21 — Kalıp kümesi ortak tanımın beş kalıbıdır: iki işaretçi, kayan pencere, açgözlü, geri izleme, not alma. Kurs boyunca ölçülen kalıplar bunlardır.
• AD22 — Bir tur, ortamda geçirilen bir çalışma oturumudur. Tur başına problem sayısı ortam türüne göre sabittir: havuz 24, yarışma 5, değerlendirme 2. Altı tur ölçülür.
• AD23 — Havuz tabanlı ortamda seçimin ağırlığı 50, 30, 10, 6, 4’tür; diğer iki ortamda dağılım düzgündür. Ağırlık, çalışanın tanıdık kalıba dönme eğilimini modeller.
• AD24 — Seçim ortak tanımın belirlenimci üreteciyle yapılır; random kullanılmaz.
• AD25 — Denge oranı, en az görülen kalıbın sayısının eşit dağılımdaki paya bölümüdür. Beş kalıp eşit görülseydi oran 1,0000 olurdu.

"""Uc ortam turunde kalip cesitliligi , ortak tanimin bes kalibi uzerinde."""
TOHUM, IKINCI = 20260218, 20260219
KALIP = ["iki isaretci", "kayan pencere", "acgozlu", "geri izleme", "not alma"]
ORTAM = [("havuz tabanli alistirma ", 24, [50, 30, 10, 6, 4]),
         ("zamanli yarisma         ", 5, [20, 20, 20, 20, 20]),
         ("sirket ici degerlendirme", 2, [20, 20, 20, 20, 20])]


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def sec(r, agirlik):
    x = r(sum(agirlik))
    for i, a in enumerate(agirlik):
        if x < a:
            return i
        x -= a
    return len(agirlik) - 1


def olcut(sayim):
    toplam = sum(sayim)
    esit = toplam / len(sayim)
    return {"problem": toplam, "kapsanan": sum(1 for c in sayim if c),
            "denge": round(min(sayim) / esit, 4),
            "bas_iki": round(sum(sorted(sayim)[-2:]) / toplam, 4)}


def kosum(tohum, tur=6):
    print(f"tohum {tohum} , {tur} tur")
    print("ortam                     problem  kapsanan   denge  bas iki  dagilim")
    for ad, basina, agirlik in ORTAM:
        r = uretec(tohum)
        sayim = [0] * len(KALIP)
        for _ in range(tur * basina):
            sayim[sec(r, agirlik)] += 1
        o = olcut(sayim)
        print(f"{ad}  {o['problem']:7d}  {o['kapsanan']:8d}  {o['denge']:6.4f}"
              f"  {o['bas_iki']:7.4f}  {sayim}")


kosum(TOHUM)
print()
kosum(IKINCI)
print()
print("havuz tabanli ortam , tur tur birikimli (tohum 20260218)")
print("tur  problem  kapsanan   denge  bas iki")
r = uretec(TOHUM)
sayim = [0] * len(KALIP)
for t in range(1, 7):
    for _ in range(24):
        sayim[sec(r, ORTAM[0][2])] += 1
    o = olcut(sayim)
    print(f"{t:3d}  {o['problem']:7d}  {o['kapsanan']:8d}  {o['denge']:6.4f}"
          f"  {o['bas_iki']:7.4f}")

tohum 20260218 , 6 tur
ortam                     problem  kapsanan   denge  bas iki  dagilim
havuz tabanli alistirma       144         5  0.2431   0.7986  [64, 51, 11, 11, 7]
zamanli yarisma                30         5  0.6667   0.5000  [4, 5, 9, 6, 6]
sirket ici degerlendirme       12         5  0.4167   0.5833  [1, 4, 3, 2, 2]

tohum 20260219 , 6 tur
ortam                     problem  kapsanan   denge  bas iki  dagilim
havuz tabanli alistirma       144         5  0.1389   0.8194  [76, 42, 16, 6, 4]
zamanli yarisma                30         5  0.6667   0.5667  [8, 4, 9, 4, 5]
sirket ici degerlendirme       12         5  0.4167   0.6667  [1, 1, 5, 2, 3]

havuz tabanli ortam , tur tur birikimli (tohum 20260218)
tur  problem  kapsanan   denge  bas iki
  1       24         4  0.0000   0.8333
  2       48         5  0.2083   0.7917
  3       72         5  0.2778   0.7639
  4       96         5  0.2604   0.7500
  5      120         5  0.2500   0.7750
  6      144         5  0.2431   0.7986

Birinci tablo iki ölçütü aynı anda çürütüyor. Havuz tabanlı ortam 144, zamanlı yarışma 30, şirket içi değerlendirme 12 problem çözüyor — arada 12 kat fark var. Buna karşılık kapsanan kalıp sayısı üçünde de 5. Yani iki soru da ortamları ayırt etmiyor: “kaç problem çözdüm” 12 kat sapıyor, “kaç ayrı kalıp gördüm” hiç oynamıyor.

Ayırt eden ölçüt dağılımdır. Havuz tabanlı ortamda denge oranı 0,2431: en az görülen kalıp, eşit dağılımdaki payının dörtte birinden azını alıyor ve en çok görülen iki kalıp problemlerin 0,7986’sını kaplıyor. Zamanlı yarışma 30 problemle 0,6667 denge veriyor — beş kat az problemle 2,74 kat dengeli. Şirket içi değerlendirmedeki 0,4167 ise dağılımdan değil, örneklemin küçüklüğünden gelir.

Üçüncü tablo dersin en aykırı sonucudur. Havuz tabanlı ortamda kapsama ikinci turda 5’e çıkıyor ve bir daha hiç değişmiyor: üçüncü turdan altıncı tura kadar çözülen 72 problem kapsama ölçütüne hiçbir şey eklemiyor. Denge oranı ise üçüncü turda 0,2778 ile en yüksek noktasına çıkıp sonra düşüyor — dördüncü turda 0,2604, altıncı turda 0,2431. Problem sayısı artarken ilerleme ölçütü geriliyor, çünkü eklenen her problem baskın iki kalıba gidiyor.

İkinci dağarcık sıralamayı doğruluyor: 20260219 tohumunda havuz 0,1389, yarışma 0,6667, değerlendirme 0,4167. Havuzun değeri 0,2431’den 0,1389’a düşüyor, yani mutlak değer dağarcığa bağlıdır; ama üç ortamın sırası ve havuz ile yarışma arasındaki büyüklük farkı iki dağarcıkta da aynı yönde.

Ortam Hatayı Gösteriyor mu

Dağılım tek başına da yetmez. Bir kalıbı elli kez uygulamak, o kalıbın ön koşulu bozulduğunda ne yaptığını göstermez — ortak tanımın birinci okuması bunu zaten kanıtladı: ön koşul sağlanan 40 girdinin 40’ında iki işaretçi kâhinle aynı yanıtı veriyor; ön koşulu sağlayan girdilerle dolu bir ortamda çalışan biri kalıbın yanlışını hiç görmez.

Burada ölçülen şey ortamın karışımıdır: girdilerin yüzde kaçı ön koşulu sağlıyor, ve bu oran görülen yanlış yanıt sayısını nasıl değiştiriyor. İki seçim politikası karşılaştırılır.

• AD26 — Havuz tabanlı ortamda girdilerin yüzde 90’ı, zamanlı yarışmada yüzde 75’i, şirket içi değerlendirmede yüzde 50’si ön koşulu sağlar. Havuzda problemler kalıba göre hazırlanmıştır, değerlendirmede girdi olduğu gibi gelir.
• AD27 — Alışkanlıkla seçim, en çok pratik edilen kalıbı her probleme uygular ve ön koşulu sınamaz.
• AD28 — Ön koşul kontrolüyle seçim, önce girdinin sıralı olup olmadığına bakar; sıralı değilse kalıbı uygulamaz, kâhine düşer. Sınama en fazla $n-1$ adımdır ve ilk aykırı çiftte durur.
• AD29 — Her ortamda 40 problem çözülür ve hedef 11’dir.

"""Iki secim politikasi , kahin karsisinda , uc ortam karisimi."""
TOHUM, IKINCI = 20260218, 20260219


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self, n=1):
        self.adim += n


def karisim(sirali_oran, tohum=TOHUM, n=40, uzunluk=12):
    """sirali_oran: girdilerin yuzde kaci on_kosulu sagliyor."""
    r = uretec(tohum)
    kume = []
    for _ in range(n):
        dizi = [r(30) - 9 for _ in range(uzunluk)]
        kume.append(sorted(dizi) if r(100) < sirali_oran else dizi)
    return kume


def kahin_ciftler(dizi, hedef, s):
    for i in range(len(dizi)):
        for j in range(i + 1, len(dizi)):
            s.say()
            if dizi[i] + dizi[j] == hedef:
                return True
    return False


def iki_isaretci(dizi, hedef, s):
    sol, sag = 0, len(dizi) - 1
    while sol < sag:
        s.say()
        t = dizi[sol] + dizi[sag]
        if t == hedef:
            return True
        sol, sag = (sol + 1, sag) if t < hedef else (sol, sag - 1)
    return False


def aliskanlik(dizi, hedef, s):
    """En cok pratik edilen kalibi her probleme uygular."""
    return iki_isaretci(dizi, hedef, s)


def on_kosul_kontrolu(dizi, hedef, s):
    """Once on_kosulu sinar; saglanmiyorsa kahine duser."""
    for i in range(len(dizi) - 1):
        s.say()
        if dizi[i] > dizi[i + 1]:
            return kahin_ciftler(dizi, hedef, s)
    return iki_isaretci(dizi, hedef, s)


def olc(politika, kume, hedef=11):
    ayrilan, ak, ah = 0, 0, 0
    for dizi in kume:
        s1, s2 = Sayac(), Sayac()
        a = politika(list(dizi), hedef, s1)
        b = kahin_ciftler(list(dizi), hedef, s2)
        ak, ah = ak + s1.adim, ah + s2.adim
        if a != b:
            ayrilan += 1
    return ayrilan, ak, ah


ORTAM = [("havuz tabanli alistirma ", 90), ("zamanli yarisma         ", 75),
         ("sirket ici degerlendirme", 50)]

for tohum in (TOHUM, IKINCI):
    print(f"tohum {tohum} , her ortamda 40 problem , hedef 11")
    print("ortam                     sirali  aliskanlik      on_kosul kontrolu   kahin")
    print("                          girdi   ayrilan  adim   ayrilan  adim      adim")
    for ad, oran in ORTAM:
        K = karisim(oran, tohum)
        s = sum(1 for d in K if d == sorted(d))
        a1, k1, h1 = olc(aliskanlik, K)
        a2, k2, _ = olc(on_kosul_kontrolu, K)
        print(f"{ad}  {s:6d}  {a1:7d}  {k1:4d}   {a2:7d}  {k2:4d}      {h1:4d}")
    print()

tohum 20260218 , her ortamda 40 problem , hedef 11
ortam                     sirali  aliskanlik      on_kosul kontrolu   kahin
                          girdi   ayrilan  adim   ayrilan  adim      adim
havuz tabanli alistirma       34        5   165         0   600       834
zamanli yarisma               29        8   199         0   681       914
sirket ici degerlendirme      17       15   255         0   754       856

tohum 20260219 , her ortamda 40 problem , hedef 11
ortam                     sirali  aliskanlik      on_kosul kontrolu   kahin
                          girdi   ayrilan  adim   ayrilan  adim      adim
havuz tabanli alistirma       36        2   213         0   609      1055
zamanli yarisma               31        4   238         0   691      1079
sirket ici degerlendirme      22       10   296         0   823      1161

Üç sayı yan yana. Kâhin: havuz karışımında 834 adım, 40 girdinin 40’ında doğru. Kalıp: alışkanlıkla seçim 165 adım, ön koşul kontrolüyle seçim 600 adım. Ayrılan girdi: alışkanlıkla seçim havuzda 5, yarışmada 8, değerlendirmede 15; ön koşul kontrolü üç ortamda da 0.

Birinci okuma ortamla ilgilidir. Aynı politika, aynı kalıp, aynı problem sayısı — ve gördüğü yanlış yanıt sayısı 5’ten 15’e, üç katına çıkıyor. Farkı yaratan tek şey ortamın girdi karışımıdır: havuzda 40 girdinin 34’ü ön koşulu sağlıyor, değerlendirmede 17’si. Hazırlanmış girdilerle çalışan biri kalıbının yanlışını daha az görür, ve az görmek düzelmek değildir.

İkinci okuma politikayla ilgilidir. Ön koşul kontrolü üç ortamda da 0 ayrılan girdi veriyor, yani hiç yanılmıyor; bedeli havuz karışımında 165 adımdan 600 adıma çıkmak, yani 3,64 kat. Buna karşılık kâhinin 834 adımının hâlâ altında: kontrol, doğruluğu kaba kuvvet pahasına değil, kaba kuvvetin yüzde 72’si pahasına satın alıyor. İkinci dağarcık aynı sıralamayı veriyor (2, 4, 10) ve ön koşul kontrolü orada da üç ortamda 0 ayrılan girdi üretiyor; mutlak sayılar dağarcığa bağlı, sıralama değil.

Buradan tekrarlı çalışmanın ilerleme ölçütü çıkar ve üç sayıdan oluşur: kaç kalıp görüldü, dağılımın denge oranı, ve kaç kalıp ön koşulu bozulmuş hâlde görüldü. Çözülen problem sayısı bu üçünün hiçbirini vermez.

Özet

• Ortamlar türleriyle ayrılır: havuz tabanlı alıştırmada dağılımı çalışan seçer, zamanlı yarışmada ve şirket içi değerlendirmede ortam seçer ve küme küçüktür.
• Çözülen problem sayısı ortamları 12 kat ayırıyor (144, 30, 12) ama kapsanan kalıp sayısı üçünde de 5; iki ölçüt de ilerlemeyi göstermiyor.
• Ayırt eden ölçüt dağılımdır: havuz tabanlı ortamda denge oranı 0,2431 ve baskın iki kalıp problemlerin 0,7986’sını kaplıyor; zamanlı yarışma beş kat az problemle 0,6667 veriyor.
• Kapsama ikinci turda 5’e çıkıp donuyor, denge oranı üçüncü turda 0,2778 ile tepe yapıp 0,2431’e geriliyor — problem eklemek ölçütü kötüleştirebiliyor.
• Ortamın girdi karışımı görülen yanlışı belirliyor: aynı politika havuzda 5, yarışmada 8, şirket içi değerlendirmede 15 ayrılan girdi üretiyor.
• Ön koşul kontrolüyle seçim üç ortamda da 0 ayrılan girdi veriyor; bedeli 165 adımdan 600 adıma çıkmak, yani kâhinin 834 adımının yüzde 72’si.

Kurs Kapanışı

Yirmi üç ders tek bir soruyu sordu: bir kalıp seçmek neyi kabul etmektir. Yanıt her derste üç sayıyla verildi. Kâhin her zaman kaba kuvvetti ve her zaman doğruydu — ama her zaman pahalı değildi: En Uzun Yol Problemi sekiz düğümde kâhini 562, kalıbı 3626 adımda ölçtü ve eşiğin on düğümde olduğunu gösterdi. Kalıp genellikle daha az adım harcadı. Ayrılan girdi, kalıbın kâhinden farklı yanıt verdiği girdi sayısıydı. Kursun kuralı buydu: bir kalıbın sayısı kazandırdığı adım değil, ön koşulu bozulduğunda verdiği yanlış yanıt sayısıdır.

Ders	Kâhin (adım)	Kalıp (adım)	Ayrılan girdi / bedel
Kaba Kuvvet	tam sayım 2640	eleme 866	eleme 0; örnekleme 406’da 14
Böl ve Yönet	3120	doğrusal birleştirme 2680	0; eksik birleştirme 920’de 40/40
Açgözlü Algoritmalar	alttan yukarı	açgözlü	969 sistemin 827’si (0,8535); en büyük fazlalık 16 para
Dinamik Programlama	163.840	tam anahtarlı not alma 2440 (67,15 kat az)	0; eksik anahtar 39/40; örtüşme yokken defter 19 giriş boşa
Geri İzleme	budamasız 960.800 düğüm, n=7	budamalı 552 düğüm	1740,6 kat, oran n ile büyür (72,3 → 8156,2); aşırı budama 0 çözüm
Rastgeleleştirme	780	doğrulamalı örnekleme 944–1056	0; doğrulamasız 200’de, ön koşul bozukken 40/40
İki İşaretçi	972	154 (6,31 kat az)	sırasızda 25/40, hızlanma 2,33 kata
Kayan Pencere	2396	867 (2,76 kat az)	negatifte 10/40, daha az adımda
Hızlı ve Yavaş İşaretçi	480	299	ikinci kenarda 14/40; adım hiç değişmez
Aralık Birleştirme	başlangıca göre sıralama: 40/40 doğru	2154	bitişe göre 29/40, uzunluğa göre ve sıralamasız 40/40
Döngüsel Yerleştirme	1..n, tekrarsız	karşılaştırmasız	tekrarlıda yalın 40/40, korumalı 39/40, eksikte 0/40
İki Yığın	480 ortanca	denge adımıyla 1261	dengesiz 295/480 yanlış; denge kalıbın yarısından fazlası (1261/550)
K’ıncı Eleman	dört k x 40 girdi	k boyutlu yığın	0/40; “k’ıncı ayrı değer” ayrı sorudur: 27/40
Izgara Gezinmesi	aynı komşulukla 40/40	bağlı bileşen	tanımlar ayrılınca 38/40
Sırt Çantası	bölünebilirde 100.800	açgözlü 174	bölünebilirde 0/40; aynı sıra 0/1’de 5/40, kayıp 7
Gezgin Satıcı	352.800 (20 örnek)	en yakın komşu 560	17/20; sapma ort. 9,3, en kötü 33,33; iki değişim 2/20
En Uzun Yol	çevrimsizde 40/40	gevşetme yordamı	çevrimlide 38/40; en büyük fazla tahmin 228
N Vezir	budamalı 2057 düğüm, n=8	simetri elemesiyle 1029	oran 2,00, beş boyda sabit; budamanınki büyür, simetrininki büyümez
At Turu ve Labirent	yol modeli 90.111	hücre modeli 25	oran 3604, ayrılan 0
Hamilton Yolları	sayma 29.270	karar 1526	oran 19,18; yol bulunmayanların hepsinde karar = sayma
Problem Okuma ve Kısıt	866	karma tablo 486, sıralayan kalıp 1398, sayma 396	yanlış kısıt okuması 40 girdinin 18’inde ayrılıyor (ikinci dağarcıkta 17); n=10<sup>8</sup>’de üç çözüm de bütçeye sığmıyor
Çözüm Doğrulama	kaba kuvvet, 52 girdide 1596	doğru iki işaretçi 329	40 rastgele girdi 5 kusurun 4’ünü, 12 kenar durumu 5’ini yakalıyor; aynı kusuru paylaşan kâhinde ayrılan 3’ten 0’a düşüyor
Alıştırma Ortamları	834	alışkanlıkla seçim 165, ön koşul kontrolü 600	havuzda 5, yarışmada 8, değerlendirmede 15 ayrılan girdi; ön koşul kontrolü 0 ayrılan ama 3,64 kat adım

Tablonun ikinci okuması birincisinden değerlidir: hızlandırma yanlışa yaklaştırır ve bazen hızlandırmaz bile. Sırasız girdide iki işaretçinin hızlanması 2,33 kata düşerken 25 girdide yanılıyor; açgözlü 969 sistemin 827’sinde fazla veriyor; not alma örtüşme yokken 19 girişi boşa tutuyor. Hiçbiri saklanmadı: bir kalıbın ne zaman yanıldığını bilmeyen, onu ne zaman seçeceğini de bilemez.

Üçüncü ve kalıcı sonuç kâhinin kendisiyle ilgilidir: kaba kuvvet bir taban değil, bir kâhindir. Kursun bütün sayıları onun sayesinde yazılabildi. Son derste bu bir alışkanlığa döndü: doğruluğu bir görüşe değil, ikinci bir çözümün yanıtına karşı saymak.

Bir sonraki kurs, Hesaplama Kuramı, kâhinin gölgesinde bırakılan soruyu alır. Gezgin satıcı ve Hamilton yolları derslerinde “bu problem neden zor” sorusu açıkça ertelendi. Orada sorulacak olan şudur: bazı problemler için kaba kuvvetten daha iyisinin bilinmemesi, bilgimiz hakkında mı yoksa problemler hakkında mı bir gerçektir. Yanıt karar verilebilirlik, indirgeme ve karmaşıklık sınıflarıyla verilecek.