--- title: 'Alıştırma Ortamlarını Kullanma' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/alistirma-ortamlarini-kullanma' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:29+00:00' license: 'CC BY-SA 4.0' --- # Alıştırma Ortamlarını Kullanma Tekrarlı çalışmanın ilerleme ölçütünün ortak tanımın beş kalıbı üzerinde sayılması: 144 problem çözen ortam beş kalıbı da görüyor ama denge oranı 0,2431, 30 problem çözen ortamda 0,6667. Önceki iki ders tek bir çözümle ilgiliydi: hangi kalıp seçilir, seçilen kalıp nasıl sınanır. Bu ders soruyu tek çözümün dışına taşır. Alıştırma tekrarlı bir iştir ve tekrarlı işin bir ilerleme ölçütü olmak zorundadır, yoksa çalışma sürer ama nereye gittiği bilinmez. Ortamlar **türleriyle** anılır, çünkü ölçülen şey ortamın kendisi değil, ürettiği **problem akışının biçimidir**. Sonuç iki adımda çıkar: çözülen problem sayısı bir ilerleme ölçütü değildir, kaç ayrı kalıp görüldüğü de değildir. ## Üç Ortam Türü **Havuz tabanlı alıştırma ortamında** çok sayıda problem durur ve seçimi çalışan yapar. Seçim serbest olduğu için tanıdık olana kayar; kalıp dağılımı çalışanın alışkanlığını yansıtır. **Zamanlı yarışma ortamında** kümeyi ortam belirler ve çalışan hepsini görmek zorundadır; küme küçüktür. **Şirket içi değerlendirmede** problem sayısı en azdır, dağılımı yine çalışan seçmez, girdiler hazırlanmamıştır. - **AD21** — Kalıp kümesi ortak tanımın beş kalıbıdır: iki işaretçi, kayan pencere, açgözlü, geri izleme, not alma. Kurs boyunca ölçülen kalıplar bunlardır. - **AD22** — Bir tur, ortamda geçirilen bir çalışma oturumudur. Tur başına problem sayısı ortam türüne göre sabittir: havuz 24, yarışma 5, değerlendirme 2. Altı tur ölçülür. - **AD23** — Havuz tabanlı ortamda seçimin ağırlığı 50, 30, 10, 6, 4'tür; diğer iki ortamda dağılım düzgündür. Ağırlık, çalışanın tanıdık kalıba dönme eğilimini modeller. - **AD24** — Seçim ortak tanımın belirlenimci üreteciyle yapılır; `random` kullanılmaz. - **AD25** — **Denge oranı**, en az görülen kalıbın sayısının eşit dağılımdaki paya bölümüdür. Beş kalıp eşit görülseydi oran 1,0000 olurdu. ```python """Uc ortam turunde kalip cesitliligi , ortak tanimin bes kalibi uzerinde.""" TOHUM, IKINCI = 20260218, 20260219 KALIP = ["iki isaretci", "kayan pencere", "acgozlu", "geri izleme", "not alma"] ORTAM = [("havuz tabanli alistirma ", 24, [50, 30, 10, 6, 4]), ("zamanli yarisma ", 5, [20, 20, 20, 20, 20]), ("sirket ici degerlendirme", 2, [20, 20, 20, 20, 20])] def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki def sec(r, agirlik): x = r(sum(agirlik)) for i, a in enumerate(agirlik): if x < a: return i x -= a return len(agirlik) - 1 def olcut(sayim): toplam = sum(sayim) esit = toplam / len(sayim) return {"problem": toplam, "kapsanan": sum(1 for c in sayim if c), "denge": round(min(sayim) / esit, 4), "bas_iki": round(sum(sorted(sayim)[-2:]) / toplam, 4)} def kosum(tohum, tur=6): print(f"tohum {tohum} , {tur} tur") print("ortam problem kapsanan denge bas iki dagilim") for ad, basina, agirlik in ORTAM: r = uretec(tohum) sayim = [0] * len(KALIP) for _ in range(tur * basina): sayim[sec(r, agirlik)] += 1 o = olcut(sayim) print(f"{ad} {o['problem']:7d} {o['kapsanan']:8d} {o['denge']:6.4f}" f" {o['bas_iki']:7.4f} {sayim}") kosum(TOHUM) print() kosum(IKINCI) print() print("havuz tabanli ortam , tur tur birikimli (tohum 20260218)") print("tur problem kapsanan denge bas iki") r = uretec(TOHUM) sayim = [0] * len(KALIP) for t in range(1, 7): for _ in range(24): sayim[sec(r, ORTAM[0][2])] += 1 o = olcut(sayim) print(f"{t:3d} {o['problem']:7d} {o['kapsanan']:8d} {o['denge']:6.4f}" f" {o['bas_iki']:7.4f}") ``` ``` tohum 20260218 , 6 tur ortam problem kapsanan denge bas iki dagilim havuz tabanli alistirma 144 5 0.2431 0.7986 [64, 51, 11, 11, 7] zamanli yarisma 30 5 0.6667 0.5000 [4, 5, 9, 6, 6] sirket ici degerlendirme 12 5 0.4167 0.5833 [1, 4, 3, 2, 2] tohum 20260219 , 6 tur ortam problem kapsanan denge bas iki dagilim havuz tabanli alistirma 144 5 0.1389 0.8194 [76, 42, 16, 6, 4] zamanli yarisma 30 5 0.6667 0.5667 [8, 4, 9, 4, 5] sirket ici degerlendirme 12 5 0.4167 0.6667 [1, 1, 5, 2, 3] havuz tabanli ortam , tur tur birikimli (tohum 20260218) tur problem kapsanan denge bas iki 1 24 4 0.0000 0.8333 2 48 5 0.2083 0.7917 3 72 5 0.2778 0.7639 4 96 5 0.2604 0.7500 5 120 5 0.2500 0.7750 6 144 5 0.2431 0.7986 ``` Birinci tablo iki ölçütü aynı anda çürütüyor. Havuz tabanlı ortam **144**, zamanlı yarışma **30**, şirket içi değerlendirme **12** problem çözüyor — arada 12 kat fark var. Buna karşılık **kapsanan kalıp sayısı üçünde de 5**. Yani iki soru da ortamları ayırt etmiyor: "kaç problem çözdüm" 12 kat sapıyor, "kaç ayrı kalıp gördüm" hiç oynamıyor. Ayırt eden ölçüt dağılımdır. Havuz tabanlı ortamda denge oranı **0,2431**: en az görülen kalıp, eşit dağılımdaki payının dörtte birinden azını alıyor ve en çok görülen iki kalıp problemlerin **0,7986'sını** kaplıyor. Zamanlı yarışma 30 problemle **0,6667** denge veriyor — beş kat az problemle **2,74 kat** dengeli. Şirket içi değerlendirmedeki 0,4167 ise dağılımdan değil, örneklemin küçüklüğünden gelir. Üçüncü tablo dersin en aykırı sonucudur. Havuz tabanlı ortamda kapsama **ikinci turda** 5'e çıkıyor ve bir daha hiç değişmiyor: üçüncü turdan altıncı tura kadar çözülen 72 problem kapsama ölçütüne **hiçbir şey eklemiyor**. Denge oranı ise üçüncü turda 0,2778 ile en yüksek noktasına çıkıp sonra **düşüyor** — dördüncü turda 0,2604, altıncı turda 0,2431. Problem sayısı artarken ilerleme ölçütü geriliyor, çünkü eklenen her problem baskın iki kalıba gidiyor. İkinci dağarcık sıralamayı doğruluyor: `20260219` tohumunda havuz 0,1389, yarışma 0,6667, değerlendirme 0,4167. Havuzun değeri 0,2431'den 0,1389'a düşüyor, yani **mutlak değer dağarcığa bağlıdır**; ama üç ortamın sırası ve havuz ile yarışma arasındaki büyüklük farkı iki dağarcıkta da aynı yönde. ## Ortam Hatayı Gösteriyor mu Dağılım tek başına da yetmez. Bir kalıbı elli kez uygulamak, o kalıbın **ön koşulu bozulduğunda ne yaptığını** göstermez — ortak tanımın birinci okuması bunu zaten kanıtladı: ön koşul sağlanan 40 girdinin 40'ında iki işaretçi kâhinle aynı yanıtı veriyor; ön koşulu sağlayan girdilerle dolu bir ortamda çalışan biri kalıbın yanlışını **hiç görmez**. Burada ölçülen şey ortamın karışımıdır: girdilerin yüzde kaçı ön koşulu sağlıyor, ve bu oran görülen yanlış yanıt sayısını nasıl değiştiriyor. İki seçim politikası karşılaştırılır. - **AD26** — Havuz tabanlı ortamda girdilerin **yüzde 90'ı**, zamanlı yarışmada **yüzde 75'i**, şirket içi değerlendirmede **yüzde 50'si** ön koşulu sağlar. Havuzda problemler kalıba göre hazırlanmıştır, değerlendirmede girdi olduğu gibi gelir. - **AD27** — **Alışkanlıkla seçim**, en çok pratik edilen kalıbı her probleme uygular ve ön koşulu sınamaz. - **AD28** — **Ön koşul kontrolüyle seçim**, önce girdinin sıralı olup olmadığına bakar; sıralı değilse kalıbı uygulamaz, kâhine düşer. Sınama en fazla $n-1$ adımdır ve ilk aykırı çiftte durur. - **AD29** — Her ortamda 40 problem çözülür ve hedef 11'dir. ```python """Iki secim politikasi , kahin karsisinda , uc ortam karisimi.""" TOHUM, IKINCI = 20260218, 20260219 def uretec(tohum): d = tohum def sonraki(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return sonraki class Sayac: def __init__(self): self.adim = 0 def say(self, n=1): self.adim += n def karisim(sirali_oran, tohum=TOHUM, n=40, uzunluk=12): """sirali_oran: girdilerin yuzde kaci on_kosulu sagliyor.""" r = uretec(tohum) kume = [] for _ in range(n): dizi = [r(30) - 9 for _ in range(uzunluk)] kume.append(sorted(dizi) if r(100) < sirali_oran else dizi) return kume def kahin_ciftler(dizi, hedef, s): 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 iki_isaretci(dizi, hedef, s): sol, sag = 0, len(dizi) - 1 while sol < sag: s.say() t = dizi[sol] + dizi[sag] if t == hedef: return True sol, sag = (sol + 1, sag) if t < hedef else (sol, sag - 1) return False def aliskanlik(dizi, hedef, s): """En cok pratik edilen kalibi her probleme uygular.""" return iki_isaretci(dizi, hedef, s) def on_kosul_kontrolu(dizi, hedef, s): """Once on_kosulu sinar; saglanmiyorsa kahine duser.""" for i in range(len(dizi) - 1): s.say() if dizi[i] > dizi[i + 1]: return kahin_ciftler(dizi, hedef, s) return iki_isaretci(dizi, hedef, s) def olc(politika, kume, hedef=11): ayrilan, ak, ah = 0, 0, 0 for dizi in kume: s1, s2 = Sayac(), Sayac() a = politika(list(dizi), hedef, s1) b = kahin_ciftler(list(dizi), hedef, s2) ak, ah = ak + s1.adim, ah + s2.adim if a != b: ayrilan += 1 return ayrilan, ak, ah ORTAM = [("havuz tabanli alistirma ", 90), ("zamanli yarisma ", 75), ("sirket ici degerlendirme", 50)] for tohum in (TOHUM, IKINCI): print(f"tohum {tohum} , her ortamda 40 problem , hedef 11") print("ortam sirali aliskanlik on_kosul kontrolu kahin") print(" girdi ayrilan adim ayrilan adim adim") for ad, oran in ORTAM: K = karisim(oran, tohum) s = sum(1 for d in K if d == sorted(d)) a1, k1, h1 = olc(aliskanlik, K) a2, k2, _ = olc(on_kosul_kontrolu, K) print(f"{ad} {s:6d} {a1:7d} {k1:4d} {a2:7d} {k2:4d} {h1:4d}") print() ``` ``` tohum 20260218 , her ortamda 40 problem , hedef 11 ortam sirali aliskanlik on_kosul kontrolu kahin girdi ayrilan adim ayrilan adim adim havuz tabanli alistirma 34 5 165 0 600 834 zamanli yarisma 29 8 199 0 681 914 sirket ici degerlendirme 17 15 255 0 754 856 tohum 20260219 , her ortamda 40 problem , hedef 11 ortam sirali aliskanlik on_kosul kontrolu kahin girdi ayrilan adim ayrilan adim adim havuz tabanli alistirma 36 2 213 0 609 1055 zamanli yarisma 31 4 238 0 691 1079 sirket ici degerlendirme 22 10 296 0 823 1161 ``` Üç sayı yan yana. **Kâhin:** havuz karışımında 834 adım, 40 girdinin 40'ında doğru. **Kalıp:** alışkanlıkla seçim 165 adım, ön koşul kontrolüyle seçim 600 adım. **Ayrılan girdi:** alışkanlıkla seçim havuzda **5**, yarışmada **8**, değerlendirmede **15**; ön koşul kontrolü üç ortamda da **0**. Birinci okuma ortamla ilgilidir. Aynı politika, aynı kalıp, aynı problem sayısı — ve gördüğü yanlış yanıt sayısı 5'ten 15'e, **üç katına** çıkıyor. Farkı yaratan tek şey ortamın girdi karışımıdır: havuzda 40 girdinin 34'ü ön koşulu sağlıyor, değerlendirmede 17'si. Hazırlanmış girdilerle çalışan biri kalıbının yanlışını daha az görür, ve az görmek düzelmek değildir. İkinci okuma politikayla ilgilidir. Ön koşul kontrolü üç ortamda da **0 ayrılan girdi** veriyor, yani hiç yanılmıyor; bedeli havuz karışımında 165 adımdan **600 adıma** çıkmak, yani **3,64 kat**. Buna karşılık kâhinin 834 adımının hâlâ altında: kontrol, doğruluğu kaba kuvvet pahasına değil, **kaba kuvvetin yüzde 72'si** pahasına satın alıyor. İkinci dağarcık aynı sıralamayı veriyor (2, 4, 10) ve ön koşul kontrolü orada da üç ortamda 0 ayrılan girdi üretiyor; mutlak sayılar dağarcığa bağlı, sıralama değil. Buradan tekrarlı çalışmanın ilerleme ölçütü çıkar ve üç sayıdan oluşur: **kaç kalıp görüldü**, **dağılımın denge oranı**, ve **kaç kalıp ön koşulu bozulmuş hâlde görüldü**. Çözülen problem sayısı bu üçünün hiçbirini vermez. ## Özet - Ortamlar türleriyle ayrılır: havuz tabanlı alıştırmada dağılımı çalışan seçer, zamanlı yarışmada ve şirket içi değerlendirmede ortam seçer ve küme küçüktür. - Çözülen problem sayısı ortamları 12 kat ayırıyor (144, 30, 12) ama kapsanan kalıp sayısı üçünde de 5; iki ölçüt de ilerlemeyi göstermiyor. - Ayırt eden ölçüt dağılımdır: havuz tabanlı ortamda denge oranı 0,2431 ve baskın iki kalıp problemlerin 0,7986'sını kaplıyor; zamanlı yarışma beş kat az problemle 0,6667 veriyor. - Kapsama ikinci turda 5'e çıkıp donuyor, denge oranı üçüncü turda 0,2778 ile tepe yapıp 0,2431'e **geriliyor** — problem eklemek ölçütü kötüleştirebiliyor. - Ortamın girdi karışımı görülen yanlışı belirliyor: aynı politika havuzda 5, yarışmada 8, şirket içi değerlendirmede 15 ayrılan girdi üretiyor. - Ön koşul kontrolüyle seçim üç ortamda da 0 ayrılan girdi veriyor; bedeli 165 adımdan 600 adıma çıkmak, yani kâhinin 834 adımının yüzde 72'si. ## Kurs Kapanışı Yirmi üç ders tek bir soruyu sordu: bir kalıp seçmek neyi kabul etmektir. Yanıt her derste üç sayıyla verildi. **Kâhin** her zaman kaba kuvvetti ve her zaman doğruydu — ama **her zaman pahalı değildi**: `En Uzun Yol Problemi` sekiz düğümde kâhini 562, kalıbı 3626 adımda ölçtü ve eşiğin on düğümde olduğunu gösterdi. **Kalıp** genellikle daha az adım harcadı. **Ayrılan girdi**, kalıbın kâhinden farklı yanıt verdiği girdi sayısıydı. Kursun kuralı buydu: 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**. | Ders | Kâhin (adım) | Kalıp (adım) | Ayrılan girdi / bedel | |---|---|---|---| | Kaba Kuvvet | tam sayım **2640** | eleme 866 | eleme **0**; örnekleme 406'da **14** | | Böl ve Yönet | **3120** | doğrusal birleştirme **2680** | **0**; eksik birleştirme 920'de **40/40** | | Açgözlü Algoritmalar | alttan yukarı | açgözlü | **969 sistemin 827'si** (0,8535); en büyük fazlalık **16 para** | | Dinamik Programlama | **163.840** | tam anahtarlı not alma **2440** (67,15 kat az) | **0**; eksik anahtar **39/40**; örtüşme yokken defter 19 giriş boşa | | Geri İzleme | budamasız **960.800** düğüm, n=7 | budamalı **552** düğüm | **1740,6 kat**, oran n ile büyür (72,3 → 8156,2); aşırı budama 0 çözüm | | Rastgeleleştirme | **780** | doğrulamalı örnekleme **944–1056** | **0**; doğrulamasız 200'de, ön koşul bozukken **40/40** | | İki İşaretçi | **972** | **154** (6,31 kat az) | sırasızda **25/40**, hızlanma **2,33 kata** | | Kayan Pencere | **2396** | **867** (2,76 kat az) | negatifte **10/40**, **daha az adımda** | | Hızlı ve Yavaş İşaretçi | **480** | **299** | ikinci kenarda **14/40**; adım **hiç değişmez** | | Aralık Birleştirme | başlangıca göre sıralama: **40/40** doğru | **2154** | bitişe göre **29/40**, uzunluğa göre ve sıralamasız **40/40** | | Döngüsel Yerleştirme | 1..n, tekrarsız | karşılaştırmasız | tekrarlıda yalın **40/40**, korumalı **39/40**, eksikte **0/40** | | İki Yığın | **480** ortanca | denge adımıyla **1261** | dengesiz **295/480** yanlış; denge kalıbın **yarısından fazlası** (1261/550) | | K'ıncı Eleman | dört k x 40 girdi | k boyutlu yığın | **0/40**; "k'ıncı ayrı değer" ayrı sorudur: **27/40** | | Izgara Gezinmesi | aynı komşulukla **40/40** | bağlı bileşen | tanımlar ayrılınca **38/40** | | Sırt Çantası | bölünebilirde **100.800** | açgözlü **174** | bölünebilirde **0/40**; aynı sıra 0/1'de **5/40**, kayıp 7 | | Gezgin Satıcı | **352.800** (20 örnek) | en yakın komşu **560** | **17/20**; sapma ort. 9,3, **en kötü 33,33**; iki değişim 2/20 | | En Uzun Yol | çevrimsizde **40/40** | gevşetme yordamı | çevrimlide **38/40**; en büyük fazla tahmin **228** | | N Vezir | budamalı **2057** düğüm, n=8 | simetri elemesiyle **1029** | oran **2,00**, beş boyda sabit; budamanınki büyür, simetrininki **büyümez** | | At Turu ve Labirent | yol modeli **90.111** | hücre modeli **25** | oran **3604**, ayrılan **0** | | Hamilton Yolları | sayma **29.270** | karar **1526** | oran **19,18**; yol bulunmayanların **hepsinde** karar = sayma | | Problem Okuma ve Kısıt | **866** | karma tablo **486**, sıralayan kalıp **1398**, sayma **396** | yanlış kısıt okuması 40 girdinin **18'inde** ayrılıyor (ikinci dağarcıkta 17); n=108'de üç çözüm de bütçeye sığmıyor | | Çözüm Doğrulama | kaba kuvvet, 52 girdide **1596** | doğru iki işaretçi **329** | 40 rastgele girdi 5 kusurun **4'ünü**, 12 kenar durumu **5'ini** yakalıyor; aynı kusuru paylaşan kâhinde ayrılan **3'ten 0'a** düşüyor | | Alıştırma Ortamları | **834** | alışkanlıkla seçim **165**, ön koşul kontrolü **600** | havuzda **5**, yarışmada **8**, değerlendirmede **15** ayrılan girdi; ön koşul kontrolü 0 ayrılan ama 3,64 kat adım | Tablonun ikinci okuması birincisinden değerlidir: **hızlandırma yanlışa yaklaştırır ve bazen hızlandırmaz bile.** Sırasız girdide iki işaretçinin hızlanması 2,33 kata düşerken 25 girdide yanılıyor; açgözlü 969 sistemin 827'sinde fazla veriyor; not alma örtüşme yokken 19 girişi boşa tutuyor. Hiçbiri saklanmadı: bir kalıbın ne zaman yanıldığını bilmeyen, onu ne zaman seçeceğini de bilemez. Üçüncü ve kalıcı sonuç kâhinin kendisiyle ilgilidir: **kaba kuvvet bir taban değil, bir kâhindir.** Kursun bütün sayıları onun sayesinde yazılabildi. Son derste bu bir alışkanlığa döndü: doğruluğu bir görüşe değil, ikinci bir çözümün yanıtına karşı saymak. Bir sonraki kurs, **Hesaplama Kuramı**, kâhinin gölgesinde bırakılan soruyu alır. Gezgin satıcı ve Hamilton yolları derslerinde "bu problem neden zor" sorusu açıkça ertelendi. Orada sorulacak olan şudur: bazı problemler için kaba kuvvetten daha iyisinin bilinmemesi, **bilgimiz hakkında mı yoksa problemler hakkında mı** bir gerçektir. Yanıt karar verilebilirlik, indirgeme ve karmaşıklık sınıflarıyla verilecek.