Lecture: Theory of Computation (251-0006-00)

Lecturers: Prof. Jürg Nievergelt and Prof. David Basin

Classes: 3V

• Thu 8-11, HG F 7

Exercises: 2U

• Mon 08-10, ML H 43 - Vania Bättig
• Mon 08-10, ML J 34.1 - Beat Gfeller
• Mon 08-10, ML H 34.3 - Manuel Hilty
• Mon 08-10, HG F 26.5 - Yvonne Anne Oswald
• Tue 15-17, HG F 26.3 - Markus Brändle
• Tue 15-17, ML H 44 - Katrin Bretscher
• Tue 15-17, HG G 26.1 - Boris Köpf
• Tue 15-17, HG G 26.5 - Vincent Tscherter

Language: German

Topics:

What is "theory of computation"?

• Basic question: What can or cannot be computed with given resources: primitive operations, bounds on resources (time, memory=space, wire length, fanout, energy consumed, ...)
• Brief survey of the historical development:
  Computability, decidability (1930s, 40s: A. Church, E.L. Post, A.M. Turing, A.A. Markov, S.C. Kleene).
  Church's thesis: the most general concept of automatic computation.
  Formal languages and grammars as models of natural language (50s: N. Chomsky)
  Classes of automata: computing devices of limited power
  Relationship between classes of automata and languages
  Complexity (60s, 70s): how many operations and memory cells are needed.
• Content of our course: Automata, formal languages, computability, complexity.
  Various guest lectures will introduce additional self-contained theoretical topics and application

Why a theory of computation? Nothing is more practical than a good theory!

• What kind of knowledge can you acquire today that will serve for your entire career, that will still be valid in the year 2040? (Hint: concepts that have already survived half a century of CS development.)
• Theory extracts the basic concepts that apply to any conceivable implementation of computing machines. These concepts are of timeless validity, in contrast to technology-specific and product-specific know-how.
• A firm mastery of basic concepts is a great "data compression technique": many seemingly unrelated facts, presented in time-varying jargon, can be understood intuitively as instances of the same principle.

Schedule, Lecture Notes, and Exercises

Exam & Testat:

• Hand in all homework, alone or in groups of 2 students in the following week.
• Exam problems are formulated in English, answers may be written in English or German. Closed book exam (keine Hilfsmittel).

Useful Links:

• Exorciser
• Kara

Literature:

• N. Blum: Theoretische Informatik - eine anwendungsorientierte Einführung, Oldenburg, München, 1998
• U. Schöning: Theoretische Informatik - kurzgefasst, Spektrum Akademischer Verlag, Heidelberg, 1997
• I. Wegener: Theoretische Informatik, Teubner, Stuttgart 1 1993
• E. Engeler, P. Laeuchli: Berechnungstheorie fuer Informatiker, Teubner, Stuttgart 1988
• J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to automata theory, languages and computation, Addison-Wesley 2001
• M. Minsky: Computation: Finite and infinite machines, Prentice-Hall, 1967
• H.R. Lewis, C.H. Papadimitriou: Elements of the theory of computation, Prentice-Hall, 1981
• M. Sipser: Introduction to the theory of computation, PWS Publ. Co, Boston, 1997