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
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
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
Undervisningen tilrettelægges i henhold til de generelle undervisningsformer for uddannelsen jf. § 17.
Det forventes at den studerende bruger 30 timer per ECTS, hvilket for denne aktivitet betyder 150 timer.
Prøvens navn | Algoritmer og beregnelighed |
Prøveform | Skriftlig eller mundtlig |
ECTS | 5 |
Bedømmelsesform | 7-trins-skala |
Censur | Intern prøve |
Vurderingskriterier | Vurderingskriterierne er angivet i Universitetets eksamensordning |
Kontakt: Studienævn for datalogi via cs-sn@cs.aau.dk eller 9940 8854
Engelsk titel | Algorithms and Computability |
Modulkode | DSNSWFB621 |
Modultype | Kursus |
Varighed | 1 semester |
Semester | Forår
|
ECTS | 5 |
Undervisningssprog | Dansk |
Tomplads | Ja |
Undervisningssted | Campus Aalborg |
Modulansvarlig |
Studienævn | Studienævn for Datalogi |
Institut | Institut for Datalogi |
Fakultet | Det Teknisk Fakultet for IT og Design |