Introduktion till reduktioner, omvänd föreläsning

Förberedelser inför föreläsningen

Titta på den här videon:

Här är föreläsningsanteckningarna: f20.pdf Download f20.pdf

Det finns också ett avsnitt om reduktioner i kursboken. (KT: 451-459)

Uppgifter som görs under föreläsningen

1

Räcker det med att det finns en matching i den bipartita grafen för att det ska finnas en lösning på motsvarande representantproblem? Om inte, vad krävs av matchningen för att representantproblemet ska vara lösbart?

2

På sidorna 2-5 i föreläsningsanteckningarna beskrivs fyra stycken reduktioner. Vissa av dem går på båda hållen, men vissa inte. Vilka av reduktionerna går bara på ett håll? Och varför fungerar inte reduktionen på det andra hållet?

3

Formulera Maximal Oberoende Mängd som ett beslutsproblem, ett optimeringsproblem och ett konstruktionsproblem.

Visa sedan hur man kan reducera optimeringsproblemet till beslutsproblemet, och hur man kan reducera konstruktionsproblemet till optimeringsproblemet.

Vad är tidskomplexiteten för de två reduktionerna?

Om du har tid över, visa också hur man kan reducera beslutsproblemet till optimeringsproblemet, och hur man kan reducera optimeringsproblemet till konstruktionsproblemet.