Randomiserede algoritmer til dataanalyse (RAD)

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 og store datastrømme med relevans for maskinlæring og dataanalyse, 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.

Engelsk titel

Randomised Algorithms for Data Analysis (RAD)

Uddannelse

Bacheloruddannelsen i datalogi

Målbeskrivelse

Viden om:

Relevant kombinatorisk sandsynlighedsteori og randomiserede teknikker i algoritmik:

  • Varians og spredning
  • Haleuligheder
  • Randomiserede datastrukturer
  • Randomiserede 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


Kompetencer til at:

  • Ræsonnere om og anvende randomiserede teknikker til dataanalyseproblemer
  • Finde simple og effektive randomiserde algoritmer og datastrukturer, hvor traditionelle deterministiske metoder er vanskeligere eller mindre effektive

Forelæsninger, øvelser, ugeopgaver og et implementeringsprojekt.

Se Absalon.

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".

Skriftlig
Individuel
Kollektiv
Løbende feedback i undervisningsforløbet
ECTS
7,5 ECTS
Prøveform
Mundtlig prøve, 30 minutter
Prøveformsdetaljer
Der er 30 minutters forberedelse til den mundtlige eksamen
Hjælpemidler
Alle hjælpemidler tilladt
Bedømmelsesform
7-trins skala
Censurform
Ekstern censur
Kriterier for bedømmelse

Se læringsmålene.

Enkeltfag dagtimer (tompladsordning)

  • Kategori
  • Timer
  • Forelæsninger
  • 28
  • Forberedelse (anslået)
  • 100
  • Teoretiske øvelser
  • 28
  • Øvelser
  • 24
  • Projektarbejde
  • 25
  • Eksamen
  • 1
  • Total
  • 206

Kursusinformation

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

1 blok

Placering
Blok 4
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-6d71716e71717c42666b306d7730666d)
Underviser

Mikkel Thorup & Christian Wulff-Nilsen.

Gemt den 28-02-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