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.

Faglige forudsætninger

Algoritmer og Datastrukturer 1+2

Underviser

Gudmund Frandsen

Undervisnings- og arbejdsform

Forelæsninger (2+2t/uge)

Litteratur

Annonceres senere

Kursushjemmeside

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

 

Eksamensterminer

Juni/juli, reeksamen august

Udbyder

Datalogisk Institut

Tilmelding til undervisning

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

Studieordning og bedømmelse

Bacheloruddannelsen i datalogi

  • Hj.opg. + Multiple choice, bedømt efter 7-skala med intern censur

Bacheloruddannelsen i datalogi (1.del i datalogi-matematik)

  • Hj.opg. + Multiple choice, bedømt efter 7-skala med intern censur


Projekt og multiple choice
7-skala, ingen censur