Kaba Kuvvet ve Sınırları

Algoritmalar kursu bir ölçüt kurarak kapandı: işlem sayımı, asimptotik gösterim, alt sınır. O kursta ölçülen tek şey maliyetti, çünkü her algoritmanın doğru olduğu varsayılmıştı. Bu kurs o varsayımı kaldırarak açılır.

Bir tasarım kalıbı seçmek yalnız hızlanmak değildir; bir ön koşulu (precondition) kabul etmektir. Ön koşul bozulduğunda kalıp yavaşlamaz — yanlış yanıt verir, ve yanlışlığı çıktısına bakarak anlaşılmaz, çünkü yine bir sayı döndürür. Bu yüzden kursun merkezinde kaba kuvvet (brute force) durur; ama burada “yavaş seçenek” olarak değil, kâhin (oracle) olarak durur. 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; ön koşulu kâhinle sınanmayan kalıp ölçülmemiş sayılır.

• TY1. Ölçü adımdır, süre değil. Hiçbir derste gerçek zaman ölçülmez.
• TY2. Tohum 20260218. Aynı tohum aynı dağarcığı verir; buradaki her sayı yeniden üretilebilir.
• TY3. Dağarcık (input corpus) 40 diziden oluşur; her dizi 12 değer taşır ve değerler -9 ile 20 arasındadır.
• TY4. Bir adım, iki değerin toplanıp hedefle karşılaştırılmasıdır. Sayaç her adımı bir sayar.
• TY5. Kâhin her zaman kaba kuvvettir: bütün olasılıkları gören, erken çıkmayan yordam. Kâhinin yanıtı tanım gereği doğru sayılır.
• TY6. Bir adayın doğruluğu ancak kâhinle karşılaştırılarak iddia edilir. Kâhinsiz doğruluk iddiası yazılmaz.
• TY7. Ayrılan girdi, kâhin ile adayın farklı yanıt verdiği girdidir; 40 üzerinden sayılır.
• TY8. Çözünürlük: 40 girdide 1 ayrılma ölçülmemiş sayılır, 3 ve üzeri anlamlıdır.
• TY9. Rastgelelik belirlenimci bir üreteçle modellenir; standart kitaplığın rastgele sayı üreteci kullanılmaz.
• TY10. Her ölçüm 20260219 tohumlu ikinci bir dağarcıkta da koşturulur.

Kaba Kuvvet Neden Kâhin Olabiliyor

Kaba kuvvet, çözüm uzayının tamamını sayan yordamdır: bütün ikilileri, bütün alt kümeleri, bütün sıralamaları. Algoritmalar kursunun metin algoritmaları konusunda kaba kuvvet örüntü arama bir taban olarak kurulmuştu; oradaki soru, daha akıllı yordamların o tabandan kaç karşılaştırma kazandığıydı. Burada rol değişir.

Kaba kuvvetin bu kurstaki ayrıcalığı hızıyla değil, ön koşulsuz olmasıyla ilgilidir. İki işaretçi dizinin sıralı olmasını ister, kayan pencere değerlerin negatif olmamasını, açgözlü seçim yerel seçimin küresel çözüme uymasını. Tam sayımın böyle bir isteği yoktur: bütün olasılıkları gördüğü için hiçbir varsayımı bozulamaz. Bozulacak varsayımı olmayan tek yordam, başkalarının bozulmuş varsayımını ölçebilecek tek yordamdır.

Bunun bedeli her derste ödenir. Kâhin pahalıdır ve pahalılığı kusur değil, kâhinliğin karşılığıdır. Bir kalıbın kâhinden hızlı olması bir başarı değildir; kâhinle aynı yanıtı verirken hızlı olması bir başarıdır. Bu ayrımı sayıya çeviren şey, ayrılan girdi sayısıdır.

Ölçüm Çerçevesi

Kursun bütün ölçümleri aynı dağarcık ve aynı sayaç üzerinde yapılır. Dağarcık, ön koşulları kasıtlı olarak bozan girdilerden kurulur; ön koşulu sağlayan öbekler ondan türetilir.

