Dersi Veren Fakülte \ Bölüm
Mühendislik Fakültesi \ Bilgisayar Mühendisliği
Kredi
AKTS
Ders Türü
Öğretim Dili
Bu ders, otomata teorisindeki temel kavramları ve kanıt tekniklerini sunar. İşlenen konular şunlardır: DFA, NFA, düzenli dillerin özellikleri, düzenli ifadeler, düzenli diller için pompalama lemması, bağlam-bağımsız gramerler, Chomsky normal formu, PDA, Turing makineleri, karar verilemezlik, NP-tamamlılık.
Ders Kitapları ve/veya Kaynaklar
Introduction to the Theory of Computation. By Michael Sipser.
Hesaplamanın formal modellerine dair temel anlayış.
Düzenli ifadeleri ve bağlam-bağımsız gramerleri anlama ve yazma.
TM'leri, indirgeme kanıtlarını, ve hesaplamanın sınırlarını anlama.
1. DFA'ları ve NFA'ları tasarlamak ve anlamak
2. Düzenli ifadeler yazmak
3. Bir dilin düzenli olmadığını kanıtlamak
4. CFG'leri ve PDA'ları tasarlamak ve anlamak
5. Bir grameri CNF'ye basitleştirmek
6. Turing makinelerini ve indirgeme ispat tekniğini öğrenmek
1. Hafta: DFA
2. Hafta: NFA
3. Hafta: Düzenli ifadeler
4. Hafta: Pompalama lemması
5. Hafta: Bağlam-bağımsız gramerler
6. Hafta: Bağlam-bağımsız gramerler
7. Hafta: Belirsiz gramerler, CNF
8. Hafta: PDA
9. Hafta: Turing makinaları
10. Hafta: Karar verilemeyen problemler
11. Hafta: Karmaşıklık kuramı
12. Hafta: NP-tam problemler
Referans Değerlendime Ölçütleri
Vize % 35
Final % 35
Quiz % 10
Ödev % 20
|
Program Çıktısı
*
|
| 1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
|
Ders Çıktısı
|
|---|
| 1 |
C
|
|
|
|
|
|
|
|
|
|
|
| 2 |
C
|
|
|
|
|
|
|
|
|
|
|
| 3 |
C, D
|
|
|
|
|
|
|
|
|
|
|
| 4 |
C
|
|
|
|
|
|
|
|
|
|
|
| 5 |
C
|
|
|
|
|
|
|
|
|
|
|
| 6 |
C
|
|
|
|
|
|
|
|
|
|
|