The course develops the concept of computation and of the machine needed to perform them. The principal question is : «what can we compute or cannot compute with this or that computational device(s)».
Table of contents:
(General introduction, Three central model of computation, Symbolic model of computation).
Part (1) Regular grammars, finite automata, Equivalence of deterministic and non-deterministic automata, Closure theorems, Pumping lemma, Myhill-Nerode theorem, Recognizability of automata properties, Regular expressions.
Part (2) Context free grammaras and stack automata, deterministic versions, Chomsky normal form, Recognizability of stack-automata properties, Pumping lemma and closure properties.
Part (3) Turing machines and other models of computation, Unsolvability, Rice theorem, Gödel theorem.
Learning Outcomes:
The course is "concept-oriented", and focuses on the concepts that constitute the theory of computation and led to the development of the relevant technology.
The competences we seek to develop are the following:
Knowledge: master the basic concepts of computation theory: alphabets, languages, virtual machines, syntax and semantics.
Understanding: recognize computational processes as finite processes with a beginning, steps and termination, driven by clear and finite instructions.
Synthesis: be able to define and manipulate formal (symbolic) languages, especially simple forms (smooth and discontextual) and integrate simple computational problems into the above basic language categories.
Analysis: be able to handle standard language analysis tools (transition diagrams, syntactic analysis, syntax trees).
Student Performance Evaluation
Specific details on grading can be found on the course’ s website
The courses of the Computer Science Department are designated with the letters "CS" followed by three decimal digits. The first digit denotes the year of study during which students are expected to enroll in the course; the second digit denotes the area of computer science to which the course belongs.
First Digit
Advised Year of Enrollment
1,2,3,4
First, Second, Third and Fourth year
5,6
Graduate courses
7,8,9
Specialized topics
Second Digit
Computer Science Area
0
Introductory - General
1
Background (Mathematics, Physics)
2
Hardware Systems
3
Networks and Telecommunication
4,5
Software Systems
6
Information Systems
7
Computer Vision and Robotics
8
Algorithms and Theory of Computation
9
Special Projects
The following pages contain tables (one for each course category) summarizing courses offered by the undergraduate studies program of the Computer Science Department at the University of Crete. Courses with code-names beginning with "MATH" or "PHYS" are taught by the Mathematics Department and Physics Department respectively at the University of Crete.