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

Rammer for udbud

Uddannelsessprog: (se under Undervisnings- og arbejdsform)
Niveau: Obligatorisk overbygningskursus
Semester/kvarter: Q4 i 2007/2008
Timer per uge: 6
Deltagerbegrænsning:
Undervisningssted: Århus
Hovedområde: Det Naturvidenskabelige Fakultet
Udbud ID: 7834

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.