Behörighetskrav

20 p matematik och 40 p datavetenskap, inkl.

Logik och bevisteknik DV1,

Algoritmer och datastrukturer DV1 och DV2,

Teknisk databehandling DV1,

Matematisk statistik DV1. Eller motsvarande

kurser.

Syfte

Att utveckla studenternas förmåga att

med algoritmer lösa problem, genom att lära ut avancerade algoritmiska tekniker för svåra problem.

Innehåll

Uttömmande sökmetoder, lokal sökning, branch-and-bound, evaluering av spelträd, dynamisk programmering, alpha-beta pruning, heuristisk lokal sökning, Kernighan-Lin's, sökning med variabel djup, tabu search, simulated annealing, linjärprogrammering, relaxations, randomiserade och approximativa algoritmer. Genetiska algoritmer. NP-hårda optimeringsproblem.

Undervisning

Seminarier.

Varje student utför ett projekt som kombinerar nämnda och eventuellt andra tekniker för att lösa ett svårt problem.

Examination

Uppgifter och/eller projekt.