Kursusnavn (dansk): | Beregnelighed og Semantik |
Kursusnavn (engelsk): | Computability and Semantics |
Semester: | Forår 2002 |
Udbydes under: | cand. it, softwareudvikling (swu) |
Omfang i ECTS: | 7,50 |
Kursussprog: | Dansk |
Kursushjemmeside: | https://learnit.itu.dk |
Min. antal deltagere: | 0 |
Forventet antal deltagere: | 0 |
Maks. antal deltagere: | 0 |
Formelle forudsætninger: | A fundamental understanding of formal languages, simpel syntax analysis, simple machine models and their applications.
Can be aquired by completing the DTU course:
|
Læringsmål: | The aim of the course is to give students an understanding for the central concepts of computability and semantics.
- 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.
- 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.
|
Fagligt indhold: |
- 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.
- 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
Course URL: http://www.imm.dtu.dk/courses/02240 |
Læringsaktiviteter: | The course consists of lectures and theoretical and practical programming exercises. In the current plan for programming exercises are: Implementation of a |
Eksamensform og -beskrivelse: | X. experimental examination form (7-scale; external exam), 13-skala, Intern censur Written exam graded on the danish 13-scale.
|
Litteratur udover forskningsartikler: |
- Introduction to Automata Theory, Languages, and Computation,
John E. Hopcroft, Rajeev Motwani, Jefrey D. Ullman, Second Edition, Addison-Wesley, 2001
- Semantics with Applications: A Formal Introduction,
<br/> Hanne Riis Nielson and Flemming Nielson. <br/> |
| |