Mästarprov 1

Inlämningsdatum 15 okt 2024 av 19:00
Poäng 0
Lämnar in en filuppladdning
Filtyper pdf
Tillgänglig 26 sep 2024 kl 8:00–15 okt 2024 kl 19.20

Den här uppgiften låstes 15 okt 2024 kl 19.20.

Mästarprovet ska lösas individuellt och redovisas både skriftligt och muntligt. Inget samarbete är tillåtet, se vidare hederskodexen. Du ska alltså inte diskutera lösningar med någon annan fram till dess att alla muntliga redovisningar är avklarade. Vi tar mycket allvarligt på detta och följer KTH:s riktlinjer om att misstänkta fall av samarbete ska anmälas till rektor. (Förra året blev några studenter anmälda och sedan avstängda av disciplinnämnden för otillåtet samarbete i mästarprovet.) Du får inte använda generativ AI för att lösa mästarprovsuppgifterna och inte heller för att granska eller förbättra din lösning. Däremot får du gärna använda generativ AI för att typsätta med LaTeX. Inlämningarna plagiatgranskas.

Skriftliga lösningar ska lämnas in i Canvas (som PDF; inskannade handskrivna lösningar går bra) senast tisdag 15 oktober 2024 klockan 19:00. Det är viktigt att du lämnar in i tid! Om du inte ser någon inlämningsknapp på denna sida så ska du kontrollera att du är inloggad i Canvas. Klicka i så fall på inloggningsikonen i den blåa vänstermenyn.

Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på dina lösningar inför den individuella muntliga redovisningen som kommer att ske 21–25 oktober (i tentaveckan) i Zoom eller på KTH för någon av lärarna. Boka tid för en 10 minuters (om du har löst en uppgift) eller 20 minuters (om du har löst 2-3 uppgifter) muntlig redovisning senast 15 oktober klockan 20. Bokningslistorna läggs upp 14 oktober, se sist på denna sida. Vänta med att boka tid tills du har lämnat in uppgiften.

Det är viktigt att du förbereder dig inför den muntliga redovisningen. För att en uppgift ska godkännas ska du kunna förklara och motivera algoritmen muntligt och reda ut eventuella oklarheter.

Läs uppgifterna mycket noga så att du inte råkar basera dina lösningar på en missuppfattning. Fråga en lärare på kursen om något är oklart, företrädesvis på föreläsningarna 26-27 september eller via diskussioner i kursrummet. Formatet/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.

Mästarprovet är ett obligatoriskt moment i kursen. Det består av tre uppgifter som motsvarar betygskriterierna för E, C respektive A. För godkänt (betyg E) krävs helt rätt på en av uppgifterna. Helt rätt på två av uppgifterna ger betyg C och alla rätt ger betyg A. Ett mindre fel på en uppgift sänker betyget ett steg. Läs mer om betyg under rubriken Examination och slutförande i kurs-PM.

För att se exempel på hur utförliga lösningarna bör vara kan du titta på lösningar till tidigare mästarprov, både autentiska studentlösningar och mönsterlösningar. Där finns också tips om hur man skriver pseudokod, som du bör läsa innan du formulerar dina algoritmer.

Uppgift 1 Ättlikhet

Betygskriterium: utveckla algoritmer med datastrukturer för enkla problem givet en konstruktionsmetod.

En ätt kan enligt Wikipedia Links to an external site. definieras som "Alla avkommor till en viss anfader eller anmoder. Detta är en unilinjär härstamningsgrupp." Enligt denna definition ingår inte gemåler i ätten utan bara avkomlingar ("ättlingar") och själva anfadern eller anmodern.

Det kan vara intressant att undersöka om olika ätter har samma struktur som varandra.

Din uppgift är att först bestämma en lämplig datastruktur för att lagra en ätt inklusive dess strukturella egenskaper (anfader/anmoder, kön och barnrelationer) och sedan konstruera en algoritm som givet en lista med LaTeX: n $n$ stycken ätter svarar sant om alla ätterna i listan är strukturellt lika med varandra och falskt annars. Algoritmen ska vara effektiv (polynomisk i $n$ och LaTeX: m $m$ där $n$ är antalet ätter i listan och $m$ är antalet medlemmar i den största ätten). Använd dekomposition som algoritmkonstruktionsmetod. Du kan anta att ingen person i ätten har mer än tolv barn, och du kan också anta att samma individ inte finns på flera ställen i samma ätt (t ex både som sonsonsonson och dotterdotterdotterson).

Beskriv din algoritm med pseudokod och beräkna tidskomplexiteten (gör en tight analys som du anger med ordoklass/thetaklass).

Något korrekthetsbevis för din pseudokod behövs inte i denna uppgift, men du ska redogöra för vad som skulle behöva visas i ett korrekthetsbevis.

