Högskola och universitet hos Göteborgs universitet, 7,5 högskolepoäng.
Kursen ger kunskaper om:
Vad är en effektiv algoritm?
Verktyg för analys av algoritmer. O-notation. Analysera loopar och rekursiva anrop. Lösa rekursionekvationer.
Datastrukturer och algoritmer. Granskning av grundläggande datastrukturer.
Kombinera datastrukturer. Merge-and-find.
Grafalgoritmer.
Giriga algoritmer.
Divide-and-conquer.
Dynamisk programmering.
Backtracking och Implicita sökträd. Branch-and-bound.
Kort introduktion till lokala sök-och approximationsalgoritmer.
Grundläggande komplexitetsteori. Komplexitetsklasserna P, NP och NPC, reduktioner. Exempel på NP-fullständiga problem. Att hantera svåra problem.
Kort introduktion till andra designtekniker: lokal sökning, approximationsalgoritmer, randomiserade algoritmer, förbehandling, nätverksflöde.