Mästarprov 2

Inlämningsdatum 3 dec 2018 av 9.15
Poäng 0
Lämnar in en filuppladdning
Filtyper pdf

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. Vid mästarprov 1 var vi tvungna att anmäla ett fall av misstänkt otillåtet samarbete.

Skriftliga lösningar ska lämnas in i Canvas (som PDF) senast måndag 3 december 2018 klockan 9.15. 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 blåa vänstermenyn.

Skriv ditt namn och personnummer överst på framsidan av lösningarna. Se till att skriva ut en kopia av dina lösningar som du läser på och tar med till den muntliga redovisningen som kommer att ske mellan 6 och 13 december för någon av assistenterna eller lärarna. Boka tid för en femton minuters muntlig redovisning i Canvas senast 3 december klockan 9.15. Bokningslistorna läggs upp senast 29 november 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 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.

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.

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.

Uppgift 1 Sjukhusträning

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

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

Elvis Mammson som är chef för ett nybyggt sjukhus har kommit på att patienter som behöver motionera bör göra det genom att gå från sjukhusentrén igenom alla sjukhusets våningar och tillbaka till entrén. För att det inte ska uppstå någon stockning ska patienterna följa samma väg och aldrig besöka samma våning mer än en gång (utom entrévåningen där banan börjar och slutar). Dessutom vill Elvis att patienterna ska använda den jobbigaste vägen. Tyvärr är detta problem mycket svårare än vad Elvis trodde, vilket du ska visa i denna uppgift.

Sjukhuset kan beskrivas som en rektangel bestående av n stycken våningar numrerade från 1 till n, där n>2. Varje våning består av en enda m meter lång korridor. Sjukhusentrén ligger på våning 1, i korridorens första ände, dvs med koordinat (1,0). Var trapporna ligger i huset beskrivs av heltalsmatrisen S[1..n, 0..m]. Om S[i, j] = k så finns det en trappa från våning i till våning k, och den trappan startar j meter in i korridoren på våning i och kommer fram j meter in i korridoren på våning k. Trappan kan bara användas för att ta sig från våning i direkt till våning k och inte till mellanliggande våningar. Man kan förstås gå både uppåt och nedåt i en trappa, så om S[i, j] = k så är alltid S[k, j] = i. Det finns som mest m+1 trappor från varje våning, en per meter. (S[i, j] = 0 om det inte finns någon trappa på våning i vid meter j.)

Hur jobbigt det är för en patient att ta en trappa beror bara på hur många våningar trappan går och är |k-i| oavsett om trappan används uppåt eller nedåt (uttryckt i arbetsenheter). Dessutom kostar det 1 arbetsenhet per meter för en patient att gå i en korridor. Elvis söker alltså den väg som uppfyller villkoren ovan och som kräver största möjliga sammanlagda arbete att följa. Vägen kommer att bestå av n trappor, n-1 korridorsträckor mellan trappor, sträckan från entrén till första trappans början och sträckan från sista trappans slut tillbaka till entrén.

Formulera först detta problem som ett beslutsproblem, som vi kan kalla sjukhusträningsproblemet, genom att införa ett mål K. 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 NP-fullständiga problemet Hamiltonsk cykel (definieras i problemlistan i uppgift 2 nedan) till sjukhusträningsproblemet.

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 Lapptäcke

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

Patchwork, en produkt från programvaruföretaget Stitcher, är en programvara som hjälper dig att pussla ihop rektangulära lappar till ett lapptäcke, som inte har några hål och där inga lappar överlappar varandra.

Indata till programmet är en lista av rektangulära lappar. För varje lapp anges en bredd och en höjd i hela millimeter. Man anger också den önskade storleken (bredd och höjd) på det färdiga (rektangulära) lapptäcket.

Om det är möjligt att pussla ihop en delmängd av lapparna till ett täcke av rätt storlek så producerar programmet en beskrivning av hur detta kan gå till.
För varje lapp som ska användas får man veta var i lapptäcket den ska placeras. Man får också veta om man behöver vrida på lappen för att den ska passa.

