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 2009 - 5 ECTS )

Rammer for udbud

Uddannelsessprog: engelsk (eller dansk)
Niveau: Kandidatkursus
Semester/kvarter: Q3
Timer per uge: 4
Deltagerbegrænsning: Ingen
Undervisningssted: Århus
Hovedområde: Det Naturvidenskabelige Fakultet
Udbud ID: 13855

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.

Obligatorisk program

The participants must at the end of the course be able to:

distinguish and explain basic concepts related to randomized algorithms and analysis of randomized algorithms.
describe and analyze known randomized algorithms within a representative selection of algorithmic models and application areas.
apply basic tools from probability theory and probabilistic analysis for design and analysis of algorithms and data structures.
implement randomized algorithms on standard hardware (without access to truly random bits).
predict and analyze the usefulness of a proposed application of randomization in the solution of a concrete problem.
perspectivate the use of true randomness and pseudo randomness for solving algorithmic problems.

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.