Dynamisk programmering 1.4

  • Hur ser den triangulära matrisen M ut?
    Svar: a) Eftersom radnumret representerar första matrisen i kedjan i delproblemet och kolumnnumret sista matrisen i kedjan så måste radnumret alltid vara mindre än kolumnnumret, vilket innebär att matrisen M är högertriangulär.
  • Fundera nu vidare på steg 3 för matriskedjemultiplikationsproblemet. Försök komma fram till en lämplig beräkningsordning och skriv sedan en algoritm som beräknar delproblemens värden enligt din beräkningsordning.
  • 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äs sida 251-260 i Kleinberg-Tardos, helst före föreläsningen.
  • På föreläsningen 14 september klockan 12-13 i sal D1 kommer vi förutom att ta upp frågorna arbeta med steg 3 i dynamisk programmering för olika problem, däribland matriskedjemultiplikation.
Feedback Nyheter