Ö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 22 november. 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.

Kortaste omblandade texten

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

Låt oss ta bort kravet på att orden i den packade texten i övningsmästarprov 1 ska vara i samma ordning som i indata. Då kan det vara möjligt att packa texten på färre rader än den giriga algoritmen kan.
Textpackningsproblemet har som indata ordlängderna w₁, ..., w_n och radlängden len. Alla tal i indata är positiva heltal.
Problemet är att ta reda på det minimala antalet rader av längd len som dom n orden kan rymmas på om det är tillåtet att blanda om orden. Orden ska ha mellanslag mellan sig när dom placeras ut på raderna, precis som i övningsmästarprov 1.

Formulera detta minimeringsproblem som ett beslutsproblem (genom att införa ett mål) och visa att beslutsproblemet är NP-fullständigt. När du ska visa att problemet är NP-svårt är det lämpligt att reducera problemet Mängdpartitionering (givet en multimängd positiva heltal, går det att partitionera talen i två delar som har samma summa?).

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.

Ovanstående krav ska vid det ordinariet 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.