--- title: 'Yaklaşım ve Sezgisel Yöntemler' source: 'https://academia.sh/tr/kurslar/hesaplama-kurami/yaklasim-ve-sezgisel-yontemler' course: 'Hesaplama Kuramı' language: tr updated: '2026-08-17T18:08:28+00:00' license: 'CC BY-SA 4.0' --- # Yaklaşım ve Sezgisel Yöntemler 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 iki katından az artıyor. Kâhinin adımı 5120'den **1.310.720**'ye çıkıyor, yani 256 katına. On altı sayıda kâhin yaklaşımın 279 katı adım harcıyor, ve bu oran her dört sayıda on altıyla çarpılarak büyüyor. Kayıp sütunu ise düzenli değil: 0,0109, 0,0125, 0,0037. Tam bulan örnek sayısı da 19, 15, 19. Bu düzensizlik beklenir, çünkü her satır ayrı bir dağarcıktır ve tek bir satırdan yön okunamaz. Okunabilecek olan şey daha küçük ve daha kesindir: **ölçülen bütün girdi büyüklüklerinde kayıp yüzde bir buçuğun altında kaldı**, ve bu cümlenin geçerli olduğu aralık 8 ile 16 sayı arasıdır. Sağdaki sütun bu aralığın neden dar olduğunu da söylüyor. Yirmi dört sayıda kâhin 16.777.216 alt küme görmek zorundadır; orada kayıp ölçülemez, çünkü karşılaştırılacak kesin sonuç bilinmez. Bir yaklaşık çözümün büyük girdideki kalitesi hakkında yazılan her cümle ya küçük girdide ölçülmüş bir kayıptan genelleme yapar ya da kanıtlanmış bir yaklaşım oranına dayanır; bu ders birincisini yaptı ve ikincisini iddia etmiyor. ## Sezgisel Yöntemin Bilemediği Ölçülen kaybın ötesinde bir sınır daha var ve sayısı yoktur. Yaklaşık yordam, bir örnekte ayrıldığını **kendisi bilemez**. k=0 çalıştırıldığında elde bir sayı olur; o sayının kâhinin sayısı olup olmadığı ancak kâhin koşturularak anlaşılır, ve kâhin koşturulabiliyorsa yaklaşıma gerek yoktur. Ayrılan örnek sayısının 15 olduğunu bilmek, hangi 15 örnek olduğunu bilmek demek değildir. Bunun pratik sonucu şudur. Bir yaklaşık çözüm devreye alınırken yanına yazılması gereken şey, ortalama kayıp değil **en kötü kayıptır** ve o kayıp hangi girdi aralığında ölçüldüğüdür. Bir raporda "yüzde bir kayıpla çalışıyor" cümlesi, girdi büyüklüğü ve kâhinin koşturulabildiği aralık yazılmadan bir şey anlatmaz. ## Özet - En iyileme biçiminde bir yanıt yanlış değil eksik olabilir; eksiklik ancak bir kâhinle ölçülür ve kâhin koşturulamayan girdide kayıp ölçülemez. - Saf açgözlü yaklaşım 20 örneğin 5'inde kesin sonucu buluyor, 15'inde ayrılıyor, en kötü bağıl kayıp 0,0676 ve bedeli 240 adım; kâhin 81.920 adım harcıyor. - Bütçe k=4'te ayrılan örnek 5'e ve kayıp 0,0125'e, k=8'de 0'a iniyor; bedeli 2980 ve 35.956 adım. - k=12'de yordam 553.948 adım harcayarak kâhinin 81.920 adımını geçiyor: bütçesi sonuna kadar büyütülmüş bir sezgisel yöntem iyi bir kesin yordam vermiyor. - Sıfır kayıp gözlemi, o bütçenin her girdide kesin sonucu bulacağının kanıtı değildir; ölçülen bağıl kayıp ile kanıtlanmış yaklaşım oranı ayrı şeylerdir. - Yaklaşık yordam ayrıldığını kendisi bilemez; devreye alınırken yazılması gereken şey en kötü kayıp ve ölçüldüğü girdi aralığıdır. ## Kurs Kapanışı Hesaplama Kuramı kursu on derste tek bir soruyu izledi: **sonlu bir bütçe neyi yanıtlar, neyi yanıtlayamaz, ve bütçeyi büyütmek bunu değiştirir mi.** Aşağıdaki tablo her dersin bütçesini ve o bütçenin iki yanını toplar. **Hesaplama Modelleri konusunun dört satırı kaynak derslerinden alınmıştır**; sayılar uydurulmaz. | Ders | Bütçe | Bütçenin yanıtladığı | Yanıtlayamadığı | |---|---|---|---| | Sonlu Otomatlar | durum 1–3, evren 31 dizi | 2, 26 ve **1054** ayrı dil | 2³¹ dilin yanında pay **0,0000004908**; k=2 uzunluk 2'den sonra **26'da donuyor** | | Bağlamdan Bağımsız Diller | durum 1–5, uzunluk 2–10 | öbek **4, 6, 8, 10, 12**; tam sayımla uzunluk 4'te en küçük k **5** | sabit bir k'nın **hiçbir** uzunlukta yetmediği ölçülemez; üç satırlık kural hedefin tamamını üretiyor | | Turing Makinesi | adım 2–200, 20.736 makine | **9784** duruyor, en uzun koşum **6 adım** | bütçe 6'dan sonra sayı **hiç değişmiyor**; durmayan 10.952'nin 5040'ı kanıtla, **5912'si bilinmiyor** | | Karar Verilemezlik | adım 5–200, 1000 başlangıç | **7, 155, 569, 756, 1000** | 5000 başlangıçta aynı bütçe **9 tanesini** karara bağlayamıyor; **1000/1000 durması kanıt değildir** | | P Sınıfı | adım bütçesi 12–10.000 | eşik 20/20 (12 adım), ikili 20/20 (66 adım) | alt küme toplamı 100 adımda 7/20; problemin P'de olup olmadığı | | NP Sınıfı | adım bütçesi 13–10.000 | sertifikayla 20/20, toplam 101 adım | çözerek 13 adımda 0/20; tanığın nasıl bulunacağı | | NP-Tam ve NP-Zor | adım bütçesi 15–10.000 | indirgeme 20/20, 300 adım, yanıt korunuyor | bölüştürmenin NP-tam olduğu; her NP probleminin indirgendiği | | co-NP ve Sınıflar Arası İlişkiler | adım bütçesi 13–10.000 | yapılı hayır 20/20, 260 adım | yapısız hayır 20/20 tam tarama istedi; NP ile co-NP'nin eşitliği | | P–NP Sorusu | adım bütçesi 13–10.000, girdi büyüklüğü 8–24 | buluşma 1357 adım, 20/20 uyuşuyor | açıklığın kapanıp kapanmadığı; sorunun yanıtı | | Yaklaşım ve Sezgisel Yöntemler | k = 0, 4, 8, 12 | k=0'da 5/20, k=8'de 20/20 tam | k=8'in her girdide tam bulacağı; kanıtlanmış yaklaşım oranı | Sağ sütun bu kursun asıl ürünüdür. Sol sütundaki her sayı bir koşumdan gelir; sağ sütundaki her satır, koşumun **ulaşamadığı** yeri adlandırır. Bu kurs, ölçümün nerede bittiğini gösteren kurstur. M01 Bilgisayar Bilimi müfredatı sekiz kursta tek bir ekseni izledi: bitin donanımdaki temsilinden (K01) programın yazılışına (K02), verinin yerleşimine (K03), yordamın maliyetinin ölçülmesine (K04), makinenin paylaşılmasına (K05), sistemin gösterilmesine (K06), zor problemlerin kâhinle karşılaştırılmasına (K07) ve ölçümün sınırına (K08) kadar her katmanda **bedel sayıldı, ve sayılmayan bedel bilinmiş sayılmadı.** **M01/K07'nin iki borcu bu kursta ödendi.** Birincisi, gezgin satıcı ve Hamilton yolları derslerinin ayrı birer bölümde buraya havale ettiği "bu problem neden zor" sorusuydu. Yanıt bir kanıt değil bir **sınıflandırmadır**: bu problemlerin "evet" yanıtı kısa bir sertifikayla ucuza doğrulanır (`02`), zorlukları birbirine ucuz indirgemelerle taşınır (`03`), ve "hayır" yanıtı aynı indirimi kabul etmez (`04`). Sınıfların adları NP, NP-tam ve NP-zordur. İkincisi K07'nin Kurs Kapanışı'ndaki soruydu: kaba kuvvetten daha iyisinin bilinmemesi, **bilgimiz hakkında mı yoksa problemler hakkında mı** bir gerçektir. Bu sorunun bir adı vardır ve **P–NP sorusudur** (`05`). Yanıtı bilinmiyor. Borç, soruyu yanıtlayarak değil, **doğru adlandırarak ve neden yanıtlanmadığını göstererek** ödenir: ölçüm bir yordamın adımını sayabilir, bütün yordamlar hakkında konuşamaz. Sonraki müfredat **M03 Linux ve Sistem Yönetimi**'dir ve zemini değiştirir. M01 kavramları kurdu ve modelledi; M03 aynı kavramların çalışan bir sistemdeki karşılığını ele alır: kabuk, dosya sistemi, süreçler, servisler, ağ ve çekirdek arayüzleri. M01/K05 süreci ve dosya sistemini **modelleyip saymıştı**; M03 aynı kavramları komut düzeyinde kullanır. İlk soru da bu geçişe uygundur: bir sistemle konuşmanın arayüzü nedir, ve o arayüzde verilen bir komut hangi katmana kadar iner.