# Olcum cercevesi: dagarcik ve adim sayaci. Sure degil ADIM sayilir.
TOHUM = 20260218
UZUNLUK = 12
DAGARCIK = 40


def uretec(tohum):
    """Belirlenimci uretec. Ayni tohum ayni dagarcigi verir."""
    d = tohum

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


def dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK):
    r = uretec(tohum)
    kume = []
    for i in range(n):
        dizi = [r(30) - 9 for _ in range(uzunluk)]        # -9 .. 20
        kume.append({"no": i + 1, "dizi": dizi,
                     "negatif": any(x < 0 for x in dizi),
                     "sirali": dizi == sorted(dizi)})
    return kume


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

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


K = dagarcik()
print("dagarcik:", len(K), "dizi x", UZUNLUK, "deger")
print("sirali olan:", sum(1 for k in K if k["sirali"]),
      "| negatif iceren:", sum(1 for k in K if k["negatif"]))
print("ilk dizi:", K[0]["dizi"])

dagarcik: 40 dizi x 12 deger
sirali olan: 0 | negatif iceren: 40
ilk dizi: [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1]

Kırk dizinin sıfırı sıralı, kırkı negatif değer içeriyor. Bu bir kaza değil, tasarımdır: taban dağarcık, kursun ele alacağı ön koşulların çoğunu ihlal eder. Ön koşulu sağlayan öbekler bu diziler sıralanarak ya da mutlak değerleri alınarak üretilir, böylece iki öbek aynı üreteçten gelir ve aralarındaki tek fark ön koşulun kendisi olur.

Kâhinin Adımı ve İki Kısaltma

Ölçülen problem şudur: bir dizide, toplamı hedefe eşit iki ayrı konum var mı. Hedef 11 alınır. Üç yordam yazılır. İlki kâhindir: bütün ikilileri görür, uyum bulsa bile durmaz. İkincisi bir eleme uygular, ilk uyumda çıkar. Üçüncüsü bir örnekleme uygular, yalnız ilk altı konuma bakar.

# Onceki blogun uzerine: dagarcik, Sayac ve K oradan gelir.
HEDEF = 11


def kahin_tam(dizi, hedef, s):
    """Butun ciftleri gorur, erken cikmaz. Hakem budur."""
    bulundu = False
    for i in range(len(dizi)):
        for j in range(i + 1, len(dizi)):
            s.say()
            if dizi[i] + dizi[j] == hedef:
                bulundu = True
    return bulundu


def erken_cikan(dizi, hedef, s):
    """ELEME: ilk uyumda durur. Atlanan ciftler yaniti degistiremez."""
    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 orneklemeli(dizi, hedef, s, bak=6):
    """ORNEKLEME: yalniz ilk 'bak' konuma bakar. Gorulmeyen cift bilinmez."""
    for i in range(min(bak, len(dizi))):
        for j in range(i + 1, min(bak, len(dizi))):
            s.say()
            if dizi[i] + dizi[j] == hedef:
                return True
    return False


def olc(aday, kahin, kume, hedef):
    """Adayi kahinle karsilastirir; ayrilan girdiyi sayar."""
    ayrilan, aa, ah = [], 0, 0
    for k in kume:
        s1, s2 = Sayac(), Sayac()
        if aday(k["dizi"], hedef, s1) != kahin(k["dizi"], hedef, s2):
            ayrilan.append(k["no"])
        aa += s1.adim
        ah += s2.adim
    return {"girdi": len(kume), "ayrilan": len(ayrilan), "ayrilan_no": ayrilan[:6],
            "aday_adim": aa, "kahin_adim": ah,
            "oran": round(ah / aa, 2) if aa else 0.0}


s = Sayac()
for k in K:
    kahin_tam(k["dizi"], HEDEF, s)
print("kahin (tam sayim) toplam adim:", s.adim)
print("eleme    ", olc(erken_cikan, kahin_tam, K, HEDEF))
print("ornekleme", olc(orneklemeli, kahin_tam, K, HEDEF))

