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]

Dynamiske algoritmer (Q4) ( forår 2009 - 5 ECTS )

Rammer for udbud

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

Formål

Deltagerne vil efter kurset have indsigt i design og analyse af dynamiske algoritmer og praktisk erfaring med implementation af dynamiske algoritmer. Kursets arbejdsform vil også træne deltagernes evne til at planlægge og gennemføre projekter, og til at læse og forstå videnskabelige artikler.

Indhold

I nogle anvendelser, hvor man ønsker at beregne en funktion mange gange, ændres input kun ganske lidt imellem de enkelte beregninger. Det indbyder til (om muligt) at genberegne funktionen uden at starte forfra hver gang. I kurset gennemgås konkrete eksempler på dynamiske algoritmer og deres analyse i et repræsentativt udvalg af anvendelsesområder: Grafalgoritmer, tekstalgoritmer, geometriske algoritmer, algebraiske algoritmer. Endvidere gennemgås teknikker og redskaber der anvendes i design og analyse af dynamiske algoritmer og datastrukturer: Balanceret-binær-træ teknik, global genopbygning, doven initialisering, van Emde Boas træer, sammenkædning og overskæring af træer, Euler-tur-træ datastrukturen, deterministisk møntkast .

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

skelne og forklare basale begreber indenfor dynamiske algoritmer.
beskrive og analysere kendte dynamiske algoritmer indenfor et repræsentativt udvalg af anvendelsesområder.
anvende og sammenligne kendte teknikker til design og analyse af dynamiske algoritmer.
implementere simple dynamiske algoritmer.
forudsige og analysere effektiviteten af foreslåede dynamiske algoritmer.
perspektivere brugen af dynamiske algoritmer som moduler i mere komplekse algoritmer.