Dynamisch programmeren begrippen

Wat is dynamisch programmeren?

Een optimalisatietechniek die problemen oplost door het opsplitsen in overlappende deelproblemen.

Definieer overlapping subproblemen.

Subproblemen die meerdere keren voorkomen in de oplossing van een groter probleem. Dit leidt tot efficiëntie door hergebruik.

Wat betekent optimaliteit?

De eigenschap dat een oplossing de best mogelijke waarde heeft, vaak gemeten in kosten of tijd.

Wat zijn memoization en tabulation?

Memoization: opslaan van resultaten in een cache. Tabulation: opbouwen van een DP-tabel van onderaf.

Vul de lege plek in: De basis van dynamisch programmeren is ________.

de decompositie van een probleem in subproblemen.

True or False: Dynamisch programmeren is altijd de snelste oplossing.

False. Het biedt vaak snellere oplossingen dan brute-force, maar is niet altijd de snelste.

Wat is een DP-tabel?

Een datastructuur die de resultaten van subproblemen opslaat, waardoor het algoritme sneller kan werken.

Vergelijk brute-force en dynamisch programmeren.

Brute-force: onderzoekt alle mogelijke oplossingen. Dynamisch programmeren: focust op overlappende deelproblemen voor efficiëntie.

Wat is de rol van de basisgevallen?

Basisgevallen zijn fundamentele oplossingen die de startpunten vormen voor het opbouwen van andere oplossingen.

Geef een voorbeeld van een klassiek DP-probleem.

Het Fibonacci-getal: $\displaystyle F(n) = F(n-1) + F(n-2)$ met basisgevallen $\displaystyle F(0) = 0$, $\displaystyle F(1) = 1$.

Wat is de tijdcomplexiteit van de Fibonacci-reeks met memoization?

O(n), omdat elk subprobleem slechts één keer wordt berekend.

Wat zijn beslissingsproblemen?

Problemen die een ja of nee antwoord vereisen, vaak relevant in dynamisch programmeren.

Vul de lege plek in: Dynamisch programmeren is vooral nuttig voor ________.

problemen met een structurele herhaling.

Wat is een state in dynamisch programmeren?

Een representatie van de huidige status van het probleem, vaak gedefinieerd door parameters.

Geef een toepassing van dynamisch programmeren.

Het knapsackprobleem: het maximaliseren van de waarde van voorwerpen in een rugzak met gewichtslimiet.

Wat is de rol van de recursieve structuur?

Deze structuur helpt bij het definiëren van de relatie tussen de deelproblemen en de uiteindelijke oplossing.

Wat is de knapsack probleem?

Een optimalisatieprobleem waarbij een verzamelaar items met verschillende waarden en gewichten moet kiezen om in een rugzak van beperkte capaciteit te passen. Doel is om de totale waarde te maximaliseren.

Wat is het verschil tussen de 0-1 knapsack en de fractionele knapsack?

0-1 knapsack laat alleen hele items toe, terwijl fractionele knapsack ook delen van items toestaat. Hierdoor is de fractionele knapsack gemakkelijker op te lossen.

Vul het in: de Fibonacci-reeks kan worden berekend met ________ programmeren.

dynamisch

Wat is de toepassing van dynamisch programmeren in de edit distance?

Het bepaalt het minimale aantal bewerkingen (invoegen, verwijderen, vervangen) om één string in een andere te veranderen. Dit wordt vaak gebruikt in tekstvergelijkingen en spellingscorrectie.

Waarvoor worden dynamische programmeren technieken gebruikt in spraakherkenning?

Bij het optimaliseren van de waarschijnlijkheid van sequenties van woorden, waarbij de beste volgorde wordt gekozen op basis van eerder geluisterde woorden.

Waarbij helpt het longest common subsequence probleem?

Het vindt de langste reeks elementen die in een bepaalde volgorde voorkomen in twee of meer sequenties. Dit is nuttig voor versiebeheer en DNA-sequencing.

Is het waar of niet: dynamisch programmeren kan alle NP-problemen efficiënt oplossen.

Niet waar. Dynamisch programmeren is effectief voor specifieke problemen, maar niet voor alle NP-problemen.

Geef een voorbeeld waar dynamisch programmeren wordt toegepast in de routeplanning.

Bij het vinden van de kortste route tussen twee steden op basis van afstand of reistijd, waarbij verschillende tussenstops kunnen worden geoptimaliseerd.

Wat is de rol van dynamisch programmeren in de coin change problem?

Het zoekt naar de minimum aantal munten dat nodig is om een bepaalde waarde te bereiken, door alle mogelijke combinaties van munten te overwegen.

Wat is de toepassing van dynamisch programmeren in portfolio-optimalisatie?

Het helpt bij het kiezen van een optimale set van investeringen om het verwachte rendement te maximaliseren onder gelimiteerde risico's.

Wat is de relatie tussen dynamisch programmeren en machine learning?

Dynamisch programmeren helpt bij het optimaliseren van parameters en het maken van beslissingen in algoritmen zoals reinforcement learning.

Vul het in: de ________ algoritme maakt gebruik van dynamisch programmeren om de kortste pad tussen knopen te vinden.

Dijkstra's

Wat is memoization?

Een techniek waarbij resultaten van subproblemen worden opgeslagen en hergebruikt om herberekeningen te vermijden.

Vul de lege plek in: Greediness is _______ en dynamisch programmeren is _______.

suboptimaal; optimaal

Wat is het doel van optimalisatie in dynamisch programmeren?

Het minimaliseren van tijdcomplexiteit en ruimtecomplexiteit van algoritmen.

Waarvoor wordt een kostentabel gebruikt?

Om de kosten van subproblemen bij te houden, zodat optimale beslissingen kunnen worden genomen.

True or False: Dynamisch programmeren is altijd sneller dan brute force.

True; omdat het subproblemen oplost en resultaten opslaat, vermindert het de rekenlast.

Vergelijk top-down met bottom-up aanpak.

Top-down: begint met het grote probleem en splitst het op. Bottom-up: lost subproblemen op en bouwt naar het grote probleem.

Wat is de rol van recursie in dynamisch programmeren?

Recursie wordt gebruikt om een probleem op te splitsen in kleinere, beheersbare subproblemen.

Vul de lege plek in: De tijdcomplexiteit van een dynamisch programmeren algoritme is vaak _______.

polynoomtijd, zoals O(n^2)

Geef een voorbeeld van een technologische toepassing van dynamisch programmeren.

Optimalisatie van leverroutes in logistiek met behulp van de 'Travelling Salesman Problem'.

Wat is de betekenis van 'overlapping subproblems'?

Een eigenschap waarbij dezelfde subproblemen meerdere keren voorkomen in verschillende takken van de rekenschema.

Noem een techniek voor het verminderen van ruimtecomplexiteit.

In-place optimalisatie; het gebruik van enkele variabelen in plaats van een volledige tabel.

Wat is de relatie tussen dynamisch programmeren en optimalisatie?

Dynamisch programmeren is een strategie voor het oplossen van optimalisatieproblemen door efficiënt subproblemen op te lossen.