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; fuldstændighed;

• 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

Undervisningen tilrettelægges i henhold til de generelle undervisningsformer for uddannelsen jf. § 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