--- title: 'Problem Okuma ve Kısıt Çözümlemesi' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/problem-okuma-ve-kisit-cozumlemesi' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:27+00:00' license: 'CC BY-SA 4.0' --- # Problem Okuma ve Kısıt Çözümlemesi Girdi büyüklüğünden adım bütçesi çıkarma ve bu bütçenin kalıbı tek başına seçemediğini ölçme: n=12'de sıralayan kalıp kâhinden 1,61 kat pahalı, yanlış kısıt okuması 40 girdinin 18'inde yanlış yanıt veriyor. Önceki konu, adı konmuş problemlerle çalıştı: sırt çantası, gezgin satıcı, n vezir. Bu problemlerin biçimi verilmişti; sorulan şey hangi yaklaşımın onları çözdüğüydü. Alıştırmada durum tersinedir. Elde bir metin vardır, metnin içinde birkaç sayı geçer, ve hangi kalıbın uygun olduğu söylenmez. Kalıbı seçen şey problemin adı değil, **kısıtlarıdır**. Bu ders, kısıt okumasını bir yordama çevirir ve o yordamın nerede işe yaradığını, nerede tahmine dönüştüğünü ölçer. Sonuç iki yönlüdür: girdi büyüklüğü büyük çözüm ailelerini gerçekten eler, ama geriye kalanlar arasından seçimi **yapmaz** — ve kısıt yanlış okunduğunda ortaya çıkan çözüm hepsinden ucuz olabilir, yine de yanlıştır. ## Girdi Büyüklüğünden Adım Bütçesine Kısıt okuma tek bir hesaptır: problem metnindeki en büyük girdi büyüklüğü alınır, o büyüklükte harcanabilecek adım sayısına bir üst sınır konur, ve her aday çözümün o sınıra sığıp sığmadığı hesaplanır. Sınıra **adım bütçesi** denir. Asimptotik gösterimin kendisi Algoritmalar kursunun Çözümleme konusunda kuruldu ve burada tekrarlanmıyor; burada yapılan şey gösterimi bir **karar ölçütüne** çevirmektir. - **AD1** — Adım bütçesi, bir çözümün kabul edilebilir sayılması için harcayabileceği en çok adımdır. Bu derste bütçe **10⁸ adımdır** ve bir sabit olarak alınır. - **AD2** — Bütçe **en kötü durum** üzerinden hesaplanır. Ortalama girdi bütçe hesabına girmez; hesabın amacı bir çözümü elemektir, övmek değil. - **AD3** — Karma tablosundaki bir arama bir adım, bir ekleme bir adımdır. İkisi de sabittir. - **AD4** — Sıralamanın adımı, gerçekten yapılan **kıyaslama sayısıdır** ve sayılarak ölçülür. Sıralama algoritmalarının kendisi Algoritmalar kursunda kuruldu, burada kullanılıyor. - **AD5** — En kötü girdi şöyle üretilir: bütün değerler çift, hedef tek. O zaman hiçbir ikili hedefi veremez ve her çözüm sonuna kadar çalışmak zorunda kalır. Problem şudur: bir dizide **toplamı hedefe eşit iki ayrı konum** var mı. Üç aday vardır. Kaba kuvvet bütün ikilileri dener; bu kursun kâhini odur. İkinci aday diziyi sıralar ve iki işaretçi ile tarar. Üçüncüsü tek geçişte karma tablosu tutar. ```python """Uc cozumun ayni problemdeki adimi , en kotu girdide sayiliyor.""" from functools import cmp_to_key TOHUM = 20260218 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 en_kotu_girdi(n, tohum=TOHUM): """Butun degerler cift , hedef tek: hicbir ikili hedefi vermez.""" dizi = [2 * i for i in range(n)] r = uretec(tohum) for i in range(n - 1, 0, -1): j = r(i + 1) dizi[i], dizi[j] = dizi[j], dizi[i] return dizi 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 kalip_sirala_iki(dizi, hedef, s): def kiyas(a, b): s.say() return -1 if a < b else (1 if a > b else 0) d = sorted(dizi, key=cmp_to_key(kiyas)) sol, sag = 0, len(d) - 1 while sol < sag: s.say() 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 kalip_karma(dizi, hedef, s): gorulen = set() for x in dizi: s.say() if hedef - x in gorulen: return True s.say() gorulen.add(x) return False print("n kaba kuvvet sirala+iki isaretci karma tablo") for n in (4, 8, 32, 128, 512, 2048): d = en_kotu_girdi(n) s1, s2, s3 = Sayac(), Sayac(), Sayac() kahin_ciftler(d, 7, s1) kalip_sirala_iki(d, 7, s2) kalip_karma(d, 7, s3) print(f"{n:5d} {s1.adim:11d} {s2.adim:19d} {s3.adim:11d}") print() for ad, kalip in (("sirala+iki isaretci", kalip_sirala_iki), ("karma tablo ", kalip_karma)): for n in range(2, 40): d = en_kotu_girdi(n) s1, s2 = Sayac(), Sayac() kahin_ciftler(d, 7, s1) kalip(d, 7, s2) if s2.adim < s1.adim: print(f"{ad} kaba kuvvetten ucuzlastigi ilk n: {n}" f" (kalip {s2.adim} , kahin {s1.adim})") break ``` ``` n kaba kuvvet sirala+iki isaretci karma tablo 4 6 10 8 8 28 22 16 32 496 152 64 128 8128 861 256 512 130816 4483 1024 2048 2096128 22015 4096 sirala+iki isaretci kaba kuvvetten ucuzlastigi ilk n: 8 (kalip 22 , kahin 28) karma tablo kaba kuvvetten ucuzlastigi ilk n: 6 (kalip 12 , kahin 15) ``` Tablonun ilk satırı kısıt okumasının en çok gözden kaçan sonucudur: n=4'te **kaba kuvvet üç çözümün en ucuzudur** — 6 adım, karma tablosunun 8 adımına ve sıralayan kalıbın 10 adımına karşı. Sıralayan kalıp kâhinden ancak **n=8'de**, karma tablosu **n=6'da** ucuzlar. Kaba kuvvet küçük girdide kötü bir seçenek değildir; kötü olan, hangi girdide kötüleştiğini bilmeden onu seçmektir. ## Dört Girdi Büyüklüğünde Bütçe Hesabı Ölçüm 2048'e kadar gidiyor, ama kısıt okuması 10⁸'e kadar karar vermek zorundadır ve o büyüklükte kaba kuvveti gerçekten koşturmak bir seçenek değildir. Bu yüzden bütçe hesabı **ölçülmüş sayıdan doğrulanmış bir formülle** yapılır: önce formülün küçük n'de ölçümü tutup tutmadığına bakılır, sonra formül büyük n'ye taşınır. - **AD6** — Kaba kuvvetin en kötü adımı $n(n-1)/2$, karma tablosununki $2n$, sıralayan kalıbınki $n\log_2 n + n$ olarak tahmin edilir. - **AD7** — Bir formül, ölçülen adımı **aşmadığı sürece** bütçe hesabında kullanılabilir. Az gösteren formül kabul edilmez. ```python """Olculen adim formulu tutuyor mu , ve dort buyuklukte butce hesabi.""" from math import log2 OLCUM = {8: (28, 22, 16), 32: (496, 152, 64), 128: (8128, 861, 256), 512: (130816, 4483, 1024), 2048: (2096128, 22015, 4096)} BUTCE = 10 ** 8 def tahmin(n): return (n * (n - 1) // 2, int(n * log2(n)) + n, 2 * n) print("n kaba kuvvet sirala+iki isaretci karma tablo") print(" olculen tahmin o/t olculen tahmin o/t olculen tahmin") for n, (a, b, c) in OLCUM.items(): ta, tb, tc = tahmin(n) print(f"{n:5d} {a:7d} {ta:6d} {a / ta:.2f} {b:8d} {tb:6d} {b / tb:.2f}" f" {c:8d} {tc:6d}") print() print(f"adim butcesi: {BUTCE}") print("n kaba kuvvet sirala+iki karma tablo") for n in (10 ** 3, 10 ** 5, 10 ** 6, 10 ** 8): ta, tb, tc = tahmin(n) d = [("sigar" if t <= BUTCE else "sigmaz") for t in (ta, tb, tc)] print(f"{n:<11d} {ta:.2e} {d[0]:6s} {tb:.2e} {d[1]:6s} {tc:.2e} {d[2]:6s}") ``` ``` n kaba kuvvet sirala+iki isaretci karma tablo olculen tahmin o/t olculen tahmin o/t olculen tahmin 8 28 28 1.00 22 32 0.69 16 16 32 496 496 1.00 152 192 0.79 64 64 128 8128 8128 1.00 861 1024 0.84 256 256 512 130816 130816 1.00 4483 5120 0.88 1024 1024 2048 2096128 2096128 1.00 22015 24576 0.90 4096 4096 adim butcesi: 100000000 n kaba kuvvet sirala+iki karma tablo 1000 5.00e+05 sigar 1.10e+04 sigar 2.00e+03 sigar 100000 5.00e+09 sigmaz 1.76e+06 sigar 2.00e+05 sigar 1000000 5.00e+11 sigmaz 2.09e+07 sigar 2.00e+06 sigar 100000000 5.00e+15 sigmaz 2.76e+09 sigmaz 2.00e+08 sigmaz ``` Üst tablo formülü doğruluyor. Kaba kuvvette ölçülen ile tahmin **birebir aynı** (oran 1,00); karma tablosunda da aynı. Sıralayan kalıpta oran 0,69'dan 0,90'a **yükseliyor**: formül gerçek kıyaslama sayısını her n'de fazla gösteriyor, yani güvenli yönde yanılıyor ve AD7'yi karşılıyor. Fazla göstermenin miktarı sabit değil — küçük n'de tahmin ölçümün 1,45 katı, n=2048'de 1,12 katı. **Kısıt okumasının tahmine dönüştüğü nokta burasıdır:** kullanılan formül bir katsayı içerir ve o katsayı ölçülmeden bütçe hesabı bir tahmindir. Alt tablo dersin istediği dört büyüklüktür. n=1.000'de **üç çözüm de** bütçeye sığıyor; kısıt okuma burada hiçbir şey elemiyor ve seçim başka bir ölçüte kalıyor. n=100.000'de kaba kuvvet 5,00·10⁹ adımla eleniyor, geriye iki aday kalıyor. n=1.000.000'da tablo aynı kalıyor. n=10⁸'de **üçü de sığmıyor** — en ucuzu olan karma tablosu bile 2,00·10⁸ adımla bütçenin iki katını istiyor. Bu son satır kısıt okumasının en yararlı çıktısıdır: o büyüklükte tek geçişli bir çözüm bile yetmiyorsa, problem metni **başka bir kısıt** veriyor olmalıdır ve okunmamıştır. ## Kısıt Yanlış Okunduğunda Yukarıdaki hesabın tamamı bir şeyi varsaydı: adayların üçü de doğru yanıt veriyor. Bu varsayım sınanmadan bütçe hesabı bir çözüm seçemez. Kursun kuralı burada da geçerlidir — **ön koşulu kâhinle sınanmayan kalıp ölçülmemiş sayılır.** Dördüncü bir aday eklenir. Problem metninde "değerler 20'yi aşmaz" yazdığını düşünen biri, 0..20 arasını işaretleyen bir dizi tutup tek geçişte yanıt verebilir. Metinde alt sınırın yazmadığı ve değerlerin negatif olabildiği gözden kaçmıştır. - **AD8** — Dağarcık ortak tanımın dağarcığıdır: 40 girdi, her biri 12 değer, değerler −9 ile 20 arasında. Hedef 11. - **AD9** — Yanlış kısıt okuması, aralık dışındaki değeri **sessizce atlar**; çökmez, bir yanıt döndürür. - **AD10** — İkinci dağarcık `20260219` tohumuyla üretilir ve ayrılan girdi oranının aynı büyüklük düzeninde kalıp kalmadığı yazılır. ```python """Butce hesabi kalibi secmez , kahin secer. Iki dagarcik.""" from functools import cmp_to_key TOHUM, IKINCI, UZUNLUK, DAGARCIK = 20260218, 20260219, 12, 40 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 dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK): r = uretec(tohum) return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]} for i in range(n)] 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 kalip_sirala_iki(dizi, hedef, s): def kiyas(a, b): s.say() return -1 if a < b else (1 if a > b else 0) d = sorted(dizi, key=cmp_to_key(kiyas)) sol, sag = 0, len(d) - 1 while sol < sag: s.say() 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 kalip_karma(dizi, hedef, s): gorulen = set() for x in dizi: s.say() if hedef - x in gorulen: return True s.say() gorulen.add(x) return False def kalip_sayma(dizi, hedef, s, ust=20): """YANLIS KISIT OKUMASI: degerler 0..ust araliginda saniliyor.""" var = [False] * (ust + 1) for x in dizi: s.say() if 0 <= x <= ust: e = hedef - x if 0 <= e <= ust and var[e]: return True var[x] = True return False def olc(kalip, kume, hedef): ayrilan, ak, ah = [], 0, 0 for k in kume: s1, s2 = Sayac(), Sayac() a = kalip(k["dizi"], hedef, s1) b = kahin_ciftler(k["dizi"], hedef, s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan.append(k["no"]) return {"ayrilan": len(ayrilan), "no": ayrilan[:5], "kalip_adim": ak, "kahin_adim": ah} for tohum in (TOHUM, IKINCI): print(f"dagarcik tohum {tohum} , 40 girdi x 12 deger , hedef 11") K = dagarcik(tohum) for ad, kalip in (("sirala+iki isaretci", kalip_sirala_iki), ("karma tablo ", kalip_karma), ("sayma (kisit yanlis)", kalip_sayma)): print(f" {ad}", olc(kalip, K, 11)) print() ``` ``` dagarcik tohum 20260218 , 40 girdi x 12 deger , hedef 11 sirala+iki isaretci {'ayrilan': 0, 'no': [], 'kalip_adim': 1398, 'kahin_adim': 866} karma tablo {'ayrilan': 0, 'no': [], 'kalip_adim': 486, 'kahin_adim': 866} sayma (kisit yanlis) {'ayrilan': 18, 'no': [4, 10, 13, 14, 15], 'kalip_adim': 396, 'kahin_adim': 866} dagarcik tohum 20260219 , 40 girdi x 12 deger , hedef 11 sirala+iki isaretci {'ayrilan': 0, 'no': [], 'kalip_adim': 1441, 'kahin_adim': 970} karma tablo {'ayrilan': 0, 'no': [], 'kalip_adim': 566, 'kahin_adim': 970} sayma (kisit yanlis) {'ayrilan': 17, 'no': [3, 4, 6, 7, 8], 'kalip_adim': 391, 'kahin_adim': 970} ``` Üç sayı yan yana. **Kâhin:** 866 adım, 40 girdinin 40'ında doğru. **Kalıp:** karma tablosu 486 adım, sıralayan kalıp 1398 adım, yanlış kısıt okuması 396 adım. **Ayrılan girdi:** ilk ikisinde **0**, yanlış okumada **18** — yani 40 girdinin 18'inde kâhinden farklı yanıt, oran **0,4500**. Sonuç iki şey söylüyor. Birincisi, **adım sayısı sıralaması doğruluk sıralaması değildir**: en az adımı harcayan aday (396) tam da yanlış yanıt veren adaydır. İkincisi, n=12'de sıralayan kalıp kâhinden **1,61 kat pahalıdır** (1398'e karşı 866). Bütçe hesabı bu kalıbı büyük n için seçmişti; gerçek girdi büyüklüğü 12 olduğunda aynı seçim kâhinden kötüdür. Bütçe hesabı bir **eleme** aracıdır, bir seçme aracı değil. İkinci dağarcık sonucu doğruluyor: ayrılan girdi 18'den 17'ye (oran 0,4250) iniyor, aynı büyüklük düzeninde kalıyor; doğru iki kalıp orada da 0 ayrılan girdi veriyor. Ortak tanımın birinci okuması, sırasız girdide iki işaretçinin 40 girdinin 25'inde yanıldığını zaten göstermişti; buradaki 18, aynı kuralın **kısıt okuma** tarafındaki karşılığıdır — kalıp doğru, okuma yanlış. ## Özet - Kısıt okuma, girdi büyüklüğünden bir **adım bütçesi** çıkarıp adayları eleme işlemidir; bu derste bütçe 10⁸ adım ve hesap her zaman en kötü durum üzerinden yapılır. - Ölçüm küçük girdide kaba kuvveti haklı çıkarıyor: n=4'te üç çözümün en ucuzu 6 adımla kaba kuvvet; karma tablosu ancak n=6'da, sıralayan kalıp n=8'de ondan ucuzluyor. - Bütçe dört büyüklükte farklı sayıda aday bırakıyor: n=1.000'de üçü de sığıyor, n=100.000 ve n=1.000.000'da kaba kuvvet eleniyor, n=10⁸'de **hiçbiri** sığmıyor — karma tablosu bile 2,00·10⁸ adım istiyor. - Formül ölçümle doğrulanmadan bütçe hesabı bir tahmindir: sıralayan kalıpta tahmin ölçümün n=8'de 1,45, n=2048'de 1,12 katı; kaba kuvvet ve karma tablosunda oran tam olarak 1,00. - Kâhin karşılaştırması bütçe hesabının söyleyemediğini söylüyor: en az adımı harcayan aday (396 adım) 40 girdinin **18'inde** yanlış yanıt veriyor, ikinci dağarcıkta 17'sinde; doğru iki kalıp ise iki dağarcıkta da 0 ayrılan girdi veriyor. - Gerçek girdi büyüklüğünde bütçe sıralaması tersine dönebilir: n=12'de sıralayan kalıp kâhinden 1,61 kat pahalı. Bütçe hesabı eler, seçmez. ## Sonraki Adım Bu derste kâhin bir kez kullanıldı ve yanlış bir kısıt okumasını 18 girdide yakaladı. Ama o 18 girdi hazır bir dağarcıktan geldi; dağarcık başka olsaydı yakalanan sayı da başka olurdu. Sonraki ders bu bağımlılığı konu edinir: bir çözümün kâhinle karşılaştırılması **hangi girdilerle** yapılmalıdır, kenar durumları rastgele üretilen bir dağarcıkta kaç kez çıkar, ve ayrılan bir girdi bulunduğunda o girdi nasıl en küçük hâline indirilir. Ölçü yine sayıdır: bilerek bozulmuş sürümlerin kaçı hangi dağarcıkla yakalanıyor.