Selected Notions in the Theory of Computing

Lectures: 38 h

Recommended for:
Foundational course for ECSEL.

The course last ran:
1997.

Goals:
The course presents selected topics in theory of computing. The basic concept in this context is a notion of discrete computation, or discrete process. At an abstract level it can be seen as a sequence of transitions between states triggered by some events. Thus, we will discuss systems consisting of states and transitions observing certain rules. Such systems turned out to be very  useful, for example in modelling industrial processes, in design of digital circuits or in compiler construction. The course wil lsurvey several specific classes of the systems which are of particular importance for the applications.

Computations performed by computers follow certain algorithms described by the programs controlling the computations. The notion of algorithm is thus another basic concept in the focus of this course. It has been formalized by Alan Turing in terms of a state transition system known as Turing machine. We discuss how formalisation of the notion of algorithm allows one to show that some practically interesting problems are undecidable (i.e. there are no algorithms solving them), or intractable (there are no sufficiently efficient algorithms).

In addition we survey some commonly used data structures, like lists, trees, stacks, and some commonly used algorithms for searching and sorting. On these examples we demonstrate techniques for complexity analysis of the algorithms.

Prerequisites:
MSc in a non-computer-science area and some programming experience.

Organization:
Lectures and discussion sessions.

Contents:
The course consists of the following parts.

1. Abstract Automata and Formal Languages. This part is motivated by applications such as modelling of discrete event systems or compiler construction. It presents the classical transition systems: Finite Automata (deterministic and nondeterministic) and Push-Down Automata, and the corresponding languages: regular and context-free. These languages are also characterized by grammars, commonly used as a language specification formalism.

2. Petri Nets and the modelling of systems. Petri Nets provide a natural formalism for modelling of systems. We survey basic concepts and discuss some applications of the formalism, e.g. for design of digital circuits or for modelling of concurrent processes, and their synchronisation. We show relation to abstract automata discussed in Part 1.

3. Algorithms. We discuss the notions of algorithmic problem, algorithm and data structure. We illustrate them by examples of some comonly used algorithms on data structures. We survey some basic notions of complexity theory and discuss their relevance for analysis of algorithms.

4. Tractability and decidability. We discuss Turing machines as formalisation of the notion of algorithm. We show its relevance for studying decidability and tractability of algorithmic problems. We present an important concept of NP-complete problem. Many practically relevant algorithmic problems, like planning and scheduling fall in this class. We give examples of such problems, among others the Constraint Satisfaction Proble

Literature:
D. Kelley Automata and Formal Languages. An Introduction, Prentice Hall, 1995.
J.L Peterson Petri Net Theory and the Modelling of Systems , Prentice Hall, 1981, Chapters 1-4. (For Part 2 of the course)
D. Harel Algorithmics, 2nd edition, Addison Weseley, 1992 Chapters 1-9. (For Parts 3 and 4 of the course)

Examiner:
Jan Maluszynski.

Schedule:
Fall 1998.

Examination:
Home assignments, presentations at the discussion session.

Credit:
6 credit points (for graduate students not having studied this material before).

Page responsible: Webmaster
Last updated: 2012-05-03