Bilgisayar Mühendisliği

CE 315 | Ders Tanıtım Bilgileri

Dersin Adı

Automata Theory and Formal Languages

Kodu	Yarıyıl	Teori (saat/hafta)	Uygulama/Lab (saat/hafta)	Yerel Kredi	AKTS
CE 315	FALL	3	2	4	7

Ön-Koşul(lar)	CE 215 To Succeed (To get a grade of at least DD)
Dersin Dili	English
Dersin Türü	Zorunlu
Dersin Düzeyi	Lisans
Dersin Veriliş Şekli	Face-To-Face
Dersin Öğretim Yöntem ve Teknikleri	Discussion Problem Solving Q&A Critique Lecture / Presentation
Ulusal Meslek Sınıflandırma Kodu	-
Dersin Koordinatörü	Dr. Öğr. Üyesi Alper Demir
Öğretim Eleman(lar)ı	Dr. Öğr. Üyesi Alper Demir
Yardımcı(ları)	Araş. Gör. Melek Büşra Temuçin

Dersin Amacı

The aim of this course is to introduce automata theory and formal languages, which are one step more abstract than existing programming languages. Fundamental models of computation that form the basis for various branches of computer science, such as compiler design and software engineering, will be presented. At the end of the course, all students are expected to have mastered all these concepts from an engineering perspective.

Öğrenme Çıktıları

Bu dersi başarıyla tamamlayabilen öğrenciler;

Ad	Açıklama	PC Alt	* Katkı Düzeyi
Ad	Açıklama	PC Alt	1	2	3	4	5
LO1	Will be able to map the Chomsky language hierarchy to the corresponding automata and grammar types,						X
LO2	Will be able to trace a given automata or grammar,					X
LO3	Will be able to translate a given automaton or grammar into another equivalent form,				X
LO4	Design an automata or grammar for a given language,					X
LO5	Will be able to use LR(k) parsers for efficient processing of context-insensitive languages,			X
LO6	Will be able to define the concepts of polynomial time, non-deterministic polynomial time, NP-completeness, decidability and undecidability.			X

Ders Tanımı

In this course, the most fundamental theories of computer science will be covered, including regular expressions and context-free languages, finite and pushdown automata, Turing machines, computability, undecidability and problem complexity.

Dersin İlişkili Olduğu Sürdürülebilir Kalkınma Amaçları

Dersin Kategorisi	Temel Ders	X
	Uzmanlık/Alan Dersleri
	Destek Dersleri
	İletişim ve Yönetim Becerileri Dersleri
	Aktarılabilir Beceri Dersleri

HAFTALIK KONULAR VE İLGİLİ ÖN HAZIRLIK ÇALIŞMALARI

Hafta	Konular	Ön Hazırlık	Öğrenme Çıktısı
1	Deterministic Finite Automata	Chapter 1. Sections 1.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO1
2	Deterministic Finite Automata	Chapter 1. Sections 1.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO2
3	Nondeterministic finite automata	Chapter 1. Sections 1.2. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO4
4	Nondeterministic finite automata	Chapter 1. Sections 1.2. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO2
5	Regular Expressions	Chapter 1. Sections 1.3. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO3
6	Context-free Grammars	Chapter 2. Sections 2.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO1
7	Context-free Grammars	Chapter 2. Sections 2.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO4
8	Pushdown Automata	Chapter 2. Sections 2.2. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO2
9	Pushdown Automata	Chapter 2. Section 2.3.. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO3
10	Pushdown Automata	Chapter 2. Section, 2.4. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO5
11	Turing Machines	Chapter 3. Sections 3.1. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO1
12	Turing Machines	Chapter 3. Sections 3.2, 3.3. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO3
13	Complexity classes P, NP, and NP complete	Chapter 7. Sections 7.1-- 7.4. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO6
14	Decidability and undecidability	Chapter 4. Introduction to the theory of computation. Michael Sipser. ISBN 053494728X	LO6
15	Review of the Semester		-
16	Final Exam		-

Ders Kitabı	Introduction to the theory of computation. 3rd Edition. Michael Sipser. ISBN 113318779X.
Önerilen Okumalar/Materyaller	https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/

DEĞERLENDİRME ÖLÇÜTLERİ

Yarıyıl Aktiviteleri	Sayı	Katkı Payı %	LO1	LO2	LO3	LO4	LO5	LO6
Küçük Sınav / Stüdyo Kritiği	4	20	X	X	X	X	X	X
Ödev	1	10	X	X	X	X	X	X
Ara Sınav	1	30	X	X	X	X
Final Sınavı	1	40	X	X	X	X	X	X
Toplam	7	100

AKTS / İŞ YÜKÜ TABLOSU

Yarıyıl Aktiviteleri	Sayı	Süre (Saat)	İş Yükü
Katılım	-	-	-
Teorik Ders Saati	16	3	48
Laboratuvar / Uygulama Ders Saati	16	2	32
Sınıf Dışı Ders Çalışması	14	5	70
Arazi Çalışması	-	-	-
Küçük Sınav / Stüdyo Kritiği	4	3	12
Portfolyo	-	-	-
Ödev	2	5	10
Sunum / Jüri Önünde Sunum	-	-	-
Proje	-	-	-
Seminer/Çalıştay	-	-	-
Sözlü Sınav	-	-	-
Ara Sınavlar	1	20	20
Final Sınavı	1	20	20
		Toplam	212