• kth.se
  • Studentwebben
  • Intranät
  • kth.se
  • Studentwebben
  • Intranät
Logga in
DD2350 HT22 (adk22)
Ommästarprov 2
Hoppa över till innehåll
Översikt
  • Logga in
  • Översikt
  • Kalender
  • Inkorg
  • Historik
  • Hjälp
Stäng
  • Min översikt
  • DD2350 HT22 (adk22)
  • Uppgifter
  • Ommästarprov 2
  • Startsida
  • Kursöversikt
  • Uppgifter
  • Course Evaluation

Ommästarprov 2

  • Inlämningsdatum 4 Jan 2023 av 19:00
  • Poäng 0
  • Lämnar in en filuppladdning
  • Filtyper pdf
  • Tillgänglig 19 Dec 2022 kl 12:00–4 Jan 2023 kl 19.30
Den här uppgiften låstes 4 Jan 2023 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. Detta är något som vi tar allvarligt på. Inlämningarna plagiatgranskas. Misstänkt otillåtet samarbete måste enligt KTH:s regler anmälas till rektor. Vid ordinarie mästarproven var vi tvungna att anmäla ett fall av misstänkt otillåtet samarbete.

Skriftliga lösningar ska lämnas in senast onsdag 4 januari 2023 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 under perioden 9-12 januari 2023. 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 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.

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.

Problemet är en variant på Artistproblemet i det ordinarie mästarprovet. Det gäller i den nya varianten av problemet att boka in alla artister på dom hotell som finns tillgängliga. Till skillnad mot i problemet i det ordinarie mästarprovet är det bara för hotell 1 som antalet hotellplatser är begränsat, nämligen till 5. För övriga hotell finns ingen begränsning för hur många artister som ryms. Det finns, liksom i det tidigare problemet, en lista med par av artister som inte vill bo tillsammans. Varje artist finns med i minst ett par i listan.
Beslutsproblemet är att, givet antalet hotell och en lista med par av artister som inte vill bo på samma hotell, avgöra ifall det är möjligt att boka in alla artister på dom tillgängliga hotellen så att inga restriktioner bryts.
Visa att detta beslutsproblem är NP-fullständigt genom att dels visa att det ligger i NP och dels utforma en polynomisk Karpreduktion mellan det NP-fullständiga problemet Graffärgning (se föreläsning 25) och artistproblemet.

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.

Exempel på indata:

3 hotell, lista LaTeX: \left((a_1,a_2), (a_1, a_4), (a_1,a_5), (a_2, a_3), (a_2, a_4), (a_3, a_5), (a_4, a_5), (a_4, a_6), (a_5,a_6), (a_5,a_7)\right)((a1,a2),(a1,a4),(a1,a5),(a2,a3),(a2,a4),(a3,a5),(a4,a5),(a4,a6),(a5,a6),(a5,a7))

Detta är exempel på en ja-instans, eftersom en bokning av artisterna 1, 3 och 6 på hotell 1, 2 och 5 på hotell 2, samt 4 och 7 på hotell inte bryter mot några restriktioner..

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

Här kommer länk till bokningslistor att läggas upp 3 januari.

Läs instruktionerna nedan innan du bokar!

Redovisningen är 10 minuter och sker i Zoom. Du ska ha kameran på och vara beredd att visa ID vid redovisningen.

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.

1672855200 01/04/2023 07:00pm
Inkludera en beskrivning
Ytterligare kommentarer:
Maxresultat för gradering till > poäng
Inkludera en bedömningstitel

Matris

 
 
 
 
 
 
 
     
Det går inte att ändra en matris efter att du börjat använda den.  
Hitta en matris
Hitta matris
Inkludera en titel
Titel
Du har redan bedömt studenter med den här matrisen. Större ändringar kan påverka resultaten för deras uppgifter.
Titel
Kriterier Bedömningar Poäng
Redigera beskrivning av kriterium Ta bort kriterium rad
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera ranking Radera ranking
5 till >0 poäng
Full poäng
blank
Redigera ranking Radera ranking
0 till >0 poäng
Inga poäng
blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Redigera beskrivning av kriterium Ta bort kriterium rad
Det här kriteriet är länkat till ett lärandemål Beskrivning av kriterium
tröskel: 5 poäng
Redigera ranking Radera ranking
5 till >0 poäng
Full poäng
blank
Redigera ranking Radera ranking
0 till >0 poäng
Inga poäng
blank_2
Det här området kommer användas av utvärderaren för kommentarer relaterade till det här kriteriet.
poäng
  / 5 poäng
--
Ytterligare kommentarer
Poängsumma: 5 av 5
Föregående
Nästa
Ommästarprov 1 Bokning av munta