--- title: Algoritmalar source: 'https://academia.sh/tr/kurslar/algoritmalar' language: tr updated: '2026-08-17T04:39:26+00:00' license: 'CC BY-SA 4.0' lessons: 25 outcomes: - 'Bir algoritmanın zaman ve alan karmaşıklığını asimptotik gösterimle ifade eder' - 'Sıralama ve arama algoritmalarını doğruluk ve maliyet ekseninde karşılaştırır' - 'Klasik çizge ve metin algoritmalarını uygun problemlere uygular' --- # Algoritmalar Asimptotik çözümlemeden sıralama, arama, çizge ve metin algoritmalarına; çözümlerin doğruluk ve maliyet ekseninde karşılaştırılması. ## Algoritma Çözümlemesi Algoritma ölçütleri, asimptotik gösterimler, karmaşıklık sınıfları ve maliyet hesaplama yöntemleri. ### Algoritma Nedir Source: https://academia.sh/tr/kurslar/algoritmalar/algoritma-nedir Algoritmanın ölçütleri, doğruluk ve sonlanma ayrımı, hesaplama modeli ve neden süre ölçmenin yetmediği. Veri Yapıları kursu, verinin nasıl düzenlendiğini ve bu düzenin maliyeti nasıl belirlediğini kurdu. Maliyet ifadeleri — $O(1)$, $O(\log n)$, $O(n)$ — kullanıldı ama tanımlanmadı; yalnızca "veri büyüdükçe maliyetin hangi hızla arttığı" biçiminde sezgisel olarak anlatıldı. Bu kurs o boşluğu kapatır ve soruyu tersine çevirir: veri değil **çözüm** incelenir. Aynı problemin farklı çözümleri nasıl karşılaştırılır ve karşılaştırma neye göre yapılır? #### Algoritmanın Ölçütleri **Algoritma**, bir problemi çözen sonlu adımlar dizisidir. Tanım bu kadar kısa olsa da, bir yöntemin algoritma sayılması için beş ölçüt aranır: **Girdi.** Sıfır veya daha çok, iyi tanımlanmış girdi alır. **Çıktı.** En az bir çıktı üretir ve bu çıktı girdiyle ilişkilidir. **Belirlilik.** Her adım tek anlamlıdır; aynı girdi aynı adımları aynı sırayla yürütür. Programlama Temelleri kursundaki belirlilik tartışması buraya bağlanır. **Sonluluk.** Her geçerli girdi için sonlu adımda durur. Sonsuz döngüye giren bir yöntem algoritma değildir. **Etkinlik.** Her adım, sonlu sürede ve tanımlı araçlarla uygulanabilir olmalıdır. "Doğru yanıtı bul" bir adım değildir; "diziyi baştan sona tara" adımdır. Beş ölçüt, gündelik dilde "algoritma" denen her şeyi kapsamaz. Rastgeleleştirilmiş yöntemler belirlilik ölçütünü gevşetir; yaklaşık yöntemler çıktının kesinliğini gevşetir. Bu gevşetmeler, ilgili yerlerde açıkça belirtilir. #### Problem, Örnek ve Program Üç kavram sık karıştırılır ve ayrımları kursun geri kalanında varsayılır. **Problem**, girdilerle kabul edilebilir çıktılar arasındaki ilişkinin belirtimidir: "girdi, tam sayılardan oluşan bir dizidir; çıktı, aynı elemanların azalmayan sırada dizilmiş hâlidir." Belirtim bir yöntem söylemez, yalnızca neyin doğru sayılacağını söyler. **Örnek (instance)**, problemin tek bir girdisidir: `[5, 2, 9]` dizisi bir örnektir. Bir algoritma, tek bir örneği değil **tüm** örnekleri çözmelidir; belirli bir girdide doğru yanıt vermek yeterli değildir. **Program**, bir algoritmanın belirli bir dilde, belirli bir makine için yazılmış gerçekleştirimidir. Aynı algoritmanın sayısız programı olabilir; hepsi aynı adımları izlediği sürece aynı algoritmadır. Bu ayrım, doğruluğun neye göre ölçüldüğünü belirler: bir algoritma programa göre değil, **problem belirtimine** göre doğrudur. Bu nedenle algoritmalar genellikle sözde kodla yazılır — dil ayrıntıları belirtimle ilgisizdir. #### Doğruluk İki Parçalıdır Bir algoritmanın doğru olduğunu söylemek iki ayrı iddiada bulunmaktır: **Kısmi doğruluk:** Algoritma **durursa**, sonuç doğrudur. **Sonlanma:** Algoritma her geçerli girdi için durur. İkisi birlikte **tam doğruluk** verir. Ayrım, ispatların da iki ayrı parçaya bölünmesini sağlar ve bu bölme pratikte işe yarar — biri sağlanıp diğeri sağlanmayan yöntemler vardır. Kısmi doğruluğun standart aracı, Programlama Temelleri kursunda tanıtılan **döngü değişmezidir**: döngüye girmeden önce doğru, her tur korunuyor ve döngü bittiğinde istenen sonucu veriyorsa, kısmi doğruluk kanıtlanmıştır. Sonlanmanın standart aracı ise **azalan bir büyüklüktür**: her turda kesin olarak azalan ve alttan sınırlı bir değer bulunursa, döngü sonsuza kadar süremez. ```python def en_buyugu_bul(olcumler: list[int]) -> int: """En büyük ölçümü döndürür. Liste boş olmamalıdır. Değişmez: her turun başında `en_buyuk`, o ana kadar gezilen elemanların en büyüğüdür. Sonlanma: kalan eleman sayısı her turda bir azalır. """ en_buyuk = olcumler[0] for olcum in olcumler: if olcum > en_buyuk: en_buyuk = olcum return en_buyuk print(en_buyugu_bul([12, 18, 7, 25, 14])) # 25 ``` Belgedeki iki satır süs değildir: biri kısmi doğruluğun, diğeri sonlanmanın gerekçesidir. Bir algoritmanın doğru olduğunu göstermek, bu iki cümleyi yazabilmektir. #### Aynı Problem, Farklı Algoritmalar Bir problemin birden çok çözümü olabilir ve çözümler yalnızca hızda değil, **yapıda** farklılaşır. ```python def toplam_dongu(n: int) -> int: """1'den n'e kadar sayıların toplamı; her sayı ayrı ayrı eklenir.""" toplam = 0 for i in range(1, n + 1): toplam += i return toplam def toplam_formul(n: int) -> int: """Aynı toplam; kapalı formülle tek adımda.""" return n * (n + 1) // 2 print(toplam_dongu(100), toplam_formul(100)) # 5050 5050 print(toplam_dongu(1_000_000) == toplam_formul(1_000_000)) # True ``` İki işlev aynı sonucu verir. Birincisi $n$ toplama yapar; ikincisi bir çarpma, bir toplama ve bir bölme yapar — girdi ne olursa olsun. Fark, bir eniyileme ayrıntısı değildir: birinci çözümün maliyeti girdiyle büyür, ikincisi büyümez. Bir milyon için birincisi bir milyon işlem, ikincisi üç işlem yapar. Bu, kursun temel sorusunu somutlaştırır: iki çözüm arasındaki farkı **nasıl ölçeriz**? #### Süre Ölçmek Neden Yetmez Akla ilk gelen ölçüt, çalışma süresidir. Ancak süre üç etkene birden bağlıdır ve bunların hiçbiri algoritmanın kendisine ait değildir. **Donanım.** Aynı program farklı işlemcilerde farklı sürer; Bilgisayarlar Nasıl Çalışır kursundaki bellek hiyerarşisi bu farkın kaynaklarından biriydi. **Gerçekleştirim.** Dil, derleyici ve çalışma zamanı seçimleri süreyi kat kat değiştirir. Veri Yapıları kursundaki önbellek ölçümünde bu etki, ölçülmek isteneni gizleyecek kadar büyüktü. **Girdi.** Aynı algoritma farklı girdilerde farklı sürer; sıralı bir dizi ile karışık bir dizi aynı sıralama algoritmasında bambaşka davranır. Ölçüm bu nedenle bir algoritmanın **özelliği** değil, belirli bir çalıştırmanın gözlemidir. Karşılaştırmanın taşınabilir olması için, donanımdan ve dilden bağımsız bir ölçüt gerekir. #### Hesaplama Modeli ve İşlem Sayımı Çözüm, soyut bir **hesaplama modeli** benimsemektir. Bu kursta kullanılan model şu varsayımlara dayanır: - Temel işlemler — toplama, karşılaştırma, atama, dizin erişimi — sabit sürede yapılır. - Bellek erişimi konumdan bağımsız olarak aynı maliyettedir. - İşlemler sırayla yürütülür. Model, gerçekliğin sadeleştirilmiş hâlidir: önbellek katmanları ve komut boru hattı yok sayılır. Karşılığında, algoritmalar donanımdan bağımsız karşılaştırılabilir hâle gelir. Ölçüt de buradan çıkar: **girdi büyüklüğüne göre yapılan temel işlem sayısı.** ```python def dogrusal_arama(dizi: list[int], hedef: int) -> tuple[int, int]: """(bulunan dizin veya -1, karşılaştırma sayısı) döndürür.""" karsilastirma = 0 for i, deger in enumerate(dizi): karsilastirma += 1 if deger == hedef: return i, karsilastirma return -1, karsilastirma dizi = list(range(1000)) print(dogrusal_arama(dizi, 0)) # (0, 1) — en iyi durum print(dogrusal_arama(dizi, 999)) # (999, 1000) — en kötü durum print(dogrusal_arama(dizi, -1)) # (-1, 1000) — bulunamadı ``` Aynı algoritma, aynı girdi boyutunda 1 ile 1000 arasında değişen sayıda işlem yapar. Bu nedenle tek bir sayı yerine üç ayrı ölçüt tanımlanır: - **En iyi durum:** En az işlem gerektiren girdi. - **En kötü durum:** En çok işlem gerektiren girdi. - **Ortalama durum:** Girdilerin bir olasılık dağılımı üzerinden beklenen işlem sayısı. Varsayılan ölçüt **en kötü durumdur**; bir güvence verir ve dağılım varsayımı gerektirmez. Ortalama durum, dağılım gerçekten biliniyorsa anlamlıdır — karma tablosunun "ortalama sabit" vaadi tam olarak böyle bir iddiaydı. #### Özet - Algoritma; girdi, çıktı, belirlilik, sonluluk ve etkinlik ölçütlerini sağlayan sonlu adımlar dizisidir. - Problem bir belirtimdir, örnek tek bir girdidir, program bir gerçekleştirimdir; doğruluk belirtime göre ölçülür. - Doğruluk iki parçadır: kısmi doğruluk (durursa sonuç doğru) döngü değişmeziyle, sonlanma (her girdide durur) azalan bir büyüklükle gerekçelendirilir. - Aynı problemin çözümleri yapı olarak farklılaşır; fark, maliyetin girdiyle büyüyüp büyümemesinde ortaya çıkar. - Çalışma süresi donanıma, gerçekleştirime ve girdiye bağlıdır; algoritmanın özelliği değildir. - Ölçüt, soyut bir modelde girdi büyüklüğüne göre yapılan temel işlem sayısıdır ve en iyi, en kötü ile ortalama durum ayrı ayrı ele alınır. #### Sonraki Adım İşlem sayımı doğru yönde bir adımdır ama hâlâ ayrıntıya boğulur: bin elemanlık dizide 1000 mü, 1002 mi karşılaştırma yapıldığı önemsizdir. Sonraki ders, bu ayrıntıyı eleyip yalnızca büyüme hızını tutan gösterimi — asimptotik gösterimi — biçimsel olarak tanımlayacak. ### Asimptotik Gösterim Source: https://academia.sh/tr/kurslar/algoritmalar/asimptotik-gosterim Büyük O, büyük omega ve büyük teta tanımları, sabitlerin elenmesi, toplam ve çarpım kuralları, yaygın yanlış okumalar. Önceki ders, ölçütü işlem sayısı olarak belirledi ama bir sorun bıraktı: bin elemanlık bir dizide 1000 mü, 1002 mi karşılaştırma yapıldığı önemsizdir. Bu ayrıntılar gerçekleştirime bağlıdır; algoritmanın kendisine ait olan, **girdi büyüdükçe işlem sayısının hangi hızla arttığıdır**. Asimptotik gösterim, bu hızı yakalayan ve gerisini eleyen dildir. #### Büyük O: Üst Sınır $f$ ve $g$, pozitif tam sayılardan pozitif gerçel sayılara fonksiyonlar olsun. $$ f(n) = O(g(n)) \iff \exists\, c > 0,\ n_0 \in \mathbb{N} : \forall n \geq n_0,\ f(n) \leq c \cdot g(n) $$ Sözle: **yeterince büyük** her $n$ için $f$, $g$'nin sabit bir katını aşmıyorsa, $f$ en fazla $g$ kadar hızlı büyür. Tanımın iki niceleyicisi de gereklidir. Sabit $c$, çarpansal farkları eler — iki katı hızlı çalışan bir gerçekleştirim aynı sınıfta kalır. Eşik $n_0$ ise küçük girdilerdeki düzensizlikleri eler; asimptotik ifade, büyük girdiler hakkında bir iddiadır. Bir örnek üzerinde açıkça gösterilebilir. $f(n) = 3n^2 + 5n + 20$ için $g(n) = n^2$ seçilirse, $c = 4$ ve $n_0 = 8$ değerleri tanımı sağlar: ```python def f(n: int) -> int: return 3 * n**2 + 5 * n + 20 c, n0 = 4, 8 print(f(7) <= c * 7**2) # False — eşiğin altında sağlanmıyor print(f(8) <= c * 8**2) # True print(all(f(n) <= c * n**2 for n in range(n0, 10_000))) # True ``` Yedide sağlanmaması bir sorun değildir: tanım, **eşikten sonrası** için bir şey söyler. Sekizden itibaren eşitsizlik hep geçerlidir; dolayısıyla $3n^2 + 5n + 20 = O(n^2)$ yazılır. #### Büyük Omega: Alt Sınır $$ f(n) = \Omega(g(n)) \iff \exists\, c > 0,\ n_0 : \forall n \geq n_0,\ f(n) \geq c \cdot g(n) $$ Büyük O bir tavan, büyük omega bir taban verir. "Bu algoritma en az şu kadar iş yapar" demek için kullanılır. Alt sınırlar, tek bir algoritma için değil **problem** için konuşulduğunda güçlüdür: "karşılaştırmalı sıralama en az $\Omega(n \log n)$ karşılaştırma gerektirir" ifadesi, hiçbir karşılaştırmalı algoritmanın bu sınırın altına inemeyeceğini söyler. Bu tür bir sonuç, arama ve sıralama konusunda kanıt fikriyle birlikte ele alınacaktır. #### Büyük Teta: Sıkı Sınır $$ f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \ \text{ ve } \ f(n) = \Omega(g(n)) $$ Teta, büyümenin **tam olarak** $g$ mertebesinde olduğunu söyler: hem tavan hem taban aynı fonksiyondur. $3n^2 + 5n + 20$ ifadesi $\Theta(n^2)$'dir. Aynı ifade $O(n^3)$ de olur — üst sınır gevşek olabilir — ancak $\Theta(n^3)$ değildir. Günlük kullanımda büyük O, çoğu zaman sıkı sınır kastedilerek yazılır. Bu bir kolaylıktır; kesin konuşulması gereken yerlerde teta tercih edilir. #### Sadeleştirme Kuralları Karmaşıklık ifadeleri birkaç kuralla sadeleşir. **Sabit çarpanlar elenir.** $O(3n) = O(n)$. Sabit, tanımdaki $c$ tarafından zaten soğurulur. **Toplamda büyük terim kalır.** $O(n^2 + n) = O(n^2)$. Ardışık iki bölümden pahalı olanı belirleyicidir. **Çarpımda çarpanlar korunur.** İç içe döngülerde maliyetler çarpılır: $O(n) \cdot O(\log n) = O(n \log n)$. **Geçişlilik geçerlidir.** $f = O(g)$ ve $g = O(h)$ ise $f = O(h)$'dir. | İfade | Sadeleşmiş | Gerekçe | |---|---|---| | $5n + 100$ | $O(n)$ | Sabitler ve sabit terim elenir | | $n^2 + 1000n$ | $O(n^2)$ | Büyük terim baskın | | $\log_2 n$ ile $\log_{10} n$ | Aynı $O(\log n)$ | Taban değişimi sabit çarpandır | | $2^{n+1}$ | $O(2^n)$ | $2^{n+1} = 2 \cdot 2^n$ | | $n! $ ile $2^n$ | Farklı sınıflar | Faktöriyel üstelden hızlı büyür | Üçüncü satır sık sorulan bir noktayı yanıtlar: logaritmanın tabanı belirtilmez, çünkü taban değişimi yalnızca sabit bir çarpan üretir ve o çarpan elenir. #### Sabit ve Eşiği Bulmak Bir iddiayı kanıtlamak, uygun bir $c$ ve $n_0$ **üretmek** demektir. Polinomlar için mekanik bir yöntem vardır: her düşük dereceli terim, $n \geq 1$ için baskın terimle sınırlanır ve katsayılar toplanır. $f(n) = 3n^2 + 5n + 20$ örneğinde $n \geq 1$ için $5n \leq 5n^2$ ve $20 \leq 20n^2$ yazılabilir. Toplandığında $f(n) \leq 28n^2$ çıkar; yani $c = 28$, $n_0 = 1$ da tanımı sağlayan geçerli bir çifttir. Yukarıda $c = 4$ ile daha küçük bir sabit bulundu, ama gerekli değildi: tanım **bir** çiftin varlığını ister, en küçüğünü değil. Bu, asimptotik iddiaların neden kolay kanıtlandığını açıklar — kaba bir sınır bile yeterlidir. #### Yaygın Yanlış Okumalar **"$O(n)$ demek, tam olarak $n$ işlem demek değildir."** Üst sınırdır; $3n$ ve $n/2$ ikisi de $O(n)$'dir. **"$O$ en kötü durum demek değildir."** İkisi ayrı eksenlerdir. En iyi, en kötü ve ortalama durumların her biri için ayrı ayrı $O$, $\Omega$ ve $\Theta$ yazılabilir. "En kötü durumda $O(n^2)$" ile "her durumda $O(n^2)$" farklı iddialardır. **"Küçük $O$ her zaman daha iyi değildir."** Asimptotik gösterim sabitleri elediği için, $O(n \log n)$ bir algoritma küçük girdilerde $O(n^2)$ bir algoritmadan yavaş olabilir. Bu, sıralama kütüphanelerinin küçük parçalara farklı algoritma uygulamasının nedenidir. **Gösterim bir eşitlik değildir.** $f(n) = O(g(n))$ yazımı yerleşmiştir ama yanıltıcıdır; doğrusu $f \in O(g)$ biçiminde bir küme üyeliğidir. Bu nedenle eşitlik simetrik değildir: $O(n) = f(n)$ yazılmaz. #### Girdi Büyüklüğü Nedir Son bir tanım gerekir: $n$ neyi sayar? Yanıt probleme göre değişir ve belirtilmezse ifade anlamsızdır. - Dizi işlemlerinde eleman sayısı. - Metin algoritmalarında karakter sayısı. - Çizge algoritmalarında hem düğüm hem kenar sayısı — bu yüzden maliyetler $O(V + E)$ gibi iki değişkenle yazılır. - Sayısal algoritmalarda genellikle sayının **bit uzunluğu**; sayının kendisi değil. Son madde ince bir ayrımdır. Bir sayının asal olup olmadığını sayıya kadar bölerek sınayan yöntem, girdi olarak sayının değeri alınırsa $O(\sqrt{N})$ görünür; oysa girdi $N$ değil, onu yazmak için gereken bit sayısıdır. Bit uzunluğu cinsinden aynı yöntem üsteldir. Bu ayrım, karmaşıklık kuramında sınıflandırmanın temelidir ve **Hesaplama Kuramı** kursunda ele alınır. #### Özet - Asimptotik gösterim, sabitleri ve düşük dereceli terimleri eleyerek büyüme hızını tutar. - Büyük O üst sınır, büyük omega alt sınır, büyük teta sıkı sınır verir. - Tanımdaki $c$ sabiti çarpansal farkları, $n_0$ eşiği küçük girdileri eler. - Sadeleştirmede sabitler elenir, toplamda büyük terim kalır, çarpımda çarpanlar korunur; logaritmanın tabanı yazılmaz, çünkü taban değişimi sabit çarpandır. - $O$ ile "en kötü durum" farklı eksenlerdir; küçük asimptotik sınıf, küçük girdilerde hızlı olmayı garanti etmez. - Girdi büyüklüğünün ne sayıldığı açıkça belirtilmelidir. #### Sonraki Adım Büyük O ve omega, sınırın sıkı olup olmadığını söylemez: $n$ hem $O(n)$ hem $O(n^2)$'dir. Sonraki ders, sınırın kesinlikle gevşek olduğunu belirten küçük gösterimlerini tanımlayacak ve bunların hangi ifadeleri mümkün kıldığını gösterecek. ### Küçük o ve Küçük omega Source: https://academia.sh/tr/kurslar/algoritmalar/kucuk-o-ve-kucuk-omega Sıkı olmayan sınırların tanımı, limit ölçütü, beş gösterimin karşılaştırma işleçleriyle benzeşimi ve sıralama ilişkisinin sınırları. Büyük O bir üst sınır verir ama sınırın **sıkı** olup olmadığını söylemez. $n$ fonksiyonu hem $O(n)$ hem $O(n^2)$'dir; ikinci ifade doğrudur ama bilgi vermez. Bazı durumlarda söylemek istediğimiz şey daha güçlüdür: "$f$, $g$'den **kesinlikle** daha yavaş büyür." Bu ders o ifadeyi mümkün kılan iki gösterimi tanımlar. #### Küçük o $$ f(n) = o(g(n)) \iff \forall c > 0,\ \exists n_0 : \forall n \geq n_0,\ f(n) < c \cdot g(n) $$ Büyük O ile farkı niceleyicidedir. Büyük O'da "**bir** $c$ bulunur" denir; küçük o'da "**her** $c$ için" denir — sabit ne kadar küçük seçilirse seçilsin, yeterince büyük $n$ için eşitsizlik sağlanır. Sonuç, $f$'nin $g$ yanında **giderek önemsizleşmesidir**. Eşdeğer ve kullanışlı biçimi limitle verilir: $$ f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 $$ Örneğin $n = o(n^2)$'dir, çünkü oran $1/n \to 0$'dır. Buna karşılık $3n$ ifadesi $o(n)$ **değildir**: oran sabit $3$'te kalır, sıfıra gitmez. Büyük O ise ikisini de kabul eder — $3n = O(n)$ doğrudur. #### Küçük omega $$ f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty $$ Küçük omega, küçük o'nun aynadaki görüntüsüdür: $f$, $g$'yi kesinlikle geride bırakır. $n^2 = \omega(n)$ ve $2^n = \omega(n^{100})$ doğrudur — üstel büyüme, her polinomu sonunda geçer. #### Beş Gösterimin Benzeşimi Beş gösterim, sayı karşılaştırmalarıyla birebir eşleşir: | Gösterim | Karşılaştırma benzeşimi | Limit ölçütü | |---|---|---| | $f = O(g)$ | $f \leq g$ | Oran sonlu (sıfır olabilir) | | $f = \Omega(g)$ | $f \geq g$ | Oran sıfırdan büyük (sonsuz olabilir) | | $f = \Theta(g)$ | $f = g$ | Oran sonlu ve sıfırdan büyük bir sabite gider | | $f = o(g)$ | $f < g$ | Oran sıfıra gider | | $f = \omega(g)$ | $f > g$ | Oran sonsuza gider | Benzeşim öğreticidir ama tam değildir; farkları bu dersin son bölümünde ele alınır. #### Limit Ölçütü Uygulaması Limit, iki fonksiyonun ilişkisini belirlemenin en pratik yoludur. Oran hesaplanır ve sonsuza giderken davranışına bakılır. ```python import math def oran(f, g, n_degerleri): return [f(n) / g(n) for n in n_degerleri] n_degerleri = [10, 100, 1_000, 10_000, 100_000] print([f"{x:.4f}" for x in oran(lambda n: n, lambda n: n**2, n_degerleri)]) # ['0.1000', '0.0100', '0.0010', '0.0001', '0.0000'] — sıfıra gidiyor: n = o(n²) print([f"{x:.4f}" for x in oran(lambda n: 3*n, lambda n: n, n_degerleri)]) # ['3.0000', '3.0000', '3.0000', '3.0000', '3.0000'] — sabit: 3n = Θ(n), o(n) değil print([f"{x:.4f}" for x in oran(math.log2, lambda n: n, n_degerleri)]) # ['0.3322', '0.0664', '0.0100', '0.0013', '0.0002'] — sıfıra gidiyor: log n = o(n) print([f"{x:.2f}" for x in oran(lambda n: n * math.log2(n), lambda n: n**2, n_degerleri)]) # ['0.33', '0.07', '0.01', '0.00', '0.00'] — n log n = o(n²) ``` Sayısal gözlem bir kanıt değildir; limitin gerçekten sıfıra gittiği matematiksel olarak gösterilir. Ancak beklentiyi doğrulamanın ve hata yakalamanın hızlı yoludur. Üçüncü satır, sık kullanılan bir sonucu doğrular: **logaritma, her pozitif kuvvetten yavaş büyür.** Dördüncü satır ise $n \log n$ ile $n^2$ arasındaki farkın neden bu kadar belirleyici olduğunu gösterir — oran sıfıra gider, yani fark girdi büyüdükçe açılır. #### Büyüme Hiyerarşisi Küçük o, sık kullanılan fonksiyonları kesin bir zincire dizer. Her adımda soldaki, sağdakinin küçük o'sudur: $$ 1 = o(\log \log n) = o(\log n) = o(n^{\varepsilon}) = o(n) = o(n \log n) = o(n^2) = o(2^n) = o(n!) $$ Burada $\varepsilon$, sıfırdan büyük herhangi bir sabittir. Zincir üç genel kuralı özetler: - **Logaritma, her pozitif kuvvetten yavaş büyür.** $\log n = o(n^{0{,}001})$ bile doğrudur; logaritmanın kaç kez uygulandığı da fark etmez. - **Her polinom, her üstelden yavaş büyür.** $n^{1000} = o(1{,}001^n)$ doğrudur; taban bire ne kadar yakın olursa olsun. - **Üstel, faktöriyelden yavaş büyür.** $n!$ çarpanlarının ortalaması $n$ ile birlikte büyür, $2^n$'in çarpanları ise sabit kalır. Zincirdeki her ilişki küçük o ile yazıldığından, aradaki ayrımlar kesindir; bir sınıftan diğerine geçmek sabit bir iyileştirme değil, mertebe değişimidir. Aynı zincir, $\Theta$ ile küçük gösterimler arasındaki bağı da verir: $f = \Theta(g)$ ise $f$ ne $o(g)$ ne de $\omega(g)$'dir. Üç durum birbirini dışlar ve —oranın limiti varsa— birlikte tüm olasılıkları kapsar. #### Ne İşe Yarar Küçük gösterimler üç yerde kullanılır. **Sınıf hiyerarşisini kurmak.** "$\log n = o(n)$ ve $n = o(n^2)$" ifadeleri, karmaşıklık sınıflarının kesin olarak ayrıldığını söyler. Büyük O ile aynı iddia yapılamaz; $O$ gevşek olabileceği için ayrımı göstermez. **İhmal edilebilirliği belirtmek.** Bir ifadenin küçük terimi $o(\cdot)$ ile yazılırsa, "bu terim asimptotik olarak önemsizdir" denmiş olur: $n^2 + o(n^2)$ ifadesi, ikinci terimin baskın terimin yanında kaybolduğunu belirtir. **Kesin ayrım iddiası.** İki algoritmanın farklı sınıflarda olduğu, ancak küçük gösterimlerle söylenebilir. "Birincisi $O(n^2)$, ikincisi $O(n \log n)$" ifadesi tek başına ikincisinin daha iyi olduğunu kanıtlamaz — birincinin sınırı gevşek olabilir. Kesin ifade, ikinci algoritmanın maliyetinin birincininkinin $o(\cdot)$'ı olduğudur. #### Tam Sıralama Değildir Karşılaştırma benzeşimi bir yerde bozulur: sayılarda iki değerden biri mutlaka diğerinden küçük, büyük veya ona eşittir. Fonksiyonlarda böyle bir güvence yoktur. İki fonksiyon **karşılaştırılamaz** olabilir: aralarındaki oran salınırsa, ne limit vardır ne de bir sınır ilişkisi kurulabilir. Örneğin $n$ ile, tek $n$'lerde $n^2$ çift $n$'lerde $1$ değerini alan bir fonksiyon arasında hiçbir asimptotik ilişki yoktur. ```python def salinan(n: int) -> int: return n**2 if n % 2 == 1 else 1 print([salinan(n) / n for n in range(1, 8)]) # [1.0, 0.5, 3.0, 0.25, 5.0, 0.16666666666666666, 7.0] — oran salınıyor ``` Oran ne sıfıra ne sonsuza yakınsar; ikisi arasında gidip gelir. Böyle bir fonksiyon $O(n)$ de değildir, $\Omega(n)$ de. Pratikte karşılaşılan algoritma maliyetleri düzenli fonksiyonlardır ve bu sorun çıkmaz; ancak gösterimin bir **kısmi sıralama** olduğunu bilmek, ifadeleri dikkatli kurmayı gerektirir. #### Özet - Küçük o, sınırın kesinlikle gevşek olduğunu belirtir: her sabit için eşitsizlik sağlanır, oran sıfıra gider. - Küçük omega, aynı ilişkinin ters yönüdür; oran sonsuza gider. - Beş gösterim sayı karşılaştırmalarına benzer: $O \approx \leq$, $\Omega \approx \geq$, $\Theta \approx =$, $o \approx <$, $\omega \approx >$. - Limit ölçütü, iki fonksiyonun ilişkisini belirlemenin pratik yoludur. - Küçük gösterimler sınıf hiyerarşisini kurmak, ihmal edilebilirliği belirtmek ve kesin ayrım iddiasında bulunmak için kullanılır. - İlişki tam sıralama değildir; oranı salınan fonksiyonlar karşılaştırılamaz. #### Sonraki Adım Gösterimler tanımlandı; sıra bunların temsil ettiği büyüme sınıflarına geldi. Sonraki ders, sabit zamandan faktöriyele uzanan sınıfları sayısal olarak karşılaştıracak ve "algoritma ne kadar büyük girdiyle başa çıkabilir" sorusunu yanıtlayacak. ### Karmaşıklık Sınıflarını Okumak Source: https://academia.sh/tr/kurslar/algoritmalar/karmasiklik-siniflari Sabit, logaritmik, doğrusal, doğrusal-logaritmik, polinom, üstel ve faktöriyel büyüme; ölçek büyütme davranışı ve pratik sınırlar. Gösterimler tanımlandı; bu ders onların temsil ettiği büyüme sınıflarını somutlaştırır. Amaç, bir maliyet ifadesini gördüğünde ne anlama geldiğini **sayısal olarak** bilmektir: $O(n^2)$ bir algoritmanın milyon elemanla çalışıp çalışamayacağı, tahmin değil hesap işidir. #### Sınıflar En yavaştan en hızlı büyüyene doğru sık karşılaşılan sınıflar: | Sınıf | Ad | Tipik örnek | |---|---|---| | $O(1)$ | Sabit | Dizi elemanına erişim, karma tablosunda arama | | $O(\log n)$ | Logaritmik | İkili arama, dengeli ağaçta arama | | $O(n)$ | Doğrusal | Diziyi tarama, en büyüğü bulma | | $O(n \log n)$ | Doğrusal-logaritmik | Verimli sıralama algoritmaları | | $O(n^2)$ | Karesel | İç içe iki döngü, temel sıralamalar | | $O(n^3)$ | Kübik | Üç boyutlu iç içe döngü, kaba matris çarpımı | | $O(2^n)$ | Üstel | Tüm alt kümeleri denemek | | $O(n!)$ | Faktöriyel | Tüm sıralamaları denemek | Aradaki bazı sınıflar da vardır — $O(\sqrt{n})$, $O(n \log \log n)$, $O(n^{2{,}37})$ gibi — ancak yukarıdaki liste pratiğin büyük bölümünü kapsar. #### Sayısal Karşılaştırma Sınıflar arasındaki fark, birkaç sayı yazılınca görünür hâle gelir. ```python import math def islem_sayisi(n: int) -> dict[str, float]: return { "log n": math.log2(n), "n": n, "n log n": n * math.log2(n), "n²": n**2, "2ⁿ": 2**n if n <= 40 else float("inf"), } for n in (10, 100, 1_000, 1_000_000): d = islem_sayisi(n) print(n, {k: f"{v:.3g}" for k, v in d.items()}) # 10 {'log n': '3.32', 'n': '10', 'n log n': '33.2', 'n²': '100', '2ⁿ': '1.02e+03'} # 100 {'log n': '6.64', 'n': '100', 'n log n': '664', 'n²': '1e+04', '2ⁿ': 'inf'} # 1000 {'log n': '9.97', 'n': '1e+03', 'n log n': '9.97e+03', 'n²': '1e+06', '2ⁿ': 'inf'} # 1000000 {'log n': '19.9', 'n': '1e+06', 'n log n': '1.99e+07', 'n²': '1e+12', '2ⁿ': 'inf'} ``` Bir milyon elemanda logaritmik bir algoritma **yirmi** adım atar; karesel bir algoritma **bir trilyon**. Aradaki fark, "biraz daha yavaş" değil, bir problemi çözülebilir olmakla olmamak arasındaki farktır. Üstel sütunun kırkın üzerinde hesaplanmaması bir kolaylık değil, zorunluluktur: $2^{100}$ yaklaşık $1{,}3 \times 10^{30}$'dur ve saniyede bir milyar adım atan bir makine bu kadar adımı ancak evrenin yaşının binlerce katı bir sürede tamamlar. #### Ölçek Büyütme Davranışı Pratikte en yararlı soru şudur: **girdi ikiye katlanırsa maliyet nasıl değişir?** | Sınıf | Girdi $2\times$ olduğunda maliyet | Girdi $10\times$ olduğunda | |---|---|---| | $O(1)$ | Değişmez | Değişmez | | $O(\log n)$ | Sabit bir miktar artar | Sabit bir miktar artar | | $O(n)$ | $2\times$ | $10\times$ | | $O(n \log n)$ | $2\times$'ten biraz fazla | $10\times$'ten biraz fazla | | $O(n^2)$ | $4\times$ | $100\times$ | | $O(n^3)$ | $8\times$ | $1000\times$ | | $O(2^n)$ | Karesi alınır | Anlamsız | Bu tablo, ölçüm yapmadan tahmin yürütmeyi sağlar. Bin kayıtla iki saniye süren karesel bir işlem, on bin kayıtla iki yüz saniye sürer. Aynı iş doğrusal-logaritmik bir algoritmayla yapılıyorsa, on kat veriyle yaklaşık on üç kat artış olur. Ters yönde de kullanılır: ölçülen sürelerin girdiyle nasıl değiştiğine bakarak algoritmanın sınıfı tahmin edilebilir. Girdi ikiye katlandığında süre dörde katlanıyorsa, kodda karesel bir davranış vardır. #### Alt Doğrusal Sınıflar $O(\log n)$ ve $O(\sqrt{n})$ gibi sınıflar, girdinin **tamamını okumadan** sonuç üretir. Bu ancak veri önceden düzenlenmişse mümkündür: ikili arama sıralılık varsayar, karma tablosu önceden kurulmuş bir tablo varsayar. Bu nedenle alt doğrusal maliyetler genellikle bir **önişleme** maliyetiyle birlikte gelir. Bir dizi sıralanıp sonra bin kez aranacaksa, $O(n \log n)$ sıralama maliyeti bin aramaya bölünür ve kendini fazlasıyla öder. Tek bir arama için sıralamak ise anlamsızdır. Karar ölçütü budur: **önişleme maliyeti, sorgu sayısına bölündüğünde kazanç kalıyor mu?** #### Neden $n \log n$ Sık Görünür Bu sınıf, iki nedenle sık karşımıza çıkar. Birincisi, **böl ve yönet** yapısının doğal sonucudur: problem her adımda ikiye bölünür ($\log n$ derinlik), her düzeyde tüm elemanlar işlenir ($n$ iş). Birleştirmeli sıralama bunun kanonik örneğidir. İkincisi, karşılaştırmaya dayalı sıralamanın **alt sınırıdır**: hiçbir karşılaştırmalı algoritma bundan hızlı olamaz. Bu sonuç, arama ve sıralama konusunda kanıtlanacaktır. #### Üstel Sınıflar ve Kombinatoryel Patlama Üstel ve faktöriyel sınıflar, "tüm olasılıkları dene" biçimindeki çözümlerden doğar: - $n$ elemanın tüm alt kümeleri: $2^n$ tane. - $n$ elemanın tüm sıralamaları: $n!$ tane. ```python import math for n in (10, 20, 30, 50): print(n, f"2^n = {2**n:.3g}", f"n! = {math.factorial(n):.3g}") # 10 2^n = 1.02e+03 n! = 3.63e+06 # 20 2^n = 1.05e+06 n! = 2.43e+18 # 30 2^n = 1.07e+09 n! = 2.65e+32 # 50 2^n = 1.13e+15 n! = 3.04e+64 ``` Otuz elemanla alt küme sayısı bir milyarı aşar; yirmi elemanla sıralama sayısı iki kentilyona ulaşır. Bu, kaba kuvvet çözümlerinin neden yalnızca çok küçük girdilerde kullanılabildiğini gösterir. Böyle problemlerde üç yol izlenir: girdiyi küçük tutmak, akıllı budama ile arama uzayını daraltmak (Programlama Temelleri kursundaki geri izleme), ya da kesin çözümden vazgeçip yaklaşık sonuç üretmek. Bu problemlerin kuramsal sınıflandırması **Hesaplama Kuramı** kursuna aittir. #### Sabitler Ne Zaman Önemli Asimptotik gösterim sabitleri eler, ancak gerçek dünyada sabitler vardır ve küçük girdilerde baskındır. $100n$ maliyetli bir algoritma ile $n^2$ maliyetli bir algoritma karşılaştırıldığında, ikincisi $n < 100$ için daha hızlıdır. Kesişim noktası, sabitlerin oranıyla belirlenir. Pratik sonucu, kütüphane gerçekleştirimlerinde görülür: sıralama algoritmaları küçük alt dizilerde eklemeli sıralamaya geçer, çünkü o boyutlarda basit algoritmanın küçük sabiti kazanır. Bu tür karma yaklaşımlar, asimptotik çözümlemenin nerede bitip ölçümün nerede başladığını gösterir. #### Özet - Sınıflar, sabit ve logaritmikten üstel ve faktöriyele doğru sıralanır; aradaki farklar büyük girdilerde mertebe düzeyindedir. - Girdi ikiye katlandığında maliyetin nasıl değiştiği, sınıfı tanımanın pratik yoludur. - Alt doğrusal sınıflar önceden düzenlenmiş veri gerektirir; önişleme maliyeti sorgu sayısına bölünerek değerlendirilir. - $n \log n$, böl ve yönet yapısının doğal sonucu ve karşılaştırmalı sıralamanın alt sınırıdır. - Üstel ve faktöriyel sınıflar kaba kuvvet çözümlerinden doğar ve yalnızca çok küçük girdilerde uygulanabilir. - Sabitler küçük girdilerde baskındır; kütüphaneler bu nedenle karma yaklaşımlar kullanır. #### Sonraki Adım Sınıflar tanındı; sıra bir kod parçasına bakıp hangi sınıfa ait olduğunu **belirlemeye** geldi. Sonraki ders, döngülerin, özyinelemenin ve amortize edilmiş işlemlerin maliyetini hesaplama yöntemlerini adım adım kuracak. ### Karmaşıklık Hesaplama Yöntemi Source: https://academia.sh/tr/kurslar/algoritmalar/karmasiklik-hesaplama Döngü ve koşul kurallarıyla maliyet sayımı, özyineleme bağıntıları, ana teorem ve amortize çözümleme. Sınıflar tanındı; sıra bir kod parçasına bakıp hangi sınıfa ait olduğunu belirlemeye geldi. Bu ders, hesabın kurallarını verir. Kurallar azdır ve birleştirilerek uygulanır. #### Temel Kurallar **Ardışık bölümler toplanır.** İki bölüm arka arkaya çalışıyorsa maliyetleri toplanır ve büyük olan baskın kalır: $O(n) + O(n^2) = O(n^2)$. **Döngü, gövde maliyeti çarpı tur sayısıdır.** Gövdesi sabit olan ve $n$ kez dönen döngü $O(n)$'dir. **İç içe döngülerde maliyetler çarpılır.** Her ikisi de $n$ kez dönen iki döngü $O(n^2)$'dir. **Koşullu yapılarda en kötü dal alınır.** Güvence en kötü durum üzerinden verilir. **Sabit sayıda tekrar sabittir.** Kaç kez döndüğü $n$'e bağlı olmayan döngü $O(1)$'dir. ```python def sayim_ornekleri(n: int) -> dict[str, int]: sayac = {"tekli": 0, "icice": 0, "ucgen": 0, "yarilanan": 0} for i in range(n): # O(n) sayac["tekli"] += 1 for i in range(n): # O(n²) for j in range(n): sayac["icice"] += 1 for i in range(n): # O(n²) — üçgensel ama yine karesel for j in range(i): sayac["ucgen"] += 1 i = 1 while i < n: # O(log n) sayac["yarilanan"] += 1 i *= 2 return sayac print(sayim_ornekleri(8)) # {'tekli': 8, 'icice': 64, 'ucgen': 28, 'yarilanan': 3} print(sayim_ornekleri(16)) # {'tekli': 16, 'icice': 256, 'ucgen': 120, 'yarilanan': 4} ``` Girdi ikiye katlandığında sayılar sınıfların beklediği gibi değişir: tekli iki katına, iç içe dört katına çıkar; yarılanan döngü ise yalnızca bir artar. Üçgensel döngü dikkat ister. Toplam tur sayısı $n(n-1)/2$'dir; sabit çarpan elendiğinde $O(n^2)$ kalır. "Yarısı kadar dönüyor" gözlemi sınıfı değiştirmez — yalnızca sabiti değiştirir. #### Döngü Sınırının Değişimi Tur sayısı, döngü değişkeninin nasıl ilerlediğine bağlıdır: | İlerleme | Tur sayısı | Sınıf | |---|---|---| | `i += 1` | $n$ | $O(n)$ | | `i += k` | $n/k$ | $O(n)$ | | `i *= 2` | $\log_2 n$ | $O(\log n)$ | | `i = i * i` | $\log \log n$ | $O(\log \log n)$ | | `i -= 1` (n'den) | $n$ | $O(n)$ | İkinci satır önemlidir: sabit adımla ilerlemek sınıfı değiştirmez. Çarpımsal ilerleme ise değiştirir; ikili aramanın logaritmik olmasının kaynağı budur. #### Özyineleme Bağıntıları Özyinelemeli bir algoritmanın maliyeti, kendi cinsinden yazılır. Bu ifadeye **özyineleme bağıntısı** denir. Üç yaygın kalıp: $$ T(n) = T(n-1) + O(1) \implies T(n) = O(n) $$ Her adımda problem bir eleman küçülür ve sabit iş yapılır; toplam $n$ adım. Faktöriyel hesabı bu kalıptadır. $$ T(n) = T(n/2) + O(1) \implies T(n) = O(\log n) $$ Her adımda problem yarılanır ve sabit iş yapılır; yarılama sayısı $\log_2 n$'dir. İkili arama bu kalıptadır. $$ T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n) $$ Problem iki yarıya bölünür, her düzeyde tüm elemanlar işlenir. Birleştirmeli sıralama bu kalıptadır ve bir sonraki konunun ana örneğidir. #### Özyineleme Ağacı Bağıntıyı çözmenin sezgisel yolu, çağrıları bir ağaç olarak çizip düzey düzey maliyet toplamaktır. $T(n) = 2T(n/2) + n$ bağıntısında: | Düzey | Çağrı sayısı | Çağrı başına iş | Düzey toplamı | |---|---|---|---| | 0 | 1 | $n$ | $n$ | | 1 | 2 | $n/2$ | $n$ | | 2 | 4 | $n/4$ | $n$ | | $k$ | $2^k$ | $n/2^k$ | $n$ | Her düzeyin toplamı $n$'dir ve düzey sayısı $\log_2 n$'dir; toplam $n \log n$ çıkar. Aynı yöntem $T(n) = 2T(n/2) + O(1)$ için farklı sonuç verir: düzey toplamları $1, 2, 4, \dots, n$ biçiminde büyür ve toplam $O(n)$ olur. Yaprak sayısı baskın hâle gelir. #### Ana Teorem Böl ve yönet bağıntılarının çoğu tek bir kalıba uyar: $$ T(n) = a\,T(n/b) + f(n) $$ Burada $a$ alt problem sayısı, $b$ küçülme çarpanı, $f(n)$ bölme ve birleştirme maliyetidir. Sonuç, $f(n)$ ile $n^{\log_b a}$ karşılaştırılarak belirlenir: - $f(n)$ küçükse: $T(n) = \Theta(n^{\log_b a})$ — yapraklar baskın. - İkisi aynı mertebedeyse: $T(n) = \Theta(n^{\log_b a} \log n)$ — tüm düzeyler eşit. - $f(n)$ büyükse: $T(n) = \Theta(f(n))$ — kök baskın. Birleştirmeli sıralamada $a = 2$, $b = 2$, $f(n) = n$'dir; $n^{\log_2 2} = n$ olduğundan ikinci durum geçerlidir ve sonuç $\Theta(n \log n)$ çıkar. Teoremin tam ifadesi ek koşullar içerir ve her bağıntı bu kalıba uymaz; uymayanlar için ağaç yöntemi veya doğrudan çözüm kullanılır. #### Amortize Çözümleme Bazı işlemlerin maliyeti tek tek bakıldığında yanıltıcıdır. Veri Yapıları kursundaki dinamik dizi buna örnekti: sona ekleme çoğunlukla sabit, ara sıra doğrusaldır. **Toplam maliyet yöntemi**, $m$ işlemin toplam maliyetini hesaplar ve $m$'e böler. Dinamik dizide $n$ ekleme için toplam kopyalama $2n$'den azdı — kapasite ikiye katlandığında kopyalamaların toplamı $1 + 2 + 4 + \dots$ biçiminde bir geometrik diziydi; ekleme başına amortize maliyet sabittir. ```python def toplam_kopyalama(n: int) -> int: """n eklemede yapılan toplam kopyalama sayısı (kapasite ikiye katlanarak).""" kapasite, uzunluk, kopyalama = 1, 0, 0 for _ in range(n): if uzunluk == kapasite: kopyalama += uzunluk # tüm elemanlar yeni bloğa taşınır kapasite *= 2 uzunluk += 1 return kopyalama for n in (16, 1000, 100_000): print(n, toplam_kopyalama(n), f"{toplam_kopyalama(n)/n:.2f}") # 16 15 0.94 # 1000 1023 1.02 # 100000 131071 1.31 ``` Ekleme başına ortalama kopyalama sayısı, girdi büyüdükçe küçük bir sabitin çevresinde kalır; doğrusal büyümez. Amortize sabit maliyet ifadesi tam olarak bunu söyler. İki yöntem daha vardır. **Muhasebe yöntemi**, her ucuz işleme ileride yapılacak pahalı iş için bir pay yükler; **potansiyel yöntemi**, yapının "biriken enerjisini" bir fonksiyonla ifade eder. Üçü de aynı sonucu verir; seçim, ispatın hangisiyle daha kısa yazıldığına bağlıdır. #### Uygulama Sırası Bir kod parçasının maliyetini bulmak için izlenen sıra: 1. **Girdi büyüklüğünü tanımla.** $n$ neyi sayıyor? 2. **En iç işlemi bul.** Hangi işlem en sık tekrarlanıyor? 3. **Tur sayılarını çarp.** İç içe yapılarda dıştan içe doğru. 4. **Ardışık bölümleri topla**, büyük terimi al. 5. **Özyineleme varsa bağıntıyı yaz** ve çöz. 6. **Amortize davranış varsa** toplam maliyeti işlem sayısına böl. Adımlar sırayla uygulandığında, sezgiye başvurmadan sonuç elde edilir. #### Özet - Ardışık bölümler toplanır, iç içe döngülerde maliyetler çarpılır, koşullarda en kötü dal alınır. - Döngü değişkeninin çarpımsal ilerlemesi tur sayısını logaritmik yapar; sabit adımla ilerleme sınıfı değiştirmez. - Özyinelemeli maliyet bir bağıntıyla yazılır; üç yaygın kalıp doğrusal, logaritmik ve doğrusal-logaritmik sonuç verir. - Özyineleme ağacı, düzey düzey maliyet toplayarak bağıntıyı çözer. - Ana teorem, böl ve yönet bağıntılarını üç durumda sınıflandırır. - Amortize çözümleme, bir işlem dizisinin toplam maliyetini işlem sayısına böler. #### Sonraki Adım Buraya kadar yalnızca zaman ele alındı. Oysa algoritmalar bellek de kullanır ve ikisi sıklıkla birbirinin yerine geçer: daha çok bellek kullanarak daha hızlı, daha az bellek kullanarak daha yavaş çalışmak mümkündür. Sonraki ders bu ödünleşimi ve tipik kalıplarını ele alacak. ### Zaman ve Alan Ödünleşimi Source: https://academia.sh/tr/kurslar/algoritmalar/zaman-ve-alan-odunlesimi Alan karmaşıklığı, yerinde çalışma, özyineleme yığıtının maliyeti, anımsama ve önhesaplama kalıpları; ödünleşimin sınırları. Buraya kadar tek bir kaynak sayıldı: işlem sayısı. Oysa algoritmalar bellek de tüketir ve iki kaynak sıklıkla birbirinin yerine geçer. Daha çok bellek kullanarak daha az işlem yapmak, ya da tersi, çoğu problemde mümkündür. Bu ders, ikinci ekseni tanımlar ve aralarındaki değiş tokuşun kalıplarını gösterir. #### Alan Karmaşıklığı **Alan karmaşıklığı**, girdi büyüklüğüne göre kullanılan bellek miktarının büyüme hızıdır. Zaman karmaşıklığıyla aynı gösterimler kullanılır. İki ayrı büyüklük vardır ve karıştırılmaları yaygın bir hatadır: **Toplam alan**, girdi dahil kullanılan tüm bellektir. $n$ elemanlık bir dizi üzerinde çalışan her algoritma en az $O(n)$ toplam alan kullanır. **Ek alan (auxiliary space)**, girdi dışında ayrılan bellektir. Karşılaştırmalarda anlamlı olan budur; çünkü girdiyi tutmak zaten zorunludur. Ek alanı sabit olan algoritmalara **yerinde (in-place)** denir. Diziyi ters çeviren şu işlev yerindedir: kaç eleman olursa olsun üç değişkenden fazlasını kullanmaz. ```python def ters_cevir_yerinde(dizi: list[int]) -> None: """Diziyi yerinde ters çevirir. Ek alan: O(1).""" sol, sag = 0, len(dizi) - 1 while sol < sag: dizi[sol], dizi[sag] = dizi[sag], dizi[sol] sol += 1 sag -= 1 def ters_cevir_kopyali(dizi: list[int]) -> list[int]: """Yeni dizi üretir. Ek alan: O(n).""" return [dizi[i] for i in range(len(dizi) - 1, -1, -1)] d = [1, 2, 3, 4, 5] ters_cevir_yerinde(d) print(d) # [5, 4, 3, 2, 1] print(ters_cevir_kopyali([1, 2, 3, 4, 5])) # [5, 4, 3, 2, 1] ``` İkisi de $O(n)$ zamanlıdır; ayrıldıkları eksen alandır. Seçim, çağıranın özgün diziye ihtiyacı olup olmamasına ve belleğin ne kadar kısıtlı olduğuna bağlıdır. #### Özyineleme Yığıtı Alan Tüketir Özyinelemeli bir çözümde açıkça dizi ayrılmasa bile bellek kullanılır: her bekleyen çağrı, Programlama Temelleri kursunda tanıtılan çağrı yığıtında bir çerçeve tutar. Alan maliyeti, **en derin nokta**daki çağrı sayısıdır — toplam çağrı sayısı değil. | Yapı | En büyük derinlik | Ek alan | |---|---|---| | Doğrusal özyineleme ($n$ adım) | $n$ | $O(n)$ | | İkiye bölen özyineleme | $\log n$ | $O(\log n)$ | | Kuyruk özyinelemesi (döngüye çevrilmişse) | $1$ | $O(1)$ | Ayrım pratik sonuç doğurur: milyon elemanlık bir dizide doğrusal derinlikli bir özyineleme, çalışma zamanının yığıt sınırını aşar. Aynı algoritmanın döngülü yazımı sınıra takılmaz. #### Klasik Ödünleşim Kalıpları Belleği zamana çevirmenin birkaç yerleşik yolu vardır. **Anımsama (memoization).** Hesaplanan sonuçlar saklanır, tekrar istendiğinde yeniden hesaplanmaz. Zaman düşer, alan artar. **Önhesaplama.** Sonuçlar sorgu gelmeden önce bir tabloya yazılır. Sorgu maliyeti sabite iner, tablo alanı ödenir. **Dizinleme.** Veri Yapıları kursundaki karma tablosu ve ağaçlar, ek yapı karşılığında arama maliyetini düşürür. **Sıkıştırma.** Ters yön: alan azalır, kodlama-çözme işlemi zamanı artırır. Anımsamanın etkisi, aynı hesabı iki kez yapan bir özyinelemede en açık görülür. ```python def fib_saf(n: int, sayac: list[int]) -> int: sayac[0] += 1 if n < 2: return n return fib_saf(n - 1, sayac) + fib_saf(n - 2, sayac) def fib_tablolu(n: int, sayac: list[int], tablo: dict[int, int]) -> int: sayac[0] += 1 if n < 2: return n if n not in tablo: tablo[n] = fib_tablolu(n - 1, sayac, tablo) + fib_tablolu(n - 2, sayac, tablo) return tablo[n] for n in (10, 20, 30): a, b = [0], [0] print(n, fib_saf(n, a), a[0], fib_tablolu(n, b, {}), b[0]) # 10 55 177 55 19 # 20 6765 21891 6765 39 # 30 832040 2692537 832040 59 ``` Çağrı sayısı üstelden doğrusala iner: otuz için iki milyon yedi yüz bin çağrı yerine elli dokuz. Ödenen bedel, $n$ girdilik bir sözlüktür — yani $O(n)$ ek alan. #### Aynı Problem, İki Denge Noktası Ödünleşim, tek bir problem üzerinde iki çözüm yazılarak somutlaşır. Problem: bir dizide toplamı verilen hedefe eşit olan iki eleman var mı? ```python def iki_toplam_karma(dizi: list[int], hedef: int) -> tuple[int, int] | None: """Zaman O(n), ek alan O(n).""" gorulen: dict[int, int] = {} for i, deger in enumerate(dizi): if hedef - deger in gorulen: return gorulen[hedef - deger], i gorulen[deger] = i return None def iki_toplam_iki_uc(dizi: list[int], hedef: int) -> tuple[int, int] | None: """Sıralı dizi üzerinde zaman O(n), ek alan O(1).""" sol, sag = 0, len(dizi) - 1 while sol < sag: toplam = dizi[sol] + dizi[sag] if toplam == hedef: return sol, sag if toplam < hedef: sol += 1 else: sag -= 1 return None print(iki_toplam_karma([8, 3, 11, 5, 2], 13)) # (0, 3) — 8 + 5 print(iki_toplam_iki_uc([2, 3, 5, 8, 11], 13)) # (0, 4) print(iki_toplam_karma([8, 3, 11, 5, 2], 100)) # None ``` Birinci çözüm sırasız dizide tek geçişte çalışır ama $n$ girdilik bir sözlük tutar. İkincisi hiç ek alan kullanmaz, karşılığında dizinin sıralı olmasını ister; sıralama maliyeti eklenirse toplam $O(n \log n)$ olur. Seçim, "hangisi daha iyi" sorusunun yanıtı değildir; hangi kaynağın kısıtlı olduğuna bağlıdır. Bellek boldu ve tek sorgu yapılacaksa birincisi; bellek darsa veya dizi zaten sıralıysa ikincisi. #### Ödünleşim Her Zaman Geçerli Değil İki uyarı, ödünleşimi mekanik bir kural saymayı engeller. **Daha az alan bazen daha hızlıdır.** Bilgisayarlar Nasıl Çalışır kursundaki bellek hiyerarşisi nedeniyle, küçük ve bitişik bir yapı önbelleğe sığar ve dağınık büyük bir yapıdan hızlı çalışabilir. Alan azaltmak burada zamanı da azaltır. **Bazı iyileştirmeler her iki eksende de kazandırır.** Karesel bir algoritmayı doğrusal-logaritmiğe indiren bir fikir, çoğu zaman ek alan da istemez. Ödünleşim, algoritma sabit tutulduğunda geçerlidir; daha iyi bir algoritma bulunduğunda değil. Bu nedenle sıralama, önce algoritmanın kendisini iyileştirmeye bakmak, ödünleşime ancak sonra başvurmaktır. #### Karar Ölçütü Uygulamada seçim üç soruyla yapılır: 1. **Hangi kaynak kısıtlı?** Gömülü bir sistemde bellek, toplu işlemede zaman. 2. **Sonuç kaç kez kullanılacak?** Tek kullanımlık hesapta önhesaplama zarardır; çok sorguluda kendini öder. 3. **Girdi ne kadar büyüyecek?** Alan doğrusal artıyorsa, girdi belli bir noktadan sonra belleğe sığmaz ve çözüm geçersizleşir. Üçüncü soru sıklıkla atlanır: zaman aşımı bir gecikmedir, bellek aşımı ise çalışmanın tamamen durmasıdır. #### Özet - Alan karmaşıklığı, bellek kullanımının girdiye göre büyüme hızıdır; toplam alan ile ek alan ayrı büyüklüklerdir. - Ek alanı sabit olan algoritmalara yerinde denir. - Özyineleme, en derin noktadaki çağrı sayısı kadar yığıt alanı tüketir. - Anımsama, önhesaplama ve dizinleme belleği zamana çevirir; sıkıştırma ters yönde çalışır. - Aynı problemin farklı denge noktalarındaki çözümleri, kısıtlı kaynağa göre seçilir. - Ödünleşim algoritma sabitken geçerlidir; daha iyi bir algoritma her iki eksende de kazandırabilir. #### Sonraki Adım Çözümleme araçları tamamlandı: maliyet tanımlandı, gösterimle ifade edildi, hesaplandı ve iki eksene ayrıldı. Sonraki konu bu araçları ilk kez ciddi bir algoritma ailesine uygulayacak — arama ve sıralama. Aynı problemin yarım düzine çözümü, tam da bu ölçütlerle karşılaştırılacak. ## Arama ve Sıralama Doğrusal ve ikili arama, temel ve gelişmiş sıralama algoritmaları, karşılaştırmasız yöntemler ve seçim ölçütleri. ### Doğrusal Arama Source: https://academia.sh/tr/kurslar/algoritmalar/dogrusal-arama Sırasız veride tarama, başarılı ve başarısız aramanın beklenen karşılaştırma sayısı, nöbetçi değişkeni ve doğrusal alt sınırın gerekçesi. Çözümleme araçları hazır; bu konu onları ilk kez bir algoritma ailesine uygular. Arama ve sıralama, aynı problemin farklı maliyetlerdeki çözümlerini yan yana koymaya elverişli olduğu için bu iş için uygun bir zemindir. En basit aramayla başlanır: elemanları baştan sona gezmek. #### Algoritma ve Doğruluğu **Doğrusal arama**, diziyi baştan sona tarar ve aranan değeri bulduğu ilk konumu döndürür. ```python def dogrusal_arama(dizi: list[int], hedef: int) -> int: """Hedefin ilk konumu; yoksa -1. Değişmez: her turun başında, 0..i-1 aralığında hedef yoktur. Sonlanma: kalan eleman sayısı her turda bir azalır. """ for i in range(len(dizi)): if dizi[i] == hedef: return i return -1 olcumler = [5, 2, 9, 1, 5, 6] print(dogrusal_arama(olcumler, 9)) # 2 print(dogrusal_arama(olcumler, 5)) # 0 — ilk eşleşme print(dogrusal_arama(olcumler, 7)) # -1 ``` Doğruluğu belgedeki iki cümle verir. Döngü değişmezi, döngü bittiğinde "0..n-1 aralığında hedef yoktur" hâline gelir; bu da `-1` dönüşünü gerekçelendirir. Azalan büyüklük, sonlanma güvencesidir. İki tasarım kararı örtük olarak alınmıştır: eşit değerler varsa **ilk** konum döndürülür ve bulunamama, geçerli bir dizin olamayacak bir değerle bildirilir. #### Üç Durumun Maliyeti Ölçüt karşılaştırma sayısıdır. **En iyi durum:** Hedef ilk elemandır; 1 karşılaştırma, $O(1)$. **En kötü durum:** Hedef son elemandır veya hiç yoktur; $n$ karşılaştırma, $O(n)$. **Ortalama durum:** Hedefin dizide bulunduğu ve her konumun eşit olasılıklı olduğu varsayılırsa, beklenen karşılaştırma sayısı $$ \frac{1 + 2 + \dots + n}{n} = \frac{n+1}{2} $$ olur; bu da $O(n)$'dir. Başarısız aramada her zaman $n$ karşılaştırma yapılır. ```python def karsilastirma_sayisi(dizi: list[int], hedef: int) -> int: for i in range(len(dizi)): if dizi[i] == hedef: return i + 1 return len(dizi) dizi = list(range(100)) toplam = sum(karsilastirma_sayisi(dizi, h) for h in dizi) print(toplam / len(dizi)) # 50.5 — (n+1)/2 print(karsilastirma_sayisi(dizi, -1)) # 100 — başarısız arama ``` Ortalama, en kötü durumun yaklaşık yarısıdır. Sabit çarpan farkı asimptotik sınıfı değiştirmez: iki durum da doğrusaldır. Bu, ortalama durum çözümlemesinin ne zaman anlamlı olduğunu gösterir — sınıfı değil, sabiti belirler. #### Nöbetçi Değişkeni Döngü her turda iki sınama yapar: dizin sınırı aşıldı mı, eleman hedefe eşit mi. Hedef dizinin sonuna geçici olarak eklenirse, sınır sınaması gereksizleşir; arama en geç o elemanda durur. ```python def nobetci_ile_arama(dizi: list[int], hedef: int) -> int: dizi.append(hedef) # nöbetçi i = 0 while dizi[i] != hedef: i += 1 dizi.pop() return i if i < len(dizi) else -1 d = [5, 2, 9, 1, 5, 6] print(nobetci_ile_arama(d, 9), nobetci_ile_arama(d, 7), d) # 2 -1 [5, 2, 9, 1, 5, 6] ``` Kazanç sabit çarpandadır; sınıf yine $O(n)$'dir. Yöntemin bedeli, diziyi geçici olarak değiştirmesidir — paylaşılan veride veya çok iş parçacıklı bir ortamda kullanılamaz. Bu, kursun tekrar eden bir dersidir: sabit iyileştirmeler gerçektir ama sınıfı değiştiren bir fikrin yerini tutmaz. #### Neden Daha İyisi Yapılamaz Sırasız bir dizide aramanın maliyeti düşürülemez ve bunun gerekçesi bir **karşı oyuncu** akıl yürütmesidir. Bir algoritmanın $n$ elemanın hepsine bakmadığını varsayalım. Bakmadığı en az bir konum vardır. Karşı oyuncu, algoritma "bulunamadı" dediğinde o konuma hedefi yerleştirir; algoritmanın gözlemleri değişmediği için yanıtı da değişmez, ama yanıt artık yanlıştır. Öyleyse doğru çalışan her algoritma, en kötü durumda tüm elemanlara bakmak zorundadır: sırasız veride arama $\Omega(n)$'dir. Doğrusal arama bu sınıra ulaştığı için, sıra varsayımı olmadan **eniyi**dir. Sınırdan kaçmanın tek yolu varsayımı değiştirmektir: veriyi sıralı tutmak veya bir dizin yapısı kurmak. Sonraki ders birinci yolu, Veri Yapıları kursundaki karma tablosu ikinci yolu izler. #### Erişim Dağılımı ve Sıralamanın Etkisi Ortalama durum hesabı, her elemanın eşit olasılıkla arandığını varsayıyordu. Gerçek erişimler çoğu zaman eşit dağılmaz: birkaç kayıt sık, geri kalanı seyrek aranır. Beklenen karşılaştırma sayısı, $i$ numaralı elemanın aranma olasılığı $p_i$ iken $$ \sum_{i=1}^{n} i \cdot p_i $$ olur. İfade, elemanlar **azalan olasılık sırasına** dizildiğinde en küçük değerini alır. Yani dizinin sırası maliyeti belirler ve en iyi statik düzen, sıklığa göre sıralamadır. ```python def beklenen_maliyet(olasiliklar: list[float]) -> float: return sum((i + 1) * p for i, p in enumerate(olasiliklar)) print(round(beklenen_maliyet([0.1, 0.2, 0.7]), 2)) # 2.6 — kötü düzen print(round(beklenen_maliyet([0.7, 0.2, 0.1]), 2)) # 1.4 — sıklığa göre ``` Sıklıklar önceden bilinmiyorsa, listeyi çalışma anında düzenleyen sezgiler kullanılır: bulunan eleman başa taşınır ya da bir sıra öne alınır. Bunlar en kötü durumu değiştirmez — sınıf yine $O(n)$'dir — ancak eğik dağılımlarda ortalamayı belirgin biçimde düşürür. #### Tek Geçişte Birden Çok Bilgi Doğrusal tarama yalnızca eşleşme aramaz; aynı geçişte birkaç büyüklük birden toplanabilir. En küçük ile en büyüğü ayrı ayrı aramak $2n - 2$ karşılaştırma ister; elemanlar ikişer ikişer işlenirse maliyet düşer. ```python def en_kucuk_ve_en_buyuk(dizi: list[int]) -> tuple[int, int, int]: """(en küçük, en büyük, karşılaştırma sayısı) döndürür.""" n = len(dizi) if n % 2 == 0: kucuk, buyuk = min(dizi[0], dizi[1]), max(dizi[0], dizi[1]) i, sayac = 2, 1 else: kucuk = buyuk = dizi[0] i, sayac = 1, 0 while i < n - 1: a, b = dizi[i], dizi[i + 1] if a > b: a, b = b, a sayac += 3 # çift içi + iki uçla karşılaştırma kucuk = min(kucuk, a) buyuk = max(buyuk, b) i += 2 return kucuk, buyuk, sayac print(en_kucuk_ve_en_buyuk([5, 2, 9, 1, 5, 6])) # (1, 9, 7) print(en_kucuk_ve_en_buyuk(list(range(100)))) # (0, 99, 148) ``` Yüz eleman için 148 karşılaştırma yapılır; ayrı ayrı arama 198 isterdi. Genel formül $\lceil 3n/2 \rceil - 2$'dir ve bu, iki uç için bilinen alt sınırdır. Sınıf yine $O(n)$'dir. Kazanç, veri diskten veya ağdan geliyorsa ve her geçiş pahalıysa önem kazanır: tek geçişte toplanabilecek her bilgi, ikinci bir geçişten ucuzdur. #### Özet - Doğrusal arama sırasız veride çalışır; doğruluğu döngü değişmezi ve azalan büyüklükle gerekçelendirilir. - En iyi durum sabit, en kötü durum doğrusaldır; başarılı aramanın beklenen maliyeti $(n+1)/2$ karşılaştırmadır. - Nöbetçi değişkeni sınır sınamasını kaldırır; kazanç sabit çarpandadır, sınıf değişmez. - Karşı oyuncu akıl yürütmesi, sırasız veride aramanın $\Omega(n)$ olduğunu gösterir; doğrusal arama bu sınıra ulaşır. - Erişim olasılıkları eşit değilse, elemanları azalan sıklıkla dizmek beklenen maliyeti düşürür. - Tek geçişte birden çok büyüklük toplamak, geçiş sayısını ve toplam karşılaştırmayı düşürür. #### Sonraki Adım Doğrusal alt sınırdan kaçmanın yolu, veri üzerinde bir varsayım kurmaktır. Veri sıralıysa her karşılaştırma yalnızca bir elemanı değil, elemanların yarısını eler. Sonraki ders bu fikri — ikili aramayı — ve doğru yazılması şaşırtıcı derecede zor olan sınır koşullarını ele alacak. ### İkili Arama Source: https://academia.sh/tr/kurslar/algoritmalar/ikili-arama Sıralı veride yarıya bölme, döngü değişmeziyle sınır koşulları, ilk konumu bulan değişkeler ve tekdüze yüklem üzerinde arama. Doğrusal arama sırasız veri için eniyiydi. Varsayım değişirse sınır da değişir: dizi sıralıysa, bir karşılaştırma tek bir elemanı değil, kalan elemanların **yarısını** eler. Bu ders o fikri işler. Fikir basittir; doğru yazmak değildir — ikili arama, yayımlanmış gerçekleştirimlerinde onlarca yıl hata barındırmış olmasıyla tanınır. #### Aralık Değişmezi Algoritma, hedefin bulunabileceği bir aralık tutar ve her turda aralığı yarıya indirir. Sınır hatalarından kaçınmanın yolu, aralığın anlamını en baştan yazmaktır. Bu derste **kapalı aralık** kullanılır: `[sol, sag]` sınırlarının ikisi de aralığa dahildir. ```python def ikili_arama(dizi: list[int], hedef: int) -> int: """Sıralı dizide hedefin bir konumu; yoksa -1. Değişmez: hedef dizide varsa, [sol, sag] aralığındadır. Sonlanma: sag - sol her turda en az bir azalır. """ sol, sag = 0, len(dizi) - 1 while sol <= sag: orta = sol + (sag - sol) // 2 if dizi[orta] == hedef: return orta if dizi[orta] < hedef: sol = orta + 1 else: sag = orta - 1 return -1 sirali = [1, 3, 4, 7, 9, 11, 15, 20] print(ikili_arama(sirali, 9)) # 4 print(ikili_arama(sirali, 1)) # 0 print(ikili_arama(sirali, 20)) # 7 print(ikili_arama(sirali, 10)) # -1 ``` Üç ayrıntı, gerçekleştirimin doğruluğunu taşır: **Döngü koşulu `sol <= sag`.** Aralık kapalı olduğu için tek elemanlı aralık da geçerlidir; `<` yazılırsa son eleman hiç sınanmaz. **Sınırların `orta ± 1` ile güncellenmesi.** Sınanan eleman aralığın dışında bırakılır. `sag = orta` yazılırsa aralık küçülmeyebilir ve döngü sonsuza girer — sonlanma güvencesi tam olarak bu adımdan gelir. **Orta noktanın `sol + (sag - sol) // 2` ile hesaplanması.** `(sol + sag) // 2` yazımı, sabit genişlikli tam sayı kullanan dillerde büyük dizilerde taşabilir. Bilgisayarlar Nasıl Çalışır kursundaki taşma davranışı burada somut bir hataya dönüşür. #### Maliyet Her tur aralığı yarılar ve sabit iş yapar: $$ T(n) = T(n/2) + O(1) \implies T(n) = O(\log n) $$ En kötü durumda karşılaştırma sayısı $\lfloor \log_2 n \rfloor + 1$'dir. ```python from collections.abc import Sequence def sayimli_ikili_arama(dizi: Sequence[int], hedef: int) -> tuple[int, int]: sol, sag, sayac = 0, len(dizi) - 1, 0 while sol <= sag: orta = sol + (sag - sol) // 2 sayac += 1 if dizi[orta] == hedef: return orta, sayac if dizi[orta] < hedef: sol = orta + 1 else: sag = orta - 1 return -1, sayac for n in (1_000, 1_000_000, 1_000_000_000): # range dizinlenebilir olduğu için milyarlık dizi bellek ayrılmadan sınanır cift_sayilar = range(0, 2 * n, 2) print(n, sayimli_ikili_arama(cift_sayilar, n + 1)[1]) # tek sayı: dizide yok # 1000 10 # 1000000 20 # 1000000000 30 ``` Milyar elemanlı bir dizide otuz karşılaştırma yeterlidir. Doğrusal arama aynı işi bir milyar karşılaştırmayla yapar — Karmaşıklık Sınıflarını Okumak dersindeki ölçek büyütme tablosunun somut karşılığı budur. Alan maliyeti $O(1)$'dir. Aynı algoritma özyinelemeli de yazılabilir, ancak o durumda $O(\log n)$ yığıt alanı kullanır. #### Alt Sınır: Neden Daha Hızlısı Yok Karşılaştırmaya dayalı arama, her adımda üç sonuçtan birini üretir: küçük, eşit, büyük. Algoritmanın davranışı bir karar ağacı olarak çizilirse, ağacın her yaprağı olası bir yanıttır ve $n$ elemanlı dizide en az $n$ farklı yanıt vardır. Yüksekliği $h$ olan ikili bir ağacın en çok $2^h$ yaprağı olabilir. $2^h \geq n$ koşulundan $h \geq \log_2 n$ çıkar: karşılaştırmalı arama $\Omega(\log n)$'dir. Aynı karar ağacı fikri, sıralamanın alt sınırında yeniden kullanılacak. #### İlk ve Son Konum Dizide yinelenen değerler varsa, yukarıdaki gerçekleştirim **herhangi** bir eşleşmeyi döndürür. Sıralamayla ilgili birçok işlem ise ilk eşleşmeyi ister. **Alt sınır (lower bound)**, hedeften küçük olmayan ilk elemanın konumudur. Eşleşme yoksa, hedefin sıralamayı bozmadan eklenebileceği yeri verir. ```python def alt_sinir(dizi: list[int], hedef: int) -> int: """dizi[i] >= hedef koşulunu sağlayan en küçük i (yoksa len(dizi)). Değişmez: yanıt [sol, sag] aralığındadır; aralık yarı açık tutulur. """ sol, sag = 0, len(dizi) while sol < sag: orta = sol + (sag - sol) // 2 if dizi[orta] < hedef: sol = orta + 1 else: sag = orta return sol tekrarli = [1, 3, 3, 3, 7, 9, 9] print(alt_sinir(tekrarli, 3)) # 1 — ilk 3 print(alt_sinir(tekrarli, 9)) # 5 — ilk 9 print(alt_sinir(tekrarli, 4)) # 4 — eklenecek yer print(alt_sinir(tekrarli, 10)) # 7 — dizinin sonu ``` Bu değişke **yarı açık** aralık kullanır: `sag` aralığa dahil değildir. Bu yüzden döngü koşulu `sol < sag` ve güncelleme `sag = orta`'dır. İki değişkeyi karıştırmak, ikili aramadaki hataların en yaygın kaynağıdır — aralığın hangi biçimde tutulduğu bir kez seçilir ve tüm satırlar ona göre yazılır. Üst sınır, hedeften **büyük** ilk elemanı bulur; iki sonucun farkı, hedefin dizide kaç kez geçtiğini verir. #### Sıralı Dizinin Ötesinde İkili aramanın gerçek koşulu "dizi sıralı" değil, daha geneldir: **tekdüze bir yüklem** bulunmasıdır. Bir koşul, belirli bir noktaya kadar yanlış ve o noktadan sonra hep doğruysa, o nokta ikili aramayla bulunabilir. ```python def tam_karekok(n: int) -> int: """k*k <= n koşulunu sağlayan en büyük k.""" sol, sag, yanit = 0, n, 0 while sol <= sag: orta = sol + (sag - sol) // 2 if orta * orta <= n: yanit = orta sol = orta + 1 else: sag = orta - 1 return yanit print(tam_karekok(0), tam_karekok(15), tam_karekok(16), tam_karekok(10**18)) # 0 3 4 1000000000 ``` Ortada bir dizi yoktur; aranan şey, `orta * orta <= n` yükleminin doğru kaldığı son değerdir. Yüklem tekdüze olduğu için yarıya bölme geçerlidir. Bu genelleme yaygın bir tasarım aracıdır: "en küçük yeterli kapasite", "en büyük geçerli eşik" biçimindeki problemler, doğrudan denenecek değer aralığı üzerinde ikili aramayla çözülür. #### Ne Zaman Kullanılmaz İkili arama üç varsayıma dayanır ve biri bozulduğunda tercih edilmez. **Sıralılık bedavaya gelmiyorsa.** Tek bir arama için diziyi sıralamak $O(n \log n)$'dir; doğrusal arama $O(n)$. Sıralama ancak çok sorgulu kullanımda kendini öder. **Rastgele erişim yoksa.** Bağlı listede orta elemana gitmek doğrusaldır ve logaritmik kazanç yok olur. Veri Yapıları kursundaki arama ağaçları, tam olarak bu boşluğu doldurur. **Veri sürekli değişiyorsa.** Her eklemede sıralı diziyi güncellemek $O(n)$'dir; bu durumda dengeli ağaç veya karma tablosu daha uygundur. #### Özet - İkili arama sıralı veride aralığı yarılar; doğruluğu, aralığın anlamını sabit tutan bir değişmezle gerekçelendirilir. - Kapalı ve yarı açık aralık değişkeleri farklı döngü koşulu ve güncelleme ister; ikisi karıştırılmamalıdır. - Maliyet $T(n) = T(n/2) + O(1)$ bağıntısından $O(\log n)$ çıkar; alan $O(1)$'dir. - Karar ağacı akıl yürütmesi, karşılaştırmalı aramanın $\Omega(\log n)$ olduğunu gösterir. - Alt sınır değişkesi ilk eşleşmeyi veya ekleme konumunu verir. - Yöntem, tekdüze bir yüklemin doğru olduğu ilk değeri arayan her probleme uygulanır. #### Sonraki Adım İkili aramanın koşulu sıralılıktı; öyleyse sıralamanın kendisi incelenmelidir. Sonraki ders üç temel sıralama algoritmasını — kabarcık, seçmeli ve eklemeli — karesel maliyetleri, kararlılıkları ve birbirlerinden ayrıldıkları noktalarla ele alacak. ### Kabarcık, Seçmeli ve Eklemeli Sıralama Source: https://academia.sh/tr/kurslar/algoritmalar/temel-siralamalar Sıralama probleminin tanımı, kararlılık ve yerinde çalışma ölçütleri, üç karesel algoritmanın karşılaştırma ve taşıma maliyetleri, ters çift sayısı. İkili arama sıralılık varsayıyordu; öyleyse sıralamanın kendisi incelenmelidir. Sıralama, algoritma öğretiminin merkezinde durur: aynı problem, farklı fikirlerle onlarca kez çözülmüş ve çözümler tam olarak bu kursun araçlarıyla karşılaştırılmıştır. Bu ders karesel maliyetli üç temel algoritmayı ele alır. Amaç yalnızca onları öğrenmek değil, sonraki derslerin daha iyi algoritmalarını karşılaştıracak bir taban kurmaktır. #### Problem ve Ölçütler **Sıralama problemi:** Girdi, karşılaştırılabilir elemanlardan oluşan bir dizidir. Çıktı, aynı elemanların bir **permütasyonu** olan ve azalmayan sırada dizilmiş bir dizidir. İki koşul da gereklidir. Yalnızca sıralılık istenirse, girdiyi silip boş dizi döndürmek "çözüm" sayılırdı; permütasyon koşulu bunu engeller. Sıralama algoritmaları üç ölçütle ayrılır: **Kararlılık (stability).** Eşit anahtarlı elemanların göreli sırası korunuyorsa algoritma kararlıdır. Çok anahtarlı sıralamalarda belirleyicidir: önce şehre, sonra kararlı bir algoritmayla tarihe göre sıralanan kayıtlarda şehir sırası bozulmaz. **Yerinde çalışma.** Ek alan sabitse algoritma yerindedir. **Uyarlanabilirlik.** Girdi kısmen sıralıysa maliyeti düşüyorsa algoritma uyarlanabilirdir. Ayrıca iki ayrı maliyet sayılır: **karşılaştırma** sayısı ve **taşıma** (yer değiştirme veya kaydırma) sayısı. Elemanlar büyük nesnelerse taşıma pahalıdır; karşılaştırma karmaşık bir işlevse karşılaştırma pahalıdır. #### Kabarcık Sıralama Komşu elemanlar karşılaştırılır ve sıra bozuksa yer değiştirilir. Her geçişte en büyük eleman sona "kabarır". ```python def kabarcik_siralama(dizi: list[int]) -> list[int]: """Değişmez: her dış turdan sonra son `n - son` eleman kesin yerindedir.""" d = list(dizi) for son in range(len(d) - 1, 0, -1): degisim = False for i in range(son): if d[i] > d[i + 1]: d[i], d[i + 1] = d[i + 1], d[i] degisim = True if not degisim: # hiç değişim yoksa dizi sıralıdır break return d print(kabarcik_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` Erken çıkış bayrağı olmadan algoritma her durumda $n(n-1)/2$ karşılaştırma yapar. Bayrakla birlikte sıralı girdide tek geçişte durur: en iyi durum $O(n)$ olur. En kötü ve ortalama durum $O(n^2)$'dir. Taşıma sayısı da karesel olabilir — ters sıralı girdide her karşılaştırma bir yer değiştirmeye yol açar. Algoritma kararlıdır (yalnızca kesin büyüklükte yer değiştirilir) ve yerindedir. #### Seçmeli Sıralama Kalan bölümün en küçüğü bulunur ve bulunduğu yerle sınırın başı yer değiştirir. ```python def secmeli_siralama(dizi: list[int]) -> list[int]: """Değişmez: her turdan sonra ilk i eleman kesin sıralıdır.""" d = list(dizi) for i in range(len(d) - 1): en_kucuk = i for j in range(i + 1, len(d)): if d[j] < d[en_kucuk]: en_kucuk = j d[i], d[en_kucuk] = d[en_kucuk], d[i] return d print(secmeli_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` Karşılaştırma sayısı girdiden bağımsızdır: her zaman $n(n-1)/2$. Uyarlanabilir değildir — sıralı girdide de tam maliyeti öder. Buna karşılık **taşıma sayısı en çok $n-1$**'dir ve bu, algoritmanın tek üstünlüğüdür: elemanlar çok büyükse veya yazma işlemi pahalıysa (bazı kalıcı bellek türlerinde okuma ile yazma maliyeti eşit değildir), az yazma yapan bir algoritma tercih edilebilir. Bu biçimiyle kararlı **değildir**: uzak bir elemanla yer değiştirme, eşit anahtarlıların sırasını bozabilir. ```python def secmeli_siralama_kayit(kayitlar: list[tuple[int, str]]) -> list[tuple[int, str]]: """Yalnızca ilk alana (anahtara) göre sıralar; ikinci alan kimliktir.""" d = list(kayitlar) for i in range(len(d) - 1): en_kucuk = i for j in range(i + 1, len(d)): if d[j][0] < d[en_kucuk][0]: en_kucuk = j d[i], d[en_kucuk] = d[en_kucuk], d[i] return d print(secmeli_siralama_kayit([(2, "a"), (2, "b"), (1, "c")])) # [(1, 'c'), (2, 'b'), (2, 'a')] ``` Çıktıda `b`, `a`'nın önüne geçmiştir; girdide sıra tersineydi. Yer değiştirme yerine kaydırma yapan bir değişke kararlı olur, ama o zaman taşıma üstünlüğü kaybolur. #### Eklemeli Sıralama Her eleman, kendisinden önceki sıralı bölüme doğru yerine kaydırılarak eklenir. İskambil kâğıtlarını elde sıralama biçimi budur. ```python def eklemeli_siralama(dizi: list[int]) -> list[int]: """Değişmez: her turun başında ilk i eleman kendi arasında sıralıdır.""" d = list(dizi) for i in range(1, len(d)): anahtar = d[i] j = i - 1 while j >= 0 and d[j] > anahtar: d[j + 1] = d[j] # kaydır j -= 1 d[j + 1] = anahtar return d def eklemeli_siralama_kayit(kayitlar: list[tuple[int, str]]) -> list[tuple[int, str]]: d = list(kayitlar) for i in range(1, len(d)): anahtar = d[i] j = i - 1 while j >= 0 and d[j][0] > anahtar[0]: d[j + 1] = d[j] j -= 1 d[j + 1] = anahtar return d print(eklemeli_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(eklemeli_siralama_kayit([(2, "a"), (2, "b"), (1, "c")])) # [(1, 'c'), (2, 'a'), (2, 'b')] — girdideki a, b sırası korundu ``` Döngü koşulundaki `>` işareti kararlılığın kaynağıdır: eşitlikte kaydırma durur, yeni eleman eşitinin arkasına yerleşir. `>=` yazılsaydı algoritma kararlılığını yitirirdi. En iyi durum sıralı girdidir: iç döngü hiç çalışmaz, maliyet $O(n)$. En kötü durum ters sıralı girdidir: $n(n-1)/2$ kaydırma, $O(n^2)$. Ortalama durumda her eleman sıralı bölümün yarısı kadar kayar; yine karesel ama sabiti küçüktür. #### Ters Çift Sayısı Eklemeli sıralamanın maliyeti, girdinin "ne kadar bozuk" olduğuyla tam olarak ölçülebilir. **Ters çift (inversion)**, $i < j$ iken $d_i > d_j$ olan çiftlerdir. Sıralı dizide sıfır, ters sıralı dizide $n(n-1)/2$ tanedir. Eklemeli sıralamanın yaptığı her kaydırma tam olarak bir ters çifti giderir; dolayısıyla toplam kaydırma sayısı ters çift sayısına eşittir ve maliyet $O(n + \text{ters çift})$ olur. ```python def ters_cift_sayisi(dizi: list[int]) -> int: return sum(1 for i in range(len(dizi)) for j in range(i + 1, len(dizi)) if dizi[i] > dizi[j]) def eklemeli_kaydirma_sayisi(dizi: list[int]) -> int: d, sayac = list(dizi), 0 for i in range(1, len(d)): anahtar, j = d[i], i - 1 while j >= 0 and d[j] > anahtar: d[j + 1] = d[j] j -= 1 sayac += 1 d[j + 1] = anahtar return sayac for ornek in ([1, 2, 3, 4, 5], [5, 2, 9, 1, 5, 6], [5, 4, 3, 2, 1]): print(ornek, ters_cift_sayisi(ornek), eklemeli_kaydirma_sayisi(ornek)) # [1, 2, 3, 4, 5] 0 0 # [5, 2, 9, 1, 5, 6] 6 6 # [5, 4, 3, 2, 1] 10 10 ``` İki sütunun her satırda eşit olması rastlantı değildir; algoritmanın ne yaptığının tam tanımıdır. Sonuç pratikte önemlidir: **neredeyse sıralı** veride eklemeli sıralama doğrusala yakın çalışır. Sıralı bir kütüğe birkaç yeni kayıt eklenmiş bir dizi bu tanıma girer. #### Karşılaştırma | Ölçüt | Kabarcık | Seçmeli | Eklemeli | |---|---|---|---| | En iyi durum | $O(n)$ (bayrakla) | $O(n^2)$ | $O(n)$ | | Ortalama / en kötü | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | | Taşıma sayısı | $O(n^2)$ | $O(n)$ | $O(n^2)$ | | Kararlı | Evet | Hayır | Evet | | Yerinde | Evet | Evet | Evet | | Uyarlanabilir | Evet | Hayır | Evet | Üçü de karesel sınıftadır; aralarındaki fark sabitlerde ve ikincil ölçütlerdedir. Pratikte eklemeli sıralama, küçük dizilerde ve neredeyse sıralı veride öne çıkar — bu nedenle gelişmiş sıralama gerçekleştirimleri, küçük parçalarda ona geçer. Kabarcık sıralamanın belirgin bir üstünlüğü yoktur; öğretici değeri, komşu takas fikrinin en yalın hâli olmasıdır. #### Özet - Sıralama problemi iki koşul ister: çıktı sıralı olmalı ve girdinin bir permütasyonu olmalıdır. - Algoritmalar kararlılık, yerinde çalışma ve uyarlanabilirlik ölçütleriyle ayrılır; karşılaştırma ve taşıma sayıları ayrı sayılır. - Kabarcık sıralama komşu takasla çalışır; erken çıkış bayrağı en iyi durumu doğrusala indirir. - Seçmeli sıralama her zaman karesel karşılaştırma yapar ama doğrusal sayıda taşıma yapar; bu biçimiyle kararlı değildir. - Eklemeli sıralama kararlı, yerinde ve uyarlanabilirdir; kaydırma sayısı ters çift sayısına eşittir. - Üçü de karesel sınıftadır; fark sabitlerde ve ikincil ölçütlerdedir. #### Sonraki Adım Karesel sınıf, ölçek büyütme tablosunun gösterdiği gibi milyonluk verilerde kullanılamazdı. Sonraki ders, karmaşıklık hesabı dersinde bağıntısı çözülen böl ve yönet fikrini sıralamaya uygular: birleştirmeli sıralama, $O(n \log n)$ güvencesini kararlılıkla birlikte verir. ### Birleştirmeli Sıralama Source: https://academia.sh/tr/kurslar/algoritmalar/birlestirmeli-siralama Böl ve yönet ile kararlı sıralama, birleştirme işleminin doğruluğu, alttan yukarı değişke, dış sıralama ve ters çift sayımı. Karesel algoritmalar milyonluk verilerde kullanılamaz. Karmaşıklık Hesaplama Yöntemi dersinde çözülen bağıntı, çıkış yolunu zaten göstermişti: $$ T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n) $$ Bu ders, o bağıntıyı üreten algoritmayı kurar: diziyi ikiye böl, her yarıyı sırala, sıralı iki yarıyı birleştir. #### Birleştirme Algoritmanın çekirdeği, **sıralı iki diziyi tek sıralı diziye** birleştirmektir. İki imleç kullanılır; her adımda küçük olan alınır. ```python def birlestir(sol: list[int], sag: list[int]) -> list[int]: """Sıralı iki diziyi sıralı tek diziye birleştirir. Değişmez: sonuç, iki dizinin alınmış elemanlarının sıralı hâlidir ve alınmayan her eleman sonuçtaki her elemandan küçük değildir. """ sonuc: list[int] = [] i = j = 0 while i < len(sol) and j < len(sag): if sol[i] <= sag[j]: # eşitlikte sol öncelikli: kararlılık sonuc.append(sol[i]) i += 1 else: sonuc.append(sag[j]) j += 1 sonuc.extend(sol[i:]) # biri bittiğinde diğerinin kalanı eklenir sonuc.extend(sag[j:]) return sonuc print(birlestir([1, 5, 9], [2, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` Birleştirme $O(n)$'dir: her eleman tam bir kez alınır ve bir daha bakılmaz. `<=` işareti kararlılığın kaynağıdır. Eşitlikte soldaki — yani girdide önce gelen — eleman seçilir. `<` yazılırsa algoritma kararlılığını yitirir; bu, tek karakterlik bir farkın davranışsal bir özelliği belirlediği örneklerden biridir. #### Böl ve Yönet Kalan yalnızca özyinelemeli çatıdır. ```python def birlestirmeli_siralama(dizi: list[int]) -> list[int]: if len(dizi) <= 1: # taban durumu: sıfır veya tek eleman sıralıdır return list(dizi) orta = len(dizi) // 2 sol = birlestirmeli_siralama(dizi[:orta]) sag = birlestirmeli_siralama(dizi[orta:]) return birlestir(sol, sag) print(birlestirmeli_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(birlestirmeli_siralama([])) # [] print(birlestirmeli_siralama([3, 3, 3])) # [3, 3, 3] ``` Doğruluğu tümevarımla gerekçelendirilir: taban durumu doğrudur; iki yarı doğru sıralanmışsa birleştirme işlemi de doğru bir sıralı dizi üretir. Sonlanma, alt problemlerin kesin olarak küçülmesinden gelir — `orta` hesabı, her iki parçanın da boş olmamasını sağlar. #### Maliyet Özyineleme ağacının her düzeyinde toplam $n$ birim birleştirme işi yapılır ve düzey sayısı $\log_2 n$'dir. Bölme, girdinin içeriğine bakmadan yapıldığı için **her durumda** aynıdır: | Durum | Karşılaştırma | Sınıf | |---|---|---| | En iyi | $\sim \frac{n \log_2 n}{2}$ | $\Theta(n \log n)$ | | Ortalama | $\sim n \log_2 n$ | $\Theta(n \log n)$ | | En kötü | $\sim n \log_2 n$ | $\Theta(n \log n)$ | Girdi ne olursa olsun aynı maliyet — bu güvence, sonraki dersteki hızlı sıralamanın sahip olmadığı özelliktir. Alan maliyeti algoritmanın zayıf noktasıdır: birleştirme, sonuç için $O(n)$ ek dizi kullanır. Buna özyineleme yığıtının $O(\log n)$ derinliği eklenir. Dizi üzerinde çalışan yerinde birleştirme değişkeleri vardır, ancak sabitleri büyüktür ve kodu karmaşıklaştırır. ```python def sayimli_siralama(dizi: list[int]) -> tuple[list[int], int]: """(sıralı dizi, karşılaştırma sayısı)""" if len(dizi) <= 1: return list(dizi), 0 orta = len(dizi) // 2 sol, a = sayimli_siralama(dizi[:orta]) sag, b = sayimli_siralama(dizi[orta:]) sonuc: list[int] = [] i = j = sayac = 0 while i < len(sol) and j < len(sag): sayac += 1 if sol[i] <= sag[j]: sonuc.append(sol[i]); i += 1 else: sonuc.append(sag[j]); j += 1 sonuc.extend(sol[i:]); sonuc.extend(sag[j:]) return sonuc, a + b + sayac import math for n in (16, 1024, 65_536): veri = [(i * 7919) % n for i in range(n)] # düzenli ama sıralı olmayan girdi print(n, sayimli_siralama(veri)[1], int(n * math.log2(n))) # 16 35 64 # 1024 8929 10240 # 65536 956515 1048576 ``` Ölçülen karşılaştırma sayısı $n \log_2 n$ tahmininin altında kalır; birleştirmede bir dizi erkenden tükendiğinde kalan elemanlar karşılaştırmasız aktarıldığı için gerçek sayı sınırın biraz altındadır. Mertebe aynıdır. #### Alttan Yukarı Değişke Aynı algoritma özyinelemesiz yazılabilir: önce bir elemanlık bloklar ikişer ikişer birleştirilir, sonra ikişerlikler, sonra dörderlikler. ```python def alttan_birlestirmeli(dizi: list[int]) -> list[int]: d = list(dizi) genislik = 1 while genislik < len(d): for bas in range(0, len(d), 2 * genislik): orta = min(bas + genislik, len(d)) son = min(bas + 2 * genislik, len(d)) d[bas:son] = birlestir(d[bas:orta], d[orta:son]) genislik *= 2 return d print(alttan_birlestirmeli([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(alttan_birlestirmeli([4, 3, 2, 1])) # [1, 2, 3, 4] ``` Sonuç aynıdır, yığıt alanı harcanmaz. Uyarlanabilir bir değişke, bir elemanlık bloklar yerine girdide zaten sıralı olan **koşuları (run)** başlangıç blokları sayar; neredeyse sıralı veride düzey sayısını düşürür. #### Ardışık Erişimle Çalışması Birleştirme, elemanlara baştan sona tek yönde erişir; rastgele erişim gerektirmez. Bu özellik iki alanda belirleyicidir. **Bağlı listelerde.** Veri Yapıları kursundaki bağlı listede orta elemana gitmek doğrusaldır, ama birleştirme yalnızca bağlantı yeniden yönlendirmesiyle yapılır. Bağlı listeler için pratikte tercih edilen sıralama budur ve ek dizi gerektirmez. **Dış sıralamada.** Veri belleğe sığmıyorsa, parçalar tek tek belleğe alınıp sıralanır, diske yazılır, sonra sıralı parçalar akış hâlinde birleştirilir. Birleştirmenin tek yönlü okuma yapması, disk veya ağ üzerinden ardışık okumayı mümkün kılar — Bilgisayarlar Nasıl Çalışır kursundaki yerellik ilkesinin doğrudan sonucu. #### Ters Çiftleri Saymak Bir önceki dersteki ters çift sayısı, kaba kuvvetle $O(n^2)$'de hesaplanıyordu. Birleştirme sırasında sağdaki elemanın öne geçtiği her durum, soldaki **kalan tüm elemanlarla** ters çift oluşturur; bu gözlem sayımı $O(n \log n)$'e indirir. ```python def ters_cift_hizli(dizi: list[int]) -> tuple[list[int], int]: if len(dizi) <= 1: return list(dizi), 0 orta = len(dizi) // 2 sol, a = ters_cift_hizli(dizi[:orta]) sag, b = ters_cift_hizli(dizi[orta:]) sonuc: list[int] = [] i = j = sayac = 0 while i < len(sol) and j < len(sag): if sol[i] <= sag[j]: sonuc.append(sol[i]); i += 1 else: sonuc.append(sag[j]); j += 1 sayac += len(sol) - i # soldaki kalan elemanların hepsi ters çift sonuc.extend(sol[i:]); sonuc.extend(sag[j:]) return sonuc, a + b + sayac print(ters_cift_hizli([5, 2, 9, 1, 5, 6])[1]) # 6 print(ters_cift_hizli([5, 4, 3, 2, 1])[1]) # 10 print(ters_cift_hizli(list(range(1000)))[1]) # 0 ``` Sonuçlar kaba kuvvet sayımıyla aynıdır. Bu, böl ve yönet fikrinin sıralamanın ötesinde de kullanıldığının ilk örneğidir: birleştirme adımına yapılan küçük bir ekleme, bambaşka bir büyüklüğü hesaplar. #### Özet - Birleştirmeli sıralama diziyi ikiye böler, yarıları sıralar ve sıralı yarıları doğrusal maliyetle birleştirir. - Birleştirmede eşitlikte soldaki elemanın seçilmesi kararlılığı sağlar. - Maliyet her durumda $\Theta(n \log n)$'dir; bölme girdinin içeriğine bağlı değildir. - Ek alan $O(n)$'dir; bu, algoritmanın başlıca bedelidir. - Alttan yukarı değişke özyineleme yığıtını ortadan kaldırır; koşu tabanlı değişke uyarlanabilirlik kazandırır. - Ardışık erişimle çalıştığı için bağlı listelerde ve dış sıralamada tercih edilir. #### Sonraki Adım Birleştirmeli sıralama güvenli ama ek alan ister. Sonraki ders, aynı doğrusal-logaritmik mertebeyi yerinde çalışarak elde eden hızlı sıralamayı ele alacak — karşılığında en kötü durum güvencesini kaybederek. Pivot seçiminin bu kaybı nasıl olasılığa çevirdiği dersin merkezinde olacak. ### Hızlı Sıralama Source: https://academia.sh/tr/kurslar/algoritmalar/hizli-siralama Bölümleme ile yerinde sıralama, pivot seçiminin ortalama ve en kötü duruma etkisi, üç yollu bölümleme ve k'ıncı elemanı seçme. Birleştirmeli sıralama işi birleştirme adımında yapıyordu: bölme ucuz, birleştirme pahalıydı. Hızlı sıralama bunu tersine çevirir — **bölme pahalı, birleştirme yoktur**. Fikir şudur: bir eleman seçilir (pivot), dizi ondan küçükler ve büyükler olarak ikiye ayrılır. Pivot artık kesin yerindedir; iki parça bağımsız sıralanır ve yan yana durdukları için ek bir işlem gerekmez. #### Bölümleme Bölümleme, pivotu son eleman seçip diziyi tek geçişte iki bölgeye ayırır. ```python def bolumle(d: list[int], bas: int, son: int) -> int: """d[bas..son] aralığını pivota göre böler, pivotun son konumunu döndürür. Değişmez: d[bas..i] pivottan küçük veya eşit, d[i+1..j-1] pivottan büyük. """ pivot = d[son] i = bas - 1 for j in range(bas, son): if d[j] <= pivot: i += 1 d[i], d[j] = d[j], d[i] d[i + 1], d[son] = d[son], d[i + 1] return i + 1 ornek = [5, 2, 9, 1, 5, 6] k = bolumle(ornek, 0, len(ornek) - 1) print(k, ornek) # 4 [5, 2, 1, 5, 6, 9] ``` Pivot değeri 6'dır; işlem sonunda 4 numaralı dizine yerleşir. Solunda ondan büyük hiçbir eleman, sağında ondan küçük hiçbir eleman kalmaz. Bölümleme $O(n)$ zaman, $O(1)$ ek alan kullanır. Bu **Lomuto** bölümlemesidir; yazımı kısadır. **Hoare** bölümlemesi iki uçtan ortaya doğru ilerler, daha az yer değiştirme yapar ve pratikte tercih edilir; karşılığında sınır koşulları daha incedir ve pivotun kesin konumunu döndürmez. #### Özyinelemeli Çatı ```python def hizli_siralama(dizi: list[int]) -> list[int]: d = list(dizi) def sirala(bas: int, son: int) -> None: if bas >= son: # taban durumu: sıfır veya tek eleman return k = bolumle(d, bas, son) sirala(bas, k - 1) sirala(k + 1, son) # pivot (k) yerinde; yeniden işlenmez sirala(0, len(d) - 1) return d print(hizli_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(hizli_siralama([]), hizli_siralama([4])) # [] [4] ``` Doğruluk tümevarımla gelir: bölümlemeden sonra pivot kesin yerindedir ve iki parça birbirinden bağımsızdır; parçalar doğru sıralanırsa tüm dizi sıralıdır. Algoritma **yerindedir** — ek alan yalnızca özyineleme yığıtıdır — ve **kararlı değildir**: uzak elemanlarla yer değiştirme, eşit anahtarlıların sırasını bozar. #### Maliyet ve Pivot Seçimi Maliyet, bölümlemenin ne kadar dengeli olduğuna bağlıdır. **Dengeli bölme.** Pivot her seferinde ortaya düşerse bağıntı $T(n) = 2T(n/2) + O(n)$ olur ve sonuç $\Theta(n \log n)$'dir. **Dengesiz bölme.** Pivot her seferinde en küçük veya en büyük eleman olursa bir parça boş kalır: $T(n) = T(n-1) + O(n)$, yani $\Theta(n^2)$. İkinci durum kuramsal değildir. Son elemanı pivot seçen yukarıdaki gerçekleştirim, **zaten sıralı** bir dizide tam olarak bu davranışı gösterir. ```python def bolumleme_sayaci(dizi: list[int]) -> int: """Bölümleme karşılaştırmalarının toplam sayısı.""" d, toplam = list(dizi), 0 def sirala(bas: int, son: int) -> None: nonlocal toplam if bas >= son: return toplam += son - bas k = bolumle(d, bas, son) sirala(bas, k - 1) sirala(k + 1, son) sirala(0, len(d) - 1) return toplam n = 500 print(bolumleme_sayaci(list(range(n)))) # 124750 — sıralı: karesel print(bolumleme_sayaci([(i * 7919) % n for i in range(n)])) # 5322 — dengeli girdi ``` Sıralı girdide karşılaştırma sayısı $n(n-1)/2$'ye tam olarak eşittir. Aynı boyuttaki dengeli girdide sayı yirmi kattan fazla düşer. Çözüm pivotu daha dikkatli seçmektir: | Seçim | En kötü durumu tetikleyen girdi | |---|---| | İlk veya son eleman | Sıralı veya ters sıralı dizi | | Ortadaki eleman | Özel olarak kurulmuş dizi | | Üçün ortancası (ilk, orta, son) | Özel olarak kurulmuş dizi | | Rastgele eleman | Yok — girdi belirlemez | İlk üçü belirlidir (deterministic); yeterince bilgili bir karşı oyuncu, algoritmayı karesele düşüren girdiyi her zaman üretebilir. Rastgele pivotta ise girdinin hangi elemanının seçileceği belli olmadığından beklenen maliyet $O(n \log n)$'dir ve bu, girdiye değil rastgeleliğe dayanır. Beklenen maliyetin doğrusal-logaritmik olmasının nedeni, bölmelerin **çoğunlukla makul** olmasıdır: rastgele bir pivot, ortadaki yarıya yaklaşık $1/2$ olasılıkla düşer ve böyle bir bölme problem boyutunu en az dörtte üç oranında küçültür. Sabit olasılıkla sabit oranda küçülme, logaritmik derinlik demektir. Yığıt derinliği de denetlenebilir: önce **küçük** parça özyinelemeye verilir, büyük parça döngüyle işlenirse yığıt derinliği en kötü durumda bile $O(\log n)$ kalır. #### Yinelenen Anahtarlar Dizinin tamamı aynı değerden oluşuyorsa, Lomuto bölümlemesi her elemanı küçük-eşit bölgesine koyar ve bölme yine dengesizleşir. Çözüm, diziyi **üç** bölgeye ayırmaktır: küçükler, eşitler, büyükler. ```python def uc_yollu_siralama(dizi: list[int]) -> list[int]: if len(dizi) <= 1: return list(dizi) pivot = dizi[len(dizi) // 2] kucuk = [x for x in dizi if x < pivot] esit = [x for x in dizi if x == pivot] buyuk = [x for x in dizi if x > pivot] return uc_yollu_siralama(kucuk) + esit + uc_yollu_siralama(buyuk) print(uc_yollu_siralama([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(uc_yollu_siralama([3, 3, 3, 3, 3])) # [3, 3, 3, 3, 3] ``` Eşitler bölgesi bir daha işlenmez; yalnızca birkaç farklı değer içeren dizilerde maliyet doğrusala yaklaşır. Buradaki yazım okunurluk için yeni listeler üretir; yerinde çalışan üç yollu bölümleme aynı fikri ek alan kullanmadan uygular. #### Seçme Problemi Bölümlemenin ikinci kullanımı, tüm diziyi sıralamadan **k'ıncı en küçük** elemanı bulmaktır. Bölümleme sonrası pivotun konumu bilindiğine göre, aranan eleman yalnızca bir tarafta olabilir; diğer taraf hiç işlenmez. ```python def hizli_sec(dizi: list[int], k: int) -> int: """k'ıncı en küçük eleman (k sıfırdan başlar).""" d = list(dizi) bas, son = 0, len(d) - 1 while True: if bas == son: return d[bas] p = bolumle(d, bas, son) if p == k: return d[p] if k < p: son = p - 1 else: bas = p + 1 veri = [5, 2, 9, 1, 5, 6] print(hizli_sec(veri, 0), hizli_sec(veri, 3), hizli_sec(veri, 5)) # 1 5 9 print(sorted(veri)[3]) # 5 ``` Beklenen maliyet $O(n)$'dir: her adımda problem boyutu sabit bir oranda küçülür ve maliyetler $n + n/2 + n/4 + \dots < 2n$ biçiminde toplanır. Sıralayıp k'ıncıyı okumak $O(n \log n)$ olurdu. Aynı problemin en kötü durumu da doğrusal olan bir çözümü vardır ("ortancaların ortancası"), ancak sabiti büyüktür ve pratikte rastgele pivotlu seçme tercih edilir. #### Özet - Hızlı sıralama pivota göre bölümler ve birleştirme adımı gerektirmez; yerinde çalışır, kararlı değildir. - Bölümleme $O(n)$ zaman ve $O(1)$ ek alan kullanır; pivot kesin yerine oturur. - Dengeli bölmede maliyet $\Theta(n \log n)$, dengesiz bölmede $\Theta(n^2)$'dir. - Belirli pivot seçimleri karesel girdilerle tetiklenebilir; rastgele pivot beklenen maliyeti girdiden bağımsız kılar. - Üç yollu bölümleme, yinelenen anahtarlarda maliyeti düşürür. - Aynı bölümleme, k'ıncı elemanı beklenen doğrusal maliyetle bulur. #### Sonraki Adım Hızlı sıralama yerinde çalışıyor ama en kötü durum güvencesi yok; birleştirmeli sıralamada güvence var ama ek alan gerekiyor. Sonraki ders ikisini birleştiren üçüncü yolu ele alacak: yığın sıralaması, Veri Yapıları kursundaki yığın yapısını kullanarak yerinde çalışır ve her durumda $O(n \log n)$ verir. ### Yığın Sıralaması Source: https://academia.sh/tr/kurslar/algoritmalar/yigin-siralamasi Dizi üzerinde ikili yığın, aşağı süzme, doğrusal maliyetli yığın kurma, yerinde ve garantili doğrusal-logaritmik sıralama, ilk k eleman. Elde iki seçenek vardı: her durumda güvenceli ama $O(n)$ ek alan isteyen birleştirmeli sıralama, ya da yerinde çalışan ama en kötü durumu karesel olan hızlı sıralama. Üçüncü bir yol, her iki iyi özelliği birden verir. Araç, Veri Yapıları kursunda tanıtılan **ikili yığındır (binary heap)**. #### Diziyle Yığın Yığın, tam ikili bir ağaçtır ve tam olduğu için işaretçi olmadan bir dizide tutulabilir. `i` numaralı düğüm için: - Sol çocuk: `2i + 1` - Sağ çocuk: `2i + 2` - Ebeveyn: `(i - 1) // 2` **Maksimum yığın koşulu**, her düğümün çocuklarından küçük olmamasıdır. Kök, dizinin en büyük elemanıdır. Koşul bozulduğunda düzelten işlem **aşağı süzmedir**: bir düğüm, çocuklarının büyüğüyle yer değiştirerek yerini bulana kadar iner. ```python def asagi_suz(d: list[int], kok: int, sinir: int) -> None: """d[kok] düğümünü, d[0..sinir) yığınında yerine indirir. Değişmez: kök dışındaki her düğüm yığın koşulunu sağlar. Sonlanma: kok her turda en az bir düzey artar. """ while True: en_buyuk = kok sol, sag = 2 * kok + 1, 2 * kok + 2 if sol < sinir and d[sol] > d[en_buyuk]: en_buyuk = sol if sag < sinir and d[sag] > d[en_buyuk]: en_buyuk = sag if en_buyuk == kok: return d[kok], d[en_buyuk] = d[en_buyuk], d[kok] kok = en_buyuk ``` Maliyet, düğümün inebileceği düzey sayısıyla sınırlıdır: $O(\log n)$. #### Yığın Kurmak Doğrusaldır Sırasız bir diziyi yığına çevirmenin yolu, yaprak olmayan düğümleri **sondan başa** doğru süzmektir. Yapraklar zaten geçerli birer yığındır, dolayısıyla işlem ortadan başlar. ```python def yigin_kur(d: list[int]) -> None: for i in range(len(d) // 2 - 1, -1, -1): asagi_suz(d, i, len(d)) ornek = [5, 2, 9, 1, 5, 6] yigin_kur(ornek) print(ornek) # [9, 5, 6, 1, 2, 5] ``` Yüzeysel bakış $n$ düğümün her biri için $O(\log n)$ verip $O(n \log n)$ tahmin eder. Gerçek maliyet daha düşüktür, çünkü düğümlerin çoğu **kısa** yolları kat eder: yaprağa yakın düğümler çoğunluktadır ve az iner. Yükseklik $h$ olan düğüm sayısı en çok $n / 2^{h+1}$'dir ve her biri en çok $h$ adım iner: $$ \sum_{h=0}^{\log n} \frac{n}{2^{h+1}} \cdot h \;\leq\; n \sum_{h=0}^{\infty} \frac{h}{2^{h+1}} = n $$ Toplam $O(n)$'dir — yığın kurmak, tek tek ekleme yapmaktan ($O(n \log n)$) ucuzdur. ```python def kurma_adimlari(d: list[int]) -> int: sayac = 0 def suz(kok: int, sinir: int) -> None: nonlocal sayac while True: en_buyuk, sol, sag = kok, 2 * kok + 1, 2 * kok + 2 if sol < sinir and d[sol] > d[en_buyuk]: en_buyuk = sol if sag < sinir and d[sag] > d[en_buyuk]: en_buyuk = sag if en_buyuk == kok: return d[kok], d[en_buyuk] = d[en_buyuk], d[kok] sayac += 1 kok = en_buyuk for i in range(len(d) // 2 - 1, -1, -1): suz(i, len(d)) return sayac for n in (1_000, 10_000, 100_000): veri = [(i * 7919) % n for i in range(n)] print(n, kurma_adimlari(veri)) # 1000 706 # 10000 7529 # 100000 71808 ``` Yer değiştirme sayısı $n$ ile doğru orantılı kalır — üç ölçümde de yaklaşık $0{,}72n$. $n \log_2 n$ olsaydı yüz bin eleman için bir buçuk milyonu aşardı. #### Sıralama Yığın kurulduktan sonra sıralama basittir: kök (en büyük) dizinin sonuna alınır, yığın sınırı bir küçültülür ve yeni kök süzülür. ```python def yigin_siralamasi(dizi: list[int]) -> list[int]: d = list(dizi) yigin_kur(d) for sinir in range(len(d) - 1, 0, -1): d[0], d[sinir] = d[sinir], d[0] # en büyüğü yerine koy asagi_suz(d, 0, sinir) # kalan bölümü onar return d print(yigin_siralamasi([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] print(yigin_siralamasi([3, 3, 3])) # [3, 3, 3] print(yigin_siralamasi([])) # [] ``` Değişmez şudur: her turdan sonra dizinin sağ ucu kesin sıralıdır ve sol bölüm geçerli bir yığındır. Maliyet: kurma $O(n)$, ardından $n-1$ kez $O(\log n)$ süzme; toplam $\Theta(n \log n)$ — **her durumda**. En kötü durum güvencesi vardır ve ek alan $O(1)$'dir; algoritma yerinde çalışır. Kararlı değildir: kökle sondaki elemanın yer değiştirmesi, eşit anahtarlıların sırasını bozar. #### Üç Algoritmanın Karşılaştırması | Ölçüt | Birleştirmeli | Hızlı | Yığın | |---|---|---|---| | En kötü durum | $\Theta(n \log n)$ | $\Theta(n^2)$ | $\Theta(n \log n)$ | | Ortalama | $\Theta(n \log n)$ | $\Theta(n \log n)$ | $\Theta(n \log n)$ | | Ek alan | $O(n)$ | $O(\log n)$ yığıt | $O(1)$ | | Kararlı | Evet | Hayır | Hayır | | Bellek erişimi | Ardışık | Çoğunlukla yerel | Dağınık | Son satır, yığın sıralamasının neden en iyi güvencelere sahip olmasına karşın pratikte her zaman ilk tercih olmadığını açıklar. Süzme işlemi diziyi `2i + 1` sıçramalarıyla gezer; Bilgisayarlar Nasıl Çalışır kursundaki önbellek satırı mantığı burada aleyhe işler. Hızlı sıralamanın bölümlemesi ise diziyi baştan sona ardışık okur. Bu gözlem, yaygın bir karma tasarımı doğurur: hızlı sıralamayla başlanır, özyineleme derinliği bir eşiği aşarsa (yani bölmeler dengesizleşiyorsa) yığın sıralamasına geçilir ve küçük parçalar eklemeli sıralamaya bırakılır. Sonuç, hızlı sıralamanın pratik hızını yığın sıralamasının en kötü durum güvencesiyle birleştirir. #### İlk k Eleman Yığının sıralama dışındaki asıl kullanımı **öncelik kuyruğudur**; bunun sıralamaya en yakın uygulaması, tüm veriyi sıralamadan en büyük $k$ elemanı bulmaktır. Yöntem, $k$ boyutlu bir **minimum** yığın tutmaktır: yeni eleman yığının kökünden büyükse kök atılır, yenisi girer. ```python import heapq def en_buyuk_k(veri: list[int], k: int) -> list[int]: """En büyük k elemanı artan sırada döndürür. Maliyet O(n log k).""" yigin: list[int] = [] for deger in veri: if len(yigin) < k: heapq.heappush(yigin, deger) elif deger > yigin[0]: heapq.heapreplace(yigin, deger) return sorted(yigin) veri = [(i * 7919) % 1000 for i in range(1000)] print(en_buyuk_k(veri, 5)) # [995, 996, 997, 998, 999] print(en_buyuk_k([5, 2, 9, 1, 5, 6], 3)) # [5, 6, 9] ``` Maliyet $O(n \log k)$'dir; $k$ küçükse bu, sıralamanın $O(n \log n)$'inden belirgin biçimde ucuzdur. Ek alan $O(k)$'dir — veri bir akıştan geliyor ve tamamı belleğe sığmıyorsa tek uygulanabilir yol budur. #### Özet - Tam ikili ağaç olan yığın, işaretçisiz biçimde bir dizide tutulur; çocuk ve ebeveyn dizinleri aritmetikle bulunur. - Aşağı süzme $O(\log n)$'dir; yaprak olmayan düğümleri sondan başa süzerek yığın kurmak $O(n)$'dir. - Yığın sıralaması kökü sona taşıyıp sınırı daraltır; her durumda $\Theta(n \log n)$ ve yerinde çalışır. - Kararlı değildir ve belleğe dağınık eriştiği için sabiti hızlı sıralamadan büyüktür. - Karma tasarımlar, hızlı sıralamanın hızını yığın sıralamasının güvencesiyle birleştirir. - $k$ boyutlu yığın, en büyük $k$ elemanı $O(n \log k)$ maliyetle ve $O(k)$ alanla verir. #### Sonraki Adım Üç algoritma da doğrusal-logaritmik sınıra dayandı; bu bir rastlantı değil, karşılaştırmaya dayalı sıralamanın alt sınırıdır. Sonraki ders önce bu alt sınırı kanıtlayacak, sonra sınırın **nasıl aşılabileceğini** gösterecek: elemanları karşılaştırmayan, onları doğrudan konumlarına yerleştiren sıralamalar. ### Karşılaştırmasız Sıralamalar Source: https://academia.sh/tr/kurslar/algoritmalar/karsilastirmasiz-siralamalar Karşılaştırmalı sıralamanın karar ağacı alt sınırı; sayma, kova ve taban sıralamasının varsayımları, maliyetleri ve sınırları. Üç farklı fikir — birleştirme, bölümleme, yığın — aynı sınıra çıktı: $\Theta(n \log n)$. Bu bir rastlantı değildir. Bu ders önce sınırın neden aşılamadığını kanıtlar, sonra kanıtın **varsayımını** kaldırarak sınırın nasıl aşılabildiğini gösterir. #### Alt Sınırın Kanıtı Karşılaştırmalı bir sıralama algoritması, elemanların değerlerine değil yalnızca karşılaştırma sonuçlarına bakar. Böyle bir algoritmanın davranışı bir **karar ağacı** olarak çizilebilir: her iç düğüm bir karşılaştırma, her dal sonuçlardan biri, her yaprak üretilen bir permütasyondur. Algoritma doğruysa, $n$ elemanın **her** olası dizilişini doğru sıralamalıdır; dolayısıyla ağaçta en az $n!$ yaprak bulunur. En kötü durum karşılaştırma sayısı ağacın yüksekliğidir ve yüksekliği $h$ olan ikili ağacın en çok $2^h$ yaprağı vardır: $$ 2^h \geq n! \implies h \geq \log_2(n!) = \Omega(n \log n) $$ Son eşitlik, $n!$ çarpanlarının en az yarısının $n/2$'den büyük olmasından çıkar: $n! \geq (n/2)^{n/2}$, yani $\log_2(n!) \geq \frac{n}{2}\log_2\frac{n}{2}$. ```python import math for n in (10, 100, 1_000, 10_000): print(n, round(math.log2(math.factorial(n))), round(n * math.log2(n))) # 10 22 33 # 100 525 664 # 1000 8529 9966 # 10000 118458 132877 ``` Alt sınır ile üst sınır aynı mertebededir; birleştirmeli sıralama sınırın yalnızca küçük bir çarpanı kadar uzağındadır. Karşılaştırmalı sıralamada yapılacak iyileştirme sabitle sınırlıdır. Kanıtın dayandığı varsayım tektir: **algoritma yalnızca karşılaştırma yapar.** Anahtarların yapısı kullanılırsa kanıt geçersizleşir. #### Sayma Sıralaması Varsayım: anahtarlar, $0$ ile $k-1$ arasında tam sayılardır. Her değerin kaç kez geçtiği sayılır, sayımlar birikimli toplama çevrilir ve elemanlar doğrudan son konumlarına yazılır. ```python def sayma_siralamasi(dizi: list[int], k: int) -> list[int]: """Anahtarlar 0..k-1 aralığında. Maliyet O(n + k), kararlı.""" sayim = [0] * k for deger in dizi: sayim[deger] += 1 for i in range(1, k): # birikimli toplam: bitiş konumları sayim[i] += sayim[i - 1] sonuc = [0] * len(dizi) for deger in reversed(dizi): # sondan başa gitmek kararlılığı korur sayim[deger] -= 1 sonuc[sayim[deger]] = deger return sonuc print(sayma_siralamasi([5, 2, 9, 1, 5, 6], 10)) # [1, 2, 5, 5, 6, 9] print(sayma_siralamasi([3, 0, 3, 0], 4)) # [0, 0, 3, 3] ``` Maliyet $O(n + k)$, ek alan $O(n + k)$'dir. Hiçbir karşılaştırma yapılmaz; her eleman konumunu aritmetikle bulur. Ters yönde dolaşmak bir ayrıntı değildir: kararlılığı sağlayan tam olarak budur. Eşit anahtarlı elemanlardan sonda olan, birikimli sayacın son konumuna yerleşir ve göreli sıra korunur. Sayıların kendisinde bu görünmez; anahtarın bir kaydın parçası olduğu kullanımda belirleyicidir. Yöntemin sınırı $k$'dedir: değer aralığı eleman sayısına göre çok büyükse ($k \gg n$), maliyet ve bellek $k$ tarafından belirlenir. Otuz iki bitlik tam sayıları sayma sıralamasıyla sıralamak dört milyar girdilik bir sayım dizisi ister. #### Kova Sıralaması Varsayım: anahtarlar bilinen bir aralıkta ve **yaklaşık düzgün** dağılmıştır. Aralık eşit parçalara bölünür, her eleman kendi kovasına atılır, kovalar kendi içinde sıralanır ve sırayla birleştirilir. ```python def kova_siralamasi(dizi: list[float], kova_sayisi: int) -> list[float]: """0 <= x < 1 aralığındaki değerler için. Düzgün dağılımda beklenen maliyet O(n).""" if not dizi: return [] kovalar: list[list[float]] = [[] for _ in range(kova_sayisi)] for deger in dizi: kovalar[int(deger * kova_sayisi)].append(deger) sonuc: list[float] = [] for kova in kovalar: kova.sort() # küçük kova: eklemeli sıralama da olur sonuc.extend(kova) return sonuc print(kova_siralamasi([0.42, 0.11, 0.95, 0.47, 0.03], 5)) # [0.03, 0.11, 0.42, 0.47, 0.95] ``` Düzgün dağılımda her kovaya ortalama $n / \text{kova sayısı}$ eleman düşer; kova sayısı $n$ ile orantılı seçilirse kova içi sıralamalar sabit maliyetli olur ve beklenen toplam $O(n)$ çıkar. Varsayım bozulduğunda güvence de bozulur: tüm elemanlar tek kovaya düşerse maliyet, kova içi algoritmanın maliyetine — genellikle $O(n \log n)$ veya $O(n^2)$'ye — geriler. Bu, "doğrusal" iddiasının veriye bağlı olduğu bir örnektir. #### Taban Sıralaması Varsayım: anahtarlar sabit sayıda **basamaktan** oluşur. Elemanlar basamak basamak sıralanır. En az anlamlı basamaktan başlanır ve her basamakta **kararlı** bir sıralama kullanılır; kararlılık, önceki basamaklarda kurulan sıranın korunmasını sağlar. ```python def taban_siralamasi(dizi: list[int], taban: int = 10) -> list[int]: """Negatif olmayan tam sayılar için. Maliyet O(d * (n + taban)).""" if not dizi: return [] sonuc = list(dizi) bolen = 1 while max(sonuc) // bolen > 0: kovalar: list[list[int]] = [[] for _ in range(taban)] for deger in sonuc: kovalar[(deger // bolen) % taban].append(deger) sonuc = [deger for kova in kovalar for deger in kova] bolen *= taban return sonuc print(taban_siralamasi([170, 45, 75, 90, 2, 802, 24, 66])) # [2, 24, 45, 66, 75, 90, 170, 802] print(taban_siralamasi([5, 2, 9, 1, 5, 6])) # [1, 2, 5, 5, 6, 9] ``` Basamak sayısı $d$ ve taban $b$ için maliyet $O(d \cdot (n + b))$'dir. Anahtar genişliği sabitse — sabit genişlikli tam sayılar, sabit uzunlukta metinler — bu ifade $O(n)$'e indirgenir. En anlamlı basamaktan başlayan değişkeler de vardır; metin sıralamasında erken ayrım sağladıkları için tercih edilirler, ancak özyinelemeli bir yapı gerektirirler. #### "Doğrusal" Ne Kadar Doğrusal Üç algoritma da alt sınırı aşar, ama bedelsiz değildir. Dürüst bir değerlendirme üç noktayı kaydeder. **Varsayımlar gerçek kısıtlardır.** Sayma sıralaması küçük tam sayı aralığı, kova sıralaması düzgün dağılım, taban sıralaması sabit genişlikli anahtar ister. Genel amaçlı bir kütüphane sıralaması bu varsayımları yapamaz. **Anahtar genişliği $n$'e bağlıdır.** $n$ farklı anahtar birbirinden ayrılacaksa her anahtar en az $\log_2 n$ bit olmalıdır. Taban sıralamasında basamak sayısı bu yüzden $d = \Theta(\log n)$'dir ve maliyet aslında $\Theta(n \log n)$ bit işlemine karşılık gelir. Alt sınır çiğnenmez; farklı bir işlem birimi sayılmıştır. **Ek alan gerekir.** Üçü de yerinde değildir; sayma ve kova sıralaması $O(n + k)$ alan kullanır. Buna karşın koşullar sağlandığında kazanç gerçektir: milyonlarca kaydı sabit genişlikli bir kimlik alanına göre sıralamak, taban sıralamasıyla karşılaştırmalı bir algoritmadan belirgin biçimde hızlıdır. #### Özet - Karar ağacı akıl yürütmesi, karşılaştırmalı sıralamanın en kötü durumda $\Omega(n \log n)$ karşılaştırma gerektirdiğini gösterir. - Kanıtın tek varsayımı, algoritmanın yalnızca karşılaştırma yapmasıdır; anahtar yapısı kullanılırsa sınır aşılabilir. - Sayma sıralaması küçük tam sayı aralığında $O(n + k)$ ve kararlıdır; ters yönde dolaşmak kararlılığın koşuludur. - Kova sıralaması düzgün dağılımda beklenen $O(n)$ verir; dağılım bozulursa güvence kaybolur. - Taban sıralaması, her basamakta kararlı bir sıralama kullanarak $O(d(n + b))$ çalışır. - Doğrusallık iddiaları varsayıma bağlıdır ve anahtar genişliği $n$'e bağlıysa alt sınır farklı bir birimde yeniden görünür. #### Sonraki Adım Yedi algoritma ve birbirinden farklı ölçütler birikti: en kötü durum, kararlılık, ek alan, uyarlanabilirlik, bellek erişim düzeni ve anahtar yapısı. Sonraki ders bunları tek bir karar tablosunda toplayacak ve "hangi veriye hangi algoritma" sorusunu yanıtlayacak. ### Sıralama Algoritması Seçimi Source: https://academia.sh/tr/kurslar/algoritmalar/siralama-algoritmasi-secimi Veri özelliklerine göre karar tablosu, çok anahtarlı sıralamada kararlılığın kullanımı, karma gerçekleştirimler ve sıralamanın gereksiz olduğu durumlar. Yedi algoritma ve altı ayrı ölçüt birikti. Bu ders onları tek bir karar çerçevesinde toplar. Amaç bir sıralama listesi ezberlemek değil; **eldeki verinin hangi özelliğinin seçimi belirlediğini** görmektir. #### Ölçütlerin Toplu Görünümü | Algoritma | En kötü | Ortalama | Ek alan | Kararlı | Uyarlanabilir | |---|---|---|---|---|---| | Eklemeli | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Evet | Evet | | Seçmeli | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Hayır | Hayır | | Kabarcık | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Evet | Evet | | Birleştirmeli | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Evet | Değişkeye bağlı | | Hızlı | $O(n^2)$ | $O(n \log n)$ | $O(\log n)$ | Hayır | Hayır | | Yığın | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | Hayır | Hayır | | Sayma | $O(n + k)$ | $O(n + k)$ | $O(n + k)$ | Evet | Hayır | | Taban | $O(d(n + b))$ | $O(d(n + b))$ | $O(n + b)$ | Evet | Hayır | Tablo tek başına karar vermez; hangi sütunun önemli olduğunu problem belirler. #### Karar Tablosu | Verinin özelliği | Uygun seçim | Gerekçe | |---|---|---| | Az sayıda eleman (onlarca) | Eklemeli | Küçük sabit, basit kod | | Neredeyse sıralı | Eklemeli veya koşu tabanlı birleştirmeli | Ters çift sayısı küçük | | Kararlılık zorunlu | Birleştirmeli, sayma, taban | Tanım gereği kararlı | | Bellek çok kısıtlı | Yığın | Ek alan $O(1)$, güvence var | | En kötü durum güvencesi gerekli | Yığın veya birleştirmeli | Karesel duruma düşmez | | Genel amaçlı, dizi üzerinde | Karma (hızlı + yığın + eklemeli) | Pratik hız ve güvence | | Bağlı liste | Birleştirmeli | Ardışık erişim yeterli | | Belleğe sığmayan veri | Dış birleştirmeli | Akış hâlinde okuma | | Anahtarlar küçük tam sayı | Sayma | $O(n + k)$, karşılaştırmasız | | Sabit genişlikli anahtar, çok kayıt | Taban | Basamak başına doğrusal | | Çok fazla yinelenen anahtar | Üç yollu hızlı | Eşitler bölgesi tekrar işlenmez | | Yalnızca en büyük $k$ eleman | $k$ boyutlu yığın | $O(n \log k)$, sıralama gerekmez | Satırların çoğu birbirini dışlamaz; birden çok koşul sağlanıyorsa daha kısıtlayıcı olan belirleyicidir. "Kararlılık zorunlu" ile "bellek kısıtlı" çakışırsa, kararlı ve yerinde bir algoritma aranır — bu ikisini birden veren gerçekleştirimler vardır, ancak sabitleri büyüktür. #### Karma Gerçekleştirimler Genel amaçlı kütüphane sıralamaları tek bir algoritma kullanmaz. İki yaygın tasarım vardır ve ikisi de bu bölümün derslerinden derlenmiştir. **Bölümleme temelli karma.** Hızlı sıralamayla başlanır. Özyineleme derinliği $c \log n$ eşiğini aşarsa — yani bölmeler sürekli dengesizse — yığın sıralamasına geçilir. Belirli bir boyutun altındaki parçalar eklemeli sıralamaya bırakılır. Sonuç: hızlı sıralamanın pratik hızı, yığın sıralamasının en kötü durum güvencesi, eklemeli sıralamanın küçük sabiti. **Koşu temelli karma.** Girdide zaten sıralı olan **koşular** bulunur, kısa koşular eklemeli sıralamayla uzatılır, ardından koşular birleştirilir. Neredeyse sıralı veride doğrusala yaklaşır, kararlıdır ve en kötü durumda $O(n \log n)$ kalır. Karşılığında ek alan ister. Ortak ders: gerçek gerçekleştirimler, tek bir algoritmanın en iyisi olduğu iddiasında değildir; her algoritmayı en iyi olduğu bölgede kullanırlar. #### Çok Anahtarlı Sıralama Kararlılığın en yaygın kullanımı, birden çok ölçüte göre sıralamadır. İki yol vardır. **Bileşik anahtar.** Karşılaştırma işlevi, ölçütleri sırayla değerlendirir. Tek geçişte biter ve kararlılık gerektirmez. **Ardışık kararlı sıralamalar.** Önce **ikincil** ölçüte, sonra **birincil** ölçüte göre sıralanır. İkinci sıralama kararlı olduğu için, birincil ölçütte eşit olanların ikincil sırası korunur. ```python kayitlar = [ ("Ankara", 3), ("İzmir", 1), ("Ankara", 1), ("Bursa", 2), ("İzmir", 3), ("Ankara", 2), ] # İkincil ölçüt (sayı) önce, birincil ölçüt (şehir) sonra adim1 = sorted(kayitlar, key=lambda k: k[1]) adim2 = sorted(adim1, key=lambda k: k[0]) print(adim2) # [('Ankara', 1), ('Ankara', 2), ('Ankara', 3), ('Bursa', 2), ('İzmir', 1), ('İzmir', 3)] # Bileşik anahtarla tek geçiş — aynı sonuç print(sorted(kayitlar, key=lambda k: (k[0], k[1])) == adim2) # True ``` İki yol aynı sonucu verir. Ardışık yöntem, ölçütlerin çalışma anında belirlendiği durumlarda (kullanıcının seçtiği sütuna göre sıralanan bir tablo) daha esnektir; bileşik anahtar ise tek geçiş olduğu için ucuzdur. Taban sıralamasının basamak basamak çalışması da aynı ilkedir: her basamak bir ölçüttür ve kararlılık, önceki ölçütlerin sonucunu korur. #### Karşılaştırma Maliyeti Asimptotik tablolar karşılaştırmayı sabit sayar. Anahtar karmaşıksa bu varsayım bozulur: uzun metinlerin karşılaştırılması metin uzunluğuyla orantılıdır ve dile duyarlı sıralama kuralları çok daha pahalıdır. İki sonuç doğar. Birincisi, karşılaştırma pahalıysa **karşılaştırma sayısını** azaltan algoritma (birleştirmeli) tercih edilir; taşıma pahalıysa taşımayı azaltan (seçmeli). İkincisi, pahalı anahtar dönüşümü sıralamadan **önce bir kez** yapılıp saklanabilir — sıralama boyunca her karşılaştırmada yeniden hesaplanmaz. Bu, Zaman ve Alan Ödünleşimi dersindeki önhesaplama kalıbının doğrudan uygulanışıdır. #### Sıralamanın Gereksiz Olduğu Durumlar Sıralama, ihtiyaç duyulandan fazlasını yapan bir işlemdir ve sık sık gereksiz yere çağrılır. | İhtiyaç | Sıralama yerine | Maliyet | |---|---|---| | En büyük veya en küçük eleman | Tek geçişte tarama | $O(n)$ | | k'ıncı en küçük eleman | Hızlı seçme | Beklenen $O(n)$ | | En büyük $k$ eleman | $k$ boyutlu yığın | $O(n \log k)$ | | Bir değerin varlığı | Karma tablosu | Beklenen $O(1)$ | | Yinelenenleri ayıklamak | Karma kümesi | Beklenen $O(n)$ | | Ortanca değeri | Seçme algoritması | Beklenen $O(n)$ | Sıralamanın kendisi gerekliyse — çıktının sıralı sunulması, ikili aramaya hazırlık, çok sorgulu kullanım — maliyeti yerindedir. Tek bir soruya yanıt için sıralamak, $O(n \log n)$ ödeyip $O(n)$'lik bir iş yapmaktır. #### Ölçmeden Karar Verilmeyen Nokta Asimptotik çözümleme sınıfı belirler; sınıf içi seçim ölçüm ister. İki algoritma da $O(n \log n)$ ise fark sabittedir ve sabit; bellek erişim düzenine, anahtar tipine, veri büyüklüğüne ve gerçekleştirime bağlıdır. Ölçüm yapılırken üç kural geçerlidir: **gerçek veriyle** ölçülmeli (rastgele veri, gerçek verinin kısmi sıralılığını taşımaz), **girdi büyüklüğü değiştirilerek** ölçülmeli (tek boyutta ölçüm sınıfı göstermez) ve ölçülen sürelerin girdiyle nasıl ölçeklendiğine bakılmalıdır — Karmaşıklık Sınıflarını Okumak dersindeki ölçek büyütme tablosu bu iş içindir. #### Özet - Seçim, algoritmanın kendisinden değil verinin özelliklerinden çıkar: boyut, kısmi sıralılık, yinelenen anahtar oranı, anahtar yapısı, bellek kısıdı ve kararlılık gereksinimi. - Genel amaçlı gerçekleştirimler karmadır; her algoritmayı en iyi olduğu bölgede kullanır. - Çok anahtarlı sıralama, ardışık kararlı sıralamalarla veya bileşik anahtarla yapılır. - Karşılaştırma pahalıysa karşılaştırma sayısını, taşıma pahalıysa taşıma sayısını azaltan algoritma seçilir. - En küçük, k'ıncı, ilk $k$ veya varlık sorularında sıralama gereksizdir; doğrusal veya beklenen sabit maliyetli çözümler vardır. - Sınıf içi karar ölçümle verilir; ölçüm gerçek veriyle ve birden çok girdi boyutunda yapılır. #### Sonraki Adım Arama ve sıralama, tek boyutlu veriler üzerinde çalıştı: elemanlar arasında yalnızca sıra ilişkisi vardı. Sonraki konu, elemanlar arasında **bağlantı** olan verilere geçer. Veri Yapıları kursunda çizgeler tanımlanmış, enine ve derine arama kurulmuştu; şimdi ağırlıklı çizgelerde en kısa yol, en ucuz kapsayan ağaç ve en büyük akış problemleri ele alınacak. ## Çizge Algoritmaları En kısa yol algoritmaları, sezgisel arama, minimum kapsayan ağaç ve ağ akışı. ### Dijkstra Algoritması Source: https://academia.sh/tr/kurslar/algoritmalar/dijkstra-algoritmasi Ağırlıklı çizgede tek kaynaktan en kısa yol, gevşetme işlemi, açgözlü seçimin gerekçesi, öncelik kuyruğuyla gerçekleştirim ve negatif ağırlık kısıtı. Veri Yapıları kursunda çizgeler tanımlanmış, enine ve derine arama kurulmuştu. Enine arama, **kenar sayısı** cinsinden en kısa yolu buluyordu: her kenarın maliyeti eşit sayılıyordu. Gerçek problemlerde kenarların maliyeti farklıdır — mesafe, süre, ücret. Bu konu ağırlıklı çizgelerde çalışan algoritmaları kurar ve ilk sorusu en kısa yoldur. #### Problem ve Gösterim **Tek kaynaktan en kısa yol problemi:** Ağırlıklı bir çizge ve bir kaynak düğüm verilir; kaynaktan diğer tüm düğümlere giden en düşük toplam ağırlıklı yollar istenir. Bu konu boyunca aynı çizge kullanılır: düğümler `A`–`F`, kenarlar yönlü ve ağırlıklı. ```python cizge: dict[str, list[tuple[str, int]]] = { "A": [("B", 4), ("C", 2)], "B": [("C", 5), ("D", 10)], "C": [("E", 3)], "D": [("F", 11)], "E": [("D", 4)], "F": [], } ``` Komşuluk listesi gösterimi, seyrek çizgelerde uygundur ve tüm kenarları gezmek $O(V + E)$'dir. Yoğun çizgelerde komşuluk matrisi tercih edilir; seçimin maliyet üzerindeki etkisi Veri Yapıları kursunda ele alınmıştı. #### Gevşetme Algoritmaların ortak yapı taşı **gevşetmedir (relaxation)**: bilinen bir tahmini, bulunan daha iyi bir yolla düşürmek. Her düğüm için kaynaktan gelen en iyi bilinen uzaklık `u[v]` tutulur; başlangıçta kaynak için $0$, diğerleri için sonsuzdur. `(v, w)` kenarı için: $$ u[w] > u[v] + \text{ağırlık}(v, w) \implies u[w] \leftarrow u[v] + \text{ağırlık}(v, w) $$ Gevşetme hiçbir zaman yanlış bir değer üretmez: `u[w]` her zaman **gerçekten var olan bir yolun** uzunluğudur. Algoritmalar, bu değerlerin ne zaman kesinleştiğine dair verdikleri güvenceyle ayrılır. #### Açgözlü Seçim Dijkstra algoritmasının fikri şudur: **henüz kesinleşmemiş düğümler arasında en küçük tahmini olan düğüm, artık kesinleşmiştir.** Gerekçe, ağırlıkların negatif olmamasına dayanır. Kaynaktan `v`'ye giden herhangi bir başka yol, kesinleşmemiş bir düğümden geçmek zorundadır; o düğümün tahmini `u[v]`'den küçük olmadığına ve kalan kenarlar maliyeti azaltamayacağına göre, alternatif yol daha kısa olamaz. Bu akıl yürütme, algoritmanın değişmezini verir: **kesinleşmiş düğümlerin uzaklıkları gerçek en kısa yol uzunluklarıdır.** #### Gerçekleştirim ```python import heapq def dijkstra(cizge: dict[str, list[tuple[str, int]]], kaynak: str) -> tuple[dict[str, float], dict[str, str | None]]: """(uzaklıklar, önceki düğümler) döndürür. Ağırlıklar negatif olmamalıdır.""" uzaklik: dict[str, float] = {d: float("inf") for d in cizge} onceki: dict[str, str | None] = {d: None for d in cizge} uzaklik[kaynak] = 0 kuyruk: list[tuple[float, str]] = [(0, kaynak)] kesinlesen: set[str] = set() while kuyruk: d, v = heapq.heappop(kuyruk) if v in kesinlesen: # eskimiş kayıt: atla continue kesinlesen.add(v) for komsu, agirlik in cizge[v]: if d + agirlik < uzaklik[komsu]: uzaklik[komsu] = d + agirlik onceki[komsu] = v heapq.heappush(kuyruk, (uzaklik[komsu], komsu)) return uzaklik, onceki uzaklik, onceki = dijkstra(cizge, "A") print(uzaklik) # {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20} ``` `A`'dan `D`'ye doğrudan giden yol `A→B→D` ile 14 uzunluğundadır; algoritma `A→C→E→D` yolunu 9 ile bulur. Açgözlü seçim, daha uzun görünen bir başlangıcın toplamda daha kısa olmasını engellemez — çünkü seçim kenarlara değil, birikmiş uzaklıklara bakar. #### Yolu Geri Kurmak Uzaklık tek başına yetmez; hangi yoldan gidildiği de gerekir. `onceki` sözlüğü bu bilgiyi taşır: her düğüm, kendisine en kısa yolla gelinen düğümü işaret eder. ```python def yolu_kur(onceki: dict[str, str | None], hedef: str) -> list[str]: yol: list[str] = [] dugum: str | None = hedef while dugum is not None: yol.append(dugum) dugum = onceki[dugum] return yol[::-1] print(yolu_kur(onceki, "F")) # ['A', 'C', 'E', 'D', 'F'] print(yolu_kur(onceki, "B")) # ['A', 'B'] ``` Bu işaretçiler bir **en kısa yol ağacı** oluşturur: kaynaktan tüm düğümlere giden en kısa yolları birlikte kodlayan, kök kaynağa oturan bir ağaç. #### Maliyet Her düğüm en çok bir kez kesinleşir; her kenar en çok bir gevşetme ve bir kuyruk ekleme üretir. İkili yığınla: $$ O\big((V + E)\log V\big) $$ Kuyrukta aynı düğümün birden çok kaydı bulunabilir — buradaki gerçekleştirim eskimiş kayıtları çıkarırken atlar. Bu **tembel silme**, azaltma işlemi olan bir öncelik kuyruğu gerektirmeden aynı asimptotik sınırı verir ve kodu belirgin biçimde kısaltır. Yoğun çizgelerde ($E \approx V^2$) kuyruk yerine dizi taraması kullanan değişke $O(V^2)$'dir ve daha hızlı olabilir. Fibonacci yığını kullanan kuramsal değişke $O(E + V \log V)$ verir; sabitleri büyük olduğu için pratikte seyrek görülür. #### Sık Kullanılan Değişkeler Temel yapı küçük değişikliklerle farklı sorulara uyarlanır. **Tek hedef için erken çıkış.** Yalnızca belirli bir düğüme uzaklık gerekiyorsa, o düğüm kuyruktan çıkarıldığı anda durulabilir; değeri o noktada kesinleşmiştir. Kalan düğümler hiç işlenmez. **Çok kaynaklı arama.** "Herhangi bir depoya en yakın uzaklık" gibi sorularda, tüm kaynaklar başlangıçta sıfır uzaklıkla kuyruğa konur. Bu, tek bir yapay kaynağın tüm depolara sıfır ağırlıklı kenar çektiği çizgeye denktir; Veri Yapıları kursundaki çok kaynaklı enine aramanın ağırlıklı karşılığıdır. **Ulaşılamayan düğümler.** Kaynaktan erişilemeyen düğümlerin uzaklığı sonsuz kalır. Sonucu kullanan kodun bu değeri sınaması gerekir; sonsuzu sayısal bir uzaklık gibi işleme sokmak sessiz hatalara yol açar. **Ağırlıkların yalnızca 0 ve 1 olması.** Bu durumda öncelik kuyruğu yerine çift uçlu kuyruk yeter: sıfır ağırlıklı kenar başa, bir ağırlıklı kenar sona eklenir. Maliyet $O(V + E)$'ye iner — logaritmik çarpan, ağırlık çeşitliliğinin bedelidir. #### Negatif Ağırlık Kısıtı Algoritmanın doğruluğu, "kesinleşen düğümün değeri bir daha düşemez" varsayımına dayanıyordu. Negatif ağırlıklı bir kenar bu varsayımı bozar. ```python negatifli = { "A": [("B", 1), ("C", 2)], "B": [("D", 1)], "C": [("B", -2)], "D": [], } print(dijkstra(negatifli, "A")[0]) # {'A': 0, 'B': 0, 'C': 2, 'D': 2} — D yanlış: gerçek uzaklık 1 ``` `B` düğümü, ağırlığı 1 olan doğrudan kenarla kesinleştirilir ve `D` bu değer üzerinden 2 olarak gevşetilir. Sonra `C` işlenir ve `A→C→B` yolunun $2 + (-2) = 0$ olduğu ortaya çıkar; `B`'nin değeri düzelir ama `B` kesinleşmiş sayıldığı için çıkan kenarları bir daha gevşetilmez. `D` eski değerinde kalır. Algoritma hata vermez; **sessizce yanlış sonuç üretir.** Bu, ön koşulları belgelemenin neden bir biçimsellik olmadığını gösteren örneklerden biridir. Negatif ağırlıklarla çalışan algoritma sonraki dersin konusudur. #### Özet - Tek kaynaktan en kısa yol problemi, ağırlıklı çizgede kaynaktan tüm düğümlere en düşük toplam maliyetli yolları ister. - Gevşetme, bir düğümün tahmini uzaklığını bulunan daha iyi bir yolla düşürür ve her tahmin gerçek bir yola karşılık gelir. - Dijkstra, kesinleşmemiş düğümler arasında en küçük tahminliyi seçer; doğruluğu ağırlıkların negatif olmamasına dayanır. - Öncelik kuyruklu gerçekleştirim $O((V + E)\log V)$'dir; tembel silme, azaltma işlemi gerektirmez. - Önceki düğüm işaretçileri en kısa yol ağacını kodlar ve yolun geri kurulmasını sağlar. - Negatif ağırlıkta algoritma hata vermeden yanlış sonuç üretir. #### Sonraki Adım Negatif ağırlıklar gerçek problemlerde ortaya çıkar: para birimi çevrimlerinde kazanç, üretim planında geri kazanım. Sonraki ders, açgözlü seçimden vazgeçip tüm kenarları tekrar tekrar gevşeten Bellman–Ford algoritmasını kuracak ve negatif döngülerin neden problemi tanımsız kıldığını gösterecek. ### Bellman–Ford Algoritması Source: https://academia.sh/tr/kurslar/algoritmalar/bellman-ford-algoritmasi Tüm kenarları yineleyerek gevşetme, kenar sayısına göre tümevarım, negatif döngü tespiti, yönlü çevrimsiz çizgede doğrusal çözüm. Dijkstra, bir düğümü kesinleştirdikten sonra bir daha ona dönmüyordu; bu, ağırlıkların negatif olmamasına dayanan bir kazançtı. Negatif ağırlık varsa, bir düğümün değeri sonradan düşebilir ve tek geçiş yetmez. Bellman–Ford bu varsayımdan vazgeçer: hiçbir düğümü kesinleştirmez, **tüm kenarları tekrar tekrar** gevşetir. #### Algoritma Kaynak dışındaki tüm uzaklıklar sonsuzdur. Ardından tüm kenarlar üzerinden $V-1$ geçiş yapılır; her geçişte her kenar bir kez gevşetilir. ```python def bellman_ford(cizge: dict[str, list[tuple[str, int]]], kaynak: str) -> tuple[dict[str, float], bool]: """(uzaklıklar, negatif döngü var mı) döndürür.""" uzaklik: dict[str, float] = {d: float("inf") for d in cizge} uzaklik[kaynak] = 0 kenarlar = [(v, w, a) for v in cizge for w, a in cizge[v]] for _ in range(len(cizge) - 1): degisim = False for v, w, agirlik in kenarlar: if uzaklik[v] + agirlik < uzaklik[w]: uzaklik[w] = uzaklik[v] + agirlik degisim = True if not degisim: # erken çıkış: hiçbir şey iyileşmedi break for v, w, agirlik in kenarlar: # bir geçiş daha hâlâ iyileştiriyorsa if uzaklik[v] + agirlik < uzaklik[w]: return uzaklik, True return uzaklik, False negatifli = { "A": [("B", 1), ("C", 2)], "B": [("D", 1)], "C": [("B", -2)], "D": [], } print(bellman_ford(negatifli, "A")) # ({'A': 0, 'B': 0, 'C': 2, 'D': 1}, False) ``` Önceki dersin Dijkstra ile yanlış hesapladığı `D` uzaklığı burada doğru çıkar: 1. Fark, `B`'nin değeri düştükten sonra çıkan kenarlarının yeniden gevşetilmesidir. Aynı algoritma negatif ağırlık olmayan çizgelerde de doğrudur; Dijkstra'nın üstünlüğü doğrulukta değil hızdadır. #### Neden $V-1$ Geçiş Gerekçe, yolun kenar sayısı üzerinden tümevarımdır. **İddia:** $k$'ıncı geçişten sonra, en çok $k$ kenar kullanan tüm en kısa yollar doğru hesaplanmıştır. Taban durumu $k = 0$'dır: kaynağın uzaklığı sıfırdır. Adım için, en çok $k+1$ kenarlık bir en kısa yolun son kenarı $(v, w)$ olsun. Yolun `v`'ye kadarki bölümü en çok $k$ kenar kullanır ve tümevarım varsayımıyla $k$'ıncı geçişten sonra doğrudur; $k+1$'inci geçişte bu kenar gevşetildiğinde `w` de doğru değerini alır. Negatif döngü yoksa hiçbir en kısa yol bir düğümü iki kez ziyaret etmez; dolayısıyla en çok $V-1$ kenar içerir. Bu yüzden $V-1$ geçiş yeterlidir. Erken çıkış, pratikte geçiş sayısını belirgin biçimde azaltır: bir geçişte hiçbir değer iyileşmediyse sonraki geçişler de iyileştirmez. #### Negatif Döngü $V-1$ geçişten sonra hâlâ gevşeyen bir kenar varsa, kaynaktan ulaşılabilen bir **negatif döngü** vardır. ```python donguluu = { "A": [("B", 1)], "B": [("C", -3)], "C": [("B", 1)], # B → C → B döngüsü: -3 + 1 = -2 } print(bellman_ford(donguluu, "A")[1]) # True ``` Böyle bir döngüde problem **tanımsızdır**: döngü her dolaşıldığında toplam maliyet düşer, dolayısıyla "en kısa yol" diye bir şey yoktur. Tespit, hesaplanan değerleri kurtarmak için değil, sorunun kendisini bildirmek için yapılır. Tespit yeteneği bir yan ürün değil, algoritmanın başlıca kullanım nedenlerinden biridir. Klasik uygulama, çevrim kazançlarının tespitidir: kur oranlarının çarpımsal kazancı $-\log$ dönüşümüyle toplamsal maliyete çevrilirse, kazançlı bir çevrim negatif döngü hâline gelir ve algoritma onu bulur. #### Etkilenen Düğümleri İşaretlemek Negatif döngünün varlığını bilmek çoğu zaman yetmez; **hangi düğümlerin** bundan etkilendiği sorulur. Döngüden ulaşılabilen her düğümün uzaklığı istenildiği kadar küçültülebilir, yani eksi sonsuzdur; geri kalan düğümlerin değerleri ise geçerlidir. Ayrım, $V-1$ geçiş daha yaparak ve gevşeyen kenarların hedeflerini eksi sonsuz olarak işaretleyerek yapılır. ```python def bellman_ford_isaretli(cizge: dict[str, list[tuple[str, int]]], kaynak: str) -> dict[str, float]: uzaklik: dict[str, float] = {d: float("inf") for d in cizge} uzaklik[kaynak] = 0 kenarlar = [(v, w, a) for v in cizge for w, a in cizge[v]] for _ in range(len(cizge) - 1): for v, w, agirlik in kenarlar: if uzaklik[v] + agirlik < uzaklik[w]: uzaklik[w] = uzaklik[v] + agirlik for _ in range(len(cizge) - 1): # eksi sonsuzu yay for v, w, agirlik in kenarlar: if uzaklik[v] != float("inf") and ( uzaklik[v] + agirlik < uzaklik[w] or uzaklik[v] == float("-inf") ): uzaklik[w] = float("-inf") return uzaklik donguluu_genis = { "A": [("B", 1)], "B": [("C", -3)], "C": [("B", 1), ("D", 2)], "D": [], "E": [("A", 1)], # kaynaktan ulaşılamaz } print(bellman_ford_isaretli(donguluu_genis, "A")) # {'A': 0, 'B': -inf, 'C': -inf, 'D': -inf, 'E': inf} ``` Üç ayrı durum aynı sözlükte görünür: geçerli uzaklık (`A`), negatif döngüden etkilenen düğümler (`B`, `C`, `D`) ve ulaşılamayan düğüm (`E`). Bir sonucu kullanan kodun üç durumu da ayırt etmesi gerekir. #### Maliyet Her geçişte tüm kenarlar işlenir ve en çok $V-1$ geçiş yapılır: $$ O(V \cdot E) $$ Dijkstra'nın $O((V+E)\log V)$ maliyetiyle karşılaştırıldığında belirgin biçimde pahalıdır. Alan maliyeti $O(V)$'dir. | Ölçüt | Dijkstra | Bellman–Ford | |---|---|---| | Negatif ağırlık | Kabul etmez | Kabul eder | | Negatif döngü | Tespit etmez | Tespit eder | | Maliyet | $O((V+E)\log V)$ | $O(V \cdot E)$ | | Yaklaşım | Açgözlü | Yinelemeli gevşetme | Seçim ölçütü nettir: ağırlıklar negatif olamıyorsa Dijkstra, olabiliyorsa Bellman–Ford. Tüm düğüm çiftleri arasındaki uzaklıklar isteniyorsa, her düğümden ayrı çalıştırmak yerine tüm çiftler için tasarlanmış algoritmalar kullanılır; bunlar İleri Algoritmalar kursunun konusudur. #### Çevrimsiz Çizgede Daha Ucuz Yol Çizge **yönlü ve çevrimsizse (DAG)**, döngü olmadığı için gevşetme sırası bir kez doğru seçilirse tek geçiş yeter. Doğru sıra, Veri Yapıları kursundaki topolojik sıralamadır: bir düğüm işlendiğinde, ona gelen tüm kenarlar zaten gevşetilmiştir. ```python def dag_en_kisa_yol(cizge: dict[str, list[tuple[str, int]]], sira: list[str], kaynak: str) -> dict[str, float]: """sira: topolojik sıralama. Maliyet O(V + E).""" uzaklik: dict[str, float] = {d: float("inf") for d in cizge} uzaklik[kaynak] = 0 for v in sira: if uzaklik[v] == float("inf"): continue for w, agirlik in cizge[v]: if uzaklik[v] + agirlik < uzaklik[w]: uzaklik[w] = uzaklik[v] + agirlik return uzaklik cizge = { "A": [("B", 4), ("C", 2)], "B": [("C", 5), ("D", 10)], "C": [("E", 3)], "D": [("F", 11)], "E": [("D", 4)], "F": [], } print(dag_en_kisa_yol(cizge, ["A", "B", "C", "E", "D", "F"], "A")) # {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 5, 'F': 20} ``` Sonuç, Dijkstra'nın aynı çizgede bulduğuyla aynıdır; maliyet ise $O(V + E)$'ye düşer. Üstelik bu yöntem **negatif ağırlıkları da** kabul eder, çünkü açgözlü bir seçim yapmaz. Aynı yapı, en **uzun** yolu bulmak için de kullanılır: karşılaştırma yönü ters çevrilir. Genel çizgelerde en uzun yol problemi zor bir problemdir; çevrimsizlik onu doğrusal hâle getirir. Proje planlamasındaki kritik yol hesabı bu türdendir. #### Özet - Bellman–Ford hiçbir düğümü kesinleştirmez; tüm kenarları $V-1$ geçiş boyunca gevşetir. - $k$'ıncı geçişten sonra en çok $k$ kenarlık tüm en kısa yollar doğrudur; negatif döngü yoksa en kısa yol en çok $V-1$ kenar içerir. - $V$'inci geçişte hâlâ gevşeyen bir kenar, kaynaktan ulaşılabilen negatif döngü demektir ve problem tanımsızdır. - Maliyet $O(V \cdot E)$'dir; erken çıkış pratikte geçiş sayısını azaltır. - Ağırlıklar negatif olamıyorsa Dijkstra, olabiliyorsa Bellman–Ford seçilir. - Çevrimsiz çizgelerde topolojik sırayla tek geçiş yeterlidir ve maliyet $O(V + E)$'dir. #### Sonraki Adım İki algoritma da hedefi olmayan aramalar yaptı: kaynaktan **tüm** düğümlere uzaklık hesaplandı. Belirli bir hedefe gidiliyorsa bu israftır. Sonraki ders, hedefin yönünü bilen bir tahmin işleviyle aramayı daraltan A* algoritmasını ve tahminin hangi koşulda doğruluğu bozmadığını ele alacak. ### A* Arama Source: https://academia.sh/tr/kurslar/algoritmalar/a-yildiz-arama Sezgisel fonksiyonla hedefe yönelmiş arama, kabul edilebilirlik ve tutarlılık koşulları, Dijkstra ile ilişkisi ve genişletilen düğüm sayısındaki kazanç. Önceki iki algoritma kaynaktan **tüm** düğümlere uzaklık hesaplıyordu. Belirli bir hedefe gidiliyorsa bu israftır: hedefin tersi yöndeki düğümler de aynı özenle işlenir. A*, hedefin nerede olduğuna dair bir tahmini aramaya katarak bu israfı azaltır. #### Değerlendirme İşlevi Her düğüm için iki büyüklük tutulur: - $g(v)$ — kaynaktan `v`'ye bilinen en iyi maliyet (Dijkstra'daki uzaklık). - $h(v)$ — `v`'den hedefe **tahmini** kalan maliyet; problem bilgisinden gelir. Arama, ikisinin toplamına göre yapılır: $$ f(v) = g(v) + h(v) $$ $f(v)$, `v` üzerinden geçen bir çözümün tahmini toplam maliyetidir. Öncelik kuyruğu uzaklığa değil bu değere göre sıralanır; gerisi Dijkstra ile aynıdır. ```python import heapq def a_yildiz(cizge: dict[str, list[tuple[str, int]]], baslangic: str, hedef: str, h: dict[str, int]) -> float | None: g: dict[str, float] = {baslangic: 0} acik: list[tuple[float, float, str]] = [(h[baslangic], 0, baslangic)] kapali: set[str] = set() while acik: _, maliyet, dugum = heapq.heappop(acik) if dugum in kapali: continue kapali.add(dugum) if dugum == hedef: return maliyet for komsu, agirlik in cizge[dugum]: yeni = maliyet + agirlik if yeni < g.get(komsu, float("inf")): g[komsu] = yeni heapq.heappush(acik, (yeni + h[komsu], yeni, komsu)) return None ``` $h(v) = 0$ alınırsa $f = g$ olur ve algoritma tam olarak Dijkstra'ya dönüşür. A*, bu anlamda Dijkstra'nın genellemesidir: sezgi, aramaya eklenen ek bilgidir. #### Kabul Edilebilirlik Sezgi keyfî olamaz. **Kabul edilebilir (admissible)** olması, hiçbir düğümde gerçek kalan maliyeti **aşmaması** demektir: $$ h(v) \leq h^*(v) $$ Burada $h^*(v)$ gerçek kalan maliyettir. Kabul edilebilir sezgiyle A*, bulduğu ilk çözümün eniyi olduğunu garanti eder — kapatılan düğümlerin $g$ değeri kesinleşmiş olduğu sürece. Bu koşulun ne zaman sağlandığı aşağıdaki tutarlılık bölümünün konusudur. Gerekçe: hedef kuyruğun başına geldiğinde $f(\text{hedef}) = g(\text{hedef})$'tir. Daha iyi bir çözüm olsaydı, o çözümün yolundaki bir düğüm kuyrukta bulunur ve $f$ değeri — tahminler aşmadığı için — gerçek toplam maliyetten küçük olurdu; dolayısıyla hedeften önce çıkarılırdı. Koşul ihlal edilirse eniyilik kaybolur. ```python cizge = { "A": [("B", 1), ("C", 5)], "B": [("H", 10)], "C": [("H", 1)], "H": [], } asiri = {"A": 0, "B": 1, "C": 10, "H": 0} # C'nin tahmini gerçeğin (1) çok üstünde kabul_edilebilir = {"A": 6, "B": 10, "C": 1, "H": 0} print(a_yildiz(cizge, "A", "H", asiri)) # 11 — eniyi değil print(a_yildiz(cizge, "A", "H", kabul_edilebilir)) # 6 print(a_yildiz(cizge, "A", "H", {d: 0 for d in cizge})) # 6 — Dijkstra ``` Aşırı tahmin, `C` üzerinden geçen gerçek en kısa yolu (`A→C→H`, 6) elemeye yol açar; algoritma `A→B→H` yolunu (11) döndürür. #### Tutarlılık Daha güçlü bir koşul, **tutarlılıktır (consistency)**: her `(v, w)` kenarı için $$ h(v) \leq \text{ağırlık}(v, w) + h(w) $$ Bu, üçgen eşitsizliğinin sezgi üzerindeki karşılığıdır. Tutarlı bir sezgi kabul edilebilirdir ve ek olarak şunu sağlar: bir düğüm kapatıldığında $g$ değeri kesinleşmiştir, yani hiçbir düğüm iki kez genişletilmez. Tutarlı olmayan ama kabul edilebilir bir sezgide kapatılan düğümün $g$ değeri kesinleşmiş olmayabilir. Eniyilik ancak kapatılmış bir düğüm daha ucuz bir yoldan bulunduğunda **yeniden açılırsa** korunur; yukarıdaki gerçekleştirim kapalı düğümü koşulsuz atladığı için böyle bir sezgide eniyi olmayan bir yol döndürebilir. Pratikte kullanılan sezgilerin çoğu — düzlemde kuş uçuşu uzaklık, ızgarada Manhattan uzaklığı — tutarlıdır ve bu yüzden sorun doğmaz. #### Ölçülen Kazanç Kazanç, **genişletilen düğüm sayısında** görünür. Aşağıdaki ızgarada her adım bir birim maliyetlidir; komşuluk dört yöndedir. ```python def izgara_ara(izgara: list[str], baslangic: tuple[int, int], hedef: tuple[int, int], sezgi) -> tuple[int, int]: """(yol maliyeti, genişletilen düğüm sayısı)""" g = {baslangic: 0} acik = [(sezgi(baslangic, hedef), 0, baslangic)] kapali: set[tuple[int, int]] = set() sayac = 0 while acik: _, maliyet, dugum = heapq.heappop(acik) if dugum in kapali: continue kapali.add(dugum) sayac += 1 if dugum == hedef: return maliyet, sayac s, t = dugum for ds, dt in ((-1, 0), (0, -1), (0, 1), (1, 0)): y, x = s + ds, t + dt if 0 <= y < len(izgara) and 0 <= x < len(izgara[0]) and izgara[y][x] != "#": yeni = maliyet + 1 if yeni < g.get((y, x), float("inf")): g[(y, x)] = yeni heapq.heappush(acik, (yeni + sezgi((y, x), hedef), yeni, (y, x))) return -1, sayac sifir = lambda a, b: 0 manhattan = lambda a, b: abs(a[0] - b[0]) + abs(a[1] - b[1]) acik_izgara = ["." * 15 for _ in range(15)] duvarli = ["".join("#" if (2 <= y <= 12 and x == 7) else "." for x in range(15)) for y in range(15)] print(izgara_ara(acik_izgara, (7, 1), (7, 13), sifir)) # (12, 147) print(izgara_ara(acik_izgara, (7, 1), (7, 13), manhattan)) # (12, 13) print(izgara_ara(duvarli, (7, 1), (7, 13), sifir)) # (24, 212) print(izgara_ara(duvarli, (7, 1), (7, 13), manhattan)) # (24, 169) ``` Engelsiz ızgarada A*, hedefe giden şeridi izler ve 147 yerine 13 düğüm genişletir. Yol maliyeti aynıdır — kazanç doğrulukta değil, harcanan işte. Duvarlı ızgarada kazanç erir: Manhattan uzaklığı duvarı görmediğinden tahmin gerçeğin çok altında kalır ve sezgi arama yönünü yeterince daraltmaz. **Sezginin kalitesi, gerçeğe ne kadar yaklaştığıyla ölçülür**; $h = 0$ ile $h = h^*$ arasındaki her nokta, Dijkstra ile doğrudan hedefe yürüme arasında bir yerdedir. #### Ödünleşimler **Bellek.** A*, açık kümedeki tüm düğümleri saklar; büyük arama uzaylarında bellek, zaman kadar kısıtlayıcıdır. Derinliği artırarak yineleyen değişkeler ($O(b\,d)$ bellek) bu sorunu maliyet karşılığında çözer. **Kasıtlı aşırı tahmin.** Sezgiyi bir çarpanla büyütmek aramayı daraltır ama eniyiliği bozar; bulunan çözümün çarpan kadar kötü olabileceği bilinerek kullanılır. Yanıtın hızlı olması eniyi olmasından değerliyse makul bir değiş tokuştur. **Sezginin maliyeti.** $h$ her düğüm için hesaplanır; pahalı bir sezgi, kazandırdığı genişletmeden fazlasını götürebilir. Bu ödünleşimler, aramanın yapay zekâ tarafındaki uzantısıdır ve oyun ağaçlarıyla birlikte yapay zekâ müfredatının konusudur; burada ele alınmaz. #### Özet - A*, düğümleri $f(v) = g(v) + h(v)$ değerine göre genişletir; $h = 0$ alındığında Dijkstra'ya indirgenir. - Kabul edilebilir sezgi gerçek kalan maliyeti aşmaz ve bulunan çözümün eniyi olmasını garanti eder. - Tutarlı sezgi üçgen eşitsizliğini sağlar; hiçbir düğüm iki kez genişletilmez. - Kazanç genişletilen düğüm sayısında ortaya çıkar ve sezginin gerçeğe yakınlığıyla orantılıdır. - Engeller tahmini gerçekten uzaklaştırır ve kazancı azaltır. - Bellek kullanımı, kasıtlı aşırı tahmin ve sezginin hesaplama maliyeti başlıca ödünleşimlerdir. #### Sonraki Adım Buraya kadar sorulan soru "iki düğüm arasındaki en ucuz yol neydi" oldu. Sonraki ders soruyu değiştirir: tüm düğümleri birbirine bağlayan en ucuz kenar kümesi hangisidir? Minimum kapsayan ağaç problemi, açgözlü seçimin doğruluğunu farklı bir gerekçeyle — kesme özelliğiyle — kuracak. ### Minimum Kapsayan Ağaç Source: https://academia.sh/tr/kurslar/algoritmalar/minimum-kapsayan-agac Kesme özelliği, Prim ve Kruskal algoritmaları, birleşim-bulma yapısı, iki yaklaşımın karşılaştırması ve kümeleme uygulaması. Buraya kadarki sorular iki düğüm arasındaki yolla ilgiliydi. Bu ders soruyu değiştirir: **tüm düğümleri birbirine bağlayan en ucuz kenar kümesi hangisidir?** Soru, ağ tasarımının temel biçimidir: her noktayı bağlamak zorunludur, toplam kablo, boru veya hat maliyeti en aza indirilmelidir. #### Problem Ağırlıklı, yönsüz ve bağlı bir çizgede **kapsayan ağaç**, tüm düğümleri içeren ve çevrim barındırmayan bir alt çizgedir. Böyle bir alt çizgede tam olarak $V-1$ kenar bulunur. **Minimum kapsayan ağaç (MST)**, kenar ağırlıkları toplamı en küçük olan kapsayan ağaçtır. Ağırlıklar birbirinden farklıysa MST tektir; eşit ağırlıklar varsa birden çok MST olabilir ve hepsinin toplam ağırlığı aynıdır. Bu ders boyunca kullanılan çizge yönsüzdür: ```python kenarlar: list[tuple[int, str, str]] = [ (4, "A", "B"), (2, "A", "C"), (5, "B", "C"), (10, "B", "D"), (3, "C", "E"), (4, "E", "D"), (11, "D", "F"), ] dugumler = ["A", "B", "C", "D", "E", "F"] ``` #### Kesme Özelliği Her iki algoritma da açgözlüdür ve doğrulukları tek bir gözleme dayanır. **Kesme (cut)**, düğümlerin boş olmayan iki parçaya ayrılmasıdır. Bir kenar, uçları farklı parçalardaysa kesmeyi **geçer**. **Kesme özelliği:** Herhangi bir kesmeyi geçen en hafif kenar, bir minimum kapsayan ağaçta bulunur. Gerekçe bir **değiş tokuş** akıl yürütmesidir. En hafif geçen kenar $e$ olsun ve onu içermeyen bir MST düşünülsün. Bu ağaca $e$ eklenirse bir çevrim oluşur; çevrim, kesmeyi en az bir kez daha geçmek zorundadır. O geçen kenar $f$ olsun. $f$ çıkarılıp $e$ eklendiğinde yine bir kapsayan ağaç elde edilir ve ağırlığı artmamıştır, çünkü $e \leq f$'tir. Dolayısıyla $e$'yi içeren bir MST de vardır. Bu özellik, "şu an güvenli olan en ucuz kenarı al" biçimindeki her açgözlü stratejinin doğruluğunu verir. İki algoritma yalnızca **hangi kesmeye** baktıklarıyla ayrılır. #### Prim Algoritması Tek bir düğümden başlanır ve ağaç her adımda büyütülür. Bakılan kesme, ağaçtaki düğümler ile dışarıdakiler arasındaki kesmedir; seçilen kenar bu kesmeyi geçen en hafif kenardır. ```python import heapq from collections import defaultdict def komsuluk(kenarlar: list[tuple[int, str, str]]) -> dict[str, list[tuple[int, str]]]: k: dict[str, list[tuple[int, str]]] = defaultdict(list) for agirlik, v, w in kenarlar: k[v].append((agirlik, w)) k[w].append((agirlik, v)) return k def prim(kenarlar: list[tuple[int, str, str]], baslangic: str) -> tuple[list[tuple[int, str, str]], int]: komsu = komsuluk(kenarlar) icinde = {baslangic} kuyruk = [(a, baslangic, w) for a, w in komsu[baslangic]] heapq.heapify(kuyruk) agac: list[tuple[int, str, str]] = [] while kuyruk: agirlik, v, w = heapq.heappop(kuyruk) if w in icinde: # kenarın iki ucu da ağaçta: çevrim continue icinde.add(w) agac.append((agirlik, v, w)) for a, komsusu in komsu[w]: if komsusu not in icinde: heapq.heappush(kuyruk, (a, w, komsusu)) return agac, sum(a for a, _, _ in agac) print(prim(kenarlar, "A")) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` Yapı, Dijkstra'ya çok benzer; tek fark önceliğin **kaynaktan uzaklık** değil **ağaca uzaklık** olmasıdır. Maliyet de aynıdır: ikili yığınla $O(E \log V)$. #### Kruskal Algoritması Kruskal ağaç büyütmez; kenarları ağırlığa göre sıralar ve sırayla ekler. Bir kenar, iki ucu **zaten aynı bileşendeyse** çevrim yaratacağı için atlanır. Bu denetim için **birleşim-bulma (union-find)** yapısı kullanılır: her düğümün hangi bileşende olduğunu neredeyse sabit maliyetle söyleyen bir yapı. ```python class BirlesimBulma: def __init__(self, dugumler: list[str]) -> None: self.ebeveyn = {d: d for d in dugumler} self.derece = {d: 0 for d in dugumler} def bul(self, d: str) -> str: while self.ebeveyn[d] != d: self.ebeveyn[d] = self.ebeveyn[self.ebeveyn[d]] # yol sıkıştırma d = self.ebeveyn[d] return d def birlestir(self, a: str, b: str) -> bool: ka, kb = self.bul(a), self.bul(b) if ka == kb: return False # zaten aynı bileşen if self.derece[ka] < self.derece[kb]: # dereceye göre birleştirme ka, kb = kb, ka self.ebeveyn[kb] = ka if self.derece[ka] == self.derece[kb]: self.derece[ka] += 1 return True def kruskal(kenarlar: list[tuple[int, str, str]], dugumler: list[str]) -> tuple[list[tuple[int, str, str]], int]: kume = BirlesimBulma(dugumler) agac: list[tuple[int, str, str]] = [] for agirlik, v, w in sorted(kenarlar): if kume.birlestir(v, w): agac.append((agirlik, v, w)) if len(agac) == len(dugumler) - 1: # ağaç tamamlandı break return agac, sum(a for a, _, _ in agac) print(kruskal(kenarlar, dugumler)) # ([(2, 'A', 'C'), (3, 'C', 'E'), (4, 'A', 'B'), (4, 'E', 'D'), (11, 'D', 'F')], 24) ``` İki algoritma bu çizgede aynı ağacı bulur. Genel olarak yalnızca **toplam ağırlığın** aynı olması güvencedir; eşit ağırlıklı kenarlar varsa farklı ama eşit ağırlıkta ağaçlar üretebilirler. Buradaki kesme, "eklenmeye çalışılan kenarın bir ucunun bileşeni" ile geri kalan düğümlerdir; kenar, o kesmeyi geçen en hafif kenardır çünkü daha hafif olanlar zaten denenmiştir. **Yol sıkıştırma** ve **dereceye göre birleştirme** birlikte kullanıldığında, birleşim-bulma işlemlerinin amortize maliyeti neredeyse sabittir — büyümesi ters Ackermann işleviyle sınırlıdır ve pratikte dörtten küçüktür. #### Karşılaştırma | Ölçüt | Prim | Kruskal | |---|---|---| | Yaklaşım | Ağacı büyüt | Kenarları sırayla ekle | | Yardımcı yapı | Öncelik kuyruğu | Birleşim-bulma | | Maliyet | $O(E \log V)$ | $O(E \log E)$ | | Yoğun çizge | Uygun (dizi değişkesiyle $O(V^2)$) | Sıralama baskın | | Bağlı olmayan çizge | Yalnızca bir bileşeni bulur | Kapsayan **orman** üretir | Kruskal'ın maliyetine sıralama egemendir; kenarlar zaten sıralıysa maliyet neredeyse doğrusala iner. Prim, kenar sayısı düğüm sayısının karesine yaklaştığında öne çıkar. Bir ayrım pratikte belirleyicidir: çizge bağlı değilse Kruskal her bileşen için bir ağaç üretir ve sonuç kapsayan ormandır; Prim ise yalnızca başlangıç düğümünün bileşenini kapsar. #### Kümeleme Uygulaması Kruskal'ın ara adımları tek başına anlamlıdır: algoritma $V-k$ kenar eklediğinde $k$ tane bileşen kalmıştır ve bu bileşenler, **birbirine en uzak duran** $k$ kümedir. Bu, tek bağlantılı kümeleme yöntemidir: noktalar arası uzaklıklar kenar ağırlığı sayılır, MST kurulur ve en ağır $k-1$ kenar atılır. Sonuç, kümeler arası en küçük uzaklığı en büyükleyen bölünmedir. Aynı yapı, ağ tasarımı ve yaklaşık çözümlerde de kullanılır: gezgin satıcı probleminin metrik durumunda MST, eniyi turun uzunluğu için bir alt sınır verir ve iki katını aşmayan bir tur üretmeye yarar. #### Özet - Kapsayan ağaç tüm düğümleri çevrimsiz bağlar ve $V-1$ kenar içerir; minimum kapsayan ağaç bunların en hafifidir. - Kesme özelliği, herhangi bir kesmeyi geçen en hafif kenarın bir MST'de bulunduğunu söyler ve açgözlü seçimleri gerekçelendirir. - Prim ağacı büyütür ve öncelik kuyruğu kullanır; maliyeti $O(E \log V)$'dir. - Kruskal kenarları sıralar ve birleşim-bulma ile çevrim denetler; maliyeti $O(E \log E)$'dir. - Yol sıkıştırma ve dereceye göre birleştirme, birleşim-bulma işlemlerini amortize olarak neredeyse sabit yapar. - Kruskal'ın ara durumları kümeleme üretir; MST ayrıca yaklaşık çözümlerde alt sınır sağlar. #### Sonraki Adım Şimdiye kadar kenarlar maliyet taşıyordu. Sonraki ders kenarlara farklı bir anlam yükler: **kapasite**. Bir ağdan kaynaktan hedefe en çok ne kadar akıtılabilir sorusu, artık çizge üzerinde tanımlı bir eniyileme problemidir ve yanıtı beklenmedik bir eşitlikle — en büyük akış ile en küçük kesme arasındaki eşitlikle — gelir. ### Ağ Akışı Source: https://academia.sh/tr/kurslar/algoritmalar/ag-akisi Akış ağı tanımı, kalan ağ ve artıran yol, Ford–Fulkerson yöntemi ile Edmonds–Karp değişkesi, en büyük akış–en küçük kesme teoremi ve eşleme uygulaması. Kenarlar şimdiye kadar maliyet taşıdı: uzunluk, süre, ücret. Bu ders kenarlara farklı bir anlam yükler — **kapasite**. Soru artık "en ucuz yol hangisi" değil, "kaynaktan hedefe en çok ne kadar akıtılabilir" olur. Problem, boru hatlarından iletişim ağlarına ve görev atamasına kadar geniş bir aileyi tek bir çatı altında toplar. #### Akış Ağı **Akış ağı**, her kenarında negatif olmayan bir kapasite bulunan yönlü bir çizgedir. İki özel düğüm vardır: **kaynak** ve **havuz**. Bir akış, her kenara bir değer atar ve iki kısıtı sağlar: **Kapasite kısıtı.** Hiçbir kenardaki akış, kapasitesini aşamaz. **Korunum kısıtı.** Kaynak ve havuz dışındaki her düğümde, giren akış çıkan akışa eşittir. **Akışın değeri**, kaynaktan çıkan net akıştır. Amaç bu değeri en büyüklemektir. ```python kapasite: dict[str, dict[str, int]] = { "S": {"A": 10, "C": 10}, "A": {"B": 4, "C": 2, "D": 8}, "B": {"T": 10}, "C": {"D": 9}, "D": {"B": 6, "T": 10}, "T": {}, } ``` Kaynaktan çıkan toplam kapasite 20'dir, ama bu bir üst sınırdır; ağın iç yapısı daha düşük bir tavan koyabilir. #### Kalan Ağ ve Artıran Yol Açgözlü bir yaklaşım — "boş bir yol bul, doldur, tekrarla" — yanlış sonuç verir: erken yapılan bir seçim, daha sonra daha iyi bir dağılımı engelleyebilir ve geri alınamaz. Çözüm, **kalan ağ (residual network)** kavramıdır. Kalan ağda her kenar için iki değer tutulur: - İleri yönde kalan kapasite: kapasite eksi mevcut akış. - Geri yönde, mevcut akış kadar kapasite. Geri kenar, "bu kenardan gönderilen akışı iptal etme" olanağıdır. Böylece hiçbir seçim kalıcı olarak yanlış olmaz — algoritma kendi kararını sonradan düzeltebilir. Kalan ağda kaynaktan havuza giden herhangi bir yola **artıran yol** denir. Yol boyunca gönderilebilecek miktar, üzerindeki en küçük kalan kapasitedir (darboğaz). **Ford–Fulkerson yöntemi:** Artıran yol kaldığı sürece bul ve akışı artır. #### Edmonds–Karp Değişkesi Yöntem, artıran yolun **nasıl** seçileceğini söylemez. Yol her seferinde enine aramayla — yani en az kenarlı yol olarak — seçilirse, ortaya çıkan değişkenin maliyeti $O(V \cdot E^2)$'dir ve seçimden bağımsız olarak sonlanır. ```python from collections import deque, defaultdict def kalan_ag(kapasite: dict[str, dict[str, int]]) -> dict[str, dict[str, int]]: kalan: dict[str, dict[str, int]] = defaultdict(dict) for v in kapasite: for w, c in kapasite[v].items(): kalan[v][w] = c kalan[w].setdefault(v, 0) # geri kenar: başlangıçta sıfır return kalan def edmonds_karp(kapasite: dict[str, dict[str, int]], kaynak: str, havuz: str) -> tuple[int, set[str]]: """(en büyük akış, kalan ağda kaynaktan ulaşılabilen düğümler)""" kalan = kalan_ag(kapasite) toplam = 0 while True: onceki: dict[str, str | None] = {kaynak: None} kuyruk = deque([kaynak]) while kuyruk and havuz not in onceki: v = kuyruk.popleft() for w, c in kalan[v].items(): if c > 0 and w not in onceki: onceki[w] = v kuyruk.append(w) if havuz not in onceki: # artıran yol kalmadı return toplam, set(onceki) d, darbogaz = havuz, float("inf") while onceki[d] is not None: # darboğazı bul darbogaz = min(darbogaz, kalan[onceki[d]][d]) d = onceki[d] d = havuz while onceki[d] is not None: # akışı gönder, geri kenarı büyüt kalan[onceki[d]][d] -= darbogaz kalan[d][onceki[d]] += darbogaz d = onceki[d] toplam += darbogaz akis, ulasilabilir = edmonds_karp(kapasite, "S", "T") print(akis, sorted(ulasilabilir)) # 19 ['C', 'S'] ``` Kaynaktan çıkan 20 birimlik kapasiteye karşın en büyük akış 19'dur. Sınırı koyan şeyin ne olduğu, dönen ikinci değerde saklıdır. #### En Büyük Akış – En Küçük Kesme Bir **kesme**, düğümleri kaynağın bulunduğu ve havuzun bulunduğu iki parçaya ayırır. Kesmenin kapasitesi, kaynak tarafından havuz tarafına giden kenarların kapasiteleri toplamıdır. Her akışın değeri, her kesmenin kapasitesinden küçük veya ona eşittir — akış, kesmeyi geçmek zorundadır. **Teorem** bundan daha güçlüsünü söyler: $$ \text{en büyük akış} = \text{en küçük kesme kapasitesi} $$ Gerekçe algoritmadan çıkar. Algoritma durduğunda kalan ağda kaynaktan havuza yol yoktur; kaynaktan ulaşılabilen düğümler bir kesme tanımlar. Bu kesmeyi geçen ileri kenarların hepsi doludur (yoksa ulaşılabilirlik sürerdi) ve geri kenarların hepsi boştur. Dolayısıyla akışın değeri, tam olarak bu kesmenin kapasitesine eşittir. ```python kesme = [(v, w) for v in kapasite for w in kapasite[v] if v in ulasilabilir and w not in ulasilabilir] print(kesme) # [('S', 'A'), ('C', 'D')] print(sum(kapasite[v][w] for v, w in kesme)) # 19 ``` Sonuç yalnızca bir sayı değil, bir **teşhistir**: ağın darboğazı `S→A` ve `C→D` kenarlarıdır. Kapasite artırımı yapılacaksa başka bir kenarı genişletmek akışı artırmaz. Teoremin bir yan sonucu **tam sayı özelliğidir**: kapasiteler tam sayıysa, en büyük akışı veren bir akış da tam sayılıdır. Bu, akışın ayrık nesnelerin atanması olarak yorumlanabildiği problemlerde belirleyicidir. #### İndirgeme: İkili Eşleme Ağ akışının gücü, başka problemlerin ona **indirgenebilmesindedir**. İki kümeli (bipartite) bir çizgede en büyük eşleme problemi şudur: sol taraftaki her düğümü, aralarında kenar bulunan bir sağ düğüme, hiçbir düğüm iki kez kullanılmadan eşlemek. İndirgeme basittir: yapay bir kaynaktan sol düğümlere 1 kapasiteli kenarlar, mevcut kenarlara 1 kapasite, sağ düğümlerden yapay bir havuza 1 kapasiteli kenarlar. ```python def en_buyuk_esleme(sol: list[str], sag: list[str], baglar: dict[str, list[str]]) -> int: ag: dict[str, dict[str, int]] = defaultdict(dict) for s in sol: ag["S"][s] = 1 for s, liste in baglar.items(): for h in liste: ag[s][h] = 1 for h in sag: ag[h]["T"] = 1 ag["T"] = {} return edmonds_karp(ag, "S", "T")[0] print(en_buyuk_esleme(["a1", "a2", "a3"], ["i1", "i2", "i3"], {"a1": ["i1", "i2"], "a2": ["i1"], "a3": ["i2", "i3"]})) # 3 print(en_buyuk_esleme(["a1", "a2", "a3"], ["i1", "i2", "i3"], {"a1": ["i1"], "a2": ["i1"], "a3": ["i1"]})) # 1 ``` Birinci örnekte üç adayın üçü de farklı işlere yerleşir; ikincisinde hepsi tek bir işi istediği için yalnızca biri yerleşebilir. Tam sayı özelliği burada zorunludur: yarım bir eşleme anlamsız olurdu. Aynı yöntem, görev atama, ayrık yolların sayısı ve proje seçimi gibi problemleri de akışa çevirir. İndirgeme, algoritma tasarımının merkezî tekniklerinden biridir ve **Hesaplama Kuramı** kursunda zorluk sınıflarını tanımlamak için de kullanılacaktır. #### Sonlanma ve Seçim Duyarlılığı Ford–Fulkerson yöntemi, artıran yolu keyfî seçtiğinde sorun çıkarabilir: her adımda çok küçük bir miktar artıran yollar seçilirse, tam sayı kapasitelerde bile adım sayısı akışın **değeri** kadar olabilir. Kapasiteler tam sayı değilse yöntem hiç sonlanmayabilir. Enine aramayla seçim (Edmonds–Karp) bu sorunu ortadan kaldırır: artıran yolların uzunluğu azalmaz ve toplam adım sayısı $O(V \cdot E)$ ile sınırlıdır. Bu, "yöntem" ile "algoritma" ayrımının somut bir örneğidir — bir yöntemi algoritmaya çeviren şey, açık bırakılan seçimin belirlenmesidir. #### Özet - Akış ağı, kapasiteli kenarlardan oluşur; akış kapasite ve korunum kısıtlarını sağlar. - Kalan ağdaki geri kenarlar, önceki kararların geri alınmasını sağlar ve açgözlü yaklaşımın hatasını giderir. - Ford–Fulkerson artıran yol kaldıkça akışı büyütür; Edmonds–Karp yolu enine aramayla seçerek $O(V E^2)$ sınırını verir. - En büyük akış, en küçük kesme kapasitesine eşittir; kalan ağda ulaşılabilen küme bu kesmeyi verir. - Kapasiteler tam sayıysa en büyük akışı veren tam sayılı bir akış vardır. - İkili eşleme gibi problemler akış ağına indirgenerek çözülür. #### Sonraki Adım Çizge algoritmaları, aralarında bağlantı bulunan veriler üzerinde çalıştı. Sonraki konu farklı bir yapıya geçer: **sıralı simgeler**. Metin içinde örüntü aramak, ilk bakışta doğrusal bir tarama gibi görünse de, örüntünün kendi yapısı kullanıldığında belirgin biçimde hızlanır. Konu, kaba kuvvet aramanın maliyetini ölçerek başlayacak. ## Metin Algoritmaları Örüntü arama yöntemleri, önişlemeli yapılar ve kayıpsız sıkıştırma. ### Kaba Kuvvet Örüntü Arama Source: https://academia.sh/tr/kurslar/algoritmalar/kaba-kuvvet-oruntu-arama Metin içinde örüntü arama probleminin tanımı, kaydırmalı tarama, karakter karşılaştırma sayısı, en kötü durum girdileri ve gerçek metindeki davranış. Çizge algoritmaları, aralarında bağlantı bulunan verilerle çalıştı. Bu konu farklı bir yapıya geçer: **sıralı simge dizileri** — metin. Metin işlemenin temel sorusu örüntü aramadır ve bu ders, sorunun kendisini ve en yalın çözümünü kurar. Sonraki dört ders aynı problemi farklı fikirlerle iyileştirecek; ölçüt hep aynı olacak: karakter karşılaştırma sayısı. #### Problem **Örüntü arama:** Uzunluğu $n$ olan bir metin ve uzunluğu $m$ olan bir örüntü verilir; örüntünün metinde geçtiği konumlar istenir. Sorunun üç yaygın biçimi vardır ve maliyetleri farklıdır: - **İlk geçiş.** Bulunduğu anda durulur. - **Tüm geçişler.** Metnin sonuna kadar sürer. - **Geçiş sayısı.** Konumlar saklanmadan sayılır. Bu konu boyunca aynı metin ve örüntü kullanılır: ```python metin = "ABABDABACDABABCABAB" oruntu = "ABABCABAB" ``` Örüntü metinde 10 numaralı dizinde bir kez geçer. Örnek, örüntünün kendi içinde tekrarlar barındırdığı için sonraki derslerin fikirlerini de sınamaya elverişlidir. #### Kaydırmalı Tarama En yalın çözüm, örüntüyü metnin her konumuna yerleştirip karakter karakter karşılaştırmaktır. Uyuşmazlıkta örüntü bir konum sağa kaydırılır ve karşılaştırma baştan başlar. ```python def kaba_kuvvet(metin: str, oruntu: str) -> tuple[list[int], int]: """(bulunan konumlar, karakter karşılaştırma sayısı)""" n, m = len(metin), len(oruntu) konumlar: list[int] = [] sayac = 0 for kaydirma in range(n - m + 1): j = 0 while j < m: sayac += 1 if metin[kaydirma + j] != oruntu[j]: break j += 1 if j == m: konumlar.append(kaydirma) return konumlar, sayac print(kaba_kuvvet(metin, oruntu)) # ([10], 29) print(kaba_kuvvet("ABABAB", "AB")) # ([0, 2, 4], 8) ``` Değişmez şudur: `kaydirma` konumundan önceki hiçbir konumda tam eşleşme yoktur. Sonlanma, kaydırmanın her turda bir artmasından gelir. Algoritma doğrudur ve ek alan kullanmaz. Sorunu maliyetindedir. #### Maliyet Dış döngü $n - m + 1$ kez, iç döngü en çok $m$ kez çalışır: $$ O\big((n - m + 1)\, m\big) = O(nm) $$ En kötü duruma ulaşmak için, her kaydırmada uzun bir öneki eşleşen ama sonda uyuşmayan bir girdi gerekir. ```python kotu_metin = "A" * 30 + "B" kotu_oruntu = "A" * 10 + "B" print(kaba_kuvvet(kotu_metin, kotu_oruntu)) # ([20], 231) print(len(kotu_metin), len(kotu_oruntu)) # 31 11 ``` Her kaydırmada on `A` eşleşir, sonuncu karakter uyuşmaz ve tüm iş boşa gider. Karşılaştırma sayısı $(n - m + 1) \cdot m$ çarpımına yaklaşır: $21 \times 11 = 231$. Bu tür girdiler yapay görünür, ancak ikilik veri, sınırlı abeceli diziler (genetik diziler gibi) ve tekrarlı yapılar taşıyan kütükler bu davranışı gerçekten üretir. #### Gerçek Metinde Davranış Doğal dilde durum farklıdır: uyuşmazlık genellikle ilk birkaç karakterde ortaya çıkar ve iç döngü erken kırılır. ```python uzun_metin = ("bir metin icinde oruntu aramanin maliyeti " "abecenin buyuklugune ve tekrarlara baglidir. ") * 10 for desen in ("oruntu", "maliyeti", "zzz"): konumlar, sayac = kaba_kuvvet(uzun_metin, desen) print(desen, len(konumlar), sayac, len(uzun_metin)) # oruntu 10 915 870 # maliyeti 10 963 870 # zzz 0 868 870 ``` Karşılaştırma sayısı, metin uzunluğunun küçük bir katı kadardır — çarpımsal en kötü duruma hiç yaklaşılmaz. Beklenen karşılaştırma sayısı, abece büyüklüğü $\sigma$ iken kaydırma başına yaklaşık $1/(1 - 1/\sigma)$'dır; abece büyüdükçe bu değer 1'e yaklaşır. Sonuç, çözümleme derslerinin bir uyarısını hatırlatır: **en kötü durum ile tipik durum farklı sorulardır.** Kaba kuvvet arama, büyük abeceli metinlerde pratikte hızlıdır; onu sorunlu kılan, kötü girdide sessizce karesele düşmesidir. #### Karşılaştırma Birimi Algoritmalar "karakter" üzerinde tanımlanır, ama gerçek metinde bu birimin ne olduğu bir seçimdir ve sonucu değiştirir. Bilgisayarlar Nasıl Çalışır kursundaki kodlama dersi üç düzeyi ayırmıştı: **bayt**, **kod noktası** ve kullanıcının tek harf saydığı **öbek**. Bir örüntü arama, bunların hangisinde çalıştığını belirtmek zorundadır. Bayt düzeyinde arama en hızlısıdır ve çok baytlı kodlamalarda hatalı eşleşme üretmez — kodlama, bir karakterin baytlarının başka bir karakterin baytlarının ortasında görünmemesini sağlar. Ancak bulunan konum bayt cinsindendir; karakter konumu isteniyorsa dönüşüm gerekir. Kod noktası düzeyinde arama, birleşik yazılan harflerde şaşırtır: aynı görünen iki metin farklı kod noktası dizileriyle yazılmış olabilir. Bu durumda arama öncesinde bir **normalleştirme** adımı gerekir. Büyük–küçük harf duyarsız arama ise dile bağlıdır; harf katlama kuralları her dilde aynı değildir ve tek karakterlik bir dönüşümün her zaman tek karakter üretmesi de garanti değildir. Bu ayrımlar algoritmayı değiştirmez, ama karşılaştırma işleminin maliyetini ve doğruluğunu belirler. Bu derste ve sonrakilerde karşılaştırma birimi tek kod birimi sayılır. #### Kaybedilen Bilgi Algoritmanın israfı tek bir noktada toplanır: **uyuşmazlıktan önce yapılan karşılaştırmalar unutulur.** `ABABC` örüntüsü `ABABD…` metniyle karşılaştırılırken ilk dört karakterin eşleştiği bilinir. Kaba kuvvet bunu atar ve bir sağa kayıp yeniden başlar — oysa eşleşen kısmın yapısından, bazı kaydırmaların denenmesinin gereksiz olduğu çıkarılabilir. Sonraki üç ders bu bilgiyi üç farklı biçimde kullanır: | Yaklaşım | Kullanılan bilgi | |---|---| | Rabin–Karp | Pencerenin karma değeri; karşılaştırma yerine sayı eşitliği | | Knuth–Morris–Pratt | Örüntünün kendi önek–sonek yapısı | | Boyer–Moore | Uyuşmayan metin karakteri ve örüntünün sonundan eşleme | Üçü de aynı problemi çözer ve aynı sonucu üretir; ayrıldıkları nokta, hangi ön bilgiyi hesaplayıp aramada kullandıklarıdır. #### Ne Zaman Yeterli Kaba kuvvet aramanın iki üstünlüğü vardır: önişleme yapmaz ve ek alan kullanmaz. Bu, şu durumlarda onu doğru seçim yapar: - Örüntü kısa ve metin küçükse; kurulum maliyeti kazançtan büyüktür. - Her arama farklı bir örüntüyle yapılıyorsa; önişleme her seferinde yeniden ödenir. - Abece büyük ve metin doğal dilse; tipik davranış zaten doğrusala yakındır. Buna karşılık aynı örüntü çok kez aranacaksa önişlemeli yöntemler, aynı **metin** çok kez sorgulanacaksa metni önişleyen yapılar öne çıkar. Bu ikinci yol, sonek dizileri dersinin konusudur. #### Özet - Örüntü arama, bir metinde verilen dizinin geçtiği konumları bulur; ilk geçiş, tüm geçişler ve sayım biçimleri farklı maliyetlidir. - Kaba kuvvet arama her kaydırmada baştan karşılaştırır; ek alan kullanmaz ve önişleme gerektirmez. - En kötü durum $O(nm)$'dir ve tekrarlı, küçük abeceli girdilerde gerçekten ortaya çıkar. - Doğal dilde uyuşmazlık erken oluştuğu için tipik maliyet doğrusala yakındır. - Algoritmanın israfı, uyuşmazlıktan önce elde edilen bilginin atılmasıdır. - Sonraki yöntemler bu bilgiyi karma değeri, örüntünün önek–sonek yapısı veya sondan eşleme yoluyla kullanır. #### Sonraki Adım İlk iyileştirme fikri şaşırtıcıdır: karakterleri hiç karşılaştırmamak. Metnin her penceresi bir sayıya indirgenip örüntünün sayısıyla karşılaştırılırsa, çoğu konum tek işlemde elenir. Sonraki ders, pencereden pencereye sabit maliyetle güncellenen yuvarlanan karma fikrini ve karma çakışmalarının nasıl ele alındığını kuracak. ### Rabin–Karp Source: https://academia.sh/tr/kurslar/algoritmalar/rabin-karp Yuvarlanan karma ile örüntü eşleme, sabit maliyetli pencere güncellemesi, çakışma doğrulaması, en kötü durum ve çoklu örüntü aramada üstünlüğü. Kaba kuvvet arama, her pencerede karakterleri tek tek karşılaştırıyordu. Bu dersin fikri karşılaştırmayı bambaşka bir işleme çevirir: metnin her penceresini bir **sayıya** indirgemek ve sayıları karşılaştırmak. Sayı karşılaştırması tek işlemdir. Sorun, her pencerenin sayısını hesaplamanın $O(m)$ sürmesidir — bu hâliyle hiçbir kazanç yoktur. Çözüm, sayıyı **sıfırdan hesaplamamak.** #### Yuvarlanan Karma Pencere bir karakter sağa kaydığında, yeni karma değeri eskisinden sabit sayıda işlemle elde edilebiliyorsa yönteme **yuvarlanan karma (rolling hash)** denir. Kullanılan karma, karakterleri bir sayı tabanının basamakları gibi ele alır. Taban $b$ ve asal modül $q$ için, uzunluğu $m$ olan bir pencerenin değeri: $$ H = \left(\sum_{i=0}^{m-1} s_i \cdot b^{\,m-1-i}\right) \bmod q $$ Pencere sağa kaydığında en soldaki karakterin katkısı çıkarılır, kalan bir basamak kaydırılır ve yeni karakter eklenir: $$ H' = \big((H - s_{\text{sol}} \cdot b^{\,m-1})\cdot b + s_{\text{yeni}}\big) \bmod q $$ Üç işlem, uzunluktan bağımsız: güncelleme $O(1)$'dir. #### Gerçekleştirim ```python def rabin_karp(metin: str, oruntu: str, taban: int = 256, modul: int = 1_000_003) -> tuple[list[int], int, int]: """(konumlar, karma eşleşmesi sayısı, doğrulanan karakter sayısı)""" n, m = len(metin), len(oruntu) if m > n: return [], 0, 0 ust = pow(taban, m - 1, modul) # b^(m-1) mod q karma_o = karma_m = 0 for i in range(m): # ilk pencere ve örüntü karma_o = (karma_o * taban + ord(oruntu[i])) % modul karma_m = (karma_m * taban + ord(metin[i])) % modul konumlar: list[int] = [] esleme, dogrulama = 0, 0 for kaydirma in range(n - m + 1): if karma_m == karma_o: # aday: karmalar eşit esleme += 1 dogrulama += m if metin[kaydirma:kaydirma + m] == oruntu: konumlar.append(kaydirma) if kaydirma < n - m: # pencereyi yuvarla karma_m = (karma_m - ord(metin[kaydirma]) * ust) % modul karma_m = (karma_m * taban + ord(metin[kaydirma + m])) % modul return konumlar, esleme, dogrulama metin = "ABABDABACDABABCABAB" oruntu = "ABABCABAB" print(rabin_karp(metin, oruntu)) # ([10], 1, 9) print(rabin_karp("ABABAB", "AB")) # ([0, 2, 4], 3, 6) ``` Metnin on bir penceresinden yalnızca biri karma sınamasını geçer ve doğrulama için dokuz karakter okunur. Kaba kuvvetin aynı girdide yaptığı 29 karşılaştırmayla karşılaştırılınca fark görünür. Python'un negatif sayılarda kalan işlemi negatif olmayan sonuç ürettiği için ara değerler düzeltme gerektirmez; sabit genişlikli tam sayı kullanan dillerde çıkarma sonrası modül düzeltmesi eklenir. Bilgisayarlar Nasıl Çalışır kursundaki işaretli aritmetik farkı burada somut bir hataya dönüşebilir. #### Çakışma ve Doğrulama Karma eşitliği, dizilerin eşit olduğunu **kanıtlamaz**. Farklı diziler aynı değere düşebilir — Veri Yapıları kursundaki çakışma kavramının aynısı. Bu yüzden her karma eşleşmesi karakter karşılaştırmasıyla doğrulanır. Doğrulama olmadan algoritma yanlış sonuç üretir. ```python # Modül kasıtlı olarak küçük seçilirse çakışmalar artar print(rabin_karp("ABABDABACDABABCABAB", "ABABCABAB", modul=7)) # ([10], 4, 36) ``` Küçük modülde dört pencere karma sınamasını geçer, ancak yalnızca biri gerçek eşleşmedir; diğer üçü doğrulamada elenir. Sonuç yine doğrudur — bedel, boşa yapılan karakter karşılaştırmalarıdır. Bu, karma tabanlı yöntemlerin genel deseni: **karma eleme yapar, doğrulama karar verir.** #### Maliyet Beklenen maliyet $O(n + m)$'dir: her pencere sabit işlem alır ve çakışma olasılığı, modül yeterince büyük seçildiğinde ihmal edilebilir düzeydedir. En kötü durum $O(nm)$'dir ve iki biçimde ortaya çıkar. Birincisi, gerçekten çok sayıda eşleşme olmasıdır (`"AAAA…"` içinde `"AA"` aramak) — bu kaçınılmazdır, çünkü çıktının kendisi büyüktür. İkincisi, seçilen karma işlevine göre kurgulanmış çakışma üreten bir metindir; modül rastgele seçilerek bu saldırı olasılığa çevrilir. | Ölçüt | Kaba kuvvet | Rabin–Karp | |---|---|---| | Önişleme | Yok | $O(m)$ | | Beklenen arama | $O(nm)$ en kötü | $O(n + m)$ | | En kötü arama | $O(nm)$ | $O(nm)$ | | Ek alan | $O(1)$ | $O(1)$ | #### Taban ve Modül Seçimi İki parametre yöntemin davranışını belirler. **Taban**, abece büyüklüğünden küçük olmamalıdır; küçükse farklı karakter dizileri düzenli olarak aynı değere düşer. Bayt dizileri için 256, küçük abeceler için abece büyüklüğü kadar bir değer yeterlidir. **Modül** asal seçilir. Asal olmayan bir modül, taban ile ortak çarpanlar taşıdığında karma değerlerini belirli kalıntılara yığar ve çakışmaları artırır. Modülün büyüklüğü bir taşma sorusudur: ara çarpım `karma * taban` değeri, dilin tam sayı genişliğini aşmamalıdır. Altmış dört bitlik aritmetikte modülün yaklaşık $2^{31}$ altında tutulması bunu güvence altına alır. Python'un sınırsız tam sayıları bu kısıtı kaldırır, karşılığında büyük değerlerde işlem maliyeti artar. Çakışma olasılığı, rastgele bir modül için pencere başına yaklaşık $m/q$'dur. Daha güçlü bir güvence gerekiyorsa **iki bağımsız karma** birlikte kullanılır; ikisinin birden çakışma olasılığı çarpım kadar küçülür ve doğrulama neredeyse hiç boşa çalışmaz. #### Asıl Üstünlük: Çoklu Örüntü Yöntemin en belirgin kazancı, tek örüntülü aramada değil **aynı uzunlukta birçok örüntüyü birlikte** aramada ortaya çıkar. Örüntülerin karma değerleri bir kümede tutulur; metin tek geçişte taranır ve her pencere için tek bir küme sorgusu yapılır. ```python def coklu_rabin_karp(metin: str, oruntuler: list[str], taban: int = 256, modul: int = 1_000_003) -> dict[str, list[int]]: m = len(oruntuler[0]) if any(len(o) != m for o in oruntuler): raise ValueError("tüm örüntüler aynı uzunlukta olmalı") hedefler: dict[int, list[str]] = {} for o in oruntuler: h = 0 for karakter in o: h = (h * taban + ord(karakter)) % modul hedefler.setdefault(h, []).append(o) ust = pow(taban, m - 1, modul) karma = 0 for i in range(m): karma = (karma * taban + ord(metin[i])) % modul sonuc: dict[str, list[int]] = {o: [] for o in oruntuler} for kaydirma in range(len(metin) - m + 1): for aday in hedefler.get(karma, []): if metin[kaydirma:kaydirma + m] == aday: sonuc[aday].append(kaydirma) if kaydirma < len(metin) - m: karma = (karma - ord(metin[kaydirma]) * ust) % modul karma = (karma * taban + ord(metin[kaydirma + m])) % modul return sonuc print(coklu_rabin_karp("ABABDABACDABABCABAB", ["ABAB", "BACD", "CABA"])) # {'ABAB': [0, 10, 15], 'BACD': [6], 'CABA': [14]} ``` Üç örüntü, metnin tek geçişinde bulunur. $k$ örüntü için maliyet $O(n + km)$'dir; kaba kuvvetle her örüntüyü ayrı aramak $O(knm)$ olurdu. Aynı fikir iki boyuta genişletilir: satır karmaları yuvarlanarak bir görüntü içinde dikdörtgen örüntü aranabilir. Yuvarlanan karma ayrıca içerik tanımlı parçalama gibi alanlarda da kullanılır — aynı sabit maliyetli pencere güncellemesi, farklı bir amaç için. #### Özet - Rabin–Karp, pencereleri karma değerine indirger ve karşılaştırmayı sayı eşitliğine çevirir. - Yuvarlanan karma, pencere kaydığında değeri sabit sayıda işlemle günceller. - Karma eşitliği kanıt değildir; her aday karakter karşılaştırmasıyla doğrulanır. - Beklenen maliyet $O(n + m)$, en kötü durum $O(nm)$'dir; rastgele modül seçimi kurgulanmış girdilere karşı korur. - Asıl üstünlük, aynı uzunluktaki birçok örüntüyü tek geçişte aramaktır: $O(n + km)$. #### Sonraki Adım Rabin–Karp, örüntünün **içeriğini** bir sayıya sıkıştırdı ama **yapısını** hiç kullanmadı. Oysa `ABABCABAB` örüntüsünün öneki ile soneki arasındaki örtüşme, uyuşmazlık anında kaç konumun güvenle atlanabileceğini söyler. Sonraki ders bu yapıyı önek işlevi olarak hesaplayacak ve metinde hiç geri dönmeyen bir arama kuracak. ### Knuth–Morris–Pratt Source: https://academia.sh/tr/kurslar/algoritmalar/knuth-morris-pratt Önek işlevinin tanımı ve doğrusal hesabı, metinde geri dönmeyen arama, amortize maliyet çözümlemesi ve dizgi dönemselliği. Kaba kuvvet aramanın israfı, uyuşmazlıktan önce yapılan eşleşmeleri unutmasıydı. Rabin–Karp bu israfı karma ile azalttı ama örüntünün **yapısını** hiç kullanmadı. Knuth–Morris–Pratt algoritmasının fikri şudur: eşleşen kısım zaten biliniyorsa, örüntünün kendi iç tekrarları kaç konumun güvenle atlanabileceğini söyler. #### Gözlem `ABABCABAB` örüntüsü metinle karşılaştırılırken ilk dört karakterin (`ABAB`) eşleştiği, beşincinin uyuşmadığı düşünülsün. Metnin o bölümünde `ABAB` olduğu **kesin olarak bilinir**. Kaba kuvvet bir konum kayar ve metnin `BAB…` bölümünü baştan sınar. Oysa `ABAB`'ın `AB` öneki, aynı zamanda `AB` sonekidir; dolayısıyla iki konum kayarak örüntünün ilk iki karakterini yeniden sınamadan devam edilebilir. Ara konumlar denenmeye değmez, çünkü oradaki karakterlerin ne olduğu zaten biliniyor. Genel kural: eşleşen önekin **hem öneki hem soneki** olan en uzun parça korunur, gerisi atılır. #### Önek İşlevi **Önek işlevi** $\pi$, örüntünün her öneki için "hem öz önek hem sonek olan en uzun parçanın uzunluğunu" verir. "Öz" burada parçanın tamamın kendisi olamayacağı anlamındadır. ```python def onek_islevi(oruntu: str) -> list[int]: """pi[i]: oruntu[0..i] parçasının en uzun öz önek-sonek uzunluğu.""" pi = [0] * len(oruntu) k = 0 for i in range(1, len(oruntu)): while k > 0 and oruntu[i] != oruntu[k]: k = pi[k - 1] # daha kısa bir aday öneke geri çekil if oruntu[i] == oruntu[k]: k += 1 pi[i] = k return pi print(onek_islevi("ABABCABAB")) # [0, 0, 1, 2, 0, 1, 2, 3, 4] print(onek_islevi("AABAACAABAA")) # [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5] print(onek_islevi("ABCDE")) # [0, 0, 0, 0, 0] ``` Değerler doğrudan okunur: `ABABCABAB` örüntüsünün tamamının en uzun önek-sonek örtüşmesi 4'tür (`ABAB`), dördüncü karakterine kadarki `ABAB` parçasınınki 2'dir (`AB`), hiç tekrar içermeyen `ABCDE` için hepsi sıfırdır. Hesabın kendisi, örüntüyü kendisinde aramaktır: `k` değişkeni o ana kadar eşleşen önek uzunluğunu tutar ve uyuşmazlıkta daha kısa bir adaya geri çekilir. Maliyet $O(m)$'dir — gerekçesi aramadakiyle aynıdır ve bir sonraki bölümde verilir. #### Arama Arama, aynı geri çekilme mantığını metin üzerinde uygular. Metin imleci **hiçbir zaman geri gitmez**; yalnızca örüntü imleci geri çekilir. ```python def kmp(metin: str, oruntu: str) -> tuple[list[int], int]: """(konumlar, karakter karşılaştırma sayısı)""" pi = onek_islevi(oruntu) konumlar: list[int] = [] k = 0 sayac = 0 for i, karakter in enumerate(metin): while k > 0 and karakter != oruntu[k]: sayac += 1 k = pi[k - 1] sayac += 1 if karakter == oruntu[k]: k += 1 if k == len(oruntu): konumlar.append(i - len(oruntu) + 1) k = pi[k - 1] # örtüşen sonraki geçişi kaçırma return konumlar, sayac metin = "ABABDABACDABABCABAB" oruntu = "ABABCABAB" print(kmp(metin, oruntu)) # ([10], 23) print(kmp("ABABAB", "AB")) # ([0, 2, 4], 6) print(kmp("A" * 30 + "B", "A" * 10 + "B")) # ([20], 51) ``` Son satır belirleyicidir: kaba kuvvetin 231 karşılaştırma yaptığı girdide KMP 51 yapar. Karesel davranış tamamen ortadan kalkmıştır. Eşleşme bulunduktan sonra `k = pi[k-1]` ataması, örtüşen geçişlerin kaçırılmamasını sağlar. `ABABAB` içinde `ABAB` arandığında 0 ve 2 konumlarının ikisi de bulunur. #### Maliyet Önişleme $O(m)$, arama $O(n)$, toplam $O(n + m)$ — **en kötü durumda**. Ek alan $O(m)$'dir (önek işlevi tablosu). Gerekçe amortize bir akıl yürütmedir; Karmaşıklık Hesaplama Yöntemi dersindeki toplam maliyet yöntemi burada doğrudan uygulanır. `k` değişkeni her turda en çok bir artar; $n$ tur boyunca toplam artış en çok $n$'dir. İç döngünün her turu `k`'yi en az bir azaltır ve `k` hiç negatif olmaz. Dolayısıyla iç döngü toplam en çok $n$ kez çalışabilir. İç döngü tek tek bakıldığında $O(m)$ görünse de, tüm arama boyunca toplam maliyeti doğrusaldır. | Ölçüt | Kaba kuvvet | Rabin–Karp | KMP | |---|---|---|---| | Önişleme | Yok | $O(m)$ | $O(m)$ | | En kötü arama | $O(nm)$ | $O(nm)$ | $O(n)$ | | Ek alan | $O(1)$ | $O(1)$ | $O(m)$ | | Metinde geri dönüş | Var | Yok | Yok | Son satır pratik bir sonuç doğurur: metin imleci geri gitmediği için algoritma, tamamı bellekte olmayan bir **akış** üzerinde çalışabilir. Karakterler geldikçe işlenir, geri sarma gerekmez. #### Özdevinir Görünümü Önek işlevi, aslında bir **sonlu otomatın (finite automaton)** sıkıştırılmış hâlidir. Durumlar "şu ana kadar örüntünün kaç karakteri eşleşti" bilgisini tutar; her karakter için bir geçiş tanımlanır ve son durum bir eşleşme bildirir. Geçişler önceden hesaplanırsa, arama sırasında geri çekilme döngüsü de ortadan kalkar: her metin karakteri için tam olarak bir tablo okuması yapılır. ```python def otomat(oruntu: str, abece: str) -> list[dict[str, int]]: pi = onek_islevi(oruntu) m = len(oruntu) gecis: list[dict[str, int]] = [{} for _ in range(m + 1)] for durum in range(m + 1): for karakter in abece: if durum < m and karakter == oruntu[durum]: gecis[durum][karakter] = durum + 1 # ilerle elif durum == 0: gecis[durum][karakter] = 0 # başa dön else: gecis[durum][karakter] = gecis[pi[durum - 1]][karakter] return gecis def otomatla_ara(metin: str, oruntu: str, abece: str) -> list[int]: gecis = otomat(oruntu, abece) m, durum = len(oruntu), 0 konumlar: list[int] = [] for i, karakter in enumerate(metin): durum = gecis[durum][karakter] if durum == m: konumlar.append(i - m + 1) return konumlar print(otomatla_ara("ABABDABACDABABCABAB", "ABABCABAB", "ABCD")) # [10] ``` Bedel bellektedir: tablo $O(m\sigma)$ yer kaplar ve abece büyükse bu ciddi bir maliyettir. Önek işlevi ise $O(m)$ yer kaplayıp aynı davranışı amortize olarak üretir. İki yaklaşım arasındaki seçim, abece büyüklüğü ile arama sıklığına bakılarak yapılır. #### Dönemsellik Önek işlevi, arama dışında bir bilgiyi de doğrudan verir: bir dizginin **en küçük dönemini**. Uzunluğu $m$ olan bir dizgi için $p = m - \pi[m-1]$ değeri en küçük dönem uzunluğudur. $m$, $p$'ye tam bölünüyorsa dizgi o parçanın tekrarından oluşur. ```python def en_kucuk_donem(dizgi: str) -> tuple[int, bool]: pi = onek_islevi(dizgi) p = len(dizgi) - pi[-1] return p, len(dizgi) % p == 0 for ornek in ("ABABAB", "ABCABCABC", "ABCD", "AAAA"): print(ornek, en_kucuk_donem(ornek)) # ABABAB (2, True) # ABCABCABC (3, True) # ABCD (4, True) # AAAA (1, True) ``` `ABCD` için dönem uzunluğun kendisidir: tekrar yoktur. Bu hesap, sıkıştırmada ve dizgi denkliği sorularında kullanılır; aynı tablo iki farklı işe yarar. #### Özet - KMP, eşleşen önekin önek–sonek örtüşmesini kullanarak uyuşmazlıkta kaç konumun atlanabileceğini belirler. - Önek işlevi her önek için en uzun öz önek–sonek uzunluğunu verir ve $O(m)$'de hesaplanır. - Aramada metin imleci hiç geri gitmez; yalnızca örüntü imleci geri çekilir. - Toplam maliyet $O(n + m)$'dir; gerekçe, `k` değişkeninin toplam artışını sınırlayan amortize akıl yürütmedir. - Metinde geri dönüş olmaması, algoritmayı akış verisi için uygun kılar. - Aynı tablo, bir dizginin en küçük dönemini de verir. #### Sonraki Adım KMP, örüntüyü baştan sona eşleştirir ve metnin her karakterine en az bir kez bakar. Sonraki ders ters yönden eşleştiren bir yaklaşımı ele alacak: örüntünün **sonundan** başlayan karşılaştırma, uyuşmazlık anında metnin bazı karakterlerine **hiç bakmadan** atlamayı mümkün kılar ve pratikte doğrusalın altında davranış üretir. ### Boyer–Moore Source: https://academia.sh/tr/kurslar/algoritmalar/boyer-moore Sondan eşleme, kötü karakter ve iyi sonek kuralları, Horspool basitleştirmesi, doğrusalın altına inen davranış ve dört algoritmanın ölçülen karşılaştırması. KMP metnin her karakterine en az bir kez bakıyordu; bu, doğrusal maliyetin alt sınırı gibi görünür. Boyer–Moore ailesi bu sezgiyi bozar: bazı karakterlere **hiç bakmadan** doğru sonuç üretmek mümkündür. Fikir yön değişikliğinden çıkar — örüntü, sondan başa doğru eşleştirilir. #### Sondan Eşleme Neden Kazandırır Örüntü metnin bir penceresine yerleştirilir ve karşılaştırma **son** karakterden başlar. Uyuşmazlık en sonda olursa, metindeki o karaktere bakılarak örüntünün ne kadar kaydırılabileceği belirlenir. Metindeki karakter örüntüde **hiç geçmiyorsa**, örüntü tamamen onun ötesine kaydırılabilir: tek karşılaştırmayla $m$ konum elenmiş olur. Aradaki karakterlere hiç bakılmaz. Örüntüde geçiyorsa, örüntünün o karakteri içeren en sağdaki konumu metindekiyle hizalanacak kadar kaydırılır. Bu, **kötü karakter kuralıdır**. #### Kaydırma Tablosu Kural, örüntüden çıkarılan basit bir tabloyla uygulanır: her karakter için, örüntünün sonuna olan uzaklığı. ```python def kaydirma_tablosu(oruntu: str) -> dict[str, int]: """Karakterin örüntü sonundan uzaklığı; son karakter tabloya alınmaz.""" m = len(oruntu) return {oruntu[i]: m - 1 - i for i in range(m - 1)} print(kaydirma_tablosu("ABABCABAB")) # {'A': 1, 'B': 2, 'C': 4} ``` Tablo `m - 1` karakterden kurulur; son karakter dışarıda bırakılır, çünkü kaydırma her zaman en az bir olmalıdır. Tabloda bulunmayan bir karakter için kaydırma $m$'dir. Değerler örüntüdeki **en sağdaki** geçişten hesaplanır: aynı karakter birden çok kez geçiyorsa sözlükteki son atama kalır ve bu, en sağdaki konuma karşılık gelir. #### Horspool Değişkesi Boyer–Moore'un kolay yazılan ve pratikte yaygın kullanılan basitleştirmesi, kaydırmayı uyuşan karaktere değil **pencerenin son karakterine** göre yapar. ```python def horspool(metin: str, oruntu: str) -> tuple[list[int], int]: """(konumlar, karakter karşılaştırma sayısı)""" n, m = len(metin), len(oruntu) if m > n: return [], 0 tablo = kaydirma_tablosu(oruntu) konumlar: list[int] = [] kaydirma, sayac = 0, 0 while kaydirma <= n - m: j = m - 1 while j >= 0: # sondan başa karşılaştır sayac += 1 if metin[kaydirma + j] != oruntu[j]: break j -= 1 if j < 0: konumlar.append(kaydirma) kaydirma += 1 else: son = metin[kaydirma + m - 1] kaydirma += tablo.get(son, m) # tabloda yoksa tam örüntü boyu atla return konumlar, sayac metin = "ABABDABACDABABCABAB" oruntu = "ABABCABAB" print(horspool(metin, oruntu)) # ([10], 20) print(horspool("ABABAB", "AB")) # ([0, 2, 4], 8) print(horspool("aaa", "b")) # ([], 3) ``` Kaydırma her zaman en az 1 olduğu için sonlanma güvencededir. Doğruluk, atlanan konumlarda eşleşme **olamayacağının** kuraldan çıkmasına dayanır: kaydırma, pencerenin son karakterinin örüntüde bulunabileceği en yakın hizaya kadardır. #### Ölçülen Fark Dört algoritma aynı girdilerde karşılaştırıldığında yön ayrımı sayılarla görünür. ```python # kaba_kuvvet ve kmp: önceki iki dersin gerçekleştirimleri, blok tek başına # koşabilsin diye buraya alındı def kaba_kuvvet(metin: str, oruntu: str) -> tuple[list[int], int]: """(bulunan konumlar, karakter karşılaştırma sayısı)""" n, m = len(metin), len(oruntu) konumlar: list[int] = [] sayac = 0 for kaydirma in range(n - m + 1): j = 0 while j < m: sayac += 1 if metin[kaydirma + j] != oruntu[j]: break j += 1 if j == m: konumlar.append(kaydirma) return konumlar, sayac def onek_islevi(oruntu: str) -> list[int]: """pi[i]: oruntu[0..i] parçasının en uzun öz önek-sonek uzunluğu.""" pi = [0] * len(oruntu) k = 0 for i in range(1, len(oruntu)): while k > 0 and oruntu[i] != oruntu[k]: k = pi[k - 1] # daha kısa bir aday öneke geri çekil if oruntu[i] == oruntu[k]: k += 1 pi[i] = k return pi def kmp(metin: str, oruntu: str) -> tuple[list[int], int]: """(konumlar, karakter karşılaştırma sayısı)""" pi = onek_islevi(oruntu) konumlar: list[int] = [] k = 0 sayac = 0 for i, karakter in enumerate(metin): while k > 0 and karakter != oruntu[k]: sayac += 1 k = pi[k - 1] sayac += 1 if karakter == oruntu[k]: k += 1 if k == len(oruntu): konumlar.append(i - len(oruntu) + 1) k = pi[k - 1] # örtüşen sonraki geçişi kaçırma return konumlar, sayac uzun = ("bir metin icinde oruntu aramanin maliyeti " "abecenin buyuklugune ve tekrarlara baglidir. ") * 10 for desen in ("oruntu", "tekrarlara", "zzzzz"): print(desen, kaba_kuvvet(uzun, desen)[1], kmp(uzun, desen)[1], horspool(uzun, desen)[1]) # oruntu 915 870 240 # tekrarlara 981 900 190 # zzzzz 866 870 174 # ← metin uzunluğu: 870 ``` Horspool, metin uzunluğundan **daha az** karşılaştırma yapar: 870 karakterlik metinde 174. Örüntü uzadıkça sayı düşer, çünkü her başarısız denemede daha büyük adım atılır. Doğrusalın altındaki bu davranış bir çelişki değildir: algoritma metnin her karakterine bakmaz. Örüntünün olmadığını göstermek için tüm metni okumak gerekmez. Beklenen karşılaştırma sayısı, abece büyüklüğü $\sigma$ arttıkça $n/m$'ye yaklaşır. Doğal dil ve büyük abeceler bu koşulu sağladığından, sondan eşleme metin arama araçlarının tipik seçimidir. #### En Kötü Durum ve İyi Sonek Kuralı Yalnızca kötü karakter kuralıyla en kötü durum $O(nm)$ kalır. Küçük abeceli, tekrarlı girdilerde kaydırmalar küçülür. ```python print(horspool("A" * 30 + "B", "A" * 10 + "B")[1]) # 31 print(kaba_kuvvet("A" * 30 + "B", "A" * 10 + "B")[1]) # 231 ``` Bu girdide sonuç iyidir, çünkü uyuşmazlık ilk karşılaştırmada ortaya çıkar. Ters kurgu — `"A"*30` içinde `"BAAAAAAAAA"` gibi bir örüntü — kaydırmaları bire indirir. Tam Boyer–Moore, kötü karakter kuralına **iyi sonek kuralını** ekler: eşleşmiş olan sonek parçası, örüntünün başka bir yerinde geçiyorsa oraya hizalanır; geçmiyorsa sonekin bir öneki örüntünün başına denk getirilir. İki kuraldan büyük kaydırmayı öneren seçilir. İyi sonek tablosu, KMP'nin önek işlevine benzer biçimde $O(m)$'de kurulur. Ek bir teknikle (eşleşmiş bölgelerin yeniden karşılaştırılmasını önleyen kural) en kötü durum $O(n)$'e indirilebilir. #### Pencerenin Bir Sonrasına Bakmak Aynı ailenin bir başka değişkesi, kaydırmayı pencerenin **son karakterine** değil, pencereden hemen **sonraki** karaktere göre yapar. O karakter, bir sonraki hizalamada örüntünün içinde kalacağından, örüntüde hiç geçmiyorsa $m+1$ konum birden atlanabilir. ```python def hizli_arama(metin: str, oruntu: str) -> tuple[list[int], int]: n, m = len(metin), len(oruntu) if m > n: return [], 0 tablo = {oruntu[i]: m - i for i in range(m)} # tüm karakterler tabloda konumlar: list[int] = [] kaydirma, sayac = 0, 0 while kaydirma <= n - m: j = 0 while j < m: sayac += 1 if metin[kaydirma + j] != oruntu[j]: break j += 1 if j == m: konumlar.append(kaydirma) if kaydirma + m >= n: break kaydirma += tablo.get(metin[kaydirma + m], m + 1) return konumlar, sayac print(hizli_arama(metin, oruntu)) # ([10], 14) print(hizli_arama(uzun, "tekrarlara")[1]) # 190 ``` Karşılaştırma yönü burada baştan sonadır; kazanç yalnızca kaydırma kuralından gelir. Tablonun tüm örüntü karakterlerini içermesi ve kaydırmanın $m+1$'e kadar çıkabilmesi, gerçekleştirimi kısaltırken pratikte büyük adımlar sağlar. #### Dört Yöntemin Yeri | Ölçüt | Kaba kuvvet | Rabin–Karp | KMP | Boyer–Moore | |---|---|---|---|---| | Önişleme | Yok | $O(m)$ | $O(m)$ | $O(m + \sigma)$ | | Beklenen | $O(n)$ (büyük abece) | $O(n + m)$ | $O(n + m)$ | $O(n/m)$'ye yakın | | En kötü | $O(nm)$ | $O(nm)$ | $O(n + m)$ | $O(n)$ (tam biçim) | | Ek alan | $O(1)$ | $O(1)$ | $O(m)$ | $O(m + \sigma)$ | | Akış verisi | Uygun | Uygun | Uygun | Uygun değil | Son satır, sondan eşlemenin bedelidir: pencere içinde geri gidildiği için metnin ileriye doğru tek geçişte okunması yetmez. Seçim ölçütü şudur: **abece büyük ve örüntü uzunsa** Boyer–Moore; **en kötü durum güvencesi ya da akış işleme gerekiyorsa** KMP; **çok sayıda örüntü aynı anda aranıyorsa** Rabin–Karp; **kısa metin ve tek seferlik arama** için kaba kuvvet. #### Özet - Boyer–Moore ailesi örüntüyü sondan başa eşleştirir; bu, metnin bazı karakterlerine hiç bakmadan atlamayı mümkün kılar. - Kötü karakter kuralı, uyuşmayan metin karakterinin örüntüdeki en sağdaki konumuna hizalar; örüntüde yoksa tam örüntü boyu atlanır. - Horspool değişkesi kaydırmayı pencerenin son karakterine göre yapar ve tek tabloyla çalışır. - Beklenen karşılaştırma sayısı abece büyüdükçe $n/m$'ye yaklaşır; ölçümde metin uzunluğunun altına iner. - İyi sonek kuralı eklendiğinde en kötü durum doğrusala indirilebilir. - Sondan eşleme akış verisine uygun değildir; pencere içinde geri gidilir. #### Sonraki Adım Dört algoritma da **örüntüyü** önişledi; metin her aramada baştan tarandı. Aynı metinde binlerce sorgu yapılacaksa denge tersine döner: metni bir kez önişleyip her sorguyu logaritmik maliyetle yanıtlamak daha ucuzdur. Sonraki ders, metnin tüm soneklerini düzenleyen yapıları — sonek dizisi ve sonek ağacını — ele alacak. ### Sonek Dizileri ve Ağaçları Source: https://academia.sh/tr/kurslar/algoritmalar/sonek-dizileri-ve-agaclari Metni önişleyen yapılar, sonek dizisi kurulumu ve ikili aramayla sorgu, en uzun ortak önek dizisi, sonek ağacı ile karşılaştırma ve uygulama alanları. Önceki dört algoritma **örüntüyü** önişledi; metin her aramada baştan tarandı. Bu, tek seferlik aramalar için doğru dengedir. Denge, aynı metinde binlerce sorgu yapıldığında tersine döner: metin bir kez önişlenip sorgular metin uzunluğuna değil **örüntü** uzunluğuna bağlı maliyetle yanıtlanabilir. Bu ders o yapıları kurar. #### Sonek Dizisi Bir metnin tüm sonekleri sıralanır ve yalnızca **başlangıç konumları** saklanır. Ortaya çıkan tam sayı dizisine **sonek dizisi (suffix array)** denir. ```python def sonek_dizisi(metin: str) -> list[int]: """Sonekleri sözlük sırasına dizen başlangıç konumları.""" return sorted(range(len(metin)), key=lambda i: metin[i:]) metin = "banana" sd = sonek_dizisi(metin) print(sd) # [5, 3, 1, 0, 4, 2] print([metin[i:] for i in sd]) # ['a', 'ana', 'anana', 'banana', 'na', 'nana'] ``` Yapı yalnızca $n$ tam sayı tutar; metnin kendisi bir kez saklanır. Bellek maliyeti, sonekleri ayrı ayrı saklamaya göre çok düşüktür. Yukarıdaki kurulum, karşılaştırma başına $O(n)$ karakter okuduğu için $O(n^2 \log n)$'dir ve yalnızca gösterim amaçlıdır. Sonek dizisi, uzunlukları ikişer katlayarak sıralayan yöntemle $O(n \log n)$'de, daha ileri yöntemlerle $O(n)$'de kurulur. #### Sorgu Sonekler sıralı olduğuna göre, örüntüyle **başlayan** sonekler dizide bitişik bir aralıkta bulunur. İkili arama bu aralığın sınırlarını verir. ```python def aralik(metin: str, sd: list[int], oruntu: str) -> tuple[int, int]: """Örüntüyle başlayan soneklerin sonek dizisindeki [bas, son) aralığı.""" m = len(oruntu) lo, hi = 0, len(sd) while lo < hi: # alt sınır orta = (lo + hi) // 2 if metin[sd[orta]:sd[orta] + m] < oruntu: lo = orta + 1 else: hi = orta bas = lo lo, hi = bas, len(sd) while lo < hi: # üst sınır orta = (lo + hi) // 2 if metin[sd[orta]:sd[orta] + m] <= oruntu: lo = orta + 1 else: hi = orta return bas, lo uzun_metin = "ABABDABACDABABCABAB" sd_uzun = sonek_dizisi(uzun_metin) bas, son = aralik(uzun_metin, sd_uzun, "ABAB") print(son - bas, sorted(sd_uzun[bas:son])) # 3 [0, 10, 15] bas, son = aralik(uzun_metin, sd_uzun, "ZZ") print(son - bas) # 0 ``` İkili aramanın her adımı $m$ karaktere kadar karşılaştırma yapar; sorgu maliyeti $O(m \log n)$'dir. Geçiş **sayısı** ise aralık genişliğinden tek işlemde okunur — kaç kez geçtiğini bulmak için metni taramak gerekmez. İki maliyet karşılaştırılınca denge görünür: KMP her sorguda $O(n + m)$ öder; sonek dizisi bir kez $O(n \log n)$ öder, sonra her sorguya $O(m \log n)$ ile yanıt verir. Sorgu sayısı büyüdükçe ikinci yol kazanır — Zaman ve Alan Ödünleşimi dersindeki önişleme kalıbının metin üzerindeki karşılığı. #### En Uzun Ortak Önek Dizisi Sonek dizisi tek başına eksiktir; komşu sonekler arasındaki örtüşme bilinirse çok daha fazla soru yanıtlanır. **LCP dizisi**, sıralamada ardışık iki soneğin en uzun ortak önek uzunluğunu tutar. Kasai yöntemi bunu $O(n)$'de hesaplar. ```python def lcp_dizisi(metin: str, sd: list[int]) -> list[int]: """lcp[k]: sd[k-1] ile sd[k] soneklerinin ortak önek uzunluğu.""" n = len(metin) sira = [0] * n for k, i in enumerate(sd): sira[i] = k lcp = [0] * n h = 0 for i in range(n): if sira[i] > 0: j = sd[sira[i] - 1] while i + h < n and j + h < n and metin[i + h] == metin[j + h]: h += 1 lcp[sira[i]] = h if h: h -= 1 # bir sonraki sonek en az h-1 ortak önek taşır else: h = 0 return lcp print(lcp_dizisi("banana", sd)) # [0, 1, 3, 0, 0, 2] ``` Dizinin en büyük değeri, metinde **iki kez geçen en uzun parçayı** verir. ```python def en_uzun_tekrar(metin: str) -> str: sd = sonek_dizisi(metin) lcp = lcp_dizisi(metin, sd) k = max(range(len(lcp)), key=lambda i: lcp[i]) return metin[sd[k]:sd[k] + lcp[k]] print(en_uzun_tekrar("banana")) # ana print(en_uzun_tekrar("ABABDABACDABABCABAB")) # ABAB ``` Aynı yapı başka soruları da yanıtlar: iki metnin en uzun ortak parçası (birleştirilip tek metin gibi işlenerek), farklı parça sayısı ve sıkıştırmada tekrar tespiti. #### Sonek Ağacı **Sonek ağacı**, metnin tüm soneklerini içeren sıkıştırılmış bir sözlük ağacıdır: tek çocuklu düğüm zincirleri birleştirilir ve kenarlar metnin alt aralıklarını gösterir. Sonek dizisiyle aynı bilgiyi taşır, farklı düzenler: | Ölçüt | Sonek dizisi | Sonek ağacı | |---|---|---| | Kurulum | $O(n)$ (ileri yöntemler) | $O(n)$ | | Sorgu | $O(m \log n)$ | $O(m)$ | | Bellek sabiti | Küçük ($n$ tam sayı) | Büyük (düğüm ve işaretçiler) | | Gerçekleştirim | Basit | Karmaşık | Sorgu maliyetindeki logaritmik çarpan, sonek dizisine LCP bilgisi eklenerek de kaldırılabilir. Pratikte sonek dizisi tercih edilir: bellek sabiti küçük ve kodu daha denetlenebilirdir. Sonek ağacı, ağaç yapısının kendisini gerektiren kuramsal çözümlemelerde ve bazı özel sorgularda öne çıkar. Aynı ailedeki üçüncü yapı **sonek otomatıdır**; metnin tüm alt dizgilerini tanıyan en küçük otomattır ve alt dizgi sayma gibi soruları doğrudan yanıtlar. #### Nerede Kullanılır Önişlemeli metin yapıları, metnin sabit ve sorguların çok olduğu her yerde görünür: - **Tam metin dizinleme.** Belge kümesinde arama; sorgu başına metni taramak ölçeklenmez. - **Biyoenformatik.** Genetik diziler uzun, abece küçük ve aynı dizi üzerinde binlerce sorgu yapılır. - **Yinelenen kod ve içerik tespiti.** En uzun ortak parça sorgularıyla. - **Sıkıştırma.** Tekrar eden parçaların bulunması; Burrows–Wheeler dönüşümü doğrudan sonek sıralamasına dayanır. Ortak ölçüt aynıdır: **önişleme maliyeti sorgu sayısına bölündüğünde kazanç kalıyor mu?** Bu soru, Karmaşıklık Sınıflarını Okumak dersinde alt doğrusal sınıflar için sorulmuştu; yanıtı burada somut bir veri yapısı seçimine dönüşür. #### Özet - Sonek dizisi, metnin tüm soneklerini sözlük sırasına dizen başlangıç konumlarıdır ve $n$ tam sayı yer kaplar. - Örüntüyle başlayan sonekler bitişik bir aralıktadır; ikili arama sorguyu $O(m \log n)$'de yanıtlar ve geçiş sayısını aralık genişliği verir. - LCP dizisi ardışık soneklerin ortak önek uzunluğunu tutar ve $O(n)$'de hesaplanır; en büyük değeri en uzun tekrar eden parçayı verir. - Sonek ağacı aynı bilgiyi ağaç olarak düzenler; sorgusu $O(m)$'dir ama bellek sabiti ve gerçekleştirim karmaşıklığı yüksektir. - Yapı seçimi, önişleme maliyetinin sorgu sayısına bölünmesiyle verilir. #### Sonraki Adım Metin algoritmalarının son sorusu aramadan farklıdır: aynı bilgiyi **daha az yerle** saklamak. Sonraki ders, karakter sıklıklarına göre değişken uzunlukta kod üreten Huffman yöntemini kuracak ve açgözlü bir seçimin neden eniyi kodu verdiğini gösterecek. ### Huffman Kodlaması Source: https://academia.sh/tr/kurslar/algoritmalar/huffman-kodlamasi Değişken uzunluklu önek içermeyen kodlar, açgözlü ağaç kurulumu, eniyilik gerekçesi, entropi sınırı ve yöntemin sınırları. Metin algoritmalarının son sorusu aramadan farklıdır: aynı bilgiyi **daha az yerle** saklamak. Sabit uzunluklu kodlama, her simgeye eşit sayıda bit ayırır; Bilgisayarlar Nasıl Çalışır kursundaki karakter kodlamaları bu düzendeydi. Oysa simgeler eşit sıklıkta geçmez. Sık geçene kısa, seyrek geçene uzun kod verilirse toplam uzunluk düşer. #### Önek İçermeyen Kodlar Değişken uzunluk bir belirsizlik doğurur: `A → 0`, `B → 01` atanırsa, `001` dizisi hem `AB` hem `AA…` başlangıcı gibi okunabilir. Çözüm **önek içermeyen (prefix-free) koddur**: hiçbir simgenin kodu, başka bir simgenin kodunun öneki olamaz. Böyle bir kod tek anlamlı çözülür — okunan bitler bir koda uyduğu anda o simge kesinleşir. Önek içermeyen kodlar ikili ağaçlarla birebir eşleşir: simgeler yapraklarda durur, kod kökten yaprağa giden yolun bitleridir (sol 0, sağ 1). Yaprakta durma koşulu, önek içermeme koşulunun ta kendisidir. Bir simgenin kod uzunluğu, yaprağının derinliğidir. Amaç, ağırlıklı derinlik toplamını en küçüklemektir: $$ \text{maliyet} = \sum_{i} f_i \cdot d_i $$ Burada $f_i$ simgenin sıklığı, $d_i$ yaprağının derinliğidir. #### Açgözlü Kurulum Huffman yöntemi, ağacı **yapraklardan köke** doğru kurar: en seyrek iki simge birleştirilip tek bir düğüm gibi ele alınır ve işlem tek düğüm kalana kadar sürer. Sezgi şudur: en seyrek iki simge, en derin yaprakları hak eder; onları birleştirmek, maliyeti en az artıran adımdır. ```python import heapq from collections import Counter def huffman_kodlari(sikliklar: dict[str, int]) -> dict[str, str]: """Simge → ikili kod eşlemesi.""" if len(sikliklar) == 1: # tek simgeli özel durum return {next(iter(sikliklar)): "0"} sayac = 0 yigin: list[tuple[int, int, dict[str, str]]] = [] for simge, f in sorted(sikliklar.items()): # belirli sıra: yığın eşitlikte kararsızdır heapq.heappush(yigin, (f, sayac, {simge: ""})) sayac += 1 while len(yigin) > 1: f1, _, sol = heapq.heappop(yigin) # en seyrek iki düğüm f2, _, sag = heapq.heappop(yigin) birlesik = {s: "0" + k for s, k in sol.items()} birlesik.update({s: "1" + k for s, k in sag.items()}) heapq.heappush(yigin, (f1 + f2, sayac, birlesik)) sayac += 1 return yigin[0][2] metin = "ABRACADABRA" sikliklar = dict(Counter(metin)) print(dict(sorted(sikliklar.items()))) # {'A': 5, 'B': 2, 'C': 1, 'D': 1, 'R': 2} kod = huffman_kodlari(sikliklar) print(dict(sorted(kod.items()))) # {'A': '0', 'B': '110', 'C': '100', 'D': '101', 'R': '111'} ``` En sık geçen `A` bir bitle, en seyrek `C` ve `D` üç bitle kodlanır. Hiçbir kod diğerinin öneki değildir. Yığına konan üçüncü alan (`sayac`), eşit sıklıklarda sıralamayı belirli kılar. Bu olmadan kod eşitliklerde çalıştırmadan çalıştırmaya değişebilir; sıkıştırılmış veriyi çözecek tarafın aynı ağacı kurması gerektiğinden bu istenmeyen bir belirsizliktir. #### Kazanç ve Çözme ```python import math def kodla(metin: str, kod: dict[str, str]) -> str: return "".join(kod[karakter] for karakter in metin) def coz(bitler: str, kod: dict[str, str]) -> str: ters = {v: k for k, v in kod.items()} sonuc: list[str] = [] tampon = "" for bit in bitler: tampon += bit if tampon in ters: # önek içermediği için ilk uyum kesindir sonuc.append(ters[tampon]) tampon = "" return "".join(sonuc) bitler = kodla(metin, kod) sabit = len(metin) * math.ceil(math.log2(len(sikliklar))) print(len(bitler), sabit) # 23 33 print(coz(bitler, kod) == metin) # True ``` Beş farklı simge sabit uzunlukla üç bit gerektirir: 33 bit. Huffman kodu aynı metni 23 bitle saklar — yaklaşık üçte bir azalma. Çözme işlemi, önek içermeme özelliğinin doğrudan sonucudur: biriken bit dizisi bir koda uyduğu anda karar verilir, geri dönüş gerekmez. #### Eniyilik Huffman kodu, **simge başına kod atayan** yöntemler arasında en küçük toplam uzunluğu verir. Gerekçe iki gözleme dayanır. **Birincisi:** Eniyi bir ağaçta, en seyrek iki simge en derin düzeyde ve kardeş olacak biçimde bulunabilir. Değilse, yer değiştirme maliyeti artırmaz — Minimum Kapsayan Ağaç dersindeki değiş tokuş akıl yürütmesinin aynısı. **İkincisi:** İki simge birleştirilip tek simge sayıldığında, küçülen problemin eniyi çözümü, özgün problemin eniyi çözümünü verir. İkisi birlikte, açgözlü seçimin her adımda güvenli olduğunu gösterir. Kurulum maliyeti, öncelik kuyruğu nedeniyle $O(k \log k)$'dir; $k$ farklı simge sayısıdır. #### Entropi Sınırı Ne kadar iyileştirilebileceğinin bir sınırı vardır. Simge olasılıkları $p_i$ iken **entropi** $$ H = -\sum_i p_i \log_2 p_i $$ simge başına ortalama bit sayısının alt sınırıdır. Huffman kodu bu sınıra yakın çalışır: ortalama uzunluğu $H$ ile $H + 1$ arasındadır. ```python n = len(metin) H = -sum((f / n) * math.log2(f / n) for f in sikliklar.values()) print(round(H, 3), round(len(bitler) / n, 3)) # 2.04 2.091 ``` Ölçülen ortalama 2,091 bit, kuramsal alt sınır 2,04 bitin hemen üstündedir. Fark, kod uzunluklarının tam sayı olmak zorunda olmasından gelir; bir simge 1,5 bit alamaz. Bu sınırın aşılması ancak varsayım değiştirilerek mümkündür — tıpkı karşılaştırmalı sıralamanın alt sınırının anahtar yapısı kullanılarak aşılması gibi. Simgeleri tek tek değil öbekler hâlinde kodlayan yöntemler kesirli bit maliyetine yaklaşır; tekrar eden parçaları sözlükleyen yöntemler ise simge bağımsızlığı varsayımını bırakır ve metindeki tekrarlardan yararlanır. İkincisi, önceki dersteki sonek yapılarıyla doğrudan ilişkilidir. #### Sınırlar ve Uygulama Ayrıntıları **Sıklık tablosu gerekir.** Kodlama iki geçiş ister: önce sıklıklar sayılır, sonra kodlanır. Ayrıca çözücünün ağacı kurabilmesi için tablo da saklanır; kısa metinlerde bu ek yük kazancı yiyebilir. **Uyarlanabilir değişkeler** tabloyu akış ilerledikçe günceller ve tek geçişle çalışır; karşılığında kodlayıcı ile çözücünün tam olarak aynı güncelleme kuralını izlemesi gerekir. **Simge bağımsızlığı varsayılır.** Yöntem, bir simgenin bir öncekiyle ilişkisini kullanmaz. Doğal dilde bu ilişki güçlüdür; bu nedenle Huffman genellikle tek başına değil, tekrarları önce eleyen bir aşamanın ardından kullanılır. **Kayıpsızdır.** Çözülen veri özgün veriyle birebir aynıdır. Görüntü ve ses için kullanılan kayıplı yöntemler farklı bir aileye aittir ve bu kursun dışındadır. #### Özet - Önek içermeyen kodlar tek anlamlı çözülür ve ikili ağaçlarla birebir eşleşir; kod uzunluğu yaprağın derinliğidir. - Huffman yöntemi en seyrek iki düğümü birleştirerek ağacı yapraklardan köke kurar; maliyeti $O(k \log k)$'dir. - Eniyiliği, en seyrek iki simgenin kardeş yapılabileceği değiş tokuş akıl yürütmesine dayanır. - Ortalama kod uzunluğu entropi ile entropi artı bir arasındadır; fark, bit sayılarının tam sayı olmasından gelir. - Sıklık tablosunun saklanması, simge bağımsızlığı varsayımı ve iki geçişli yapı yöntemin başlıca sınırlarıdır. #### Kurs Kapanışı Algoritmalar kursu, ölçütle başladı ve uygulamayla bitti. Önce bir çözümün maliyeti tanımlandı: işlem sayımı, asimptotik gösterim, karmaşıklık sınıfları, hesaplama yöntemi ve zaman–alan ödünleşimi. Ardından aynı ölçüt üç alanda kullanıldı — arama ve sıralama, çizge algoritmaları, metin algoritmaları. Tekrar eden birkaç fikir, kursu tek bir sistem hâline getirir: - **Alt sınır düşünmek.** Karşılaştırmalı arama $\Omega(\log n)$, karşılaştırmalı sıralama $\Omega(n \log n)$, entropi $H$: her problemin aşılamayan bir tabanı vardır ve bu taban, ancak varsayım değiştirilerek aşılır. - **Açgözlü seçimi kanıtlamak.** Dijkstra, Prim, Kruskal ve Huffman aynı kalıbı paylaşır: seçimin güvenli olduğu bir değiş tokuş akıl yürütmesiyle gösterilir. - **Böl ve yönet.** Birleştirmeli sıralama, hızlı sıralama, ikili arama ve ters çift sayımı aynı bağıntıdan doğar. - **Önişleme ödünleşimi.** İkili arama, sonek dizisi, KMP tablosu ve karma tabanlı yöntemler, "bir kez öde, çok kez kazan" hesabının farklı biçimleridir. Sonraki kurs, **İşletim Sistemi Kavramları**, bu algoritmaların üzerinde çalıştığı katmanı ele alır: süreçler, eşzamanlılık, bellek yönetimi ve dosya sistemleri. Planlama algoritmaları, sayfa değiştirme ve kilitlenme tespiti gibi konularda buradaki çözümleme araçları doğrudan kullanılacaktır.