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]

Kombinatorisk Søgning (Q4) ( forår 2011 - 5 ECTS )

Rammer for udbud

  • Uddannelsessprog: engelsk
  • Niveau: Kandidatkursus
  • Semester/kvarter: Q4
  • Timer per uge: 6
  • Deltagerbegrænsning: Ingen
  • Undervisningssted: Århus
  • Hovedområde: Det Naturvidenskabelige Fakultet
  • Udbud ID: 27093

Formål

Deltagerne vil efter kurset have indsigt i NP-hårdhed.

Obligatorisk program

Tre obligatoriske opgaver

Indhold

Kompleksitetsklasserne P, NP and NPC. Polynomieltidsreduktioner. NP-hårdhed af konkrete problemer, deriblandt problemer fra kombinatorisk optimering, såsom "the traveling salesman problem". Approximationsalgoritmer og heuristikker for NP-hårde kombinatorisk optimeringsproblemer, specielt "the traveling salesman problem".

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

  • klassificere problemer som NP-hårde eller polynomiel tids løselige.
  • beskrive og vurdere approximationsalgoritmer og heuristikker til at opnå approximative løsninger.

Faglige forudsætninger

Optimering

Underviser

Kristoffer Arnsfelt Hansen og Peter Bro Miltersen

Undervisnings- og arbejdsform

Forelæsninger (3t/uge), holdøvelser (3t/uge)

Litteratur

Annonceres senere

Kursushjemmeside

http://www.cs.au.dk/dKS

Skemaplacering (forelæsninger)

Blokpar F, onsdag 14-16 + fredag 12-14

Eksamensterminer

Eksamen: 4. kvarter

Placering: Uge 23

Reeksamen: August

http://science.au.dk/uddannelse/undervisning/eksamen/regler-for-tilmelding-til-kurser-med-fastlagt-eksamen/

 

Udbyder

Datalogisk Institut

Tilmelding til undervisning

https://mit.au.dk/

Bedømmelse

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