| Kursusnavn (dansk): | 02240 Beregnelighed og semantik |
| Kursusnavn (engelsk): | 02240 Computability and Semantics |
| Semester: | Forår 2004 |
| Udbydes under: | cand.it., internet- og softwareteknologi (int) |
| Omfang i ECTS: | 10,00 |
| Kursussprog: | Engelsk |
| Kursushjemmeside: | https://learnit.itu.dk |
| Min. antal deltagere: | 0 |
| Forventet antal deltagere: | 0 |
| Maks. antal deltagere: | 20 |
| Formelle forudsætninger: | Prerequisites: Mastery of programmering in imperative and functional languages; including algorithms and data structures.
Understanding of teori and application of regular and context-free languages, including discrete mathematics and acquantance with simple proof techniques.
Covered by ?Informatik fagpakken? with associated ?startpakke?. |
| Læringsmål: | To give the students an introduction to the formal techniques and their applications within semantics and computability. |
| Fagligt indhold: | Semantics: Transition systems, natural semantics and structural operational semantics, Type systems, including polymorphism. Semantics of imperative, procedural and functional languages. Prototype implementations. Program Analysis: Monotone and distributive frameworks. Lattice theory and
Tarski?s fixed point theorem. Semantic correctness. Forward, backwards, first order, second order program analyses. Algorithms for constraint solving. Optimising compilers and validation of security properties. Analysis tools and prototype implementations.
Computability: Turing machines and undecidable problems. Turing machine models, non-determinism, equivalence results, universal Turing machines, recursive and recursive enumerable languages. Undecidable problems for Turing Machines other undecidable problems, including reduction techniques and Rice?s theorem.
See also <a href=\"http://shb.dtu.dk/default.asp?detail=f&page=3&kurser=02240&lang=uk&retning=*\">the course description at DTU.
NB! Students are not guaranteed admission at the DTU-courses (But we assume that there will be enough places). Students will be notified about 14 days before the beginning of the term. |
| Læringsaktiviteter: | Lectures |
| Eksamensform og -beskrivelse: | X. experimental examination form (7-scale; external exam), 13-skala, Ekstern censur See <a href=\"http://shb.dtu.dk/default.asp?detail=f&page=3&kurser=02240&lang=uk&retning=*\">the course description at DTU.
|
| Litteratur udover forskningsartikler: | See <a href=\"http://shb.dtu.dk/default.asp?detail=f&page=3&kurser=02240&lang=uk&retning=*\">the course description at DTU. |
| | |
Kursusoversigt