dynamisk programmering tentafrågor

Vad är dynamisk programmering?

En metod för att lösa komplexa problem genom att bryta ner dem i enklare delproblem. Lagrar lösningar för att undvika upprepade beräkningar.

Vilka typer av problem löser dynamisk programmering?

Optimaliseringsproblem och kombinatoriska problem, såsom sekvensalignering och resursallokering.

Fyll i luckan: Dynamisk programmering bygger på _____ och optimal delstruktur.

Memoization

Vad betyder optimal delstruktur?

Ett problem har optimal delstruktur om en optimal lösning kan konstrueras från optimala lösningar av dess delproblem.

Vad är memoization?

En teknik där resultatet av delproblem lagras för att undvika att beräkna dem igen, vilket sparar tid.

Sant eller falskt: Dynamisk programmering alltid kräver mer minne än en iterativ lösning.

Falskt. Dynamisk programmering kan ibland använda mindre minne genom att optimera hur data lagras.

Jämför top-down och bottom-up metoder.

Top-down: börjar med hela problemet och löser delproblem efter behov. Bottom-up: löser delproblem först och kombinerar dem.

Ge ett exempel på optimal substruktur.

I Fibonacci-serien: $\displaystyle F(n) = F(n-1) + F(n-2)$ gäller att $\displaystyle F(n)$ bygger på $\displaystyle F(n-1)$ och $\displaystyle F(n-2)$.

Vad är tidskomplexiteten för dynamisk programmering?

Ofta O(n*m), där n och m är storlekar på indata. Beror på problemets struktur.

Vad är ett tillstånd i dynamisk programmering?

En unik representation av delproblemen som används för att lagra och återanvända lösningar.

Fyll i luckan: Dynamisk programmering används ofta i _____ problem.

Optimerings- och sekvensproblem.

Vad är problemet med överlappande delproblem?

Delproblem som dyker upp flera gånger. Dynamisk programmering utnyttjar detta för att spara tid.

Ge exempel på en algoritm som använder dynamisk programmering.

Knapsack-problemet, där man maximerar värdet av föremål i en ryggsäck med begränsad vikt.

Vad är en rekursiv lösning?

En metod där problemet löses i termer av sig själv. Kan leda till ineffektivitet utan memoization.

Vad används ett beslutsträd till?

För att visualisera och analysera val och deras konsekvenser, ofta i dynamiska programmeringsproblem.

Vad innebär principen om optimal substruktur?

Optimal substruktur innebär att en optimal lösning av ett problem kan byggas upp av optimal lösningar av dess delproblem. Exempel: För att lösa ett kortaste vägen problem kan man kombinera kortaste vägarna mellan delmålen.

Vad är knapsackproblemet?

Ett optimeringsproblem där man maximerar värdet av objekt i en ryggsäck med begränsad kapacitet.

Sann eller falsk: Fibonacci-sekvensen använder dynamisk programmering.

Sann. Dynamisk programmering används för att effektivt beräkna Fibonacci-tal.

Vad är en typisk tillämpning av dynamisk programmering?

Lösning av problem som involverar delproblem, t.ex. sekvensalignering, knapsack, och kortaste vägen.

Fyll i blank: 0-1 knapsack maximerar _____ under en viktbegränsning.

värdet av objekt.

Jämför top-down och bottom-up metoder.

- Top-down: Rekursiv, memoization - Bottom-up: Iterativ, fyller tabeller

Hur beräknas Fibonacci-talen med dynamisk programmering?

Genom att lagra tidigare beräknade värden: $\displaystyle F(n) = F(n-1) + F(n-2)$.

Vad är längsta gemensamma delmängd?

Ett problem som använder dynamisk programmering för att hitta den längsta gemensamma sekvensen mellan två strängar.

Ge ett exempel på knapsackproblemet.

Givet objekt med vikter och värden, välj objekt för att maximera värdet utan att överskrida viktgränsen.

Sann eller falsk: Dynamisk programmering kräver alltid fullständig information.

Falsk. Den kan ofta lösa problem med delvis information genom att bygga upp lösningen.

Vad är minsta kostnadsvägen?

Ett problem där man hittar den minsta kostnaden att nå en punkt i en graf.

Fyll i blank: Dynamisk programmering används för att lösa problem med _____ överlappande delproblem.

