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 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

Uppgiftslydelse

Vägledning till hur man genomför och formulerar matematiska bevis

Detaljerade bedömningskriterier för mästarprov 2

Lösningsförslag

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

Uppgiftslydelse

Vägledning till hur man skriver pseudokod i mästarprovet

Detaljerade bedömningskriterier för mästarprov 1

Lösningsförslag

Bokning av muntlig redovisning av mästarprov 1

Viggo Kann created page 20 August 2015

commented 29 September 2015

När kommer de upp?

Teacher commented 29 September 2015

Nu!

commented 29 September 2015

Är tanken att man ska kunna svara på alla frågor nu? Eller kommer det tas upp saker under kommande föreläsningar behövs för att svara på frågorna?

Teacher commented 29 September 2015

Henning, ni kan börja jobba med alla tre uppgifterna nu, men för att lösa uppgift tre optimalt kan det hjälpa att använda metoder som tas upp på någon av dom närmaste föreläsningarna.

commented 29 September 2015

Okej, tackar!

commented 1 October 2015

Funktionen f(x) = b - x saknar minimum i [a, a + k) där a, b, k > 0 och b > a + k.

Teacher commented 1 October 2015

Svar till Isac: Detta är inget problem, för uppgift 2 utspelar sig helt på heltalspunkter på tallinjen. Efter förflyttningarna står alltså personerna fortfarande på heltalspunkter.

commented 7 October 2015

Ay, man kan ta bort andra personers bokningar på Doodle-länkarna. Känns ju inte som det bästa systemet....

Teacher commented 7 October 2015

Jag vet, men jag litar på er.

Det går att göra en en striktare Doodle -- men då kan de som saknar Doodlekonto inte ändra sina egna bokningar och inte heller se sina bokningar igen när de har glömt bort dem. Och jag litar mycket mer på er hederlighet än ert minne. :)

commented 11 October 2015

Är indata i uppgift 3 enbart ordlistan eller fås n (längden på det längsta ordet) och m (antal ord) med?

Teacher commented 11 October 2015

Alexander, man kan anta att m och n är kända.

(Om man inte känner till m och n så det ju billigt -- tidskomplexitet är inte högre än för resten av algoritmen -- att räkna ut dem.)

Mattias Larsson removed his/her comment
Joel Hagrot removed his/her comment
commented 12 October 2015

Är man helt ute och cyklar om man har kommit fram till en algoritm med en tidskomplexitet som inte direkt med något funktionsuttryck beror på k i uppgift 2, och man därför inte kan uttrycka tidskomplexiteten i annat än bara n?

Kan man anta att ordlistan i uppgift 3 inte nödvändigtvis är sorterad?

Tack på förhand!

Teacher commented 13 October 2015

Joel, det är tillåtet att ge ett tidskomplexitetsuttryck som inte innehåller k om tidskomplexiteten är oberoende av k.

Ordlistan som är indata i uppgift 3 behöver inte vara sorterad, se till exempel exemplet på indata.

Johan Darnald removed his/her comment
commented 20 October 2015

Tjenare, jag verkar ha missat att trycka på spara på doodle. Trodde att jag hade bokat 10.40 på torsdag med Adam. Hur göra nu?

Tackar på förhand!

Teacher commented 20 October 2015

Felix, kontakta Adam eller Marcus och kolla om dom har tider kvar.

Henning Spett removed his/her comment

Teacher Stefan Nilsson changed the permissions 30 November 2015

Kan därmed läsas av studerande och lärare och ändras av lärare.
commented 30 November 2015

Kort fråga om uppgift 1: man ska alltså inte lösa optimeringsproblemet öht?

Teacher commented 30 November 2015

Hej Ludvig! Man ska inte lösa problemet i uppgift 1 (eller 2) utan visa att det är NP-fullständigt. Om du gjorde logiklabben i programmeringsparadigmkursen som handlade om detta problem så fick du lösa det där, men det gick bara för små indata. Nu kommer förklaringen till att det inte gick att lösa effektivt för större probleminstanser!

Teacher Viggo Kann changed the permissions 30 November 2015

Kan därmed läsas av alla och ändras av lärare.
commented 1 December 2015

När jag har läst om delmängdssumma så formuleras det lite annorlunda på vissa sidor. Ibland står det att input kan vara endast icke-negativa tal, ibland kan det vara även negativa. Får man anta att det bara kommer inte positiva tal i för delmängdssumma?

Teacher commented 1 December 2015

Henning, använd definitionen av delmängssumma som finns i kursboken och i föreläsningsanteckningarna (föreläsning 25). Det innebär att talen i indata är positiva heltal. Problemet är fortfarande NP-fullständigt om man tillåter talen att även vara negativa, men det är inte den vanliga definitionen.

commented 4 December 2015

Hur hög nivå får man ha på sin pseudokod? Är det okej att använda mängdoperatorer såsom snitt, tillhörighet, och grafoperationer såsom grannskapet till ett hörn, och att skriva saker som att "G ← G utökad med hörnet x, kanten {x,y}"? Så länge man motiverar tidskomplexiteten tänker jag att det blir väl bara lättare att läsa.

Teacher commented 4 December 2015

Ludvig, det är okej med denna typ av pseudokod (så länge du har koll på tidskomplexiteten).

commented 4 December 2015

Fråga 2

Vad är en given lösning? Är det en spindel och ett nätverk eller är det en spindel, konspiratörer och ett nätverk?

Representeras nätverket som en graf G=(V, E)?

Teacher commented 4 December 2015

Ezeddin, att bestämma vad som är en lösning ingår i uppgiften.

Du får själv avgöra hur nätverket ska representeras på lämpligt sätt.

Andreas Forsten removed his/her comment
commented 7 December 2015

På fråga 1.

Är n , dvs antalet platser på flyktingboendet, ett positivt heltal?

Teacher commented 7 December 2015

Alexander, antal är icke-negativa heltal. I detta fall är problemet ointressant om antalet platser på boendet är noll.

Patrik Schwermer removed his/her comment
commented 7 December 2015

Något sen fråga, men i uppgift 2. Får en "vanlig person" vara bekant med fler än en konspiratör?

Teacher commented 7 December 2015

Alexander T: Ja, annars vore problemet trivialt.

commented 30 December 2015

Har det sedan igår lagts upp anmälningslistor någonstans för muntlig redovisning av ommästarprov? Jag hittar det inte.

Teacher commented 31 December 2015

Stefan kommer att lägga upp anmälningslistorna på denna sida.

commented 3 January 2016

Jag är omregistrerad på kursen så på inlämningsuppgifter ser jag bara ommästarprov adk14, ska jag lämna in där då? Det står ju också att det är ca ett år försenad.

Teacher commented 3 January 2016

Det går inte att lägga till nya personer efter att inlämningsuppgiften lagts upp så du kan inte lämna in den ordinarie vägen. Du får mejla din lösning till mej istället så ska jag skicka den vidare till den som tar emot redovisningen.

commented 3 January 2016

Jag ser fortfarande ingen anmälningssida och sista dagen är imorgon. Har den flyttats eller är den bara försenad? Och angående den nya inlämningslänken verkar den vara för adk14? Står att inlämningen är försenad med 363 dagar och ger mig inget alternativ att lämna in.

Teacher commented 3 January 2016

Niklas, eftersom anmälningssidan är försenad så tror jag att Stefan sträcker ut anmälningstiden någon dag.

Rätt länk till inlämningsuppgifterna finns under kursomgången HT2015 adk15 i menyn till vänster.

Stefan Nilsson removed his/her comment
Teacher commented 5 January 2016

Nu går det att boka tider för ommästarprovsredovisning. Boka din tid senast onsdag 6/1.

Joel Hagrot removed his/her comment
commented 8 January 2016

Tjena!

Jag undrar hur det fungerar med plussning i denna kurs.

- Går det att plussa t.ex. enbart A- eller C-uppgiften på ett visst mästarprov om man redan klarat de lägre uppgifterna i motsvarande mästarprov denna omgång?

- Kommer nästa kursomgång få en ny komplexitetsuppgift motsvarande extralabben i labb 4, och kommer man att kunna göra om bara den i så fall (förutsatt att man blev godkänd på denna kursomgångs tenta)?

Om svaret är ja på någon av dessa frågor, gäller det svaret även om man vill plussa momentet under den s.k. systerkursen som går under vårterminen?

Allt förutsatt att kursen inte ändras, givetvis.

Tacksam för svar!

Teacher commented 8 January 2016

Svar till Joel:

På muntan får man bara uppgifter på dom betygskriterier som man ännu inte visat att man uppfyllt.

Plussning innebär att man gör om ett prov (till exempel tenta eller mästarprov) som man redan är godkänd på för att få högre betyg än man tidigare hade. Vid en plussning börjar man från noll, dvs man kan inte utnyttja att man redan visat vissa kunskaper. I ADK kan man plussa teoritentan och mästarproven, och det kan man göra inom kommande omgångar av såväl ADK som systerkursen Algoritmer och komplexitet (DD2352).

Troligen kommer extralabben i labb 4 att vara kvar nästa år och redovisas i januari, men det är för tidigt att utlova något. Extralabben finns inte i systerkursen DD2352.

Feedback News