Swedish web site
Selected Notions in the Theory of ComputingFDA071, 2004HT
|
|
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
HT 2003
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: Anne Moe
