Algoritmer og beregnelighed

2020/2021

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

Modulet bygger videre på viden opnået i moduler: datalogiens teoretiske grundlag, algoritmer og datastrukturer og syntaks og semantik

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

  • afgørbare og genkendelige beslutningsproblemer; Turing-maskiner; Church-Turing-tesen; eksempler på reduktion
  • kompleksitetsteori: deterministiske og nondeterministiske Turing-maskiner og deres tidskompleksitet; tidskompleksitetsklasser; polynomielle reduktioner; NP-fuldstændighed; eksempler på NP-fuldstændige problemer

Færdigheder

  • 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

  • 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

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

Prøvens navnAlgoritmer og beregnelighed
Prøveform
Skriftlig eller mundtlig
ECTS5
Bedømmelsesform7-trins-skala
CensurIntern prøve
VurderingskriterierVurderingskriterierne er angivet i Universitetets eksamensordning

Yderligere informationer

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

 

Fakta om modulet

Engelsk titelAlgorithms and Computability
ModulkodeDSNSWCB611
ModultypeKursus
Varighed1 semester
SemesterForår
ECTS5
UndervisningssprogDansk
TompladsJa
UndervisningsstedCampus København
Modulansvarlig

Organisation

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