Dynamisk programmering 3

Detta är materialet till föreläsning 11 som är direkt efter föreläsning 10 den 19 september 2016. Vi använder omvänd undervisning (flipped classroom) för detta moment i kursen, vilket innebär att du före föreläsningen ska titta på dessa videor och försöka svara på tillhörande småuppgifter. Om du undrar något efter att ha gått igenom materialet får du gärna använda kommenterafunktionen för att ställa frågor som kan besvaras på föreläsningen. I övrigt kommer föreläsningen att bestå av problemlösning gruppvis och gemensamt.

• Titta på första videon.
• Använd informationen i totmaxpos och maxpos[i] för att konstruera och returnera elementen i den längsta delföljden. (Det kan finnas flera lika långa längsta delföljder, men algoritmen har bara lagrat information om en av dom i totmaxpos och maxpos.)
  Skriv pseudokod för konstruktionen av lösningen och analysera sedan tidskomplexiteten för konstruktionen.

• Titta på andra videon, så får du först se Viggos lösning på konstruktionen och sedan se hur man motiverar korrektheten av dynamiskprogrammeringsalgoritmer, något som är viktigt att kunna till mästarprov 1.
• Fundera på följande fråga:
  Varför gäller det att \(\delta(i,j)=d_{ij}^{(n-1)}\), alltså att längden av kortaste stigen från hörn i till hörn j är lika med längden av kortaste stigen från hörn i till j som innehåller högst n-1 kanter?
  n står för antalet hörn i grafen.
• Svaret på frågan ges i inledningen av den tredje videon, och därefter visas algoritmen som beräknar lösningen på problemet.
• Kärnan i algoritmen är följande slinga:
  for m\(\leftarrow\)2 to n-1 do
       D\(\leftarrow\)Extend(D, (\(w_{ij}\)))
  Vad är en lämplig invariant för denna slinga? Invarianten ska vara sann varje gång man kommer till början av forslingan och även då man lämnar forslingan (då med m=n).
  a) \(d_{ij}^{(m)}=\min_{1\le k\le n}(d_{ik}^{(m-1)}+w_{kj})\)
  b) \(D=(d_{ij}^{(m-1)})\)
  c) \(D=(d_{ij}^{(m)})\)
• Svaret på frågan ges i inledningen av fjärde och sista videon, och därefter visas en oväntad uppsnabbning av algoritmen.
• Om du har några frågor som du vill ha besvarade på föreläsningen så kan du skriva dom som kommentar till denna sida.

Läsanvisningar till kursboken

På sida 290-301 och 307-311 i Kleinberg-Tardos kan du se fler exempel på konstruktion och bevis av dynamiskprogrammeringsalgoritmer.

Föreläsning 10 och 11 den 19 september 2016 kl 10-12

På föreläsningarna 19 september 2016 klockan 10-12 i sal D1 kommer vi förutom att ta upp frågorna arbeta med konstruktion och motivering av dynamiskprogrammeringsalgoritmer för olika problem, däribland återigen matriskedjemultiplikation.