Beregnelighed og kompleksitet

2018/2019

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

Anbefalede faglige forudsætninger:
Modulet bygger videre på viden fra modulerne Datalogiens teoretiske grundlag, Algoritmik og datastruktur samt Syntaks og semantik.

Modulets indhold, forløb og pædagogik

Læringsmål

Viden

  • 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; opfyldelighedsproblemet (SAT); øvrige NP-fuldstændige 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

Undervisningen tilrettelægges i henhold til de generelle undervisningsformer for uddannelsen, jf. kapitel 3

Omfang og forventet arbejdsindsats

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

Eksamen

Prøver

Prøvens navnBeregnelighed og kompleksitet
Prøveform
Skriftlig eller mundtlig
ECTS5
Bedømmelsesform7-trins-skala
CensurEkstern prøve
VurderingskriterierSom angivet i Fakultets vurderingskriterier
http:/​/​www.tech.aau.dk/​digitalAssets/​337/​337434_vurderingskriterier.pdf

Yderligere informationer

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

 

Fakta om modulet

Engelsk titelComputability and Complexity
ModulkodeDSNDATFB505
ModultypeKursus
Varighed1 semester
SemesterEfterår
ECTS5
UndervisningssprogDansk
TompladsJa
UndervisningsstedCampus Aalborg
Modulansvarlig

Organisation

StudienævnStudienævnet for Datalogi
InstitutInstitut for Datalogi
FakultetDet Tekniske Fakultet for IT og Design