TÜRKÇE
ENGLISH
Information
| Unit | FACULTY OF ENGINEERING |
| COMPUTER ENGINEERING PR. (ENGLISH) | |
| Code | CEN343 |
| Name | Theory of Computation |
| Term | 2020-2021 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 |
| Label | C Compulsory |
| Mode of study | Uzaktan Öğretim |
| Catalog Information Coordinator | Prof. Dr. UMUT ORHAN |
| Course Instructor |
Prof. Dr. UMUT ORHAN
(Güz)
(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
Resources
Notes
Course Learning Outcomes
| Order | Course Learning Outcomes |
|---|---|
| LO01 | Knows Chomsky hierarchy |
| LO02 | Knows Regular languages |
| LO03 | Knows Context free languages |
| LO04 | Knows Turing machines |
| LO05 | Knows Decidability |
| LO06 | Knows P, NP and NP-complete languages |
Relation with Program Learning Outcome
| Order | Type | Program Learning Outcomes | Level |
|---|---|---|---|
| PLO01 | Bilgi - Kuramsal, Olgusal | Adequate knowledge of mathematics, science and related engineering disciplines; ability to use theoretical and applied knowledge in these fields in solving complex engineering problems. | 4 |
| PLO02 | Bilgi - Kuramsal, Olgusal | Ability to identify, formulate and solve complex engineering problems; ability to select and apply appropriate analysis and modeling methods for this purpose. | 5 |
| PLO03 | Bilgi - Kuramsal, Olgusal | Ability to design a complex system, process, device or product to meet specific requirements under realistic constraints and conditions; ability to apply modern design methods for this purpose. | |
| PLO04 | Bilgi - Kuramsal, Olgusal | Ability to select and use modern techniques and tools necessary for the analysis and solution of complex problems encountered in engineering practice; ability to use information technologies effectively. | |
| PLO05 | Bilgi - Kuramsal, Olgusal | Ability to design and conduct experiments, collect data, analyze and interpret results to investigate complex engineering problems or discipline-specific research topics. | |
| PLO06 | Bilgi - Kuramsal, Olgusal | Ability to work effectively in interdisciplinary and multidisciplinary teams; individual working skills. | |
| PLO07 | Bilgi - Kuramsal, Olgusal | Ability to communicate effectively verbally and in writing; knowledge of at least one foreign language; ability to write effective reports and understand written reports, prepare design and production reports, make effective presentations, and give and receive clear and understandable instructions. | |
| PLO08 | Bilgi - Kuramsal, Olgusal | Awareness of the necessity of lifelong learning; ability to access information, follow developments in science and technology, and constantly renew oneself. | |
| PLO09 | Bilgi - Kuramsal, Olgusal | Knowledge of ethical principles, professional and ethical responsibility, and standards used in engineering practice. | |
| PLO10 | Bilgi - Kuramsal, Olgusal | Knowledge of business practices such as project management, risk management and change management; awareness of entrepreneurship and innovation; knowledge of sustainable development. | |
| PLO11 | Bilgi - Kuramsal, Olgusal | Knowledge of the effects of engineering practices on health, environment and safety in universal and social dimensions and the problems of the age reflected in the field of engineering; awareness of the legal consequences of engineering solutions. |
Week Plan
| Week | Topic | Preparation | Methods |
|---|---|---|---|
| 1 | Discrete Mathematical Structures review | Reading related chapter in lecture notes | |
| 2 | Deterministic Finite Automata (DFA) and Non-Deterministic Finite Automata (NFA) | Reading related chapter in lecture notes | |
| 3 | NFA to DFA, Regular Expressions | Reading related chapter in lecture notes | |
| 4 | DFA to Regular Expression, Pumping Lemma for Regular Languages | Reading related chapter in lecture notes | |
| 5 | Context-Free Grammars, Chomsky Normal Form | Reading related chapter in lecture notes | |
| 6 | Push-Down Automata | Reading related chapter in lecture notes | |
| 7 | Pumping Lemma for Context-Free Languages | Reading related chapter in lecture notes | |
| 8 | Midterm Exam | Study to lecture notes and apllications | |
| 9 | Turing Machines, Church-Turing Thesis | Reading related chapter in lecture notes | |
| 10 | Non-Deterministic Turing Machines | Reading related chapter in lecture notes | |
| 11 | Decidable and Undecidable Languages | Reading related chapter in lecture notes | |
| 12 | Enumerability and Enumarable Languages | Reading related chapter in lecture notes | |
| 13 | Introduction to Complexity Theory, P and NP classes | Reading related chapter in lecture notes | |
| 14 | Non-Deterministic algorithms, NP-Complete Languages | Reading related chapter in lecture notes | |
| 15 | Review for final exam | Reading related chapter in lecture notes | |
| 16 | Final Exam | Study to lecture notes and apllications | |
| 17 | Final Exam | Study to lecture notes and apllications |
Assessment (Exam) Methods and Criteria
| Assessment Type | Midterm / Year Impact | End of Term / End of Year Impact |
|---|---|---|
| 1. Midterm Exam | 100 | 40 |
| General Assessment | ||
| Midterm / Year Total | 100 | 40 |
| 1. Final Exam | - | 60 |
| Grand Total | - | 100 |
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 | ||