TÜRKÇE
ENGLISH
Information
| Code | CENG003 |
| Name | Advanced Theory of Computation |
| Term | 2022-2023 Academic Year |
| Term | Spring |
| Duration (T+A) | 3-0 (T-A) (17 Week) |
| ECTS | 6 ECTS |
| National Credit | 3 National Credit |
| Teaching Language | İngilizce |
| Level | Doktora Dersi |
| Type | Normal |
| Mode of study | Yüz Yüze Öğretim |
| Catalog Information Coordinator | Prof. Dr. UMUT ORHAN |
| Course Instructor |
1 |
Course Goal / Objective
Understand advanced problems about Theory of Computation and create new problems
Course Content
Regular and Context Free Languages, Turing Machines, Decidability, NP-hard problems and reducibility
Course Precondition
none
Resources
Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, Thomson Course Technnology, Boston, 2006.
Notes
1. John Martin. (2010). Introduction to languages and the theory of computation, (4th ed.). New York: McGraw-Hill Science/Engineering/Math. 2. George J. Tourlakis (2012). Theory of computation. Hoboken: Wiley.
Course Learning Outcomes
| Order | Course Learning Outcomes |
|---|---|
| LO01 | Knows basics about Theory of Computation |
| LO02 | Solve applications of Regular and Context Free Languages |
| LO03 | Prepare new Turing problems |
| LO04 | Knows Turing Decidable concept |
| LO05 | Transforms NP-hard problems into each other |
Relation with Program Learning Outcome
| Order | Type | Program Learning Outcomes | Level |
|---|---|---|---|
| PLO01 | Bilgi - Kuramsal, Olgusal | On the basis of the competencies gained at the undergraduate level, it has an advanced level of knowledge and understanding that provides the basis for original studies in the field of Computer Engineering. | 3 |
| PLO02 | Bilgi - Kuramsal, Olgusal | By reaching scientific knowledge in the field of engineering, he/she reaches the knowledge in depth and depth, evaluates, interprets and applies the information. | 3 |
| PLO03 | Yetkinlikler - Öğrenme Yetkinliği | Being aware of the new and developing practices of his / her profession and examining and learning when necessary. | 4 |
| PLO04 | Yetkinlikler - Öğrenme Yetkinliği | Constructs engineering problems, develops methods to solve them and applies innovative methods in solutions. | 4 |
| PLO05 | Yetkinlikler - Öğrenme Yetkinliği | Designs and applies analytical, modeling and experimental based researches, analyzes and interprets complex situations encountered in this process. | 2 |
| PLO06 | Yetkinlikler - Öğrenme Yetkinliği | Develops new and / or original ideas and methods, develops innovative solutions in system, part or process design. | 3 |
| PLO07 | Beceriler - Bilişsel, Uygulamalı | Has the skills of learning. | 4 |
| PLO08 | Beceriler - Bilişsel, Uygulamalı | Being aware of new and emerging applications of Computer Engineering examines and learns them if necessary. | |
| PLO09 | Beceriler - Bilişsel, Uygulamalı | Transmits the processes and results of their studies in written or oral form in the national and international environments outside or outside the field of Computer Engineering. | 3 |
| PLO10 | Beceriler - Bilişsel, Uygulamalı | Has comprehensive knowledge about current techniques and methods and their limitations in Computer Engineering. | |
| PLO11 | Beceriler - Bilişsel, Uygulamalı | Uses information and communication technologies at an advanced level interactively with computer software required by Computer Engineering. | 2 |
| PLO12 | Bilgi - Kuramsal, Olgusal | Observes social, scientific and ethical values in all professional activities. | 2 |
Week Plan
| Week | Topic | Preparation | Methods |
|---|---|---|---|
| 1 | Theory of Computation review | Reading related chapter in lecture notes | Öğretim Yöntemleri: Anlatım |
| 2 | Deterministic and Non-deterministic Finite Automata | 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 | Mid-Term 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-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 | Term Exams | Study to lecture notes and apllications | Ölçme Yöntemleri: Yazılı Sınav |
| 17 | Term Exams | Study to lecture notes and applications | Ö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 | 5 | 70 |
| Assesment Related Works | |||
| Homeworks, Projects, Others | 0 | 0 | 0 |
| Mid-term Exams (Written, Oral, etc.) | 1 | 15 | 15 |
| Final Exam | 1 | 30 | 30 |
| Total Workload (Hour) | 157 | ||
| Total Workload / 25 (h) | 6,28 | ||
| ECTS | 6 ECTS | ||