bild
Skolan för
elektroteknik
och datavetenskap

Examination i Algoritmer och komplexitet, hösten 2009

Följande betygskriterier kommer att tillämpas. Du måste uppfylla alla kriterier på det betyg du ska få.

Betygskriterier i DD2354 Algoritmer och komplexitet

Nedanstående betygskriterier bygger på kursens lärandemål och är utformade efter den nya betygsskalan A, B, C, D, E där A är högst betyg. För den som är registrerad på den gamla kursen 2D1354 används betygsskalan 5, 4, 3 där A=5, C=4, E=3.

målEDCBA
utveckla algoritmer 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 mästarprov 1 och muntlig tenta
analysera algoritmer med avseende på effektivitet förklara principerna, analysera enklare algoritmer analysera rekursiva algoritmer med mästarsatsen analysera svårare algoritmer
examineras med mästarprov 1, teoritenta 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 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 teoritenta (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 (för nivå C) och muntlig tenta

Kursen har tre obligatoriska moment i Ladok:

  • MAS1, mästarprov 1, 1,5 hp
  • MAS2, mästarprov 2, 1,5 hp
  • TEN2, tenta, 3 hp
Nedan finns detaljerad information om dessa moment.

Individuella uppgifter: mästarprov

Två obligatoriska individuella uppgifter, mästarprov, kommer att delas ut. Dessa ska lösas individuellt och redovisas både skriftligt och muntligt. Skriftliga lösningar till dessa uppgifter ska lämnas till föreläsaren eller lämnas in på studentexpeditionen senast den tid som anges på uppgiftslydelsen. Den muntliga redovisningen kommer att ske senare samma vecka på en tid som ska bokas i förväg med bok-kommandot.

Varje mästarprov består av tre uppgifter av olika svårighetsgrad. En rätt löst uppgift ger betyg E på momentet, två rätt lösta uppgifter ger betyg C och alla rätt ger betyg A.

Den som inte godkänts på ett mästarprov får möjlighet att göra ett nytt efter teoritentan, men kan då bara få betyg E på mästarprovet.

Du kan se dina resultat på redovisade uppgifter i kursen med kommandot

res show algokomp09

på någon av skolans Unixdatorer.

Tenta

Ordinarietentan går fredagen den 18 december 2009. Närmaste omtentatillfälle blir i augustiperioden.

Tentan är en teoritenta (om 20 poäng) utan hjälpmedel. För godkänt krävs minst 10 poäng. 14 poäng ger betyg D och 17 poäng ger betyg C. Betyg B och A delas inte ut på teoritentan.

Skrivtiden är tre timmar. Den som hamnar under men tillräckligt nära gränsen för godkänt på tentan ges möjlighet att komplettera. Kursledaren avgör gränsen för komplettering liksom hur och när kompletteringsuppgifter ska redovisas.

Du behöver inte anmäla dig till tentan.

Muntlig tenta för högre betyg

Den som fått godkänt på båda mästarproven och teoritentan får godkänt på kursen. Den som fått minst betyg C på samtliga betygsatta moment (mästarproven och teoritentan) får betyg C på kursen, samma sak för betyg B. Den som fått minst betyg C på minst två av momenten och minst betyg E på det tredje har möjlighet att gå upp på en muntlig tenta för att få högre betyg. Den muntliga tentan kan bokas in (efter att teoritentan är rättad). Vid den muntliga tentan kommer läraren att kontrollera att du uppfyller alla betygskriterier för det betyg du aspirerar på. Kursboken är tillåtet hjälpmedel.
Copyright © Sidansvarig: Johan Karlander <johank@nada.kth.se>
Uppdaterad 2010-10-29