Tik-79.148 Introduction to theoretical computer science
Requirements, spring 2001
The goal of the coures is to introduce the basic concepts of
theoretical computer science. After the course the student should be
able to define, for example, what means Turing-decidable,
grammatically computable, primitive recursive function, regular
language, etc.
Moreover the student must know how to apply these concepts. in
different constructions and proofs. Examples of these are:
- define a finite state automaton that correspods a regular
expression
- define a pushdown automaton that correspods a given context free grammar G
-
define a context free grammar that defines language L = {x | P(x) }
-
transform a given finite state automaton to an equivalent
deterministic finite automaton
- prove that a given language L is not context free
- prove that a function f(x,y) is Turing computable
The course includes a lot of material. Therefore it should be
studied in the following order (because it is quite probable that
students have limited time for this course).
- The first 1-3 pages of each chapter give an overview of the subject
- The definitions of the basic concepts (words in bold)
- Different proofs and constructions (these are often parts of the
proofs), the most important proofs are mentioned below.
- Other proofs.
The concepts of the course can be put into the language hierarchy
of Chomsky. This can help to remember things.
Parts of the textbook that are inluded in the course
"Lewis-Papadimitriou: Elements of the theory of computation"
There are currently two different editions of the course book (1983
and 1998 ones). There are a few differences between the editions, but
both may be used. The newer one's presentation is somewhat clearer,
but the topic of Gödel-numbering is left out of it, so you should that
part from the older edition.
Below numbers [in brackets] are from old edition, if the numbering of
the sections or theorems differ between editions.
- Chapter 1, especially 1.7-1.8 [1.8 - 1.9]
- Chapter 2
- Chapter 3, except 3.7 [3.6 and pages 127 - 130]
- Chapter 4
- Chapter 5, except 5.6, Especially 5.3 [chapters 5-6, except
6.4.2 - 6.4.3 and 6.5 . Especially 6.1]
- From chapters 6 and 7 parts 6.1, 6.4, and 7.1-7.2. [7.1, 7.4, and
7.5]
Most important theorems and lemmas
- T2.2.1 [T2.3.1]
- T2.3.1 [T2.4.1]
- T2.3.2 [T2.5.1]
- T2.4.1 [T2.6.1]
- T2.6.1 [T2.4.2]
- T3.4.1, L3.4.1, L3.4.2 [T3.4.1, L3.4.3, L3.4.4]
- T3.5.1
- T3.5.3
- T4.5.1 [L4.6.1, T4.6.1]
- T4.6.2 [L5.2.1, T5.2.1]
- T4.7.1 [T5.6.1]
- [T5.5.1] (the equivalence of grammars and mu-recursive functions,
it follows from T4.6.2 and T4.7.1)
- T5.3.1 [T6.1.5]
- [T6.2.1 - T6.2.4] (relation between Turing-acceptable and
Turing-decidable languages)
- T5.4.2 [T6.3.1 - T6.3.2]
- T5.5.2 [T6.4.1]
- D6.1.1 [D7.1.1,D7.4.1]
- [T7.1.1] (Any Turing machine can have an arbitrary linear speedup)
- D6.4.1 [D7.4.2]
- T6.4.1 [T7.4.1]
- D7.1.1 [D7.5.1, D7.5.2]
- D7.1.2 [D7.5.3]
- T7.1.1 [T7.5.1]
- T7.2.2 [T7.5.2]