Forudsætninger/Anbefalede forudsætninger for at deltage i modulet

Modulets indhold, forløb og pædagogik

Læringsmål

Viden

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

Færdigheder

• 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

Kompetencer

• kunne anvende begreber og teknikker fra teorierne for beregnelighed og beregningskompleksitet til analyse af beregningsproblemer

Undervisningsform

Se generel beskrivelse af anvendte undervisningsformer i studieordningens § 17.

Omfang og forventet arbejdsindsats

Det forventes at den studerende bruger 30 timer per ECTS, hvilket for denne aktivitet betyder 150 timer.

Eksamen

Prøver

Yderligere informationer

Kontakt: Studienævn for datalogi via cs-sn@cs.aau.dk eller 9940 8854