NDAA04010U Algoritmer og datastrukturer (AD)

Årgang 2014/2015
Engelsk titel

Algorithms and Data Structures (AD)

Uddannelse
Bacheloruddannelsen i datalogi
Bacheloruddannelsen i naturvidenskab og it
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å polynomielle problemer.

Indhold:

 

  • Del og hersk
  • Dynamisk programmering
  • Grådige algoritmer
  • Sortering
  • Grafalgoritmer
  • Korrekthedsbeviser

 

Målbeskrivelser

 

 

Kompetencer

 

 

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


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.
  • Anvende  passende datastrukturer på nye problemstillinger.
  • Argumentere for korrekthed af algoritmer v.h.a. induktion (herunder formulering af løkkeinvarianter) samt direkte og modstridsbeviser.


Viden

 

 

 

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

 

 

Diskrete matematiske strukturer eller Mat. Intro og Lineær Algebra. De studerende forventes bl.a. at have kendskab til grafer, induktionsbeviser og "Store-O" notation. Studerende med manglende forudsætninger bør kontakte den kursusansvarlige.
Forelæsninger og øvelsestimer
  • Kategori
  • Timer
  • Eksamen
  • 1
  • Forberedelse
  • 149
  • Forelæsninger
  • 28
  • Teoretiske øvelser
  • 28
  • I alt
  • 206
Point
7,5 ECTS
Prøveform
Mundtlig prøve, 30 minutter
De skriftlige ugentlige 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 en godkendelse af 4 ud af 5 skriftlige ugentlige opgaver.

Er kravene ikke opfyldt, kan de opfyldes inden reeksamen. De 5 skriftlige opgaver, hvoraf mindst 4 skal godkendes, afleveres senest to uger inden tilmeldingsperioden til reeksamen slutter.
Bedømmelsesform
7-trins skala
Censurform
Ekstern censur
Kriterier for bedømmelse

Se målbeskrivelser.