TÜRKÇE
ENGLISH
Genel Bilgi
| Kod | CEN343 |
| Ad | Theory of Computation |
| Dönem | 2022-2023 Eğitim-Öğretim Yılı |
| Yarıyıl | 5. Yarıyıl |
| Süre (T+U) | 3-0 (T-U) (17 Hafta) |
| AKTS | 5 AKTS |
| Yerel Kredi | 3 Yerel Kredi |
| Eğitim Dil | İngilizce |
| Seviye | Lisans Dersi |
| Tür | Normal |
| Öğretim Şekli | Yüz Yüze Öğretim |
| Bilgi Paketi Koordinatörü | Prof. Dr. UMUT ORHAN |
| Dersin Öğretim Elemanı |
Prof. Dr. UMUT ORHAN
(A Grubu)
(Sor. Öğr. Ele.)
|
Dersin Amacı / Hedefi
Bu derste temel amaç, dil sınıflarını gramer ve otomata açısından tanımlamaktır.
Dersin İçeriği
Chomsky hiyerarşisi, Düzenli diller, İçerikten bağımsız diller, Turing makineleri, Karar-verilebilirlik, P ve NP dilleri, NP-complete diller
Dersin Ön Koşulu
yok
Kaynaklar
Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012.
Notlar
Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, Thomson Course Technnology, Boston, 2006. Introduction to Languages and the Theory of Computation, 4th Edition. John C. Martin, 2011, Mc Graw Hill.
Dersin Öğrenme Çıktıları
| Sıra | Dersin Öğrenme Çıktıları |
|---|---|
| ÖÇ01 | Chomsky hiyerarşisini bilir |
| ÖÇ02 | Düzenli dil problemlerini çözer |
| ÖÇ03 | İçerikten bağımsız dil problemlerini çözer |
| ÖÇ04 | Turing makinelerini bilir ve tasarlar |
| ÖÇ05 | Karar-verilebilirlik kavramını bilir |
| ÖÇ06 | P, NP ve NP-complete problemlerini bilir ve dönüştürür |
Program Öğrenme Çıktıları ile İlişkisi
| Sıra | Tür | Program Öğrenme Çıktıları | Duzey |
|---|---|---|---|
| PÖÇ01 | Bilgi - Kuramsal, Olgusal | 1. Matematik, fen bilimleri ve bilgisayarla ilgili mühendislik konularında yeterli altyapıya sahip olma; bu alanlardaki kuramsal bilgileri beraber kullanabilme | 4 |
| PÖÇ02 | Bilgi - Kuramsal, Olgusal | 2. Karmaşık mühendislik problemlerini saptama, tanımlama, formüle etme ve çözme becerisi; bu amaçla uygun analitik yöntemler ve modelleme tekniklerini seçme ve uygulama | 3 |
| PÖÇ03 | Bilgi - Kuramsal, Olgusal | 3. Karmaşık bir sistemi, sistem bileşenini ya da süreci analiz etme ve istenen gereksinimleri karşılamak üzere gerçekçi kısıtlar altında tasarlama becerisi; bu doğrultuda modern tasarım yöntemlerini uygulama becerisi | 4 |
| PÖÇ04 | Bilgi - Kuramsal, Olgusal | 4. Mühendislik uygulamaları için gerekli olan modern teknik ve araçları geliştirme, seçme ve kullanma becerisi; bilişim teknolojilerini etkin kullanma becerisi | 3 |
| PÖÇ05 | Bilgi - Kuramsal, Olgusal | 5. Karmaşık bilgisayar mühendisliği problemlerin çözümüne ilişkin deney tasarlama, deney yapma, veri toplama, sonuçları analiz etme ve yorumlama becerisi | 4 |
| PÖÇ06 | Bilgi - Kuramsal, Olgusal | Bireysel olarak ve disiplin içi/çok disiplinli takımlarda etkin çalışabilme becerisi, sorumluluk alma ve özgüven | |
| PÖÇ07 | Beceriler - Bilişsel, Uygulamalı | Bilgiye erişebilme, kaynak araştırması yapabilme ve bilgi kaynaklarını kullanabilme becerisi | 3 |
| PÖÇ08 | Beceriler - Bilişsel, Uygulamalı | Yaşam boyu öğrenmenin gerekliliği bilinci; bilim ve teknolojideki gelişmeleri izleme ve kendini sürekli yenileme becerisi | 3 |
| PÖÇ09 | Yetkinlikler - Bağımsız Çalışabilme ve Sorumluluk Alabilme Yetkinliği | 9. Türkçe sözlü ve yazılı etkin iletişim kurma, ve en az bir yabancı dilde teknik yayın okuyup anlayabilme, rapor hazırlama ve sunum yapma becerisi | 4 |
| PÖÇ10 | Yetkinlikler - Öğrenme Yetkinliği | Mesleki ve etik sorumluluk bilinci; mühendislik uygulamalarında kullanılan standartlar hakkında bilgi | 2 |
| PÖÇ11 | Yetkinlikler - Öğrenme Yetkinliği | 11. Proje yönetimi, işyeri uygulamaları, çalışanların sağlığı, çevre ve iş güvenliği, ve mühendislik uygulamalarının hukuksal sonuçları hakkında farkındalık | 3 |
| PÖÇ12 | Yetkinlikler - Öğrenme Yetkinliği | 12. Mühendislik çözümlerinin ve uygulamalarının evrensel ve toplumsal boyutlardaki etkileri, girişimcilik ve yenilikçilik, ve çağın sorunları hakkında bilgi sahibi olmak | 2 |
Haftalık Akış
| Hafta | Konu | Ön Hazırlık | Yöntemler |
|---|---|---|---|
| 1 | Kesikli matematiksel yapılar tekrarı | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 2 | Deterministik sonlu otomata (DFA) ve Deterministik olmayan sonlu otomata (NFA) | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 3 | DFAdan NFAya dönüşüm, Düzenli ifadeler | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 4 | DFA'dan düzenli ifadeye dönüşüm, Düzenli diller için Pumping Lemma | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 5 | İçerik bağımsız gramerler, Chomsky normalizasyonu | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 6 | Push-Down otomata | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 7 | İçerik-bağımsız diller için Pumping Lemma | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 8 | Arasınav | Ders notları ve uygulamalara hazırlanmak | Ölçme Yöntemleri: Yazılı Sınav |
| 9 | Turing makineleri, Church-Turing tezi | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 10 | Deterministik olmayan Turing makineleri | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 11 | Karar-verilebilir ve Karar-verilemez diller | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 12 | Sayılabilirlik ve Sayılabilir diller | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 13 | Karmaşıklık Teorisine giriş, P ve NP sınıfları | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 14 | Deterministik olmayan algoritmalar, NP-bütün diller | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Anlatım |
| 15 | Final sınavı için tekrar | Ders notunun ilgili bölümünü incelemek | Öğretim Yöntemleri: Soru-Cevap |
| 16 | Final Sınavı | Ders notları ve uygulamalara hazırlanmak | Ölçme Yöntemleri: Yazılı Sınav |
| 17 | Final Sınavı | Ders notları ve uygulamalara hazırlanmak | Ölçme Yöntemleri: Yazılı Sınav |
Öğrenci İş Yükü - AKTS
| Çalışmalar | Sayısı | Süresi (Saat) | İş Yükü (Saat) |
|---|---|---|---|
| Ders ile İlgili Çalışmalar | |||
| Ders (Sınav haftaları dahil değildir) | 14 | 3 | 42 |
| Sınıf Dışı Ders Çalışma (Ön çalışma, pekiştirme) | 14 | 3 | 42 |
| Değerlendirmeler ile İlgili Çalışmalar | |||
| Ödev, Proje, Diğer | 0 | 0 | 0 |
| Ara Sınavlar (Yazılı, Sözlü, vs.) | 1 | 12 | 12 |
| Yarıyıl/Yıl Sonu/Final Sınavı | 1 | 18 | 18 |
| Toplam İş Yükü (Saat) | 114 | ||
| Toplam İş Yükü / 25 (s) | 4,56 | ||
| AKTS | 5 AKTS | ||