--- title: 'Rastgeleleştirilmiş Algoritmalar' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/rastgelelestirilmis-algoritmalar' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:27+00:00' license: 'CC BY-SA 4.0' --- # Rastgeleleştirilmiş Algoritmalar Rastgeleliğin iki ayrı yerde kullanılabileceği ve ikisinin ayrı ölçüldüğü: doğrulamasız örnekleme çoğunluğu olmayan 40 dizinin 40'ında yanlış değer döndürürken doğrulamalı örnekleme aynı dizilerde hiç yanılmıyor, ve on altı vezirlik tahtada rastgele sütun sırası 10.053 düğümlük belirlenimci aramayı ortalama 360 düğüme indiriyor. 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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. ```python # 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.