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]

Approximationsalgorithmer Q3 Honours Version ( 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: 22259

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 og præsentation af en forskningsartikel

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. Anvendelse af kursets teknikker til at diskutere og reflektere over de nyeste forskningsartikler.

Faglige forudsætninger

Optimering (kan følges samtidigt)

Underviser

Peter Bro Miltersen og Nguyen Kim Thang

Undervisnings- og arbejdsform

Forelæsninger og øvelser

Engelsk

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.
  • reflektere over løsningsbegreber og -teknikker i relation til konkrete problemer.
  • diskutere nyeste resultater for konkrete problemområder.

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

Bedømmelse

  • Mundtlig, bedømt efter 7-skala med intern censur
    • 5 xxxxx

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