Rastgeleleştirilmiş Algoritmalar

Buraya kadarki bütün yordamlar belirlenimciydi: aynı girdi her zaman aynı adımları ve aynı yanıtı veriyordu. Son tasarım yaklaşımı bu güvenceyi gevşetir. Yordamın içine bir rastgele seçim konur ve karşılığında bir şey umulur — ya arama alanının kötü bölgelerine takılmamak, ya da tam sayım yapmadan bir yanıta ulaşmak.

Gevşetilen güvencenin hangisi olduğu belirleyicidir ve iki seçenek vardır. Birincisinde yanıt kesin kalır, yalnız adım sayısı rastgeleleşir; yordam her zaman doğru yanıtı verir, ne kadar adımda vereceği belli değildir. İkincisinde adım sayısı sınırlı kalır, yanıt olasılıklı olur; yordam hızlıdır ama bazen yanılır. Bu ders ikisini de aynı ölçüyle sayar ve rastgeleliği bu kursun kuralına göre modeller: belirlenimci bir üreteçle.

• TY47. Rastgelelik belirlenimci bir üreteçle modellenir; standart kitaplığın rastgele sayı üreteci kullanılmaz. Her koşum tohumuyla yeniden üretilebilir.
• TY48. İki tohum kullanılır: 20260218 ve 20260219. Rastgele bir yordamın sonucu tek tohumla bildirilmez.
• TY49. Ölçülen ilk problem: 15 değerli bir dizide çoğunluk elemanı — uzunluğun yarısından çoğunu kaplayan değer. Yoksa doğru yanıt “yok”tur.
• TY50. Kâhin her değeri tek tek sayar; hiçbir örnekleme yapmaz.
• TY51. Dağarcık iki öbektir: çoğunluğu olan 40 dizi ve olmayan 40 dizi.
• TY52. Bir adım, bir örnek çekmek ya da bir değeri karşılaştırmaktır.
• TY53. Kalıbın ön koşulu: çoğunluk elemanının var olması. İkinci öbek bu ön koşulu bozar.
• TY54. Ölçülen ikinci problem: vezir yerleşiminde ilk çözümü bulmak; sütun sırası rastgeleleştirilir.
• TY55. Rastgele adım sayısı en az, ortalama ve en çok olarak bildirilir; yirmi koşum alınır ve tek bir sayı yeterli sayılmaz.
• TY56. Beklenen başarım adımın ortalamasıdır, süre değildir.

Rastgelelik Nasıl Modellenir

Bu kursta rastgelelik bir kütüphane çağrısı değil, tohumlu bir üreteçtir. Nedeni ölçmedir: bir rastgele yordamın ayrılan girdi sayısı ancak koşum yeniden üretilebilirse bildirilebilir.

# Rastgelelik belirlenimci uretecle modellenir; standart kitapligin ureteci kullanilmaz.
UZUNLUK = 15


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

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


def uretec(tohum):
    d = tohum

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


def cogunluklu(tohum, adet=40, cogunluk=True):
    """cogunluk=True -> bir deger uzunlugun yarisindan cok yer tutar."""
    r = uretec(tohum)
    kume = []
    for i in range(adet):
        baskin = r(6)
        pay = 8 + r(3) if cogunluk else 5 + r(3)      # 8..10 ya da 5..7
        dizi = [baskin] * pay + [6 + r(6) for _ in range(UZUNLUK - pay)]
        for j in range(len(dizi) - 1, 0, -1):          # belirlenimci karistirma
            k = r(j + 1)
            dizi[j], dizi[k] = dizi[k], dizi[j]
        kume.append({"no": i + 1, "dizi": dizi})
    return kume


def kahin_cogunluk(dizi, s):
    """Her degeri tek tek sayar. Hakem budur."""
    for i in range(len(dizi)):
        sayi = 0
        for j in range(len(dizi)):
            s.say()
            if dizi[j] == dizi[i]:
                sayi += 1
        if sayi * 2 > len(dizi):
            return dizi[i]
    return None


