|
02240 Beregnelighed og semantik |
| Engelsk titel: Computability and Semantics |
|
Sprog: Engelsk Point: 10, Ekstern censur. |
|
| Type: civilkursus, udbydes under åben uddannelse |
|
Eksamensplacering: |
F1-A (maj 27 2002), E1-A (dec 10 2001)
|
|
Undervisningsform: Forelæsninger |
|
Evalueringsform: Skriftlig eksamen
|
| Karakter: 13-skala |
| Faglige forudsætninger: 02140 , diskret matematik |
| Kursusmål: Formålet med kurset er at give de studerende forståelse forcentrale begreber indenfor beregnelighed og semantik.For emnet beregnelighed indebærer det forståelse af forskelligematematiske modeller af programmer og datamaskiner og deres indbyrdesstyrke. Desuden skal de studerende have en forståelse af grænserne forde opgaver der kan løses ved brug af databaskiner og grænsenmellem de opgaver der er praktisk løsbare og dem der næppe er praktiskløsbare.For emnet semantik indebærer det en forståelse af at programmer ogderes virkemåde kan beskrives ved matematiske begreber. Herunderforståelse af semantikken for en række grundlæggende begreber fraprogrammeringssprog. |
| Kursusindhold: a) Automatbaserede modeller for datamaskiner, herunder stakmaskiner ogTuringmaskiner. Karakterisering af de forskellige modellers styrkeved formelle sprog, der beskrives ved grammatikker. For de forskelligemodeller vil det blive belyst hvilke type opgaver, der ikke kan løsesaf den pågældende datamaskine. Desuden indføreskompleksitetsklasserne: P og NP, og begrebet NP-fuldstændighed vilblive behandlet.b) Forskellige former for semantik, herunder operationel (naturligsemantik og strukturel oprationel semantik), denotationel (med simpelfixpunktteori) og axiomatisk semantik af et simpeltprogrammeringssprog. Ækvivalensbeviser. |
| Kontaktperson: Michael Reichardt Hansen, building 322, (+45) 4525 3727, mrh@imm.dtu.dk |
| Institut: 002 Informatik og Matematisk Modellering |
| Kursus URL: http://www.imm.dtu.dk/courses/02240 |
| Opdateret: 14-01-2002 |
|
|
