Theory of Computational Systems Course, Summer 2005

Department of Computer Sciences, University of Salzburg

Prof. Christoph Kirsch

Time, Location: Tue 3-4, Th 2-4, Techno-Z T04. First two lectures on Thursday, March 17, 2-4, Techno-Z T04 and Friday (!), March 18, 1-2, Techno-Z T01 (to catch up with lost time).

Brief Overview:

This course is for the practically-minded graduate student who always wanted to know what the theory of computation and systems is good for. The course provides a hands-on yet graduate-level introduction to the classical theory of computation and to the theory of computational systems such as concurrent, reactive, real-time, and hybrid systems. The first part of the course reviews classical automata theory, formal languages, and computational complexity theory; the second part gives an overview of concurrency models such as CSP, CCS, and Petri nets, as well as of reactive, real-time, and hybrid systems such as timed and hybrid automata. The key question asked in this course is: why do we need theories of computation and systems and how do they manifest in practice? The purpose of this course is to give practical meaning to computer science theory and advocate principled engineering. The target audience are students interested in the design of complex software systems such as operating systems, distributed systems, and real-time systems. Students will experience casual access to computer science theory by designing (defining) and implementing (proving) their own mini theories of computation or systems in class projects.

Goal of the course:

Learn how to make sense of computer science theory and appreciate principled engineering.

Assignments:

  • Teams of 2-3 students will define their own mini theory of computation or systems, prove interesting properties, present their results at the end of the semester, and write project reports that could eventually result in publications. Each team creates a wiki page that describes the project.

Project:

Required Textbooks:

  • Michael Sipser: Introduction to the Theory of Computation. Boston, MA: PWS Publishing Company, 1997. Computer science theory presented from a uniquely intuitive, "big picture" perspective. I will mainly use this book.
  • Michael R. Garey and David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979. The standard reference on NP-Complete problems - an important category of problems whose solutions appear to require an impractically long time to compute.
  • Hopcroft, John E., and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation. Reading, MA: Addison-Wesley, 1979. One of the standard references in the field.
Recommended Textbooks:
  • James L. Hein: Theory of Computation. Sudbury, MA: Jones & Bartlett, 1996. A gentle introduction to the field, appropriate for second-year undergraduate computer science students.
  • R. Gregory Taylor: Models of Computation. New York: Oxford University Press, 1998. An unusually readable textbook, appropriate for upper-level undergraduates or beginning graduate students.
Web sources:

Grading: 100% project.

Prerequisites: Basic knowledge in automata theory, formal languages, and computational complexity theory is helpful but not required.

Administrative contact: Petra . Kirchweger @ cs . uni-salzburg . at