Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Randomiserede algoritmer (Q3) ( forår 2008 - 5 ECTS )

Rammer for udbud

Uddannelsessprog: (se under Undervisnings- og arbejdsform)
Niveau: Valgfrit overbygningskursus
Semester/kvarter: Q3 i 2007/2008
Timer per uge: 4
Deltagerbegrænsning:
Undervisningssted: Århus
Hovedområde: Det Naturvidenskabelige Fakultet
Udbud ID: 7978

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.