Mästarprov 2

Mä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. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast torsdag 5 december 2019 klockan 13.00. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du se till att du är inloggad i Canvas genom att klicka på inloggningsikonen i den gråa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den muntliga redovisningen som kommer att ske mellan 9 och 13 december för någon av assistenterna eller lärarna. Boka tid för en femton minuters muntlig redovisning i Canvas senast 5 december klockan 13.00. Bokningslistorna läggs upp den 2 december sist på denna sida. Om du inte hinner göra uppgiften så avbokar du enkelt din bokning.

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 reduktionen/algoritmen muntligt och reda ut eventuella oklarheter.

Läs uppgifterna 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 är oklart. Uppgiftslydelserna kommer också att gås igenom på föreläsningarna 25 november (uppgift 1 och 3) och 26 november.

Mästarprovet är ett obligatoriskt moment i kursen. Det består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. För godkänt (betyg E) krävs helt rätt på uppgift 1 eller 2. Helt rätt på uppgift 1 och 2 ger betyg C och alla rätt ger betyg A. Ett mindre fel på en uppgift sänker betyget ett steg. Läs mer om betyg här.

Den som blir godkänd på uppgift 3 men bara en av uppgift 1 och 2 får betyg E eller D, men resultatet för uppgift 3 sparas i Canvas, så det går sedan att munta till betyg A genom att endast göra en muntauppgift för betyg C på mästarprov 2 (eftersom den därmed har visat uppfyllelse av betygskriterierna för alla nivåer). 

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. Där finns också tips om hur man formulerar och genomför matematiska bevis, som du bör läsa innan du bevisar dina reduktioner. Format/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

Uppgift 1 Nattparkering av långt godståg

Betygskriterium: förklara principerna, utföra enklare reduktioner mellan givna problem.

Vi ska studera en utvidgning av problem 1 och 3 från mästarprov 1.

SJ vill återigen optimera nattparkeringen så att så kort del av parkeringsspåren som möjligt används. Men man har nu kommit på att packningen av tåget kan bli ännu bättre om man inte har någon begränsning alls på antalet vagnskopplingar som får lösgöras.

Problemet som vi ska studera är att givet d och vagnslängderna v₁, v₂, v₃, ..., v_n (alla tal i indata är positiva heltal) hitta och returnera det minsta L så att tåget kan parkeras på d parkeringsspår av längd L. Alla d spår ska användas. Du kan anta att d<n, men du kan inte anta någon specifik begränsning av maximala vagnslängden.

Om inmatningen exempelvis är d=3, v[1..8]=[3,4,4,2,10,6,3,4] så är svaret 12, eftersom det går att parkera tåget på 3 spår så att vagn 2, 3 och 8 står på första spåret (längd 4+4+4), vagn 4 och 5 på andra spåret (längd 2+10), vagn 1, 6 och 7 på tredje spåret (längd 3+6+3).

Om inmatningen är d=4, v[1..8]=[3,4,4,2,10,6,3,4] så är svaret 10.

Formulera först detta minimeringsproblem som ett beslutsproblem, som vi kan kalla nattparkeringsproblemet, genom att införa ett mål m. Visa sedan att beslutsproblemet är NP-fullständigt genom att dels visa att det ligger i NP och dels utforma en polynomisk Karpreduktion av det känt NP-fullständiga problemet delmängdssumma (se övningsmästarprov 2) till nattparkeringsproblemet.

I uppgift 1 ä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.

Uppgift 2 Spel med färgkort

Betygskriterium:  visa NP-fullständighet eller oavgörbarhet.

Spelet börjar med att n spelare får n stycken färgkort vardera. Antalet olika färger kan vara allt från 1 till n². Spelarna kan se varandras kort. Slumpen avgör vem som får börja.

Varje spelare samlar poäng under spelets gång. 

Ett steg i spelet går till så här.
Den spelare X som står på tur väljer två kort av samma färg, ett i sin egen hand och ett hos en annan spelare Y. (Om det inte finns någon annan spelare som har något kort i samma färg som något kort som X har så tar spelet slut.)
Sedan händer tre saker:

1. X kastar sitt eget matchande kort.
2. X får lika många poäng som antalet kort i Y:s hand.
3. Turen går över till Y.

Det vore kul att veta om det är möjligt att få ihop minst p poäng (totalt för alla spelare) efter s stycken steg. Indata är händerna för dom n spelarna, vilken spelare som börjar, p och s.
Visa att detta beslutsproblem är NP-fullständigt!

I reduktionen ska du som känt NP-fullständigt problem använda något av dom nio problemen i listan över användbara NP-fullständiga problem som presenterades på föreläsning 25, inget annat problem. Det vill säga:

1. 3CNF-SAT
   Indata: boolesk 3CNF-formel
   Fråga: Finns någon variabeltilldelning som satisfierar formeln?
2. CLIQUE
   Indata: oriktad graf G, positivt heltal K
   Fråga: Finns det K hörn i G som är fullständigt sammanbundna?
3. INDEPENDENT SET (oberoende mängd)
   Indata: oriktad graf G, positivt heltal K
   Fråga: Finns det K hörn i G som är helt oberoende?
4. VERTEX COVER (hörntäckning)
   Indata: oriktad graf G, positivt heltal K
   Fråga: Finns det K hörn i G som täcker samtliga kanter?
5. GRAPH COLORING (graffärgning)
   Indata: oriktad graf G, positivt heltal K
   Fråga: Kan hörnen i G färgas med K färger så att inga närliggande hörn har samma färg?
6. HAMILTONSK CYKEL
   Indata: oriktad graf G
   Fråga: Finns det någon cykel i G som passerar varje hörn exakt en gång?
7. SUBSET SUM (delmängdssumma)
   Indata: En mängd positiva heltal P, positivt heltal K
   Fråga: Finns det en delmängd av talen i P vars summa är K?
8. INTEGER PROGRAMMING (heltalsprogrammering)
   Indata: m×n-matris A, m-vektor b, n-vektor c, tal K. Alla indata är heltal.
   Fråga: Finns det en n-vektor x med heltal så att Ax≤b och c_°x≥K?
9. SET COVER (mängdtäckning)
   Indata: Uppsättning delmängder av en mängd M, positivt heltal K
   Fråga: Finns det K av delmängderna som tillsammans innehåller alla element i M?

Använd Karpreduktion, inte Turingreduktion, när du visar att beslutsproblemet är NP-svårt.

Uppgift 3 Konstruktion av nattparkering av långt godståg

Betygskriterium: utföra konstruktionsreduktioner.

Åter till nattparkeringsproblemet i uppgift 1. Anta att det finns en algoritm NightParkingPossible(d, v[1..n], m) som löser (det NP-fullständiga) beslutsproblemet. Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till NightParkingPossible löser konstruktionsproblemet, alltså problemet att ta fram den nattparkering (på vilket spår ska vilken vagn parkeras) som parkerar hela tåget på så korta parkeringsspår som möjligt.

Konstruera en effektiv Turingreduktion av konstruktionsproblemet till beslutsproblemet. Antalet anrop av NightParkingPossible ska vara polynomiskt, och för övrigt ska reduktionen ta polynomisk tid. Beskriv reduktionen med pseudokod. Även om det finns flera möjliga optimala lösningar så ska bara en returneras. Analysera tidskomplexiteten för din reduktion och motivera att den är korrekt.

Detaljerade bedömningskriterier