Till KTH:s startsida Till KTH:s startsida

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 föreskrivna 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.