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.
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
Code
Computer Science Area
A1
Computer architecture and microelectronics
A2
Computer systems, parallel and high performance computing
A3
Computer security and distributed systems
A4
Computer networks, mobile computing, and telecommunications
B1
Algorithms and systems analysis
B2
Databases, information and knowledge management
B3
Software engineering and programming languages
B4
Artificial Intelligence and machine learning
C1
Signal processing and analysis
C2
Computer vision and robotics
C3
Computer graphics and human-computer interaction
C4
Βioinformatics, medical informatics, and computational neuroscience
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.