Semester 9

Course: Complexity theory



Course Code: Ε10
Course Level: Undergratuate
Obligatory/Elective: Elective
Semester: 9
Division: Division of Computers
Group: Group A
ECTS Credits: 5
Hours Per Week: 4
Website: eclass.uowm.gr/courses/ICTE160/
Language: Greek
Content:

Problems, algorithms and computational complexity. Turing machines, Non-deterministic Turing machines. Global Turing machines. The position of Church. Recursive functions, computability and incomputability, time and space bounded computation, retrospective and back countable languages, deterministic and non-deterministic time classes and space classes, LOGSPACE, NL, P, NP, PSPACE, etc; Cook-Levin theorem

Learning Outcomes:
  • to understand and design Turing Machines
  • to understand Church’s position
  • to study and perceive computability and incomputability issues
  • to comprehend the terms of time and space bounded computation
  • to study and perceive deterministic time and space classes
  • to study and perceive non-deterministic time and space classes
  • to comprehend the terms of NP, P, NL, PSPACE
Pre-requirements:

-

Teaching Methods:

Lectures, Notes, Exercises

Validation:

Assignment (30% of the total mark) and exams (70% of the total mark)

Suggested Books:
  • SIPSER MICHAEL, ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, 2009
  • Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Στοιχεία θεωρίας υπολογισμού, ΕΚΔΟΣΕΙΣ ΚΡΙΤΙΚΗ, 2005