CEN343 Theory of Computation

5 ECTS - 3-0 Duration (T+A)- 5. Semester- 3 National Credit

Information

Code CEN343
Name Theory of Computation
Term 2022-2023 Academic Year
Semester 5. Semester
Duration (T+A) 3-0 (T-A) (17 Week)
ECTS 5 ECTS
National Credit 3 National Credit
Teaching Language İngilizce
Level Lisans Dersi
Type Normal
Mode of study Yüz Yüze Öğretim
Catalog Information Coordinator Prof. Dr. UMUT ORHAN
Course Instructor Prof. Dr. UMUT ORHAN (A Group) (Ins. in Charge)


Course Goal / Objective

In this course, the main goal is to define the language classes in terms of grammars and automata.

Course Content

Chomsky hierarchy, Regular languages, Context free languages, Turing machines, Decidability, P and NP languages, NP-complete languages

Course Precondition

none

Resources

Introduction to Theory of Computation, Anil Maheshwari and Michiel Smid, Carleton University, 2012.

Notes

Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, Thomson Course Technnology, Boston, 2006. Introduction to Languages and the Theory of Computation, 4th Edition. John C. Martin, 2011, Mc Graw Hill.


Course Learning Outcomes

Order Course Learning Outcomes
LO01 Knows Chomsky hierarchy
LO02 Solve Regular language problems
LO03 Solve context free language problems
LO04 Knows and designs Turing machines
LO05 Knows Decidability concept
LO06 Knows and transforms P, NP and NP-complete problems


Relation with Program Learning Outcome

Order Type Program Learning Outcomes Level
PLO01 Bilgi - Kuramsal, Olgusal Has capability in the fields of mathematics, science and computer that form the foundations of engineering 4
PLO02 Bilgi - Kuramsal, Olgusal Identifies, formulates, and solves engineering problems, selects and applies appropriate analytical methods and modeling techniques, 3
PLO03 Bilgi - Kuramsal, Olgusal Analyzes a system, its component, or process and designs under realistic constraints to meet the desired requirements,gains the ability to apply the methods of modern design accordingly. 4
PLO04 Bilgi - Kuramsal, Olgusal Ability to use modern techniques and tools necessary for engineering practice and information technologies effectively. 3
PLO05 Bilgi - Kuramsal, Olgusal Ability to design and to conduct experiments, to collect data, to analyze and to interpret results 4
PLO06 Bilgi - Kuramsal, Olgusal Has ability to work effectively as an individual and in multi-disciplinary teams, take sresponsibility and builds self-confidence
PLO07 Beceriler - Bilişsel, Uygulamalı Can access information,gains the ability to do resource research and uses information resources 3
PLO08 Beceriler - Bilişsel, Uygulamalı Awareness of the requirement of lifelong learning, to follow developments in science and technology and continuous self-renewal ability 3
PLO09 Yetkinlikler - Bağımsız Çalışabilme ve Sorumluluk Alabilme Yetkinliği Ability to communicate effectively orally and in writing, and to read and understand technical publications in at least one foreign language 4
PLO10 Yetkinlikler - Öğrenme Yetkinliği Professional and ethical responsibility, 2
PLO11 Yetkinlikler - Öğrenme Yetkinliği Awareness about project management, workplace practices, employee health, environmental and occupational safety, and the legal implications of engineering applications, 3
PLO12 Yetkinlikler - Öğrenme Yetkinliği Becomes aware of universal and social effects of engineering solutions and applications, entrepreneurship and innovation, and knowledge of contemporary issues 2


Week Plan

Week Topic Preparation Methods
1 Discrete Mathematical Structures review Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
2 Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
3 NFA to DFA, Regular Expressions Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
4 DFA to Regular Expression, Pumping Lemma for Regular Languages Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
5 Context-Free Grammars, Chomsky Normal Form Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
6 Push-Down Automata Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
7 Pumping Lemma for Context-Free Languages Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
8 Midterm Exam Study to lecture notes and apllications Ölçme Yöntemleri:
Yazılı Sınav
9 Turing Machines, Church-Turing Thesis Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
10 Non-Deterministic Turing Machines Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
11 Decidable and Undecidable Languages Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
12 Enumerability and Enumarable Languages Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
13 Introduction to Complexity Theory, P and NP classes Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
14 Non-Deterministic algorithms, NP-Complete Languages Reading related chapter in lecture notes Öğretim Yöntemleri:
Anlatım
15 Review for final exam Reading related chapter in lecture notes Öğretim Yöntemleri:
Soru-Cevap
16 Final Exam Study to lecture notes and apllications Ölçme Yöntemleri:
Yazılı Sınav
17 Final Exam Study to lecture notes and apllications Ölçme Yöntemleri:
Yazılı Sınav


Student Workload - ECTS

Works Number Time (Hour) Workload (Hour)
Course Related Works
Class Time (Exam weeks are excluded) 14 3 42
Out of Class Study (Preliminary Work, Practice) 14 3 42
Assesment Related Works
Homeworks, Projects, Others 0 0 0
Mid-term Exams (Written, Oral, etc.) 1 12 12
Final Exam 1 18 18
Total Workload (Hour) 114
Total Workload / 25 (h) 4,56
ECTS 5 ECTS

Update Time: 22.11.2022 09:56