Kompleksitetsteori

Mål:

Eit problem sin kompleksitet forklarar om eit problem i det heile let seg løyse ved hjelp av algoritmar og kor mykje ressursar (tid og plass) som i så fall krevst for å løyse problemet algoritmisk. Emnet går inn på problem som ikkje kan løysast og problem som det er vanskeleg å lage effektive algoritmar for. Vi ser på korleis vi kan kjenne att desse problema.

Innhald:

Emnet gir ein presis formell definisjon av algoritmeomgrepet (via Turingmaskinar). Hovudvekt blir lagt på sentrale kompleksitetsklassar, særleg NP-komplette problem.

Studenten skal ved avslutta emne ha følgjande læringsutbyte definert i kunnskapar, ferdigheiter og generell kompetanse:

Kunnskapar

Studenten

• har ein djupare forståing av kva ein algoritme er og kva for problem som kan løysast ved hjelp av ein algoritme.
• horstår samanhengen mellom formelle språk og Turingmaskinar.
• kjenner ulike kompleksitetsklassar og samanhengen mellom desse.

Ferdigheiter

Studenten

• kan kjenne att problem som ikkje kan løysast og NP-vanskelege problem.
• kan bevise NP-komplettheit for enkelte grunnleggjande vanskelege problem.
• kan utføre reduksjonar mellom ulike berekningsproblem

Generell kompetanse

Studenten

• kan kjenne att vanskelege problem, og bidra til forsking som går ut på å klassifisere nye problem som vanskelege eller handterlege.