|
Overview
The
goal of this course is to provide the student with a solid knowledge of
the fundamental concepts and methods of the theory of computation as well
as to outline modern research directions. Three different approaches for
capturing the idea of computing in a formal mathematical way will
be discussed finite state machines, grammars and recursive functions.
At the end of the course students are expected to be able to interpret
relate and apply the basic concepts of the theory of computation to problems
from different areas of computer science.
Course Objectives
-
Apply the algebra of theoretical machines to computing
problems
-
Possess knowledge of non-determinism in computational
models.
-
Remove nondeterminism from simple models when it
is possible.
-
Understand the basic problems of computability,
decidability and the halting problem as well as the relationships
among them.
-
Apply the concept of a Turing machine to the decidability
problem where possible.
-
Understand the Church-Turing Thesis and its significance
in computer science.
-
Have a working knowledge of the Chomsky hierarchy
of languages.
-
Relate theoretical computer science topics to programming
languages and other recursively enumerable sets.
Prerequisites
Textbook
Grading
References
-
1-
H. R. Lewis, C. H. Papadimitriou "Elements of the Theory of Computation"
Prentice Hall, 1981.
-
2-
J.E. Hopcroft, "Introduction to Automata Theory, Languages and Computations" Addison Wesley, 1979.
Assignments
(4rd ed)
|