| Fagligt indhold: | This course is concerned with the solution of
computationally hard problems.
Some well-known
problems, like Shortest Path or Minimum Spanning Tree,
enjoy the existence of efficient and exact algorithms, which
are the subject of classical algorithms courses. However,
many other problems (notably many of those encountered in
practice) like scheduling, network planning,
or register allocation, do not admit such an algorithm (at
least we don\'t know one). Instead, one must turn to a
growing class of optimization techniques: - genetic
algorithms, - simulated annealing,
- branch-and-bound,
- local
search, - approximation algorithms,
-
pseudopolynomial
algorithms, - parameterised complexity,
- randomised
algorithms, and relaxations to linear programs.
<br/>
This course presents most of these techniques, and
introduces their theoretical underpinnings, which are
considerably less well developed than classical algorithms
theory.<br/> But the main focus of the course is practical:
students implement the techniques in weekly assignments
and perform experiments on data sets of realistic sizes --
the absence of a satisfying theory in this area necessitates an
experimental approach for providing quantitative
comparisons between the many paradigms.
About the title: \"Combinatorial optimisation\" is the
traditional term for this area, although it goes my many
other names as well. \"Optimisation\" of course refers to
finding the best or cheapest solution to the given problem,
unlike for example sorting, searching, or addition, where
there is only one solution (which is even easy to find!).
\"Combinatorial\" refers to the universe of problems studied,
and includes graphs, strings, etc, as opposed to \"numerical
optimisation\" (also just called \"optimisation\") which
optimises continuous functions and is studied at Numerical
Analysis departments.
--
Kurset er en introduktion til \"optimeringslære\", dvs. løsning
af svære beregningsproblemer. For nogle få sådanne
problemer kendes kendes effektive og eksakte algoritmer, fx
Korteste Veje eller Letteste Udspændende Træ, hvilket er
genstand for klassiske algorimekurser. Men desværre tillader
de fleste praktiske problemer, som fx skemalægning,
netværksdesign, registertildeling, ingen (kendt) effektiv og
eksakt algoritme. I stedet må man ty til en efterhånden stor
klasse af optimeringteknikker: genetiske algoritmer,
simuleret udglødning (simulated annealing), branch-and-
bound, lokalsøgning, approximationsalgoritmer,
pseudopolynomielle algoritmer, parameteriseret
kompleksitet, randomiserede algoritmer, og slækning til
lineær programmering.
Kurset præsenterer de fleste af disse teknikker, og
introducerer deres teoretiske fundament, som dog er
betydeligt mindre veludbygget en den klassiske
algoritmeteoris. Men kurset fokus er først og fremmest
praktisk: i ugentlige programmeringsopgaver implementer
studenterne teknikkerne i løbet af kurset og udfører
eksperimenter på datamængder af realistisk størrelse --
fraværet af en tilfredsstillende teoridannelse på dette
område nødvendiggør nemlig en eksperimentel tilgang til
kvalitative sammenligninger af de forskellige paradigmer.
Ordforklaring: \"Optimering\" hentyder selvfølgeligt til at finde
den bedste eller billigste løsning til et givet problem, i
modsætning til fx søgning, sortering eller addition, som er
exakte problemer med kun en løsning (desuden er den nem
at finde). Betegnelsen \"kombinatorisk optimering\" skal
forstås i modsætning til \"numerisk optimering\" (også bare
kaldt \"optimering\"), en klassisk matematisk disciplin, som
involverer kontinuerte funktioner, og som i dag hører
hjemme på institutter for Numerisk Analyse.
|
Kursusoversigt