Modulets indhold, forløb og pædagogik

Læringsmål

Viden

Den studerende skal opnå viden om følgende teorier og metoder:  

• algoritmedesign-teknikker såsom del-og-hersk, grådige algoritmer, dynamisk programmering, backtracking, branch-and-bound-algoritmer, randomiserede algoritmer og lineær programmering

• teknikker indenfor avanceret algoritmeanalyse såsom amortiseret analyse, analyse af forventet kompleksitet og eksperimenter med algoritmer         

• eksempler på kernealgoritmer og datastrukturer til løsning af en række problemer fra forskellige datalogiske områder såsom algoritmer til ekstern hukommelse, fler-trådede algoritmer, søgning i tekst, avancerede grafalgoritmer og geometriske beregninger

• beregningsteori: Turing-maskiner; Church-Turing-tesen; eksempler på reduktion valgbare og genkendelige sprog; eksempler på uafklarbare problemer, herunder beviser via reduktion

• kompleksitetsteori: deterministiske og nondeterministiske Turing-maskiner og deres tidskompleksitet; tidskompleksitetsklasser; polynomielle reduktioner; NP-fuldstændighed; eksempler på NP-fuldstændige problemer

Færdigheder

• redegøre for principperne bag de vigtigste algoritme-design og –analyse teknikker

• udvælge og anvende algoritme-design og –analyse teknikker for en given problemstilling

• genkende en række problemer fra forskellige datalogiske områder og udvælge de mest passende algoritmer og datastrukturer for at løse dem

• kunne redegøre præcist og ved brug af fagets terminologi og notation for vigtige resultater inden for beregningskompleksitet og for hvordan og i hvilket omfang disse resultater kan anvendes til at klassificere beregningsproblemer, herunder kompleksitetsanalyse og anvendelser af reduktioner

• være i stand til at kategorisere beregningsproblemer som dedidable/undecidable og argumentere for, at konkrete problemer er NP-hårde ved at bruge begrebet reduktion
  
  FÆRDIGHEDSMÅL GÆLDENDE FOR STUDERENDE DER LÆSER PÅ KANDIDATNIVEAU, MEN FØLGER UNDERVISNING PÅ BACHELORNIVEAU:

• forstå og anvende principper for bevisteknikker, der er omfattet af kurset, med fokus på matematisk præcis argumentation

Kompetencer

• kunne anvende begreber og teknikker indenfor beregningskompleksitet til analyse af beregningsproblemer

• skal stillet over for et datalogisk problem kunne udvikle og analysere effektive algoritmer og datastrukturer til løsning af problemet

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