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 2010 - 5 ECTS )

Rammer for udbud

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

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

Peter Bro Miltersen and Troels Bjerre Sørensen

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/da/index.cfm

Studieordning og bedømmelse

2. del af sidefaget i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Bacheloruddannelsen i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

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

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Grundfaget i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Kandidatuddannelsen i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Sidefag i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Sidefaget i datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur

Tilvalgsfag: Datalogi

  • Mundtlig, bedømt efter 7-skala med ekstern censur


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