Mästarprov
Titta gärna på tidigare års mästarprov för att få en bra uppfattning om vad som krävs.
Ommästarprov, adk15
Uppgiftslydelse (uppgift 2E förtydligad 26 december 2015)
Problemet som studeras i uppgift 2E på mästarprovet är en generalisering av problemet i uppgift 1C.
OBS: Eftersom ickesvenskspråkiga assistenter kommer att emot redovisningar så måste lösningarna till ommästarprovet skrivas på engelska.
Lämna in din uppgift under Inlämningsuppgifter, Ommästarprov adk15 i menyn till vänster mellan 29/12 och 4/1. Om du får problemet att inlämningssidan är blank kan du lösa det på samma sätt som Marcus Larsson. Boka din tid för muntlig redovisning senast onsdag 6/1 2016:
Bokning av muntlig redovisning av ommästarprovet
Bokningssidan är bara tillgänglig för elever som är registrerade på adk15. Om du vill boka tid och inte kommer åt sidan får du kontakta Viggo som kan ge dej behörighet.
Lösningsskisser:
1E. Använd en boolesk 26 x m-matris som datastruktur, där elementet (i,j) är sant om bokstav nr i i alfabetet kan stå på plats j i ett ord som matchar det reguljära uttrycket. Matrisen byggs upp kolumnvis med en linjär genomgång av []-uttrycken i tid O(m). Matchningen av ett ord görs genom m uppslagningar i matrisen. Matchning av alla n ord tar alltså tid O(nm).
1C. Använd dynamisk programmering. Skapa en array A där A[i] anger antal sätt att lägga en list av längd i. A[0]=0, A[1]=1, A[2]=2, A[3]=3. För i>3 är A[i]=A[i-1]+A[i-2]+A[i-4] eftersom listen kan sluta antingen med en platta av bredd 1, 2 eller 4, och om den slutar med en platta av bredd j så finns det A[i-j] sätt att lägga dom tidigare plattorna i listen. Arrayen A beräknas för växande i upp till n. A[n] ger svaret på problemet. Tidskomplexiteten är O(n).
2E. Beslutsproblemet är frågan om det över huvud taget går att bilda en list av längd n med dom tillgängliga plattorna.
En lösning till en ja-instans beskrivs av den delmängd av plattor som kan bilda listen av längd n.
Att beslutsproblemet är NP-svårt ser vi genom en reduktion av delmängdssumma. Låt plattornas bredd vara dom ingående talen och låt det finnas en platta av varje sort (givet att indata är en äkta mängd). Låt n vara den sökta summan.
Mästarprov 2, adk15
Vägledning till hur man genomför och formulerar matematiska bevis
Detaljerade bedömningskriterier för mästarprov 2
Bokning av muntlig redovisning av mästarprov 2
Bokningssidan är bara tillgänglig för elever som är registrerade på adk15. Om du vill boka tid och inte kommer åt sidan får du kontakta Viggo som kan ge dej behörighet.
Mästarprov 1, adk15
Vägledning till hur man skriver pseudokod i mästarprovet