Problem Okuma ve Kısıt Çözümlemesi

Ö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.

"""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.

"""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.

"""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.