Hide menu

TDDD65 6 hp /Introduction to the Theory of Computation

Lectures


The plan is to use the same slides as last year (2012).
(Note that the references to the book refer to the 2nd edition.)
  •  Slides (2012): with references to the sections of the coursebook (Sipser). Sections that will be covered: 0.1, 0.2, 1.1, 1.2, 1.3, 1.4, 2.1, 2.2, 2.3, 3.1, 3.2, 3.3, 4.1, 4.2, 5.3, 7.1, 7.2, 7.3, 7.4 + additional topics from chapters 8-10 based on the students preferences.
    1. Introduction, Finite Automata (0.1, 0.2, 1.1, 1.2)
    2. Regular Expressions, Pumping Lemma, (1.2, 1.3, 1.4)
    3. Context-free Languages (2.1, 2.2, 2.3)
    4. Computability (two lectures) , (3.1, 3.2, 3.3, 4.1, 4.2, 5.3)
    5. Complexity (3 lectures) , (7.1, 7.2, 7.3, 7.4)
    6. If time allows, the last lecture will be about some more advanced topics in complexity theory.

Page responsible: Christer Bäckström
Last updated: 2013-08-31