Övningsmästarprov 2

Det riktiga mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Detta övningsmästarprov får däremot mycket gärna lösas i tvåpersonsgrupp. Det är dessutom tillåtet att diskutera det i ännu större grupper. Skriv ner lösningen för hand eller med dator och ta med (på papper) till övningstillfället 21 november 2019. Ta med en egen utskriven lösning även om du gjort den tillsammans med en kamrat. Vid övningen kommer lösningarna att kamraträttas enligt samma kriterier som används vid det ordinarie mästarprovet. Den som vid övningstillfället redovisar ett gott försök till lösning (den behöver inte vara korrekt i alla delar) får en teoripoäng.

Övningsmästarprovet är frivilligt, till skillnad från det ordinarie mästarprovet som är ett obligatoriskt moment i kursen. Det ordinarie mästarprovet består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. Övningsmästarprovet har bara en uppgift, och den motsvarar betygskriterierna för E. 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 skriver bevis.

Lika vikt

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

I problemet lika vikt gäller det att avgöra om det går att dela upp en uppsättning med n prylar i två grupper så att grupperna väger exakt lika mycket.

Indata till problemet är prylarnas vikter v₁, ..., v_n uttryckta i gram (positiva heltal). 

Exempel: Om indata är (10, 30, 45, 10, 15) så är svaret ja eftersom man kan dela upp vikterna i grupperna (10, 30, 15) och (45, 10) som båda har totalvikten 55 gram.

Om indata är (10, 30, 45, 10) så är svaret nej eftersom det inte finns någon uppdelning av vikterna i två grupper som väger exakt lika mycket.

Din uppgift är att visa att detta beslutsproblem är NP-fullständigt. När du ska visa att problemet är NP-svårt ska du reducera delmängdssumma (givet en lista med positiva heltal P och ett mål K, finns det någon delmängd av P som har summan K?). Delmängssumma är ett av dom nio NP-fullständiga problem som presenterades på föreläsning 25 och som i kursen anses vara känt NP-fullständiga (och därmed kan användas i NP-reduktioner). 

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 begreppen P, NP, NP-fullständighet och oavgörbarhet naturligt att övas vid redovisningen.

Följande tabell visar kraven för den första uppgiften på mästarprov 2, vilket motsvarar denna uppgift.

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

Ovanstående krav ska vid det ordinarie mästarprovet vara uppfyllda efter den muntliga redovisningen, där oklarheter och små ofullkomligheter och fel kan redas ut. Kraven på den skriftliga lösningen är något lägre.

Lösningsförslag och övningsbedömning

På övningsmästarprovsövningen gicks detta lösningsförslag Download lösningsförslag

 igenom och en kamratbedömning Download kamratbedömning

 av övningsmästarprovet genomfördes med detta rättningsprotokoll Download rättningsprotokoll

. Vid det riktiga mästarprovet kommer ett sådant rättningsprotokoll att användas vid bedömningen.