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.