TÜRKÇE
ENGLISH
Information
| Code | CEN343 |
| Name | Theory of Computation |
| 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 Goal
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 | ||