Mästarprov 2

Inlämningsdatum 5 dec 2024 av 19:00
Poäng 0
Lämnar in en filuppladdning
Filtyper pdf
Tillgänglig 20 nov 2024 kl 17.30–5 dec 2024 kl 19.20

Den här uppgiften låstes 5 dec 2024 kl 19.20.

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. Vi tar mycket allvarligt på detta och följer KTH:s riktlinjer om att misstänkta fall av samarbete ska anmälas till rektor. Du får inte använda generativ AI för att lösa mästarprovsuppgifterna. Däremot får du gärna använda generativ AI för att typsätta med LaTeX. 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 2024 klockan 19.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 10 och 16 december i Zoom eller på KTH för någon av lärarna eller assarna. Boka tid för en 10 minuters (om du har löst en uppgift) eller 20 minuters (om du har löst 2-3 uppgifter) muntlig redovisning i Canvas senast 5 december klockan 19:30. Bokningslistorna läggs upp den 4 december sist på denna sida. Vänta med att boka tid tills du har lämnat in dina lösningar.

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å ett felaktigt antagande. Fråga en lärare på kursens diskussionsforum om något är oklart (men avslöja inget av din lösning när du frågar). Uppgiftslydelserna kommer också att gås igenom på föreläsningen 21 november Links to an external site. (uppgift 1) och 25 november (uppgift 2 och 3).

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 (uppgift 3 examinerar kriterierna för A som inte inkluderar kriterierna för E eller C). 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 under rubriken Examination och slutförande i kurs-PM.

Den som blir godkänd på uppgift 3 men bara på 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, både autentiska studentlösningar och mönsterlösningar. 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 Stenblocksproblemet

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

