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öruppgift 1 Krav föruppgift 2 Krav föruppgift 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 ettkorrekthetsbevis 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.