Kurset introducerer en række fundamentale begreber og teknikker til
konstruktion og analyse af effektive algoritmer og datastrukturer.
At kunne beskrive, vurdere og anvende grundlæggende algoritmer og
datastrukturer. Og at kunne analysere en algoritme med hensyn til
køretid og ressourceforbrug.
Læringsmål:
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
Beskrive en algoritme på en forståelig måde, dvs. præcist,
kortfattet og entydigt.
Foretage basale analyser af algoritmer, herunder være i stand
til at bestemme køretider og pladsforbrug i asymptotisk
notation
Identificere og formulere det underliggende algoritmiske
problem i en given problemstilling.
Anvende og analysere basale datastrukturer, som f.eks. stakke,
køer, hægtede lister og hash-tabeller.
Anvende og analysere basale grafalgoritmer, f.eks. BFS, DFS og
Dijkstras algoritme.
Implementere og afprøve datastrukturer og algoritmer, samt lave
passende test og empiriske analyser af dem.
Analysere, vurdere og sammenligne algoritmer/datastrukturer og
på baggrund af dette vælge en passende algoritme/datastruktur til
løsning af et givet problem.
Tilpasse kendte algoritmer til at løse et givet problem.
Beskrive og sammenligne forskellige algoritmiske paradigmer,
herunder rekursion, grådige algoritmer og del-og-hersk.
Kommunikere løsninger til opgaver på en klar og præcis
måde
Være i stand til i et klart sprog at argumentere for valg
foretaget i forbindelse med løsning af et problem.
Analysere et givet problem og træffe kvalificerede valg til
løsning af problemet baseret på den foretagne
analyse.
Kursusindhold:
Begrebet algoritme; begreberne graf og træ; rekursion og iteration;
fundamentale algoritmer til sortering af data; teknikker til
analyse af algoritmers effektivitet (køretidsanalyser, analyse af
pladsforbrug); O-notation m.m.; elementære datastrukturer (stakke,
køer, hægtede lister m.m.); avancerede datastrukturer
(hash-tabeller, binære søgetræer m.m.); algoritmer på grafer
(breddeførst søgning, dybde-først søgning, topologisk ordning
m.m.). Grådige algoritmer og del-og-hersk algoritmer.
Litteraturhenvisninger:
"Introduction to Algorithms" af Cormen, Leierson, Rivest
og Stein. 3rd edition.
