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]

Approksimationsalgoritmer (Q3) ( forår 2010 - 5 ECTS )

Rammer for udbud

  • Uddannelsessprog: engelsk
  • Niveau: Kandidatkursus
  • Semester/kvarter: Q3
  • Timer per uge: Forelæsninger (2+2t/uge)
  • Deltagerbegrænsning: Ingen
  • Undervisningssted: Århus
  • Hovedområde: Det Naturvidenskabelige Fakultet
  • Udbud ID: 22135

Formål

Deltagerne vil efter kurset have indsigt i design og analyse af approksimationsalgoritmer og detaljeret kendskab til basale teknikker for approksimationsalgoritmer.

Obligatorisk program

Ugentlige opgaver

Indhold

Kurset fokuserer på design og analyse af polynomiel tids approksimationsalgoritmer med beviste kvalitetsgarantier for NP-hårde optimeringsproblemer. Målet er at forstå teknikker og algoritmiske paradigmer, som har bred anvendelighed. Vi vil specielt studere konkrete problemer spændende fra grafteori til skedulering (f.eks. Mængdedækning, Steiner træer, anlægslokalisering) og designe, analysere algoritmer med teknikker som grådige algoritmer, lokal søgning eller teknikker baseret på lineær programmering.

Faglige forudsætninger

Optimering (kan følges samtidigt)

Underviser

Peter Bro Miltersen og Nguyen Kim Thang

Undervisnings- og arbejdsform

Forelæsninger og øvelser

Litteratur

Approximation Algorithms, Vijay V. Vazirani, Springer-Verlag. Kursusnoter

Kursushjemmeside

http://www.cs.au.dk/~thang/Teaching/approx.html

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

  • beskrive og forklare basale begreber relateret til design og analyse af approksimationsalgoritmer.
  • diskutere teknikker og algoritmiske paradigmer.
  • anvende basale værktøjer til design og analyse af approksimationsalgoritmer.

Skemaplacering (forelæsninger)

http://cs.au.dk/studies/computer-science-programme/schedules/

Eksamensterminer

Marts, reeksamen efter aftale med underviseren.

Udbyder

Datalogisk Institut

Tilmelding til undervisning

http://mit.au.dk

Studieordning og bedømmelse


Tilvalgsfag: Datalogi

  • Mundtllig, bedømt efter 7-skala med intern censur


Mundtlig eksamen uden forberedelse (20 min)
7-skala, intern censur