Behörighetskrav

Matematik 20 poäng och datavetenskap 30 poäng, inklusive Algoritmer och

datastrukturer DV2 eller motsvarande kunskaper.

Syfte

Att utöka kunskaper och färdigheter kring algoritmer utöver tidigare kurser i algoritmer och datastrukturer. Avancerad analys av algoritmer med kombinatoriska och probabilistiska metoder.

Innehåll

Avancerade algoritmer och metoder för deras analys. Undre gräns för komplexitet baserad på informationsteori och spelteori. Randomiserade algoritmer och datastrukturer, NP-fullständighet,

approximeringsalgoritmer för NP-hårda optimeringsproblem, parallella algoritmer och sorterande nät.

Undervisning

Föreläsningar och övningar.

Examination

Skriftligt prov vid kursens slut. Obligatoriska uppgifter utgör en del av

examinationen.