Home

Back

DAT3 spring 2007 - Computation and Complexity Theory

Teacher: Andrea Valente (aaue.dk/~av)

Book: IATLC

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
Introduction to Automata Theory, Languages, and Computation (2nd Edition)
ISBN 0201441241 2nd edition, Addison Wesley (November 14, 2000)

Course plan:

Lecture nr: Date: Topic: Literature: Comments:

1 5/2 B207 8:30 Introduction
Computers, Turing Machines, Problems and Solutions. IATLC: part of 8.2 and 8.1
Intoduction (pdf)

12/2 B207 8:30 sick

2 19/2 B207 8:30 Formalization
Formal proofs, Set Theory (still to do: Cantor). Represent data structures with sets: couples, tuples, functions/tables, string. Languages. Chomsky hierarchy. IATLC: 1.2 - 1.5

3 26/2 B207 8:30 Finite Automata
Introduction, DFA, examples IATLC: 2.1 - 2.3 (2.4)

5/3 B207 8:30 POSTOPONED

4 12/3 B207 8:30 Finite Automata (2)
NFA, NFA with epsilon transitions, def of regular languages IATLC: 3.1 - 3.3 (3.4)

5 15/3 B207 12:30 Regular languages
Regula expressions. Pumping lemma. IATLC: 4.1 - 4.3

6 19/3 B207 8:30 Context Free languages
Regular and Non regular languages, closure properties.
Context free grammars. IATLC: 5.1 , 5.2 (5.3, 5.4)

7 22/3 B207 12:30 Context Free languages (2)
Derivation, parse trees, ambiguity. Practical applications: parsing, defining languages, understanding specifications. IATLC: 6.1 - 6.4 Exercises: what have we got so far?

8 26/3 B207 8:30 Context Free languages (3)
Pushdown automata, equivalence PDA\CFG IATLC: (7.1) 7.2 (7.3, 7.4)

9 29/3 B207 12:30 Context Free languages (4)
Properties of CF languages, Non CF languages IATLC: 8.1 - 8.3

10 2/4 B207 12:30 Turing Machines
Formal definition of TM, introduction to undecidable problems IATLC: 8.4 - 8.4.4 - 8.6 (9.2.3) Turmites

Easter vacations

11 12/4 B207 12:30 Exotic Turing Machines
Multitape TM, Turmites, Non-deterministic TM, Universal TM
Intro to Cantorian set theory (pdf) IATLC: 8.4.4 , 9.1 - 9.3 (9.5)

12 16/4 8:30 Undecidability
Halting problem. (Omega number)

13 19/4 12:30 Intractable problems
Time complexity, Class P, Class NP, Class Exp.
Examples of intractable problems. Supervision for projects: code mobility

14-15 23/4 8:30 -
26/4 12:30
B207 Intractable problems
NP-completeness, examples IATLC: 10.1 - 10.4 Discuss some of the exam questions, all together

Exam questions

Department for Software, Electronics og Mediatechnology - Aalborg University Esbjerg - Niels Bohrs Vej 8 - 6700 Esbjerg - Denmark

Lecture nr:	Date:	Topic:	Literature:	Comments:
1	5/2 B207 8:30	Introduction Computers, Turing Machines, Problems and Solutions.	IATLC: part of 8.2 and 8.1 Intoduction (pdf)
	12/2 B207 8:30	sick
2	19/2 B207 8:30	Formalization Formal proofs, Set Theory (still to do: Cantor). Represent data structures with sets: couples, tuples, functions/tables, string. Languages. Chomsky hierarchy.	IATLC: 1.2 - 1.5
3	26/2 B207 8:30	Finite Automata Introduction, DFA, examples	IATLC: 2.1 - 2.3 (2.4)
	5/3 B207 8:30	POSTOPONED
4	12/3 B207 8:30	Finite Automata (2) NFA, NFA with epsilon transitions, def of regular languages	IATLC: 3.1 - 3.3 (3.4)
5	15/3 B207 12:30	Regular languages Regula expressions. Pumping lemma.	IATLC: 4.1 - 4.3
6	19/3 B207 8:30	Context Free languages Regular and Non regular languages, closure properties. Context free grammars.	IATLC: 5.1 , 5.2 (5.3, 5.4)
7	22/3 B207 12:30	Context Free languages (2) Derivation, parse trees, ambiguity. Practical applications: parsing, defining languages, understanding specifications.	IATLC: 6.1 - 6.4	Exercises: what have we got so far?
8	26/3 B207 8:30	Context Free languages (3) Pushdown automata, equivalence PDA\CFG	IATLC: (7.1) 7.2 (7.3, 7.4)
9	29/3 B207 12:30	Context Free languages (4) Properties of CF languages, Non CF languages	IATLC: 8.1 - 8.3
10	2/4 B207 12:30	Turing Machines Formal definition of TM, introduction to undecidable problems	IATLC: 8.4 - 8.4.4 - 8.6 (9.2.3)	Turmites
Easter vacations
11	12/4 B207 12:30	Exotic Turing Machines Multitape TM, Turmites, Non-deterministic TM, Universal TM Intro to Cantorian set theory (pdf)	IATLC: 8.4.4 , 9.1 - 9.3 (9.5)
12	16/4 8:30	Undecidability Halting problem. (Omega number)
13	19/4 12:30	Intractable problems Time complexity, Class P, Class NP, Class Exp. Examples of intractable problems.		Supervision for projects: code mobility
14-15	23/4 8:30 - 26/4 12:30 B207	Intractable problems NP-completeness, examples	IATLC: 10.1 - 10.4	Discuss some of the exam questions, all together