Den studerende skal opnå viden om følgende teorier og metoder:
Beregnelighed:
deterministiske og nondeterministiske Turing-maskiner; afgørbare og genkendelige sprog og deres egenskaber: Church-Turing-tesen
acceptproblemet for Turing-maskiner; andre uafgørbare problemer for Turing-maskiner; reduktioner og deres egenskaber
Kompleksitetsteori:
tidskompleksitet for deterministiske og nondeterministiske Turing-maskiner; tidskompleksitetsklasser; polynomielle reduktioner og deres anvendelser; NP-fuldstændighed; tilfredshedsproblem (SAT); andre NP-komplette problemer
pladskompleksitet for deterministiske og nondeterministiske Turing- maskiner; pladskompleksitetsklasser, forholdet mellem tids- og pladskompleksitet
kunne redegøre præcist og ved brug af fagets terminologi og notatin for vigtige resultater inden for teorierne for beregnelighed og beregningskompleksitet og for hvordan og i hvilket omfang disse resultater kan anvendes til at klassificere beregningsproblemer
kunne gøre brug af de fornødne skriftlige færdigheder i disse sammenhænge
kunne anvende begreber og teknikker fra teorierne for beregnelighed og beregningskompleksitet til analyse af beregningsproblemer
Se generel beskrivelse af anvendte undervisningsformer i studieordningens § 17.
Det forventes at den studerende bruger 30 timer per ECTS, hvilket for denne aktivitet betyder 150 timer.
Prøvens navn | Beregnelighed og kompleksitet |
Prøveform | Skriftlig eller mundtlig |
ECTS | 5 |
Bedømmelsesform | 7-trins-skala |
Censur | Ekstern prøve |
Vurderingskriterier | Vurderingskriterierne er angivet i Universitetets eksamensordning |
Kontakt: Studienævn for datalogi via cs-sn@cs.aau.dk eller 9940 8854
Engelsk titel | Computability and Complexity |
Modulkode | DSNCSITK223 |
Modultype | Kursus |
Varighed | 1 semester |
Semester | Forår
|
ECTS | 5 |
Undervisningssprog | Engelsk |
Tomplads | Ja |
Undervisningssted | Campus Aalborg |
Modulansvarlig |
Uddannelsesejer | Cand.scient. i datalogi (it) |
Studienævn | Studienævn for Datalogi |
Institut | Institut for Datalogi |
Fakultet | Det Teknisk Fakultet for IT og Design |