DD2350HT191
    Teoriuppgifter till labb 4
    Hoppa över till innehåll
    Översikt
    • Logga in
    • Översikt
    • Kalender
    • Inkorg
    • Hjälp
    Stäng
    • Min översikt
    • DD2350HT191
    • Uppgifter
    • Teoriuppgifter till labb 4
    • Startsida

    Teoriuppgifter till labb 4

    • Inlämningsdatum 7 nov 2019 av 14.15
    • Poäng 1

    Dessa teoriuppgifter hör till labb 4 och kan redovisas för en teoripoäng till tentan. Redovisningen görs skriftligt och muntligt på övningen den 8 november (ingen annan redovisningsmöjlighet finns). Det är frivilligt att redovisa teoriuppgifterna, men för att klara av att göra labben bör du ha gjort dom. Arbeta gärna i grupp med labbteoriuppgifterna, men var och en ska av administrativa skäl ta med en egen skriftlig lösning med namn på som lämnas in vid redovisningen. Skriv gärna för hand!

    Läsanvisningar för teoriuppgifterna:

    • labblydelsen
    • föreläsning 20 (reduktioner) och 25 (NP-fullständighetsbevis) 
    • sida 451-459 och 463-495 i KT (Kleinberg-Tardos)

     

    Teoriuppgifter

    1. Skriv på valfritt sätt ned en lösning till ja-instansen av rollbesättningsproblemet som finns som indataexempel.
    2. Visa att rollbesättningsproblemet ligger i NP.
    3. Förändra nej-instansen i exemplet på indata till en ja-instans. Hur många skådespelare behöver du lägga till i just detta fall?
    4. Vilken är den minsta möjliga produktion som uppfyller indatakraven för rollbesättningsproblemet och som går att sätta upp? Skriv upp indata för denna produktion!
    5. Tänk dig en instans där rollerna är indelade i två grupper, ungefär som i matchningsproblemet, där rollerna aldrig förekommer i samma scener som roller ur samma grupp. Hur många skådespelare behövs då?
    6. Anta att film a innehåller en scen med rollerna 4, 7 och 12 medan film b har tre scener med rollerna 4 och 7, 7 och 12 samt 4 och 12. Om alla övriga villkor är identiska mellan filmerna - kommer svaren då att bli likadana? Varför/varför inte?
    1573132500 11/07/2019 02:15pm
    Ytterligare kommentarer:
    Maxresultat för gradering till > poäng

    Matris

     
     
     
     
     
     
     
         
    Det går inte att ändra en matris efter att du börjat använda den.  
    Hitta en matris
    Hitta matris
    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
    Poängsumma: 5 av 5