kahin (tam sayim) toplam adim: 2640
eleme     {'girdi': 40, 'ayrilan': 0, 'ayrilan_no': [], 'aday_adim': 866, 'kahin_adim': 2640, 'oran': 3.05}
ornekleme {'girdi': 40, 'ayrilan': 14, 'ayrilan_no': [1, 2, 3, 4, 8, 9], 'aday_adim': 406, 'kahin_adim': 2640, 'oran': 6.5}

Üç sayı yan yana duruyor. Kâhin 40 girdide 2640 adım harcıyor; bu, dizi başına tam olarak 66 ikilidir ve girdiye göre değişmez. Eleme 866 adım harcıyor, yani kâhinin 3,05 katı azını, ve 40 girdinin hiçbirinde kâhinden ayrılmıyor. Örnekleme 406 adım harcıyor, kâhinin 6,50 katı azını, ve 40 girdinin 14’ünde kâhinden ayrılıyor. Ayrılan girdi oranı 0,3500’dür ve çözünürlüğün çok üstündedir.

Bu üç satırın taşıdığı ders, kursun geri kalanının çerçevesidir. Kısaltmanın iki türü vardır ve ikisi çıktıya bakarak ayırt edilemez. Eleme, atladığı ikililerin yanıtı değiştiremeyeceğini bildiği için doğruluğu korur: uyum zaten bulunmuşsa geri kalan ikililer yanıtı True olmaktan çıkaramaz. Örnekleme böyle bir bilgiye dayanmaz; görmediği ikililer hakkında hiçbir güvencesi yoktur ve 14 girdide gerçekten yanılır.

Ayrılan girdilerin numaraları da bir örüntü taşır. Çıktıdaki ilk altısı 1, 2, 3, 4, 8 ve 9’dur; bunların ortak yanı, hedefi tutturan her ikilinin en az bir ucunun ilk altı konumun dışında kalmasıdır. Örnekleme o ikilileri hiç görmez ve “yok” yanıtı verir. Yanılgının nedeni bir hesap hatası değil, görülmeyen bir bölgeyle ilgili varsayımdır; bu, kursun bütün kalıp yanılgılarının ortak biçimidir.

Sayıların sırası da anlamlıdır. Yanlış olan, doğru olandan hızlıdır: örnekleme 406, eleme 866 adım. Hızlanma tek başına ölçüldüğünde örnekleme kazanır. Ölçüye ayrılan girdi eklendiği anda sıralama tersine döner. Bu, kursun ikinci iddiasının ilk biçimidir: hızlandırma yanlışa yaklaştırır, ve yanlışlık ucuz olduğu için çekicidir.

Tam Aramanın Sınırı

Kaba kuvvetin ne zaman kabul edilebilir olduğu sorusu, bir adım bütçesiyle yanıtlanır: bir koşumda göze alınan adım sayısı belirlenir ve her arama ailesinin o bütçeye hangi girdi büyüklüğüne kadar sığdığı hesaplanır. Bütçe burada yüz milyon adım alınmıştır.

from math import comb, factorial

BUTCE = 10**8          # bir kosumda goze alinan adim ust siniri


def sigan_n(sayim, ust=20000):
    """Adim butcesine sigan en buyuk n."""
    en = 0
    for n in range(1, ust + 1):
        if sayim(n) > BUTCE:
            break
        en = n
    return en


AILE = (("ikili secim", lambda n: comb(n, 2)),
        ("uclu secim", lambda n: comb(n, 3)),
        ("alt kume", lambda n: 2 ** n),
        ("siralama", factorial))

print("tam tarama ailesi  n=12 adim           n=20 adim  butceye sigan n")
for ad, f in AILE:
    print(f"  {ad:13s} {f(12):10d} {f(20):19d} {sigan_n(f):15d}")
print("adim butcesi:", BUTCE)