VAR = cogunluklu(20260218)
YOK = cogunluklu(20260218, cogunluk=False)
s1, s2 = Sayac(), Sayac()
v = sum(1 for k in VAR if kahin_cogunluk(k["dizi"], s1) is not None)
y = sum(1 for k in YOK if kahin_cogunluk(k["dizi"], s2) is not None)
print("cogunluklu dagarcik: 40 dizi x", UZUNLUK, "deger | cogunlugu olan:", v)
print("cogunluksuz dagarcik:", 40, "dizi | cogunlugu olan:", y)
print("kahin adimi:", s1.adim, "(cogunluklu) |", s2.adim, "(cogunluksuz)")

cogunluklu dagarcik: 40 dizi x 15 deger | cogunlugu olan: 40
cogunluksuz dagarcik: 40 dizi | cogunlugu olan: 0
kahin adimi: 780 (cogunluklu) | 9000 (cogunluksuz)

İki öbek de kurulmuş: birinde 40 dizinin 40’ında çoğunluk var, ötekinde hiçbirinde yok. Kâhinin adım sayısındaki fark da anlamlıdır — 780’e karşı 9000. Çoğunluk varsa kâhin genellikle ilk denediği değerde bulur ve durur; çoğunluk yoksa 15 değerin hepsini sonuna kadar saymak zorunda kalır, yani dizi başına tam 225 adım. Bir yordamın en pahalı hâli, yanıtın “yok” olduğu hâldir.

Olasılıklı Yanıt ve Doğrulamanın Rolü

Çoğunluk elemanı için rastgele bir yordam tek cümleyle kurulur: rastgele bir konum seç, oradaki değeri aday say. Çoğunluk varsa aday, yarıdan çok olasılıkla doğrudur. Aşağıdaki iki değişke bu fikri paylaşır ve tek bir noktada ayrılır — biri adayı doğrular, öteki doğrulamaz.

# Onceki blogun uzerine: Sayac, uretec, cogunluklu, kahin_cogunluk, VAR oradan gelir.
def orneklemeli_cogunluk(dizi, deneme, r, s, dogrulama=True):
    """deneme kadar rastgele konum secer. dogrulama=True ise adayi sayarak sinar."""
    if dogrulama:
        for _ in range(deneme):
            aday = dizi[r(len(dizi))]
            s.say()
            sayi = 0
            for x in dizi:
                s.say()
                if x == aday:
                    sayi += 1
            if sayi * 2 > len(dizi):
                return aday
        return None
    ornek = []                                    # dogrulama yok: ornegin en siki
    for _ in range(deneme):
        s.say()
        ornek.append(dizi[r(len(dizi))])
    en, en_sik = None, -1
    for a in ornek:
        c = ornek.count(a)
        if c > en_sik:
            en, en_sik = a, c
    return en


def olc(kume, deneme, tohum, dogrulama):
    r = uretec(tohum)
    ayrilan, sk, sh = 0, Sayac(), Sayac()
    for k in kume:
        a = orneklemeli_cogunluk(k["dizi"], deneme, r, sk, dogrulama)
        if a != kahin_cogunluk(k["dizi"], sh):
            ayrilan += 1
    return {"ayrilan": ayrilan, "kalip_adim": sk.adim, "kahin_adim": sh.adim}


print("deneme  tohum      dogrulamali ayrilan/adim   dogrulamasiz ayrilan/adim")
for deneme in (1, 3, 5):
    for tohum in (20260218, 20260219):
        a = olc(VAR, deneme, tohum, True)
        b = olc(VAR, deneme, tohum, False)
        print(f"{deneme:6d}  {tohum}  {a['ayrilan']:12d} / {a['kalip_adim']:5d}"
              f" {b['ayrilan']:16d} / {b['kalip_adim']:4d}")

deneme  tohum      dogrulamali ayrilan/adim   dogrulamasiz ayrilan/adim
     1  20260218            10 /   640               10 /   40
     1  20260219            17 /   640               17 /   40
     3  20260218             0 /   944                6 /  120
     3  20260219             1 /   928               13 /  120
     5  20260218             0 /   944                6 /  200
     5  20260219             0 /  1056                7 /  200

