--- title: 'Hesaplama Kuramı' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami' language: tr updated: '2026-08-17T04:39:45+00:00' license: 'CC BY-SA 4.0' lessons: 10 outcomes: - 'Sonlu otomat, üretim kuralı ve evrensel model arasındaki sınırı ölçülmüş örneklerle ayırır' - 'P, NP, NP-tam, NP-zor ve co-NP sınıflarını indirgeme ve sertifika kavramıyla tanımlar' - 'Bir sonucu bütçesiyle birlikte yazar ve gözlemi kanıt yerine koymaz' --- # Hesaplama Kuramı Hesaplama modellerinin ve karmaşıklık sınıflarının, sonlu bir bütçenin neyi yanıtlayıp neyi yanıtlayamadığı üzerinden ölçülmesi. ## Hesaplama Modelleri Sonlu otomatların tanıyabildiği diller, üretim kurallarının aştığı sınır, evrensel model ve adım bütçesinin karar verilemezlik karşısındaki yetersizliği. ### Sonlu Otomatlar Source: https://academia.sh/tr/kurslar/hesaplama-kurami/sonlu-otomatlar Durum bütçesinin tam sayımla ölçülmesi: 31 dizilik evrende 1 durumlu otomatlar 2, 2 durumlu 26, 3 durumlu 1054 ayrı dil tanıyor; evrende yazılabilecek 2 üzeri 31 dilin yanında bu, 0,0000004908'lik bir paydır. İleri Algoritmalar kursu iki soruyu bilerek açıkta bıraktı. Gezgin satıcı ve Hamilton yolları derslerinde "bu problem neden zor" sorusu ayrı birer bölümde bu kursa havale edildi; kursun kapanışı ise şunu sordu: bazı problemler için kaba kuvvetten daha iyisinin bilinmemesi, **bilgimiz hakkında mı yoksa problemler hakkında mı** bir gerçektir. İki borç da aynı yere bakar. Birincisi tek bir problemin zorluğunu sorar, ikincisi zorluğun nerede durduğunu. O kursun son ölçümü bir aday yolu sınamanın 11, böyle bir yolun olmadığını göstermenin ortalama 11.601 adım harcadığını gösteriyordu ve orada açıkça yazıldığı gibi bu bir **gözlemdi**, bir kanıt değil. Gözlemi adlandırmak ve nerede kanıta dönüştüğünü söylemek bu kursun işidir. Bu kurs bir hız kursu değildir. Sorduğu şey bir yordamın kaç adım harcadığı değil, bir **modelin** neyi hiç yapamadığıdır. Ama bir kuramın sonuçları koşturularak kanıtlanamaz. Bu yüzden burada ölçülen şey kuramın kendisi değil, **sonlu bir bütçenin ne söyleyip ne söyleyemediğidir.** Her derste üç sayı yan yana durur: bütçe, bütçenin yanıtladığı ve bütçenin yanıtlayamadığı. Kursun kuralı da buradan gelir: bir sonucun sayısı **bütçesiyle birlikte** yazılır ve bütçesi yazılmayan "çözülemez" iddiası ölçülmemiş sayılır. Sonlu bir koşum hiçbir yerde "bu dil tanınamaz" demez; yalnız **bu k için tanınmadı** diyebilir. #### Bütçe Olarak Durum Sayısı İlk model en az şeye sahip olandır. Bir **sonlu otomat (finite automaton)**, girdiyi soldan sağa bir kez okur, okuduğunu saklamaz ve yalnız sonlu sayıda **durum**dan birinde bulunur. Belleği yoktur; belleğin yerini durum sayısı tutar. Durum makinesinin tanımı Tasarım Kalıpları kursunun Durum dersinde ve Modelleme ve Gösterim kursunda kuruldu ve burada tekrarlanmaz; buradaki soru farklıdır: **kaç dil tanınabiliyor.** - **HM1** — Abece iki simgelidir. Evren, uzunluğu belirli bir sınırı geçmeyen bütün **dizilerin (string)** sonlu kümesidir ve boş dizi de evrendedir. Uzunluğu 4'ü geçmeyen evren 31 dizi içerir. - **HM2** — Bir **dil**, evrenin bir alt kümesidir. 31 dizilik evrende yazılabilecek dil sayısı $2^{31}$'dir. - **HM3** — Otomat **belirlenimci (deterministic)** kurulur: başlangıç durumu 0'dır, geçiş tablosu her durum ile simge ikilisine tek bir durum atar, kabul kümesi durumların bir alt kümesidir. Bir dizi, okunduktan sonra kalınan durum kabul kümesindeyse tanınır. - **HM4** — k durumlu **bütün** otomatlar sayılabilir: $k^{2k}$ geçiş tablosu ile $2^k$ kabul kümesinin bileşimi. k=1 için 2, k=2 için 64, k=3 için 5832 otomat. - **HM5** — Ölçü **tam sayımdır**: tahmin yoktur, örnekleme yoktur. Bu kursun hiçbir ölçüsünde `random` ve `time` kullanılmaz; ölçülen şey adımdır, süre değil. Somut bir örnek tanımı yerine oturtur. İki durumlu bir otomat, "şimdiye kadar okunan a sayısı çift mi" sorusunun yanıtını durumunda tutabilir: her a durumu değiştirir, her b durumu olduğu gibi bırakır, kabul kümesi de çift durumudur. Bu otomat girdiyi ne saklar ne geri okur; yine de her uzunluktaki her diziyi doğru sınıflar. Bir dili **tanımak** budur: dizinin dilde olup olmadığına, sonlu bir bellekle ve tek geçişte karar vermek. ```python """Sonlu otomat: k durumlu BUTUN otomatlar sayilir , tanidiklari dil toplanir.""" from itertools import product ALFABE = ("a", "b") def diziler(en_uzun): cikti = [""] for n in range(1, en_uzun + 1): cikti += ["".join(d) for d in product(ALFABE, repeat=n)] return cikti def otomat_kos(gecis, kabul, dizi, baslangic=0): d = baslangic for s in dizi: d = gecis[(d, s)] return d in kabul def otomatlar(k): """k durumlu butun belirlenimci otomatlar: gecis tablosu x kabul kumesi.""" hucreler = [(d, s) for d in range(k) for s in ALFABE] for hedefler in product(range(k), repeat=len(hucreler)): gecis = dict(zip(hucreler, hedefler)) for kabul_maske in range(1 << k): kabul = {i for i in range(k) if kabul_maske >> i & 1} yield gecis, kabul def taninabilen_diller(k, evren): """k durumlu otomatlarin evren uzerinde tanidigi AYRI dil sayisi.""" diller = set() for gecis, kabul in otomatlar(k): diller.add(frozenset(d for d in evren if otomat_kos(gecis, kabul, d))) return diller E = diziler(4) print("evren: uzunlugu 4'u gecmeyen dizi sayisi =", len(E)) print("durum otomat taninan ayri dil evrende yazilabilecek dilin orani") for k in (1, 2, 3): diller = taninabilen_diller(k, E) print(f" {k:3d} {sum(1 for _ in otomatlar(k)):6d} {len(diller):16d}" f" {len(diller) / 2 ** len(E):.10f}") print("evrende yazilabilecek butun dil sayisi: 2^31 =", 2 ** 31) ``` ``` evren: uzunlugu 4'u gecmeyen dizi sayisi = 31 durum otomat taninan ayri dil evrende yazilabilecek dilin orani 1 2 2 0.0000000009 2 64 26 0.0000000121 3 5832 1054 0.0000004908 evrende yazilabilecek butun dil sayisi: 2^31 = 2147483648 ``` Üç sayı yan yana duruyor. **Bütçe:** durum sayısı 1, 2, 3 — sırasıyla 2, 64 ve 5832 otomat. **Bütçenin yanıtladığı:** bu otomatlar 31 dizilik evrende **2**, **26** ve **1054** ayrı dili karara bağlıyor. **Bütçenin yanıtlayamadığı:** geriye $2^{31} - 1054$ dil kalıyor; üç durumlu bütçenin kapsadığı pay **0,0000004908**. Bütçe 5832 otomata çıkarken tanınan dil sayısı 2'den 1054'e, yani 527 katına çıkıyor. Buna karşılık kapsanan pay milyarda birden milyonda yarıma yükseliyor. Model sınıfı büyüyor ve **oran hâlâ sıfıra yakın.** Dikkat edilecek ikinci nokta 5832 otomatın yalnız 1054 ayrı dil üretmesidir: otomatların çoğu birbirinin kopyasıdır, çünkü ulaşılamayan durumlar ve eşdeğer durumlar aynı dili yeniden yazar. #### Bütçe Büyüdükçe Ne Değişiyor Yukarıdaki oran tek bir evrende ölçüldü ve tek bir evrende ölçülen oran bir sonuç değildir. Bütçe süpürmesi bu kursta zorunludur: her ölçü **en az üç bütçe değerinde** tekrarlanır ve sonucun bütçeyle değişip değişmediği yazılır. Burada süpürülen ikinci eksen evrenin uzunluk sınırıdır. - **HM6** — Bütçe süpürmesi iki eksende yapılır: **durum sayısı** ve **evrenin uzunluk sınırı**. Bir bütçenin yeterliliği ancak ikisi birlikte yazıldığında okunabilir. ```python """Butce supurmesi: evren buyudukce ayni durum butcesi ne kadarini kapsiyor.""" from itertools import product ALFABE = ("a", "b") def diziler(en_uzun): cikti = [""] for n in range(1, en_uzun + 1): cikti += ["".join(d) for d in product(ALFABE, repeat=n)] return cikti def otomat_kos(gecis, kabul, dizi): d = 0 for s in dizi: d = gecis[(d, s)] return d in kabul def otomatlar(k): hucreler = [(d, s) for d in range(k) for s in ALFABE] for hedefler in product(range(k), repeat=len(hucreler)): gecis = dict(zip(hucreler, hedefler)) for kabul_maske in range(1 << k): yield gecis, {i for i in range(k) if kabul_maske >> i & 1} def taninabilen_diller(k, evren): return {frozenset(d for d in evren if otomat_kos(gecis, kabul, d)) for gecis, kabul in otomatlar(k)} print("uzunluk dizi k=1 k=2 k=3 evrendeki dil k=3'un kapsadigi pay") for u in (1, 2, 3, 4): E = diziler(u) s = [len(taninabilen_diller(k, E)) for k in (1, 2, 3)] print(f"{u:7d} {len(E):4d} {s[0]:3d} {s[1]:3d} {s[2]:4d}" f" {2 ** len(E):13d} {s[2] / 2 ** len(E):.10f}") ``` ``` uzunluk dizi k=1 k=2 k=3 evrendeki dil k=3'un kapsadigi pay 1 3 2 8 8 8 1.0000000000 2 7 2 26 116 128 0.9062500000 3 15 2 26 690 32768 0.0210571289 4 31 2 26 1054 2147483648 0.0000004908 ``` Bu tablo tek başına bir dersin sonucudur. Uzunluk sınırı 1 olan üç dizilik evrende üç durumlu otomatlar **her dili** tanıyor: kapsanan pay **1,0000000000**. Uzunluk 2'de pay 0,9062500000, uzunluk 3'te 0,0210571289, uzunluk 4'te 0,0000004908. Aynı bütçe, aynı model, dört ölçüm — ve "yeterli" ile "hiç" arasındaki bütün yol. **Bir bütçenin yeterliliği bütçenin özelliği değil, bütçe ile evrenin ilişkisidir.** İkinci sütun daha da öğreticidir. İki durumlu otomatlar uzunluk 2'de 26 dil tanıyor ve uzunluk 3 ile 4'te **hâlâ 26**. Evren 7 diziden 31 diziye çıkarken tanınan dil sayısı hiç oynamıyor. Bu doyum bir ölçüm kusuru değil: iki durumla ayırt edilebilecek durum sayısı tükendiği için, evrene eklenen her yeni dizi zaten var olan 26 dilden birine düşüyor. Bütçeyi büyütmek bazen her şeyi değiştirir, bazen hiçbir şeyi; ve hangisi olduğu ancak ölçülerek görülür. #### Bir Dili Tanımak İçin Kaç Durum Gerekir Şimdiye kadar soru "k durum kaç dil tanır" biçimindeydi. Tersi daha kullanışlıdır: **verilen bir dil için en az kaç durum gerekir.** Bunun aracı **artık dildir (residual language)**: bir önekten sonra hangi kuyrukların diziyi dile soktuğu. İki önek aynı artık dili taşıyorsa hiçbir otomat onları ayırmak zorunda değildir; ayrı artık diller taşıyorlarsa otomat onları ayrı durumlara koymak zorundadır. Ayrı artık dillerin sayısına **ayırt edilebilirlik öbeği** denir. - **HM7** — Bir önekin artık dili, o önekten sonra eklendiğinde diziyi dile sokan evrendeki kuyrukların kümesidir. - **HM8** — İki öneği ancak **iki uzantısı da evrende kalan** bir kuyruk ayırabilir. Uzunluk sınırının dışına taşan bir kuyruk otomatı hiçbir şeye zorlamaz. - **HM9** — Tam sayım burada ucuzlatılır: kabul kümeleri ayrıca taranmaz, geçiş tablosu verildiğinde her diziye gereken kabul kararı toplanır ve çelişki çıkmazsa o tablo yeter. Sonuç, kabul kümelerini tek tek denemekle aynıdır. ```python """Artik dil , ayirt edilebilirlik obegi ve tam sayim yan yana.""" from itertools import product ALFABE = ("a", "b") def diziler(en_uzun): cikti = [""] for n in range(1, en_uzun + 1): cikti += ["".join(d) for d in product(ALFABE, repeat=n)] return cikti def artik_dil(onek, hedef, evren): """Onekten sonra hangi kuyruklar dile sokuyor.""" return frozenset(k for k in evren if onek + k in hedef) def en_az_durum(hedef, evren): """Ortak tanimin araci: ayirt edilebilirlik obeklerinin sayisi.""" onekler = {d[:i] for d in evren for i in range(len(d) + 1)} return len({artik_dil(o, hedef, evren) for o in onekler}) def ayrilan_onek(hedef, evren): """Iki onegi ancak IKI uzantisi da evrende kalan bir kuyruk ayirabilir.""" ev = set(evren) onekler = sorted({d[:i] for d in evren for i in range(len(d) + 1)}, key=lambda o: (len(o), o)) imza = {o: tuple((1 if o + k in hedef else 0) if o + k in ev else -1 for k in evren) for o in onekler} secilen = [] for o in onekler: if all(any(x >= 0 and y >= 0 and x != y for x, y in zip(imza[o], imza[p])) for p in secilen): secilen.append(o) return len(secilen) def taniyan_var_mi(k, hedef, evren): """k durumlu butun gecis tablolari taranir; kabul kumesi tutarlilikla secilir.""" hucreler = [(d, s) for d in range(k) for s in ALFABE] for hedefler in product(range(k), repeat=len(hucreler)): gecis = dict(zip(hucreler, hedefler)) gerek, tutarli = {}, True for dizi in evren: d = 0 for s in dizi: d = gecis[(d, s)] istenen = dizi in hedef if gerek.setdefault(d, istenen) != istenen: tutarli = False break if tutarli: return True return False def en_kucuk_k(hedef, evren, ust=5): for k in range(1, ust + 1): if taniyan_var_mi(k, hedef, evren): return k return None def cift_a(d): return d.count("a") % 2 == 0 def ab_ile_biten(d): return d.endswith("ab") print("dil uzunluk dizi obek ayrilan onek tam sayim") for ad, olcut in (("a sayisi cift", cift_a), ("ab ile biten ", ab_ile_biten)): for u in (2, 3, 4): E = diziler(u) h = frozenset(d for d in E if olcut(d)) print(f"{ad} {u:7d} {len(E):4d} {en_az_durum(h, E):4d}" f" {ayrilan_onek(h, E):12d} {en_kucuk_k(h, E):9d}") ``` ``` dil uzunluk dizi obek ayrilan onek tam sayim a sayisi cift 2 7 5 2 2 a sayisi cift 3 15 7 2 2 a sayisi cift 4 31 9 2 2 ab ile biten 2 7 4 3 3 ab ile biten 3 15 6 3 3 ab ile biten 4 31 9 3 3 ``` Üç sütun üç ayrı şey söylüyor ve ikisi birbirini düzeltiyor. Öbek sayısı "a sayısı çift" dili için 5, 7, 9 diye büyüyor; oysa tam sayım aynı dili **iki durumla** tanıyan bir otomatın var olduğunu gösteriyor. Fark evrenin kesiğinden gelir: uzunluk sınırına yaklaşan önekler, kuyrukları evrenin dışına taştığı için yapay olarak ayrılır. **Öbek sayısı bir üst sayımdır** ve tek başına durum sayısı diye okunamaz. Ayrılan önek sayısı bu kesiği hesaba katar ve altı ölçümün altısında tam sayımla birebir uyuşuyor — bu bir uyuşmadır, bir kanıt değil ve sınandığı bütçe uzunluk sınırı 4'e kadardır. Bu düzeltme kursun kuralının kendisine uygulanmasıdır. Öbek sayımı ucuz bir hesaptır ve tam sayım pahalıdır; ucuz hesabın pahalı olanın yerini tutup tutmadığı varsayılmaz, **sınanır**. Sonraki üç derste de aynı yol izlenir: ucuz ölçü önce yazılır, sonra bir bütçe içinde tam sayımla karşılaştırılır ve ayrıldığı yer saklanmaz. Düzenli dil kavramı burada tanımla değil ölçüyle kurulur. Bir dil, gereken durum sayısı **evren büyüdükçe büyümüyorsa** düzenlidir: "a sayısı çift" üç evrende de 2, "ab ile biten" üç evrende de 3. Bu iki dil için sabit bir bütçe seçilebilir ve seçilen bütçe her uzunlukta yeter. Sonraki ders aynı üç ölçüyü bu özelliği taşımayan bir dile uygular. #### Özet - Sonlu otomatın bütçesi durum sayısıdır; k durumlu bütün belirlenimci otomatlar sayılabilir ve k=1, 2, 3 için sırasıyla 2, 64 ve 5832 tanedir. - Uzunluğu 4'ü geçmeyen 31 dizilik evrende bu otomatlar 2, 26 ve 1054 ayrı dil tanıyor; evrende yazılabilecek dil sayısı 2 üzeri 31 ve üç durumun kapsadığı pay 0,0000004908. - Bütçe süpürmesi bir bütçenin yeterliliğinin evrene bağlı olduğunu gösteriyor: üç durum, uzunluk sınırı 1'de evrenin tamamını, uzunluk sınırı 4'te milyonda yarımını kapsıyor. - İki durumlu otomatların tanıdığı dil sayısı uzunluk 2'den sonra 26'da donuyor; evreni büyütmek bu bütçe için hiçbir şey değiştirmiyor. - Artık dil öbeklerinin sayısı bir üst sayımdır: "a sayısı çift" için 9 öbek çıkarken tam sayım iki durumun yettiğini gösteriyor; ayırt eden kuyruğun iki uzantısı da evrende kalmalıdır. - Bir dil, gereken durum sayısı evrenle birlikte büyümüyorsa düzenlidir; bu iki dil için üç evrende de sabit kalıyor. #### Sonraki Adım Sonraki ders aynı üç ölçüyü, sayma gerektiren bir dile uygular: eşit sayıda a'nın ardından eşit sayıda b gelen diziler. Sorulacak olan şudur: gereken durum sayısı evrenle birlikte büyürse, bütçeyi büyütmek bir çözüm müdür, yoksa değiştirilmesi gereken şey bütçe değil **model sınıfı** mıdır. Yanıt, üç satırlık bir üretim kuralının bütün bir otomat ailesinin yapamadığını yapmasıyla gelir. ### Bağlamdan Bağımsız Diller Source: https://academia.sh/tr/kurslar/hesaplama-kurami/baglamdan-bagimsiz-diller Durum bütçesinin yetmediği dillerin ölçülmesi: eşit sayıda a ve b dizisi için gereken durum sayısı uzunluk sınırıyla 3, 5, 7, 9, 11 diye büyürken tek satırlık bir üretim kuralı aynı dili tam olarak üretiyor ve kuralın betimi hiç büyümüyor. Önceki ders bir dili düzenli sayan ölçüyü kurdu: gereken durum sayısı evren büyüdükçe büyümüyorsa o dil için sabit bir bütçe seçilebilir. İki örnek bu ölçüyü geçti; "a sayısı çift" üç evrende de 2, "ab ile biten" üç evrende de 3 durum istedi. Şimdi ölçüyü geçmeyen bir dile bakılır. Sorulacak dil şudur: önce bir miktar a, sonra **tam olarak aynı sayıda** b. Bu dil bir sayma işi ister; okunan a sayısı, b'lerin sayılabilmesi için bir yerde tutulmak zorundadır. Sonlu otomatın tek belleği durumudur ve durum sayısı sabittir. Sorunun bütün ağırlığı buradadır. #### Sayma Gerektiren Bir Dil Önceki dersin üç ölçüsü aynen kullanılır: artık dil öbeklerinin sayısı, ayrılan önek sayısı ve tam sayım. Üçü de aynı evrende çalıştırılır, sonra evren süpürülür. Yanına ikinci bir dil konur: **dengeli dizi**, yani a'nın açtığı ve b'nin kapattığı sayılırsa hiçbir önekte kapanışın açılışı geçmediği ve sonda eşitlendiği dizi. - **HM10** — Hedef dil `esit_sayida`, yani bir dizinin ilk yarısı yalnız a, ikinci yarısı yalnız b ise ve uzunluk çiftse dile aittir. Boş dizi dile aittir. - **HM11** — İkinci hedef `dengeli`, tek bir sayaçla sınanır: a sayacı bir artırır, b bir azaltır; sayaç hiçbir noktada eksiye düşmez ve sonda sıfırdır. - **HM12** — Tam sayım bu derste k=1'den 5'e kadar yapılır. Beş durumlu geçiş tablosu sayısı $5^{10}$'dur; ölçünün bütçesi budur ve k=6 bu derste denenmedi. - **HM13** — Ölçüm hiçbir yerde "bu dil tanınamaz" demez. Söyleyebileceği tek şey, denenen k değerleri ve denenen uzunluk sınırları içinde ne bulunduğudur. ```python """a^n b^n ve dengeli dil: obek , ayrilan onek ve tam sayim yan yana.""" from itertools import product ALFABE = ("a", "b") def diziler(en_uzun): cikti = [""] for n in range(1, en_uzun + 1): cikti += ["".join(d) for d in product(ALFABE, repeat=n)] return cikti def esit_sayida(d): """a^n b^n biciminde mi.""" n = len(d) if n % 2: return False yari = n // 2 return d[:yari] == "a" * yari and d[yari:] == "b" * yari def dengeli(d): """a acar , b kapatir; hicbir onekte kapanis acilisi gecmez.""" sayac = 0 for s in d: sayac += 1 if s == "a" else -1 if sayac < 0: return False return sayac == 0 def en_az_durum(hedef, evren): """Ayirt edilebilirlik obekleri: artik dillerin sayisi.""" onekler = {d[:i] for d in evren for i in range(len(d) + 1)} return len({frozenset(k for k in evren if o + k in hedef) for o in onekler}) def ayrilan_onek(hedef, evren): """Iki onegi ancak IKI uzantisi da evrende kalan bir kuyruk ayirabilir.""" ev = set(evren) onekler = sorted({d[:i] for d in evren for i in range(len(d) + 1)}, key=lambda o: (len(o), o)) imza = {o: tuple((1 if o + k in hedef else 0) if o + k in ev else -1 for k in evren) for o in onekler} secilen = [] for o in onekler: if all(any(x >= 0 and y >= 0 and x != y for x, y in zip(imza[o], imza[p])) for p in secilen): secilen.append(o) return len(secilen) def taniyan_var_mi(k, hedef, evren): """k durumlu BUTUN gecis tablolari; kabul kumesi tutarlilikla secilir.""" hucreler = [(d, s) for d in range(k) for s in ALFABE] for hedefler in product(range(k), repeat=len(hucreler)): gecis = dict(zip(hucreler, hedefler)) gerek, tutarli = {}, True for dizi in evren: d = 0 for s in dizi: d = gecis[(d, s)] istenen = dizi in hedef if gerek.setdefault(d, istenen) != istenen: tutarli = False break if tutarli: return True return False print("uzunluk dizi a^n b^n: obek onek dengeli: obek onek") for u in (2, 4, 6, 8, 10): E = diziler(u) h1 = frozenset(d for d in E if esit_sayida(d)) h2 = frozenset(d for d in E if dengeli(d)) print(f"{u:7d} {len(E):5d} {en_az_durum(h1, E):12d} {ayrilan_onek(h1, E):4d}" f" {en_az_durum(h2, E):14d} {ayrilan_onek(h2, E):4d}") print() print("tam sayim: k = 1..5 icin BUTUN otomatlar denendi") print("uzunluk a^n b^n hedefi taniyan en kucuk k") for u in (2, 3, 4): E = diziler(u) h = frozenset(d for d in E if esit_sayida(d)) k = [i for i in (1, 2, 3, 4, 5) if taniyan_var_mi(i, h, E)] print(f"{u:7d} {str(sorted(h)):28s} {k[0] if k else 'yok'}") ``` ``` uzunluk dizi a^n b^n: obek onek dengeli: obek onek 2 7 4 3 4 3 4 31 6 5 7 4 6 127 8 7 11 5 8 511 10 9 16 6 10 2047 12 11 22 7 tam sayim: k = 1..5 icin BUTUN otomatlar denendi uzunluk a^n b^n hedefi taniyan en kucuk k 2 ['', 'ab'] 3 3 ['', 'ab'] 3 4 ['', 'aabb', 'ab'] 5 ``` Üç sayı yan yana. **Bütçe:** durum sayısı 1'den 5'e, uzunluk sınırı 2'den 10'a. **Bütçenin yanıtladığı:** gereken durum sayısı a'lı b'li dilde **3, 5, 7, 9, 11** diye, dengeli dilde **3, 4, 5, 6, 7** diye büyüyor; uzunluk 4 evreninde tam sayım en küçük k'yı **5** buluyor ve bu, ayrılan önek sayısıyla birebir aynı. **Bütçenin yanıtlayamadığı:** sabit bir k'nın **hiçbir** uzunlukta yetmediği. Ölçüm bunu söyleyemez; söyleyebildiği şey denenen beş uzunluk ve beş k değeri içinde durum sayısının durmadan büyüdüğüdür. Büyümenin nedeni ölçümde değil dildedir. Önce yalnız a'dan oluşan önekler düşünülsün: iki ayrı önek olan `a` ile `aa`, `b` kuyruğuyla ayrılır, çünkü `ab` dile aittir ve `aab` ait değildir; üstelik iki uzantı da evrenin içindedir. Aynı şey `aa` ile `aaa` için `bb` kuyruğuyla, `aaa` ile `aaaa` için `bbb` kuyruğuyla geçerlidir. Uzunluk sınırı 2m olan bir evrende bu zincir m+1 öneğe kadar uzar ve zincirdeki her önek ayrı bir durum ister. Sınır büyüdükçe zincir uzar. Buradaki cümle kesinlikle şudur: **her sabit k için, o k'nın yetmediği bir uzunluk ölçüldü**; "her zaman yetmez" cümlesi kuramın sonucudur ve koşumla kurulmaz. Tam sayım tablosunun ilk iki satırı da okunmalıdır. Uzunluk 2 ile 3 evreninde hedef aynı kalıyor, çünkü tek sayı uzunluklu hiçbir dizi dile ait değil; en küçük k ikisinde de 3. Uzunluk 4'te hedefe `aabb` girer girmez sayı **5'e sıçrıyor**. Yani gereken durum, evrene eklenen dizi sayısıyla değil, dile **yeni bir sayma derinliği** eklenmesiyle artıyor. İki durumlu otomatın hafızası bir bitti; burada gereken şey, kaç a okunduğunu tutan bir sayaçtır ve sayacın alacağı değer sayısı uzunlukla birlikte artar. Öbek sütunu ile önek sütunu arasındaki bir birimlik fark önceki dersteki üst sayımın sürdüğünü gösteriyor: a'lı b'li dilde öbek 4, 6, 8, 10, 12 iken ayrılan önek 3, 5, 7, 9, 11. İki sütunun **eğimi** aynı; ikisi de doğrusal büyüyor. Dengeli dilde ise iki sütun ayrışıyor, öbek 22'ye çıkarken önek 7'de kalıyor — ucuz ölçü ile sınanmış ölçü arasındaki fark, dile göre değişiyor ve bu yüzden ucuz ölçü tek başına yazılmaz. #### Üretim Kuralı Otomatın Yapamadığını Yapıyor Bütçeyi büyütmek bir yol. İkinci yol modeli değiştirmektir. **Üretim kuralı (production rule)**, bir simgeyi bir diziyle değiştirmeye izin veren kuraldır; kuralların art arda uygulanmasına **türetme (derivation)** denir. Bir dilin bütün dizileri sonlu bir kural kümesinden türetilebiliyorsa o dile **bağlamdan bağımsız dil (context-free language)** denir. Dilbilgisi ve ayrıştırma Bilgisayarlar Nasıl Çalışır kursundaki Derleme Aşamaları dersinde kuruldu; sözcük birimleri, soyut sözdizim ağacı ve işleç önceliğinin ağaca gömülmesi orada anlatıldı ve burada tekrarlanmaz. Bu dersin eklediği tek şey ölçüdür: kuralın ürettiği küme ile hedef dilin **birebir aynı** olup olmadığı. - **HM14** — Kural `S -> a S b | boş` iki seçenek taşır ve tek satırdır. Türetme derinliği, kuralın kaç kez uygulandığıdır. - **HM15** — İkinci kural `S -> a S b S | boş`, dengeli dizileri üretir. Ölçüm, üretilen küme ile evrendeki dengeli dizilerin kümesinin eşit olup olmadığıdır; alt küme yetmez. - **HM16** — Kuralın **betimi** ile **koşumu** ayrı ölçülür: betim satır sayısı, koşum türetme derinliğidir. ```python """Uretim kurali: betim sabit kalir , turetme derinligi girdiyle buyur.""" from itertools import product ALFABE = ("a", "b") KURAL = {"S": [("a", "S", "b"), ()]} # S -> a S b | bos def diziler(en_uzun): cikti = [""] for n in range(1, en_uzun + 1): cikti += ["".join(d) for d in product(ALFABE, repeat=n)] return cikti def esit_sayida(d): n = len(d) if n % 2: return False yari = n // 2 return d[:yari] == "a" * yari and d[yari:] == "b" * yari def dengeli(d): sayac = 0 for s in d: sayac += 1 if s == "a" else -1 if sayac < 0: return False return sayac == 0 def turet(en_derin): """Kuraldan en cok `en_derin` adimda uretilen diziler.""" uretilen = {""} onceki = {""} for _ in range(en_derin): yeni = {"a" + d + "b" for d in onceki} uretilen |= yeni onceki = yeni return uretilen def turet_dengeli(en_uzun): """S -> a S b S | bos ; uzunlugu en_uzun'u gecmeyen butun turetmeler.""" kume, degisti = {""}, True while degisti: degisti = False for x in list(kume): for y in list(kume): yeni = "a" + x + "b" + y if len(yeni) <= en_uzun and yeni not in kume: kume.add(yeni) degisti = True return kume print("S -> a S b | bos") print("derinlik uretilen en uzun ayni uzunluktaki hedefi kapsiyor mu") for d in (1, 2, 3, 4, 5): U = turet(d) hedef = {x for x in diziler(2 * d) if esit_sayida(x)} print(f"{d:8d} {len(U):8d} {max(len(x) for x in U):7d} {hedef <= U}") print(" 3 adimda uretilenler:", sorted(turet(3))) print() print("S -> a S b S | bos") print("uzunluk turetilen dengeli dizi ikisi ayni mi") for u in (2, 4, 6, 8): T = turet_dengeli(u) D = {x for x in diziler(u) if dengeli(x)} print(f"{u:7d} {len(T):9d} {len(D):12d} {T == D}") ``` ``` S -> a S b | bos derinlik uretilen en uzun ayni uzunluktaki hedefi kapsiyor mu 1 2 2 True 2 3 4 True 3 4 6 True 4 5 8 True 5 6 10 True 3 adimda uretilenler: ['', 'aaabbb', 'aabb', 'ab'] S -> a S b S | bos uzunluk turetilen dengeli dizi ikisi ayni mi 2 2 2 True 4 4 4 True 6 9 9 True 8 23 23 True ``` Tek satırlık kural üç türetme adımında `""`, `ab`, `aabb`, `aaabbb` üretiyor; bu, uzunluğu 6'yı geçmeyen evrendeki a'lı b'li dizilerin **tamamıdır**. Beş derinlikte uzunluk 10'a kadar aynı sonuç sürüyor: kapsama sütunu beş satırda da `True`. İkinci kural için ölçü daha sıkıdır, çünkü alt küme değil **eşitlik** sınanıyor: uzunluk 8'e kadar üretilen 23 dizi, evrendeki 23 dengeli dizinin aynısı. Bu, önceki bölümün ölçtüğü şeyin karşıtıdır. Aynı dil için otomatın istediği durum sayısı 3'ten 11'e çıkarken, kuralın satır sayısı **1'de kaldı**. Model sınıfını değiştirmek, bütçeyi büyütmekten **başka bir şeydir**: birincisi betimin boyunu sabit tutar, ikincisi betimi büyütür. #### Bütçe Nereye Konuyor İki modelin ödediği bedel aynı yerde durmuyor. Aşağıdaki tablo iki bölümün sayılarını yan yana koyar; durum sütunu ayrılan önek sayısından, derinlik sütunu türetme ölçümünden gelir. | Uzunluk sınırı | Otomat: gereken durum | Kural: satır | Kural: türetme derinliği | |---|---|---|---| | 2 | 3 | 1 | 1 | | 4 | 5 | 1 | 2 | | 6 | 7 | 1 | 3 | | 8 | 9 | 1 | 4 | | 10 | 11 | 1 | 5 | Otomatta büyüyen şey **betimdir**: daha uzun diziler için daha büyük bir makine yazılmak zorundadır ve makinenin kendisi girdiyle birlikte büyür. Kuralda büyüyen şey **koşumdur**: kural aynı kalır, yalnız daha çok kez uygulanır. Bir modelin gücünü ölçerken sorulacak soru "kaç adım harcıyor" değil, **"girdiyle birlikte ne büyüyor"** olmalıdır. Bu ayrımın bir bedeli de var ve saklanmaz. Kural, dizinin dile ait olup olmadığına sonlu otomatın tek geçişiyle karar vermez; türetmeyi araması gerekir ve arama tek geçişten pahalıdır. Ölçüm bunu da gösteriyor: dengeli dil için uzunluk 8'e kadar 23 dizi üretmek, kümenin sabit noktaya oturmasına kadar yinelemeyi sürdürmeyi gerektirdi. Güç bedava gelmiyor; ödenen şey betim boyu yerine arama. #### Özet - Eşit sayıda a ve b isteyen dilde gereken durum sayısı uzunluk sınırıyla birlikte 3, 5, 7, 9, 11 diye büyüyor; dengeli dilde 3, 4, 5, 6, 7 diye. - Uzunluk 4 evreninde k=1'den 5'e kadar bütün otomatlar denendi ve en küçük k **5** çıktı; bu sayı ayrılan önek ölçüsüyle birebir aynı. - Sabit bir k'nın hiçbir uzunlukta yetmediği ölçülmedi ve ölçülemez; ölçülen şey her denenen k için o k'nın yetmediği bir uzunluğun bulunmasıdır. - Tek satırlık `S -> a S b | boş` kuralı üç türetme adımında uzunluğu 6'yı geçmeyen bütün hedef dizileri üretiyor; `S -> a S b S | boş` kuralı uzunluk 8'e kadar 23 dengeli dizinin tamamını, fazlasız üretiyor. - Otomatta girdiyle birlikte büyüyen şey betim, üretim kuralında koşumdur; model sınıfını değiştirmek bütçeyi büyütmekten başka bir şeydir. - Gücün bedeli de ölçüldü: kural tek geçişte karar vermez, türetmeyi arar; kazanılan betim boyu, ödenen arama. #### Sonraki Adım İki model de bir sınırla tanımlandı: biri durum sayısıyla, öteki kural biçimiyle. Sonraki ders sınırı olabildiğince gevşetir ve okunan simgeyi **değiştirebilen**, ileri geri gezinebilen bir şeride sahip bir model kurar. Sorulacak soru şudur: bu modelin bütün üyelerini tek tek sayabilir miyiz ve saydığımızda kaçının durduğunu bir adım bütçesiyle öğrenebilir miyiz. Yanıtın ilk yarısı beklenenden kolay, ikinci yarısı beklenenden zordur. ### Turing Makinesi Source: https://academia.sh/tr/kurslar/hesaplama-kurami/turing-makinesi Şeritli modelin tam sayımla ölçülmesi: 2 durumlu 2 simgeli 20.736 makinenin 9784'ü duruyor, en uzun duran koşum 6 adım ve bütçe 6'dan 200'e çıkarıldığında sayı hiç değişmiyor; durmayan 10.952 makinenin 5040'ı döngü kanıtıyla karara bağlanıyor. Önceki iki ders iki modelle bir sınır çizdi. Sonlu otomat girdiyi tek geçişte okuyor ve belleği durum sayısı kadar; üretim kuralı betimini büyütmeden daha çoğunu üretiyor ama karar vermek için arama gerektiriyor. İkisinin de ortak eksiği aynı: **okuduklarını değiştiremiyorlar.** Bu ders sınırı olabildiğince gevşetir. Model, iki yönde de sınırsız uzayan bir **şeride (tape)** sahiptir; şeridin her hücresinde bir simge durur, makine bulunduğu hücreyi okur, üzerine yazar, bir adım sağa ya da sola gider ve durumunu değiştirir. Bu modelin adı **Turing makinesidir** ve kuram bu adı kullanır. Kursun kuralı gereği burada anılan yalnız addır: kişi anlatılmaz, ad hiçbir kod tanımlayıcısında geçmez. Adın taşıdığı tek bilgi, aşağıdaki tanımın kuramda hangi kavrama karşılık geldiğidir. #### Şerit ve Makine Şerit tek başına yeni bir güç değil, yeni bir **bellek** biçimidir. Sonlu otomatta bellek durum sayısıyla sınırlıydı ve girdiyle birlikte büyüyemiyordu; şeritte bellek koşum boyunca büyür. Buna karşılık makinenin **betimi** hâlâ sonludur: durum sayısı ve simge sayısı verildiğinde geçiş tablosunun satır sayısı bellidir. Bu, bir bütçe demektir ve bütçe demek tam sayım demektir. - **HM17** — Şerit iki yönde de boştur; boş hücre 0 simgesini taşır ve 0 yazılmış bir hücre hiç yazılmamış hücreden ayırt edilmez. Abece iki simgelidir. - **HM18** — Bir hücrenin içeriği üçlüdür: yazılacak simge, gidilecek yön, yeni durum. Yeni durum k ise makine **durur**; başlangıç durumu 0'dır ve makine boş şeritte başlar. - **HM19** — k durumlu, iki simgeli **bütün** makineler sayılabilir. Geçiş tablosunda 2k hücre vardır ve her hücre $2 \cdot 2 \cdot (k+1)$ seçenekten birini alır. k=1 için 64, k=2 için 20.736 makine. - **HM20** — Bütçe **adımdır**. Bir adım, tek bir hücre okuma, yazma ve hareketten oluşur. Süre ölçülmez. - **HM21** — "Durduğu bilinen" sayısı **birikimlidir**: küçük bütçede durduğu görülen bir makine büyük bütçede yeniden sayılmaz. ```python """Serit uzerinde calisan makine ailesi: k durumlu , 2 simgeli BUTUN makineler.""" from itertools import product YAZ = (0, 1) YON = (-1, 1) def makineler(k): """Hucre: (yazilacak simge, yon, yeni durum). Yeni durum k ise DUR.""" hucre = [(y, o, d) for y in YAZ for o in YON for d in range(k + 1)] yerler = [(durum, simge) for durum in range(k) for simge in (0, 1)] for secim in product(hucre, repeat=len(yerler)): yield dict(zip(yerler, secim)) def kos(makine, k, butce): """Bos serit. Doner: (durdu_mu, adim, serite yazilan 1 sayisi).""" serit = {} konum, durum, adim = 0, 0, 0 while adim < butce: simge = serit.get(konum, 0) yaz, yon, yeni = makine[(durum, simge)] serit[konum] = yaz konum += yon adim += 1 if yeni == k: return True, adim, sum(serit.values()) durum = yeni return False, adim, sum(serit.values()) def butce_taramasi(k, butceler): tum = list(makineler(k)) bilinen = set() print(f"k = {k} durumlu aile , makine sayisi {len(tum)}") for b in butceler: for i, m in enumerate(tum): if i not in bilinen and kos(m, k, b)[0]: bilinen.add(i) print(f" butce {b:4d} durdugu bilinen {len(bilinen):6d}" f" bilinmeyen {len(tum) - len(bilinen):6d}") return tum BUTCE = (1, 3, 6, 7, 10, 50, 200) butce_taramasi(1, BUTCE) tum = butce_taramasi(2, BUTCE) print() dagilim = {} en_iyi = None for m in tum: durdu, adim, bir = kos(m, 2, 200) if durdu: dagilim[adim] = dagilim.get(adim, 0) + 1 if en_iyi is None or (adim, bir) > (en_iyi[1], en_iyi[2]): en_iyi = (m, adim, bir) print("duran makinelerin adim dagilimi:", dict(sorted(dagilim.items()))) print("en uzun duran kosum:", en_iyi[1], "adim ,", en_iyi[2], "adet 1") print("gecis tablosu:", {f"d{d}s{s}": v for (d, s), v in en_iyi[0].items()}) print() print("adim durum yeni konum serit") serit, konum, durum, adim = {}, 0, 0, 0 while adim < 200: simge = serit.get(konum, 0) yaz, yon, yeni = en_iyi[0][(durum, simge)] serit[konum] = yaz konum += yon adim += 1 goster = "".join(str(serit.get(p, 0)) for p in range(min(serit), max(serit) + 1)) print(f"{adim:4d} {durum:5d} {yeni:4d} {konum:5d} {goster}") if yeni == 2: break durum = yeni ``` ``` k = 1 durumlu aile , makine sayisi 64 butce 1 durdugu bilinen 32 bilinmeyen 32 butce 3 durdugu bilinen 32 bilinmeyen 32 butce 6 durdugu bilinen 32 bilinmeyen 32 butce 7 durdugu bilinen 32 bilinmeyen 32 butce 10 durdugu bilinen 32 bilinmeyen 32 butce 50 durdugu bilinen 32 bilinmeyen 32 butce 200 durdugu bilinen 32 bilinmeyen 32 k = 2 durumlu aile , makine sayisi 20736 butce 1 durdugu bilinen 6912 bilinmeyen 13824 butce 3 durdugu bilinen 9600 bilinmeyen 11136 butce 6 durdugu bilinen 9784 bilinmeyen 10952 butce 7 durdugu bilinen 9784 bilinmeyen 10952 butce 10 durdugu bilinen 9784 bilinmeyen 10952 butce 50 durdugu bilinen 9784 bilinmeyen 10952 butce 200 durdugu bilinen 9784 bilinmeyen 10952 duran makinelerin adim dagilimi: {1: 6912, 2: 2304, 3: 384, 4: 128, 5: 16, 6: 40} en uzun duran kosum: 6 adim , 4 adet 1 gecis tablosu: {'d0s0': (1, -1, 1), 'd0s1': (1, 1, 1), 'd1s0': (1, 1, 0), 'd1s1': (1, -1, 2)} adim durum yeni konum serit 1 0 1 -1 1 2 1 0 0 11 3 0 1 1 11 4 1 0 2 111 5 0 1 1 1111 6 1 2 0 1111 ``` Üç sayı yan yana. **Bütçe:** adım bütçesi 1'den 200'e, aile büyüklüğü 64 ve 20.736. **Bütçenin yanıtladığı:** iki durumlu ailede **9784** makinenin durduğu görüldü; tek durumlu ailede **32**. **Bütçenin yanıtlayamadığı:** iki durumlu ailede **10.952** makine bu bütçede durmadı ve bütçe 6'dan 200'e çıkarıldığında bu sayı **hiç değişmedi**. Bütçe süpürmesinin verdiği asıl bilgi doyum noktasıdır. Sayı 1. adımda 6912, 3. adımda 9600, 6. adımda 9784 ve **oradan sonra sabit**. Adım dağılımı bunu tek satırda gösteriyor: 6912 makine bir adımda, 2304 makine iki adımda duruyor ve altı adımda duran yalnız 40 makine var. Bu ailede duran her koşumun en çok 6 adım sürdüğü kuramın bilinen bir sonucudur; ölçüm bu sonuçla **uyuşuyor**, onu kurmuyor. İlk satırdaki 6912 sayısı da hesaplanabilir ve hesaplanması ölçümün doğruluğunu sınar. Makine boş şeritte başladığı için ilk okunan hücre her zaman durum 0 ile simge 0'ın kesişimidir. O hücrenin 12 seçeneği vardır ve bunların 4'ünde yeni durum durma durumudur; yani makinelerin tam üçte biri daha ilk adımda durur. 20.736'nın üçte biri 6912'dir ve tablo bunu veriyor. Ölçümün beklenen bir sayıyı tutturması onu doğrulamaz ama tutturmaması bir kusuru gösterirdi; bu kursta her sayının böyle bir sağlaması aranır. Son tablo tek bir makinenin izidir ve şeridin ne işe yaradığını gösterir. Makine boş şeritte başlıyor, ilk adımda sola yazıyor, sonra sağa dönüyor ve dört hücreye 1 yazdıktan sonra altıncı adımda duruyor. Aynı hücreye iki kez uğradığı üçüncü ve beşinci adımlara dikkat edilmelidir: makine önceki yazdığını okuyup kararını ona göre veriyor. Sonlu otomatta bunun karşılığı yoktur. #### Aynı Yordam Bütün Makineleri Koşturuyor Yukarıdaki koşumların hepsini yapan tek bir yordam var: `kos`. Makine, bu yordamın içine gömülmüş değil; **argüman olarak** veriliyor. 20.736 makinenin her biri bir geçiş tablosudur, yani bir veridir ve tek bir yordam bu verilerin tümünü yürütüyor. Modelin ayırt edici özelliği budur: bir makinenin betimi başka bir makinenin girdisi olabilir. Bu yüzden bu model **evrensel** sayılır — programı veri gibi taşıyabildiği için. Buradan kuramın en çok anılan önermesi çıkar. **Church–Turing tezi**, sezgisel anlamda "yordamla hesaplanabilir" denen her şeyin bu modelle hesaplanabildiğini söyler. Tezin adında tez sözcüğü rastlantı değildir: bu bir **kanıtlanmış önerme değil**, biçimsel model ile biçimsel olmayan "yordam" kavramı arasında kurulmuş bir eşleştirmedir. Kanıtlanamaz, çünkü iki yanından biri tanımsızdır; sınanabilir, çünkü önerilen her yeni model şimdiye kadar bu modelle aynı kümeyi hesapladı. Evrenselliğin ölçülebilir yanı da var. Önceki derste bir ayrım kurulmuştu: otomatta girdiyle büyüyen şey betim, üretim kuralında koşumdu. Şeritli modelde betim **hiç büyümez**: iki durumlu bir makinenin geçiş tablosu dört satırdır ve şeride kaç hücre yazılırsa yazılsın dört satır kalır. Büyüyen tek şey koşumdur — adım sayısı ve kullanılan hücre sayısı. Bu, gücün nereden geldiğini açıkça gösterir: sonlu bir betim, sınırsız bir çalışma alanı. Tezin bu derse getirdiği pratik sonuç şudur: bir soruya **bu model** karar veremiyorsa, o soruya karar verecek bir yordam aramak da boşunadır. Bir sonraki bölümün ölçtüğü şey tam olarak bu sınırın kıyısındadır. #### Bütçenin Söylemediğini Kanıt Söyleyebilir mi "Bu bütçede durmadı" ile "hiç durmaz" aynı cümle değildir ve bu kursta ikincisi bir koşumla yazılmaz. Ama bazen koşumun içinden bir **kanıt** çıkarılabilir. Şerit iki yönde de boş olduğu için, makinenin görüntüsü yalnız duruma ve şeritteki 1'lerin **kafaya göre** konumuna bağlıdır. Aynı görüntü ikinci kez oluşursa makine aradaki hareketi sonsuza dek yineler; ilk turda durmadıysa hiçbir turda durmaz. Bu bir gözlem değil, çıkarımdır. - **HM22** — Görüntü, `(durum, kafaya göre 1 taşıyan hücrelerin kümesi)` ikilisidir. 0 yazılan hücre boş hücreden ayırt edilmez. - **HM23** — Görüntü tekrarı **döngü kanıtıdır**; makine o koşumda hiç durmaz. - **HM24** — Kanıt bulunamaması bir şey söylemez. Sonuç üç kümeye ayrılır: `durdu`, `dongu` ve `bilinmiyor`. - **HM25** — Döngü taraması da süpürülür: bütçe 10, 50 ve 200'de tekrarlanır. - **HM26** — Çizgede döngü tespiti Veri Yapıları kursunda kuruldu ve burada yeniden anlatılmaz; buradaki tek fark, düğümlerin önceden verilmemesi ve koşum sırasında üretilmesidir. ```python """Butcenin yanitlayamadigi makinelerin kaci KANITLA karara baglaniyor.""" from itertools import product YAZ = (0, 1) YON = (-1, 1) def makineler(k): hucre = [(y, o, d) for y in YAZ for o in YON for d in range(k + 1)] yerler = [(durum, simge) for durum in range(k) for simge in (0, 1)] for secim in product(hucre, repeat=len(yerler)): yield dict(zip(yerler, secim)) def cozumle(makine, k, butce): """Doner: ('durdu' | 'dongu' | 'bilinmiyor', adim). Serit iki yonde de bostur; bu yuzden konuma gore otelenmis ayni goruntu ikinci kez olusursa makine ayni hareketi sonsuza dek yineler. """ serit = {} konum, durum, adim = 0, 0, 0 gorulen = {(0, frozenset())} while adim < butce: simge = serit.get(konum, 0) yaz, yon, yeni = makine[(durum, simge)] serit[konum] = yaz konum += yon adim += 1 if yeni == k: return "durdu", adim durum = yeni imza = (durum, frozenset(p - konum for p, v in serit.items() if v)) if imza in gorulen: return "dongu", adim gorulen.add(imza) return "bilinmiyor", adim for k in (1, 2): tum = list(makineler(k)) print(f"k = {k} durumlu aile , makine sayisi {len(tum)}") en_gec = 0 for butce in (10, 50, 200): sayim = {"durdu": 0, "dongu": 0, "bilinmiyor": 0} for m in tum: sonuc, adim = cozumle(m, k, butce) sayim[sonuc] += 1 if sonuc == "dongu": en_gec = max(en_gec, adim) print(f" butce {butce:4d} durdu {sayim['durdu']:6d}" f" dongu kanitlandi {sayim['dongu']:6d}" f" bilinmiyor {sayim['bilinmiyor']:6d}") print(f" dongunun en gec yakalandigi adim: {en_gec}") ``` ``` k = 1 durumlu aile , makine sayisi 64 butce 10 durdu 32 dongu kanitlandi 16 bilinmiyor 16 butce 50 durdu 32 dongu kanitlandi 16 bilinmiyor 16 butce 200 durdu 32 dongu kanitlandi 16 bilinmiyor 16 dongunun en gec yakalandigi adim: 1 k = 2 durumlu aile , makine sayisi 20736 butce 10 durdu 9784 dongu kanitlandi 5040 bilinmiyor 5912 butce 50 durdu 9784 dongu kanitlandi 5040 bilinmiyor 5912 butce 200 durdu 9784 dongu kanitlandi 5040 bilinmiyor 5912 dongunun en gec yakalandigi adim: 8 ``` İki durumlu ailede bütçenin karara bağladığı 9784 makinenin yanına, kanıtın karara bağladığı **5040** makine ekleniyor. Geriye **5912** makine kalıyor ve bu ders bunlar için bir şey söylemez. Kalanların çoğu şeritte bir yöne doğru sürüklenen makinelerdir: her adımda yeni bir hücreye yazdıkları için görüntüleri hiç tekrarlanmaz, oysa durmadıkları bir insan gözüyle bakıldığında görülebilir. Kanıt aracının kapsamı, aradığı örüntü kadardır. Üç kümeye ayırmanın kendisi bu kursun yöntemidir. İki kümeli bir rapor, yani yalnız "durdu" ile "durmadı", ölçümü bir yargıya çevirirdi; üçüncü küme yargının nerede bittiğini yazılı tutuyor. Tek durumlu ailede de aynı yapı görülüyor: 32 durdu, 16 kanıtlandı, 16 bilinmiyor. Aile 324 kat büyüdüğünde oranlar değişti ama üçüncü küme **hiç boşalmadı**. Üç bütçede de aynı sayılar çıkıyor ve nedeni son satırda: döngü en geç **8. adımda** yakalanıyor. Yani bütçe 10 ile bütçe 200 arasında bu ölçü için hiçbir fark yok. Aynı derste iki ayrı bütçe süpürmesi iki ayrı sonuç verdi: durma taraması 6'da doydu, döngü taraması 8'de. **Doyum noktası bütçenin değil, sorunun özelliğidir.** #### Özet - Şeritli makine okuduğu hücreye yazabilir ve iki yönde gezebilir; belleği koşum boyunca büyür, betimi ise sonlu kalır. - İki simgeli ailelerde bütün makineler sayılabilir: bir durumlu ailede 64, iki durumlu ailede 20.736 makine. - Adım bütçesi süpürüldüğünde duran makine sayısı 6912, 9600, 9784 diye ilerleyip 6. adımda doyuyor; bütçenin 200'e çıkarılması bu sayıyı hiç değiştirmiyor. - En uzun duran koşum 6 adım sürüyor ve şeride dört adet 1 yazıyor; bu ailedeki üst sınırın 6 olduğu kuramın sonucudur, ölçüm yalnız onunla uyuşur. - Tek bir koşum yordamı 20.736 makinenin tümünü yürütüyor; makinenin betimi veridir ve bu, modelin evrensel sayılmasının nedenidir. - Bütçede durmayan 10.952 makinenin 5040'ı, görüntü tekrarına dayanan bir döngü kanıtıyla karara bağlanıyor; kalan 5912 makine için ölçüm bir şey söylemez. #### Sonraki Adım Bu derste "durdu" sayısı bir bütçeyle, "hiç durmaz" sayısı bir kanıtla geldi ve ikisinin toplamı aileyi kapatmadı. Sonraki ders bu boşluğun rastlantı olup olmadığını sorar. Tek satırlık bir kural üzerinde bütçe 5'ten 200'e süpürülecek, bin başlangıcın hepsinin durduğu görülecek ve tam o noktada dersin en önemli cümlesi yazılacak: gözlem kanıt değildir. ### Karar Verilemezlik Source: https://academia.sh/tr/kurslar/hesaplama-kurami/karar-verilemezlik Gözlemin kanıt olmadığının ölçülmesi: tek satırlık bir sayaç kuralında 1000 başlangıcın bütçe 5'te 7'si, 200'de 1000'i duruyor, ama aynı bütçe 5000 başlangıçlık evrende 9 tanesini karara bağlayamıyor ve her bütçeyi yanıltan bir başlangıç bulunabiliyor. Önceki ders iki durumlu makine ailesini üç kümeye ayırdı: 9784 makine durdu, 5040 makinenin hiç durmayacağı kanıtlandı, 5912 makine için hiçbir şey söylenmedi. Üçüncü kümenin varlığı bir eksiklik gibi görünebilir; bu ders onun bir eksiklik olmadığını gösterir. Bunun için makine ailesi bırakılıp tek bir kurala bakılır. Kural bir satırdır ve bir çocuğun anlayacağı kadar basittir: sayı tekse üçle çarpılıp bir eklenir, çiftse ikiye bölünür; sayı 1 olunca durulur. Kuralda ne dallanma derinliği ne de saklanan bir durum var. Kuralın kısalığı ile davranışının öngörülemezliği arasındaki uçurum bu dersin bütün konusudur. #### Tek Satırlık Kural, Öngörülemez Davranış Ölçü önceki derslerdekiyle aynı biçimde kurulur. Bütçe adım sayısıdır, evren başlangıç sayılarının kümesidir ve her bütçe değerinde kaç başlangıcın durduğu **birikimli** sayılır. - **HM27** — Kural tek satırdır ve hiçbir seçenek taşımaz: verilen sayı için sonraki sayı tektir. Belirlenimci bir kuraldır, hiçbir rastgelelik içermez. - **HM28** — Evren, 1'den üst sınıra kadar olan tam sayılardır. İlk ölçümde üst sınır 1000. - **HM29** — Bütçe adım sayısıdır. Bütçe dolduğunda koşum kesilir ve o başlangıç için sonuç **bilinmiyor** sayılır; "durmaz" yazılmaz. - **HM30** — Harcanan adım da ayrıca toplanır, çünkü bir bütçenin bedeli sonucun yanında durmadıkça okunamaz. - **HM31** — Ara değerlerin en yükseği kaydedilir. Kuralın çıktısı düşerek gitmiyor; önce büyüyor. ```python """Tek satirlik sayac kurali: adim butcesi supuruluyor.""" def sayac_kosumu(n, butce): """n tek ise 3n+1 , cift ise n/2. n=1 olunca durur.""" adim, en_yuksek = 0, n while n != 1 and adim < butce: n = 3 * n + 1 if n % 2 else n // 2 en_yuksek = max(en_yuksek, n) adim += 1 return {"durdu": n == 1, "adim": adim, "en_yuksek": en_yuksek} def butce_taramasi(butceler, ust=1000): bilinen = set() print(f"tek satirlik sayac kurali , {ust} baslangic") print("butce durdugu bilinen bilinmeyen harcanan adim") for b in butceler: harcanan = 0 for n in range(1, ust + 1): k = sayac_kosumu(n, b) harcanan += k["adim"] if k["durdu"]: bilinen.add(n) print(f"{b:5d} {len(bilinen):15d} {ust - len(bilinen):10d} {harcanan:13d}") butce_taramasi((5, 20, 50, 100, 200)) en_uzun = max(range(1, 1001), key=lambda n: sayac_kosumu(n, 1000)["adim"]) k = sayac_kosumu(en_uzun, 1000) print(f"en uzun kosum: n = {en_uzun} -> {k['adim']} adim ," f" ara degerin en yuksegi {k['en_yuksek']}") ``` ``` tek satirlik sayac kurali , 1000 baslangic butce durdugu bilinen bilinmeyen harcanan adim 5 7 993 4985 20 155 845 19159 50 569 431 37815 100 756 244 54426 200 1000 0 59542 en uzun kosum: n = 871 -> 178 adim , ara degerin en yuksegi 190996 ``` Üç sayı yan yana. **Bütçe:** 5, 20, 50, 100, 200 adım. **Bütçenin yanıtladığı:** karara bağlanan başlangıç sayısı **7**, 155, 569, 756 ve **1000**. **Bütçenin yanıtlayamadığı:** 993, 845, 431, 244 ve sonunda 0 başlangıç. Önceki dersin makine ailesinde bütçeyi büyütmek 6. adımdan sonra hiçbir şey değiştirmiyordu. Burada tersi oluyor: bütçe 40 katına çıkarken karara bağlanan başlangıç sayısı 7'den 1000'e, yani 142 katına çıkıyor. **Bütçeyi büyütmek bazen hiçbir şeyi değiştirmez, bazen her şeyi değiştirir ve hangisi olduğu ancak ölçülerek görülür.** Bedeli de ölçülmüştür: 4985 adımdan 59.542 adıma, on iki katına. Son satır kuralın neden öngörülemez olduğunu gösteriyor. En uzun koşum n=871 için 178 adım sürüyor ve bu koşumda ara değer **190.996**'ya çıkıyor. Yani 871'den başlayan bir dizi, 1'e inmeden önce başlangıcının 219 katına yükseliyor. Kuralın kendisi bir satır; davranışı ise başlangıca göre bu kadar sıçrıyor. Ve tam burada dersin en önemli cümlesi yazılmalıdır. **1000 başlangıcın 1000'inin durması, hepsinin duracağının kanıtı değildir.** Tablo yalnız şunu söyler: denenen bin başlangıcın her biri, en çok 200 adımda 1'e indi. Denenmeyenler hakkında hiçbir şey söylemez ve bir sonraki bölüm bunun boş bir kaygı olmadığını sayıyla gösterir. #### Aynı Bütçe, Başka Evren Bir bütçenin "yeterli" olması onun bir özelliği değildir. İlk derste bu, üç durumlu otomatların uzunluk sınırı 1 olan evrende her dili tanıyıp uzunluk 4'te milyonda yarımı tanımasıyla ölçülmüştü. Aynı ölçü burada yinelenir: bütçe sabit tutulur, evren büyütülür. - **HM32** — Evren süpürmesi üst sınırı 1000, 2000 ve 5000 yapar. Bütçe 200'de sabittir. - **HM33** — **Bütçeli karar verici**, bütçe dolduğunda "durmaz" diyen yordamdır. Bu yordam yanılabilir ve yanıldığı başlangıç aranarak bulunur. - **HM34** — Bir başlangıcın durduğu **kanıtla** da gösterilebilir: sayı ikinin bir kuvvetiyse her adımda ikiye bölünür ve üs kadar adımda 1'e iner. Bu bir koşum sonucu değil, kuralın okunmasıdır. ```python """Ayni butce baska evrende: yeterlilik butcenin ozelligi degil.""" def sayac_kosumu(n, butce): adim = 0 while n != 1 and adim < butce: n = 3 * n + 1 if n % 2 else n // 2 adim += 1 return n == 1 print("butce 200 , evren supurmesi") print(" ust durdugu bilinen bilinmeyen") for ust in (1000, 2000, 5000): b = sum(1 for n in range(1, ust + 1) if sayac_kosumu(n, 200)) print(f"{ust:5d} {b:15d} {ust - b:10d}") print() print("her butceyi yaniltan en kucuk baslangic") for butce in (5, 20, 50, 100, 200, 300): n = 1 while sayac_kosumu(n, butce): n += 1 print(f" butce {butce:4d} -> n = {n}") print() kuvvetler = [n for n in range(1, 1001) if n & (n - 1) == 0] print("kanitla karara baglanan: ikinin kuvvetleri") print(" 1000'e kadar", len(kuvvetler), "baslangic ,", "sinama tek karsilastirma , en uzun kosumu", max(len(bin(n)) - 3 for n in kuvvetler), "adim") print(" hepsi gercekten duruyor mu:", all(sayac_kosumu(n, 1000) for n in kuvvetler)) ``` ``` butce 200 , evren supurmesi ust durdugu bilinen bilinmeyen 1000 1000 0 2000 2000 0 5000 4991 9 her butceyi yaniltan en kucuk baslangic butce 5 -> n = 3 butce 20 -> n = 25 butce 50 -> n = 27 butce 100 -> n = 27 butce 200 -> n = 2463 butce 300 -> n = 26623 kanitla karara baglanan: ikinin kuvvetleri 1000'e kadar 10 baslangic , sinama tek karsilastirma , en uzun kosumu 9 adim hepsi gercekten duruyor mu: True ``` İlk tablo önceki bölümün sonucunu bozuyor. Bütçe 200, bin başlangıcın bininde ve iki bin başlangıcın iki bininde yetiyor; beş bin başlangıçta **9 tanesini** karara bağlayamıyor. "Bütçe 200 yeter" cümlesi, evren yazılmadan hiçbir şey anlatmaz. İkinci tablo daha keskindir. Her bütçe için, o bütçeyle çalışan karar vericiyi yanıltan bir başlangıç bulundu: bütçe 5 için 3, bütçe 20 için 25, bütçe 100 için 27, bütçe 200 için **2463**, bütçe 300 için **26.623**. Yanıltan başlangıç bütçe büyüdükçe uzaklaşıyor ama kaybolmuyor. Ölçümün söylediği tam olarak şudur: **denenen altı bütçenin altısı için de bir karşı örnek bulundu.** Her bütçe için böyle bir örneğin var olduğu bu tablodan çıkarılamaz; o, ölçümün değil kuramın işidir. Üçüncü blok bambaşka bir kaynaktan gelen bilgiyi gösteriyor. İkinin kuvvetleri için durma, koşturulmadan bilinir: her adım sayıyı ikiye böler, üs kadar adımda 1'e iner. Bu **kanıt** tek bir karşılaştırmayla sınanır ve 1000'e kadar **10 başlangıcı** kapsar. Koşum ise 59.542 adım harcayarak 1000 başlangıcı kapsıyor. Kanıt ucuz ve dar, koşum pahalı ve geniş; ikisi farklı türden bilgi verir ve biri ötekinin yerini tutmaz. İleri Algoritmalar kursundaki ucuz sınama da tek yöne çalışıyordu; buradaki de öyledir. #### İki Yanıt ve Üç Yanıt Bütçeli bir karar vericinin iki tasarımı vardır ve aralarındaki fark ölçülebilir. Birincisi bütçe dolduğunda "durmaz" der ve her başlangıç için bir yanıt üretir. İkincisi bütçe dolduğunda "bilinmiyor" der ve bazı başlangıçları yanıtsız bırakır. İkisi tam olarak aynı koşumu yapar, aynı adımı harcar; ayrıldıkları tek yer, bütçenin bittiği andaki cümledir. - **HM35** — Referans yanıt 100.000 adımlık bir bütçeden alınır. Bu evrendeki başlangıçların tümü 300 adımın altında durduğu için referans, **bu evren için** kesindir; daha büyük bir evren için aynı şey söylenemez. - **HM36** — Yanlış sayısı, karar vericinin verdiği yanıtın referanstan ayrıldığı başlangıç sayısıdır. "Bilinmiyor" bir yanıt sayılmaz ve yanlış sayılmaz. ```python """Iki yanitli karar verici ile uc yanitli olanin ayni evrende karsilastirilmasi.""" def sayac_kosumu(n, butce): adim = 0 while n != 1 and adim < butce: n = 3 * n + 1 if n % 2 else n // 2 adim += 1 return n == 1, adim def iki_yanitli(n, butce): """Butce dolunca 'durmaz' der. Yanilabilir.""" durdu, _ = sayac_kosumu(n, butce) return "durur" if durdu else "durmaz" def uc_yanitli(n, butce): """Butce dolunca 'bilinmiyor' der. Yanilmaz , ama her zaman yanit vermez.""" durdu, _ = sayac_kosumu(n, butce) return "durur" if durdu else "bilinmiyor" UST = 5000 gercek = {n: sayac_kosumu(n, 100000)[0] for n in range(1, UST + 1)} print(f"evren {UST} baslangic , gercek yanit 100000 adimlik kosumdan alindi") print("butce iki yanitli: yanlis uc yanitli: yanlis bilinmiyor harcanan adim") for butce in (5, 20, 50, 100, 200, 300): yanlis2 = yanlis3 = bilinmiyor = harcanan = 0 for n in range(1, UST + 1): harcanan += sayac_kosumu(n, butce)[1] y2, y3 = iki_yanitli(n, butce), uc_yanitli(n, butce) if (y2 == "durur") != gercek[n]: yanlis2 += 1 if y3 == "bilinmiyor": bilinmiyor += 1 elif (y3 == "durur") != gercek[n]: yanlis3 += 1 print(f"{butce:5d} {yanlis2:19d} {yanlis3:18d} {bilinmiyor:10d} {harcanan:13d}") ``` ``` evren 5000 baslangic , gercek yanit 100000 adimlik kosumdan alindi butce iki yanitli: yanlis uc yanitli: yanlis bilinmiyor harcanan adim 5 4993 0 4993 24985 20 4758 0 4758 98948 50 3110 0 3110 218633 100 1666 0 1666 332345 200 9 0 9 387867 300 0 0 0 387968 ``` Aynı bütçe, aynı koşum, aynı adım — iki ayrı sonuç. İki yanıtlı tasarım bütçe 5'te **4993** başlangıçta yanılıyor; bütçe 200'de 9, bütçe 300'de 0. Üç yanıtlı tasarım hiçbir bütçede yanılmıyor: yanlış sütunu altı satırda da **0**. Ödediği bedel yanıtsız bıraktığı başlangıçlardır ve bu sayı yanlış sütunundakiyle birebir aynı. Yani üçüncü yanıt bir bilgi kaybı değil, **yanlışın adının doğru konmasıdır.** Son sütun bir şeyi daha söylüyor. Bütçe 200'den 300'e çıkarken harcanan adım 387.867'den 387.968'e, yani yalnız 101 adım artıyor — çünkü 200 adımı geçen yalnız 9 başlangıç var. Kalan belirsizliği kapatmanın bedeli, ona kadar harcanan bütün bütçenin yanında **on binde üçtür**. Belirsizliğin ucuz kapandığı yerde kapatılmaması bir tasarım kusurudur; ama bu evrende ucuz olması, her evrende ucuz olacağı anlamına gelmez. #### Durma Problemi Neden Karar Verilemez Şimdiye kadar ölçülen her şey tek bir kural içindi. **Durma problemi** bundan geneldir: verilen bir program betimi ile verilen bir girdi için, o programın durup durmayacağını söylemek. Bu problemin **karar verilemez** olduğu kuramın kanıtlanmış bir sonucudur ve aşağıdaki taslak o kanıtın biçimidir; bu derste hiçbir koşum bunu kurmaz. Varsayılsın ki her program betimi ve her girdi için doğru yanıt veren bir `karar_ver` yordamı var. O zaman ikinci bir yordam yazılabilir: `karsit`, kendisine verilen bir betimi alır, `karar_ver`i o betim üzerinde o betimin kendisini girdi vererek çağırır; yanıt "durur" ise sonsuza dek döner, yanıt "durmaz" ise hemen durur. Şimdi `karsit` kendi betimiyle çağrılsın. `karar_ver` "durur" derse `karsit` dönmeye başlar, yani durmaz. "Durmaz" derse `karsit` hemen durur. İki durumda da varsayılan yordam yanlış yanıt vermiştir. Varsayım çelişki ürettiğine göre böyle bir yordam yoktur. Bu kanıtın gücü, hiçbir bütçeye başvurmamasıdır. Önceki bölümde her bütçe için bir karşı örnek **arandı ve bulundu**; kanıt ise aramaz, tek bir yordamın var olamayacağını gösterir. Bir önceki derste anılan tez burada işe yarar: sonuç tek bir modele değil, "yordam" kavramının kendisine ilişkindir, çünkü tez bütün makul modelleri aynı kümeye bağlar. Sonucun mühendislikteki karşılığı şudur: bir programın davranışına ilişkin soruların büyük bölümü için **her programda doğru** yanıt veren bir yordam yoktur. İki programın aynı çıktıyı verip vermediği, bir kod parçasının hiç çalışmayacağı, bir döngünün sonlanacağı — bunların hepsi durma problemini içerir ve hepsi aynı sonucun kapsamındadır. Bu, çözümleme araçlarının yararsız olduğu anlamına gelmez; söylediği şey, böyle bir aracın **iki değil üç** yanıt vermek zorunda olduğudur. Önceki dersin `durdu`, `dongu` ve `bilinmiyor` biçimindeki üçlü ayrımı tam olarak buydu ve o üçüncü küme keyfî bir eksiklik değil, sonucun kendisidir. İleri Algoritmalar kursunun bıraktığı iki borçtan biri burada ödendi. Bazı sorular için yanıtın bilinmemesi **bilgimiz hakkında** değil, **problemler hakkında** bir gerçek olabilir ve durma problemi bunun kanıtlanmış örneğidir. İkinci borç, yani kaba kuvvetten daha iyisinin neden bilinmediği, hâlâ açıktır: orada sorulan şey bir sorunun çözülüp çözülemeyeceği değil, **ne kadar hızlı** çözülebileceğidir. #### Özet - Tek satırlık sayaç kuralında 1000 başlangıçtan bütçe 5'te 7, 20'de 155, 50'de 569, 100'de 756 ve 200'de 1000 tanesi karara bağlanıyor; harcanan adım 4985'ten 59.542'ye çıkıyor. - En uzun koşum n=871 için 178 adım sürüyor ve ara değer 190.996'ya yükseliyor; kural bir satır, davranış öngörülemez. - 1000 başlangıcın 1000'inin durması, hepsinin duracağının kanıtı değildir. - Aynı 200 bütçesi 1000 ve 2000 başlangıçta hepsini karara bağlıyor, 5000 başlangıçta 9 tanesini bağlayamıyor; denenen altı bütçenin altısı için de yanıltan bir başlangıç bulundu. - Kanıt ucuz ve dardır: ikinin kuvvetleri için durma tek bir karşılaştırmayla bilinir ve 1000'e kadar 10 başlangıcı kapsar; koşum 59.542 adımla 1000 başlangıcı kapsar. - Durma probleminin karar verilemez olduğu kuramın sonucudur, koşumun değil; sonucun pratik karşılığı ölçülmüştür: iki yanıtlı karar verici 5000 başlangıçta bütçe 5'te 4993 kez yanılırken, aynı koşumu yapan üç yanıtlı tasarımın yanlış sayısı altı bütçede de sıfırdır. #### Sonraki Adım Hesaplama Modelleri konusu sınırın bir yüzünü gösterdi: bazı soruların yanıtı **hiçbir** yordamla verilemez. Sonraki konu öteki yüzü alır. Orada bütün problemler karara bağlanabilir olacak, soru yalnız **kaç adımda** olacaktır. Karmaşıklık Sınıfları, İleri Algoritmalar kursunun bıraktığı ikinci borcu üstlenir ve önce en kolay sınıfı kurar: polinom zamanda çözülebilen karar problemleri. ## Karmaşıklık Sınıfları Polinom zaman, doğrulanabilirlik ve sertifika, indirgemeyle zorluk aktarımı, tümleyen problemlerin asimetrisi, açık kalan soru ve yaklaşık çözümlerin ölçülen sapması. ### P Sınıfı Source: https://academia.sh/tr/kurslar/hesaplama-kurami/p-sinifi Polinom zamanda çözülebilir karar problemlerinin, sonlu bir adım bütçesi altında ölçülmesi: aynı 20 örnekte eşik problemi 12 adımda, ikili problemi 66 adımda karara bağlanıyor, alt küme toplamı ise 10.000 adım bütçesi gerektiriyor. Girdi boyu 8'den 20'ye çıkarken ilk iki yordamın en kötü adımı 8'den 20'ye ve 28'den 190'a giderken üçüncüsü 256'dan 1.048.576'ya çıkıyor. Karar problemi sınıfının, Algoritmalar kursundaki büyüme sınıfından farkı ayrıca yazılıyor. Hesaplama Modelleri konusu, bir sorunun yanıtlanıp yanıtlanamayacağını sordu ve sonlu bir bütçenin o soruyu her zaman kapatamadığını ölçtü. Karmaşıklık Sınıfları konusu daha dar bir alanda çalışır: yanıtı **bulunabilen** problemler arasında, bulmanın **bedelinin** girdiyle nasıl büyüdüğünü sorar. İlk soru şudur: bir problemi ucuz kılan nedir ve ucuzluk problemin özelliği midir yoksa seçilen yordamın mı. Bu ders üç karar problemini aynı girdi üzerinde aynı bütçeyle koşturur. İki tanesi bütçeyi neredeyse hiç zorlamıyor, üçüncüsü bütçeyi büyütmeyi gerektiriyor. Ölçülen şey hangisinin "hızlı" olduğu değil, **bütçenin hangisini karara bağladığıdır**. - **KS1.** Bu konudaki bütün problemler **karar problemidir**: yanıt tek bir sözcüktür, "evet" ya da "hayır". Karar problemi kavramı M01/K07 İleri Algoritmalar kursunda kuruldu ve burada tekrarlanmaz. - **KS2.** Girdi boyu **n**, örnekteki sayı adedidir. Sayılar 3 ile 99 arasında tutulur, yani bir sayının basamak sayısı sabittir ve girdi büyüklüğü yalnız n ile değişir. - **KS3.** Ölçü **adımdır**, süre değil. Bir adımın ne olduğu her yordamda ayrıca tanımlanır ve o tanım ders boyunca değişmez. - **KS4.** **Bütçe** bir adım bütçesidir. Yordam bütçeyi tüketirse yanıt vermez; "karara bağlanmadı" döner. Bu, yanıtın olmadığı anlamına gelmez, **bu bütçede kurulamadığı** anlamına gelir. - **KS5.** Örnekler ortak tanımın üretecinden gelir: tohum **20260218**, 20 örnek, örnek başına **12 sayı**. Bu kursta **ikinci tohum yoktur**; yerine bütçe süpürmesi vardır. - **KS6.** Üç problem şunlardır. **Eşik:** sayıların toplamı hedefi aşıyor mu. **İkili:** iki sayının toplamı hedefe tam eşit mi. **Alt küme toplamı:** herhangi bir alt kümenin toplamı hedefe tam eşit mi. - **KS7.** **Bütçe süpürmesi zorunludur.** Her sonuç en az üç bütçe değerinde gösterilir ve bütçeyle değişip değişmediği yazılır. - **KS8.** Bir yordamın **gözlenen** adımı ile **en kötü durumdaki** adımı ayrı yazılır. İkisini karıştırmak bu dersin ölçtüğü farkı yok eder. - **KS9.** Bir problemin P sınıfına ait olup olmadığı **ölçülmez**. Ölçülen tek şey, belirli bir yordamın adım sayısının girdi büyüklüğüyle nasıl büyüdüğüdür. - **KS10.** Sabit çarpanlar elenmez. Ölçüm asimptotik değil, **sayılan adımdır**. #### Karar Problemi Sınıfı ile Büyüme Sınıfı M01/K04 Algoritmalar kursundaki "Karmaşıklık Sınıflarını Okumak" dersi de "karmaşıklık sınıfı" terimini kullanıyordu, ama ayrı bir şeyi adlandırıyordu. Fark tek bir cümleyle yazılabilir: **orada bir sınıf tek bir yordamın maliyet ifadesini gruplar** — $O(n^2)$, iç içe iki döngünün büyüme biçimidir — **burada bir sınıf, hakkında yordam aranan problemleri gruplar.** Ayrımın pratik sonucu şudur. Bir yordam her zaman bir büyüme sınıfına aittir; bu, koda bakılarak belirlenir. Bir **problem** ise ancak "böyle bir yordamın var olduğu" gösterilerek bir karar problemi sınıfına sokulabilir ve bu bir varlık iddiasıdır. Kod ölçülür, varlık iddiası ölçülmez. **P**, bir karar problemi sınıfıdır: girdi büyüklüğünün bir polinomuyla sınırlı adımda **kesin** yanıt veren belirlenimci bir yordamın bulunduğu problemler. Tanımdaki üç sözcük de yüklüdür. "Polinom" bir büyüme sınırıdır; "kesin" yaklaşık çözümü dışarıda bırakır; "bulunduğu" bir varlık iddiasıdır ve tek bir koşumla kurulamaz. #### Üç Karar Problemi, Bir Adım Bütçesi Aşağıdaki blok üç problemi aynı 20 örnek üzerinde koşturur. Her yordam bir adım bütçesi alır ve bütçe dolduğunda `None` döndürerek karara varamadığını bildirir. ```python TOHUM = 20260218 def ornekler(tohum=TOHUM, n=12, sayi=20): """Ortak tanimin ornek ureteci: her ornek n sayi ve bir hedef.""" 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 esik(sayilar, hedef, butce): """Toplam hedefi asiyor mu. Bir adim = bir toplama.""" toplam, adim = 0, 0 for s in sayilar: if adim >= butce: return None, adim toplam += s adim += 1 return toplam > hedef, adim def ikili(sayilar, hedef, butce): """Iki sayinin toplami hedefe esit mi. Bir adim = bir ikili.""" adim, n = 0, len(sayilar) for i in range(n): for j in range(i + 1, n): if adim >= butce: return None, adim adim += 1 if sayilar[i] + sayilar[j] == hedef: return True, adim return False, adim def alt_kume(sayilar, hedef, butce): """Bir alt kumenin toplami hedefe esit mi. Bir adim = bir alt kume.""" adim, n = 0, len(sayilar) for maske in range(1 << n): if adim >= butce: return None, adim adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim ORN = ornekler() print("butce yordam karara baglanan baglanmayan en cok adim") for b in (12, 100, 1000, 10000): for ad, f in (("esik ", esik), ("ikili ", ikili), ("alt kume", alt_kume)): cevap = ust = 0 for o in ORN: y, a = f(o["sayilar"], o["hedef"], b) if y is not None: cevap += 1 ust = max(ust, a) print(f"{b:5d} {ad} {cevap:15d} {20 - cevap:11d} {ust:11d}") ``` ``` butce yordam karara baglanan baglanmayan en cok adim 12 esik 20 0 12 12 ikili 0 20 0 12 alt kume 0 20 0 100 esik 20 0 12 100 ikili 20 0 66 100 alt kume 7 13 98 1000 esik 20 0 12 1000 ikili 20 0 66 1000 alt kume 19 1 354 10000 esik 20 0 12 10000 ikili 20 0 66 10000 alt kume 20 0 1047 ``` #### Bütçenin Yanıtladığı ve Yanıtlayamadığı Üç sayı yan yana konur. **Bütçe 12**: eşik problemi 20 örneğin 20'sini karara bağlıyor, öteki iki problem **hiçbirini**. **Bütçe 100**: ikili problemi de 20'de 20'ye çıkıyor ve en çok 66 adım harcıyor; alt küme toplamı **7 örnekte** kalıyor, 13 örnek karara bağlanmıyor. **Bütçe 10.000**: üçü de 20'de 20. Bütçe süpürmesinin okunması burada iki ayrı sonuç veriyor. Eşik ve ikili problemleri için bütçeyi 100'den 10.000'e çıkarmak **hiçbir şeyi değiştirmiyor**: en çok adım 12 ve 66'da sabit kalıyor, çünkü bu iki yordam girdiyi zaten tüketmiş durumda. Alt küme toplamı için ise bütçe büyütmek **her şeyi değiştiriyor**: 7, sonra 19, sonra 20. Bu kursun ikinci iddiası tek bir tabloda iki kez görünüyor. Sabit kalan sayıların anlamı, kalmayanlardan daha önemlidir. Eşik yordamının 12 adımı, girdide 12 sayı olduğu içindir; ikili yordamının 66 adımı, 12 sayının 66 ikilisi olduğu içindir. İkisi de **girdinin kendisinden** okunabilen sayılardır ve örneğe bakmadan önceden yazılabilir. Alt küme toplamının 98, 354, 1047 adımları ise önceden yazılamaz; hangi maskede duracağı örneğe bağlıdır. #### Girdi Boyu Büyüyünce Bir bütçe değerinde alınan sonuç, girdi büyüklüğü değiştiğinde ayakta kalmayabilir. İkinci süpürme girdi büyüklüğünu 8'den 20'ye çıkarır ve her yordam için **en kötü durumdaki** adım sayısını gözlenen en yüksek adımın yanına koyar. ```python 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 alt_kume(sayilar, hedef): """Butun alt kumeler; ilk uyanda durur. Bir adim = bir alt kume.""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim print(" n esik ikili alt kume (en kotu) alt kume (gozlenen en cok)") for n in (8, 12, 16, 20): ust = max(alt_kume(o["sayilar"], o["hedef"])[1] for o in ornekler(n=n)) print(f"{n:2d} {n:4d} {n * (n - 1) // 2:5d} {1 << n:18d} {ust:26d}") ``` ``` n esik ikili alt kume (en kotu) alt kume (gozlenen en cok) 8 8 28 256 256 12 12 66 4096 1047 16 16 120 65536 945 20 20 190 1048576 2684 ``` Eşik sütunu 8, 12, 16, 20; girdi büyüklüğüyle birebir. İkili sütunu 28, 66, 120, 190; girdi büyüklüğü iki buçuk katına çıkarken adım yaklaşık yedi katına çıkıyor, yani karesel bir artış. Alt küme sütununun en kötü durumu 256'dan **1.048.576**'ya gidiyor: her yeni sayı, taranacak alt küme sayısını ikiye katlıyor. Son sütun bir tuzağı açığa çıkarıyor. **Gözlenen** en yüksek adım 12 sayıda 1047, 16 sayıda 945, 20 sayıda 2684. Yani gözlenen değer girdi büyüklüğüyle düzenli artmıyor, hatta 12'den 16'ya inerken azalıyor. Bunun nedeni yordamın uyan ilk alt kümede durmasıdır; bu örneklerde uyan bir alt küme erken bulunuyor. Sekiz sayılık satırda gözlenen değer en kötü durumla **çakışıyor** — 256'ya 256 — çünkü o dağarcıkta hiçbir alt kümenin uymadığı bir örnek var ve orada tarama sonuna kadar gidiyor. Buradan çıkan kural şudur: **gözlenen adım, bir yordamın bedeli değildir.** Yirmi örnekte gözlenen en yüksek değerin 2684 olması, yirmi birinci örneğin 2684 adımda biteceğini söylemez. Bir yordamın bedelini yazmak, gözlenen bir sayıyı değil, **her girdi için geçerli bir sınırı** yazmaktır. #### Girdi Boyu Neyle Ölçülür P tanımındaki "polinom", **girdi büyüklüğünün** polinomudur. O halde girdi büyüklüğünün ne olduğu tanımın parçasıdır ve bu noktada dikkatsizlik sessiz bir hataya dönüşür. Alt küme toplamı için tam taramadan başka bir yordam daha vardır: erişilebilen toplamların tablosu tutulur ve her sayı tabloyu bir kez günceller. Bu yordam **n çarpı hedef** adım harcar, yani 12 sayı ve 180 hedef için yaklaşık 2160 adım — 4096'nın altında. Görünüşte polinom bir yordamdır. Aşağıdaki blok bu görünüşü sınar. Bütün sayılar ve hedef aynı çarpanla büyütülür; **sayı adedi değişmez**, yalnız her sayının basamak sayısı artar. ```python 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 tam_tarama(sayilar, hedef): """Bir adim = bir alt kume.""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def dinamik(sayilar, hedef): """Erisilen toplamlar tablosu. Bir adim = bir tablo hucresi.""" ulasilan = [False] * (hedef + 1) ulasilan[0] = True adim = 0 for s in sayilar: for t in range(hedef, s - 1, -1): adim += 1 if ulasilan[t - s]: ulasilan[t] = True return ulasilan[hedef], adim print("carpan basamak uyusan tam tarama adimi dinamik adimi") for c in (1, 10, 100): uyan, ta, da = 0, 0, 0 basamak = 0 for o in ornekler(): s = [x * c for x in o["sayilar"]] h = o["hedef"] * c basamak = max(basamak, len(str(h))) y1, a1 = tam_tarama(s, h) y2, a2 = dinamik(s, h) uyan += y1 == y2 ta, da = ta + a1, da + a2 print(f"{c:6d} {basamak:7d} {uyan:6d} {ta:16d} {da:13d}") ``` ``` carpan basamak uyusan tam tarama adimi dinamik adimi 1 3 20 4321 37994 10 4 20 4321 377780 100 5 20 4321 3775640 ``` İki yordam 20 örneğin 20'sinde aynı yanıtı veriyor, yani tablo yordamı doğru çalışıyor. Ama adım sütunları ters yönlere gidiyor. Sayılar on katına çıkarıldığında tam taramanın adımı **4321'de sabit** kalıyor; tablo yordamının adımı 37.994'ten 377.780'e, sonra 3.775.640'a çıkıyor. Girdiye eklenen şey **tek bir basamaktır** ve sayı adedi hiç değişmemiştir. Sonuç şudur: tablo yordamı, hedefin **değerinin** polinomudur, hedefi yazmak için gereken **basamak sayısının** değil. Bir sayıyı yazmak için gereken yer basamak sayısı kadardır, değeri kadar değil; bu yüzden girdi büyüklüğü bu yordam için üstel olarak büyür. Girdi boyu "sayı adedi" diye okunursa yordam polinom görünür, "yazılan basamak adedi" diye okunursa görünmez. Bu ders girdi büyüklüğünu KS2'de sabit basamakla tanımladığı için ilk satır dürüsttür; çarpan büyütüldüğünde o tanım bozulur ve tablo hemen bunu gösterir. #### P Sınıfı Ne Söyler, Ne Söylemez Yukarıdaki iki tablo eşik ve ikili problemlerini P sınıfına **sokmaz**. Sokan şey ölçüm değil, yordamın yapısıdır: eşik yordamı her girdide tam olarak n adım, ikili yordamı en çok n(n-1)/2 adım harcar ve bu iki sınır girdiye bakılmadan gösterilebilir. Ölçüm bu gösterimi **sınar**, yerine geçmez. Ters yön daha da katıdır. Alt küme toplamı probleminin 20 sayıda 1.048.576 adım istemesi, bu problemin P sınıfında **olmadığını göstermez**. Gösterdiği tek şey, **burada kurulan yordamın** bu kadar adım harcadığıdır. Aynı problem için başka bir yordam bulunmadığı ölçülmedi; yalnız bu derste kurulmadı. Bu kursun kuralı bunu bir cümleye bağlar: **bütçesi yazılmayan "çözülemez" iddiası ölçülmemiş sayılır.** Mühendislik karşılığı doğrudandır. Bir raporda "bu problem polinom zamanda çözülüyor" cümlesi, yanına **o polinomu** ve bir sınır gerekçesi ister. "Bizim yordamımız 20 örnekte 66 adımda bitiyor" cümlesi ise ölçülmüş, doğru ve çok daha zayıf bir iddiadır. İkisi aynı cümlede yazılmaz. #### Özet - Karar problemi sınıfı ile büyüme sınıfı ayrı şeylerdir: biri problemleri, öteki tek bir yordamın maliyet ifadesini gruplar. - Aynı 20 örnekte eşik problemi 12, ikili problemi 66 adımda karara bağlanıyor; alt küme toplamı 100 adım bütçesinde 20 örneğin yalnız 7'sini bağlıyor ve 10.000'de tamamlanıyor. - Bütçeyi 100'den 10.000'e çıkarmak ilk iki problemde hiçbir şeyi değiştirmiyor, üçüncüsünde yanıtlanan örnek sayısını 7'den 20'ye taşıyor. - Girdi boyu 8'den 20'ye çıkarken en kötü adım sayısı 8'den 20'ye, 28'den 190'a ve 256'dan 1.048.576'ya gidiyor. - Gözlenen adım bir yordamın bedeli değildir: 12 sayıda 1047 gözlenirken 16 sayıda 945 gözleniyor, çünkü yordam uyan ilk alt kümede duruyor. - Bir problemin P sınıfına ait olduğu ölçülerek gösterilmez; ölçüm yalnız gösterilmiş bir sınırı sınar. #### Sonraki Adım Alt küme toplamı probleminde tarama pahalıydı, ama tarama bitince elde bir şey daha kalıyordu: hedefe toplanan alt kümenin **kendisi**. O alt küme bir kez elde edildiğinde, doğru olduğunu görmek için taramayı yeniden yapmak gerekmiyor. Sonraki ders bu gözlemi ölçüye çevirir: bir yanıtı **bulmak** ile verilmiş bir yanıtı **doğrulamak** arasındaki adım farkı ne kadar ve bu farkın bir sınıf adı olması ne anlama geliyor. ### NP Sınıfı Source: https://academia.sh/tr/kurslar/hesaplama-kurami/np-sinifi Doğrulanabilirlik ve sertifika kavramının adım sayısıyla kurulması: 20 örnekte çözme 4321, sertifika doğrulama 101 adım harcıyor ve oran 42,8. Adım bütçesi 13'te sertifikayla 20 örneğin 20'si karara bağlanırken çözerek hiçbiri bağlanmıyor. Girdi boyu 24'te çözmenin en kötüsü 16.777.216, doğrulama 25 adım. Bir indisi düşürülmüş sertifika 20 örneğin 20'sinde reddediliyor. Sertifika teriminin Kriptografi müfredatındaki sayısal sertifika duyusundan farkı ayrıca yazılıyor. Önceki ders alt küme toplamı problemini 12 sayıda 1047 adıma kadar taradı ve tarama bitince elde bir şey daha kaldı: hedefe toplanan alt kümenin **kendisi**. O alt küme bir kez yazıldıktan sonra doğruluğunu görmek için taramayı yeniden yapmak gerekmiyor; birkaç toplama yetiyor. Bu ders o gözlemi ölçüye çevirir. Ölçülen fark bir hız farkı değil, **iki ayrı soruya verilen iki ayrı bedeldir**. Birinci soru: hedefe toplanan bir alt küme var mı. İkinci soru: **verilen** şu alt küme hedefe toplanıyor mu. İkinci soruyu yanıtlayan yordam hiçbir arama yapmaz; yalnız bakar. - **KS11.** **Sertifika**, bir "evet" yanıtını doğrulanabilir kılan tanıktır. Burada bir indis listesidir: hangi sayıların alındığı. - **KS12.** **Hakem**, sertifikayı alıp "evet" yanıtını sınayan yordamdır. Hakem **arama yapmaz**; bu, bu dersin en katı kısıtıdır. Arama yapan bir hakem çözücüdür. - **KS13.** Bir adım, hakem için **bir indis okumasıdır**; son karşılaştırma da bir adım sayılır. Çözücü için bir adım, **bir alt kümedir**. - **KS14.** Sertifikanın **uzunluğu** ölçülür. Girdi boyuyla orantılı kalmayan bir sertifika, doğrulamayı ucuzlatmaz. - **KS15.** Hakem yalnız kabul etmekle değil, **reddetmekle** de sınanır: bozulmuş bir sertifika verildiğinde ne dediği sayılır. - **KS16.** Sertifika "hayır" yanıtı için tanımlı değildir. Bu dersin ölçtüğü tek yön **evet** yönüdür; öteki yön `04`'e aittir. - **KS17.** Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. - **KS18.** Örnekler ortak tanımın üretecinden, tohum **20260218**, 20 örnek, örnek başına 12 sayı. İkinci tohum yoktur. - **KS19.** Bir problemin NP sınıfına ait olup olmadığı **ölçülmez**. Ölçülen şey, belirli bir hakemin belirli bir sertifikayı kaç adımda sınadığıdır. #### Sertifika Hangi Anlamda Kullanılıyor Aynı sözcük M24 Kriptografi müfredatında da geçer ve orada başka bir şeyi adlandırır. Fark tek bir cümleyle yazılır: **orada sertifika, bir kimliği bir açık anahtara bağlayan imzalı bir belgedir; burada sertifika, bir karar probleminin "evet" yanıtını kısa adımda sınanabilir kılan tanıktır.** İkisinin ortak yanı yalnız "kendisi üretilmeden de doğrulanabilir" olmalarıdır; ötesinde ilişkileri yoktur ve aynı cümlede kullanılmazlar. **NP**, bir karar problemi sınıfıdır: "evet" yanıtı, girdi büyüklüğünün bir polinomu uzunluğunda bir sertifikayla ve yine polinom adımda **doğrulanabilen** problemler. Tanımda "çözmek" geçmez. Bu yüzden NP, "polinom zamanda çözülemeyen" demek **değildir**; adın açılımı da bunu söylemez. P sınıfındaki her problem NP sınıfındadır: bir problemi polinom adımda çözebilen bir yordam varsa, hakem sertifikayı hiç okumadan problemi baştan çözer ve yanıtı verir. Ters yönün doğru olup olmadığı bu kursun `05` dersinin konusudur ve **açıktır**. #### Çözmek ile Doğrulamak Aşağıdaki blok her örnekte önce çözücüyü koşturur, çözücünün ürettiği sertifikayı alır ve hakeme verir. Sonra aynı sertifikanın bir indisi düşürülüp hakeme yeniden verilir. ```python 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 cozucu(sayilar, hedef): """Butun alt kumeler taranir. Doner: (var_mi, adim, sertifika).""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim, [i for i in range(n) if maske >> i & 1] return False, adim, None def hakem(sayilar, hedef, sertifika): """Verilen sertifikayi dogrular; hicbir arama yapmaz. Bir adim = bir indis okumasi.""" adim, toplam = 0, 0 for i in sertifika: adim += 1 toplam += sayilar[i] return toplam == hedef, adim + 1 KAYIT = [] for o in ornekler(): var, adim, sert = cozucu(o["sayilar"], o["hedef"]) ok, da = hakem(o["sayilar"], o["hedef"], sert) KAYIT.append({"ornek": o, "var": var, "cozme": adim, "sertifika": sert, "dogrulama": da, "gecerli": ok}) tc = sum(k["cozme"] for k in KAYIT) td = sum(k["dogrulama"] for k in KAYIT) print("20 ornek , n=12 | evet yaniti:", sum(1 for k in KAYIT if k["var"]), "/ 20") print(" hakem sertifikayi onayladi:", sum(1 for k in KAYIT if k["gecerli"]), "/ 20") print(" cozme adimi:", tc, "| dogrulama adimi:", td, "| oran:", round(tc / td, 1)) print(" en uzun sertifika:", max(len(k["sertifika"]) for k in KAYIT), "indis") print() print("butce cozerek kurulan sertifikayla kurulan") for b in (13, 100, 1000, 10000): c1 = sum(1 for k in KAYIT if k["cozme"] <= b) c2 = sum(1 for k in KAYIT if k["dogrulama"] <= b) print(f"{b:5d} {c1:14d} {c2:21d}") print() ret, ra = 0, 0 for k in KAYIT: s = k["sertifika"] kirpik = s[:-1] if len(s) > 1 else s + [0] ok, a = hakem(k["ornek"]["sayilar"], k["ornek"]["hedef"], kirpik) ra += a ret += not ok print("bir indisi dusurulmus sertifika | reddedilen:", ret, "/ 20", "| toplam adim:", ra) ``` ``` 20 ornek , n=12 | evet yaniti: 20 / 20 hakem sertifikayi onayladi: 20 / 20 cozme adimi: 4321 | dogrulama adimi: 101 | oran: 42.8 en uzun sertifika: 5 indis butce cozerek kurulan sertifikayla kurulan 13 0 20 100 7 20 1000 19 20 10000 20 20 bir indisi dusurulmus sertifika | reddedilen: 20 / 20 | toplam adim: 81 ``` #### Üç Sayının Okunması **Bütçe 13**: sertifikayla 20 örneğin 20'si karara bağlanıyor, çözerek **hiçbiri**. Bütçe 100'de çözme 7'ye, 1000'de 19'a, 10.000'de 20'ye çıkıyor. Sertifika sütunu ise **hiç değişmiyor**: en küçük bütçede zaten doldu ve büyütmek eklenecek bir şey bulamadı. Bu kursun ikinci iddiasının en temiz görünümü budur — bütçeyi büyütmek bir sütunda her şeyi, ötekinde hiçbir şeyi değiştiriyor. Toplamlar aynı şeyi söylüyor: çözme **4321**, doğrulama **101** adım, oran **42,8**. Sertifika uzunluğu en çok **5 indis**; girdide 12 sayı var, yani sertifika girdiden kısa. Uzunluğun ölçülmesi biçimsel bir titizlik değil: hakemin adım sayısı sertifikanın uzunluğuna bağlıdır ve girdiden uzun bir sertifikaya izin verilirse doğrulamanın ucuzluğu kendiliğinden yok olur. Dördüncü sayı hakemin ciddiyetini gösteriyor. Sertifikadan bir indis düşürüldüğünde 20 örneğin **20'sinde** hakem reddediyor ve bunu toplam **81 adımda** yapıyor. Reddetmek, kabul etmekten daha ucuza gelmiyor ama daha pahalıya da gelmiyor; hakem her iki durumda da yalnız bakıyor. Bu ölçüm olmadan "doğrulama ucuzdur" cümlesi eksik kalırdı: her sertifikayı onaylayan bir yordam da ucuzdur ve hiçbir işe yaramaz. #### Sertifikanın Kısalığı Neden Tanımın Parçası NP tanımı sertifikanın **polinom uzunlukta** olmasını ister. Bu koşul kaldırılırsa tanım boşalır ve bu ölçülebilir. Aşağıdaki blok aynı problem için üç ayrı sertifika tasarımını yan yana koyar: indis listesi, yalnızca "evet" sözcüğü ve bütün alt küme toplamlarının listesi. ```python 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 kisa_sertifika(sayilar, hedef): """Indis listesi. Uzunluk en cok n.""" n = len(sayilar) for maske in range(1 << n): if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return [i for i in range(n) if maske >> i & 1] return [] def kisa_hakem(sayilar, hedef, sertifika): adim, toplam = 0, 0 for i in sertifika: adim += 1 toplam += sayilar[i] return toplam == hedef, adim + 1 def bos_hakem(sayilar, hedef, sertifika): """Sertifika yalnizca 'evet' sozcugu; hakem aramak zorunda kalir.""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def uzun_sertifika(sayilar, hedef): """Butun alt kume toplamlari sirayla yazilir. Uzunluk 2^n.""" n = len(sayilar) return [sum(sayilar[i] for i in range(n) if m >> i & 1) for m in range(1 << n)] def uzun_hakem(sayilar, hedef, sertifika): adim = 0 for t in sertifika: adim += 1 if t == hedef: return True, adim return False, adim ORN = ornekler() print("sertifika uzunluk hakem adimi butce 13 butce 100 butce 10000") for ad, uret, hkm in (("indis listesi ", kisa_sertifika, kisa_hakem), ("yalniz 'evet' ", lambda s, h: [], bos_hakem), ("butun toplamlar", uzun_sertifika, uzun_hakem)): uz = ha = 0 b13 = b100 = b1e4 = 0 for o in ORN: sert = uret(o["sayilar"], o["hedef"]) ok, a = hkm(o["sayilar"], o["hedef"], sert) uz += len(sert) ha += a b13 += a <= 13 b100 += a <= 100 b1e4 += a <= 10000 print(f"{ad:15s} {uz:7d} {ha:11d} {b13:8d} {b100:9d} {b1e4:11d}") ``` ``` sertifika uzunluk hakem adimi butce 13 butce 100 butce 10000 indis listesi 81 101 20 20 20 yalniz 'evet' 0 4321 0 7 20 butun toplamlar 81920 4321 0 7 20 ``` Üç satır aynı yanıtı üretiyor ama üç ayrı iş yapıyor. İlk satırda toplam sertifika uzunluğu **81 indis** ve hakem **101 adım** harcıyor. İkinci satırda sertifika boş: hakem hiçbir tanık almadığı için baştan aramak zorunda ve **4321 adım** harcıyor; bu bir hakem değil, çözücüdür. Üçüncü satır daha sinsidir. Sertifika var, hatta çok var — toplam **81.920 sayı**, yani örnek başına 4096 — ve hakem gerçekten yalnız okuyor, aramıyor. Ama okuduğu şey girdiden üstel olarak uzun olduğu için adım sayısı yine **4321**. Bütçe sütunları farkı kapatıyor: bütçe 13'te yalnız ilk tasarım 20'de 20 veriyor, ötekiler sıfırda. Uzunluk sınırı olmasaydı her problem için "doğrulanabilir" bir tasarım kurulabilirdi ve NP bütün karar problemlerini içerirdi. **Tanımdaki kısalık koşulu, tanımı boş olmaktan kurtaran şeydir.** M01/K07 İleri Algoritmalar kursu bu farkı başka bir problemde çoktan ölçmüştü: Hamilton yolu dersinde bir aday yolu doğrulamak çizge başına 7 adım, yolu bulmak ortalama 61 adım tutuyordu ve on iki düğümde doğrulama 11 adımken yol olmadığını göstermek ortalama 11.601 adıma çıkıyordu. O ders farkı ölçüp adlandırmayı buraya bırakmıştı; adı **doğrulanabilirlik**, sınıfı **NP**'dir. #### Uçurum Girdi Boyuyla Ne Yapıyor Yirmi örnekteki 42,8 oranı tek bir girdi büyüklüğünde alınmış bir sayıdır. İkinci süpürme girdi boyunu değiştirir ve iki tarafın **en kötü durumdaki** adımını yan yana koyar. Bu tablo hiçbir örnek koşturmaz; iki sayıyı doğrudan hesaplar, çünkü ikisi de girdiye bakmadan yazılabilir. ```python print(" n cozme (en kotu) dogrulama (en kotu) oran") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {1 << n:15d} {n + 1:19d} {(1 << n) // (n + 1):9d}") ``` ``` n cozme (en kotu) dogrulama (en kotu) oran 8 256 9 28 12 4096 13 315 16 65536 17 3855 20 1048576 21 49932 24 16777216 25 671088 ``` Sol sütun her satırda ikiye katlanarak ilerliyor: 256, 4096, 65.536, 1.048.576, 16.777.216. Orta sütun birer birer artıyor: 9, 13, 17, 21, 25. Oran 28'den **671.088**'e çıkıyor. Girdi boyu üç katına çıkarken açıklık yirmi dört bin katına çıkıyor. Tablodaki sol sütun bir uyarı taşır. **16.777.216 sayısı, bu problemin bedeli değildir; buradaki çözücünün bedelidir.** Aynı problem için daha az adım harcayan bir yordam olup olmadığı burada ölçülmedi. Ölçülen tek şey, tam taramanın 24 sayıda kaç alt küme göreceğidir. Sağ sütun ise problemin kendisine daha yakındır: sertifika verildiğinde n+1 adım yeter ve bu sınır yordam seçiminden bağımsızdır. #### Doğrulanabilirlik Neyi Vaat Etmez Bir problemin NP sınıfında olması, o problemin ucuz olduğunu **söylemez**. NP, yalnız şunu söyler: doğru yanıt "evet" ise, bunu size gösterecek kısa bir tanık **vardır**. Tanığın nasıl bulunacağı hakkında hiçbir şey söylemez ve bu ders o bulmanın 4321 adım sürdüğünü ölçtü. Ayrım mühendislikte doğrudan karşılık bulur. Bir sistemde bir yerleşim planının, bir çizelgenin ya da bir yapılandırmanın **geçerli** olduğunu sınamak çoğu zaman ucuzdur ve ölçülebilir. Aynı planı **üretmek** bambaşka bir iştir. Bir raporda "doğrulama 13 adım" ile "üretim 4096 adım" sayıları yan yana yazılmadıkça, "sistem planı doğruluyor" cümlesi hangi işin yapıldığını söylemez. Sınıfın adı da bir uyarı taşır. NP, "belirlenimci olmayan polinom zaman" ifadesinin kısaltmasıdır ve buradaki belirlenimsizlik bir makine tasarımına değil, **tanığın verilmiş sayılmasına** karşılık gelir. Sınıfın adını "polinom değil" diye okumak yaygın bir yanlıştır ve bu dersin ölçtüğü her sayıyı ters çevirir: P sınıfındaki eşik problemi de NP sınıfındadır, çünkü hakem sertifikaya hiç bakmadan 13 adımda yanıtı kurar. Son bir sınır: bu derste ölçülen hiçbir sayı, alt küme toplamı probleminin NP sınıfında olduğunu **kanıtlamaz**. Kanıtlayan şey, hakemin yapısıdır — sertifika en çok n indis taşır ve hakem en çok n+1 adım harcar, her girdide. Ölçüm bu yapıyı sınadı ve 20 örnekte tutarlı buldu; bu bir sınamadır, kanıtın yerine geçmez. #### Özet - Sertifika, bir "evet" yanıtını arama yapmadan sınanabilir kılan tanıktır; hakem sertifikayı okur, aramaz. - Aynı 20 örnekte çözme 4321, doğrulama 101 adım harcıyor ve oran 42,8; en uzun sertifika 5 indis, girdi ise 12 sayı. - Adım bütçesi 13'te sertifikayla 20 örneğin 20'si karara bağlanıyor, çözerek hiçbiri; bütçeyi 10.000'e çıkarmak sertifika sütununda hiçbir şeyi değiştirmiyor. - Bir indisi düşürülmüş sertifika 20 örneğin 20'sinde reddediliyor; hakem kabul ettiği kadar reddetmekle de sınanır. - Girdi boyu 8'den 24'e çıkarken çözmenin en kötüsü 256'dan 16.777.216'ya, doğrulama 9'dan 25'e gidiyor ve oran 671.088'e çıkıyor. - NP sınıfında olmak ucuzluk vaat etmez; yalnız "evet" yanıtının kısa bir tanığı olduğunu söyler ve tanığın nasıl bulunacağı hakkında hiçbir şey söylemez. #### Sonraki Adım Bu derste tek bir problem ölçüldü. Ama zorluk hakkında söylenen çoğu cümle tek bir problem hakkında değildir: "şu problem en az şu kadar zor" biçiminde, iki problemi karşılaştıran bir cümledir. Sonraki ders bu karşılaştırmanın nasıl kurulduğunu sayar: bir problemi bir başkasına çeviren dönüşümün kaç adım tuttuğunu, dönüşümün yanıtı koruyup korumadığını ve çevirinin neden zorluğu **taşıdığını** ama **azaltmadığını**. ### NP-Tam ve NP-Zor Source: https://academia.sh/tr/kurslar/hesaplama-kurami/np-tam-ve-np-zor İndirgeme yoluyla zorluk aktarımının adım sayısıyla ölçülmesi: alt küme toplamı örneğini bölüştürme örneğine çeviren dönüşüm 15 adım tutuyor, kaynağı çözmenin 0,2632'si. Yirmi örnekte indirgeme 300, kaynağı çözme 4321, hedefi çözme 19.847 adım ve 20 örneğin 20'sinde iki yanıt uyuşuyor. Girdi boyu 24'te indirgeme 27 adımda kalırken çözme 16.777.216 adıma çıkıyor. Çevirinin yönünün neyi kanıtlayıp neyi kanıtlamadığı ayrıca yazılıyor. Önceki ders tek bir problem ölçtü. Ama zorluk hakkında söylenen cümlelerin çoğu tek bir problem hakkında değildir: "şu problem en az şu kadar zor" biçiminde, iki problemi karşılaştıran bir cümledir. Böyle bir cümle nasıl kurulur ve bedeli nedir. Araç, M01/K07 İleri Algoritmalar kursunda tanıtılan **indirgemedir**: bir problemin örneğini, başka bir problemin örneğine çeviren dönüşüm. O kursta indirgeme bir çözüm tekniğiydi — tanıdık bir kalıba çevirip kalıbın yordamını kullanmak. Burada aynı dönüşüm başka bir iş için kullanılır: **bir problemin zorluğunu bir başkasına aktarmak.** Yordam tekrarlanmaz; sayıya çevrilir. - **KS20.** **Kaynak problem** alt küme toplamıdır: bir alt kümenin toplamı hedefe eşit mi. **Hedef problem** bölüştürmedir: sayılar, toplamları eşit iki paya ayrılabilir mi. - **KS21.** **İndirgeme**, kaynağın bir örneğini hedefin bir örneğine çeviren yordamdır ve yanıtı **korumak zorundadır**: kaynak "evet" ise hedef de "evet", kaynak "hayır" ise hedef de "hayır" vermelidir. - **KS22.** İndirgemede bir adım, **bir eleman kopyalamasıdır**; toplam alma ve eklenen elemanın hesabı için üç adım daha sayılır. - **KS23.** İndirgemenin doğruluğu **varsayılmaz, sınanır**: 20 örneğin her birinde iki yanıt karşılaştırılır ve uyuşan örnek sayısı yazılır. - **KS24.** Üç adım sayısı ayrı tutulur: **indirgeme**, **kaynağı çözme**, **hedefi çözme**. İkincisi ile üçüncüsü karıştırılırsa indirgemenin ne yaptığı görünmez olur. - **KS25.** İndirgemenin **yönü** yazılır. Kaynaktan hedefe indirgeme, **hedef en az kaynak kadar zordur** der; ters yönü söylemez. - **KS26.** Bütçe süpürmesi dört değerde yapılır: 15, 100, 1000, 10.000 adım. - **KS27.** Örnekler ortak tanımın üretecinden, tohum **20260218**, 20 örnek, örnek başına 12 sayı. İkinci tohum yoktur. - **KS28.** Hiçbir problemin NP-tam olduğu **koşumla gösterilmez**. Koşum yalnız tek bir indirgemenin adımını ve doğruluğunu ölçer. #### Zorluğu Aktarmak Ne Demek İndirgemenin okunma biçimi ters sezgiseldir ve yanlış okunması yaygındır. Kaynak problemin bir örneği hedef problemin bir örneğine çevriliyorsa, **hedefi çözebilen her yordam kaynağı da çözebilir**: önce çevir, sonra hedefi çöz, yanıtı olduğu gibi al. Bunun sonucu şudur — hedef problem için ucuz bir yordam bulunursa, kaynak problem için de ucuz bir yordam olurdu. Buradan çıkan cümle **hedef hakkındadır**: hedef, kaynaktan **daha kolay olamaz**. Çeviri kaynağı ucuzlatmaz; hedefin ucuzlama ihtimalini kaynağa bağlar. Yön karıştırılırsa cümle tersine döner ve hiçbir şey söylemez hale gelir. İki sınıf adı bu okumanın üzerine kurulur. Bir problem, **NP sınıfındaki her problem ona indirgenebiliyorsa** NP-zordur. Bir problem hem **NP-zor** hem de **NP sınıfındaysa**, yani kendi "evet" yanıtının kısa bir sertifikası varsa, **NP-tamdır**. Fark tek bir koşuldadır: NP-zor bir problem NP sınıfında olmak zorunda değildir, hatta bir karar problemi olmak zorunda bile değildir. #### Bir İndirgemenin Ölçülmesi Aşağıdaki dönüşüm şunu yapar: sayıların toplamı $T$, hedef $h$ olsun; listeye tek bir yeni eleman eklenir. Bu eleman, toplamın iki eşit paya bölünebilmesini ancak kaynakta $h$'ye toplanan bir alt küme varsa mümkün kılacak biçimde seçilir. Dönüşümün yanıtı koruyup korumadığı varsayılmaz; her örnekte sınanır. ```python 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 alt_kume_hakem(sayilar, hedef): """Kaynak problem: bir alt kumenin toplami hedefe esit mi.""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def indirge(sayilar, hedef): """Alt kume toplami ornegini iki esit paya bolusturme ornegine cevirir. Bir adim = bir eleman kopyalamasi; uc adim da toplam ve ek eleman icin.""" toplam = sum(sayilar) yeni = list(sayilar) + [2 * hedef - toplam] if 2 * hedef >= toplam else \ list(sayilar) + [toplam - 2 * hedef] return yeni, len(sayilar) + 3 def bolusturme_hakem(sayilar): """Hedef problem: sayilar iki esit toplamli paya bolunebilir mi.""" toplam = sum(sayilar) if toplam % 2: return False, 1 var, adim = alt_kume_hakem(sayilar, toplam // 2) return var, adim + 1 ORN = ornekler() uyusan, ia, ka, ha = 0, 0, 0, 0 for o in ORN: var1, a1 = alt_kume_hakem(o["sayilar"], o["hedef"]) yeni, ad = indirge(o["sayilar"], o["hedef"]) var2, a2 = bolusturme_hakem(yeni) uyusan += var1 == var2 ia, ka, ha = ia + ad, ka + a1, ha + a2 print("20 ornek , n=12 | yaniti uyusan:", uyusan, "/ 20") print(" indirgeme:", ia, "adim | kaynagi cozme:", ka, "adim | hedefi cozme:", ha, "adim") print(" indirgemenin kaynagi cozmeye orani:", round(ia / ka, 4)) print() o = ORN[0] yeni, ad = indirge(o["sayilar"], o["hedef"]) var1, a1 = alt_kume_hakem(o["sayilar"], o["hedef"]) var2, a2 = bolusturme_hakem(yeni) print("ilk ornek | indirgeme", ad, "adim | kaynak yanit", var1, f"({a1} adim)", "| hedef yanit", var2, f"({a2} adim)") print(" oran:", round(ad / a1, 4)) print() print("butce indirgenen kaynagi cozulen hedefi cozulen") for b in (15, 100, 1000, 10000): i1 = sum(1 for x in ORN if indirge(x["sayilar"], x["hedef"])[1] <= b) k1 = sum(1 for x in ORN if alt_kume_hakem(x["sayilar"], x["hedef"])[1] <= b) h1 = sum(1 for x in ORN if bolusturme_hakem(indirge(x["sayilar"], x["hedef"])[0])[1] <= b) print(f"{b:5d} {i1:10d} {k1:15d} {h1:14d}") ``` ``` 20 ornek , n=12 | yaniti uyusan: 20 / 20 indirgeme: 300 adim | kaynagi cozme: 4321 adim | hedefi cozme: 19847 adim indirgemenin kaynagi cozmeye orani: 0.0694 ilk ornek | indirgeme 15 adim | kaynak yanit True (57 adim) | hedef yanit True (288 adim) oran: 0.2632 butce indirgenen kaynagi cozulen hedefi cozulen 15 20 0 0 100 20 7 0 1000 20 19 12 10000 20 20 20 ``` #### İndirgeme Ucuz, Çözme Değil İlk örnek üç sayıyı yan yana koyuyor: **indirgeme 15 adım**, **kaynağı çözme 57 adım**, **hedefi çözme 288 adım**. İndirgeme, kaynağı çözmenin **0,2632**'si kadar. Yirmi örneğin toplamında oran daha da düşüyor: 300'e karşı 4321, yani **0,0694**. İkinci sayı çifti daha öğreticidir. Hedefi çözmek **19.847 adım** tutuyor, kaynağı çözmenin neredeyse beş katı. Çeviri hiçbir şeyi ucuzlatmadı; tersine, listeye bir eleman eklediği için hedef örnek kaynaktan **daha pahalı** hale geldi. İndirgemenin işi ucuzlatmak değildir. İşi, iki problemin zorluğu arasında bir **bağ** kurmaktır ve bu bağ kurulurken hesap ucuza gelir. Doğruluk sütunu bu bağın ön koşuludur: 20 örneğin **20'sinde** iki yanıt uyuşuyor. Uyuşmasaydı indirgeme geçersiz olurdu ve adım sayısının hiçbir anlamı kalmazdı. Yirmi örnekte uyuşması ise dönüşümün her girdide doğru olduğunu **kanıtlamaz**; dönüşümün doğruluğu, eklenen elemanın seçiminden gelen bir gerekçedir ve ölçüm o gerekçeyi yalnız sınar. Bütçe süpürmesi üç sütunda üç ayrı davranış gösteriyor. **İndirgeme sütunu bütçe 15'te dolu** ve 10.000'de hâlâ 20; bütçeyi büyütmek hiçbir şey eklemiyor. Kaynağı çözme 0'dan 7'ye, 19'a, 20'ye çıkıyor. Hedefi çözme daha geç açılıyor: 1000'de yalnız 12, 10.000'de 20. Aynı bütçe, çevrilmiş örnek için daha az yetiyor. #### Girdi Boyu Büyüdüğünde Ne Kalıyor Tek bir girdi büyüklüğünde alınan 0,2632 oranı, indirgemenin ucuzluğunu tam olarak anlatmaz. Asıl soru, girdi büyüklüğü büyüdüğünde iki tarafın **birbirine göre** ne yaptığıdır. ```python print(" n indirgeme kaynagi cozme hedefi cozme indirgeme/cozme") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {n + 3:9d} {1 << n:13d} {1 << (n + 1):12d}" f" {(n + 3) / (1 << n):15.6f}") ``` ``` n indirgeme kaynagi cozme hedefi cozme indirgeme/cozme 8 11 256 512 0.042969 12 15 4096 8192 0.003662 16 19 65536 131072 0.000290 20 23 1048576 2097152 0.000022 24 27 16777216 33554432 0.000002 ``` İndirgeme sütunu 11, 15, 19, 23, 27: girdi büyüklüğüyle birer birer, düz. Çözme sütunları her satırda ikiye katlanıyor. Oran 0,042969'dan **0,000002**'ye iniyor. Girdi boyu üç katına çıkarken indirgemenin payı yirmi bin kat küçülüyor. Bu tablonun taşıdığı sonuç şudur: **indirgemenin bedeli, aktardığı zorluğun yanında yok sayılabilir hale geliyor.** Bir problemin zor olduğu biliniyorsa ve o problem ucuz bir dönüşümle başka bir probleme çevrilebiliyorsa, ikinci problem hakkında söylenecek söz birinciden gelir. Zorluk taşınabilir bir şeydir ve taşıma masrafı düşüktür. #### Yanlış Bir Çevirim Nasıl Görünür İndirgemenin ucuzluğu tek başına bir erdem değildir. Daha ucuz ama **yanıtı korumayan** bir çevirim her zaman kurulabilir ve ucuzluğuna bakarak ayırt edilemez. Aşağıdaki blok doğru çevirimin yanına, hedefi düpedüz atan bir çevirimi koyar. Üçüncü ölçüm ters yöndedir: bölüştürme örneği alt küme toplamı örneğine çevrilir. ```python 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 alt_kume_hakem(sayilar, hedef): adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def bolusturme_hakem(sayilar): toplam = sum(sayilar) if toplam % 2: return False, 1 var, adim = alt_kume_hakem(sayilar, toplam // 2) return var, adim + 1 def dogru_indirge(sayilar, hedef): """Yaniti koruyan cevirim: tek bir denklestirici eleman eklenir.""" toplam = sum(sayilar) ek = 2 * hedef - toplam if 2 * hedef >= toplam else toplam - 2 * hedef return list(sayilar) + [ek], len(sayilar) + 3 def naif_indirge(sayilar, hedef): """Hedefi atan cevirim: liste oldugu gibi bolusturmeye verilir.""" return list(sayilar), len(sayilar) def ters_indirge(sayilar): """Bolusturme ornegini alt kume toplami ornegine cevirir.""" toplam = sum(sayilar) return list(sayilar), toplam // 2, len(sayilar) + 1 print("cevirim uyusan ayrilan cevirim adimi") for ad, f in (("dogru", dogru_indirge), ("naif ", naif_indirge)): uyusan = ayrilan = ca = 0 for o in ornekler(): k, _ = alt_kume_hakem(o["sayilar"], o["hedef"]) yeni, adim = f(o["sayilar"], o["hedef"]) h, _ = bolusturme_hakem(yeni) ca += adim if k == h: uyusan += 1 else: ayrilan += 1 print(f"{ad:13s} {uyusan:6d} {ayrilan:7d} {ca:13d}") print() uyusan, ta, ha = 0, 0, 0 for o in ornekler(): yeni, _ = dogru_indirge(o["sayilar"], o["hedef"]) h, a1 = bolusturme_hakem(yeni) s, hedef2, adim = ters_indirge(yeni) k, a2 = alt_kume_hakem(s, hedef2) uyusan += h == k ta, ha = ta + adim, ha + a2 print("ters yon (bolusturme -> alt kume toplami)") print(" uyusan:", uyusan, "/ 20 | cevirim adimi:", ta, "| hedefi cozme adimi:", ha) ``` ``` cevirim uyusan ayrilan cevirim adimi dogru 20 0 300 naif 8 12 240 ters yon (bolusturme -> alt kume toplami) uyusan: 20 / 20 | cevirim adimi: 280 | hedefi cozme adimi: 19827 ``` Naif çevirim **240 adım** harcıyor, doğrusundan **60 adım ucuz**. Ama 20 örneğin **12'sinde** yanlış yanıt veriyor. Yanıtı korumadığı için indirgeme değildir ve hiçbir zorluk aktarmaz. Sekiz örnekte doğru yanıt vermesi de bir savunma sayılmaz: bir dönüşüm ya her örnekte yanıtı korur ya da geçersizdir. **İndirgemede iş, adım sayısında değil, doğruluk gerekçesindedir.** Naif çevirimin nerede kırıldığı da okunabilir. Bölüştürme sorusu her zaman **toplamın yarısını** sorar; bu örneklerdeki hedef ise toplamın yaklaşık **üçte biridir**. Hedefi atmak, soruyu değiştirmek demektir ve değişen soru başka bir yanıt verir. Doğru çevirimin eklediği tek eleman tam olarak bu farkı kapatmak içindir: eklenen değer, yarıyı hedefin bulunduğu yere taşır. Ters yön daha kısa: bölüştürme örneği, hedefi toplamın yarısı olan bir alt küme toplamı örneğine **280 adımda** çevriliyor ve 20 örneğin 20'sinde yanıt korunuyor. İki yön birlikte okunduğunda ortaya çıkan sonuç şudur: bu iki problem birbirine **karşılıklı** olarak indirgeniyor, yani birinin ucuz bir yordamı ötekini de ucuzlatır. Zorluk açısından bu iki problem ayrılamaz. #### Koşumun Söylemediği Bu derste ölçülen hiçbir sayı, bölüştürme probleminin NP-tam olduğunu **göstermez**. Gösterilen tek şey, **bir** problemin ona indirgendiğidir. NP-zorluk tanımı, NP sınıfındaki **bütün** problemlerin indirgenebilmesini ister; bu, sonlu bir koşumun kapsayamayacağı bir niceleyicidir. Bu iki problemin NP-tam olduğu kuramın sonucudur ve buraya **kuramın sonucu olarak** girer; yukarıdaki tabloların hiçbiri onu kanıtlamaz. Ölçümün gerçekten kanıtladığı şey daha küçük ve daha somuttur: bu dönüşüm 20 örneğin 20'sinde yanıtı korudu, 15 adım tuttu ve girdi büyüklüğü büyüdükçe payı düştü. Bir raporda yazılabilecek cümle budur. "Bölüştürme NP-tamdır" cümlesi ise ölçüme değil, kaynağa dayanır ve kaynağı belirtilmeden yazılmaz. Ters yön de açıkça söylenmeli. Kaynaktan hedefe kurulan bir indirgeme, hedefin **en az** kaynak kadar zor olduğunu destekler. Hedefin **en fazla** ne kadar zor olduğu hakkında hiçbir şey söylemez ve kaynağın kolay olduğunu hiç söylemez. Bir yönde kurulmuş bir bağı iki yönde okumak, bu konudaki en sık hatadır. #### Özet - İndirgeme, bir problemin örneğini başka bir problemin örneğine çeviren ve **yanıtı koruyan** dönüşümdür; yön, hedefin kaynaktan daha kolay olamayacağını söyler. - İlk örnekte indirgeme 15, kaynağı çözme 57, hedefi çözme 288 adım; oran 0,2632. Yirmi örnekte 300'e karşı 4321 ve 19.847. - Çeviri hiçbir şeyi ucuzlatmıyor: hedef örnek bir eleman daha taşıdığı için kaynaktan beş kat pahalıya çözülüyor. - Yirmi örneğin 20'sinde iki yanıt uyuşuyor; bu bir sınamadır, dönüşümün her girdide doğru olduğunun kanıtı değildir. - Girdi boyu 8'den 24'e çıkarken indirgeme 11'den 27 adıma, çözme 256'dan 16.777.216 adıma gidiyor ve oran 0,000002'ye iniyor. - NP-zor, NP sınıfındaki her problemin indirgenebildiği problemdir; NP-tam ise buna ek olarak NP sınıfında olandır. Hiçbiri sonlu bir koşumla gösterilemez. #### Sonraki Adım Buraya kadar ölçülen her şey **evet** yönündeydi: sertifika bir "evet"i doğruluyordu, indirgeme bir "evet"i taşıyordu. Sonraki ders eksik yönü ölçer. Bir yanıt "hayır" olduğunda ne gösterilebilir ve gösterilecek şey aynı uzunlukta mı. Yirmi örnekte "evet" sertifikası 13 adımda kapanırken "hayır" kanıtının kaç adım istediği ve bazı "hayır" yanıtlarının neden ucuza kapandığı sayılacak. ### co-NP ve Sınıflar Arası İlişkiler Source: https://academia.sh/tr/kurslar/hesaplama-kurami/co-np-ve-siniflar-arasi-iliskiler Tümleyen problemlerin durumu ve evet ile hayır yanıtları arasındaki ölçülmüş asimetri: 20 örnekte evet sertifikası 101 adımda kapanırken hayır yanıtı tam tarama ile 81.920 adım istiyor. Yapılı hayır örneklerinde 260 adımlık kısa bir kanıt 20/20 çalışıyor, yapısız örneklerde aynı kanıt 20/20 hiçbir şey söyleyemiyor. Girdi boyu 24'te evet sertifikası 25, hayır kanıtı 16.777.216 adım. Eşik problemi iki yönde de 260 adımda kapanıyor. Buraya kadar ölçülen her şey **evet** yönündeydi: sertifika bir "evet"i doğruluyordu, indirgeme bir "evet"i taşıyordu. Bir yanıt "hayır" olduğunda ne gösterilebilir. Bu ders eksik yönü ölçer ve iki yönün simetrik olmadığını sayar. Sorunun kaynağı NP tanımının kendisindedir. Tanım yalnız "evet" yanıtı için bir tanık ister; "hayır" yanıtı için hiçbir şey vaat etmez. M01/K07 İleri Algoritmalar kursu bu asimetriyi Hamilton yolu dersinde çoktan gözlemişti: yol bulunmayan çizgelerin **hepsinde** karar yordamı sayma yordamının gezdiği ağacın tamamını gezmişti. O gözlem burada bir sınıf ayrımına dönüşür. - **KS29.** Bir karar probleminin **tümleyeni**, aynı girdide yanıtı ters çevrilmiş problemdir: "hedefe toplanan bir alt küme var mı" sorusunun tümleyeni "hiçbir alt küme hedefe toplanmıyor mu" sorusudur. - **KS30.** **co-NP**, tümleyeni NP sınıfında olan karar problemlerinin sınıfıdır. Eşdeğer okunuşu şudur: **"hayır" yanıtının kısa ve hızlı sınanabilir bir tanığı olan** problemler. - **KS31.** Üç örnek kümesi kurulur. **Evet kümesi:** ortak tanımın 20 örneği. **Yapılı hayır kümesi:** bütün sayılar ikiye katlanır, hedef tek yapılır. **Yapısız hayır kümesi:** aynı sayılar, hedef olarak erişilemeyen bir değer seçilir. - **KS32.** Yapısız kümenin hedefi seçilirken erişilen toplamlar tam olarak çıkarılır. Bu bir **kurulum adımıdır**, hakem değildir ve adımı ölçüme katılmaz. - **KS33.** **Kısa hayır kanıtı** yalnız bir gerek koşulu sınar: bütün sayılar çiftse toplamları da çifttir, dolayısıyla tek bir hedefe ulaşılamaz. Bu kanıt "hayır" diyebilir, "evet" diyemez; diyemediğinde **bilinmiyor** döner. - **KS34.** Bir adım, kısa kanıt için **bir sayı okumasıdır**; tam tarama için **bir alt kümedir**. - **KS35.** Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. - **KS36.** Örnekler ortak tanımın üretecinden, tohum **20260218**. İkinci tohum yoktur. - **KS37.** NP ile co-NP'nin eşit olup olmadığı **açık bir sorudur** ve bu derste yanıtlanmaz. Ölçüm yalnız belirli kanıtların belirli örneklerde çalışıp çalışmadığını sayar. #### Tümleyen Neden Ayrı Bir Soru Bir karar problemini çözen yordam, tümleyenini de çözer: yanıtı ters çevirmek bir adım bile tutmaz. Bu yüzden **çözülebilirlik** açısından bir problem ile tümleyeni arasında fark yoktur ve P sınıfı tümleyen almaya kapalıdır — P'deki bir problemin tümleyeni de P'dedir. Doğrulanabilirlik açısından durum başkadır. "Şu alt küme hedefe toplanıyor" tanığı, "hiçbir alt küme toplanmıyor" iddiasını desteklemez; tersine, o iddiayı çürütür. "Hiçbiri" demek için gösterilecek şeyin ne olduğu ayrı bir tasarım sorusudur ve her problem için bir yanıtı olduğu **bilinmez**. Bu yüzden NP ile co-NP ayrı adlar taşır. Alt küme toplamının NP sınıfında olduğu `02`'de gösterildi; co-NP sınıfında olup olmadığı gösterilmedi ve bu ders de göstermez. #### İki Yönün Ölçülmesi Aşağıdaki blok üç örnek kümesini aynı hakemle koşturur, sonra her kümede iki ayrı kısa kanıt dener: "evet" için sertifika, "hayır" için çift-tek gerek koşulu. ```python 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 hakem(sayilar, hedef): """Tam tarama. Doner: (var_mi, adim, sertifika).""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim, [i for i in range(n) if maske >> i & 1] return False, adim, None def evet_dogrula(sayilar, hedef, sertifika): """Bir adim = bir indis okumasi.""" adim, toplam = 0, 0 for i in sertifika: adim += 1 toplam += sayilar[i] return toplam == hedef, adim + 1 def hayir_dogrula(sayilar, hedef): """Tek yone calisan kisa kanit: butun sayilar cift ise toplamlari da cifttir , dolayisiyla tek bir hedefe ulasilamaz.""" adim = 0 for s in sayilar: adim += 1 if s % 2: return "bilinmiyor", adim adim += 1 return ("hayir", adim) if hedef % 2 else ("bilinmiyor", adim) def ulasilmayan(sayilar): """Kurulum adimi (hakem degil): erisilen toplamlar cikarilir ve ucte bire en yakin erisilmeyen deger secilir.""" ulasilan = {0} for x in sayilar: ulasilan |= {u + x for u in ulasilan} return min((t for t in range(1, sum(sayilar)) if t not in ulasilan), key=lambda t: abs(t - sum(sayilar) // 3)) ORN = ornekler() EVET = [(o["sayilar"], o["hedef"]) for o in ORN] YAPILI = [([2 * x for x in o["sayilar"]], 2 * o["hedef"] + 1) for o in ORN] YAPISIZ = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ORN] print("kume hakem yaniti tam tarama adimi") for ad, kume, bekle in (("evet ", EVET, True), ("yapili ", YAPILI, False), ("yapisiz", YAPISIZ, False)): top = sum(hakem(s, h)[1] for s, h in kume) uyan = sum(1 for s, h in kume if hakem(s, h)[0] == bekle) print(f"{ad} {uyan:2d}/20 beklenen {top:16d}") print() es = sum(evet_dogrula(s, h, hakem(s, h)[2])[1] for s, h in EVET) print("evet sertifikasi (20 ornek) dogrulama adimi:", es) for ad, kume in (("yapili ", YAPILI), ("yapisiz", YAPISIZ)): hy = sum(1 for s, h in kume if hayir_dogrula(s, h)[0] == "hayir") ha = sum(hayir_dogrula(s, h)[1] for s, h in kume) print(f"kisa hayir kaniti {ad} | 'hayir' diyebildigi: {hy:2d}/20 | adim: {ha}") print() print("butce evet sertifikasi yapili hayir kaniti yapisiz tam tarama") for b in (13, 100, 1000, 10000): a1 = sum(1 for s, h in EVET if evet_dogrula(s, h, hakem(s, h)[2])[1] <= b) a2 = sum(1 for s, h in YAPILI if hayir_dogrula(s, h)[0] == "hayir" and hayir_dogrula(s, h)[1] <= b) a3 = sum(1 for s, h in YAPISIZ if hakem(s, h)[1] <= b) print(f"{b:5d} {a1:16d} {a2:19d} {a3:19d}") ``` ``` kume hakem yaniti tam tarama adimi evet 20/20 beklenen 4321 yapili 20/20 beklenen 81920 yapisiz 20/20 beklenen 81920 evet sertifikasi (20 ornek) dogrulama adimi: 101 kisa hayir kaniti yapili | 'hayir' diyebildigi: 20/20 | adim: 260 kisa hayir kaniti yapisiz | 'hayir' diyebildigi: 0/20 | adim: 39 butce evet sertifikasi yapili hayir kaniti yapisiz tam tarama 13 20 20 0 100 20 20 0 1000 20 20 0 10000 20 20 20 ``` #### Asimetrinin Okunması İlk tablo tek başına asimetriyi kuruyor. Evet kümesinde tam tarama **4321 adım** harcıyor, çünkü uyan bir alt küme bulununca duruyor. İki hayır kümesinde ise **81.920 adım** — yani örnek başına tam **4096**, hiçbir indirim yok. Sayı iki kümede birebir aynı çünkü nedeni yordamsal değil mantıksaldır: "hiçbiri" demek için görülmemiş tek bir alt küme kalmamalıdır. İkinci blok üç sayıyı yan yana getiriyor. **Evet sertifikası 101 adım.** **Yapılı hayır kanıtı 260 adım** ve 20 örneğin 20'sinde "hayır" diyebiliyor. **Yapısız hayır kanıtı 39 adım** harcıyor ve 20 örneğin **hiçbirinde** bir şey söyleyemiyor — ilk tek sayıyı görünce çekiliyor. Bu üçlü, co-NP tanımının neden bir varlık iddiası olduğunu gösteriyor. Kısa bir "hayır" tanığı **bazı örnekler için vardır** ve ölçüldü: 4096 adım yerine 13. Ama tanığın **her** örnek için var olması ayrı bir iddiadır ve yapısız küme bu iddianın kendiliğinden sağlanmadığını gösteriyor. Ölçümün söylediği şey şudur: **bu kanıt bu örneklerde çalışmadı.** Söylemediği şey ise, başka bir kısa kanıtın var olmadığıdır; öyle bir kanıt aranmadı, yalnız bu bir tane denendi. Bütçe süpürmesi aynı ayrımı bir kez daha veriyor. Evet sertifikası ve yapılı hayır kanıtı bütçe 13'te doluyor; bütçeyi bin katına çıkarmak ikisinde de hiçbir şey değiştirmiyor. Yapısız küme ise 1000'de hâlâ sıfırda ve ancak 10.000'de 20'ye çıkıyor. #### İki Yönü de Ucuz Olan Problem Her problemde bu asimetri yoktur. Eşik problemi — sayıların toplamı hedefi aşıyor mu — iki yönde de aynı yordamla kapanır: toplam bir kez hesaplanır ve karşılaştırılır. ```python 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 esik(sayilar, hedef): """Toplam hedefi asiyor mu. Iki yon de ayni yordamla kapanir.""" toplam, adim = 0, 0 for s in sayilar: toplam += s adim += 1 return toplam > hedef, adim + 1 ev = hy = ea = ha = 0 for o in ornekler(): y1, a1 = esik(o["sayilar"], o["hedef"]) y2, a2 = esik(o["sayilar"], sum(o["sayilar"]) + 1) ev, hy = ev + y1, hy + (not y2) ea, ha = ea + a1, ha + a2 print("esik problemi | evet:", ev, "/20 ,", ea, "adim | hayir:", hy, "/20 ,", ha, "adim") print() print(" n evet sertifikasi hayir kaniti (tam tarama)") for n in (8, 12, 16, 20, 24): print(f"{n:2d} {n + 1:16d} {1 << n:25d}") ``` ``` esik problemi | evet: 20 /20 , 260 adim | hayir: 20 /20 , 260 adim n evet sertifikasi hayir kaniti (tam tarama) 8 9 256 12 13 4096 16 17 65536 20 21 1048576 24 25 16777216 ``` Eşik probleminde iki yön de **260 adım**: birebir eşit ve eşitlik bir rastlantı değil yordamın yapısından geliyor. Bu problem hem NP hem co-NP sınıfındadır, çünkü P sınıfındadır ve P her iki sınıfın da içindedir. Yanıtın yönü maliyeti değiştirmiyor. Alt satırdaki tablo karşıt uçtur. Girdi boyu 8'den 24'e çıkarken evet sertifikası 9'dan **25** adıma, hayır kanıtı 256'dan **16.777.216** adıma gidiyor. İki sütun aynı problemin iki yüzüdür ve aynı hızda büyümüyorlar. #### Aynı Hayır, Daha Az Adım Yapısız kümede tam taramanın 81.920 adım harcaması, o örnekler için "hayır" demenin bedeli **değildir**; yalnız tam taramanın bedelidir. Bunu göstermenin yolu, aynı yanıtı daha az adımda kuran başka bir yordam denemektir. Aşağıdaki blok iki tane dener: kısmi toplam hedefi aştığında dalı kesen budamalı bir tarama ve `01`'de tanıtılan erişilen toplamlar tablosu. ```python 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 ulasilmayan(sayilar): ulasilan = {0} for x in sayilar: ulasilan |= {u + x for u in ulasilan} return min((t for t in range(1, sum(sayilar)) if t not in ulasilan), key=lambda t: abs(t - sum(sayilar) // 3)) def tam_tarama(sayilar, hedef): adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def budamali(sayilar, hedef): """Kismi toplam hedefi asinca dal kesilir. Bir adim = bir dugum.""" s = sorted(sayilar) n, adim = len(s), 0 def gez(i, toplam): nonlocal adim adim += 1 if toplam == hedef: return True if toplam > hedef or i == n: return False return gez(i + 1, toplam + s[i]) or gez(i + 1, toplam) return gez(0, 0), adim def dinamik(sayilar, hedef): """Erisilen toplamlar tablosu. Bir adim = bir tablo hucresi.""" ulasilan = [False] * (hedef + 1) ulasilan[0] = True adim = 0 for x in sayilar: for t in range(hedef, x - 1, -1): adim += 1 if ulasilan[t - x]: ulasilan[t] = True return ulasilan[hedef], adim YAPISIZ = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ornekler()] print("yordam hayir diyen toplam adim butce 1000 butce 10000") for ad, f in (("tam tarama ", tam_tarama), ("budamali tarama", budamali), ("dinamik tablo ", dinamik)): hy = top = b3 = b4 = 0 for s, h in YAPISIZ: y, a = f(s, h) hy += not y top += a b3 += a <= 1000 b4 += a <= 10000 print(f"{ad:15s} {hy:11d} {top:11d} {b3:10d} {b4:11d}") ``` ``` yordam hayir diyen toplam adim butce 1000 butce 10000 tam tarama 20 81920 0 20 budamali tarama 20 21594 12 20 dinamik tablo 20 15736 16 20 ``` Üç yordam da 20 örneğin 20'sinde "hayır" diyor, yani üçü de aynı yanıtı kuruyor. Adım sayıları ise **81.920**, **21.594** ve **15.736**: budamalı tarama tam taramanın dörtte birinden biraz fazlasını, tablo yordamı beşte birinden azını harcıyor. Bütçe 1000'de tam tarama sıfırda kalırken budamalı tarama 12, tablo yordamı 16 örneği karara bağlıyor. Bir bölüm önce "bu kanıt bu örneklerde çalışmadı" denmişti; şimdi aynı örnekler dört beş kat ucuza kapanıyor. Yine de kapanma **n+1 adıma** inmedi ve tablo yordamının ucuzluğu `01`'de görüldüğü gibi hedefin değerine bağlıdır. Sonuç iki cümleye sığar: **ölçülen en iyi sayı, ölçülebilecek en iyi sayı değildir**; ve daha iyi bir sayı bulmak, bir sınır kanıtlamakla aynı şey değildir. #### Bilinen ve Açık Olan Bilinenler kısadır. **P sınıfı hem NP'nin hem co-NP'nin içindedir** ve tümleyen almaya kapalıdır. **NP-tam bir problemin tümleyeninin NP sınıfında olduğu bilinmiyor.** Bir problem hem NP hem co-NP sınıfındaysa, iki yönde de kısa tanığı var demektir; bu güçlü bir özelliktir ve her problemde bulunmaz. Açık olan da kısadır: **NP ile co-NP'nin eşit olup olmadığı bilinmiyor.** Bu ders o soruyu yanıtlamaz ve yanıtlamaya çalışmaz. Ölçtüğü şey, tek bir kısa kanıtın 20 örnekte çalışıp 20 örnekte çalışmadığıdır. Yapısız kümede kanıtın 0/20 vermesi, o örnekler için kısa bir kanıt **olmadığını göstermez**; yalnız **bu** kanıtın onlara uymadığını gösterir. Bu ayrım kursun aşırı iddia yasağının doğrudan uygulanmasıdır. Mühendislik karşılığı somuttur. Bir doğrulayıcıda "geçerli" yanıtını gerekçelendirmek ile "geçersiz" yanıtını gerekçelendirmek iki ayrı iştir: ilki bir tanık gösterebilir, ikincisi çoğu zaman "her ihtimali gördüm" demek zorundadır. İki yönün adım sayısı ayrı yazılmadıkça doğrulayıcının maliyeti bilinmiş sayılmaz. #### Özet - Bir problemin tümleyeni, çözülebilirlik açısından ondan farksızdır; doğrulanabilirlik açısından ayrı bir sorudur, çünkü sertifika ters çevrilerek kullanılamaz. - Evet kümesinde tam tarama 4321 adım harcıyor, iki hayır kümesinde 81.920 adım — örnek başına 4096, hiçbir indirim yok. - Kısa hayır kanıtı yapılı örneklerin 20'sinde 20'sinde çalışıyor ve 260 adım tutuyor; yapısız örneklerin hiçbirinde bir şey söyleyemiyor ve 39 adımda çekiliyor. - Eşik probleminde iki yön de 260 adımda kapanıyor; bu problem P sınıfında olduğu için hem NP hem co-NP sınıfındadır. - Girdi boyu 8'den 24'e çıkarken evet sertifikası 9'dan 25 adıma, hayır kanıtı 256'dan 16.777.216 adıma gidiyor. - NP ile co-NP'nin eşit olup olmadığı açık bir sorudur; bir kanıtın bu örneklerde çalışmaması, hiçbir kısa kanıtın olmadığını göstermez. #### Sonraki Adım Bu dersle birlikte dört sınıf adı ve aralarındaki bilinen ilişkiler kuruldu. Geriye en çok konuşulan, en az yanıtlanan soru kaldı: doğrulanabilir olan her şey aynı zamanda çözülebilir mi. Sonraki ders bu soruyu ifade eder ve **ölçemeyeceğini ölçmeye çalışmaz.** Ölçebildiği tek şey bilinen en iyi yordam ile bilinen alt sınır arasındaki farktır; o fark daraltılabiliyor mu, daraltılınca kapanıyor mu ve daralmanın kendisi bir yön göstergesi sayılabilir mi. ### P–NP Sorusu Source: https://academia.sh/tr/kurslar/hesaplama-kurami/p-np-sorusu Açık kalan sorunun ifadesi ve ölçülebilen tek şeyin ortaya konması: bilinen alt sınır 240, buluşma yordamı 1357, tam tarama 4321 adım harcıyor ve iki yordam 20 örneğin 20'sinde aynı yanıtı veriyor. Girdi boyu 24'te alt sınır 24, buluşma 8192, tam tarama 16.777.216 adım; açıklığın oranı 341,3'e karşı 699.050,7. Bir milyon adımlık bütçede tam tarama 19, buluşma 37 sayıya yetiyor. Soru açıktır ve bu derste hiçbir yön iddia edilmiyor. Dört sınıf adı ve aralarındaki bilinen ilişkiler kuruldu. Geriye en çok konuşulan, en az yanıtlanan soru kaldı: **doğrulanabilir olan her şey aynı zamanda çözülebilir mi.** Bu ders o soruyu ifade eder ve **ölçemeyeceğini ölçmeye çalışmaz.** Sorunun neden ölçülemediği ders boyunca sürekli görünür olacak. Ölçüm sonlu bir koşumdur ve sonlu bir koşum ancak "şu yordam şu kadar adım harcadı" der. Soru ise bütün yordamlar üzerine bir niceleyici taşır: "hiçbir yordam yok mu." Bu iki cümle arasındaki mesafe, bu dersin konusudur. Ölçülebilen tek şey **bilinen en iyi yordam ile bilinen alt sınır arasındaki farktır**. - **KS38.** Soru şu kapsama ilişkisidir: **P sınıfı NP sınıfının tamamına eşit midir.** P'nin NP'nin içinde olduğu `02`'de kuruldu; sorulan şey **ters yöndür**. - **KS39.** Soru **açıktır**. Bu derste hiçbir yön iddia edilmez, olası sayılmaz, "beklenir" denmez. - **KS40.** **Bilinen alt sınır**, hiçbir yordamın altına inemeyeceği gösterilmiş adım sayısıdır. Burada kullanılan alt sınır en zayıf olanıdır: girdiyi okumadan karar verilemeyeceği için **en az n adım**. - **KS41.** **Bilinen en iyi yordam**, bu derste kurulan yordamların en azını harcayanıdır. "Bilinen" sözcüğü bu kursun kapsamına göre okunur; kursun dışında daha iyisinin bulunup bulunmadığı burada ölçülmez. - **KS42.** İkinci yordam **buluşma yordamıdır**: girdi ikiye bölünür, ilk yarının bütün alt küme toplamları bir tabloya yazılır, ikinci yarı bu tabloya sorulur. - **KS43.** Buluşma yordamının doğruluğu varsayılmaz; her örnekte tam taramanın yanıtıyla karşılaştırılır. - **KS44.** Bir adım, tam tarama için **bir alt küme**, buluşma yordamı için **bir alt küme ya da bir sorgu**, alt sınır için **bir sayı okumasıdır**. - **KS45.** Bütçe süpürmesi dört değerde yapılır: 13, 100, 1000, 10.000 adım. İkinci süpürme girdi büyüklüğü üzerinedir. - **KS46.** Örnekler ortak tanımın üretecinden, tohum **20260218**. İkinci tohum yoktur. - **KS47.** Bir açıklığın daralması **yön göstergesi sayılmaz**. Daralma ölçülür, yorumlanmaz. #### Sorunun Kendisi İfade kısa ve tek anlamlıdır. P, girdi büyüklüğünün bir polinomuyla sınırlı adımda **çözülen** karar problemlerinin sınıfıdır. NP, "evet" yanıtı aynı sınırda **doğrulanan** problemlerin sınıfıdır. Her çözülen problem doğrulanabilir olduğuna göre P, NP'nin içindedir. Sorulan şey şudur: **NP'nin içinde, P'de olmayan bir problem var mı.** Sorunun bir yönü kurulmuştur ve gösterilmesi kolaydır. Öteki yön iki biçimde kapanabilirdi: ya NP-tam bir problem için polinom adımlı bir yordam bulunur ve iki sınıf çakışır, ya da öyle bir problem için polinom adımın yetmediği kanıtlanır ve ayrılırlar. **İkisi de yapılmamıştır** ve bu ders hangisinin olacağı hakkında hiçbir şey söylemez. Neden bir koşumun bu soruyu kapatamayacağı da açıktır. Bir yordamın 4096 adım harcaması, o problem için 4096 adımın gerektiğini göstermez; yalnız **o yordamın** o kadar harcadığını gösterir. Bir alt sınır kanıtı ise bütün yordamlar hakkında konuşur ve hiçbir koşum bütün yordamları tüketemez. Bu kursun aşırı iddia yasağı tam olarak bu boşluğu kapatmak içindir. #### Ölçülebilen Tek Şey Aşağıdaki blok üç sayıyı yan yana koyar: bilinen alt sınır, bu kursta kurulan en iyi yordamın adımı ve tam taramanın adımı. Buluşma yordamının yanıtı her örnekte tam taramayla karşılaştırılır. ```python 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 tam_tarama(sayilar, hedef): """Bir adim = bir alt kume.""" adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def bulusma(sayilar, hedef): """Girdi ikiye bolunur , her yarinin butun alt kume toplamlari cikarilir ve ikinci yaridan sorgulanir. Bir adim = bir alt kume ya da bir sorgu.""" n = len(sayilar) sol, sag = sayilar[: n // 2], sayilar[n // 2:] adim, tablo = 0, set() for maske in range(1 << len(sol)): adim += 1 tablo.add(sum(sol[i] for i in range(len(sol)) if maske >> i & 1)) for maske in range(1 << len(sag)): adim += 1 t = sum(sag[i] for i in range(len(sag)) if maske >> i & 1) if hedef - t in tablo: return True, adim return False, adim ORN = ornekler() uyan, tt, bt, asg = 0, 0, 0, 0 for o in ORN: y1, a1 = tam_tarama(o["sayilar"], o["hedef"]) y2, a2 = bulusma(o["sayilar"], o["hedef"]) uyan += y1 == y2 tt, bt, asg = tt + a1, bt + a2, asg + len(o["sayilar"]) print("20 ornek , n=12 | iki yordamin yaniti uyusan:", uyan, "/ 20") print(" bilinen alt sinir:", asg, "adim | bulusma yordami:", bt, "adim | tam tarama:", tt, "adim") print() print("butce tam tarama bulusma yordami") for b in (13, 100, 1000, 10000): c1 = sum(1 for o in ORN if tam_tarama(o["sayilar"], o["hedef"])[1] <= b) c2 = sum(1 for o in ORN if bulusma(o["sayilar"], o["hedef"])[1] <= b) print(f"{b:5d} {c1:10d} {c2:15d}") print() print(" n alt sinir bulusma tam tarama bulusma/alt sinir tarama/alt sinir") for n in (8, 12, 16, 20, 24): bul = (1 << (n - n // 2)) + (1 << (n // 2)) print(f"{n:2d} {n:9d} {bul:7d} {1 << n:10d} {bul / n:17.1f}" f" {(1 << n) / n:16.1f}") ``` ``` 20 ornek , n=12 | iki yordamin yaniti uyusan: 20 / 20 bilinen alt sinir: 240 adim | bulusma yordami: 1357 adim | tam tarama: 4321 adim butce tam tarama bulusma yordami 13 0 0 100 7 20 1000 19 20 10000 20 20 n alt sinir bulusma tam tarama bulusma/alt sinir tarama/alt sinir 8 8 32 256 4.0 32.0 12 12 128 4096 10.7 341.3 16 16 512 65536 32.0 4096.0 20 20 2048 1048576 102.4 52428.8 24 24 8192 16777216 341.3 699050.7 ``` #### Açıklığın Okunması Üç sayı yan yana: **alt sınır 240**, **buluşma 1357**, **tam tarama 4321**. İkinci yordam birincinin üçte birinden azını harcıyor ve 20 örneğin 20'sinde aynı yanıtı veriyor. Bu bir iyileşmedir, ölçüldü ve gerçektir. Bütçe süpürmesi iyileşmenin nerede işe yaradığını gösteriyor. **Bütçe 100'de tam tarama 7 örnekte kalırken buluşma yordamı 20'de 20 veriyor.** Bütçe 1000'de tam tarama 19'a çıkıyor, 10.000'de ikisi de dolu. Yani iyileşmenin görünür olduğu bir bütçe aralığı var ve o aralığın dışında iki yordam ayırt edilemiyor. Girdi boyu tablosu asıl soruyu yanıtlıyor: **açıklık kapanıyor mu.** Buluşma sütunu 32, 128, 512, 2048, 8192; her satırda dörde katlanıyor. Tam tarama sütunu 256'dan 16.777.216'ya, her satırda on altıya katlanarak gidiyor. Alt sınıra oranlar ise 4,0'dan **341,3**'e ve 32,0'dan **699.050,7**'ye çıkıyor. Okunması gereken şey iki sütunun **ikisinin de büyümesidir**. İyileşme oranı azaltmadı; artış hızını azalttı. Yirmi dört sayıda buluşma yordamı tam taramadan 2048 kat ucuz, ama alt sınırdan hâlâ 341 kat pahalı. **Açıklık daraldı, kapanmadı** ve bu tabloda kapanacağına dair hiçbir işaret yoktur — kapanmayacağına dair de yoktur. #### İyileşme İki Yönde de Var Mı Evet kümesindeki 3,18 katlık kazanç kısmen erken durmadan geliyor olabilir: tam tarama uyan alt kümeyi bulunca duruyor ve bu, ona haksız bir avantaj değil, gerçek bir indirim sağlıyor. Kazancın yapıdan mı yoksa erken durmadan mı geldiği, erken durmanın hiç olmadığı bir kümede ölçülür. `04`'ün yapısız hayır örnekleri tam olarak böyledir. ```python 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 ulasilmayan(sayilar): """Kurulum adimi: erisilmeyen bir hedef secilir , yanit kesin 'hayir'.""" ulasilan = {0} for x in sayilar: ulasilan |= {u + x for u in ulasilan} return min((t for t in range(1, sum(sayilar)) if t not in ulasilan), key=lambda t: abs(t - sum(sayilar) // 3)) def tam_tarama(sayilar, hedef): adim, n = 0, len(sayilar) for maske in range(1 << n): adim += 1 if sum(sayilar[i] for i in range(n) if maske >> i & 1) == hedef: return True, adim return False, adim def bulusma(sayilar, hedef): n = len(sayilar) sol, sag = sayilar[: n // 2], sayilar[n // 2:] adim, tablo = 0, set() for maske in range(1 << len(sol)): adim += 1 tablo.add(sum(sol[i] for i in range(len(sol)) if maske >> i & 1)) for maske in range(1 << len(sag)): adim += 1 t = sum(sag[i] for i in range(len(sag)) if maske >> i & 1) if hedef - t in tablo: return True, adim return False, adim ORN = ornekler() EVET = [(o["sayilar"], o["hedef"]) for o in ORN] HAYIR = [(o["sayilar"], ulasilmayan(o["sayilar"])) for o in ORN] print("kume uyusan tam tarama bulusma oran") for ad, kume in (("evet ", EVET), ("hayir", HAYIR)): uyan = tt = bt = 0 for s, h in kume: y1, a1 = tam_tarama(s, h) y2, a2 = bulusma(s, h) uyan += y1 == y2 tt, bt = tt + a1, bt + a2 print(f"{ad} {uyan:6d} {tt:10d} {bt:7d} {round(tt / bt, 2):5}") ``` ``` kume uyusan tam tarama bulusma oran evet 20 4321 1357 3.18 hayir 20 81920 2560 32.0 ``` Hayır kümesinde iki yordam da erken duramıyor, yani ikisi de işlerinin tamamını yapıyor. Tam tarama **81.920**, buluşma **2560** adım harcıyor ve oran **32,0**. Bu, evet kümesindeki 3,18'in on katıdır. Sonuç şudur: **kazancın kaynağı erken durma değil, yordamın yapısıdır**; evet kümesindeki oranın düşük görünmesi, tam taramanın oradan bir indirim almasındandır. Bu ayrım açık soruyla ilgilidir. Bir iyileşmenin gerçekten yapısal olup olmadığı, ancak indirimsiz bir kümede ölçülerek görülür. Buna karşın **32,0 oranı da bir yön göstermez**: sabit bir çarpanla bölünen bir üstel, hâlâ bir üsteldir ve tablo bunu 24 sayıda 341 katlık uzaklıkla zaten göstermişti. #### Bütçe Sabitken Ne Kadar İleri Gidilir İyileşmenin mühendislikteki karşılığı orandan çok **erişilen girdi büyüklüğüdur**. Bir adım bütçesi sabitlenip her yordamın o bütçede en çok kaç sayı işleyebildiği hesaplanabilir. Aşağıdaki tablo üçüncü bir sütun daha taşır ve o sütun **varsayımsaldır**: karesel adımlı bir yordam bulunsaydı ne olurdu. Böyle bir yordamın var olduğu iddia edilmiyor; sütun yalnız sorunun neyi değiştireceğini gösteriyor. ```python def en_buyuk_n(butce, maliyet, ust=200000): """Butce icinde kalan en buyuk girdi buyuklugu.""" en = 0 for n in range(1, ust + 1): if maliyet(n) <= butce: en = n return en def tarama(n): return 1 << n def bulusma(n): return (1 << (n - n // 2)) + (1 << (n // 2)) def karesel(n): return n * n print("adim butcesi tam tarama bulusma varsayimsal n^2") for b in (10 ** 4, 10 ** 6, 10 ** 8, 10 ** 10): print(f"{b:14d} {en_buyuk_n(b, tarama):10d} {en_buyuk_n(b, bulusma):7d}" f" {en_buyuk_n(b, karesel):15d}") ``` ``` adim butcesi tam tarama bulusma varsayimsal n^2 10000 13 24 100 1000000 19 37 1000 100000000 26 50 10000 10000000000 33 64 100000 ``` Bütçe bir milyon katına çıkarıldığında tam taramanın eriştiği girdi büyüklüğü 13'ten 33'e çıkıyor: bütçe milyon kat büyüyor, girdi büyüklüğü **yirmi sayı** kazanıyor. Buluşma yordamı aynı bütçelerde 24'ten 64'e gidiyor, yani her bütçede tam taramanın **yaklaşık iki katı** girdiye yetiyor. Bu gerçek ve ölçülmüş bir kazançtır. Üçüncü sütun farkın niteliğini gösteriyor. Varsayımsal karesel yordam aynı bütçelerde 100'den **100.000**'e çıkıyor. İlk iki sütun bütçeyi büyüterek birkaç sayı kazanıyor, üçüncüsü büyüklük düzeyi kazanıyor. P–NP sorusunun mühendislikteki karşılığı bu iki davranış arasındaki farktır: birinci ve ikinci sütun aynı ailedendir, üçüncüsü başka bir ailedendir ve alt küme toplamı probleminin hangi ailede olduğu **bilinmiyor**. #### Bu Dersin Söylemediği Yukarıdaki hiçbir sayı bir yön göstermez ve gösterecek biçimde okunmamalıdır. Buluşma yordamının tam taramayı 2048 kat geçmesi, daha iyisinin bulunacağını **düşündürmez**; buluşma yordamının alt sınırdan 341 kat uzak kalması da bulunmayacağını düşündürmez. Ölçüm bu iki cümlenin hiçbirini destekleyecek türden bir şey değildir. Söylenebilecek olan tam olarak şudur. Bu derste kurulan en iyi yordam 12 sayıda 1357 adım harcadı; bilinen alt sınır 240 adımdı; aradaki oran girdi büyüklüğü 24'te 341,3'e çıktı. Bu cümle ölçülmüştür ve bütçesiyle birlikte yazılmıştır. "Alt küme toplamı polinom zamanda çözülemez" cümlesi ise ölçülmemiştir, bu kursta kanıtlanmamıştır ve **kimse tarafından kanıtlanmamıştır**; yazılırsa kurala aykırıdır. Aynı katılık ters yön için de geçerlidir. "Bir gün polinom bir yordam bulunacak" cümlesi de ölçülmüş değildir. Açık bir soru hakkında yazılabilecek tek dürüst cümle, sorunun açık olduğunu söyleyen cümledir. #### Mühendislikte Karşılığı Sorunun açık kalması bir mühendisi işsiz bırakmaz; tersine, ne yapılacağını netleştirir. Bir problemin NP-tam bir probleme indirgendiği biliniyorsa, o probleme genel ve ucuz bir çözüm aramak, **çözülmemiş bir kuram sorusunu çözmeye çalışmakla aynı şeydir**. Bu, yapılamaz demek değildir; yapılan işin ne olduğunu doğru adlandırmaktır. Pratikte üç yol kalır ve üçü de bu kursta ölçüldü ya da ölçülecek. Birincisi girdiyi küçük tutmaktır: bütçe tablosu 12 sayıda hangi yordamın yettiğini gösterdi. İkincisi yordamı iyileştirmektir: buluşma yordamı erişilen girdi büyüklüğünu iki katına çıkardı. Üçüncüsü kesin çözümden vazgeçmektir ve bu sonraki dersin konusudur. #### Özet - P–NP sorusu, NP sınıfının içinde P'de olmayan bir problem bulunup bulunmadığını sorar ve **açıktır**; bu ders hiçbir yön iddia etmez. - Sonlu bir koşum soruyu kapatamaz, çünkü bir yordamın adımını ölçer, bütün yordamlar hakkında konuşamaz. - Yirmi örnekte bilinen alt sınır 240, buluşma yordamı 1357, tam tarama 4321 adım; iki yordam 20 örneğin 20'sinde aynı yanıtı veriyor. - Girdi boyu 8'den 24'e çıkarken buluşma 32'den 8192'ye, tam tarama 256'dan 16.777.216'ya gidiyor; alt sınıra oran 4,0'dan 341,3'e ve 32,0'dan 699.050,7'ye çıkıyor. Açıklık daraldı, kapanmadı. - Bir milyon adımlık bütçede tam tarama 19, buluşma 37 sayıya yetiyor; varsayımsal karesel bir yordam 1000 sayıya yeterdi. - Açık bir soru hakkında yazılabilecek tek dürüst cümle, ölçülmüş açıklığı bütçesiyle birlikte bildiren ve sorunun açık olduğunu söyleyen cümledir. #### Sonraki Adım Bu ders üçüncü yolu açıkta bıraktı: kesin çözümden vazgeçmek. Sonraki ders bunun bedelini sayar. Yaklaşık bir çözüm kaç örnekte kesin sonucu buluyor, bulamadığında ne kadar uzağa düşüyor ve yaklaşık yordama verilen bütçe büyütüldüğünde kayıp gerçekten kapanıyor mu. Kursun ve M01 müfredatının son dersi bu soruyla biter. ### Yaklaşım ve Sezgisel Yöntemler Source: https://academia.sh/tr/kurslar/hesaplama-kurami/yaklasim-ve-sezgisel-yontemler Kesin çözümden vazgeçmenin bedelinin sayılması ve kursun kapanışı: açgözlü yaklaşım 20 örneğin 5'inde kesin sonucu buluyor, 15'inde ayrılıyor ve en kötü bağıl kayıp 0,0676. Tam taranan eleman sayısı 0'dan 8'e çıkarıldığında ayrılan örnek 15'ten 0'a iniyor, adım 240'tan 35.956'ya çıkıyor; k=12'de yordam 553.948 adımla kâhinin 81.920 adımını geçiyor. Kurs kapanışı on satırlık bütçe tablosunu ve M01 müfredatının kapanışını taşıyor. Ö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. ```python 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. ```python 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 üç katından az artıyor. Kâhinin adımı 5120'den **1.310.720**'ye çıkıyor, yani 256 katına — her dört sayıda on altıyla çarpılarak. On altı sayıda kâhin yaklaşımın 279 katı adım harcıyor; yaklaşımın adımı da büyüdüğü için bu oran 3,2'den 27,5'e ve 279'a, yani her dört sayıda yaklaşık on katına çıkı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; tek satırlık kural üç türetme adımında hedefin tamamını üretiyor | | Turing Makinesi | adım 1–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.