tam tarama ailesi  n=12 adim           n=20 adim  butceye sigan n
  ikili secim           66                 190           14142
  uclu secim           220                1140             844
  alt kume            4096             1048576              26
  siralama       479001600 2432902008176640000              11
adim butcesi: 100000000

Dört aile aynı bütçede dört ayrı dünyaya karşılık geliyor. İkili seçim on dört binin üzerinde bir girdiyi kaldırıyor; üçlü seçim 844’te duruyor; bütün alt kümeleri sayan arama 26’da, bütün sıralamaları sayan arama 11’de duruyor. Aradaki uçurum, bu kursun neden yalnız hızlanma değil kalıp seçimi öğrettiğinin nedenidir: sıralama ailesinde kalan bir çözüm, girdi bir eleman büyüdüğünde bütçesini bir daha aşar.

Sınırın kâhin rolünü ortadan kaldırmadığına dikkat etmek gerekir. Bir yordam üretimde n=1000 ile çağrılacak olsa bile, kâhinle karşılaştırma n=12’lik bir dağarcıkta yapılır; orada tam sayım 2640 adımdır ve hiçbir bütçeyi zorlamaz. Kaba kuvvet çözüm olarak küçük girdilerde biter, ölçüm aracı olarak her derste kullanılabilir kalır.

Dağarcığın Boyu Kâhinin Bütçesidir

Bir önceki tablo, dağarcığın neden on iki elemanlı dizilerden kurulduğunu da açıklar. Kurs boyunca kâhin yalnız ikili seçim ailesinde kalmayacak; bazı problemlerde bütün alt kümeleri taramak gerekecek. O tarama, dağarcığın eleman sayısına doğrudan bağlıdır.

# Onceki bloklarin uzerine: dagarcik, Sayac ve UZUNLUK oradan gelir.
SINIR = 30


def kahin_alt_kume(dizi, sinir, s):
    """Toplami siniri asmayan en buyuk alt kume toplami. Butun alt kumeler taranir."""
    en_iyi = 0
    for maske in range(1 << len(dizi)):
        s.say()
        toplam = sum(dizi[i] for i in range(len(dizi)) if maske >> i & 1)
        if toplam <= sinir and toplam > en_iyi:
            en_iyi = toplam
    return en_iyi


K = dagarcik()
s = Sayac()
for k in K:
    kahin_alt_kume(k["dizi"], SINIR, s)
print("dizi basina alt kume:", 2 ** UZUNLUK, "| 40 dizide kahin adimi:", s.adim)
for uzunluk in (12, 16, 20, 26):
    print(f"  uzunluk {uzunluk:2d} -> 40 dizide {40 * 2 ** uzunluk:12d} adim",
          "(butce icinde)" if 40 * 2 ** uzunluk <= 10**8 else "(butce disinda)")

dizi basina alt kume: 4096 | 40 dizide kahin adimi: 163840
  uzunluk 12 -> 40 dizide       163840 adim (butce icinde)
  uzunluk 16 -> 40 dizide      2621440 adim (butce icinde)
  uzunluk 20 -> 40 dizide     41943040 adim (butce icinde)
  uzunluk 26 -> 40 dizide   2684354560 adim (butce disinda)

On iki elemanlı bir dizide 4096 alt küme vardır; kırk dizide kâhin 163.840 adım harcar ve bütçenin binde ikisini kullanır. Aynı kâhin yirmi elemanlı dizilerde 41.943.040 adıma çıkar — hâlâ sığar, ama bütçenin yüzde kırkını yer. Yirmi altı elemanda dağarcığın kendisi bütçeyi yirmi yedi kat aşar.

Buradan çıkan kural, kursun ölçüm düzeninin temelidir: dağarcığın eleman sayısı, ölçülecek en pahalı kâhine göre seçilir. On iki, kırk girdilik bir dağarcıkta alt küme taramasını bile taşıyan en büyük rahat sayıdır. Dağarcığı büyütmek daha zengin girdi vermez; yalnız kâhini ulaşılmaz kılar ve ölçümü ortadan kaldırır. Kalıbı hızlandırmanın bir sınırı olduğu gibi, kalıbı sınamanın da bir sınırı vardır ve ikisi aynı bütçeden ödenir.

