NDAA04010G Algoritmer og datastrukturer (AD)

Årgang 2018/2019
Engelsk titel

Algorithms and Data Structures (AD)

Uddannelse

Bacheloruddannelsen i matematik

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å problemer, der kan løses i polynomiel tid.

Målbeskrivelser

Viden

  • Sorteringsalgoritmer.
  • Grafalgoritmer til bestemmelse af korteste veje og mindste udspændende træer.
  • Fibonacci heaps 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 vha. 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.
Undervisningsmateriale

Se Absalon for kursuslitteratur.

Grundlæggende programmeringserfaring samt kendskab til grafer, bevisteknikker (f.eks. bevis ved induktion og modstridsbevis) og asymptotisk notation. Hvis du er i tvivl om, hvorvidt dine forudsætninger er tilstrækkelige, bør du kontakte den kursusansvarlige.
Spørgetimer, øvelsestimer og forventeligt videooptagelser af forelæsninger.
Kurset er identisk med NDAA04010U Algoritmer og datastrukturer (AD), men er kun åbent for studerende på bacheloruddannelsen i matematik på specialisering i matematik-datalogi.
Kurset udbydes kun i studieåret 2018-19.
  • Kategori
  • Timer
  • Eksamen
  • 1
  • E-læring
  • 28
  • Forberedelse
  • 149
  • Teoretiske øvelser
  • 28
  • I alt
  • 206
Skriftlig
Individuel
Løbende feedback i undervisningsforløbet
Point
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.
Krav til indstilling til eksamen

En forudsætning for at gå op til eksamen er godkendelse af 4 ud af 5 skriftlige ugentlige opgaver.

Hjælpemidler
Alle hjælpemidler tilladt
Bedømmelsesform
7-trins skala
Censurform
Ekstern censur
Reeksamen

Kvalificering til reeksamen opnås ved aflevering af og godkendelse af 4 ud af 5 opgaver senest 2 uger før reeksamen. 

Reeksamensform er samme som ordinær eksamen.

 

Kriterier for bedømmelse

Se målbeskrivelsen.