| Ders Adı | Kodu | Verildiği Yıl | Verildiği Yarıyıl | Süresi (T+U) | Yerel Kredisi | AKTS Kredisi |
| Hesaplama Teorisi | CENG 611 | | | 3 + 0 | 3 | 7,50 |
| |
| Ders Bilgileri |
| Dersin Öğretim Dili | İngilizce |
| Dersin Seviyesi | Doktora |
| Dersin Türü | Seçmeli |
| Dersin Veriliş Biçimi | Yüz Yüze |
| |
Dersin Öğrenme Kazanımları:
Bu dersi başarı ile tamamlayan öğrenciler: |
| 1. Otomata teorisinin ve biçimsel dillerin temel kavramlarını anlar. |
| 2. Belirli hesaplama problemlerini çözmek için sonlu otomatlar, bağlamdan bağımsız gramerler ve Turing makineleri tasarlar. |
| 3. Problemleri hesaplama karmaşıklıkları açısından analiz eder ve bunları karmaşıklık sınıflarına göre sınıflandırır. |
| 4. Hesaplamalı problemlerin karar verilebilirliğini ve karar verilemezliğini anlar. |
| |
| Dersin Önkoşulları ve Birlikte Alınması Gereken Dersler | Yok |
| Daha Önce Alınmış Olması Önerilen Dersler | Yok |
| |
Dersin Tanımı:
Biçimsel diller ve otomat teorisi, otomat, biçimsel diller, dil bilgisi, hesaplanabilirlik ve karar verilebilirlik kavramlarıyla ilgilenir. Biçimsel Diller ve Otomat Teorisi'ni incelemenin nedenleri şunlardır: Otomat Teorisi, bilgisayar adını verdiğimiz karmaşık makinenin basit ve zarif bir görünümünü sağlar. Otomat Teorisi, bilgisayar sistemlerinin teknolojisi, gelişimi ve yönetiminin sürekli değişen paradigmalarının aksine, yüksek derecede kalıcılığa ve istikrara sahiptir. Dahası, Otomat teorisinin bazı bölümlerinin uygulamaya doğrudan etkisi vardır, örneğin Otomat devre tasarımı, derleyici tasarımı ve arama algoritmaları; Biçimsel Diller ve Dilbilgileri derleyici tasarımı; ve Karmaşıklık üretim, işletme ve yönetimdeki kriptografi ve optimizasyon sorunları. Son olarak, araştırma odaklı öğrenciler bu derste incelenen Otomat teorisinden iyi bir şekilde yararlanacaklardır. |
| |
| Dersin İçeriği (Haftalık Konu Dağılımı): |
| |
| Hafta | Konu |
| 1 | Sonlu Otomata - Deterministik Olmayan Otomatalar |
| 2 | Normal Diller - Düzenli İfadeler |
| 3 | Pumping Lemma |
| 4 | Bağlamdan Bağımsız Dilbilgisi |
| 5 | Turing Makineleri ve Hesaplanabilirlik Teorisi |
| 6 | Karmaşıklık Teorisi |
| 7 | İleri Konular ve Güncel Araştırmalar |
| 8 | Durma probleminin kararsızlığı |
| 9 | İlkel ve kısmi özyinelemeli fonksiyonlar |
| |
| Kaynaklar: |
| John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2007), Introduction to Automata Theory Languages andComputation, 3rdedition, Pearson Education.
J. Glenn Brookshear (1989) Theory of Computation: Formal Languages, Automata, and Complexity, also published by Addison-Wesley, 0805301437AB04062001 |
| |
| Diğer Kaynaklar: |
| K. L. P Mishra, N. Chandrashekaran (2003), Theory of Computer Science-Automata Languages and Computation, Prentice Hall. |
| |
| Öğretim Yöntem ve Teknikleri: |
| Dersler, sınıf içi tartışmalar, problem çözme seansları, ödevler. |
| |
| Değerlendirme Sistemi: |
| Yöntem | Adet | Katkı (%) |
| Ara Sınav | 1 | %30 |
| Final Sınavı | 1 | %30 |
| Ödev | 4 | %40 |
| |
| Ders İşbaşı Eğitimi (iş yerinde eğitim) Gerektiriyor mu? |
| Gerektirmiyor |