Uppgift 2 Måntransporter

Betygskriterium: utveckla algoritmer med datastrukturer för icketriviala problem.

Året är 2172 och du är ansvarig för att bygga grundläggande transportinfrastruktur på månen. Ett antal baser är planerade på månytan och under ytan. Det är så dyrt att bygga något på månen att målet är att minimera kostnaden av nätverket och inte tiden någon transport tar. Det är dock nödvändigt att det går att nå vilken bas som helst från varje annan bas.
Dina kollegor, som är fysiker och geologer, har redan undersökt vilka baser som skulle kunna förbindas med hänsyn till geologin och befintliga basers verksamhet.
Du får en lista med baser representerade som heltal $LaTeX: \left(1,2,\ldots,n\right)$ $\left(1,2,\ldots,n\right)$ och en lista $LaTeX: \left(i_1,j_1\right),\left(i_2,j_2\right),\ldots,\left(i_m,j_m\right)$ $\left(i_1,j_1\right),\left(i_2,j_2\right),\ldots,\left(i_m,j_m\right)$ med potentiella förbindelser mellan baser som par av sådana heltal.
Det finns dock flera transportsätt: vägförbindelse, linbana, eller raketdriven kapsel. Väg är billig att bygga i korta sträckor, men dyrt för långa pga avståndet ifrån någon bas. Linbana är billigast för medellånga sträckor. Raketdriven kapsel är billig för långa resor, men dyr för korta resor eftersom raketbaser är dyra att bygga.
Ingen hänsyn tas till tidsåtgång eller energiförbrukning för något transportsätt när den faktiskt används.
Avstånden (i meter) och kostnaden (i kronor) för de olika typerna av förbindelser ges av funktioner som avbildar potentiella förbindelser på positiva heltal:

$LaTeX: D\left(i,j\right)$ $D\left(i,j\right)$ ger avståendet mellan $i$ och $j$ .
$LaTeX: V\left(i,j\right)$ $V\left(i,j\right)$ ger vägkostnaden för $LaTeX: \left(i,j\right)$ $\left(i,j\right)$ .
$LaTeX: L\left(i,j\right)$ $L\left(i,j\right)$ ger linbanekostnaden för $LaTeX: \left(i,j\right)$ $\left(i,j\right)$ .
$LaTeX: R\left(i,j\right)$ $R\left(i,j\right)$ ger raketkapselkostnaden för $LaTeX: \left(i,j\right)$ $\left(i,j\right)$ .

Alla tre kostnadsfunktionerna växer monotont med längden på en förbindelse, dvs för ett givet transportsätt är en längre förbindelse alltid dyrare.

Din algoritm ska som utdata ge en lista med förbindelser som ska byggas (som är bland de möjliga förbindelserna som angivits av dina kollegor) och för varje förbindelse indikera om det är väg $LaTeX: \left(V\right)$ $\left(V\right)$ , linbana $LaTeX: \left(L\right)$ $\left(L\right)$ , eller raketbaser för raketkapsel $LaTeX: \left(R\right)$ $\left(R\right)$ som är lämpligt att bygga. Din lösning ska minimera totala kostnaden för bygget.

Konstruera en effektiv algoritm för problemet. Använd pseudokod för att beskriva algoritmen. Analysera tidskomplexiteten uttryckt i antalet baser och antalet möjliga förbindelser (med enhetskostnad), och den får högst vara kubisk. Motivera också att algoritmen är korrekt.

Det är tillåtet att använda och hänvisa till en datastruktur från kurslitteraturen (kursböckerna) i din lösning, om du gör tydligt varifrån datastrukturen är hämtad och hur den anropas i din algoritm. Du behöver inte visa korrektheten för en hjälpdatastruktur från kurslitteraturen.

Uppgift 3 Ättlikhet med oordnade barnskaror

Betygskriterium: utveckla algoritmer med datastrukturer för svårare problem med den metod som passar bäst.

Vi återvänder i denna uppgift till problemet att visa strukturell likhet för ätter. Skillnaden i denna uppgift är att hänsyn inte ska tas till ordningen mellan barn (dvs plats i syskonskaran). Det innebär att en ätt som består av en anmoder som har två barn, där dottern är äldre än sonen (och som inte har egna barn) ska räknas som strukturellt lika med en ätt som består av en anmoder som har två barn där dottern är yngre än sonen.

Indata är liksom i uppgift 1 en lista med LaTeX: n $n$ stycken ätter där ingen ätt innehåller fler än LaTeX: m $m$ personer och ingen person har mer än 12 barn, och algoritmen ska svara sant om alla ätterna i listan är strukturellt lika med varandra (utan hänsyn till plats i barnskaran) och falskt annars.

I exemplet ovan (i uppgift 1) är dom två ätterna strukturellt lika om vi inte tar hänsyn till plats i barnskaran.

