Konstruktionsprinciper för algoritmer: dekomposition, giriga algoritmer, dynamisk programmering. Algoritmanalys. Probabilistiska algoritmer. Approximation. Tillämpningar med algoritmer för problem på mängder, grafer, aritmetik och geometri.
Beräkningsbarhet och komplexitet: reduktionsbegreppet, komplexitetsklasserna P (polynomisk tid) och NP (ickedeterministisk polynomisk tid) och NC (effektivt parallelliserbara problem), NP-fullständiga problem, oavgörbara problem.
Efter kursen ska studenten kunna
- utveckla och implementera algoritmer med datastrukturer och analysera dem med avseende på korrekthet och effektivitet,
- jämföra alternativa algoritmer med hänsyn till effektivitet och pålitlighet,
- definiera begreppen P, NP, NP-fullständighet, PSPACE och oavgörbarhet,
- jämföra problem med hänsyn till komplexitet med hjälp av reduktioner,
för att
- självständigt kunna konstruera datorprogram som effektivt utnyttjar tid och minne,
- i yrkeslivet kunna identifiera och angripa problem som är orealistiskt resurskrävande eller inte alls går att lösa med dator.