Enkeltfag Engelsk 5 ECTS

Algoritmer og datastrukturer 1

Overordnede kursusmål

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.

See course description in English

Læringsmål

  • Beskrive en algoritme på en forståelig måde, dvs. præcist, kortfattet og entydigt.
  • Argumentere for korrekthed af algoritmer.
  • Analysere 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 grafer til at modellere en given problemstilling.
  • Anvende og analysere basale grafalgoritmer, f.eks. BFS, DFS og Dijkstras algoritme.
  • 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.
  • Implementere og afprøve datastrukturer og algoritmer, samt lave passende test og empiriske analyser af dem.
  • Være i stand til i et klart sprog at argumentere for valg foretaget i forbindelse med løsning af et problem.

Kursusindhold

Begrebet algoritme; begreberne graf og træ; rekursion og iteration; fundamentale algoritmer til sortering af data; teknikker til analyse af algoritmers effektivitet (køretidsanalyser); O-notation m.m.; elementære datastrukturer (stakke, køer, hægtede lister m.m.); avancerede datastrukturer (hobe, binære søgetræer m.m.); algoritmer på grafer (bredde-først søgning, dybde-først søgning, topologisk ordning m.m.). Grådige algoritmer og del-og-hersk algoritmer.

Anbefalede forudsætninger

02002/02003/02100/02101/02102/01017/01019, Et kursus i indledende programmering + et indledende kursus i diskret matematik. Eller tilsvarende kompetencer.

Undervisningsform

Forelæsninger og grupperegninger. Undervisningen udbydes parallelt på både engelsk og dansk såvidt muligt.

Se kurset i kursusbasen

Tilmelding

Sprog

Engelsk

Varighed

13 uger

Institut

Compute

Sted

DTU Lyngby Campus

Kursus ID 02105
Kursustype Bachelor
Semesterstart Uge 5
Semester slut Uge 19
Dage tors 8-12
Pris

7.500,00 kr.

0 pladser tilbage

Tilmelding