Detaljerade bedömningskriterier för mästarprov 2

Mästarprov 2 betygsätts efter betygskriterierna för målen jämföra problem med hänsyn till komplexitet med hjälp av reduktioner samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet definiera och översätta begreppen P, NP, NP-fullständighet och oavgörbarhet naturligt att övas vid redovisningen.

För att det ska bli extra tydligt hur dom tre uppgifterna bedöms och för att dom assistenter som tar emot muntliga redovisningar ska hålla precis samma kravnivå finns det detaljerade bedömningskriterier, som assistenterna bedömer både skriftligt och muntligt på ett bedömningsprotokoll.

Följande tabell visar kraven för dom olika uppgifterna.

Bedömningsgrund	Krav för uppgift 1	Krav för uppgift 2	Krav för uppgift 3
NP-fullständighet/NP-tillhörighet
Förklarar principerna för NP-fullständighetsbevis	ja	nej	-
Formulerar problemet som beslutsproblem	-	ja	-
Förklarar vad en lösning består av	ja	ja	-
Visar NP-tillhörighet	ja	ja	-
Motiverar att verifikationsalgoritmen (motsv.) är polynomisk	ja	ja	-
Reduktionsalgoritm
Beskriver reduktionen övergripande i ord och ev. i bild	måttliga	måttliga	höga
Beskriver reduktionen tydligt	ja	ja	ja, med pseudokod
Reduktionen är korrekt	ja	ja	ja
Tidskomplexitet för reduktionen
Reduktionen är polynomisk	ja	ja	ja
Anger tidskomplexitet i lämpliga variabler	ja	ja	ja
Motiverar tidskomplexitet	måttliga	höga	höga
Korrekthetsresonemang
Redogör för vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ	ja	ja	ja
Framställer grundläggande idé för korrekthetsresonemanget	nej	ja, åtminstone åt ena hållet	ja
Genomför ett fullständigt korrekthetsresonemang	nej	ja	ja

Ovanstående krav ska vara uppfyllda efter den muntliga redovisningen. Kraven på den skriftliga lösningen är något lägre.