Algoritmer

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.