Ommästarprov 2
- Inlämningsdatum 4 jan 2024 av 19:00
- Poäng 0
- Lämnar in en filuppladdning
- Filtyper pdf
- Tillgänglig 18 dec 2023 kl 12:00–4 jan 2024 kl 19.30
Detta ommästarprov ger möjlighet att bli godkänd (betyg E) på mästarprov 2 (momentet MAS2).
Ommä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. Vid ordinarie mästarproven var vi tvungna att anmäla ett fall av misstänkt otillåtet samarbete. Du får inte använda generativ AI för att lösa mästarprovsuppgifterna. 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 senast torsdag 4 januari 2024 klockan 19.00 i Canvas som PDF-dokument. Det är tillåtet att skriva för hand och skanna in dokumentet.
Skriv ditt namn och KTH-adress överst på framsidan av lösningarna. Läs på din inlämning inför den muntliga redovisningen som kommer att ske i Zoom under perioden 8-11 januari 2024. Boka tid för muntlig redovisning senast 4 januari klockan 19. Bokningslistorna läggs upp 3 januari sist på denna sida.
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 uppgiften 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 i uppgiftslydelsen är oklart. Du kan skriva frågan i Canvas eller mejla den till viggo@kth.se
För godkänt (betyg E) på mästarprov 2 krävs helt rätt på uppgiften.
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. Format/datastruktur för indata och utdata ska du välja själv om det inte står specificerat i uppgiften.
Mästarprov 2, E-uppgift
Betygskriterium: jämföra problem med hänsyn till komplexitet med hjälp av reduktioner: förklara principerna, utföra enklare reduktioner mellan givna problem.
I denna uppgift är det viktigt att du visar att du kan principerna för NP-fullständighet och reduktioner. Ett fullständigt bevis för reduktionens korrekthet krävs inte.
Ledning: För en triangel där två av hörnen inte är grannar med något hörn utanför triangeln behöver (minst) två av hörnen vara med i delmängden för att alla triangelns hörn ska vara dubbeldominerade.
Detaljerade bedömningskriterier
För att det ska bli extra tydligt hur uppgiften 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.
E-nivå för mästarprov 2
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.
| Bedömningsgrund | Krav för uppgiften |
| NP-fullständighet/NP-tillhörighet | |
| Förklarar principerna för NP-fullständighetsbevis | ja |
| Förklarar vad en lösning består av | ja |
| Visar NP-tillhörighet | ja |
| Motiverar att verifikationsalgoritmen (motsv.) är polynomisk | ja |
| Reduktionsalgoritm | |
| Beskriver reduktionen övergripande i ord och ev. i bild | måttliga |
| Beskriver reduktionen tydligt | ja |
| Reduktionen är korrekt | ja |
| Tidskomplexitet för reduktionen | |
| Reduktionen är polynomisk | ja |
| Anger tidskomplexitet i lämpliga variabler | ja |
| Motiverar tidskomplexitet | måttliga |
| Korrekthetsresonemang | |
| Redogör för vad som i allmänhet behöver visas i ett korrekthetsbevis av denna typ |
ja |
| Framställer grundläggande idé för korrekthetsresonemanget |
nej |
| Genomför ett fullständigt korrekthetsresonemang | nej |
Ovanstående krav ska vara uppfyllda efter den muntliga redovisningen. Kraven på den skriftliga lösningen är något lägre.
Bokning av muntlig redovisning
Boka senast 4 januari 2024 klockan 19 en tid för en tiominuters muntlig redovisning av ommästarprov 2. Det är olika tider för redovisning av ommästarprov 1 och ommästarprov 2.
Länk till bokningslistor som publiceras 3 januari.
Läs instruktionerna nedan innan du bokar!
Redovisningen är 10 minuter. Var beredd att visa ID. Om redovisningen är i Zoom ska du ha kameran på.
Den tid som står på bokningslistesidan är tiden för den första redovisningen det aktuella redovisningspasset. När du bokar en tid ska du därför notera vilken tid du får.
Bokningslistorna stängs för ändring efter deadline, så du kan inte byta redovisningstid efter 4 januari.
Det är 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 reduktioner och algoritmer muntligt och reda ut eventuella oklarheter.
Hitta matris
