Ö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. Var och en ska vid redovisningen vid övningstillfället 19 november ladda upp en egen skriftlig lösning med namn på som PDF-dokument. Det går bra att lämna in en inskannad handskriven lösning.  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. 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. Uppgiften på mästarprovet kommer antingen att gälla NP-fullständighet eller oavgörbarhet. Om det är ett oavgörbarhetsproblem modifieras kriterierna nedan på det naturliga sättet (verifikation och reduktion i ändlig tid istället för polynomisk tid, R.E. istället för NP etc).

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 kommer en lösning till uppgiften att gås igenom och du får göra en kamratbedömning av övningsmästarprovet med hjälp av ett rättningsprotokoll. Vid det riktiga mästarprovet kommer ett sådant rättningsprotokoll att användas vid bedömningen.