Algoritmer og datastrukturer (AD)

Kursusindhold

Kursets formål er at præsentere en række algoritmiske paradigmer (herunder del-og-hersk, det grådige princip og dynamisk programmering), samt at introducere en række analyseværktøjer (korrekthed, køretid, pladsbehov). Fokus er på polynomielle problemer.

Engelsk titel

Algorithms and Data Structures (AD)

Uddannelse

Bacheloruddannelsen i datalogi
Bacheloruddannelsen i naturvidenskab og it
Bacheloruddannelsen i matematik

Målbeskrivelse

Viden

  • Sorteringsalgoritmer.
  • Grafalgoritmer til bestemmelse af korteste veje og mindste udspændende træer.
  • Hobe og binære søgetræer.
  • Amortiseret analyse.
  • Del og hersk.
  • Dynamisk programmering.
  • Grådige algoritmer.
  • Korrekthedsbeviser.

 

Færdigheder

  • Genkende algoritmiske paradigmer (for eksempel del og hersk, dynamisk programmering, grådige algoritmer) og anvende dem på nye problemstillinger.
  • Foretage asymptotisk kompleksitetsanalyse af algoritmer (herunder løsning af rekursive ligninger).
  • Anvende  passende datastrukturer på nye problemstillinger.
  • Argumentere for korrekthed af algoritmer v.h.a. induktion (herunder formulering af løkkeinvarianter) samt direkte og modstridsbeviser.

 

Kompetencer

  • Evaluere hvilke paradigmer og datastrukturer er velegnede til at løse nye algoritmiske problemer.

Forelæsninger og øvelsestimer

Grundlæggende programmeringserfaring samt kendskab til grafer, induktionsbeviser og asymptotisk notation, matricer og vektorer. Studerende med manglende forudsætninger bør kontakte den kursusansvarlige.

ECTS
7,5 ECTS
Prøveform
Mundtlig prøve, 30 minutter med 30 minutters forberedelse
De skriftlige ugentlige opgaver kan danne grundlag for spørgsmål ved den mundtlige eksamen.
Bedømmelsesform
7-trins skala
Censurform
Ekstern censur
Kriterier for bedømmelse

Se målbeskrivelser.

Enkeltfag dagtimer (tompladsordning)

  • Kategori
  • Timer
  • Forelæsninger
  • 28
  • Teoretiske øvelser
  • 28
  • Forberedelse
  • 149
  • Eksamen
  • 1
  • Total
  • 206