Formulera detta konstruktionsproblem med matematisk notation och visa att det tillhörande beslutsproblemet (existerar en lösning?) ä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:

3CNF-SAT
Indata: boolesk 3CNF-formel
Fråga: Finns någon variabeltilldelning som satisfierar formeln?
CLIQUE
Indata: oriktad graf G, positivt heltal K
Fråga: Finns det K hörn i G som är fullständigt sammanbundna?
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?
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?
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?
HAMILTONSK CYKEL
Indata: oriktad graf G
Fråga: Finns det någon cykel i G som passerar varje hörn exakt en gång?
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?
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?
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 jobbigaste sjukhusvägen

Betygskriterium: utföra konstruktionsreduktioner.

Åter till sjukhusträningsproblemet i uppgift 1. Anta att det finns en algoritm TrainingPossible(S, K) som löser (det NP-svåra) beslutsproblemet. Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till TrainingPossible löser konstruktionsproblemet, alltså det problem som Elvis vill ha löst.

Konstruera en effektiv Turingreduktion av konstruktionsproblemet till beslutsproblemet. Antalet anrop av TrainingPossible 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

Mästarprov 2 betygsätts efter betygskriterierna för målen jämföra problem med hänsyn till komplexitet med hjälp av reduktioner samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet definiera och översätta centrala begrepp som P, NP, NP-fullständighet och oavgörbarhet naturligt att övas vid redovisningen.

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

Följande tabell visar kraven för dom olika uppgifterna.

Bedömningsgrund	Krav för uppgift 1	Krav för uppgift 2	Krav för uppgift 3
NP-fullständighet/NP-tillhörighet
Förklarar principerna för NP-fullständighetsbevis	ja	nej	-
Formulerar problemet som beslutsproblem	ja	ja	-
Förklarar vad en lösning består av	ja	ja	-
Visar NP-tillhörighet	ja	ja	-
Motiverar att verifikationsalgoritmen (motsv.) är polynomisk	ja	ja	-
Reduktionsalgoritm
Beskriver reduktionen övergripande i ord och ev. i bild	måttliga	måttliga	höga
Beskriver reduktionen tydligt	ja	ja	ja, med pseudokod
Reduktionen är korrekt	ja	ja	ja
Tidskomplexitet för reduktionen
Reduktionen är polynomisk	ja	ja	ja
Anger tidskomplexitet i lämpliga variabler	ja	ja	ja
Motiverar tidskomplexitet	måttliga	höga	höga
Korrekthetsresonemang
Redogör för vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ	ja	ja	ja
Framställer grundläggande idé för korrekthetsresonemanget	nej	ja, åtminstone åt ena hållet i den skriftliga inlämningen	ja
Genomför ett fullständigt korrekthetsresonemang	nej	ja, åtminstone muntligt	ja

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

Förtydliganden av uppgiftslydelserna som gjorts efter den ursprungliga publiceringen

I uppgift 1 (och därmed också i uppgift 3) har antalet sjukhusvåningar n i indata begränsats till minst 3, vilket gör att specialfallen för n=1 och n=2 (som inte är helt specificerade i uppgiftslydelsen) inte behöver hanteras.

Problemet Hamiltonsk cykel som nämns i uppgift 1 är problem 6 i problemlistan i uppgift 2.

Format/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

Bokning av muntlig redovisning

Boka en tid för 15 minuters muntlig redovisning 6-13 december i någon av bokningslistorna på bokningssidan.

Redovisningen är 15 minuter, oavsett om du ska redovisa en, två eller tre av uppgifterna. Notera noga vilken tid du bokar och vilket rum redovisningen ska vara i. Alla redovisningsrum är på plan 5 i D-huset.

Det är viktigt att du förbereder dig inför den muntliga redovisningen och tar med din inlämnade lösning på papper till redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera reduktioner och algoritmer muntligt och reda ut eventuella oklarheter.