Hide menu

Selected Notions in the Theory of Computing

FDA071, 2003HT

Status Archive
School Excellence Center for Computer Science and Systems Engineering in Linköping (ECSEL)
Division SAS
Owner Jan Maluszynski
Homepage http://www.ida.liu.se/~janma/ecsel03/ecsel.html

  Log in  




Course plan

Lectures

30h + seminars

Recommended for

ECSEL students with non-computer-science background.
The students with background in computer science may only be admitted to the modules presenting the material not covered in their undergraduate studies.

The course was last given

VT 2001

Goals

The course gives an introduction to basic concepts of:
- Automata Theory and Formal Languages,
- Petri Nets,
- Algorithms, Tractability and Decidability
and discusses their practical importance.

Prerequisites

An introductory course in Discrete Mathematics or equivalent knowledge.

Organization

The course has 3 modules/parts (see below).
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. The lectures will be grouped in 3 hours sessions, one session per week.

Contents

Module 1: 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.

Module 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 Module 1.

Module 3: Algorithms, Tractability and Decidability.
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.
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.

Literature

H.R.Lewis and C.H. Papadimitriou Elements of the Theory of Computation, Prentice Hall, 1998. (Module 1 and 3)

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

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

D. Harel Algorithmics, 2nd edition, Addison Weseley, 1992, Chapters 1-9. (Module 3)

Lecturers

Jan Maluszynski

Examiner

Jan Maluszynski

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

Module 1: 1.5 credits
Module 2: 1.5 credits
Module 3: 3.0 credits

To obtain the course credits it is necessary:
(1) to deliver a complete solution to the homework assignment for every module taken,
(2) to participate in and to contribute to the closing sessions of the taken modules.

Comments


Page responsible: Director of Graduate Studies