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 advanced knowledge of computing and/or informatics to solve software engineering problems. | X | ||||
| 2 | Develop solutions using different technologies, software architectures and life-cycle approaches. | |||||
| 3 | An ability to design, implement and evaluate a software system, component, process or program by using modern techniques and engineering tools required for software engineering practices. | |||||
| 4 | An ability to gather/acquire, analyze, interpret data and make decisions to understand software requirements. | |||||
| 5 | Skills of effective oral and written communication and critical thinking about a wide range of issues arising in the context of working constructively on software projects. | X | ||||
| 6 | An ability to access information in order to follow recent developments in science and technology and to perform scientific research or implement a project in the software engineering domain. | |||||
| 7 | An understanding of professional, legal, ethical and social issues and responsibilities related to Software Engineering. | |||||
| 8 | Skills in project and risk management, awareness about importance of entrepreneurship, innovation and long-term development, and recognition of international standards of excellence for software engineering practices standards and methodologies. | |||||
| 9 | An understanding about the impact of Software Engineering solutions in a global, environmental, societal and legal context while making decisions. | |||||
| 10 | Promote the development, adoption and sustained use of standards of excellence for software engineering practices. | |||||
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 | ||