At få kendskab til begreberne 'algoritme' og 'datastruktur'. At blive i stand til at analysere og konstruere algoritmer. At kunne beskrive, vurdere og anvende algoritmer til sortering, søgning og beregning på grafer.
Læringsmål:
En studerende, der fuldt ud har opfyldt kursets mål, vil kunne:
omforme løst beskrevne algoritmer til algoritmer i pseudokode.
konstruere både iterative og rekursive algoritmer i pseudokode, og kunne oversætte algoritmer fra den ene til den anden type.
lave beregninger som involverer udtryk i asymptotisk notation.
foretage basale analyser af algoritmer, herunder være i stand til at bestemme køretider.
formulere simple korrekthedsbeviser for algoritmer, herunder være i stand til at bestemme løkke-invarianter.
implementere ikke-trivielle datastrukturer og algoritmer samt lave passende tests og emperiske analyser af dem.
anvende, analysere og sammenligne en række basale sorterings-algoritmer.
anvende, analysere og sammenligne en række basale algoritmer på grafer og træer.
analysere, vurdere og sammenligne forskellige implementationer af givne datastrukturer.
foretage et kvalificeret valg af datastrukturer og algoritmer givet et problem som skal løses.
konstruere egne simple algoritmer udfra en beskrivelse af et problem som skal løses.
Kursusindhold:
Begrebet algoritme; begreberne graf og træ; rekursion og iteration; fundamentale algoritmer til sortering af data (fletsortering, hobsortering m.m.); teknikker til analyse af algoritmers effektivitet (køretidsanalyser); O-notation m.m.; elementære datastrukturer (stakke, køer, lænkede lister m.m.); avancerede datastrukturer (hash-tabeller, binære søgetræer m.m.); algoritmer på grafer (bredde-først søgning, dybde-først søgning, topologisk ordning, korteste stier af vægtede grafer m.m.).
Litteratur::
T. Corman et al.: Introduction to Algorithms, Second Edition, The MIT Press, 2001.
