Search and Optimization
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
Eksamensform
Mundtlig eksamen, 13-skalaen
Sprog
Dansk
Point
10 ECTS
Semester
Forår