Ommästarprov 2

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

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å. Inlämningarna plagiatgranskas. 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 några fall av misstänkt otillåtet samarbete.

Skriftliga lösningar ska lämnas in senast måndag 4 januari 2021 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 perioden 7-11 januari 2021. 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 på mästarprov 2 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, både autentiska studentlösningar och mönsterlösningar.

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.

Vi ska i denna uppgift studera problemet 3CNF-3, som är ett slags satisfierbarhetsproblem där indata är tre stycken 3CNF-formler (som i problemet 3CNFSAT i föreläsning 25). Frågan är om det finns någon variabeltilldelning som gör att alla tre formlerna får samma värde (dvs alla är sanna eller alla är falska). 

Visa att 3CNF-3 ä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 3-CNFSAT. 

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.

Förtydligande till 3CNF

3CNF är ett format för formler (konjunktiv normalform med tre literaler per klausul).

3CNFSAT är problemet att avgöra om en formel i 3CNF är satisfierbar.

3CNF-3 är (i denna uppgift) problemet att avgöra om det finns någon variabeltilldelning som gör att tre formler i 3CNF får samma värde.

Indata (en instans) till 3CNF-3 består alltså av tre formler i 3CNF.

Till exempel:
formel 1: (x₁ v x₂ v x₃) ^ (x₃ v x₅ v icke x₁)
formel 2: (x₂ v x₄ v x₆) 
formel 3: (x₁ v icke x₂ v icke x₃)

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 2