Üç sayı yan yana. Kâhin 780 adım harcıyor. Doğrulamalı örnekleme beş denemede 944 ile 1056 adım harcıyor ve iki tohumda da 0 girdide ayrılıyor. Doğrulamasız örnekleme 200 adım harcıyor — kâhinden neredeyse dört kat az — ve iki tohumda 6 ve 7 girdide ayrılıyor.

Deneme sayısının etkisi iki sütunda farklı. Doğrulamalı sütunda ayrılan girdi 10 ve 17’den üç denemede 0 ile 1’e, beş denemede 0 ile 0’a iniyor: her yeni deneme, önceki denemelerin hepsinin başarısız olma olasılığını yarıdan çok azaltır. Doğrulamasız sütunda ise ayrılan girdi 10 ve 17’den 6 ve 7’ye iniyor ve orada kalıyor; örneklem büyüdükçe iyileşiyor ama sıfıra ulaşmıyor.

Aradaki asıl fark sayının büyüklüğü değil hatanın yönüdür. Doğrulamalı sürüm yanlış bir değer döndüremez; adayı saymadan kabul etmediği için ya doğru değeri verir ya da “yok” der. Bir denemede gördüğümüz 10 ayrılma, on girdide yanlış değer verdiği anlamına gelmez — on girdide bulamadığı anlamına gelir. Doğrulamasız sürüm ise gerçekten yanlış değer döndürür. Doğrulama adımı, hatayı iki yönlüden tek yönlüye çevirir ve bu, 200 adıma karşı 944 adımın satın aldığı şeydir.

Ön koşul Bozulduğunda

Bu ayrımın önemi, çoğunluk elemanı bulunmadığında görünür hâle gelir.

# Onceki bloklarin uzerine: olc, VAR ve YOK oradan gelir.
print("on_kosul  tohum      dogrulamali ayrilan  dogrulamasiz ayrilan")
for ad, kume in (("saglaniyor", VAR), ("bozuk     ", YOK)):
    for tohum in (20260218, 20260219):
        a = olc(kume, 5, tohum, True)
        b = olc(kume, 5, tohum, False)
        print(f"{ad}  {tohum}  {a['ayrilan']:16d}  {b['ayrilan']:20d}")

on_kosul  tohum      dogrulamali ayrilan  dogrulamasiz ayrilan
saglaniyor  20260218                 0                     6
saglaniyor  20260219                 0                     7
bozuk       20260218                 0                    40
bozuk       20260219                 0                    40

Çoğunluğu olmayan 40 dizide doğrulamasız örnekleme 40 girdinin 40’ında kâhinden ayrılıyor; doğrulamalı örnekleme hiçbirinde ayrılmıyor. Sonuç iki tohumda da aynı, yani dağarcığa bağlı değil.

Nedeni açıktır ve kursun genel biçimine uyar. Doğrulamasız yordam, “çoğunluk vardır” varsayımını kodun içine gömmüştür: örneklemin en sık değerini döndürür ve o değerin gerçekten çoğunluk olup olmadığını hiç sormaz. Ön koşul bozulduğunda yavaşlamaz — yine 200 adımda biter — ama her seferinde var olmayan bir yanıtı bildirir. Doğrulama, ön koşulu kodun içinden çıkarıp çalışma anında sınanan bir koşula dönüştürür; bedeli dizi başına bir tam tarama, kazancı ön koşul bozulduğunda sessiz kalmamaktır.

Kesin Yanıt, Rastgele Adım

Rastgeleliğin ikinci kullanımı yanıta hiç dokunmaz. Önceki dersin budamalı vezir araması sütunları her zaman soldan sağa deniyordu; sıra rastgeleleştirildiğinde bulunan çözüm yine geçerlidir, değişen tek şey ona kaç düğümde ulaşıldığıdır.

# Onceki bloklarin uzerine: Sayac ve uretec oradan gelir.
def vezir_ilk_cozum(n, r=None):
    """Ilk cozumde durur. Sutun sirasi rastgele ise adim degisir, yanit degismez."""
    s = Sayac()
    bulunan = None

    def gez(satir, yer):
        nonlocal bulunan
        s.say()
        if satir == n:
            bulunan = tuple(yer)
            return
        sutunlar = list(range(n))
        if r:
            for j in range(n - 1, 0, -1):
                k = r(j + 1)
                sutunlar[j], sutunlar[k] = sutunlar[k], sutunlar[j]
        for sutun in sutunlar:
            if any(sutun == y or abs(sutun - y) == satir - i
                   for i, y in enumerate(yer)):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
            if bulunan is not None:
                return
    gez(0, [])
    return {"dugum": s.adim, "gecerli": bulunan is not None}


