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)
  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 först i fjärde och sista videon, och därefter visas en oväntad uppsnabbning av algoritmen.