Algoritmalar Teorisi
Bu sene bilgisayar mühendisliği 3. sınıf öğrencisi olarak aldığım “Algoritmalar Teorisi” dersi hakkında kendi notlarımı derleyip, kaynak oluşturmak istedim.
Öncelikle “Algoritmalar Teorisi” nedir bununla başlayalım.
Esasen, mekanik olarak ne tür bir şeyi gerçekten hesaplayabileceğiniz, bunu yapmanın ne kadar hızlı ve ne kadar yer kaplayacağı ile ilgilidir.
Bu hesaplamaları yaparken kullandığımız araçlara da “otomat” adı verilmiştir. Kağıt üzerinde basit işlemleri yapabilen araç olarak düşünebiliriz.
Bu otomatlar sayesinde, matematikçiler, bilgisayar bilimcileri makinelerin nasıl çalıştığını, problem çözdüğünü, fonksiyonların hesaplanabilirliğini anlayabilir.
Otomatlar 4 ana başlıkta incelenir:
- Sonlu-Durum Makineleri (Finite State Machine)
- Aşağı Sürüklemeli Otomatlar (Push-Down Automata)
- Doğrusal Sınırlı Otomatlar (Linear Bounded Automata)
- Turing Machine (Turing Makinesi)
Bu makinelerden en basit olanı Sonlu Durum Makineleriyken, en karmaşık yapıda olanı da günümüzdeki bilgisayarların temeli olan Turing Makineleridir. Bir Turing Makinesi aynı zamanda Sonlu Durum makinesiyken, tersi doğru değildir.
Son cümlede ne demek istediğimi aşağıdaki görsel açıklıyor:
Şimdi bu otomatları ayrı ayrı inceleyelim:
Sonlu Durum Makinesi (Finite State Machine) Nedir?
Sonlu Durum Makinesi, sembol dizisini girdi olarak alır ve durumunu buna göre değiştirir. Girişte istenilen sembol bulunursa, geçiş gerçekleşir.
Geçiş sırasında otomatlar bir sonraki duruma (state) geçebilir ya da aynı durumda kalabilir.
Sonlu durum makinesinin iki çeşidi vardır:
- Deterministic Finite State Automata (Belirli Sonlu Otomat):
>Her geçiş sadece tek bir duruma gider. Bir durumdan (state) başka bir duruma giderken bir kelime ile sadece bir duruma gidilebilir.
>Tek bir bitiş durumu vardır (Final State). Birden fazla final state olamaz.
>Lambda veya epsilon kelimeleri (belirsizlik bildirir) durumlar arası geçişte yer alamaz.
- Non-deterministic Finite State Automata (Belirsiz Sonlu Otomat): DFA’nın tersine; karşık geçişlerin olduğu, birden fazla final state’in kabul edildiği, bir sonraki geçişte nereye gidileceğinin belli olmadığı otomatlardır.
Sonlu durum makinesinde iki durum vardır:
- Accept State (Kabul durumu)
- Reject State (Red durumu)
Eğer otomat son duruma (final state) ulaşırsa, işlem kabul edilecektir.
Aşağı Sürüklemeli Otomatlar (Push-Down Automata) Nedir?
Basitçe “harici yığın (stack) belleği” ile güçlendirilmiş Non-deterministic Finite State Automata olarak düşünülebilir (NFA). Stack (yığın) eklenmesi Push-Down otomatlarına “Last In First Out” (LIFO), yani son giren ilk çıkar ile yönetilen bellek yeteneği kazandırır.
Push-Down otomatlar, sınırsız miktarda bilgi depolayabilir fakat stack (yığın) yapısından dolayı, bellekte sınırlı miktarda bilgiye erişilebilir.
Push-Down otomatlarda, Push-Pop metotları kullanılır. Yani otomat, bir ögeyi stack(yığın) üstüne itebilir (push) ve ögeyi yığının tepesinden çıkarabilir (pop). Stack’in aşağısında kalan bir ögeyi okumak için, üstteki ögelerin dışarı atılması (pop) gerekir.
Sonlu durum makinelerinden daha güçlüdür, sonlu durum makinelerinde hafıza konsepti yokken, push-down otomatlarında sınırsız hafıza, sınırlı erişim bulunur bu da PDA’yı daha güçlü kılar.
Doğrusal Sınırlı Otomatlar (Linear Bounded Automata) Nedir?
Basitçe;
- Belirli, sınırlı ve sonlu uzunlukta banta sahip,
- Deterministic olmayan,
- Multi-track,
bir Turing Makinesidir.
Turing Makinesi (Turing Machine) Nedir?
Turing Makinesi, girdilerin verildiği hücrelere bölünmüş sonsuz uzunlukta bir banttan (tape) oluşan matematiksel bir modeldir. Giriş bandını (tape), okuyan bir kafadan (head) oluşur.
Durum kaydı, Turing Makinesinin durumunu saklar yani bu da demek oluyor ki Turing Makinesinin hafızası vardır. Bir giriş sembolü okunduktan sonra başka bir sembolle değiştirilir, head(kafa) sayesinde bir hücreden bir hücreye, sağa veya sola hareket edip okuma yapabilir. Final state (son duruma) ulaşılırsa, girdi kabul edilir (accepted).
Tasarımın basitliğine karşın, Turing Makinesi ile herhangi bir bilgisayar algoritması -ne kadar karışık olursa olsun- simüle edilebilir.
Sonsuz hafıza ve sonsuz erişim özellikleri sayesinde konuştuğumuz makinelerden en güçlüsü Turing Makinesidir.
Bu konuştuğumuz makinelerde bir güç sıralaması yapacak olursak;
Turing Machine > Linear-Bounded Automata > Push-Down Automata > Finite State Machine
diyebiliriz.
