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.