Bakgrund: Året är 2737 och Nick Bostrom hade rätt om konvergens (https://en.wikipedia.org/wiki/Instrumental_convergence Links to an external site.), men von Neuman, Turing, Vinge, och Nick hade dock bara delvis rätt om den teknologiska singulariteten (https://en.wikipedia.org/wiki/Technological_singularity Links to an external site.). AI har inte upptäckt någon polynomisk algoritm för NP-fullständiga problem, och behöver fortfarande hjälp med logik och matematik.
Du befinner dig i Rom och i ett sista desperat försök att övertyga AI om att inte göra stenkuber av Colosseum, Pantheon, och alla andra monument måste du visa att det är ett NP-fullständigt problem som inte verkar gå att lösa effektivt.

En instans av stenblocksproblemet är en hög rätblock av sten och ett positivt heltal. En instans ges av en osorterad lista

((l_{1}, h_{1}, b_{1}), . . ., (l_{m}, h_{m}, b_{m}))

$((l_1,h_1,b_1),...,(l_m,h_m,b_m))$ där

l_{i}

$l_i$ är längden,

h_{i}

$h_i$ är höjden och

b_{i}

$b_i$ är bredden på det

i

$i$ :te rätblocket av sten (alla mått är positiva heltal), och ett positivt heltal

d

$d$ som ger storleken (på sidan) på kuben som ska byggas.

Beslutsproblemet är att avgöra om det går att bygga en

d \times d \times d

$d \times d \times d$ -kub (som inte har några inre hål) av en delmängd av rätblocken av sten, dvs om det finns en delmängd

I

$I$ av

{1, 2, . . ., m}

$\{1,2,...,m\}$ sådan att det går att bygga en kub av rätblocken vars index ligger i

I

$I$ . Varje rätblock kan ställas, läggas och vridas som det passar.

AI litar förstås på den arkiverade kurslitteraturen för ADK anno 2024. I föreläsning 25 klargörs att "subset sum" (problemet delmängdssumma) är NP-fullständigt, och du ska använda det problemet för att visa att också stenblocksproblemet är NP-fullständigt.

En instans av den variant av subset sum du ska utgå ifrån består av en osorterad lista med positiva heltal

(a_{1}, . . ., a_{m})

$(a_1,...,a_m)$ och ett positivt heltal

s

$s$ , och beslutsproblemet är avgöra om det går att hitta en delmängd

M

$M$ av

{1, 2, . . ., m}

$\{1,2,...,m\}$ så att

\sum_{i \in M} a_{i} = s

$\sum_{i\in M} a_i=s$ .
AI har som sagt svårt för matematik och tenderar att tappa humöret så du måste ge hen en fullständig, tydlig, och lättläst framställning som visar att stenblocksproblemet är NP-fullständigt.

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 däremot inte. Se kraven för uppgift 1 i tabellen nedan för detaljer.

Uppgift 2 Fontänproblemet

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

Indata till fontänproblemet är en beskrivning av strukturen för en speciell fontän som består av $n$ stycken en centimeter tjocka plexiglasskivor som ligger horisontellt rakt ovanpå varandra i en ställning med fyra centimeters avstånd mellan varje skiva. Varje skiva har ett $n\times n$ -rutnät där varje ruta antingen har ett cirkulärt hål i sig eller inte har något hål. Rutorna i varje rutnät har koordinater mellan $\left(1,1\right)$ och $\left(n,n\right)$ där $\left(1,1\right)$ är närmaste vänstra hörnet och $\left(n,n\right)$ är det bortesta högra hörnet. Det verkligt speciella med fontänen är att det har $n$ stycken reglage, ett för varje $x$ -värde. Varje reglage kan ställas in i $k$ olika lägen, ett för varje $y$ -värde mellan 1 och $k$ . När reglage $i$ är inställt i läge $j$ kommer alla hål som är på position $\left(i,j\right)$ i alla plexiglasskivor att samtidigt täckas så att inget vatten kan rinna igenom dessa hål. Ovanpå den översta plexiglasskivan sprutar det ut vatten. Frågan är om det går att ställa in dom $n$ reglagen så att vattnet kan rinna ner igenom alla $n$ plexiglasskivor och ner i den uppsamlingsbassäng som finns under understa skivan. Vattnet kan förstås bara rinna ner igenom en skiva om det finns minst ett hål i den som inte är täckt av något reglage. Om alla hål är täckta kommer vattnet att stanna ovanpå den skivan och fontänen gå sönder.

Fontän med n=3 och k=3. Exemplet ovan visar en fontän med n=3, alltså tre plexiglasskivor av storlek 3 x 3, k=3 och tre reglage R1, R2 och R3, ett för varje x-värde. I exemplet är det sex hål i varje skiva, men det behöver inte vara samma antal hål i varje skiva.

Indata består av heltalen $n$ och $k$ samt en array holesAtLevel $\left\lbrack1,n\right\rbrack$ med listor över koordinaterna för alla hål som finns i var och en av skivorna. Listan holesAtLevel $\left\lbrack1\right\rbrack$ beskriver hålen i den översta skivan osv. Du kan anta att det finns minst ett hål i varje skiva och att det för varje x-värde finns minst ett hål i någon av skivorna för det x-värdet.

Visa att fontänproblemet är NP-fullständigt.

I reduktionen ska du som känt NP-fullständigt problem använda något av dom problem som listats som eller visats vara NP-fullständiga problem på föreläsning 25 (se föreläsningsbilderna), inget annat problem.

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

Uppgift 3 Konstruktion av fontän

Betygskriterium: utföra konstruktionsreduktioner.

Vi återvänder till fontänproblemet som definierades i uppgift 2. Anta att det finns en algoritm WorkingFountain som löser (det NP-fullständiga) beslutsproblemet som definierades i uppgift 2. Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till WorkingFountain löser konstruktionsproblemet, alltså givet en fontänbeskrivning som har en lösning, bestämma vilka inställningar reglagen ska ha för att fontänen ska fungera. Även om det finns flera möjliga lösningar så ska bara en returneras.

Konstruera en effektiv Turingreduktion av konstruktionsproblemet till beslutsproblemet. Antalet anrop till WorkingFountain ska vara högst $\min(nk,m)-n$ , där $m$ är totala antalet hål i skivorna i fontänen. I övrigt ska reduktionen ta polynomisk tid. Beskriv reduktionen med pseudokod. Du kan anta att indata beskriver en lösbar instans. Analysera tidskomplexiteten för din reduktion och motivera att reduktionen ä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 i 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 fullständighetsbevis	ja	nej	-
Förklarar vad certifikatet (vittnet) består av	ja	ja	-
Visar NP-tillhörighet	ja, pseudokod krävs inte	ja, pseudokod krävs inte	-
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 tillräckligt effektiv	ja	ja	ja
Anger tidskomplexitet i lämpliga variabler	ja	ja	ja
Motiverar tidskomplexitet	måttliga	höga	höga
Korrekthetsresonemang för reduktionen
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, med invarianter eller induktion

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

Om uppgift 2 redovisas för betyg E (dvs om uppgift 1 inte lösts/godkänts) används betygskriterierna för E (uppgift 1) vid bedömningen.

Bokning av muntlig redovisning

Tider för muntlig redovisning finns mellan 10 och 16 december.

Lämna in din skriftliga lösning i Canvas innan du bokar tid för muntlig redovisning. Du kan boka tid fram till kl 20:00 den 5 december. Efter det är tiderna fixa och kan inte ändras.

Observera att det är olika bokningslistor för den som redovisar för betyg E och för den som redovisar för betyg A-D. Den som bara har gjort en uppgift, eller som har försökt på flera uppgifter men bara till kriterienivå E, ska boka tid på en lista märkt "för betyg E". Den som har löst flera uppgifter ska boka tid på en lista märkt "för betyg A-D".

På bokningslistan står om redovisningen sker i Zoom eller på KTH. Du ska i båda fallen kunna visa fysiskt ID vid redovisningen.

Redovisningen är 10 minuter om du redovisar för betyg E och 20 minuter om du redovisar för betyg A-D. Det är i båda fallen viktigt att du förbereder dig inför den muntliga redovisningen så att du snabbt kan svara på assistentens frågor. För att en uppgift ska godkännas ska du kunna förklara och motivera algoritmen muntligt och reda ut eventuella oklarheter.

Den som löst flera uppgifter och bokar en E-tid garanteras inte att få redovisa alla lösta uppgifter, utan det sker i mån av tid.

Lösningsförslag

Lösningsförslag till mästarprov 2 Download Lösningsförslag till mästarprov 2 har nu publicerats efter att alla muntliga redovisningar genomförts. Nu är det tillåtet att diskutera uppgifterna med andra.