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 Ph.D.
Mode of Delivery Face To Face
Learning and Teaching Strategies Lecture, Discussion, Question and Answer, Brain Storming.
Course Coordinator
Course Lecturer(s)
Course Assistants
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;
  • Students are expected to develop their mathematical orientation and capabilities through theorem proving in computer science discipline.
  • Students are expected to learn about one of the fundamental bases of computer science: The Computability Theory.
  • Students are expected to better recognize and position the science and engineering of computer.
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 Comprehends the most advanced technology and literature in the field of software engineering research.
2 Gains the ability to conduct world-class research in software engineering and publish scholarly articles in top conferences and journals in the area.
3 Conducts quantitative and qualitative studies in software engineering.
4 Develops and applies software engineering approaches to acquire the necessary skills to bridge the gap between academia and industry in the field of software engineering and to solve real-world problems.
5 Gains the ability to access the necessary information to follow current developments in science and technology, and to conduct scientific research or develop projects in the field of software engineering.
6 Gains awareness and a sense of responsibility regarding professional, legal, ethical, and social issues in the field of software engineering.
7 Acquires project and risk management skills; gains awareness of the importance of entrepreneurship, innovation, and sustainable development; adapts international excellence standards for software engineering practices and methodologies.
8 Gains awareness of the universal, environmental, social, and legal consequences of software engineering practices when making decisions.
9 Develops, adopts, and supports the sustainable use of excellence standards 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