De studerende lærer 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
Foretage basale analyser af algoritmer, herunder være i stand til at bestemme køretider og pladsforbrug i asymptotisk notation
Foretage et kvalificeret valg af datastrukturer og algoritmer givet et problem som skal løses
Tilpasse kendte algoritmer til at løse et givet problem
Analysere, vurdere og sammenligne forskellige implementationer af givne datastrukturer
Implementere ikke-trivielle datastrukturer og algoritmer samt lave passende tests og empiriske analyser af dem
Konstruere iterative og rekursive algoritmer
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.
