Yaklaşım ve Sezgisel Yöntemler

Önceki ders üç yol bıraktı ve üçüncüsünü açıkta bıraktı: kesin çözümden vazgeçmek. Bu ders o yolun bedelini sayar. Yaklaşık bir çözüm kaç örnekte kesin sonucu buluyor, bulamadığında ne kadar uzağa düşüyor, ve verilen bütçe büyütüldüğünde kayıp gerçekten kapanıyor mu.

Ölçülecek problem yine alt küme toplamıdır, ama sorusu değişir. Karar biçiminde soru “hedefe tam ulaşan bir alt küme var mı” idi. En iyileme biçiminde soru şudur: hedefi geçmeyen en büyük alt küme toplamı nedir. Bu biçim yaklaşık çözüme yer açar, çünkü artık bir yanıt “yanlış” değil, eksik olabilir.

• KS48. Kâhin tam taramadır: hedefi geçmeyen en büyük toplam, bütün alt kümeler görülerek bulunur. Kâhinin doğruluğu tanım gereğidir.
• KS49. Bağıl kayıp, kâhinin bulduğu değer eksi yaklaşımın bulduğu değer, bölü kâhinin bulduğu değerdir. Ortalama değil, en kötü bağıl kayıp yazılır.
• KS50. Yaklaşım oranı, bütün girdiler için kanıtlanmış bir sınırdır. Bu derste ölçülen şey yaklaşım oranı değil, 20 örnekte gözlenen bağıl kayıptır ve ikisi aynı cümlede kullanılmaz.
• KS51. Yaklaşık yordam karma yordamdır: en büyük k eleman üzerinde tam tarama yapılır, kalanlar açgözlü doldurulur. k = 0 saf açgözlü yaklaşımdır, k = n tam taramaya dönüşür.
• KS52. Bütçe, tam taranan eleman sayısı k’dir ve süpürülür: 0, 4, 8, 12.
• KS53. Bir adım, bir eleman incelemesidir; kâhin için bir alt kümedir.
• KS54. Ayrılan örnek sayısı ile bağıl kayıp ayrı yazılır. Ayrılmak tek başına ne kadar ayrıldığını söylemez.
• KS55. Örnekler ortak tanımın üretecinden, tohum 20260218, 20 örnek, örnek başına 12 sayı. İkinci tohum yoktur.
• KS56. Bir bütçede kayıp sıfır çıkarsa, bu o bütçenin her girdide kesin sonucu bulacağı anlamına gelmez. Gözlem kanıt değildir.
• KS57. Girdi boyu süpürmesinde her satır ayrı bir dağarcıktır; satırlar birbirinin genişletilmişi değildir ve tek bir satırdan yön okunmaz.
• KS58. Kâhinin koşturulamadığı girdi büyüklüğünde kayıp ölçülmez. Ölçülmemiş bir aralık için sayı yazılmaz.

Kayıp Neye Göre Ölçülür

Yaklaşık bir çözümün kalitesi ancak bir kâhin varsa ölçülebilir. M01/K07 İleri Algoritmalar kursu bu yordamı gezgin satıcı probleminde kurmuştu: kâhin tam sayımla en iyi turu bulur, kalıp ona göre ölçülür. Yordam tekrarlanmaz, doğrudan kullanılır — ve aynı sınır burada da geçerlidir. Kâhin koşturulamayan girdide kayıp ölçülemez, yalnız küçük girdiden yapılmış bir genelleme vardır.

İkinci ayrım terimseldir ve bu kursta katıdır. Yaklaşım oranı kanıtlanmış bir sınırdır: her girdi için geçerlidir ve bir kanıttan gelir. Bağıl kayıp ölçülmüş bir değerdir: belirli örneklerde gözlenir. Yirmi örnekte en kötü bağıl kaybın 0,0676 çıkması, yaklaşım oranının 0,0676 olduğunu söylemez; yirmi birinci örneğin ne vereceği ölçülmedi.

Bütçe Süpürmesi

Aşağıdaki blok yaklaşık yordama verilen bütçeyi dört değerde süpürür ve her bütçede kâhinle karşılaştırır.

TOHUM = 20260218