print(" n  belirlenimci  tohum      en az  ortalama  en cok  gecerli cozum")
for n in (8, 12, 16):
    b = vezir_ilk_cozum(n)
    for tohum in (20260218, 20260219):
        r = uretec(tohum)
        kosum = [vezir_ilk_cozum(n, r) for _ in range(20)]
        d = [k["dugum"] for k in kosum]
        print(f"{n:2d} {b['dugum']:13d}  {tohum}  {min(d):6d} {sum(d) / 20:9.1f}"
              f" {max(d):7d}  {sum(k['gecerli'] for k in kosum):9d} / 20")

 n  belirlenimci  tohum      en az  ortalama  en cok  gecerli cozum
 8           114  20260218       9      35.7      89         20 / 20
 8           114  20260219      16      35.0     101         20 / 20
12           262  20260218      15      98.7     491         20 / 20
12           262  20260219      17      90.1     356         20 / 20
16         10053  20260218      19     359.6    3379         20 / 20
16         10053  20260219      19     355.8    1237         20 / 20

Son sütun bütün satırlarda 20 / 20: kırk koşumun hepsi geçerli bir yerleşim buluyor. Yanıt rastgele değildir; rastgele olan yalnız adımdır. On altı vezirlik tahtada belirlenimci sıra 10.053 düğüm geziyor, rastgele sıra ortalama 359,6 ve 355,8 düğüm — yaklaşık 28 kat az. İki tohumun ortalamaları birbirine çok yakın, yani beklenen başarım dağarcığa bağlı değil.

Uç değerler bu tabloyu tamamlar ve tek bir ortalamanın neden yeterli olmadığını gösterir. En az 19 düğüm, en çok 3379; aradaki fark 178 kat ve iki tohumun en çok değerleri de birbirinden uzak, 3379 ile 1237. Rastgele bir yordamın başarımı tek bir sayıyla bildirilemez; ortalama bir güvence değil, bir beklentidir. Belirlenimci sıranın 10.053 düğümü ise bir kaza değildir: sabit sıra, çözüm içermeyen aynı bölgeyi her koşumda aynı derinlikte gezer ve kötü bir sıranın bedeli hiçbir koşumda azalmaz. Rastgeleleştirmenin kazandırdığı şey, aynı kötü sırayı iki kez denememektir.

Uzun Kuyruğu Kesmek

3379 düğümlük uç değer, rastgele yordamın asıl sorunudur: koşumların çoğu kısa, birkaçı çok uzun. Bu kuyruk bir bütçeyle kesilebilir — arama belirli bir düğüm sayısını aşarsa bırakılır ve yeni bir rastgele sırayla baştan başlanır.

# Onceki bloklarin uzerine: Sayac, uretec ve vezir_ilk_cozum oradan gelir.
def butceli_arama(n, r, butce):
    """Butce asilirsa vazgecer. Vazgecmek yanlis yanit degildir - yanit yoktur."""
    s = Sayac()
    bulunan = None

    def gez(satir, yer):
        nonlocal bulunan
        s.say()
        if s.adim > butce or bulunan is not None:
            return
        if satir == n:
            bulunan = tuple(yer)
            return
        sutunlar = list(range(n))
        for j in range(n - 1, 0, -1):
            k = r(j + 1)
            sutunlar[j], sutunlar[k] = sutunlar[k], sutunlar[j]
        for sutun in sutunlar:
            if any(sutun == y or abs(sutun - y) == satir - i
                   for i, y in enumerate(yer)):
                continue
            yer.append(sutun)
            gez(satir + 1, yer)
            yer.pop()
            if bulunan is not None or s.adim > butce:
                return
    gez(0, [])
    return s.adim, bulunan


