Learning Outcomes
Cognitive: The main aim of the course is the students to know the foundations and principles of computer science and to understand the notion of computation and the capabilities/limitations of our computing machines.
Skills: Students are expected to be able to develop formally defined and mathematically substantiated reasoning, for the equivalence of mathematical models of computation and for algorithms to compute formal languages of diverse complexity classes and for problems that are not computable.
Course Content (Syllabus)
Introduction, Regular Languages: Regular Expressions and Finite Automata, Context-Free Languages: Grammars and Pushdown Automata, Turing Machines, Undecidability
Keywords
Languages, Grammars, Automata, Undecidability
Course Bibliography (Eudoxus)
1. H.R. Lewis, Χ. Παπαδημητρίου, "Στοιχεία θεωρίας υπολογισμού", 1η έκδοση/2005, Εκδόσεις Κριτική, ISBN: 978-960-218-397-7
Κωδικός Βιβλίου στον Εύδοξο: 11776
2. M. Sipser, "Εισαγωγή στη Θεωρία Υπολογισμού", 1η έκδοση/2009, Εκδόσεις ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, ISBN: 978-960-524-243-5
Κωδικός Βιβλίου στον Εύδοξο: 257
Additional bibliography for study
1. Π. Κατσαρός, "Θεωρία Υπολογισμού και Εφαρμογές", 2015, Αποθετήριο Κάλλιπος, https://repository.kallipos.gr/handle/11419/5744
2. E. Rich, "Automata, Computability and Complexity: Theory and Applications", 1st edition/2007, Prentice Hall, ISBN: 978-0132288064
3. J. E. Hopcroft, R. Motwani, J. D. Ullman, "Introduction to Automata Theory, Languages, and Computation", 3rd edition/2006, Prentice Hall, ISBN: 978-0321455369