Algoritmer og datastrukturer (AD)

Kursusindhold

Kursets formål er at præsentere en række algoritmiske paradigmer (herunder del og hersk, grådige algoritmer og dynamisk programmering), samt at introducere en række analyseværktøjer (korrekthed, køretid, pladsbehov). Fokus er på teoretisk analyse af algoritmer og datastrukturer. Kurset beskæftiger sig med algoritmiske problemer, der kan løses i polynomiel tid.

Engelsk titel

Algorithms and Data Structures (AD)

Uddannelse

Bacheloruddannelsen i datalogi
Bacheloruddannelsen i datalogi-økonomi
Bacheloruddannelsen i machine learning og datavidenskab

Målbeskrivelse

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 så som del og hersk, dynamisk programmering og grådige algoritmer.
  • Foretage asymptotisk kompleksitetsanalyse af algoritmer og datastrukturer (herunder løsning af rekursive ligninger).
  • Argumentere for korrekthed af algoritmer og datastrukturer vha. induktion (herunder formulering af løkkeinvarianter) samt direkte og modstridsbeviser.

 

Kompetencer

  • Anvende passende algoritmer og datastrukturer på nye problemstillinger.
  • Anvende algoritmiske paradigmer på nye problemstillinger.

Forelæsninger og øvelsestimer.

Se Absalon for kursuslitteratur.

Grundlæggende programmeringserfaring samt kendskab til grafer, bevisteknikker (f.eks. bevis ved induktion og modstridsbevis), asymptotisk notation og simple datastrukturer så som lister og stakke. Hvis du er i tvivl om, hvorvidt dine forudsætninger er tilstrækkelige, bør du kontakte den kursusansvarlige.

Skriftlig
Individuel
Kollektiv
Løbende feedback i undervisningsforløbet
ECTS
7,5 ECTS
Prøveform
Skriftlig prøve, 4 timer med opsyn.
Hjælpemidler
Kun visse hjælpemidler tilladt

Visse hjælpemidler tilladt: computer, noter, opgaver og lærebøger

Bedømmelsesform
7-trins skala
Censurform
Ekstern censur
Kriterier for bedømmelse

Se målbeskrivelsen.

Enkeltfag dagtimer (tompladsordning)

  • Kategori
  • Timer
  • Forelæsninger
  • 28
  • Forberedelse (anslået)
  • 96
  • Teoretiske øvelser
  • 78
  • Eksamen
  • 4
  • Total
  • 206

Kursusinformation

Undervisningssprog
Dansk
Kursusnummer
NDAA04010U
ECTS
7,5 ECTS
Niveau
Bachelor
Varighed

1 blok

Placering
Blok 3
Skemagruppe
C
Kapacitet
Ingen begrænsning
Der kan være færre pladser i eftertilmeldingsperioden
Studienævn
Studienævn for Matematik og Datalogi
Udbydende institut
  • Datalogisk Institut
Udbydende fakultet
  • Det Natur- og Biovidenskabelige Fakultet
Kursusansvarlig
  • Christian Wulff-Nilsen   (7-7d81817e81818c52767b407d8740767d)
Underviser

Christian Wulff-Nilsen
Pawel Winter

Gemt den 18-03-2022

Are you BA- or KA-student?

Are you bachelor- or kandidat-student, then find the course in the course catalog for students:

Courseinformation of students