Effektiva algoritmer och problemkomplexitet, 7.5 hp
Om kursen
Moment 1 av kursen behandlar centrala begrepp och resultat kring effektiva algoritmiska tekniker å ena sidan och problemkomplexitet å andra sidan. Algoritmiska tekniker som behandlas omfattar divide-and-conquer, greedy methods och dynamic programming samt deras analys med avseende på effektivitet. I samband med begreppet problemkomplexitet diskuteras i första hand klasserna P och NP samt reduktion och NP-fullständighet. Kursens huvudfokus ligger på värsta-fall-analyser och algoritmernas tidseffektivitet, men även genomsnittlig effektivitet och algoritmers eller problems krav på minnesutrymme diskuteras.
Moment 2 består av ett antal påbyggnadsområden som studenten får välja ibland. Utbudet av dessa områden kan variera. Typiska exempel omfattar
- analys av konkreta program med hjälp av profiling software,
- effektiva algoritmer och problemkomplexitet inom området Automater och formella språk,
- effektiva parallella algoritmer och relaterade komplexitetsklasser.
Utbildningsnivå: Avancerad nivå
Kursmeny
