Bilgi Paketi
baskent.edu.tr

Bilgisayar Mühendisliği Programı (İngilizce)

CSE328

AUTOMATA THEORY

Ders Kodu
CSE328
Yarıyıl
-
Teori+Uygulama
3 + 0
AKTS
5
Dersin TürüSeçmeli
Dersin DüzeyiLisans
Dersin Yılı-
Dersin Yarıyılı-
AKTS5
Öğretim Eleman(lar)ı
Öğrenme Kazanımları

Bu dersin sonunda öğrenciler;

  1. Otomata Teorisi, Hesaplama kuramı ve Biçimsel dillere ilişkin temel kavramları ve modelleri öğrenecekler.
  2. Sonlu durum makineleri, Aşağı itmeli makineler ve Turing makineleri gibi soyut makineler üzerine sorular çözebilecekler.
  3. Biçimsel dillerin; düzenli ifadeler ve biçimsel gramerlerle gösterimlerini öğrenecekler.
  4. Hesaplama sürecinin soyut modellerini anlayacaklar, bu modellerin güçleri ve sınırları hakkında fikir yürütebilecekler.
Veriliş BiçimiYüz Yüze
ÖnkoşullarYok
Önerilen DerslerYok
Ders TanımıOtomata Teorisine giriş. Temel matematiksel kavramlar ve yöntemler. Simgeler, Alfabeler, Dizgiler, Diller, Problemler. Deterministik sonlu durum makineleri. Deterministik olmayan sonlu durum makineleri. Düzenli diller ve ifadeler. Kleene teoremi. Biçimsel gramerler. İçerikten bağımsız diller. Aşağı itmeli özdevinirler. Turing makineleri. Hesaplanabilirlik ve Karar verilebilirlik. Durma problemi, Çözülemez problemler. Karmaşıklık kuramı: P ve NP sınıflar.
Ders İçeriği
HAFTA KONULAR
1. Hafta Otomata Teorisine giriş.
2. Hafta Temel matematiksel kavramlar ve yöntemler.
3. Hafta Simgeler, Alfabeler, Dizgiler, Diller, Problemler.
4. Hafta Deterministik sonlu durum makineleri.
5. Hafta Deterministik olmayan sonlu durum makineleri.
6. Hafta Düzenli diller ve ifadeler.
7. Hafta Kleene teoremi.
8. Hafta Ara-sınav
9. Hafta Biçimsel gramerler.
10. Hafta İçerikten bağımsız diller.
11. Hafta Aşağı itmeli özdevinirler.Turing makineleri.
12. Hafta Hesaplanabilirlik ve Karar verilebilirlik.
13. Hafta Durma problemi, Çözülemez problemler.
14. Hafta Karmaşıklık kuramı: P ve NP sınıflar.
15. Hafta Genel Tekrar
Kaynaklar1. Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages and Computation, 3/E, Addison Wesley, 2006
2. Kelley D., Automata and Formal Languages, Prentice Hall, 1995
3. Sipser M., Introduction to the Theory of Computation, 2/E, Thomson / Course Technology, 2005
Öğretim Yöntemleri
  • Anlatım
  • Soru-Cevap
  • Sunum
  • Rapor Hazırlama
  • Proje
  • Deney
  • Sorun/Problem Çözme
  • Eğitim-Uygulama
Değerlendirme
Sayısı Toplam Katkısı (%)
Ara Sınav 1 30
Ödev 8 10
Mini-Sınav 4 20
Toplam(%) 60
Yıl İçinin Başarıya Oranı(%) 60
Finalin Başarıya Oranı(%) 40
Toplam(%) 100
DilTürkçe
Staj / UygulamaYok

Program Yeterlilikleri / Öğrenme Kazanımları

Ö1 Ö2 Ö3 Ö4
P1 X X X X
P2
P3
P4
P5
P6
P7
P8 X X
P9
P10
P11