--- title: 'Kayan Pencere' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/kayan-pencere' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:30+00:00' license: 'CC BY-SA 4.0' --- # Kayan Pencere Bitişik alt dizide artımlı hesap; negatif değerin küçültme kuralını bozduğu 10 girdi ve ön koşulun pencereye değil kurala ait olduğu. Önceki ders iki işaretçiyi dizinin iki ucuna koyuyor ve ortada buluşturuyordu; ön koşulu sıraydı. Bu dersin kalıbı işaretçileri **aynı yönde** tutar. Aralarındaki bölge bir **pencere**dir: sağ işaretçi ilerledikçe pencere büyür, bir koşul sağlandığında sol işaretçi ilerleyerek pencereyi küçültür. Kazanç, pencere her kaydığında toplamın sıfırdan hesaplanmamasından gelir; giren değer eklenir, çıkan değer düşülür. Ön koşulu ise sıraya hiç bakmaz: **hiçbir değer negatif olmamalıdır**. Bu ders o ön koşulun bozulduğu girdileri kâhinle sayar ve ön koşulun aslında pencerenin değil **küçültme kuralının** ön koşulu olduğunu gösterir. ## Problem, Kâhin ve Kalıp Problem şudur: toplamı hedeften küçük olmayan **en kısa bitişik alt dizinin uzunluğu** nedir. Kâhin her başlangıç konumundan başlayıp sağa doğru genişler ve hedefi ilk aştığı yerde durur; bütün başlangıçları dener. Kalıp tek geçişte ilerler: sağ uç değeri toplama katar, toplam hedefi aştığı sürece sol uçtan değer düşerek pencereyi daraltır. **PK10.** Dağarcık, önceki dersin dağarcığıdır: tohum `20260218`, 40 dizi, her biri 12 değer, değerler −9 ile 20 arasında. Kırk dizinin **kırkı** negatif değer içerir. **PK11.** Ön koşulu sağlayan öbek, aynı dizilerin değerlerinin **mutlak değeridir**. İki öbeğin tek farkı işarettir; uzunluk, konum ve üreteç aynıdır. **PK12.** Hedef 25'tir ve bir alt dizi hedefi tam olarak tutturmak zorunda değildir; "hedeften küçük olmamak" yeterlidir. **PK13.** Kâhin kaba kuvvettir ve her zaman doğru sayılır. Yanıt bir uzunluktur; hiçbir alt dizi hedefi tutturamıyorsa yanıt tanımsızdır. ```python TOHUM = 20260218 def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=TOHUM, n=40, uzunluk=12): r = uretec(tohum) return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]} for i in range(n)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_en_kisa(dizi, hedef, s): """Butun bitisik alt dizileri dener. Her zaman dogru.""" en_iyi = None for i in range(len(dizi)): toplam = 0 for j in range(i, len(dizi)): s.say() toplam += dizi[j] if toplam >= hedef and (en_iyi is None or j - i + 1 < en_iyi): en_iyi = j - i + 1 break return en_iyi def kalip_kayan_pencere(dizi, hedef, s): """ONKOSUL: butun degerler negatif olmamali.""" sol, toplam, en_iyi = 0, 0, None for sag in range(len(dizi)): s.say() toplam += dizi[sag] while toplam >= hedef: if en_iyi is None or sag - sol + 1 < en_iyi: en_iyi = sag - sol + 1 toplam -= dizi[sol] sol += 1 s.say() return en_iyi def olc(kume, hedef): ayrilan, ak, ah = [], 0, 0 for k in kume: s1, s2 = Sayac(), Sayac() a = kalip_kayan_pencere(k["dizi"], hedef, s1) b = kahin_en_kisa(k["dizi"], hedef, s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan.append(k["no"]) return {"ayrilan": len(ayrilan), "ilk_ayrilan": ayrilan[:6], "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2)} K = dagarcik() P = [dict(k, dizi=[abs(x) for x in k["dizi"]]) for k in K] print("dagarcik:", len(K), "dizi | negatif iceren:", sum(1 for k in K if any(x < 0 for x in k["dizi"]))) for ad, kume in (("on_kosul saglaniyor", P), ("on_kosul bozuk ", K)): print(f" {ad}", olc(kume, 25)) ``` ``` dagarcik: 40 dizi | negatif iceren: 40 on_kosul saglaniyor {'ayrilan': 0, 'ilk_ayrilan': [], 'kalip_adim': 867, 'kahin_adim': 2396, 'oran': 2.76} on_kosul bozuk {'ayrilan': 10, 'ilk_ayrilan': [2, 12, 13, 15, 24, 26], 'kalip_adim': 761, 'kahin_adim': 2462, 'oran': 3.24} ``` Ön koşul sağlandığında kalıp **867** adımda 40 girdinin 40'ında kâhinle aynı yanıtı veriyor; kâhin **2396** adım harcıyor, oran **2,76**. Negatif değer içeren dağarcıkta ayrılan girdi **10** oluyor. Buradaki sayı, önceki dersin 25'inden düşük ve bu düşüklük dersin en tehlikeli tarafıdır. Kalıp girdilerin dörtte üçünde hâlâ doğru yanıt veriyor. Bir sınama kümesi rastgele seçilseydi temiz sonuç verme olasılığı yüksekti; kusur, gözlemle değil **kâhinle** ortaya çıkar. İkinci satırın oranı da dikkat çekicidir: **3,24**, yani ön koşul sağlandığındaki 2,76'dan **yüksek**. Kalıp bozuk girdide daha az adım harcıyor (761'e karşı 867), çünkü negatif değerler toplamı düşürüyor ve küçültme döngüsü daha seyrek çalışıyor. **Daha az adım daha iyi yanıt demek değildir.** ## Küçültme Kuralı Neye Dayanıyor Kalıbın tek riskli satırı `while toplam >= hedef` döngüsüdür. Bu döngü, soldan bir değer düşüldüğünde toplamın **azalacağını** varsayar. Negatif olmayan değerlerde bu doğrudur; toplam, sol uç ilerledikçe tekdüze azalır ve döngü ilk kez koşulu bozduğunda o başlangıç için en kısa pencere bulunmuş olur. Negatif bir değer düşüldüğünde toplam **artar**. O anda pencere daralmış ama toplam büyümüştür; kalıp bunu bir ilerleme sayar ve sol ucu bir daha geri almaz. Atlanan başlangıçlar arasında daha kısa bir çözüm varsa görülmez. **PK14.** Kalıp sol ucu **geri almaz**; her konum en çok bir kez sol uçtan çıkar. Kalıbın doğrusal adım sayısı bu geri almama kuralından gelir, dolayısıyla kural gevşetilemez. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum): r = uretec(tohum) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] def kahin_en_kisa(dizi, hedef): en_iyi = None for i in range(len(dizi)): toplam = 0 for j in range(i, len(dizi)): toplam += dizi[j] if toplam >= hedef and (en_iyi is None or j - i + 1 < en_iyi): en_iyi = j - i + 1 break return en_iyi def kalip_kayan_pencere(dizi, hedef): sol, toplam, en_iyi = 0, 0, None for sag in range(len(dizi)): toplam += dizi[sag] while toplam >= hedef: if en_iyi is None or sag - sol + 1 < en_iyi: en_iyi = sag - sol + 1 toplam -= dizi[sol] sol += 1 return en_iyi ikinci = dagarcik(20260218)[1] print("girdi 2:", ikinci) print(" kalip:", kalip_kayan_pencere(ikinci, 25), "| kahin:", kahin_en_kisa(ikinci, 25)) print(" mutlak degerle:", [abs(x) for x in ikinci]) print(" kalip:", kalip_kayan_pencere([abs(x) for x in ikinci], 25), "| kahin:", kahin_en_kisa([abs(x) for x in ikinci], 25)) print() print("tohum hedef on_kosul ayrilan/40 oran") for tohum in (20260218, 20260219): for hedef in (25, 15): K = dagarcik(tohum) obek = (("saglaniyor", [[abs(x) for x in d] for d in K]), ("bozuk ", K)) for ad, kume in obek: ayrilan = sum(1 for d in kume if kalip_kayan_pencere(d, hedef) != kahin_en_kisa(d, hedef)) print(f"{tohum} {hedef:5d} {ad} {ayrilan:8d} {ayrilan / 40:.4f}") ``` ``` girdi 2: [-6, 15, 10, 11, 6, -5, -4, 3, 2, 17, -8, 5] kalip: 3 | kahin: 2 mutlak degerle: [6, 15, 10, 11, 6, 5, 4, 3, 2, 17, 8, 5] kalip: 2 | kahin: 2 tohum hedef on_kosul ayrilan/40 oran 20260218 25 saglaniyor 0 0.0000 20260218 25 bozuk 10 0.2500 20260218 15 saglaniyor 0 0.0000 20260218 15 bozuk 6 0.1500 20260219 25 saglaniyor 0 0.0000 20260219 25 bozuk 8 0.2000 20260219 15 saglaniyor 0 0.0000 20260219 15 bozuk 6 0.1500 ``` İkinci girdide kâhin **2** diyor, kalıp **3**. Doğru yanıt `15 + 10` çiftidir; kalıp bu çifti göremiyor, çünkü sol uç `-6` değerini düşürdüğünde toplam artmış ve pencere yanlış yerde sabitlenmiş. Kalıbın çıktısı yine bir uzunluk, yine akla yatkın, yine yanlış. **PK15.** İkinci dağarcık `20260219` tohumundan gelir. Ayrılan girdi oranı aynı büyüklük düzeninde kalmazsa sonuç dağarcığa bağlıdır ve öyle yazılır. İkinci dağarcıkta hedef 25 için ayrılan girdi **8**, birincide **10**; hedef 15 için ikisi de **6**. Dört ölçümün dördü de 0,15 ile 0,25 arasında, yani **aynı büyüklük düzeninde**. Sonuç dağarcığa bağlı değildir. Ön koşulun sağlandığı dört satırda ayrılan girdi **sıfırdır**. ## Ön koşul Pencerenin Değil, Kuralın Kayan pencere adı iki ayrı kalıbı birden anar ve ikisinin ön koşulu aynı değildir. Yukarıdaki biçim **değişken boyutludur**: pencere bir koşul sağlanana kadar büyür, sağlandığında küçülür. Bir de **sabit boyutlu** biçim vardır: pencere hep k geniştir, sağdan bir değer girer, soldan bir değer çıkar. Sabit boyutlu biçimde küçültme kuralı yoktur; pencere bir koşula bakarak daralmaz, yalnızca kayar. O hâlde toplamın tekdüze azalması da gerekmez. **PK16.** Sabit boyutlu pencere yalnız **artımlı toplam** kullanır: bir toplama, bir çıkarma. Kalıbın adımı k'dan bağımsızdır; kâhinin adımı k ile büyür. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=20260218): r = uretec(tohum) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_sabit(dizi, k, s): """Her pencerenin toplamini sifirdan hesaplar.""" en_iyi = None for i in range(len(dizi) - k + 1): toplam = 0 for j in range(i, i + k): s.say() toplam += dizi[j] if en_iyi is None or toplam > en_iyi: en_iyi = toplam return en_iyi def kalip_sabit(dizi, k, s): """Pencere sabit boyutlu: bir deger girer, bir deger cikar. Isaret on_kosulu yok.""" toplam, en_iyi = 0, None for sag in range(len(dizi)): s.say() toplam += dizi[sag] if sag >= k: toplam -= dizi[sag - k] if sag >= k - 1 and (en_iyi is None or toplam > en_iyi): en_iyi = toplam return en_iyi print("k girdi ayrilan/40 kalip kahin oran") for k in (3, 4, 6): for ad, hazirla in (("negatifsiz", lambda d: [abs(x) for x in d]), ("negatifli ", list)): ayrilan, ak, ah = 0, 0, 0 for dizi in dagarcik(): d = hazirla(dizi) s1, s2 = Sayac(), Sayac() ayrilan += (kalip_sabit(d, k, s1) != kahin_sabit(d, k, s2)) ak, ah = ak + s1.adim, ah + s2.adim print(f"{k} {ad} {ayrilan:12d} {ak:5d} {ah:5d} {ah / ak:5.2f}") ``` ``` k girdi ayrilan/40 kalip kahin oran 3 negatifsiz 0 480 1200 2.50 3 negatifli 0 480 1200 2.50 4 negatifsiz 0 480 1440 3.00 4 negatifli 0 480 1440 3.00 6 negatifsiz 0 480 1680 3.50 6 negatifli 0 480 1680 3.50 ``` Altı satırın altısında ayrılan girdi **sıfır**. Negatif değerler sabit boyutlu pencereyi hiç etkilemiyor; kalıbın adımı üç k değerinde de **480**, kâhinin adımı k ile büyüyor ve oran 2,50'den 3,50'ye çıkıyor. Bu, dersin yapısal sonucudur: **ön koşul kalıbın adına değil, kalıbın içindeki tek bir kurala aittir.** "Kayan pencere negatif değerle çalışmaz" cümlesi yanlıştır; doğru cümle, "toplamın tekdüze azaldığı varsayımına dayanan küçültme kuralı negatif değerle çalışmaz" cümlesidir. Bir kalıbı ön koşuluyla birlikte öğrenmek, kalıbın adını değil o kuralı bilmek demektir. ## Üç Sayı | Ölçüt | Kâhin | Kalıp | Ayrılan girdi | |---|---|---|---| | Değişken pencere, ön koşul sağlanıyor | 2396 adım | 867 adım | **0/40** | | Değişken pencere, ön koşul bozuk | 2462 adım | 761 adım | **10/40** | | Sabit pencere (k=4), negatifli girdi | 1440 adım | 480 adım | **0/40** | İkinci satır kalıbın en az adımı harcadığı satırdır ve tek bozuk satırdır. Üçüncü satır aynı girdiyle sıfır ayrılma veriyor, çünkü kalıp değişti. ## Denetim Doğruluğu Geri Alır, Hızlanmayı Almaz Ön koşulu denetlemek ucuzdur: bir dizide negatif değer aramak en çok n karşılaştırmadır ve ilk negatifte durur. Denetim başarısızsa iş kâhine bırakılır. Bu düzenlemenin doğruluğu tamdır; sorulması gereken, geriye ne kadar hızlanma kaldığıdır. **PK17.** Denetimli kalıp, denetimin adımlarını da kendi hanesine yazar; kâhine devredildiğinde kâhinin adımı da kalıbın adımına eklenir. ```python def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def dagarcik(tohum=20260218): r = uretec(tohum) return [[r(30) - 9 for _ in range(12)] for _ in range(40)] class Sayac: def __init__(self): self.adim = 0 def say(self): self.adim += 1 def kahin_en_kisa(dizi, hedef, s): en_iyi = None for i in range(len(dizi)): toplam = 0 for j in range(i, len(dizi)): s.say() toplam += dizi[j] if toplam >= hedef and (en_iyi is None or j - i + 1 < en_iyi): en_iyi = j - i + 1 break return en_iyi def kalip_kayan_pencere(dizi, hedef, s): sol, toplam, en_iyi = 0, 0, None for sag in range(len(dizi)): s.say() toplam += dizi[sag] while toplam >= hedef: if en_iyi is None or sag - sol + 1 < en_iyi: en_iyi = sag - sol + 1 toplam -= dizi[sol] sol += 1 s.say() return en_iyi def denetimli(dizi, hedef, s): """Onkosulu sinar; saglanmiyorsa kahine birakir.""" for x in dizi: s.say() if x < 0: return kahin_en_kisa(dizi, hedef, s) return kalip_kayan_pencere(dizi, hedef, s) for ad, hazirla in (("negatifsiz", lambda d: [abs(x) for x in d]), ("negatifli ", list)): ayrilan, ad_denetimli, ad_kahin = 0, 0, 0 for dizi in dagarcik(): d = hazirla(dizi) s1, s2 = Sayac(), Sayac() ayrilan += (denetimli(d, 25, s1) != kahin_en_kisa(d, 25, s2)) ad_denetimli += s1.adim ad_kahin += s2.adim print(f"{ad} ayrilan {ayrilan}/40 denetimli kalip {ad_denetimli:5d}" f" kahin {ad_kahin:5d} oran {ad_kahin / ad_denetimli:.2f}") ``` ``` negatifsiz ayrilan 0/40 denetimli kalip 1347 kahin 2396 oran 1.78 negatifli ayrilan 0/40 denetimli kalip 2568 kahin 2462 oran 0.96 ``` Ayrılan girdi iki satırda da **sıfır**. Ama ikinci satırın oranı **0,96**: negatifli dağarcıkta denetimli kalıp, kâhinden **daha çok** adım harcıyor. Bunun nedeni açıktır — kırk dizinin kırkı denetimden geçemiyor, iş kırk kez kâhine düşüyor ve denetimin 106 adımı üstüne biniyor. Ön koşulun sağlandığı dağarcıkta oran 1,78'de kalıyor, yani denetim orada bile 2,76'dan 1,78'e bir kayıp yazdırıyor. Buradan çıkan okuma şudur: **ön koşul denetimi bir doğruluk aracıdır, bir başarım aracı değildir.** Girdilerin hangi oranda ön koşulu sağladığı bilinmeden denetimli kalıbın kazandıracağı söylenemez; bu dağarcıkta o oran sıfırdır ve kalıp bütünüyle kâhine dönüşmüştür. ## Özet - Kayan pencere iki işaretçiyi aynı yönde tutar ve toplamı sıfırdan hesaplamak yerine artımlı günceller. - Değişken boyutlu biçimde küçültme kuralı, soldan değer düşüldüğünde toplamın azalacağını varsayar; bu varsayım yalnız negatif olmayan değerlerde doğrudur. - Negatif içeren dağarcıkta kalıp **10 girdide** kâhinden ayrılıyor ve bunu **daha az adımla** yapıyor; az adım doğruluk göstergesi değildir. - İkinci dağarcıkta ayrılan girdi 8; oran aynı büyüklük düzeninde kaldığı için sonuç dağarcığa bağlı değildir. - Sabit boyutlu pencere küçültme kuralı taşımadığı için negatif değerden etkilenmez: altı ölçümün altısında ayrılan girdi sıfırdır. ## Sonraki Adım İki kalıp da tek bir dizide, konum sayısı bilinerek çalıştı. Sonraki kalıp işaretçileri yine aynı yönde ilerletir ama **farklı hızlarda** ve uzunluğun bilinmediği bir yapıda: her düğümün bir ardılı vardır, sonu olup olmadığı bilinmez. Sonraki ders bu yapıda döngü tespitini ve orta elemanı ölçer; ön koşulu, ilerlemenin gerçekten tek yönlü olmasıdır ve o ön koşul bozulduğunda kalıp yalnız yanlış yanıt vermez, hiç durmayabilir.