def ornekler(tohum=TOHUM, n=12, sayi=20):
    d = tohum
    kume = []
    for _ in range(sayi):
        sayilar = []
        for _ in range(n):
            d = (d * 1103515245 + 12345) % 2147483648
            sayilar.append(d % 97 + 3)
        d = (d * 1103515245 + 12345) % 2147483648
        kume.append({"sayilar": sayilar, "hedef": sum(sayilar) // 3 + d % 7})
    return kume


def kahin(sayilar, hedef):
    """Hedefi gecmeyen en buyuk alt kume toplami. Tam tarama."""
    n, en, adim = len(sayilar), 0, 0
    for maske in range(1 << n):
        adim += 1
        t = sum(sayilar[i] for i in range(n) if maske >> i & 1)
        if en < t <= hedef:
            en = t
    return en, adim


def karma(sayilar, hedef, k):
    """En buyuk k eleman uzerinde tam tarama , kalani acgozlu doldurur.
    k=0 saf acgozlu yaklasimdir , k=n tam taramaya donusur.
    Bir adim = bir eleman incelemesi."""
    s = sorted(sayilar, reverse=True)
    bas, kalan = s[:k], s[k:]
    en, adim = 0, 0
    for maske in range(1 << k):
        t, gecerli = 0, True
        for i in range(k):
            adim += 1
            if maske >> i & 1:
                t += bas[i]
                if t > hedef:
                    gecerli = False
                    break
        if not gecerli:
            continue
        for x in kalan:
            adim += 1
            if t + x <= hedef:
                t += x
        en = max(en, t)
    return en, adim


ORN = ornekler()
print("butce k  tam bulan  ayrilan  en kotu bagil kayip  toplam adim")
for k in (0, 4, 8, 12):
    tam = ayrilan = top = 0
    en_kotu = 0.0
    for o in ORN:
        e, _ = kahin(o["sayilar"], o["hedef"])
        y, a = karma(o["sayilar"], o["hedef"], k)
        top += a
        if y == e:
            tam += 1
        else:
            ayrilan += 1
            en_kotu = max(en_kotu, (e - y) / e)
    print(f"{k:7d}  {tam:9d}  {ayrilan:7d}  {round(en_kotu, 4):19}  {top:11d}")
print()
print("kahin (tam tarama) toplam adim:", sum(kahin(o["sayilar"], o["hedef"])[1]
                                             for o in ORN))

butce k  tam bulan  ayrilan  en kotu bagil kayip  toplam adim
      0          5       15               0.0676          240
      4         15        5               0.0125         2980
      8         20        0                  0.0        35956
     12         20        0                  0.0       553948

kahin (tam tarama) toplam adim: 81920

Kaybın Okunması

Üç sayı yan yana. Bütçe k=0: saf açgözlü yaklaşım 20 örneğin 5’inde kesin sonucu buluyor, 15’inde ayrılıyor, en kötü bağıl kayıp 0,0676, ve bunu 240 adımda yapıyor. Kâhin aynı iş için 81.920 adım harcıyor. Yani 341 kat az adımla, en kötü durumda yüzde yediden az bir kayıp.

Bütçeyi büyütmek kaybı gerçekten kapatıyor. k=4: ayrılan örnek 15’ten 5’e, en kötü kayıp 0,0676’dan 0,0125’e iniyor; bedeli 240 yerine 2980 adım. k=8: ayrılan örnek 0, kayıp 0, bedeli 35.956 adım. Bu kursta bütçe süpürmesinin “her şeyi değiştirdiği” en net örneklerden biridir.

Son satır ise bir uyarı taşır. k=12’de yordam 553.948 adım harcıyor — kâhinin 81.920 adımının neredeyse yedi katı. Bütçesi sonuna kadar büyütülmüş bir sezgisel yöntem, tam taramaya dönüşmekle kalmıyor, tam taramadan pahalı bir tam taramaya dönüşüyor; her maske için kalan elemanları yeniden dolduruyor. Yaklaşık bir yordamı kesin hale getirmek, iyi bir kesin yordam üretmez.

k=8 satırındaki sıfırlar da dikkatle okunmalıdır. Sıfır kayıp, bu 20 örnekte gözlendi. Sekiz elemanlık tam taramanın her girdide kesin sonucu bulacağı gösterilmedi; kalan dört eleman açgözlü dolduruluyor ve o dolgunun her zaman en iyiyi vereceğine dair bir gerekçe yok. Bu kursun üçüncü iddiası burada son kez geçerlidir: gözlem kanıt değildir.

Girdi Boyu Değişince

k=4 satırındaki 0,0125’lik kayıp tek bir girdi büyüklüğünde alınmış bir sayıdır. İkinci süpürme aynı bütçeyi üç ayrı girdi büyüklüğünde koşturur. Her satır kendi girdi büyüklüğüne göre üretilmiş ayrı bir dağarcıktır; on altı sayılık örnekler on iki sayılık örneklerin genişletilmişi değildir.

TOHUM = 20260218


def ornekler(tohum=TOHUM, n=12, sayi=20):
    d = tohum
    kume = []
    for _ in range(sayi):
        sayilar = []
        for _ in range(n):
            d = (d * 1103515245 + 12345) % 2147483648
            sayilar.append(d % 97 + 3)
        d = (d * 1103515245 + 12345) % 2147483648
        kume.append({"sayilar": sayilar, "hedef": sum(sayilar) // 3 + d % 7})
    return kume


def kahin(sayilar, hedef):
    n, en, adim = len(sayilar), 0, 0
    for maske in range(1 << n):
        adim += 1
        t = sum(sayilar[i] for i in range(n) if maske >> i & 1)
        if en < t <= hedef:
            en = t
    return en, adim


def karma(sayilar, hedef, k):
    """En buyuk k eleman tam taranir , kalan acgozlu doldurulur."""
    s = sorted(sayilar, reverse=True)
    bas, kalan = s[:k], s[k:]
    en, adim = 0, 0
    for maske in range(1 << k):
        t, gecerli = 0, True
        for i in range(k):
            adim += 1
            if maske >> i & 1:
                t += bas[i]
                if t > hedef:
                    gecerli = False
                    break
        if not gecerli:
            continue
        for x in kalan:
            adim += 1
            if t + x <= hedef:
                t += x
        en = max(en, t)
    return en, adim


print(" n  tam bulan  en kotu bagil kayip  yaklasim adimi  kahin adimi")
for n in (8, 12, 16):
    tam, ya, ha = 0, 0, 0
    en_kotu = 0.0
    for o in ornekler(n=n):
        e, a1 = kahin(o["sayilar"], o["hedef"])
        y, a2 = karma(o["sayilar"], o["hedef"], 4)
        ha, ya = ha + a1, ya + a2
        if y == e:
            tam += 1
        else:
            en_kotu = max(en_kotu, (e - y) / e)
    print(f"{n:2d}  {tam:9d}  {round(en_kotu, 4):19}  {ya:14d}  {ha:11d}")

 n  tam bulan  en kotu bagil kayip  yaklasim adimi  kahin adimi
 8         19               0.0109            1620         5120
12         15               0.0125            2980        81920
16         19               0.0037            4690      1310720

İki sütun iki ayrı büyüme gösteriyor. Yaklaşımın adımı 1620, 2980, 4690: girdi büyüklüğü iki katına çıkarken iki katından az artıyor. Kâhinin adımı 5120’den 1.310.720’ye çıkıyor, yani 256 katına. On altı sayıda kâhin yaklaşımın 279 katı adım harcıyor, ve bu oran her dört sayıda on altıyla çarpılarak büyüyor.

Kayıp sütunu ise düzenli değil: 0,0109, 0,0125, 0,0037. Tam bulan örnek sayısı da 19, 15, 19. Bu düzensizlik beklenir, çünkü her satır ayrı bir dağarcıktır ve tek bir satırdan yön okunamaz. Okunabilecek olan şey daha küçük ve daha kesindir: ölçülen bütün girdi büyüklüklerinde kayıp yüzde bir buçuğun altında kaldı, ve bu cümlenin geçerli olduğu aralık 8 ile 16 sayı arasıdır.

Sağdaki sütun bu aralığın neden dar olduğunu da söylüyor. Yirmi dört sayıda kâhin 16.777.216 alt küme görmek zorundadır; orada kayıp ölçülemez, çünkü karşılaştırılacak kesin sonuç bilinmez. Bir yaklaşık çözümün büyük girdideki kalitesi hakkında yazılan her cümle ya küçük girdide ölçülmüş bir kayıptan genelleme yapar ya da kanıtlanmış bir yaklaşım oranına dayanır; bu ders birincisini yaptı ve ikincisini iddia etmiyor.

Sezgisel Yöntemin Bilemediği

Ölçülen kaybın ötesinde bir sınır daha var ve sayısı yoktur. Yaklaşık yordam, bir örnekte ayrıldığını kendisi bilemez. k=0 çalıştırıldığında elde bir sayı olur; o sayının kâhinin sayısı olup olmadığı ancak kâhin koşturularak anlaşılır, ve kâhin koşturulabiliyorsa yaklaşıma gerek yoktur. Ayrılan örnek sayısının 15 olduğunu bilmek, hangi 15 örnek olduğunu bilmek demek değildir.

Bunun pratik sonucu şudur. Bir yaklaşık çözüm devreye alınırken yanına yazılması gereken şey, ortalama kayıp değil en kötü kayıptır ve o kayıp hangi girdi aralığında ölçüldüğüdür. Bir raporda “yüzde bir kayıpla çalışıyor” cümlesi, girdi büyüklüğü ve kâhinin koşturulabildiği aralık yazılmadan bir şey anlatmaz.

Özet

• En iyileme biçiminde bir yanıt yanlış değil eksik olabilir; eksiklik ancak bir kâhinle ölçülür ve kâhin koşturulamayan girdide kayıp ölçülemez.
• Saf açgözlü yaklaşım 20 örneğin 5’inde kesin sonucu buluyor, 15’inde ayrılıyor, en kötü bağıl kayıp 0,0676 ve bedeli 240 adım; kâhin 81.920 adım harcıyor.
• Bütçe k=4’te ayrılan örnek 5’e ve kayıp 0,0125’e, k=8’de 0’a iniyor; bedeli 2980 ve 35.956 adım.
• k=12’de yordam 553.948 adım harcayarak kâhinin 81.920 adımını geçiyor: bütçesi sonuna kadar büyütülmüş bir sezgisel yöntem iyi bir kesin yordam vermiyor.
• Sıfır kayıp gözlemi, o bütçenin her girdide kesin sonucu bulacağının kanıtı değildir; ölçülen bağıl kayıp ile kanıtlanmış yaklaşım oranı ayrı şeylerdir.
• Yaklaşık yordam ayrıldığını kendisi bilemez; devreye alınırken yazılması gereken şey en kötü kayıp ve ölçüldüğü girdi aralığıdır.

Kurs Kapanışı

Hesaplama Kuramı kursu on derste tek bir soruyu izledi: sonlu bir bütçe neyi yanıtlar, neyi yanıtlayamaz, ve bütçeyi büyütmek bunu değiştirir mi. Aşağıdaki tablo her dersin bütçesini ve o bütçenin iki yanını toplar. Hesaplama Modelleri konusunun dört satırı kaynak derslerinden alınmıştır; sayılar uydurulmaz.

Ders	Bütçe	Bütçenin yanıtladığı	Yanıtlayamadığı
Sonlu Otomatlar	durum 1–3, evren 31 dizi	2, 26 ve 1054 ayrı dil	2³¹ dilin yanında pay 0,0000004908; k=2 uzunluk 2’den sonra 26’da donuyor
Bağlamdan Bağımsız Diller	durum 1–5, uzunluk 2–10	öbek 4, 6, 8, 10, 12; tam sayımla uzunluk 4’te en küçük k 5	sabit bir k’nın hiçbir uzunlukta yetmediği ölçülemez; üç satırlık kural hedefin tamamını üretiyor
Turing Makinesi	adım 2–200, 20.736 makine	9784 duruyor, en uzun koşum 6 adım	bütçe 6’dan sonra sayı hiç değişmiyor; durmayan 10.952’nin 5040’ı kanıtla, 5912’si bilinmiyor
Karar Verilemezlik	adım 5–200, 1000 başlangıç	7, 155, 569, 756, 1000	5000 başlangıçta aynı bütçe 9 tanesini karara bağlayamıyor; 1000/1000 durması kanıt değildir
P Sınıfı	adım bütçesi 12–10.000	eşik 20/20 (12 adım), ikili 20/20 (66 adım)	alt küme toplamı 100 adımda 7/20; problemin P’de olup olmadığı
NP Sınıfı	adım bütçesi 13–10.000	sertifikayla 20/20, toplam 101 adım	çözerek 13 adımda 0/20; tanığın nasıl bulunacağı
NP-Tam ve NP-Zor	adım bütçesi 15–10.000	indirgeme 20/20, 300 adım, yanıt korunuyor	bölüştürmenin NP-tam olduğu; her NP probleminin indirgendiği
co-NP ve Sınıflar Arası İlişkiler	adım bütçesi 13–10.000	yapılı hayır 20/20, 260 adım	yapısız hayır 20/20 tam tarama istedi; NP ile co-NP’nin eşitliği
P–NP Sorusu	adım bütçesi 13–10.000, girdi büyüklüğü 8–24	buluşma 1357 adım, 20/20 uyuşuyor	açıklığın kapanıp kapanmadığı; sorunun yanıtı
Yaklaşım ve Sezgisel Yöntemler	k = 0, 4, 8, 12	k=0’da 5/20, k=8’de 20/20 tam	k=8’in her girdide tam bulacağı; kanıtlanmış yaklaşım oranı

Sağ sütun bu kursun asıl ürünüdür. Sol sütundaki her sayı bir koşumdan gelir; sağ sütundaki her satır, koşumun ulaşamadığı yeri adlandırır. Bu kurs, ölçümün nerede bittiğini gösteren kurstur.

M01 Bilgisayar Bilimi müfredatı sekiz kursta tek bir ekseni izledi: bitin donanımdaki temsilinden (K01) programın yazılışına (K02), verinin yerleşimine (K03), yordamın maliyetinin ölçülmesine (K04), makinenin paylaşılmasına (K05), sistemin gösterilmesine (K06), zor problemlerin kâhinle karşılaştırılmasına (K07) ve ölçümün sınırına (K08) kadar her katmanda bedel sayıldı, ve sayılmayan bedel bilinmiş sayılmadı.

M01/K07’nin iki borcu bu kursta ödendi. Birincisi, gezgin satıcı ve Hamilton yolları derslerinin ayrı birer bölümde buraya havale ettiği “bu problem neden zor” sorusuydu. Yanıt bir kanıt değil bir sınıflandırmadır: bu problemlerin “evet” yanıtı kısa bir sertifikayla ucuza doğrulanır (02), zorlukları birbirine ucuz indirgemelerle taşınır (03), ve “hayır” yanıtı aynı indirimi kabul etmez (04). Sınıfların adları NP, NP-tam ve NP-zordur.

İkincisi K07’nin Kurs Kapanışı’ndaki soruydu: kaba kuvvetten daha iyisinin bilinmemesi, bilgimiz hakkında mı yoksa problemler hakkında mı bir gerçektir. Bu sorunun bir adı vardır ve P–NP sorusudur (05). Yanıtı bilinmiyor. Borç, soruyu yanıtlayarak değil, doğru adlandırarak ve neden yanıtlanmadığını göstererek ödenir: ölçüm bir yordamın adımını sayabilir, bütün yordamlar hakkında konuşamaz.

Sonraki müfredat M03 Linux ve Sistem Yönetimi’dir ve zemini değiştirir. M01 kavramları kurdu ve modelledi; M03 aynı kavramların çalışan bir sistemdeki karşılığını ele alır: kabuk, dosya sistemi, süreçler, servisler, ağ ve çekirdek arayüzleri. M01/K05 süreci ve dosya sistemini modelleyip saymıştı; M03 aynı kavramları komut düzeyinde kullanır. İlk soru da bu geçişe uygundur: bir sistemle konuşmanın arayüzü nedir, ve o arayüzde verilen bir komut hangi katmana kadar iner.