Description:

This course is an introductory course to the theory of computation for undergraduate students. It covers the following topics:

• Alphabets and languages.
• Finite automata. Properties of finite automata and their accepting languages. Regular expressions and regular languages. Equivalence of finite automata and regular expressions.
• Grammars and the Chomsky hierarchy. Context-free languages.
• Pushdown automata and the pumping lemma for context-free languages. Equivalence of context-free grammars and pushdown automata.
• The notion of computability. Turing Machines.
• Decidable and enumerable languages. Church-Turing thesis. Solvable and non-solvable problems.
• Introduction to computational complexity. 
• Reduction and completeness. Non-determinism and NP-completeness, P vs. NP.

Aims – Learning Outcomes

This course aims to introduce students to the concept of computation and the basic models of computation.

Upon successful completion of this course, the students will be able to:

• Understand in depth the concept of computation and computability.
• Familiarize themselves with the simplest models of computation, such as finite automata (deterministic and nondeterministic) and pushdown automata.
• Become acquainted grammars and, particularly, context-free grammars.
• Make a first foray into Turing Machines and complexity classes such as P, ΝΡ, PSPACE, and the notion of NP-completeness.

Syllabus

Week #1: Alphabets and languages.

Week #2: Finite state automata.

Week #3: Properties of finite automata and properties of the languages they accept.

Week #4: Regular expressions and regular languages. Equivalence of finite automata and regular expressions.

Week #5: The pumping lemma for regular languages.

Week #6: Grammars and the Chomsky hierarchy. Context-free languages.

Week #7: Pushdown automata and the equivalence of context-free grammars and pushdown automata.

Week #8: The pumping lemma for context-free languages.

Week #9: The notion of computability. Turing Machines. Decidable and enumerable languages.

Week #10: Church-Turing thesis. Solvable and non-solvable problems. The halting problem.

Week #11: Introduction to computational complexity. Time complexity, the P class, the Cook-Karp thesis.

Week #12: Reduction and completeness. Non-determinism and NP-completeness, P vs. NP.

Week #13: Space complexity, the PSPACE class and PSPACE-complete problems.

• “Εισαγωγή στη Θεωρία Υπολογισμού”, Sipser Michael, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN 978-960-524-558-0, 2019
• “Στοιχεία θεωρίας υπολογισμού”, Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Εκδόσεις Κριτική ΑΕ, ISBN 978-960-218-397-7, 2005

Educational and learning methods:

• Face to face lectures
• The learning process is supported through the Ionian University e-learning platform (https://opencourses.ionio.gr/courses/DDI188/)

Evaluation methods:

• Written examination (problem solving), 100% of the final grade.
• The grading terms are stated explicitly on the course website.