-
WWW http://www.cs.kent.edu/~dragan/CS6-76202-ThComp.html
-
Course Description
This is a graduate level course. We will cover the following
topics.
Finite state automata (overview): Deterministic
and nondeterministic finite state machines; regular expressions and
languages. Techniques for identifying and describing regular languages;
techniques for showing that a language is not regular. Properties of such
languages.
Contextfree languages (overview): Contextfree
grammars, parse trees, derivations and ambiguity. Relation to pushdown
automata. Properties of such languages and techniques for showing that
a language is not contextfree.
Turing Machines: Basic definitions and relation
to the notion of an algorithm or program. Power of Turing Machines and
Church’s hypothesis.
Undecidability: Recursive and recursively enumerable
languages. Universal Turing Machines. Limitations on our ability to compute;
undecidable problems.
Computational Complexity: Decidable problems for
which no “efficient” algorithms are known. Polynomial time computability.
The notion of NP-completeness and problem reductions. Examples of “hard”
problems. Lower bounds in computational complexity.
-
Prerequisites
Introduction to Theory of Automata, Formal Languages,
Computation - CS 4/56201, Design & Analysis of Algorithms
- CS 4/56101
-
Texts
-
Michael Sipser, Introduction to the Theory of Computation,
PWS Publishing, Boston 1997. ( Errata)
(order on-line)
-
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman,
Introduction
to Automata Theory, Languages, and Computation, 2/e. Addison-Wesley,
2001.
-
Christos H. Papadimitriou, Computational Complexity,
Addison-Wesley,
1994. ( Errata)
-
Motivation and Overview ( by Rajeev Motwani )
"I have been told by past students that this is one of
the more difficult courses in the Computer Science curriculum, but at the
same time they enjoyed it the most. Keep this in mind when the going gets
tough! The reason for the difficulty is that it covers abstract and mathematical
topics which are not very easy to grasp without putting in a good deal
of hard work. There are a number of excellent reasons for becoming proficient
with the theoretical tools that we will develop in this course.
1. Most of what you learn in the first part of the course
will be required in the design or analysis of almost any reasonably complex
software or hardware system. For example, the theory of finite state machines
and regular expressions is needed for the design of switching circuits,
components of compilers such as lexical analysis, patternmatching,
texteditors, unification as needed in Prolog or for automated deduction,
and almost any program which processes user commands. The description of
programming languages and the design of parsers for them will require an
intimate knowledge of contextfree grammars. More interestingly, with
the presence of a large amount of unstructured text on the Worldwide
Web, it has become increasingly important to employ techniques taught in
the course to extract structured information from this chaos.
2. The second half of the course is concerned with a more
philosophical approach to computer science. Here we will be concerned with
the basic questions of computability and tractability. Using the concept
of Turing Machines we will try to make precise the notion of an algorithm
and explore its limitations. We will encounter undecidable problems, viz.
those which cannot be solved by any algorithm or computer. Even if a problem
is decidable it may turn out to be intractable, i.e., there does not exist
any efficient algorithm to solve that problem. These notions have had (and
will continue to have) a profound influence on our approach to using computers
to solve problems.
3. Finally, I think the most important role of this course
is to turn you into ``mathematically mature'' computer scientists. This
course is quite mathematical and should develop your skills of precise
and formal reasoning. These skills will prove to be extremely important
in the design, analysis, and verification of complex software and hardware
systems. "
-
Course Requirements
| Homework |
- |
- |
- |
40% |
| Midterm Exam |
TBA |
March ??, 2002 |
6:15 - 7:30 pm |
30% |
| Final Exam |
Monday |
May 6, 2002 |
5:45 - 8:00 pm |
30% |
-
Milestone for successful completion of the course
-
Attend the classes regularly,
-
Perform the homework thoroughly and independently,
-
Read the book carefully and several times.
-
Students with Disabilities
In accordance with university policy, if you have a documented
disability and require accommodations to obtain equal access in this course,
please contact the instructor at the beginning of the semester or when
given an assignment for which an accommodation is required. Students with
disabilities must verify their eligibility through the Office of Student
Disability Services (SDS) in the Michael Schwartz Student Services Center
(672-3391).