---
title: 'Çözüm Doğrulama'
source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/cozum-dogrulama'
course: 'İleri Algoritmalar ve Problem Çözme'
language: tr
updated: '2026-08-17T18:07:28+00:00'
license: 'CC BY-SA 4.0'
---
# Çözüm Doğrulama
Bir çözümün kâhinle karşılaştırılmasının yordama çevrilmesi: 40 rastgele girdi beş kusurun dördünü yakalıyor, 12 kenar durumu beşini de yakalıyor, ve ayrılan bir girdi 12 değerden 1 değere 23 denemede iniyor.
Önceki ders bir çözümün adım bütçesine sığmasının onu doğru yapmadığını gösterdi: en az adımı
harcayan aday, 40 girdinin 18'inde kâhinden ayrılıyordu. O 18 sayısı hazır bir dağarcıktan
geldi ve sorgulanmadı. Bu ders o sorgulamayı yapar — **hangi girdilerle karşılaştırıldığı,
karşılaştırmanın kendisi kadar belirleyicidir.**
Test yazma disiplini, kenar durumu düşünme ve gözden geçirme alışkanlıkları başka kurslarda
kuruldu ve burada tekrarlanmıyor. Bu dersin eklediği tek şey **kâhindir**: doğruluğun bir
görüşe değil, ikinci bir çözümün yanıtına karşı sayılmasıdır.
## Doğrulama Yordamı
Yordam üç adımdır ve sırası değişmez. Birincisi, girdi kümesi üretilir. İkincisi, hem sınanan
çözüm hem kâhin aynı girdilerde koşturulur. Üçüncüsü, iki yanıtın farklı çıktığı girdiler
**sayılır**. Çıktı bir sayıdır: **ayrılan girdi**. Sıfırsa o kümede kanıt bulunamamıştır;
sıfırdan büyükse çözüm yanlıştır ve elde somut bir örnek vardır.
- **AD11** — Sınanan çözüm sıralı dizide iki işaretçidir. Ön koşul her girdide sağlanır; bu
ders ön koşulu değil **gerçeklemeyi** sınar.
- **AD12** — Beş kusurlu sürüm elle üretilir ve her kusur **tek satırlık** bir değişikliktir:
bitiş koşulu, başlangıç konumu, bitiş konumu, ilerleme yönü, boş girdi.
- **AD13** — Bir sürüm çöktüğünde bu da ayrılma sayılır; çökme sessiz yanlıştan daha az
tehlikelidir ama yine bir ayrılmadır.
- **AD14** — Rastgele dağarcık 40 girdidir, her biri **tam 12 değer** taşır; hedef de aynı
üreteçten gelir ve $-18$ ile $22$ arasındadır.
- **AD15** — Kenar durumu kümesi 12 girdidir ve elle kurulur: boş dizi, tek eleman, iki eleman,
yalnız tekrar eden değerler, uçlardaki değerler, ulaşılamayan hedef.
```python
"""Bes kusurlu surum , iki ayri girdi kumesi , kahin karsisinda."""
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 rastgele_kume(tohum=TOHUM, n=40, uzunluk=12):
r = uretec(tohum)
return [(sorted(r(30) - 9 for _ in range(uzunluk)), r(41) - 18)
for _ in range(n)]
KENAR = [([], 11), ([5], 10), ([5], 5), ([5, 6], 11), ([5, 6], 10),
([7, 7], 14), ([-9, -9], -18), ([0, 0, 0], 0), ([-9, 20], 11),
([1, 2, 3, 4], 3), ([1, 2, 3, 4], 7), ([2, 2, 2, 2], 4)]
def kahin(d, hedef, s):
for i in range(len(d)):
for j in range(i + 1, len(d)):
s.say()
if d[i] + d[j] == hedef:
return True
return False
def iki_isaretci(d, hedef, s, kusur=None):
"""kusur=None dogru surum. Her kusur tek satirdir."""
sol = 1 if kusur == "K2" else 0
sag = (len(d) - 2) if kusur == "K3" else (len(d) - 1)
if kusur == "K5":
d[0] # bos diziyi hesaba katmiyor
while (sol <= sag) if kusur == "K1" else (sol < sag):
s.say()
t = d[sol] + d[sag]
if t == hedef:
return True
ileri = (t > hedef) if kusur == "K4" else (t < hedef)
sol, sag = (sol + 1, sag) if ileri else (sol, sag - 1)
return False
KUSUR = [(None, "dogru surum"), ("K1", "sol <= sag"), ("K2", "ilk eleman atlaniyor"),
("K3", "son eleman atlaniyor"), ("K4", "yonler ters"),
("K5", "bos dizi hesapta yok")]
def olc(kusur, kume):
ayrilan, ak, ah = 0, 0, 0
for d, hedef in kume:
s1, s2 = Sayac(), Sayac()
try:
a = iki_isaretci(list(d), hedef, s1, kusur)
except IndexError:
a = "coktu"
b = kahin(list(d), hedef, s2)
ak, ah = ak + s1.adim, ah + s2.adim
if a != b:
ayrilan += 1
return ayrilan, ak, ah
R = rastgele_kume()
print(f"rastgele dagarcik {len(R)} girdi x 12 deger | "
f"kenar durumu kumesi {len(KENAR)} girdi")
print("kusur rastgele kenar kalip adim kahin adim")
for k, ad in KUSUR:
ar, akr, ahr = olc(k, R)
ak, akk, ahk = olc(k, KENAR)
print(f"{ad:22s} {ar:8d} {ak:5d} {akr + akk:10d} {ahr + ahk:10d}")
print()
Y = rastgele_kume(IKINCI)
print("ikinci dagarcik 20260219 , rastgele kume:",
{ad: olc(k, Y)[0] for k, ad in KUSUR})
```
```
rastgele dagarcik 40 girdi x 12 deger | kenar durumu kumesi 12 girdi
kusur rastgele kenar kalip adim kahin adim
dogru surum 0 0 329 1596
sol <= sag 3 2 344 1596
ilk eleman atlaniyor 4 5 297 1596
son eleman atlaniyor 3 5 317 1596
yonler ters 25 2 423 1596
bos dizi hesapta yok 0 1 329 1596
ikinci dagarcik 20260219 , rastgele kume: {'dogru surum': 0, 'sol <= sag': 2, 'ilk eleman atlaniyor': 2, 'son eleman atlaniyor': 2, 'yonler ters': 27, 'bos dizi hesapta yok': 0}
```
Üç sayı yan yana. **Kâhin:** 52 girdinin tamamında **1596 adım** ve her girdide doğru yanıt.
**Kalıp:** doğru sürüm **329 adım**, yani kâhinin **4,85 katı azı**. **Ayrılan girdi:** doğru
sürümde iki kümede de **0**; beş kusurlu sürümde 0 ile 25 arasında.
Tablonun asıl bulgusu son satırdadır. Rastgele dağarcık **40 girdiyle beş kusurun dördünü**
yakalıyor ve beşincisini — boş girdiyi hesaba katmayan sürümü — **hiç yakalamıyor**. Sebep
yordamsaldır, şanssızlık değil: dağarcığın her girdisi tam 12 değer taşır, yani boş ve tek
elemanlı girdi o kümede **hiç yoktur**. Bir kusur sınıfı, girdi üretecinin biçimi yüzünden
yapısal olarak erişilemez durumdadır ve dağarcığı 40'tan 400'e çıkarmak bunu değiştirmez.
Kenar durumu kümesi bunun tersini yapıyor: **12 girdiyle beş kusurun beşini** de yakalıyor.
Girdi başına verim 40'ta 4'e karşı 12'de 5'tir — **0,1000'e karşı 0,4167**. Buna karşılık
kenar kümesi tek başına da yetmiyor: yönleri ters çevrilmiş sürümü yalnız 2 girdide
yakalarken rastgele dağarcık onu 25 girdide yakalıyor. İki küme farklı kusur sınıfları
görüyor ve biri diğerinin yerini almıyor.
İkinci dağarcık sonucu doğruluyor: `20260219` tohumuyla sayılar 2, 2, 2, 27, 0 çıkıyor — dört
kusur yine yakalanıyor, boş girdi kusuru yine kaçıyor, ve yönleri ters sürümün baskınlığı
sürüyor. Ayrılan girdi oranı aynı büyüklük düzeninde; sonuç dağarcığa bağlı değildir.
## Ayrılan Girdiyi Küçültmek
Bir ayrılma bulunduğunda elde 12 değerlik bir dizi vardır ve o dizinin hangi özelliği kusuru
tetikliyor belli değildir. Küçültme bunu çözer: girdiden bir değer çıkarılır, ayrılma sürüyorsa
küçük hâli tutulur, sürmüyorsa değer geri konur. İşlem hiçbir çıkarma ayrılmayı korumayana
kadar tekrarlanır.
- **AD16** — Küçültme yalnız **değer çıkarır**; değer eklemez ve değiştirmez. Sonuç, başlangıç
girdisinin bir alt dizisidir.
- **AD17** — Bir deneme, aday girdide hem kusurlu sürümü hem kâhini bir kez koşturmaktır.
- **AD18** — Küçültmenin sonucu **yerel olarak en küçüktür**: tek değer çıkarmayla daha da
küçültülemez. Bütün alt diziler arasında en küçük olduğu iddia edilmez.
```python
"""Ayrilan girdiyi en kucuk haline indirme."""
from math import comb
TOHUM = 20260218
def uretec(tohum):
d = tohum
def sonraki(n):
nonlocal d
d = (d * 1103515245 + 12345) % 2147483648
return d % n
return sonraki
def rastgele_kume(tohum=TOHUM, n=40, uzunluk=12):
r = uretec(tohum)
return [(sorted(r(30) - 9 for _ in range(uzunluk)), r(41) - 18)
for _ in range(n)]
def kahin(d, hedef):
return any(d[i] + d[j] == hedef
for i in range(len(d)) for j in range(i + 1, len(d)))
def iki_isaretci(d, hedef, kusur=None):
sol = 1 if kusur == "K2" else 0
sag = (len(d) - 2) if kusur == "K3" else (len(d) - 1)
if kusur == "K5":
d[0]
while (sol <= sag) if kusur == "K1" else (sol < sag):
t = d[sol] + d[sag]
if t == hedef:
return True
ileri = (t > hedef) if kusur == "K4" else (t < hedef)
sol, sag = (sol + 1, sag) if ileri else (sol, sag - 1)
return False
def ayriliyor(d, hedef, kusur):
try:
return iki_isaretci(list(d), hedef, kusur) != kahin(d, hedef)
except IndexError:
return True
def kucult(d, hedef, kusur):
"""Bir deger cikarilir; ayrilma suruyorsa cikarilmis hali tutulur."""
deneme = 0
ilerledi = True
while ilerledi:
ilerledi = False
for i in range(len(d)):
aday = d[:i] + d[i + 1:]
deneme += 1
if ayriliyor(aday, hedef, kusur):
d, ilerledi = aday, True
break
return d, deneme
R = rastgele_kume()
print("kusur ilk ayrilan girdi no uzunluk kuculmus deneme en kucuk girdi")
for kusur in ("K1", "K2", "K3", "K4"):
for no, (d, hedef) in enumerate(R, 1):
if ayriliyor(d, hedef, kusur):
kd, deneme = kucult(d, hedef, kusur)
print(f"{kusur:5s} {no:20d} {len(d):7d} {len(kd):8d}"
f" {deneme:6d} {kd} hedef {hedef}")
break
print()
print("12 uzunlukta sirali girdi sayisi (degerler -9..20):", comb(41, 12))
print("52 girdilik kume bu uzayin", f"{52 / comb(41, 12):.1e}", "kadarini gorur")
```
```
kusur ilk ayrilan girdi no uzunluk kuculmus deneme en kucuk girdi
K1 1 12 1 23 [-8] hedef -16
K2 17 12 2 31 [-8, -5] hedef -13
K3 7 12 2 21 [-5, 16] hedef 11
K4 4 12 3 20 [-3, 18, 20] hedef 15
12 uzunlukta sirali girdi sayisi (degerler -9..20): 7898654920
52 girdilik kume bu uzayin 6.6e-09 kadarini gorur
```
Dört ayrılan girdinin dördü de **12 değerden 1, 2 ve 3 değere** iniyor ve bu 20 ile 31 arası
denemeyle oluyor. Küçültmenin kazandırdığı şey adım değil, **okunabilirliktir**: `[-3, 18, 20]`
ve hedef 15 girdisine bakan biri, yönleri ters çevrilmiş sürümün neden yanıldığını doğrudan
görebilir; aynı bilgi 12 değerlik bir dizide gizlidir.
Birinci satır iki bölümü birbirine bağlıyor. Bitiş koşulu bozuk sürümün en küçük ayrılan
girdisi **tek elemanlı** bir dizidir: `[-8]`, hedef $-16$. O tek elemanlı girdi, önceki
bölümdeki kenar durumu kümesinde **elle** yazılmıştı. Yani küçültme, elle kurulan kenar
durumlarının bir kısmını **kendiliğinden üretiyor** — rastgele bir 12 değerlik girdiden yola
çıkıp aynı yere varıyor. Kenar durumu listesi bir sezgi ürünü olmak zorunda değildir; ayrılan
bir girdiden türetilebilir.
## Kâhinin Bağımsız Olması
Yordamın tamamı kâhinin doğruluğuna dayanıyor. Kâhin yanlışsa ayrılan girdi sayısı yanlış
çıkar, ve bu yanlışlık en tehlikeli yönde çıkar: **sıfır.** Kâhin, sınanan çözümle aynı gözden
kaçırmayı paylaşıyorsa ikisi de aynı yanlış yanıtı verir ve karşılaştırma hiçbir şey bulmaz.
- **AD19** — Kâhin, sınanan çözümle **aynı düşünceden türetilmemiş** olmalıdır. Kaba kuvvet bu
şartı taşır, çünkü hiçbir kalıp varsayımı kullanmaz.
- **AD20** — Aynı gözden kaçırmayı paylaşan bir kâhin, sınanan çözümle **0 ayrılan girdi**
üretir; bu sıfır bir doğruluk kanıtı değil, bir bağımlılık belirtisidir.
```python
"""Kahinin bagimsizligi: ayni yanlisi paylasan iki cozum 0 ayrilan girdi verir."""
TOHUM = 20260218
def uretec(tohum):
d = tohum
def sonraki(n):
nonlocal d
d = (d * 1103515245 + 12345) % 2147483648
return d % n
return sonraki
def rastgele_kume(tohum=TOHUM, n=40, uzunluk=12):
r = uretec(tohum)
return [(sorted(r(30) - 9 for _ in range(uzunluk)), r(41) - 18)
for _ in range(n)]
def tara(d, hedef):
return any(d[i] + d[j] == hedef
for i in range(len(d)) for j in range(i + 1, len(d)))
def kahin_dogru(d, hedef):
return tara(d, hedef)
def kahin_kusurlu(d, hedef):
"""Ayni gozden kacirma: son eleman hic bakilmiyor."""
return tara(d[:-1], hedef)
def kalip_kusurlu(d, hedef):
"""Iki isaretci son elemani hic gormuyor."""
sol, sag = 0, len(d) - 2
while sol < sag:
t = d[sol] + d[sag]
if t == hedef:
return True
sol, sag = (sol + 1, sag) if t < hedef else (sol, sag - 1)
return False
def ayrilan(a, b, kume):
return sum(1 for d, hedef in kume if a(d, hedef) != b(d, hedef))
R = rastgele_kume()
print("karsilastirilan iki cozum ayrilan girdi / 40")
print("kusurlu kalip - dogru kahin ", ayrilan(kalip_kusurlu, kahin_dogru, R))
print("kusurlu kalip - kusurlu kahin ", ayrilan(kalip_kusurlu, kahin_kusurlu, R))
print("kusurlu kahin - dogru kahin ", ayrilan(kahin_kusurlu, kahin_dogru, R))
```
```
karsilastirilan iki cozum ayrilan girdi / 40
kusurlu kalip - dogru kahin 3
kusurlu kalip - kusurlu kahin 0
kusurlu kahin - dogru kahin 3
```
Aynı kusurlu kalıp, aynı 40 girdide, iki farklı kâhine karşı **3** ve **0** veriyor. Ortadaki
satırın sıfırı bir doğruluk haberi gibi okunur ve değildir: kalıp da kâhin de son elemanı
görmüyor, ikisi de aynı girdilerde aynı yanlış yanıtı veriyor, ve fark ölçen bir yordam farkı
olmayan yerde kör kalıyor. Üçüncü satır kusurlu kâhinin kendisinin **3 girdide** yanlış
olduğunu gösteriyor — yani hata oradaydı, ölçüm onu göremedi.
Bu, kaba kuvvetin neden bu kursta kâhin olarak kaldığının ölçülmüş gerekçesidir. Kaba kuvvet
hiçbir kalıp varsayımı taşımaz: sıralılık, işaret, aralık, tekillik varsaymaz. Bir kalıbın
hızlandırılmış bir sürümünü kâhin yapmak, hızlandırmanın dayandığı varsayımı ölçümün içine
taşımak demektir.
## Sıfır Ayrılan Girdi Ne Kanıtlar
Doğru sürüm iki kümede de 0 ayrılan girdi verdi. Bu, sürümün doğru olduğunu **kanıtlamaz** ve
öyle yazılamaz. Son iki satır neden olmadığını söylüyor: değerleri $-9$ ile $20$ arasında
olan 12 uzunluklu sıralı girdilerin sayısı **7.898.654.920**, ve 52 girdilik küme bu uzayın
**6,6·10-9** kadarını görüyor. Hedefin de 41 ayrı değer aldığı düşünülürse oran
daha da küçülür.
Bu yüzden doğrulamanın çıktısı iki farklı cümledir ve karıştırılmamalıdır. **Ayrılan girdi
sıfırdan büyükse:** çözüm yanlıştır, elde kanıt vardır, ve kanıt küçültülerek okunabilir hâle
getirilebilir. **Ayrılan girdi sıfırsa:** bu kümede kusur bulunamamıştır — kusur yok değildir,
bulunamamıştır. İkinci cümlenin gücü kümenin genişliğiyle değil, **kapsadığı kusur
sınıflarıyla** artar; 40 rastgele girdi boş girdi kusurunu 400'e çıkarılsa da yakalayamazdı,
12 elle kurulmuş girdi ise tek satırda yakaladı.
## Özet
- Doğrulama yordamı üç adımdır: dağarcık üret, kâhini aynı girdilerde koştur, iki yanıtın
ayrıldığı girdiyi say. Çıktı bir görüş değil, bir sayıdır.
- 40 girdilik rastgele dağarcık beş kusurun **dördünü** yakalıyor; boş girdiyi hesaba katmayan
kusuru yakalayamıyor, çünkü dağarcığın her girdisi tam 12 değer taşıyor ve o kusur sınıfı
yapısal olarak erişilemez.
- 12 girdilik kenar durumu kümesi beş kusurun **beşini** de yakalıyor; girdi başına verim
0,1000'e karşı 0,4167. Ama yönleri ters sürümü yalnız 2 girdide yakalıyor, rastgele dağarcık
onu 25 girdide yakalıyor — iki küme birbirinin yerine geçmiyor.
- İkinci dağarcık aynı sonucu veriyor (2, 2, 2, 27, 0). Ayrılan bir girdi, tek değer çıkarma
denemeleriyle 12 değerden 1–3 değere iniyor ve bu 20–31 deneme tutuyor; bitiş koşulu bozuk
sürümün en küçük ayrılan girdisi `[-8]`, yani elle yazılmış kenar durumlarından biri.
- Kâhin sınanan çözümle aynı gözden kaçırmayı paylaşırsa ayrılan girdi 3'ten **0'a** düşüyor;
o sıfır doğruluk değil, bağımlılık belirtisidir. Kaba kuvvet kâhin olarak kalır çünkü hiçbir
kalıp varsayımı taşımaz.
- Sıfır ayrılan girdi doğruluk kanıtı değildir: 52 girdilik küme, 7.898.654.920 girdilik
uzayın 6,6·10-9 kadarını görüyor.
## Sonraki Adım
İki ders bir çözümün nasıl seçileceğini ve nasıl sınanacağını sayıya bağladı. Geriye tek bir
soru kalıyor ve o soru tek bir çözümle ilgili değil: bu işi tekrar tekrar yapan biri
ilerlediğini nereden bilecek. Sonraki ders alıştırma ortamlarının türlerini ayırır ve tekrarlı
çalışmanın ilerleme ölçütünü ortak tanımın kalıp kümesi üzerinde sayar. Ölçülecek şey
şaşırtıcıdır: çözülen problem sayısı bir ilerleme ölçütü değildir, ve bunun neden olmadığı
üç ortam türünde ayrı ayrı sayılacaktır.