--- title: 'Kaba Kuvvet ve Sınırları' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/kaba-kuvvet-ve-sinirlari' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:25+00:00' license: 'CC BY-SA 4.0' --- # Kaba Kuvvet ve Sınırları Kaba kuvvetin bu kurstaki rolü bir yavaş seçenek değil bir kâhindir: tam sayım 40 girdide 2640 adım harcıyor, erken çıkan eleme 866 adımla aynı yanıtı veriyor, ilk altı konuma bakan örnekleme ise 406 adımla 14 girdide kâhinden ayrılıyor. Algoritmalar kursu bir ölçüt kurarak kapandı: işlem sayımı, asimptotik gösterim, alt sınır. O kursta ölçülen tek şey maliyetti, çünkü her algoritmanın **doğru olduğu varsayılmıştı**. Bu kurs o varsayımı kaldırarak açılır. Bir tasarım kalıbı seçmek yalnız hızlanmak değildir; bir **ön koşulu (precondition)** kabul etmektir. Ön koşul bozulduğunda kalıp yavaşlamaz — **yanlış yanıt verir**, ve yanlışlığı çıktısına bakarak anlaşılmaz, çünkü yine bir sayı döndürür. Bu yüzden kursun merkezinde **kaba kuvvet (brute force)** durur; ama burada "yavaş seçenek" olarak değil, **kâhin (oracle)** olarak durur. Bir kalıbın sayısı kazandırdığı adım değil, ön koşulu bozulduğunda verdiği yanlış yanıt sayısıdır; ön koşulu kâhinle sınanmayan kalıp ölçülmemiş sayılır. - **TY1.** Ölçü **adımdır**, süre değil. Hiçbir derste gerçek zaman ölçülmez. - **TY2.** Tohum **20260218**. Aynı tohum aynı dağarcığı verir; buradaki her sayı yeniden üretilebilir. - **TY3.** **Dağarcık (input corpus)** 40 diziden oluşur; her dizi 12 değer taşır ve değerler -9 ile 20 arasındadır. - **TY4.** Bir **adım**, iki değerin toplanıp hedefle karşılaştırılmasıdır. Sayaç her adımı bir sayar. - **TY5.** **Kâhin her zaman kaba kuvvettir:** bütün olasılıkları gören, erken çıkmayan yordam. Kâhinin yanıtı tanım gereği doğru sayılır. - **TY6.** Bir adayın doğruluğu ancak kâhinle karşılaştırılarak iddia edilir. **Kâhinsiz doğruluk iddiası yazılmaz.** - **TY7.** **Ayrılan girdi**, kâhin ile adayın farklı yanıt verdiği girdidir; 40 üzerinden sayılır. - **TY8.** Çözünürlük: 40 girdide 1 ayrılma **ölçülmemiş sayılır**, 3 ve üzeri anlamlıdır. - **TY9.** Rastgelelik belirlenimci bir üreteçle modellenir; standart kitaplığın rastgele sayı üreteci kullanılmaz. - **TY10.** Her ölçüm **20260219** tohumlu ikinci bir dağarcıkta da koşturulur. ## Kaba Kuvvet Neden Kâhin Olabiliyor Kaba kuvvet, çözüm uzayının tamamını sayan yordamdır: bütün ikilileri, bütün alt kümeleri, bütün sıralamaları. Algoritmalar kursunun metin algoritmaları konusunda kaba kuvvet örüntü arama bir **taban** olarak kurulmuştu; oradaki soru, daha akıllı yordamların o tabandan kaç karşılaştırma kazandığıydı. Burada rol değişir. Kaba kuvvetin bu kurstaki ayrıcalığı hızıyla değil, **ön koşulsuz olmasıyla** ilgilidir. İki işaretçi dizinin sıralı olmasını ister, kayan pencere değerlerin negatif olmamasını, açgözlü seçim yerel seçimin küresel çözüme uymasını. Tam sayımın böyle bir isteği yoktur: bütün olasılıkları gördüğü için hiçbir varsayımı bozulamaz. Bozulacak varsayımı olmayan tek yordam, başkalarının bozulmuş varsayımını ölçebilecek tek yordamdır. Bunun bedeli her derste ödenir. Kâhin pahalıdır ve pahalılığı kusur değil, kâhinliğin karşılığıdır. Bir kalıbın kâhinden hızlı olması bir başarı değildir; kâhinle **aynı yanıtı verirken** hızlı olması bir başarıdır. Bu ayrımı sayıya çeviren şey, ayrılan girdi sayısıdır. ## Ölçüm Çerçevesi Kursun bütün ölçümleri aynı dağarcık ve aynı sayaç üzerinde yapılır. Dağarcık, ön koşulları kasıtlı olarak **bozan** girdilerden kurulur; ön koşulu sağlayan öbekler ondan türetilir. ```python # Olcum cercevesi: dagarcik ve adim sayaci. Sure degil ADIM sayilir. TOHUM = 20260218 UZUNLUK = 12 DAGARCIK = 40 def uretec(tohum): """Belirlenimci uretec. Ayni tohum ayni dagarcigi verir.""" d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=TOHUM, n=DAGARCIK, uzunluk=UZUNLUK): r = uretec(tohum) kume = [] for i in range(n): dizi = [r(30) - 9 for _ in range(uzunluk)] # -9 .. 20 kume.append({"no": i + 1, "dizi": dizi, "negatif": any(x < 0 for x in dizi), "sirali": dizi == sorted(dizi)}) return kume class Sayac: def __init__(self): self.adim = 0 def say(self, n=1): self.adim += n K = dagarcik() print("dagarcik:", len(K), "dizi x", UZUNLUK, "deger") print("sirali olan:", sum(1 for k in K if k["sirali"]), "| negatif iceren:", sum(1 for k in K if k["negatif"])) print("ilk dizi:", K[0]["dizi"]) ``` ``` dagarcik: 40 dizi x 12 deger sirali olan: 0 | negatif iceren: 40 ilk dizi: [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1] ``` Kırk dizinin **sıfırı** sıralı, **kırkı** negatif değer içeriyor. Bu bir kaza değil, tasarımdır: taban dağarcık, kursun ele alacağı ön koşulların çoğunu ihlal eder. Ön koşulu sağlayan öbekler bu diziler sıralanarak ya da mutlak değerleri alınarak üretilir, böylece iki öbek aynı üreteçten gelir ve aralarındaki tek fark ön koşulun kendisi olur. ## Kâhinin Adımı ve İki Kısaltma Ölçülen problem şudur: bir dizide, toplamı hedefe eşit **iki ayrı konum** var mı. Hedef 11 alınır. Üç yordam yazılır. İlki kâhindir: bütün ikilileri görür, uyum bulsa bile durmaz. İkincisi bir **eleme** uygular, ilk uyumda çıkar. Üçüncüsü bir **örnekleme** uygular, yalnız ilk altı konuma bakar. ```python # Onceki blogun uzerine: dagarcik, Sayac ve K oradan gelir. HEDEF = 11 def kahin_tam(dizi, hedef, s): """Butun ciftleri gorur, erken cikmaz. Hakem budur.""" bulundu = False for i in range(len(dizi)): for j in range(i + 1, len(dizi)): s.say() if dizi[i] + dizi[j] == hedef: bulundu = True return bulundu def erken_cikan(dizi, hedef, s): """ELEME: ilk uyumda durur. Atlanan ciftler yaniti degistiremez.""" for i in range(len(dizi)): for j in range(i + 1, len(dizi)): s.say() if dizi[i] + dizi[j] == hedef: return True return False def orneklemeli(dizi, hedef, s, bak=6): """ORNEKLEME: yalniz ilk 'bak' konuma bakar. Gorulmeyen cift bilinmez.""" for i in range(min(bak, len(dizi))): for j in range(i + 1, min(bak, len(dizi))): s.say() if dizi[i] + dizi[j] == hedef: return True return False def olc(aday, kahin, kume, hedef): """Adayi kahinle karsilastirir; ayrilan girdiyi sayar.""" ayrilan, aa, ah = [], 0, 0 for k in kume: s1, s2 = Sayac(), Sayac() if aday(k["dizi"], hedef, s1) != kahin(k["dizi"], hedef, s2): ayrilan.append(k["no"]) aa += s1.adim ah += s2.adim return {"girdi": len(kume), "ayrilan": len(ayrilan), "ayrilan_no": ayrilan[:6], "aday_adim": aa, "kahin_adim": ah, "oran": round(ah / aa, 2) if aa else 0.0} s = Sayac() for k in K: kahin_tam(k["dizi"], HEDEF, s) print("kahin (tam sayim) toplam adim:", s.adim) print("eleme ", olc(erken_cikan, kahin_tam, K, HEDEF)) print("ornekleme", olc(orneklemeli, kahin_tam, K, HEDEF)) ``` ``` kahin (tam sayim) toplam adim: 2640 eleme {'girdi': 40, 'ayrilan': 0, 'ayrilan_no': [], 'aday_adim': 866, 'kahin_adim': 2640, 'oran': 3.05} ornekleme {'girdi': 40, 'ayrilan': 14, 'ayrilan_no': [1, 2, 3, 4, 8, 9], 'aday_adim': 406, 'kahin_adim': 2640, 'oran': 6.5} ``` Üç sayı yan yana duruyor. **Kâhin** 40 girdide **2640 adım** harcıyor; bu, dizi başına tam olarak 66 ikilidir ve girdiye göre değişmez. **Eleme** 866 adım harcıyor, yani kâhinin **3,05 katı** azını, ve 40 girdinin **hiçbirinde** kâhinden ayrılmıyor. **Örnekleme** 406 adım harcıyor, kâhinin **6,50 katı** azını, ve 40 girdinin **14'ünde** kâhinden ayrılıyor. Ayrılan girdi oranı 0,3500'dür ve çözünürlüğün çok üstündedir. Bu üç satırın taşıdığı ders, kursun geri kalanının çerçevesidir. **Kısaltmanın iki türü vardır ve ikisi çıktıya bakarak ayırt edilemez.** Eleme, atladığı ikililerin yanıtı değiştiremeyeceğini bildiği için doğruluğu korur: uyum zaten bulunmuşsa geri kalan ikililer yanıtı `True` olmaktan çıkaramaz. Örnekleme böyle bir bilgiye dayanmaz; görmediği ikililer hakkında hiçbir güvencesi yoktur ve 14 girdide gerçekten yanılır. Ayrılan girdilerin numaraları da bir örüntü taşır. Çıktıdaki ilk altısı 1, 2, 3, 4, 8 ve 9'dur; bunların ortak yanı, hedefi tutturan **her** ikilinin en az bir ucunun **ilk altı konumun dışında** kalmasıdır. Örnekleme o ikilileri hiç görmez ve "yok" yanıtı verir. Yanılgının nedeni bir hesap hatası değil, **görülmeyen bir bölgeyle ilgili varsayımdır**; bu, kursun bütün kalıp yanılgılarının ortak biçimidir. Sayıların sırası da anlamlıdır. **Yanlış olan, doğru olandan hızlıdır:** örnekleme 406, eleme 866 adım. Hızlanma tek başına ölçüldüğünde örnekleme kazanır. Ölçüye ayrılan girdi eklendiği anda sıralama tersine döner. Bu, kursun ikinci iddiasının ilk biçimidir: **hızlandırma yanlışa yaklaştırır**, ve yanlışlık ucuz olduğu için çekicidir. ## Tam Aramanın Sınırı Kaba kuvvetin ne zaman kabul edilebilir olduğu sorusu, bir adım bütçesiyle yanıtlanır: bir koşumda göze alınan adım sayısı belirlenir ve her arama ailesinin o bütçeye hangi girdi büyüklüğüne kadar sığdığı hesaplanır. Bütçe burada yüz milyon adım alınmıştır. ```python from math import comb, factorial BUTCE = 10**8 # bir kosumda goze alinan adim ust siniri def sigan_n(sayim, ust=20000): """Adim butcesine sigan en buyuk n.""" en = 0 for n in range(1, ust + 1): if sayim(n) > BUTCE: break en = n return en AILE = (("ikili secim", lambda n: comb(n, 2)), ("uclu secim", lambda n: comb(n, 3)), ("alt kume", lambda n: 2 ** n), ("siralama", factorial)) print("tam tarama ailesi n=12 adim n=20 adim butceye sigan n") for ad, f in AILE: print(f" {ad:13s} {f(12):10d} {f(20):19d} {sigan_n(f):15d}") print("adim butcesi:", BUTCE) ``` ``` tam tarama ailesi n=12 adim n=20 adim butceye sigan n ikili secim 66 190 14142 uclu secim 220 1140 844 alt kume 4096 1048576 26 siralama 479001600 2432902008176640000 11 adim butcesi: 100000000 ``` Dört aile aynı bütçede dört ayrı dünyaya karşılık geliyor. İkili seçim on dört binin üzerinde bir girdiyi kaldırıyor; üçlü seçim 844'te duruyor; bütün alt kümeleri sayan arama **26'da**, bütün sıralamaları sayan arama **11'de** duruyor. Aradaki uçurum, bu kursun neden yalnız hızlanma değil **kalıp seçimi** öğrettiğinin nedenidir: sıralama ailesinde kalan bir çözüm, girdi bir eleman büyüdüğünde bütçesini bir daha aşar. Sınırın kâhin rolünü ortadan kaldırmadığına dikkat etmek gerekir. Bir yordam üretimde n=1000 ile çağrılacak olsa bile, kâhinle karşılaştırma **n=12'lik bir dağarcıkta** yapılır; orada tam sayım 2640 adımdır ve hiçbir bütçeyi zorlamaz. Kaba kuvvet **çözüm olarak** küçük girdilerde biter, **ölçüm aracı olarak** her derste kullanılabilir kalır. ## Dağarcığın Boyu Kâhinin Bütçesidir Bir önceki tablo, dağarcığın neden on iki elemanlı dizilerden kurulduğunu da açıklar. Kurs boyunca kâhin yalnız ikili seçim ailesinde kalmayacak; bazı problemlerde bütün alt kümeleri taramak gerekecek. O tarama, dağarcığın eleman sayısına doğrudan bağlıdır. ```python # Onceki bloklarin uzerine: dagarcik, Sayac ve UZUNLUK oradan gelir. SINIR = 30 def kahin_alt_kume(dizi, sinir, s): """Toplami siniri asmayan en buyuk alt kume toplami. Butun alt kumeler taranir.""" en_iyi = 0 for maske in range(1 << len(dizi)): s.say() toplam = sum(dizi[i] for i in range(len(dizi)) if maske >> i & 1) if toplam <= sinir and toplam > en_iyi: en_iyi = toplam return en_iyi K = dagarcik() s = Sayac() for k in K: kahin_alt_kume(k["dizi"], SINIR, s) print("dizi basina alt kume:", 2 ** UZUNLUK, "| 40 dizide kahin adimi:", s.adim) for uzunluk in (12, 16, 20, 26): print(f" uzunluk {uzunluk:2d} -> 40 dizide {40 * 2 ** uzunluk:12d} adim", "(butce icinde)" if 40 * 2 ** uzunluk <= 10**8 else "(butce disinda)") ``` ``` dizi basina alt kume: 4096 | 40 dizide kahin adimi: 163840 uzunluk 12 -> 40 dizide 163840 adim (butce icinde) uzunluk 16 -> 40 dizide 2621440 adim (butce icinde) uzunluk 20 -> 40 dizide 41943040 adim (butce icinde) uzunluk 26 -> 40 dizide 2684354560 adim (butce disinda) ``` On iki elemanlı bir dizide 4096 alt küme vardır; kırk dizide kâhin **163.840 adım** harcar ve bütçenin binde ikisini kullanır. Aynı kâhin yirmi elemanlı dizilerde 41.943.040 adıma çıkar — hâlâ sığar, ama bütçenin yüzde kırkını yer. Yirmi altı elemanda dağarcığın kendisi bütçeyi **yirmi yedi kat** aşar. Buradan çıkan kural, kursun ölçüm düzeninin temelidir: **dağarcığın eleman sayısı, ölçülecek en pahalı kâhine göre seçilir.** On iki, kırk girdilik bir dağarcıkta alt küme taramasını bile taşıyan en büyük rahat sayıdır. Dağarcığı büyütmek daha zengin girdi vermez; yalnız kâhini ulaşılmaz kılar ve ölçümü ortadan kaldırır. Kalıbı hızlandırmanın bir sınırı olduğu gibi, kalıbı **sınamanın** da bir sınırı vardır ve ikisi aynı bütçeden ödenir. ## İkinci Dağarcık Tek bir dağarcıkta ölçülen oranın dağarcığa bağlı olup olmadığı ayrıca sınanır. ```python # Onceki bloklarin uzerine: dagarcik, olc ve uc yordam oradan gelir. for ad, tohum in (("birinci dagarcik (20260218)", 20260218), ("ikinci dagarcik (20260219)", 20260219)): kume = dagarcik(tohum) e = olc(erken_cikan, kahin_tam, kume, HEDEF) o = olc(orneklemeli, kahin_tam, kume, HEDEF) print(ad) print(" eleme : ayrilan", e["ayrilan"], "/ 40 | oran", round(e["ayrilan"] / 40, 4), "| aday adim", e["aday_adim"]) print(" ornekleme: ayrilan", o["ayrilan"], "/ 40 | oran", round(o["ayrilan"] / 40, 4), "| aday adim", o["aday_adim"]) ``` ``` birinci dagarcik (20260218) eleme : ayrilan 0 / 40 | oran 0.0 | aday adim 866 ornekleme: ayrilan 14 / 40 | oran 0.35 | aday adim 406 ikinci dagarcik (20260219) eleme : ayrilan 0 / 40 | oran 0.0 | aday adim 970 ornekleme: ayrilan 21 / 40 | oran 0.525 | aday adim 512 ``` Elemenin ayrılan girdisi iki dağarcıkta da **sıfırdır**; bu beklenen sonuçtur, çünkü elemenin doğruluğu girdiye değil, atlanan dalların yanıtı değiştiremeyeceği gözlemine dayanır. Örneklemenin oranı **0,3500'den 0,5250'ye** çıkıyor. İki oran aynı büyüklük düzenindedir — ikisi de girdilerin üçte biri ile yarısı arasında — ama aradaki fark çözünürlüğün çok üstündedir. Okuma şudur: örneklemenin yanıldığı **girdi vardır ve sayıcadır**; kaç girdide yanıldığı **dağarcığa bağlıdır** ve tek bir sayıyla bildirilemez. ## Özet - Kaba kuvvet bu kursta bir yavaş seçenek değil **kâhindir**; ayrıcalığı hızından değil, bozulacak bir ön koşulu olmamasından gelir. - Aynı problemde kâhin 40 girdide **2640 adım**, eleme **866 adım** (3,05 kat az, **0 ayrılan girdi**), örnekleme **406 adım** (6,50 kat az, **14 ayrılan girdi**) harcıyor. - Kısaltmanın iki türü çıktıdan ayırt edilemez: eleme atladığı dalların yanıtı değiştiremeyeceğini bilir, örnekleme bilmez. - Yanlış olan, doğru olandan hızlıdır; ölçüye ayrılan girdi eklenmedikçe örnekleme kazanmış görünür. - Yüz milyon adımlık bütçede ikili seçim 14.142, üçlü seçim 844, alt küme araması 26, sıralama araması 11 elemana kadar sığar; kâhin rolü bu sınırdan etkilenmez çünkü ölçüm 12 elemanlık dağarcıkta yapılır. - İkinci dağarcıkta elemenin ayrılan girdisi yine 0, örneklemeninki 14 yerine 21; oran aynı büyüklük düzeninde kalıyor ama tam değeri **dağarcığa bağlıdır**. ## Sonraki Adım Bu derste kaba kuvvet bölünmeden, tek parça olarak koştu. İlk tasarım kalıbı problemi parçalar: aynı problemi daha küçük iki kopyasına indirir, her birini çözer ve sonuçları birleştirir. Sonraki ders bu kalıbın bağıntısını kurar ve iki soruyu sayar — birleştirme adımı eksik kaldığında kaç girdide yanlış yanıt çıkıyor, ve bölmenin adım kazandırmadığı girdi büyüklüğü nerede bitiyor.