Effektiva algoritmer 7,5 hp

Om kursen

Kursen behandlar tekniker för att konstruera effektiva algoritmer och typiska datastrukturer som används i dessa. Speciell hänsyn tas till att effektivitet inte bara beror på algoritmens inneboende asymptotiska beteende utan också på de specifika probleminstanser den appliceras på. Standardalgoritmer och -datastrukturer behöver därför ofta väljas ut och anpassas för att lösa problemet så effektivt som möjligt.

Modul 1, Algoritmiska tekniker och datastrukturer, 3 hp, behandlar effektiva algoritmiska tekniker (divide-and-conquer, greedy, dynamic programming) deras användningsområden och för- och nackdelar, illustrerar dessa med hjälp av centrala algoritmer, och diskuterar exempel på effektiva datatyper (t.ex. heaps, red-black trees, union-find) och deras implementation.

Modul 2, Problemlösning och algoritmanalys, 4,5 hp,
utgörs av att studenten både teoretiskt och empiriskt undersöker varianter av en känd algoritm med avseende på effektivitet och skriver en rapport om detta. Hela kedjan från initiala, vanligen otydligt specificerade frågeställningar till den färdiga algoritmiska lösningen och dess teoretisk och empirisk analys ingår. Modulen tränar studentens förmåga att gå från en otydlig formulerad problemspecifikation till en exakt formulering, ta fram en lämplig algoritmisk lösning, om möjligt förbättra den genom att anpassa den till problemets säregenheter, samt analysera och diskutera dess effektivitet.