print("butce  tohum      yeniden baslatma  toplam dugum  en cok  gecerli")
for butce in (100, 400, 100000):
    for tohum in (20260218, 20260219):
        r = uretec(tohum)
        toplam, deneme, en_cok, gecerli = 0, 0, 0, 0
        for _ in range(20):
            kosum = 0
            while True:
                adim, sonuc = butceli_arama(16, r, butce)
                kosum += adim
                deneme += 1
                if sonuc is not None:
                    gecerli += 1
                    break
            toplam += kosum
            en_cok = max(en_cok, kosum)
        print(f"{butce:6d}  {tohum}  {deneme:16d} {toplam / 20:13.1f} {en_cok:7d}"
              f" {gecerli:8d} / 20")

butce  tohum      yeniden baslatma  toplam dugum  en cok  gecerli
   100  20260218                54         225.8     940       20 / 20
   100  20260219                57         240.8    1229       20 / 20
   400  20260218                27         228.8    1731       20 / 20
   400  20260219                29         276.1     835       20 / 20
100000  20260218                20         359.6    3379       20 / 20
100000  20260219                20         355.8    1237       20 / 20

Yüz düğümlük bütçeyle yirmi çözüm için 54 ve 57 deneme yapılıyor, yani çözüm başına 2,70 ile 2,85 arası baştan başlama. Buna karşılık toplam düğüm ortalaması 359,6’dan 225,8’e, en kötü koşum 3379’dan 940’a iniyor. Son satırlar bütçesiz koşumu tekrar veriyor ve farkı doğruluyor.

Yanıt yine bozulmuyor: son sütun altı satırda da 20 / 20. Vazgeçmek yanlış yanıt vermek değildir — bütçe aşıldığında yordam bir şey söylemez, ve söylemediği için kâhinden ayrılmaz. Kursun ilk dersindeki ayrım burada son biçimini alır: bilmediğini bildiren bir yordam ölçülebilir, bilmediğini uyduran bir yordam ölçülemez.

Özet

• Rastgeleleştirme iki ayrı güvenceyi gevşetebilir: yanıt kesin kalıp adım rastgeleleşebilir, ya da adım sınırlı kalıp yanıt olasılıklı olabilir. İkisi ayrı ölçülür.
• Çoğunluk elemanında kâhin 780 adım harcıyor; doğrulamalı örnekleme beş denemede 944 ile 1056 adım ve 0 ayrılan girdi, doğrulamasız örnekleme 200 adım ve 6 ile 7 ayrılan girdi veriyor.
• Doğrulama adımı hatayı tek yönlü yapar: doğrulamalı sürüm yanlış değer döndüremez, yalnız “yok” diyebilir; doğrulamasız sürüm gerçekten yanlış değer döndürür.
• Ön koşul bozulduğunda doğrulamasız örnekleme 40 girdinin 40’ında ayrılıyor, doğrulamalı örnekleme hiçbirinde; sonuç iki tohumda da aynı.
• On altı vezirlik tahtada belirlenimci sıra 10.053 düğüm, rastgele sıra ortalama 359,6 ve 355,8 düğüm geziyor ve kırk koşumun kırkı da geçerli çözüm buluyor; uç değerler 19 ile 3379 arasında, yani ortalama bir güvence değil beklentidir.
• Yüz düğümlük bütçeyle yeniden başlatma ortalamayı 225,8’e, en kötü koşumu 3379’dan 940’a indiriyor ve yanıt yine 20 / 20 geçerli kalıyor.

Sonraki Adım

Bu konu altı tasarım yaklaşımını aynı ölçüyle geçirdi ve hepsinde aynı şey çıktı: bir kalıbın değeri kazandırdığı adımda değil, ön koşulu bozulduğunda verdiği yanlış yanıtta görünüyor. Sonraki konu bu ölçüyü problem kalıplarına taşır. Orada kalıplar daha dar ve daha tanınabilirdir — sıralı dizide karşılıklı tarama, bitişik alt dizide artımlı hesap, ızgarada bağlı bileşen arama — ve her birinin ön koşulu tek bir cümleyle yazılabilir. İlk ders sıralı girdi isteyen iki işaretçi kalıbıyla açılır ve sorusu buradakiyle aynıdır: sıralama bozulduğunda kaç girdide yanlış yanıt çıkıyor.