Theory of Computation, Summer semester 2008

Department of Computer Sciences, University of Salzburg

Lecturer:      Dr. A. Sokolova, ana.sokolova"at", office 2.17 (together with Prof. C.M. Kirsch)

Schedule:      Tuesdays 3pm-5pm, Thursdays 2pm-3pm, T04

First meeting:     Tuesday, 4.3.2008, 3pm, T04

Language:      English

The course may also be taken by PhD students

Course description: We will cover elements from the theory of computation, in a detail appropriate to a master course. In particular we will introduce different models of computation (in an increasing order of expressivity). In short, the topics are: finite automata, regular languages, pumping lemma for regular languages, context free grammars, push-down automata, cf languages, pumping lemma for cf-languages, Turing machines, undecidability. Our focus will be on the expressivity of the different models of computation (classification of languages, pumping lemmas) and on Turing machines as the most expressive model. To this end, we will study the boundaries of computation and show undecidability results.

I quote an ETH-Zurich course announcement for a similair course:

Why a theory of computation? Nothing is more practical than a good theory! (end of quote)

Prerequisites: None. Knowledge of basics of theoretical computer science is an asset. The course is somewhat complementary to the course "Theoretische Informatik" which mainly focuses on recursive functions as a model of computation. We will focus on automata and Turing machines instead.

Exam: This is a VP course. There will be two tests during the semester, and an additional exam at the end of the semester. The exam is written consisting of several excersises from the material covered during the course. Additionally, there will be homeworks, which will also contribute to the final grade. First text exam: Tuesday 20.5.2008 during class (3pm-5pm). The material for the first test is up to PDA (without them). Second text exam: Thursday 26.6.2008.

Additional exam date(s): Wednesday 2.7.2008 1pm and Tuesday 8.7.2008 3pm. Please notify me by email two days in advance in case you plan to attend these exams.

Schedule: ! Note the different schedule in the first part of the semester (due to Easter break and travelling) !
Results from the exam(s) and homeworks

Student ID Exam test 1 points (<= 100) Exam test 2 points (<= 100) Full exam points (if no tests) (<= 100) HW points Total (mark)
****240 78 94 - 6 1
****178 63 89 - 5 2
****183 57 75 - 0 3
****173 - - 63 4 3