ΠΑΝΕΠΙΣΤΗΜΙΟ ΙΩΑΝΝΙΝΩΝ - ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ SITE MAP | uoi ΕΛΛΗΝΙΚΑ | uoi ENGLISH
Theory of Computation

(Undergraduate Course)

 

INSTRUCTOR:
COURSE_ID:
MYY501
WEEKLY HOURS:
3, 2, 0
SEMESTER:
5
COURSE UNITS:
4
ECTS CREDITS:
6.00
YEAR 2018/2019:
YES
PREREQUISITE:
-
DESCRIPTION:
Finite automata and regular expressions, regular languages, closure properties, pumping lemma, algorithms. Determinism, non-determinism. Pushdown automata and context-free grammars, context-free languages, closure properties, pumping lemma, algorithms. Chomsky normal form. Turing machines, equivalence of different models. Recursive and recursively enumerable languages. Church-Turing thesis. Undecidability, the halting problem, Post’s correspondence problem. Classes P and NP.
©2010 DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING - UNIVERSITY OF IOANNINA
created by data|SCIENCE

Valid XHTML 1.0 Strict Valid CSS!

©2010 DEPARTMENT OF style="font-size: 0.1px;">COMPUTER SCIENCE style="font-size: 0.1px;">& ENGINEERING style="font-size: 0.1px;">UNIVERSITY style="font-size: 0.1px;">OF style="font-size: 0.1px;">IOANNINA