Teoriuppgifter till labb 4

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 5 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 vid redovisningen ha med en lösning. Om det är flera som samarbetat om lösningen ska du se till att det framgår klart (se hederskodex). Överarbeta inte lösningen - den behöver inte se snygg ut. Ta med lösningen på papper till övningen. Det går bra att lämna in en handskriven lösning.

Teoriuppgifter

1. Skriv på valfritt sätt ned ett certifikat (lämpligen en rolltilldelning som kan användas för att verifiera att en instans är en ja-instans) 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?