IT-Universitetet i København
 
  Tilbage Kursusoversigt
Kursusbeskrivelse
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:
Forventet antal deltagere:
Maks. antal deltagere:
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.

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

  2. 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:

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

  2. 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/>