Ommästarprov 1

Detta ommästarprov ger möjlighet att bli godkänd (betyg E) på mästarprov 1 (momentet MAS1).

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 ett fall av misstänkt otillåtet samarbete.

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

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på din inlämning inför den muntliga redovisningen som kommer att ske under veckan 7-10 januari 2020. Boka tid för muntlig redovisning senast 4 januari klockan 19. 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å 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 PE-satisfierbarhet

Problemet som ska studeras i både ommästarprov 1 och 2 är ett satisfierbarhetsproblem där indata är en boolesk formel som består av en konjunktion av klausuler, där varje klausul antingen är en disjunktion av tre booleska variabler (utan negationer) eller en ekvivalens mellan en boolesk variabel och en negerad boolesk variabel. Frågan är som vanligt om det går att satisfiera formeln.

Ett exempel på indata till problemet är $(x_1\vee <!--\; \vee \; -->x_2\vee <!--\; \vee \; -->x_3)\wedge <!--\; \wedge \; -->(x_1\vee <!--\; \vee \; -->x_3\vee <!--\; \vee \; -->x_4)\wedge <!--\; \wedge \; -->(x_3\vee <!--\; \vee \; -->x_4\vee <!--\; \vee \; -->x_5)\wedge <!--\; \wedge \; -->(x_1\vee <!--\; \vee \; -->x_5\vee <!--\; \vee \; -->x_6)\wedge <!--\; \wedge \; -->(x_1\equiv <!--\; \equiv \; -->\mathrm{\neg <!--\; \neg \; -->}{x}_5)\wedge <!--\; \wedge \; -->(x_5\equiv <!--\; \equiv \; -->\mathrm{\neg <!--\; \neg \; -->}{x}_6)$

Detta problem kallar vi för PE-satisfierbarhet.

Mästarprov 1, E-uppgift

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

Konstruera en exponentiell algoritm som löser PE-satisfierbarhetsproblemet.  Använd totalsökning.

Beskriv algoritmen med pseudokod. Analysera algoritmens tidskomplexitet. 

Detaljerade bedömningskriterier

För att det ska bli extra tydligt hur uppgiften 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.