Dynamisk programmering 1

Detta är materialet till föreläsning 9 den 14 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 den 14 september. I övrigt kommer föreläsningen att bestå av problemlösning gruppvis och gemensamt.

• Titta först på denna video.
• Prova denna visualisering av Fibonaccitalsberäkning genom att beräkna fib(7), först med Fibonacci Recursive och sedan med Fibonacci Table (som är dynamisk programmering).
• Kontrollfrågor att svara på:
  1. Vad skiljer dekomposition från dynamisk programmering?
  2. Varför går det snabbare med dynamisk programmering än med en rekursiv implementation?
• Klicka här för att få se svaren och nästa video.