| 02240 Computability and Semantics |
| Danish title: Beregnelighed og semantik |
|
Language: English ECTS-creditpoints: 10, External examination.
|
|
|
Exam schedule:
|
F1-A (maj 27 2002), E1-A (dec 10 2001) |
| Scope and form: Lectures |
| Evaluation: Written exam
|
| Examination: 13-scale |
| Prerequisites: 02140 |
Aim: The aim of the course is to give students an understanding
for the central concepts of computability and semantics.
a) Concerning computability this includes an understanding of the limit
for the problems which can be solved by computers and the limit
between the problems which are practically solvable by computers
and those which are not practically solvable.
b) Concerning semantics this includes an understanding of ways of giving
mathematical descriptions of programs and their behaviour. This
includes understanding of the semantics of a collection of central
concepts from programming languages. |
Contents: a) Automata based models of computers, e.g. Pushdown
automata and Turing machines. Charaterization of the expressibility
of the different models by formel languages, expressed by grammars.
It will be studied which problems cannot be solved by the various
models. Furthermore, the complexity classes P and NP, and the concept
og NP-completeness will be studied.
b) Different forms of semantics, including operational semantics
(natural and structural operational semantics), denotational semantics
(with simple fixpoint theory), and axiomatic semantics of a simple
programming language. Equivalence proofs.
e1 |
| Contact: Michael Reichardt Hansen, building 322, (+45) 4525 3727, mrh@imm.dtu.dk |
| Department: 002 Informatics and Mathematical Modelling |
| Course URL: http://www.imm.dtu.dk/courses/02240 |
| Updated: 14-01-2002 |
|
|
