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 Objectives:
This lesson is concept-oriented. Students are guided to develop the following abilities:
to work and think using properly the basic concepts of the theory of computation.
to be able to define and manipulate formal languages(especially regular and context-free ones).
to classify simple computational problem in the given main classes.
to be able to use the relevant analytical tools (transition diagrams, syntax trees).
Grading:
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.