ECTS - Fundamentals of the Theory of Computation
Fundamentals of the Theory of Computation (CMPE572) Course Detail
| Course Name | Course Code | Season | Lecture Hours | Application Hours | Lab Hours | Credit | ECTS |
|---|---|---|---|---|---|---|---|
| Fundamentals of the Theory of Computation | CMPE572 | Area Elective | 3 | 0 | 0 | 3 | 5 |
| Pre-requisite Course(s) |
|---|
| N/A |
| Course Language | English |
|---|---|
| Course Type | Elective Courses |
| Course Level | Natural & Applied Sciences Master's Degree |
| Mode of Delivery | Face To Face |
| Learning and Teaching Strategies | Lecture, Discussion, Question and Answer, Brain Storming. |
| Course Lecturer(s) |
|
| Course Objectives | The goal of the course is to give students an insight about fundamental aspects of computer science in the context of computability and complexity theories. |
| Course Learning Outcomes |
The students who succeeded in this course;
|
| Course Content | Models of computation, Church-Turing thesis, decidability and undecidability, recursive enumerability, time complexity, classes P and NP, space complexity, LOGSPACE, PSPACE-completeness. |
Weekly Subjects and Releated Preparation Studies
| Week | Subjects | Preparation |
|---|---|---|
| 1 | Introduction | Chapter 0 of Course Book |
| 2 | Turing Machines: The Definition, Alternative definitions, Hilbert's Tenth Problem, Church Turing Thesis | Chapter 3 of Course Book |
| 3 | Turing Machines: The definition, Alternative definitions, Hilbert's Tenth Problem, Church Turing Thesis | Chapter 3 of Course Book |
| 4 | Decidability: Decidable Languages, Halting Problem | Chapter 4 of Course Book |
| 5 | Decidability: Decidable Languages, Halting Problem | Chapter 4 of Course Book |
| 6 | Reducibility: Undecidable Problems, Mapping Reducibility | Chapter 5 of Course Book |
| 7 | MIDTERM I | |
| 8 | Recursion Theorem | Chapter 6 of Course Book |
| 9 | Time Complexity: Measuring Complexity, Class P, Class NP | Chapter 7 of Course Book |
| 10 | Time Complexity: Measuring Complexity, Class P, Class NP | Chapter 7 of Course Book |
| 11 | MIDTERM II | |
| 12 | Time Complexity: NP-Completeness | Chapter 7 of Course Book |
| 13 | Space Complexity: Savitch's Theorem, Class P-Space | Chapter 8 of Course Book |
| 14 | PAPER PRESENTATION and DISCUSSIONS |
Sources
| Course Book | 1. M. Sipser, “Introduction to the Theory of Computation”, (2nd Edition), Thomson Course Technology, 2006, ISBN-13:978-0-619-21764-8. |
|---|---|
| Other Sources | 2. E. Rich, “Automata, Computability and Complexity: Theory and Applications”, (1st Edition), Pearson/Prentice Hall, 2007, ISBN-13: 978-0132288064. |
| 3. J.E. Hopcroft, R. Motwani and J.D. Ullman, "Introduction to Automata Theory, Languages, and Computation", (2nd Edition), Addison Wesley, 2001, ISBN 0-201-44124-1. |
Evaluation System
| Requirements | Number | Percentage of Grade |
|---|---|---|
| Attendance/Participation | - | - |
| Laboratory | - | - |
| Application | - | - |
| Field Work | - | - |
| Special Course Internship | - | - |
| Quizzes/Studio Critics | - | - |
| Homework Assignments | - | - |
| Presentation | - | - |
| Project | - | - |
| Report | - | - |
| Seminar | 1 | 10 |
| Midterms Exams/Midterms Jury | 2 | 50 |
| Final Exam/Final Jury | 1 | 40 |
| Toplam | 4 | 100 |
| Percentage of Semester Work | |
|---|---|
| Percentage of Final Work | 100 |
| Total | 100 |
Course Category
| Core Courses | X |
|---|---|
| Major Area Courses | |
| Supportive Courses | |
| Media and Managment Skills Courses | |
| Transferable Skill Courses |
The Relation Between Course Learning Competencies and Program Qualifications
| # | Program Qualifications / Competencies | Level of Contribution | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | An ability to apply knowledge of mathematics, science, and engineering. | X | ||||
| 2 | An ability to design and conduct experiments, as well as to analyse and interpret data. | X | ||||
| 3 | An ability to design a system, component, or process to meet desired needs. | |||||
| 4 | An ability to function on multi-disciplinary domains. | |||||
| 5 | An ability to identify, formulate, and solve engineering problems. | X | ||||
| 6 | An understanding of professional and ethical responsibility. | |||||
| 7 | An ability to communicate effectively. | |||||
| 8 | Recognition of the need for, and an ability to engage in life-long learning. | |||||
| 9 | A knowledge of contemporary issues. | |||||
| 10 | An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice. | |||||
| 11 | Skills in project management and recognition of international standards and methodologies | |||||
| 12 | An ability to produce engineering products or prototypes that solve real-life problems. | |||||
| 13 | Skills that contribute to professional knowledge. | |||||
| 14 | An ability to make methodological scientific research. | |||||
| 15 | An ability to produce, report and present an original or known scientific body of knowledge. | |||||
| 16 | An ability to defend an originally produced idea. | |||||
ECTS/Workload Table
| Activities | Number | Duration (Hours) | Total Workload |
|---|---|---|---|
| Course Hours (Including Exam Week: 16 x Total Hours) | 14 | 3 | 42 |
| Laboratory | |||
| Application | |||
| Special Course Internship | |||
| Field Work | |||
| Study Hours Out of Class | 14 | 2 | 28 |
| Presentation/Seminar Prepration | 1 | 20 | 20 |
| Project | |||
| Report | |||
| Homework Assignments | |||
| Quizzes/Studio Critics | |||
| Prepration of Midterm Exams/Midterm Jury | 2 | 10 | 20 |
| Prepration of Final Exams/Final Jury | 1 | 15 | 15 |
| Total Workload | 125 | ||