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; 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.