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 onsdag 8 december 2021 klockan 18.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 13 och 17 december i Zoom för någon av assistenterna eller lärarna. Boka tid för en 10-20 minuters muntlig redovisning i Canvas senast 8 december klockan 18.00. Bokningslistorna läggs upp den 7 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å kursen om något är oklart. Uppgiftslydelserna kommer också att gås igenom på föreläsningen 29 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 (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 Lokal vaccinfördelning

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

En vaccinationscentral som vill kunna optimera sin vaccinfördelning på olika åldersgrupper behöver lösa vaccinfördelningsproblemet, som definieras på följande sätt:

Indata är positiva heltal D, n, a₁, ..., a_n, d₁, ..., d_n, och ickenegativa heltal t₁, ..., t_n, S.

Går det att fördela D doser vaccin till n olika åldersgrupper, där åldersgrupp k består av a_k personer? Varje person i åldersgrupp k som vaccineras får d_k doser. Minst t_k procent av grupp k måste bli färdigvaccinerad (dvs få d_k doser). Det maximala svinnet, antalet doser som blir över, får vara högst S.

Visa att problemet är NP-fullständigt genom att dels visa att det ligger i NP och dels utforma en polynomisk Karpreduktion mellan det kända NP-fullständiga problemet delmängdssumma (se föreläsning 25) och vaccinfördelningsproblemet.

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.

Uppgift 2 Effektiv vaccinering

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

Erfarenheterna från pandemin visar att det är svårt att nå ut med vaccin till en hel befolkning. I denna uppgift ska du bevisa att det även komplexitetsmässigt är svårt. Vi gör följande modell av vaccinationsproblemet:

Det gäller att på ett så effektivt sätt som möjligt ge hela befolkningen i en region möjlighet att vaccinera sig genom att besöka en utpekad vaccinationsinrättning som är nära hemmet. Vi modellerar befolkningens fördelning i regionen med en uppsättning hemorter där varje hemort har ett känt antal invånare. Och vi modellerar platser för möjliga vaccinationsinrättningar där varje möjlig vaccinationsinrättning har en övre gräns på hur många personer den kan vaccinera under vaccinationsperioden och en kostnad för att sätta upp inrättningen (en vaccinationsbuss är normalt billigare än en vaccinationscentral men kan inte vaccinera lika många personer). Dessutom behöver vi för varje vaccinationsinrättning veta tiden det skulle ta att med kollektivtrafik under vaccinationsinrättningens öppettider ta sig dit från varje hemort. Alla invånare i samma hemort ska vaccineras på samma vaccinationsinrättning.

Indata till problemet är

• ett positivt heltal k som anger antalet hemorter
• positiva heltal {a₁, ..., a_k}, där a_i anger antalet invånare i hemort i
• ett positivt heltal m som anger antalet möjliga placeringar av vaccinationsinrättningar
• positiva heltal {b₁, ..., b_m}, där b_j anger antalet invånare som maximalt kan vaccinera sig på  vaccinationsinrättning j
• positiva heltal {c₁, ..., c_m}, där c_j anger kostnaden för att sätta upp vaccinationsinrättning j
• en k x m-matris {d_i,j} med ickenegativa heltal som anger tiden att ta sig från hemorten i till vaccinationsinrättning j 
• ett positivt heltal g som anger Folkhälsomyndighetens rekommenderade gräns för hur långt (dvs hur lång tid) det som mest får vara från hemmet till den vaccinationsinrättning som är utpekad för hemorten

Det vi söker är den billigaste utplacering av vaccinationsinrättningar som klarar av att vaccinera alla invånare så att ingen invånare har längre till den vaccinationsinrättning som är utpekad för hemorten än g.

Målfunktionen är alltså summan av kostnaderna för att sätta upp vaccinationsinrättningarna.

Formulera detta optimeringsproblem som ett beslutsproblem och visa att det ä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 24-28 (se föreläsningsbilderna), inget annat problem.

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

Uppgift 3 Konstruktion av effektiv vaccinering

Betygskriterium: utföra konstruktionsreduktioner.

Vi återvänder till vaccinationsproblemet i uppgift 2. Anta att det finns en algoritm CanVaccinate som löser (det NP-fullständiga) beslutsproblemet som du definierade i uppgift 2 (om du inte löste uppgift 2 får du definiera det i uppgift 3 istället). Din uppgift är nu att ta fram en algoritm som med hjälp av anrop till CanVaccinate löser konstruktionsproblemet, alltså problemet att bestämma vilka vaccinationsinrättningar som ska sättas upp och vilka hemorter som ska vaccineras av varje vaccinationsinrättning, för att minimal kostnad ska uppnås. Ä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 CanVaccinate ska vara linjärt i indatas storlek, och för övrigt ska reduktionen ta polynomisk tid. Beskriv reduktionen med pseudokod. Om det inte finns någon lösning ska tomma mängden returneras. 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.

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 kommer att finnas mellan 13 och 17 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 18 den 8 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". 

Länk till bokningslistorna

På bokningslistan står om redovisningen sker i Zoom eller på KTH. Du ska i båda fallen kunna visa 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.

Lösningsförslag

Lösningsförslag till mästarprov 2 kommer att publiceras här när alla muntliga redovisningar genomförts. Fram till dess är det inte tillåtet att diskutera uppgifterna med någon annan.

Lösningsförslag till mästarprov 2 Download Lösningsförslag till mästarprov 2.