Betygskriterier
Målrelaterade betygskriterier i DD1352
Algoritmer, datastrukturer och komplexitet
| mål | E | D | C | B | A |
|---|---|---|---|---|---|
| utveckla algoritmer med datastrukturer | för enkla problem givet en konstruktionsmetod | för icketriviala problem givet ledtråd | för icketriviala problem | för svårare problem | för svårare problem med den metod som passar bäst |
| examineras med labbar (för nivå E), mästarprov 1 och muntlig tenta | |||||
| implementera algoritmer med datastrukturer | efter funktionsspecifikation och efter detaljerad algoritmisk specifikation, med hänsyn taget till effektivitet | ||||
| examineras med labbar | |||||
| analysera algoritmer med avseende på effektivitet | förklara principerna, analysera enklare algoritmer | analysera rekursiva algoritmer med mästarsatsen | analysera svårare algoritmer | ||
| examineras med labbar och teoritenta (för nivå E), mästarprov 1 och muntlig tenta | |||||
| analysera algoritmer med avseende på korrekthet | förklara principerna, förstå ett givet korrekthetsbevis | genomföra enklare korrekthetsbevis | resonera med invarianter och induktion | ||
| examineras med mästarprov och muntlig tenta | |||||
| jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet examineras med labbar, teoritenta och mästarprov 1 |
|||||
| definiera begreppen P, NP, NP-fullständighet och oavgörbarhet examineras med teoritenta och mästarprov 2 |
|||||
| jämföra problem med hänsyn till komplexitet med hjälp av reduktioner | förklara principerna, utföra enklare reduktioner mellan givna problem | visa NP-fullständighet givet ledtråd | visa NP-fullständighet och oavgörbarhet | göra konstruktionsreduktioner givet ledtråd | göra konstruktionsreduktioner |
| examineras med labb 4 (för nivå E), mästarprov 2 och muntlig tenta | |||||
| förklara hur man kan hantera problem med hög komplexitet | förklara behovet | förklara principerna | konstruera enkla heuristiker och totalsökningsalgoritmer | konstruera och analysera enklare approximationsalgoritmer eller heuristiker | konstruera och analysera approximationsalgoritmer eller heuristiker, eller visa undre gränser för approximation |
| examineras med teoritenta (upp till betyg C) och muntlig tenta eller labb 4-extrauppgift (för betyg A+B) |
|||||
Kursen har tre graderade Ladokmoment: mästarprov 1, mästarprov 2 och tenta.
Slutbetyget är det lägsta av dessa tre betyg.