Søgning og optimering
Motivation:En væsentlig del af de problemer man møder i industrien kan formuleres som søge- eller optimeringsproblemer over et meget stort rum af mulige løsninger. Eksempler går fra software til løsning af logistiske problemer såsom distribution af varer, over software til web server caching, til software der kan slå Kasparov i skak. Mange af disse søge- og optimeringsproblemer er svære, i den forstand at der ikke kendes algoritmer for dem for hvilke man både kan garantere en hurtig udførselstid og en optimal løsning. For disse problemer kan heuristiske teknikker ofte finde tilfredsstillende løsninger.
Mål: Målet med kurset er at få erfaring med at:
- identificere lette problemer som kan løses optimalt og effektivt,
- identificere svære problemer for hvilke dette ikke er tilfældet,
- bruge algoritmiske teknikker til de første og heuristiske til de sidste.
Emner: Algoritmer for strømning i netværk og lineær programmering. Kompleksitetsklasserne P og NP. NP-fuldstændighed. Analyse af eksponentielle søge-algoritmer. Branch and Bound. Approximationsalgoritmer. Heuristikker baseret på lokal søgning.
Forelæsere
Peter Bro Miltersen og Sven Skyum
Litteratur
Search and Optimization I, II og III
Forelæsninger
3 timer/uge
Øvelser
3 timer/uge
Obligatoriske opgaver
Der stilles en obligatorisk afleveringsopgave hver anden uge. Det er en forudsætning for kurset, at opgavebesvarelserne som helhed har været tilfredsstillende
Forudsætninger
dADS, dModLog og SS1. dModLog og SS1 kan tages sideløbende
Eksamensform
Mundtlig eksamen, 13-skalaen
Sprog
Dansk
ECTS
10
Kvarter
3+4