CS 3002 - Biçimsel Diller ve Otomata Teorisi

Ders Öğretim Planı

Ders Kodu:

CS 3002

Ders Adı:

Biçimsel Diller ve Otomata Teorisi

Dersin Sunulduğu Dil:

İngilizce

Dersin Türü:

Ders

Dersin Derecesi:

Lisans

AKTS:

5.00

Dersin Sorumlusu:

Dr. Naci ER

Dersin Amacı

Bu ders, biçimsel diller, otomatlar, hesaplanabilirlik ve karmaşıklık kavramlarına giriş sağlar. Derste, farklı otomat sınıfları, bu sınıflara karşılık gelen biçimsel diller ve bunların hesaplama ile derleyici tasarımı alanlarındaki uygulamaları ele alınmaktadır.

Dersin İçeriği

Finite State Machines, Nondeterminism, Regular Languages, Regular Expressions, Formal Grammars, Context-free Languages, Push-down Automata,

Ders Kitabı / Malzemesi / Önerilen Kaynaklar

Formal Languages And Automata Theory

Öğrenim Çıktısı

Kod	Açıklama
ÖÇ1	Formal Languages and Automata Theory dersi sonunda öğrenciler, biçimsel dillerin temel kavramlarını tanımlayabilecek, semboller, diziler, alfabeler ve dil sınıfları arasındaki farkları açıklayabilecek düzeye ulaşırlar. Deterministik ve deterministik olmayan sonlu otomatları (DFA ve NFA) modelleyebilir, bu modeller arasında dönüşümler gerçekleştirebilir ve düzenli ifadelerle otomatlar arasındaki ilişkileri kurabilirler. Ayrıca, düzenli olmayan dilleri belirlemek için Pumping Lemma gibi teorik araçları kullanabilirler. Bağlamdan bağımsız dilbilgilerini (CFG) yazabilir, bu dilbilgilerine karşılık gelen dilleri analiz edebilir ve bu dillerin tanınmasında kullanılan yığıtlı otomatları (PDA) tasarlayabilirler. Turing makineleri konusunu öğrenerek hesaplanabilirlik ve karar verilebilirlik problemlerini değerlendirebilirler. Son olarak, karmaşıklık sınıflarını tanıyarak P, NP ve NP-tam problemleri ayırt edebilir ve bu problemlerin çözümüne yönelik temel yaklaşımları kavrayabilirler. Bu öğrenme çıktıları sayesinde öğrenciler, hesaplama kuramının hem teorik temellerini hem de uygulamalarını derinlemesine anlama becerisi kazanırlar.

Kod

Açıklama

ÖÇ1

Formal Languages and Automata Theory dersi sonunda öğrenciler, biçimsel dillerin temel kavramlarını tanımlayabilecek, semboller, diziler, alfabeler ve dil sınıfları arasındaki farkları açıklayabilecek düzeye ulaşırlar. Deterministik ve deterministik olmayan sonlu otomatları (DFA ve NFA) modelleyebilir, bu modeller arasında dönüşümler gerçekleştirebilir ve düzenli ifadelerle otomatlar arasındaki ilişkileri kurabilirler. Ayrıca, düzenli olmayan dilleri belirlemek için Pumping Lemma gibi teorik araçları kullanabilirler. Bağlamdan bağımsız dilbilgilerini (CFG) yazabilir, bu dilbilgilerine karşılık gelen dilleri analiz edebilir ve bu dillerin tanınmasında kullanılan yığıtlı otomatları (PDA) tasarlayabilirler. Turing makineleri konusunu öğrenerek hesaplanabilirlik ve karar verilebilirlik problemlerini değerlendirebilirler. Son olarak, karmaşıklık sınıflarını tanıyarak P, NP ve NP-tam problemleri ayırt edebilir ve bu problemlerin çözümüne yönelik temel yaklaşımları kavrayabilirler. Bu öğrenme çıktıları sayesinde öğrenciler, hesaplama kuramının hem teorik temellerini hem de uygulamalarını derinlemesine anlama becerisi kazanırlar.

Haftalık Ders İçeriği

Hafta	İçerik
1	3
2	3
3	3

İş Yükü Hesaplaması

Bilgi bulunmamaktadır.

Değerlendirme

#	Değerlendirme Tipi	Katkı Yüzdesi (%)
1	midterm	%40
2	final	%60
TOPLAM		%100

PÇ - ÖÇ Matrisi

PÇ \ ÖÇ	ÖÇ1
PÇ-1
PÇ-2
PÇ-3
PÇ-4
PÇ-5
PÇ-6
PÇ-7
PÇ-8
PÇ-9
PÇ-10
PÇ-11

1

Düşük Katkı

2

Orta Katkı

3

Yüksek Katkı

Dersin Eğitim - Öğretim Metodları

#	Yöntem Adı	Faal	Araçlar
1	Ders (anlatım), etkileşimli tartışma	Dinleme, not alma, tekrar etme, derste getirilen eğitim materyalleri üzerinden gösterilenleri uygulama	Standart derslik teknolojileri, çoklu ortam araçları (projektör, bilgisayar, dijital sunumlar)