Randomiserede algoritmer (Q3) (5 ECTS)

Formål

Deltagerne vil efter kurset have indsigt i brug af randomisering ved design og analyse af algoritmer og praktisk erfaring med implementation af randomiserede algoritmer. Kursets arbejdsform vil også træne deltagernes evne til at planlægge og gennemføre projekter.

Indhold

Mange problemer løses simplere og mere effektivt med adgang til en kilde af tilfældige bits, fremfor uden en sådan adgang. I kurset gennemgås konkrete eksempler på randomiserede algoritmer og deres analyse i et repræsentativt udvalg af modeller og anvendelsesområder: Algoritmiske modeller hvor randomisering (kan) anvendes: Monte Carlo og Las Vegas algoritmer, on-line algoritmer og kompetitiv analyse, datastrukturer, distribuerede algoritmer, parallelle algoritmer, approksimationsalgoritmer. Anvendelsesområder: Grafalgoritmer, geometriske algoritmer, algebraiske algoritmer, talteoretiske algoritmer, kombinatorisk optimering, kryptografi. Endvidere gennemgås basale redskaber fra sandsynlighedsteori og probabilistisk analyse: Sum af indikatorvariabler; spilteoretiske teknikker og Yao's nedre grænse teknik; Chernoff grænser .

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

• skelne og forklare basale begreber vedrørende randomiserede algoritmer og analyse af randomiserede algoritmer.
• beskrive og analysere kendte randomiserede algoritmer indenfor et repræsentativt udvalg af algoritmiske modeller og anvendelsesområder.
• anvende basale redskaber fra sandsynlighedsteori og probabilistisk analyse ved design og analyse af algoritmer og datastrukturer.
• implementere randomiserede algoritmer på standard hardware (uden adgang til ægte tilfældige bits).
• forudsige og analysere nytten af en foreslået brug af randomisering ved løsning af konkrete problemer.
• perspektivere brugen af ægte tilfældighed og pseudotilfældighed ved løsning af algoritmiske problemer.

Faglige forudsætninger

dADS1+2, Matematical Modelling 1

Underviser

Gudmund Frandsen

Undervisnings- og arbejdsform

Forelæsninger (2+2t/uge)

Litteratur

Annonceres senere

Kursushjemmeside

http://www.daimi.au.dk/~gudmund/RanAlg/

Udbyder

Datalogisk Institut

Tilmelding til undervisning

http://www.brics.dk/~mis/enrollment.html

Rammer for udbud

• Niveau: Valgfrit overbygningskursus
• Semester/kvarter: Q3 i 2007/2008
• Timer per uge: 4
• Prøveform: Projekt og multiple choice
  7-skala, ingen censur
• Undervisningssprog: Dansk eller engelsk
• Deltagerbegrænsning: