Mästarprov

Mästarprov 1

Uppgiftslydelse till mästarprov 1

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

Lösningsförslag

Mästarprov 2

Uppgiftslydelse till mästarprov 2

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

Lösningsförslag

Ommästarprov

Uppgiftslydelse till ommästarprov 1

Inlämning av skriftlig redovisning av ommästarprov 1 (senast 7 januari 2014, kl 10.00)

Uppgiftslydelse till ommästarprov 2

Inlämning av skriftlig redovisning av ommästarprov 2 (senast 8 januari 2014, kl 10.00)
Om du inte följt kursomgången adk13 så kan du tyvärr inte lämna in med länken ovan. Mejla i så fall din lösning till viggo@nada.kth.se
Rubrikraden ska vara Ommästarprov 2

Tryck här för att hämta bokningslistor för muntlig redovisning av ommästarprov 1 och 2:

Teacher Viggo Kann created page 27 September 2013

Teacher Viggo Kann changed the permissions 27 September 2013

Kan därmed läsas av alla och ändras av lärare.
commented 28 September 2013

Jag har problem att tolka uppgiftslydelsen på fråga 3.

Hur ska "Låt n vara totala antalet tal i indata" tolkas? Är problemstorleken, dvs komplexiteten ska anges som O(g(n))? Är n=p+s eller n=p+s+[summan av längden på listorna i alla reaktionstuplar] eller något annat? Hur kommer m in?

Har k samma värde för alla reaktioner? Vad är komplexiteten för att titta på varje element i listan över ämnen som behövs för given en reaktion? Beror den på problemstorleken?

Teacher commented 28 September 2013

n är problemstorleken, m är det största ämnesnumret som ingår i indata, k behöver inte ha samma värde för olika reaktioner. Komplexiteten för att indexera i en array är 1. Använd enhetskostnad i analysen.

Här är ett exempel på indata som bör skingra alla oklarheter:a[]=[1,2,4], b=5, r[]=[(3,[1,4]), (5,[2,3,4])].
Eftersom det är 11 tal i indata så blir n=11. Eftersom största ämnesnumret är 5 så blir m=5.

På föreläsningen den 7 oktober kommer lydelsen till uppgift 3 att gås igenom.

commented 28 September 2013

I fråga 3, kan man anta att listan med möjliga reaktioner är sorterad efter ämnesnummer som de framställer? Dvs om två reaktioner framställer samma ämne, kommer de ligga bredvid varandra i indataarrayen?

Teacher commented 29 September 2013

Nej, man kan inte anta att indata är sorterat om det inte står det i uppgiftslydelsen.

commented 29 September 2013
The content of this comment is hidden.

has hidden kommentaren 29 September 2013

Reason: Emil undrar: Kan man anta att varje ämnesnummer mellan 1 och m finns med i indata? Svaret är nej. Att jag tog bort frågan här beror på att den fortsatte med en analys av vad olika svar på den har för verkningar, men mästarprovet ska lösas utan samarbete eller hjälp.
commented 29 September 2013

Ok, då vet jag. (Försökte formulera frågan utan att säga för mycket, men men ...)

Teacher commented 30 September 2013

mästarprovssidan finns nu ett dokument med titeln "Vad är pseudokod? En vägledning till hur man skriver pseudokod i mästarprovet". Det beskriver syftet med pseudokod, ger riktlinjer för pseudokodsskrivande och ger exempel på pseudokod.

Teacher commented 30 September 2013

På föreläsningen idag gick jag igenom lydelsen till fråga 1. Vanligaste frågan var om man får byta ordning på orden i texten. Det får man inte (för då förstör man texten).

Kristoffer Emanuelsson removed his/her comment
commented 3 October 2013

Tips till er som vill skriva lösningar i LaTeX men inte riktigt vet rent tekniskt hur ni kommer igång kan använda den här mallen. Resultatet blir någonting i stil med så här.

Dokumentation över pseudokod-syntax: http://pages.cs.wisc.edu/~tdw/files/alg.pdf.

För att få ut en pdf, så kör kommandot "pdflatex texten.tex" på någon av skolans datorer, eller ssh:a till u-shell.csc.kth.se och kör det därifrån.

commented 4 October 2013

På fråga 2, får kedjan vikas ner en rad utan att byta håll? Alltså, får nästa länk av kedjan läggas på raden nedanför utan att också byta riktning?

Teacher commented 4 October 2013

Nej, kedjan måste byta riktning när den går ner till nästa rad.

commented 6 October 2013

Ang fråga 3. Är ämnet b endast uppbyggt av råvaror a[1...p] eller kan det vara uppbyggt av råvaror samt/eller ämnen i r[1...s].

Exempel: Vi får a[1,2,3,4,5]. Vi vill framställa b. I listan r[1...s] hittar vi (b,[1,2,c,5]) - men även (c,[3,4]). Dvs vi kan framställa b genom att först bygga c. Är detta ett möjligt scenario?

commented 6 October 2013

Får man designa algoritmerna i mästarprovet med andra progammeringsparadigmer såsom funktionell programmering?

Teacher commented 6 October 2013

Pseudokoden kan vara byggd på funktionell programmering, bara det är tydligt vad som menas. Men det är klokt att undvika programspråkskonstruktioner som tar mer än konstant tid, så som till exempel ofta är fallet i logikprogrammering, för det blir svårt att analysera tidskomplexiteten då.

På föreläsningen måndag 7 oktober kl 11 kommer uppgift 3 att gås igenom, så den som har frågor på formuleringen av uppgift 3 är mycket välkomna då.

commented 8 October 2013

För uppgift 3, tillhör talet m också indata?

Elias Lousseief removed his/her comment
Teacher commented 8 October 2013

Nja, m är inte direkt indata, men det kan beräknas ur indata som det största ämnesnumret som ingår i en reaktion.

m kan vara större än antalet ämnen som ingår i indata (för vissa ämnesnummer kanske inte förekommer). Men det är inte större än att man till exempel kan deklarara en array av storlek m.

commented 9 October 2013

Alltså kunde du inte sagt det tidigare eller från början, alltså att man kan deklarera en array av storlek m? I uppgiftslydelsen ser det ut som att talen i indata kan vara i princip hur stora som helst, vilket ju innebär att man inte hur som helst bara kan deklarera en array av storlek m utan att man använder för mycket minne. I alla olika problemlydelser jag läst genom åren har jag aldrig stött på att man kan anta att indatatalen (om det bara står heltal) är så små att det går att deklarera en array med storleken av det största talet. Om så ändå är fallet brukar en tydlig övre gräns på det största talet anges, eller någon typ av indikation att största talet är av samma storleksordning som storlek på indata etc.

Det var egentligen det här jag ville komma fram till i min fråga förut, då du tog bort min fråga, eftersom, precis som du skrev ovan, olika svar på den ger olika verkningar, och jag hade ingen lust att göra uppgiften svårare än vad som egentligen behövs.

Teacher commented 9 October 2013

Jag är ledsen att du fick intrycket att uppgiften var mycket svårare än den var. När talen i indata anger storlekar av något slag så kan det som du skriver vara så att datastrukturer med storlek av det största talet tar för mycket plats. I denna uppgift är talen nummer (på ämnen) och då är det en annan sak. Om du hade frågat om minneskomplexitet m var okej så hade jag svarat ja. I uppgift 3 är det ordoklassen för tidskomplexiteten som ska vara lika med undre gränsen. Hoppas inga oklarheter återstår nu!

commented 9 October 2013

Kan du avslöja huruvida det förekommer direkta eller indirekta loopar i reaktionslistorna? Typ:

r(2[2,4,5])

eller

r(2[3,4,5], 3[2,4])

Teacher commented 9 October 2013

Ja, det kan självklart förekomma cykliska beroenden bland reaktionerna.

commented 10 October 2013

Jag lämnade mitt mästarprov i den svarta brevlådan märkt CSC på Osquars Backe 2, plan 4 (enligt uppgiftslydelsen???). Kommer mitt prov att hamna i rätt händer?

commented 11 October 2013

Du sa något om att vi inte behövde vara noggranna med t ex triviala loopar. Innebär det att om jag låt säga vill kopiera en matris så räcker det att beskriva det med ord i algoritmen? Eller var det invarianten som var överflödig för (mer eller mindre irrelevanta och) triviala loopar?

commented 11 October 2013

Kopiera matris skulle kunna se ut så här:

copy[1..n,1..n] <- matrix[1..n,1..n]

Det är väl tillräckligt? (Tar naturligtvis hänsyn till en sån sats vid tidskomplexitet)

Teacher commented 11 October 2013

Inlämning av mästarprovet kan göras i den svarta brevlådan som sitter i trapphuset utanför studentexpeditionen på plan 4 i E-huset. Om expeditionen är öppen lämnar man in där.

Vad som är "tillräckligt" i pseudokod beror på pseudokodens syfte och sammanhanget. I mästarprovsuppgift 2 är det rimligt att skriva en matriskopiering på det sätt som Erik Norell föreslår.

På föreläsningen sa jag att man inte behöver ange invarianter för och argumentera korrekthet för triviala loopar. Det är dom delar av algoritmen som inte är självklara som behöver motiveras.

commented 11 October 2013

Hej, på uppgift 2 står det att man ska motivera att algoritmen är korrekt. Ska man föra ett resonemang för att algoritmen är korrekt eller vill du vill ha något mer konkret, t.ex. induktionsbevis eller hoare-logik? Och generellt i mästarprovet, måste man beskriva algoritmen förutom pseudokoden helt? Eller räcker det med att förklara kod som inte är trivial?

Teacher commented 11 October 2013

En god vana är att inleda med att förklara idén till algoritmen och därefter ge pseudokoden. Efter det analyserar man tidskomplexiteten och motiverar korrektheten. Korrekthetsmotiveringen kan se ut på många sätt. Om man använder dekomposition eller dynamisk programmering ska man utnyttja rekursionen i motiveringen (visa att rekursionen löser problemet och visa att pseudokoden implementerar rekursionen). Självklara delar (som att en slinga summerar talen i en array) behöver man inte bevisa. Läs Emmas häfte om pseudokod för att förstå vad som krävs av algoritmbeskrivningen. Titta på gamla mästarprov och deras lösningar för att få en uppfattning om vad som förväntas.

Johan Stenberg removed his/her comment
commented 11 October 2013

Tack då vet jag vad jag ska göra!

commented 12 October 2013

Vet inte om du svarar på frågor under helgen Viggo, all heder om du gör det men jag har full förståelse om du inte gör det. Svar på måndag blir nog i senaste laget, men jag har bara mig själv att skylla som inte tänkt på att fråga om detta tidigare. Det gäller två frågor kring uppgift 3 och båda berör minneskomplexitet. Ett ja eller nej räcker för min del. 

1) Det är inte angivet hur stort 's' kan vara i 'r[1..s]'. Vi vet att i '(j,[i1..ik])' så är 'j' och 'i' mindre än 'm', men även att det kan förekomma fler förekomster av ett ämne i 'r'. Med andra ord så finns inte angivet någon begränsning på 's'. Ska vi därmed anta att 's' kan vara hur stort som helst, t ex kan vi inte med säkerhet veta att det går att deklarera en array av storlek 's'?

2) Får vi ha hur komplexa datastrukturer som helst (om man kan motivera varför de behövs)? För att ta ett konstigt exempel: kan jag, i uppgift 3, deklarera en m*m-matris där varje element är en heap  - om det behövs?

commented 12 October 2013

Erik, som Viggo skrev tidigare så verkar det som att minneskomplexiteten inte spelar någon roll i denna uppgift, utan det han vill att man ska optimera är tidskomplexiteten.

I övriga fall brukar man nästan alltid kunna anta att minnesanvändningen får vara åtminstone linjär mot storleken på indata. Det vill säga man kan anta att indatat får plats i RAM.

commented 12 October 2013

Tack Emil! Det svaret duger för mig om du läser det här Viggo. Så du behöver endast svara ifall Emils resonemang inte skulle vara ok.

Eric Klaesson removed his/her comment
commented 13 October 2013

Angående Eriks exempel om komplexa datastrukturer, kan man anta att tiden det tar att skapa dessa är försumbar? Är det till exempel okej att deklarera en m*m-matris av stackar? Tekniskt sett så behöver man väl ägna konstant tid per element för att initialisera varje stack, vilket då skulle göra tidskomplexiteten beroende av m.

commented 13 October 2013

Okej, ang latex-paketet som Emil rekommenderade för pseudokod.

Jag ville dela upp pseudokoden på två sidor och det har jag lyckats med..

dock vill jag sätta radräknaren till rätt siffra, då den börjar om på 1 igen på andra sidan. Låt oss säga att jag vill sätta den på 24 istället.

Har läst lite i dokumentationen, men detta fungerar ju inte.. och vad betyder alg@inmargin?
\newcounter{alg@inmargin}\setcounter{alg@inmargin}{24}

commented 13 October 2013

Hmm jag vet inte, Eric. Oftast brukar algoritmerna få plats på en sida :)

Kan du kanske dela upp koden i två eller fler funktioner?

commented 14 October 2013

Vet inte vilket algo-paket ni använder men algpseudocode kan man göra

\setcounter{ALG@line}{11}

med t.ex.

\begin{algorithmic}[1]
\setcounter{ALG@line}{11}
\For{$i := 1$ to $m$}
    \State $n := n+1$
\EndFor
\end{algorithmic}

None

commented 23 October 2013

Hur gör man om man ännu inte redovisat Mästarprov 1 och det inte verkar finns några lediga tider att boka kvar?

Teacher commented 23 October 2013

Hej Magnus! Sista redovisningspassen var idag onsdag 23 oktober 2013. Du hade bokat ett pass igår. Det går inte att redovisa mästarprovet efter idag, så vi får hänvisa till ommästarprovet i januari.

commented 31 October 2013

Nu när mästarprov 1 är redovisat och klart, kommer det att läggas upp lösningsförslag för uppgifterna?

commented 1 November 2013

Se till att prenumerera på kursen i kth social, då får du uppdateringar direkt på emailen ;)

https://www.kth.se/social/course/DD1352/subgroup/adk13/post/resultat-pa-mastarprov-1-mast/

John Eriksson removed his/her comment
commented 1 November 2013

Emil, jag har redan inställt att få dagliga mejl från KTH Social, men det skickades först kl. 4 på natten timmarna efter att jag frågade. När jag skickade kommentaren kunde jag inte heller se någon länk bland menyerna.

commented 1 November 2013

Jag håller med om att kth social inte är optimalt för att föra fram viktig information, då information från lärare brukar spridas ut på tre olika sätt: genom att uppdatera sidorna som finns, genom att posta viktig information bland kommentarer till inlägg, eller skapa nya "lärarinlägg" som finns till höger i menyn på kursens startsida som är ganska svåra att upptäcka tycker i alla fall jag.

Det man kan göra är att ställa in inställningarna på att man får notifieringsmailen "direkt" istället för ett samlat mail kl 4 på natten. Det kan man ställa in här: https://www.kth.se/social/course/DD1352/subscription/

commented 18 November 2013

Angående mästarprov 2, uppgift 1, får man anta att textpackningsproblemet alltid blir en Nej-instans (oavsett målfunktion) om någon ordlängd är större än radlängden?

Teacher commented 18 November 2013

(Det är bara beslutsproblem som har ja-instanser och nej-instanser.)

Ni kan, liksom i mästarprov 1, anta att alla ordlängder i indata är begränsade av radlängden.

commented 18 November 2013

Hej,

Får man anta någon övre gräns för hur stora talen i indata-mängden till mängdpartitioneringsproblemet i uppgift 1 kan vara? Eller räcker det att analysera tidskomplexiteten med avseende på enhetskostnad?

Teacher commented 19 November 2013

Förtydligande till uppgift 1 och 3 på mästarprov 2

Uppgift 1

Egentligen är NP definierat med hjälp av Turingmaskinen, och därför ska bitkostnad användas vid komplexitetsanalysen om man ska vara noga. NP-verifikationen och reduktionen ska vara polynomiska i indatas längd. Om indata består av n bitar så är uppenbarligen antalet tal i indata mindre än n och största talet i indata mindre än n bitar.

Uppgift 3

Ni kan anta att det existerar en lösning till problemet, alltså att det i indata finns minst ett exjobb för varje mål som bedömts ha bristande kvalitet.

Teacher commented 20 November 2013

Bedömningen av uppgift 1 på mästarprov 2

I uppgift 1 är alla indata positiva heltal. Jag har fått frågor om vad som händer om man ändå tillåter ordlängder som är noll. Bedömningen av uppgift 1 kommer att bli så att den som löser uppgiften med ordlängder som tillåts vara noll (men i övrigt har en korrekt lösning) får mindre fel. Det är nämligen bara en liten ändring av reduktionen som behövs för att den inte ska generera några ordlängder som är noll.

commented 20 November 2013

Kan man anta att listan med positiva tal i mängdpartitioneringsproblemet innehåller minst ett tal?

commented 21 November 2013

Måste bitkostnad användas för uppgifternas komplexitetsanalys eller är det endast ifall man skall vara noga?

Teacher commented 22 November 2013

Emil: Ja, det går bra att anta att mängdpartitioneringsproblemets indata består av minst ett tal.

Adrian: Bitkostnad ger bara en faktor n större komplexitet (där n är antalet bitar i största talet) i detta fall så det spelar ingen roll för kravet att algoritmen ska vara polynomisk. Men jag vill gärna att ni visar att ni kan räkna med bitkostnad, så gör det!

commented 22 November 2013

Får man underkänt eller mindre fel om man räknar med enhetskostnad istället för bitkostnad?

Teacher commented 23 November 2013

Om man inte räknar med bitkostnad i den skriftliga lösningen får man chans att fixa till det vid den muntliga redovisningen.

commented 23 November 2013

På fråga tre på mästerprov 2 ska man anta att UKÄ problemets lösning bara är ja eller nej, eller kan man anta att den om ja skickar med en ja-instans som är utformad så som vi antog i fråga 2?

I lösningarna till gamla mästarprov ser det ut som om man bara kan säga att det är uppenbart att reduktionen är polynomisk, utan att ange exakt vad komplexiteten blir, när är det ok att detta är uppenbart?

Känner mig lite osäker på komplexitetsanalys med bitkostnad så vart kan man läsa mer om det? (utöver det som står på frl 1)

På lösningen till mästerprov 2 2012 första uppgiften anges att komplexiteten är O(n^2), beror det på att sigma adderas med si vilket med bikostnad tar n tid och att detta sker i en for-loop så det blir n^2? Om jag har en räknare i en loop som adderar 1 för varje varv, är komplexiteten då n^2 med bitkostnad, n för att n varv sker och n för varje addition?

På fråga 1 om man känner sig ganska lost på beviset av att reduktionen är korrekt (men är ganska säker på att den är korrekt, kan bara inte motivera det), kan man istället reducera ett av problemen från frl 25 till det givna problemet eller är det just Mängdpartitionering som måste reduceras?

Teacher commented 23 November 2013

Här är svar på alla Moas frågor på mästarprov 2:

1. Ett beslutsproblemet är alltid en fråga med svaret ja eller nej. En algoritm som löser beslutsproblemet svarar på denna fråga; den ger alltså ett booleskt värde som resultat. En ja-instans är ett indata till ett beslutsproblem för vilket problemets svar är ja.

2. Det är uppenbart när det är uppenbart. Om du och läraren som du redovisar för har olika uppfattningar om vad som är uppenbart så får du förklara varför det är uppenbart. Det lönar sig alltså inte att skriva att något är uppenbart om man inte tycker det.

3. Bitkostnad innebär inget mer är det som står på föreläsning 1. Det finns många exempel i kursens övningar och i gamla mästarprov som du kan titta på. Bitkostnad och enhetskostnad skiljer sig bara åt när det sker beräkningar med stora tal. I detta mästarprov är det bara additioner av tal som görs och då räcker det att veta att det tar linjär tid i talens storlek (dvs antal bitar i talen) att addera två tal.

4. I uppgift 1 från mästarprovet 2012 adderas tal med n bitar n gånger, vilket tar tid O(n^2). Att räkna upp en räknare med steget 1 från 1 till n innebär n stycken additioner av tal med log n bitar vilket tar O(n log n). Om man gör det riktigt smart räcker det faktiskt med O(n) bitoperationer.

5. Det är tillåtet att i uppgift 1 välja ett av problemet ur listan från föreläsning 25 att reducera, men jag vill inte rekommendera det.

commented 24 November 2013

Var finns listan över NP-svåra problem som man kan utgå ifrån att de är NP-svåra i mästarproven? Och vad är den engelska benämningen på mängdpartitionering?

commented 24 November 2013

Daniel:

Ordlista för ADK (partition problem): https://www.kth.se/social/course/DD1352/page/ordlista-8/

Lista på NP-fullständiga problem: http://www.csc.kth.se/utbildning/kth/kurser/DD1352/adk13/schema/F25.pdf

commented 25 November 2013

På uppgift 3, kan man anta att det alltid finns en lösning för dem indata man får, dvs att det verkligen finns ett tal k för vilket det för varje mål finns minst ett exjobb som har bristande kvalitet?

commented 25 November 2013

Tonima: Se Viggos inlägg 19 november kl. 00:24 på denna sida. 

"Uppgift 3
Ni kan anta att det existerar en lösning till problemet, alltså att det i indata finns minst ett exjobb för varje mål som bedömts ha bristande kvalitet."

commented 27 November 2013

Måste man använda bitkostnad även vid komplexitetsanalysen av uppgift 3, eller är det okej med enhetskostnad där?

Teacher commented 27 November 2013

Problemet i uppgift 3 har inga tal som indata så det lär inte vara aktuellt att räkna med stora tal i den uppgiften. Därför finns det ingen anledning att använda bitkostnad.

commented 28 November 2013

Varför har Anders Ye 0 lediga platser! Jag är djupt besviken är det någon som kanske vill byta? :)

commented 28 November 2013

Alltså angående formuläret man ska fylla i:

"visualiseringsdemo den 10/11 (NP-reduktionsvisualisering med Alvie)"

10 november var en söndag så då hade vi ingen föreläsning.

Teacher commented 28 November 2013

Sant. Alvie-demon var 11/11 och inte 10/11!Var snäll och tolka 10/11 som 11/11 i formuläret.

Niklas Axelsson removed his/her comment
Niklas Axelsson removed his/her comment
Teacher commented 25 December 2013

Niklas, det står rätt i uppgiften. Du behöver läsa på mer om hur man visar NP-fullständighet.

Feedback News