överlappande delproblem.

Jämför tidskomplexiteten för rekursiv och dynamisk lösning av Fibonacci.

- Rekursiv: O(2^n) - Dynamisk: O(n)

Vad är delproblem i dynamisk programmering?

Delproblem är mindre versioner av det ursprungliga problemet. Lösning av dessa är nyckeln till att lösa det stora problemet.

Definiera optimal substruktur.

Optimal substruktur innebär att en optimal lösning av ett problem kan byggas upp av optimal lösning av dess delproblem.

Vad är överlappande delproblem?

Överlappande delproblem är när samma delproblem löses flera gånger i en beräkning. Dynamisk programmering utnyttjar detta för att spara beräkningstid.

Ge ett exempel på en strategi.

Memoisering - lagra resultat av delproblem för att undvika omberäkning.

Sant eller falskt: Dynamisk programmering är alltid snabbare än bruteforce.

Sant. Dynamisk programmering är effektivare eftersom den utnyttjar tidigare beräkningar.

Jämför topp-ned och botten-upp strategier.

Topp-ned: rekursiv med memoization. Botten-upp: iterativ, löser små delproblem först.

Fyll i tomrummet: DP används för att ______.

optimera lösningar av problem med överlappande delproblem.

Nämn en användning av dynamisk programmering.

Ruttoptimering: hitta den kortaste vägen i grafproblem.

Vad är en rekursiv formel?

En rekursiv formel definierar ett problem i termer av sig själv. Exempel: $\displaystyle F(n) = F(n-1) + F(n-2)$ för Fibonacci.

Vad är grundprincipen för dynamisk programmering?

Att bryta ner ett problem i enklare delproblem och spara resultatet för framtida användning.

Beskriv tabellmetoden.

En metod för att organisera lösningar av delproblem i en tabell för snabb åtkomst och beräkning.

Ge ett exempel på ett delproblem.

I knapsack-problemet, beräkna maxvärdet av en delmängd av objekt med viktbegränsning.

Vad menas med tidskomplexitet?

Tidskomplexitet beskriver hur mycket tid en algoritm tar att köra beroende på storleken på indata. Vanliga notationer är O(n), O(log n) och O(n^2).

Vad är rumskomplexitet?

Rumskomplexitet avser den mängd minne som en algoritm använder som funktion av indata. Det är viktigt för att förstå algoritmers effektivitet i minnesanvändning.

True or False: Dynamisk programmering alltid minimerar tidskomplexitet.

False. Dynamisk programmering kan minska tidskomplexiteten, men det kan öka rumskomplexiteten genom att lagra mellanresultat.

Jämför bruteforce och dynamisk programmering.

- Bruteforce: hög tidskomplexitet, låg rumskomplexitet. - Dynamisk programmering: lägre tidskomplexitet, högre rumskomplexitet.

Komplettera: Tidskomplexitet för Fibonacci med DP är _____.

O(n) jämfört med O(2^n) för rekursiv lösning.

Vad är memoization?

Memoization är en teknik där mellanresultat lagras för att undvika onödiga beräkningar. Detta förbättrar tidskomplexiteten i dynamiska programmeringslösningar.

Ge ett exempel på rumskomplexitet.

Exempel: En algoritm som lagrar alla delproblem i en array har rumskomplexitet O(n), där n är antalet delproblem.

Vad är en rekursiv relation?

En rekursiv relation definierar hur ett problem kan delas upp i mindre delproblem. Den är central i dynamisk programmering för att formulera lösningar.

Vad innebär optimal substruktur?

Optimal substruktur innebär att lösningen av ett problem kan konstrueras optimalt från lösningarna av sina delproblem. Det är en nyckelfunktion i dynamisk programmering.

Förklara top-down och bottom-up strategier.

Top-down: Rekursiv metod med memoization. Bottom-up: Iterativ metod som bygger lösningar från små delproblem uppåt.

Vad är gränsen för rumskomplexitet i DP?

Gränsen beror på antalet delproblem som lagras. I värsta fall kan det vara O(n) eller O(n*m) för tvådimensionella problem.

Ge ett exempel på optimering i DP.

Exempel: Att minimera kostnaden för att nå ett mål genom att lagra de lägsta kostnaderna för varje delproblem.