2 Hafta 01
2.1 Sorular
- Turing complete
- NP Complete/NP Hard
- Regular Expressions
2.2 En Önemli 5 kavram
| # | Kavram | Açıkladığı Temel Soru |
|---|---|---|
| 1 | Hal Makineleri ve Düzenli İfadeler | En basit hafıza modeliyle neleri hesaplayabiliriz? |
| 2 | Turing Tamlığı (Sizin seçiminiz) | Güçlü bir hesaplama modelinin (ve modern bilgisayarın) sınırları nerede başlar? |
| 3 | Kararlaştırılamazlık (Durma Problemi) | Matematiksel olarak asla çözülemeyecek problemler var mıdır? |
| 4 | P vs. NP Problemi | Çözümü kolay doğrulanabilen her problem kolayca çözülebilir mi? |
| 5 | NP-Tamlık / NP-Zorluk (Sizin seçiminiz) | Pratikteki en zor optimizasyon/hesaplama problemleri hangileridir ve bunları nasıl sınıflandırırız? |
2.3 Hesaplama Kuramı, Derleyici (Compiler) ve Bilgisayar Mühendisliğindeki Yeri
2.4 Derleyici Çalışması 1
2.5 Derleyici Çalışması 2
2.6 Giriş ve Derleyici Mimarisine Genel Bakış
- Kaynak Kodun (Source Text) Biçimsel Dillerdeki Karşılığı: Alfabe (\(\)) üzerindeki katar (string) kavramı.
- Derleyicinin İki Ana Safhası: Analiz (Frontend) ve Sentez (Backend) evreleri.
- Hesaplama kuramı modellerinin derleyici mimarisindeki katmanlı rolü.
2.7 Sözcüksel Analiz (Lexical Analysis / Scanner)
- Kaynak kodun atomik jetonlara (token) ayrıştırılması.
- Düzenli İfadeler (RE) ve Sonlu Durum Otomatları (DFA / NFA) kullanımı.
- Tip-3 Düzenli Diller (Regular Languages) katmanı ve Unix
lexgibi otomatik tarayıcı üreteçleri.
2.8 Sözdizimsel Analiz (Syntax Analysis / Parser)
- Jeton dizilimlerinin dilbilgisi kurallarına uygunluğunun denetimi ve türetme ağacı (parse tree) oluşumu.
- Bağlamdan Bağımsız Gramerler (CFG) ve Yığınlı Otomatlar (Pushdown Automata - PDA).
- Tip-2 Bağlamdan Bağımsız Diller (CFL) katmanı ve Unix
yaccgibi ayrıştırıcı araçları.
2.9 Anlamsal Temsil (Semantic Representation) ve Kod Üretimi
- Tip kontrolü, anlamsal doğrulama ve Ara Temsil (Intermediate Representation - IR) oluşturma.
- Sentez (Backend) aşamasında hedef makine koduna (.exe) dönüşüm ve kuramın derleyici yazılımındaki doğrudan uygulaması.
2.10 Hesaplama Kuramı Bilgisayar Mühendisliğinde Ders Olmalı mı, Olmamalı mı?
2.10.1 Eleştirel Yaklaşım (“Zorunlu Olmamalı” Görüşü)
- Sektörel Pratiklik: Yazılımcıların büyük çoğunluğunun meslek hayatında sıfırdan derleyici yazmaması.
- Hazır Araçlar: ANTLR, Lex, Yacc, Bison gibi hazır parser üreteçlerinin yaygın kullanımı.
- Odak Noktası: Sektördeki performans ve sistem sorunlarının otomatlardan ziyade veritabanı veya ağ mimarisi hatalarından kaynaklanması.
2.10.2 Mühendislik Savunması
Hesaplama Sınırları ve Karmaşıklık
- Çözülemezlik Sınırları: Durma Problemi (Halting Problem) ve çözülemezlik (undecidability) kavramını bilerek imkansız algoritmalar yazmaktan kaçınma.
- Problem Karmaşıklığı: NP-Hard / NP-Complete problemleri tanıyıp imkansız kesin çözümler yerine sezgisel (heuristic) yöntemlere yönelme.
2.10.3 Mühendislik Savunması
Sistem Mimarisi, Güvenlik ve Kalıcı Teorik Temel
Sistem Mimarisi: Oyun döngüleri, ağ protokolleri ve durum tabanlı mikroservis tasarımında Sonlu Durum Makineleri (FSM).
Yazılım Güvenliği: Güvenli parser tasarımı ve Regex çalışma mantığını bilerek ReDoS (Regular Expression Denial of Service) açıklarını engelleme.
Teorinin Kalıcılığı: Programlama dilleri ve kütüphaneler eskir; ancak otomatlar ve hesaplama kuramının matematiksel temeli değişmez.
Turing machines/complete
2.11 Otomatlar Hiyerarşisi Karşılaştırması ve Genel Kuram Özeti**
2.11.1 Chomsky Hiyerarşisi ve Bellek Yapıları
- Otomatların geçici bellek kapasitesi ve belleğe erişim esnekliğine göre sınıflandırılması.
- Bellek kapasitesi ve erişim gücü arttıkça otomatın tanıdığı dil kümesinin genişlemesi.
2.11.2 Hiyerarşinin Seviyeleri ve Soyut Makineler
Tip-3 (Sonlu Otomat - FA): Harici belleği yoktur; yalnızca mevcut durumu tutar; Düzenli Dilleri tanır.
Tip-2 (Yığınlı Otomat - PDA): Stack (LIFO) belleğe sahiptir; Bağlamdan Bağımsız Dilleri (CFL) tanır.
Tip-1 (Doğrusal Sınırlı Otomat - LBA): Girdi boyutuyla sınırlı şerit bellek kullanır; Bağlama Duyarlı Dilleri (CSL) tanır.
Tip-0 (Turing Makinesi - TM): Sonsuz RAM / Şerit belleğe sahiptir; genel hesaplama modelidir.
2.11.3 Otomatlar Hiyerarşisi Karşılaştırma Tablosu
| Özellik / Makine | Finite Automata (FA)(Sonlu Otomat) | Pushdown Automata (PDA)(Yığıtlı Otomat) | Linear Bounded Automata (LBA)(Doğrusal Sınırlı Otomat) | Turing Machines (TM)(Turing Makinesi) |
|---|---|---|---|---|
| Chomsky Seviyesi | Tip-3 | Tip-2 | Tip-1 | Tip-0 |
| Geçici Bellek Türü | Yok (Sadece durum/state tutar) | Stack (Yığıt) | Sınırlı Şerit (Girdi boyutuyla sınırlı) | Sonsuz RAM / Şerit (Sonsuz Rastgele Erişim) |
| Bellek Erişim Yöntemi | Erişim yok LIFO (Son Giren İlk Çıkar: Push / Pop) | Sınırlı alan içerisinde Oku / Yaz & Sola / Sağa Hareket | Şerit boyunca serbest Oku / Yaz & Sola / Sağa Hareket | |
| Hesaplama Gücü | En Düşük | Orta | Yüksek | En Yüksek (En genel hesaplama modeli) |
| Tanıdığı Dil Türü | Düzenli Diller (Regular Languages) | Bağlamdan Bağımsız Diller (Context-Free - CFL) | Bağlama Duyarlı Diller (Context-Sensitive) | Doğrulanabilir Diller (Recursively Enumerable) |
| İlişkili Gramer | Düzenli Gramer (Regular Grammar) | Context-Free Grammar (CFG) | Context-Sensitive Grammar | Kısıtsız Gramer (Unrestricted Grammar) |
| Örnek Tanıdığı Dil / Yapı | Metin arama, \(a^* b^*\) biçimindeki dizilimler | \(a^n b^n\) (Eşit sayıda \(a\) ve \(b\)) | \(a^n b^n c^n\) (Üçlü eşitlikler) | Her türlü algoritmik problem |