Ders Planı / THEORY OF COMPUTATION

Ders Bilgileri

Dersin Kredisi 3.0
Dersin AKTS Kredisi 4.0
Dersin Öğretim Dili İngilizce
Dersin Düzeyi Lisans , TYYÇ: 6. Düzey , EQF-LLL: 6. Düzey , QF-EHEA: 1. Düzey
Dersin Türü Zorunlu
Dersin Veriliş Şekli Yüz-Yüze Eğitim
Ders zorunlu veya opsiyonel iş deneyimi gerektiriyor mu ? Z
Dersin Koordinatörü Prof. Dr. RAFET AKDENİZ
Dersi Veren(ler)
Dersin Yardımcıları

Amaç ve İçerik

Dersin Amacı Hesaplama Teorisine Giriş otomata teorisi, resmi gramerler hesaplama teorisi olarak bilinen ve karmaşıklık teorisi, klasik bir giriş.
Dersin İçeriği Genel Tanıtım: Diller, Gramerler, otomata (makineler), Chomsky Hiyerarşisi Uygulamalar. Sonlu Durum Makinaları, Düzenli ifadeler, Düzenli Gramerler, Nondeterminism Sigara düzenli setleri, Pompa Lemma, Düzenli Setleri Karar Algoritmalar.

Haftalık Ders Konuları

1Sonlu Durum Makineleri, Tasarım, Non-determinizm
2Kapanış özellikleri, Düzenli ifadeler, Sonlu Durum Makinelerinde Denklik
3Pumping Lemma-yakınsama özellikleriyle bir dilin düzensizliği
4Düzenli gramerler, FSM'lerin denkliği, Diğer FSM çeşitleri, FSM'lerin minimize edilmesi
5Düzenli kümeler için karar algoritmaları
6Bağlamdışı gramerler, Semantik ve Tümevarımsal Tasarımlar, Örnekler, Uygulamalar
7Chomsky Normal Formu, uygulamalar
8Ara sınav
9Bastırmalı makinalar, CFG karşılıkları
10Lemma pompalama ve içeriksiz serbest kümeler.
11Kapanış özellikleri, DCFL’ler ve kararlı algoritmalar
12Turing Makinesi, Tasarım
13Varyasyonlar ve denklemler: Non-Determinizm, Çoklu bant
14İç içe ve yinelemeli sayılabilir kümeler

Kaynaklar

1-Introduction to the Theory of Computation, Michael Sipser.