NDAB18001U Randomiserede algoritmer til dataanalyse (RAD)

Årgang 2018/2019
Engelsk titel

Randomized Algorithms for Data Analysis (RAD)

Uddannelse

Bacheloruddannelsen i datalogi

Kursusindhold

Randomiserede algoritmer er ofte deres traditionelle deterministiske modstykker overlegne.  Mange beregningsproblemer er i praksis umulige uden brug af randomisering.

Anvendelsesområder såsom grafalgoritmer, maskinlæring, distribueret databehandling, og geometri vil behandles, men fokus vil være på den grundlæggende forståelse for at give den studerende det nødvendige grundlag for at forstå og bruge sandsynligheder i algoritmer og dataanalyse.

Målbeskrivelser

Viden om:

Relevant kombinatorisk sandsynlighedsteori og randomiserede teknikker i algoritmik:

  • Varians og spredning
  • Haleuligheder
  • Den probabilistiske metode
  • Randomiserede datastrukturer
  • Randomiserede geometriske algoritmer
  • Randomiserede grafalgoritmer
  • Randomiserede distribuerede og parallelle algoritmer
  • Analyse af store datastrømme


Færdigheder i at:

  • Vise grænser for forventet køretid af randomiserede algoritmer
  • Forklare metoder til at begrænse sandsynligheden for, at en tilfældig variabel afviger langt fra dens forventede værdi
  • Anvende probabilistiske metoder, f.eks. til at bevise eksistens af algoritmer
  • Finde simple og effektive randomiserde algoritmer og datastrukturer, hvor traditionelle deterministiske metoder er vanskeligere eller mindre effektive


Kompetencer til at:

  • Ræsonnere om og anvende randomiserede teknikker til dataanalyseproblemer
Undervisningsmateriale

Forventes at være "Randomized Algorithms" af Motwani and Raghavan

Grundlæggende sandsynlighedsregning svarende til kurset "Matematisk analyse og sandsynlighedsteori i datalogi" eller "Matematisk analyse og statistik i datalogi" samt grundlæggende algoritmik svarende til kurset "Algoritmer og datastrukturer".
Forelæsninger, øvelser, ugeopgaver og et implementeringsprojekt.
  • Kategori
  • Timer
  • Eksamen
  • 1
  • Forberedelse
  • 100
  • Forelæsninger
  • 28
  • Projektarbejde
  • 25
  • Teoretiske øvelser
  • 28
  • Øvelser
  • 24
  • 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 implementeringsprojektet samt 3 ud af 4 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 implementeringsprojekt samt 3 ud af 4 ugeopgaver senest 2 uger før reeksamen. 

Reeksamensform er samme som ordinær eksamen.

Kriterier for bedømmelse

Se læringsmålene.