Selected Notions in the Theory of Computing

Lectures:

38 h

Recommended for

Foundational course for ECSEL. Recommanede for PhD students with a non-computer-science background, e.g. students from IMIE.

The course was last given:

Fall 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 will survey 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

Each module will include a number of lectures, a homework assignment and a closing session where the participants will be asked to summarize the main concepts of the module, to discuss relations between them and to discuss solutions to the homework assignments.

Contents

The course consists of the following modules.

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.

Literature

H.R.Lewis and C.H. Papadimitriou Elements of the Theory of Computation, Prentice Hall, 1998.

J.L.Peterson Petri Net Theory and the Modelling of Systems , Prentice Hall, 1981, Chapters 1-4. (For Part 2 of the course))

T. Murata Petri Nets: Properties, Analysis and Applications Proc. of the IEEE, vol. 77 No.4 (1989).

D. Harel Algorithmics, 2nd edition, Addison Weseley, 1992 Chapters 1-9. (For Parts 3 and 4 of the course)

Teachers

Jan Maluszynski

Examiner

Jan Maluszynski

Schedule

Spring 2001.

Examination

Written solutions to the homework problems are to be submitted to the examiner at latest at the closing session where the solutions are to be discussed. No solutions will be accepted after the deadline.

Credit

Each module gives 1.5 credits. To obtain the course credits it is necessary

• to deliver a complete solution to the homework assignment for every module taken,
• to participate in and to contribute to the closing sessions of the taken modules.