Ommästarprov

Ommästarprovet ger möjlighet att bli godkänd (betyg E) på mästarprov 1 (momentet MAS1), mästarprov 2 (momentet MAS2) eller båda.

Ommästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Detta är något som vi tar allvarligt på. Misstänkt otillåtet samarbete måste enligt KTH:s regler anmälas till rektor. Vid ordinarie mästarproven var vi tvungna att anmäla två fall av misstänkt otillåtet samarbete.

Skriftliga lösningar ska lämnas in senast fredag 4 januari 2019 klockan 13.00 i Canvas som PDF-dokument. Det är tillåtet att skriva för hand och skanna in dokumentet.

Skriv ditt namn och personnummer överst på framsidan av lösningarna. Läs på din inlämning inför den muntliga redovisningen som kommer att ske under veckan 7-11 januari 2019. Boka tid för muntlig redovisning senast 4 januari klockan 13. Bokningslistorna läggs upp senast 31 december sist på denna sida. 

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera algoritmen muntligt och reda ut eventuella oklarheter.

Läs uppgiften mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om något i uppgiftslydelsen är oklart. Du kan skriva frågan i Canvas eller mejla den till viggo@kth.se

För godkänt (betyg E) på mästarprov 1 krävs helt rätt på första uppgiften. För godkänt på mästarprov 2 krävs helt rätt på andra uppgiften.

För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov på kurswebben.

Problemet delmängdssumma

Ett känt NP-fullständigt problem är delmängdssumma. Det definieras så här:
Indata: En mängd positiva heltal P={p₁,p₂,...,p_n}, positivt heltal K.
Fråga: Finns det en delmängd av talen i P vars summa är K?

På föreläsning 26 visades att detta problem är NP-fullständigt när P är en multimängd, dvs att flera förekomster av samma tal tillåts. Problemet är fortfarande NP-fullständigt då P är en vanlig mängd där varje element är unikt. I detta ommästarprov låter vi P vara en vanlig mängd. Låt M vara det största talet i P.

Mästarprov 1, E-uppgift

Betygskriterium: utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod.

Denna uppgift ska göras endast av den som inte är godkänd på mästarprov 1!

Även om problemet är NP-svårt så går det att lösa med en pseudopolynomisk algoritm, det vill säga en algoritm vars tidskomplexitet är ett polynom i n och M. I denna uppgift ska du konstruera en sådan algoritm och visa att den är pseudopolynomisk.

Algoritmen ska konstrueras med dynamisk programmering. Låt S[i,j] vara ett booleskt värde som talar om ifall det är möjligt att bilda summan j av en delmängd av dom i första talen i P. Rekursionsekvationen är:

$S[0,0]=true$

$S[0,j]=false$ (för alla j>0)

$S[i,j]=S[i-1,j]\vee S[i-1,j-p_i]$ (för alla i mellan 1 och n; högra termen är bara med då j≥p_i)

Beskriv algoritmen med pseudokod. Analysera algoritmens tidskomplexitet (med enhetskostnad). 

Mästarprov 2, E-uppgift

Betygskriterium: jämföra problem med hänsyn till komplexitet med hjälp av reduktioner: förklara principerna, utföra enklare reduktioner mellan givna problem.

Denna uppgift ska göras endast av den som inte är godkänd på mästarprov 2!

Låt jämn delmängdssumma vara samma problem som delmängdssumma, men där talen i indata är begränsade till att vara positiva jämna tal. Visa att jämn delmängdssumma är NP-fullständigt genom att dels visa att det ligger i NP och dels utforma en polynomisk Karpreduktion av det NP-fullständiga problemet delmängdssumma till jämn delmängdssumma. 

I denna uppgift är det viktigt att du visar att du kan principerna för NP-fullständighet och reduktioner. Ett fullständigt bevis för reduktionens korrekthet krävs inte.

Detaljerade bedömningskriterier

För att det ska bli extra tydligt hur uppgifterna bedöms och för att dom assistenter som tar emot 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.

E-nivå för mästarprov 1

Mästarprov 1 betygsätts efter betygskriterierna för målen utveckla algoritmer med datastrukturer samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet naturligt att övas vid algoritmkonstruktionen.

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

E-nivå för mästarprov 2