PAÜ .:. Eğitim Öğretim Bilgi Sistemi

Yazdır

DERS BİLGİLERİ

Ders Kod	Ders Ad	T+U Saat	Yarıyıl	AKTS
CENG 306	BİÇİMSEL DİLLER VE OTOMATA TEORİSİ	3 + 0	6. Yarıyıl	5

DERS TANIMI

Ders Düzeyi	Lisans
Ders Türü	Zorunlu
Dersin Amacı	Bu dersin amacı biçimsel dil teorisinin temelini oluşturan otomatlar, diller, gramerler ve Turing makineleri konusunu öğretmektir. Bilgisayar bilimlerinde bu konular derleyici tasarımı ve bilgisayar dillerinin tanımlanması için temel teşkil eder. Matematikçiler için ise bu konular grup kuramı gibi matematiğin ana çalışma alanlarında giderek önem kazanmaktadır.
Ders İçeriği	Sonlu otomata Teorisi: Düzenli İfadeler, Sonlu Otomata Modelleri, Geçiş Grafları, Kleene's Teoremi, Temel tanımlar, Düzenli ve düzenli olmayan diller, Pumping Lemma ve Sonlu Otomata uygulamaları (Haberleşme Protokol Tasarımı, Sözel Analiz). Yığın Yapılı Otomata Teorisi: Bağlamdan bağımsız gramer ve diller, Parsing, Yığın Yapılı Otomata Modelleri. Turing Teorisi: Turing Makinesi Tasarımı, Turing Makineleri ile Hesaplama.
Ders Ön Koşul	Dersin ön koşulu yok.
Ders Yan Koşul	Dersin yan koşulu yok.
Öğretim Sistemi	Yüz Yüze

DERS ÖĞRENME KAZANIMLARI

1	Dersin temel kavramlarını anlama
2	Sonlu otomataları anlama
3	Yığın yapılı otomataları anlama
4	Dillerin hiyerarşisini anlama
5	Turing makinelerini anlama

DERS ÖĞRENME KAZANIMININ PROGRAM YETERLİLİKLERİNE KATKISI

No	PY 01	PY 02	PY 03	PY 04	PY 05	PY 06	PY 07	PY 08	PY 09	PY 10	PY 11	PY 12
ÖK 001	5	1	1	5	4
ÖK 002	5	1	1	5	4
ÖK 003	5	1	1	5	4
ÖK 004	5	1	1	5	4
ÖK 005	5	1	1	5	4
Ara Toplam	25	5	5	25	20
Katkı	5	1	1	5	4	0	0	0	0	0	0	0

AKTS / İŞ YÜKÜ TABLOSU

Etkinlik	Sayısı	Süresi (Saat)	Toplam İş Yükü (Saat)
Ders Süresi(14 hafta/teorik+uygulama)	14	3	42
Sınıf Dışı Ders Çalışma Süresi(Ön çalışma, pekiştirme)	14	3	42
Arasınavlar(hazırlık süresi dahil)	1	13	13
Yarıyıl Sonu Sınavı(hazırlık süresi dahil)	1	13	13
Rapor / Proje (hazırlık süresi dahil)	1	20	20
Toplam İş Yükü Dersin AKTS Kredisi			130 5

DERS ŞUBELERİ

Dönem seçiniz :

Yazdır

Ders Şube Detayları

Dersin Kodu	Dersin Ad	Saat (T+P)	Şube No	Öğretim Dili	Şube Dönemi
CENG 306	BİÇİMSEL DİLLER VE OTOMATA TEORİSİ	3 + 0	1	Türkçe	2023-2024 Bahar

Öğretim Elemanı	E-Posta	İç Hat	Ders Yeri	Devam Zorunluluğu
Prof. Dr. SEZAİ TOKAT	stokat@pau.edu.tr		MUH B0024	Dersin Devam Yüzdesi : %

Amaç		Bu dersin amacı biçimsel dil teorisinin temelini oluşturan otomatlar, diller, gramerler ve Turing makineleri konusunu öğretmektir. Bilgisayar bilimlerinde bu konular derleyici tasarımı ve bilgisayar dillerinin tanımlanması için temel teşkil eder. Matematikçiler için ise bu konular grup kuramı gibi matematiğin ana çalışma alanlarında giderek önem kazanmaktadır.
İçerik		Sonlu otomata Teorisi: Düzenli İfadeler, Sonlu Otomata Modelleri, Geçiş Grafları, Kleene's Teoremi, Temel tanımlar, Düzenli ve düzenli olmayan diller, Pumping Lemma ve Sonlu Otomata uygulamaları (Haberleşme Protokol Tasarımı, Sözel Analiz). Yığın Yapılı Otomata Teorisi: Bağlamdan bağımsız gramer ve diller, Parsing, Yığın Yapılı Otomata Modelleri. Turing Teorisi: Turing Makinesi Tasarımı, Turing Makineleri ile Hesaplama.

Haftalık Konu Başlıkları

Hafta	Konular
1	Kümeler, ilişkiler ve fonksiyonlar,
2	alfabeler ve diller, alfabelerin sonlu ifadesi
3	Deterministik sonlu otomata,
4	Non-deterministic sonlu otomata,
5	Deterministik ve non-deterministic sonlu otomata,
6	Düzenli ve düzenli olmayan diller, durum indirgeme, pumping lemma
7	Düzenli ve düzenli olmayan diller, durum indirgeme, pumping lemma
8	Push Down Automata
9	MIDTERM
10	Bağlam bağımsız diller,
11	Bağlam bağımsız diller,
12	Turing Makinesi
13	Turing Makinesi, Church-Turing Thesis
14	Hesapmala karmaşıklığı

Materyaller

Materyal belirtilmemiştir.

Kaynaklar

Kaynaklar	Kaynak Dili
H.R. Lewis, C.H. Papadimitriou, Elements of the theory of computation, second edition, Prentice-Hall, 1998.	Türkçe

Ders Değerlendirme Sistemi

Değerlendirme Yöntemi	Katkı Yüzdesi (%)	Değerlendirme Yöntemi Ad
Dönem Sonu Sınavı	60	Dönem Sonu Sınavı
Ara Sınav	40	Ara Sınav

T+U : Teorik + Pratik
PY: Program Yeterlilikleri
ÖK: Ders Öğrenme Kazanımları

Aday Öğrenci