Konstruera en så effektiv algoritm som möjligt för problemet. Analysera tidskomplexiteten med enhetskostnad (så dom vanliga taloperationerna på godtyckligt stora tal tar konstant tid). Du ska visa att din algoritm har optimal tidskomplexitet med avseende på ordoklass. Använd pseudokod för att beskriva algoritmen. Du ska också tydligt tala om vad som krävs (allmänt sett) för att bevisa korrektheten för den typ av algoritm som du skrivit och sedan bevisa korrektheten för din algoritm. Formulera invarianter för slingor och ingångs- och utgångsvillkor för eventuella hjälpfunktioner.

Det är tillåtet att använda och hänvisa till en algoritm från kurslitteraturen (kursböckerna) i din lösning, om du gör tydligt varifrån algoritmen är hämtad och hur den anropas i din algoritm. Du behöver inte visa korrektheten för en hjälpalgoritm från kurslitteraturen.

(En algoritm som går en log-faktor långsammare än den optimala räknas som mindre fel.)

Detaljerade bedömningskriterier

Mästarprov 1 betygsätts efter betygskriterierna för målen utveckla algoritmer med datastrukturer samt analysera algoritmer med avseende på effektivitet och korrekthet. Dessutom kommer målet jämföra alternativa algoritmer och datastrukturer med hänsyn till effektivitet och pålitlighet naturligt att övas vid algoritmkonstruktionen.

För att det ska bli extra tydligt hur dom tre uppgifterna bedöms och för att dom assistenter som tar emot redovisningar ska hålla precis samma kravnivå finns det detaljerade bedömningskriterier, som assistenterna bedömer både skriftligt och muntligt på ett bedömningsprotokoll.

Följande tabell visar kraven för dom olika uppgifterna.

Bedömningsgrund	Krav för uppgift 1 (E)	Krav för uppgift 2 (C)	Krav för uppgift 3 (A)
Algoritmbeskrivning
Modellerar problemet på ett rimligt sätt	nej (givet)	höga	höga
Beskriver algoritmen övertygande i ord och ev. i bild	måttliga	måttliga	höga
Beskriver algoritmen i pseudokod	ja	ja	ja
Bra urval av detaljer i pseduokoden	måttliga	måttliga	måttliga
Algoritmen är tillräckligt effektiv	polynomisk	kubisk	optimal
Algoritmen löser rätt problem	ja	ja	ja
Tidskomplexitet
Anger tidskomplexitet i föreskrivna variabler	ja	ja	ja
Motiverar tidskomplexitet	måttliga	höga	höga
Korrekthetsresonemang
Redogör för vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ	endast principerna	måttliga	höga
Framställer grundläggande idé för korrekthetsresonemanget	nej	ja	ja
Genomför ett fullständigt korrekthetsresonemang som omfattar alla delar	nej	ja, givet ledtråd vid redovisningen	ja

Ovanstående krav ska vara uppfyllda efter den muntliga redovisningen. Kraven på den skriftliga lösningen är något lägre.

Om uppgift 2 eller 3 redovisas för betyg E (dvs om uppgift 1 inte lösts/godkänts) används betygskriterierna för E (uppgift 1) vid bedömningen. Dock är kravet på algoritmens tidskomplexitet fortfarande det som uppgiften anger.

Bokning av muntlig redovisning 21-25 oktober

Tider för muntlig redovisning kommer att finnas mellan 21 och 25 oktober.

Lämna in din skriftliga lösning i Canvas innan du bokar tid för muntlig redovisning. Du kan boka tid fram till kl 20 den 15 oktober. Efter det är tiderna fixa och kan inte ändras.

Observera att det är olika bokningslistor för den som redovisar för betyg E och för den som redovisar för betyg A-D. Den som bara har gjort en uppgift, eller som har försökt på flera uppgifter men bara till kriterienivå E, ska boka tid på en lista märkt "för betyg E". Den som har löst flera uppgifter och når upp till kriterienivå C på uppgift 2 eller 3 ska boka tid på en lista märkt "för betyg A-D".

Anmäl dig inte för redovisning för en assistent som du känner väl, för då blir det jäv. Om vi upptäcker en jävssituation plockar vi bort bokningen, och då kan det bli svårare att hitta en ny redovisningstid som passar.

På bokningslistan står om redovisningen sker i Zoom eller på KTH. Du ska i båda fallen kunna visa ID vid redovisningen.

Redovisningen är 10 minuter om du redovisar för betyg E och 20 minuter om du redovisar för betyg A-D. Det är i båda fallen viktigt att du förbereder dig inför den muntliga redovisningen så att du snabbt kan svara på assistentens frågor. För att en uppgift ska godkännas ska du kunna förklara och motivera algoritmen muntligt och reda ut eventuella oklarheter.