İkinci Dağarcık

Tek bir dağarcıkta ölçülen oranın dağarcığa bağlı olup olmadığı ayrıca sınanır.

# Onceki bloklarin uzerine: dagarcik, olc ve uc yordam oradan gelir.
for ad, tohum in (("birinci dagarcik (20260218)", 20260218),
                  ("ikinci  dagarcik (20260219)", 20260219)):
    kume = dagarcik(tohum)
    e = olc(erken_cikan, kahin_tam, kume, HEDEF)
    o = olc(orneklemeli, kahin_tam, kume, HEDEF)
    print(ad)
    print("  eleme    : ayrilan", e["ayrilan"], "/ 40 | oran",
          round(e["ayrilan"] / 40, 4), "| aday adim", e["aday_adim"])
    print("  ornekleme: ayrilan", o["ayrilan"], "/ 40 | oran",
          round(o["ayrilan"] / 40, 4), "| aday adim", o["aday_adim"])

birinci dagarcik (20260218)
  eleme    : ayrilan 0 / 40 | oran 0.0 | aday adim 866
  ornekleme: ayrilan 14 / 40 | oran 0.35 | aday adim 406
ikinci  dagarcik (20260219)
  eleme    : ayrilan 0 / 40 | oran 0.0 | aday adim 970
  ornekleme: ayrilan 21 / 40 | oran 0.525 | aday adim 512

Elemenin ayrılan girdisi iki dağarcıkta da sıfırdır; bu beklenen sonuçtur, çünkü elemenin doğruluğu girdiye değil, atlanan dalların yanıtı değiştiremeyeceği gözlemine dayanır. Örneklemenin oranı 0,3500’den 0,5250’ye çıkıyor. İki oran aynı büyüklük düzenindedir — ikisi de girdilerin üçte biri ile yarısı arasında — ama aradaki fark çözünürlüğün çok üstündedir. Okuma şudur: örneklemenin yanıldığı girdi vardır ve sayıcadır; kaç girdide yanıldığı dağarcığa bağlıdır ve tek bir sayıyla bildirilemez.

Özet

• Kaba kuvvet bu kursta bir yavaş seçenek değil kâhindir; ayrıcalığı hızından değil, bozulacak bir ön koşulu olmamasından gelir.
• Aynı problemde kâhin 40 girdide 2640 adım, eleme 866 adım (3,05 kat az, 0 ayrılan girdi), örnekleme 406 adım (6,50 kat az, 14 ayrılan girdi) harcıyor.
• Kısaltmanın iki türü çıktıdan ayırt edilemez: eleme atladığı dalların yanıtı değiştiremeyeceğini bilir, örnekleme bilmez.
• Yanlış olan, doğru olandan hızlıdır; ölçüye ayrılan girdi eklenmedikçe örnekleme kazanmış görünür.
• Yüz milyon adımlık bütçede ikili seçim 14.142, üçlü seçim 844, alt küme araması 26, sıralama araması 11 elemana kadar sığar; kâhin rolü bu sınırdan etkilenmez çünkü ölçüm 12 elemanlık dağarcıkta yapılır.
• İkinci dağarcıkta elemenin ayrılan girdisi yine 0, örneklemeninki 14 yerine 21; oran aynı büyüklük düzeninde kalıyor ama tam değeri dağarcığa bağlıdır.

Sonraki Adım

Bu derste kaba kuvvet bölünmeden, tek parça olarak koştu. İlk tasarım kalıbı problemi parçalar: aynı problemi daha küçük iki kopyasına indirir, her birini çözer ve sonuçları birleştirir. Sonraki ders bu kalıbın bağıntısını kurar ve iki soruyu sayar — birleştirme adımı eksik kaldığında kaç girdide yanlış yanıt çıkıyor, ve bölmenin adım kazandırmadığı girdi büyüklüğü nerede bitiyor.