Kompleksitetsteori
Masteremne
- Studiepoeng
- 10
- Undervisningssemester
- Vår
- Emnekode
- INF235
- Talet på semester
- 1
- Undervisningsspråk
- Engelsk. Norsk om kun norskspråklege studentar deltek
- Ressursar
- Timeplan
- Litteraturliste
Emnebeskrivelse
Mål og innhald
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.
Læringsutbyte
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.
- Forstå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.
- Bevise NP-komplettheit for enkelte grunnleggjande vanskelege problem.
- 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.
Fulltid/deltid
Studiepoeng, omfang
Studienivå (studiesyklus)
Undervisningssemester
Undervisningsstad
Krav til forkunnskapar
Tilrådde forkunnskapar
Studiepoengsreduksjon
Krav til studierett
Arbeids- og undervisningsformer
Undervisninga gjevast i form av førelesningar og gruppeøvingar.
Førelesningar 4 timer i veka, gruppeøvingar 2 timer i veka.
Obligatorisk undervisningsaktivitet
Godkjente obligatoriske oppgåver.
Obligatoriske aktiviteter er gyldige i to semester, det semesteret aktiviteten godkjennes samt det påfølgjande semesteret.
Vurderingsformer
Opp til 30% av karakteren blir satt på grunnlag av aktivitet i løpet av semesteret, som innleveringsoppgåver og midtsemestereksamen i førelesningstimane. Informasjon om aktivitet som teller på karakteren og vekting av desse vil bli gjeve i byrjinga av semesteret.