06: Programmazione Dinamica

True (A)

sottostruttura della soluzione e sottoproblemi ripetuti

<p>memoization</p> Signup and view all the answers

<p>Fibonacci = Un esempio classico di problema risolvibile con la programmazione dinamica PD = Programmazione dinamica DI = Divide-et-impera LCS = Longest Common Subsequence</p> Signup and view all the answers

<p>PD può gestire sottoproblemi dipendenti, DI no (C)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>caratterizzazione della struttura di una soluzione</p> Signup and view all the answers

<p>Longest Common Subsequence (A)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Z è LCS(X, Y) e z = x.</p> Signup and view all the answers

<p>Z</p> Signup and view all the answers

<p>x = y = Z è LCS(X, Y) e z = x x ≠ y = L'ultimo elemento di Z può essere x o y Z è LCS(X, Y) = Indica che Z è una sottosequenza comune Z non è LCS(X, Y) = Esiste un'altra LCS Z' che include più elementi</p> Signup and view all the answers

<p>Z è LCS(X, Y) oppure Z è LCS(X, Y). (A)</p> Signup and view all the answers

<p>False (B)</p> Signup and view all the answers

<p>Z è LCS(X, Y) oppure Z è LCS(X, Y).</p> Signup and view all the answers

<p>LCS</p> Signup and view all the answers

<p>$f_n = f_{n-1} + f_{n-2}$ (A)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>esponenziale</p> Signup and view all the answers

<p>Fibonacci</p> Signup and view all the answers

<p>Esponenziale (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Crea una formula chiusa per calcolare i numeri di Fibonacci.</p> Signup and view all the answers

<p>massima</p> Signup and view all the answers

<p>Fib-Memoization = Θ(n) spazio e tempo Fib-BottomUp = Θ(n) tempo e spazio Fib-Iter = Θ(1) spazio e Θ(n) tempo Fib-Recursivo = Crescita esponenziale</p> Signup and view all the answers

<p>Utilizza meno spazio (C)</p> Signup and view all the answers

<p>True (A)</p> Signup and view all the answers

<p>Z prende elementi non necessariamente consecutivi da X.</p> Signup and view all the answers

<p>1</p> Signup and view all the answers

Un approccio alla soluzione dei problemi che scompone il problema in sottoproblemi e utilizza le soluzioni dei sottoproblemi per costruire la soluzione completa.

Un metodo per risolvere problemi scomponendoli in sottoproblemi indipendenti. Ogni sottoproblema viene risolto una volta e la soluzione finale è ottenuta combinando le soluzioni dei sottoproblemi.

Una delle principali proprietà che rendono un problema adatto alla programmazione dinamica. Indica che la soluzione ottimale del problema può essere costruita a partire dalle soluzioni ottimali dei suoi sottoproblemi.

Seconda proprietà importante per la programmazione dinamica. Indica che lo stesso sottoproblema viene incontrato più volte durante il processo di risoluzione.

Un passo nella risoluzione di un problema con la programmazione dinamica che consiste nel memorizzare le soluzioni dei sottoproblemi per evitare di calcolarle ogni volta.

Un algoritmo che risolve un problema lavorando dal basso verso l'alto. Inizia con i sottoproblemi più piccoli e gradualmente costruisce la soluzione finale.

Un problema che consiste nel trovare la sottosequenza più lunga comune a due sequenze di caratteri date.

Una tecnica che cerca di risolvere un problema riutilizzando le soluzioni dei sottoproblemi. Si basa sulla proprietà di sottostruttura e la presenza di sottoproblemi ripetuti.

Un approccio bottom-up per la risoluzione di un problema prevede la costruzione della soluzione passo dopo passo, partendo da soluzioni più piccole fino a raggiungere la soluzione completa.

La successione di Fibonacci è una sequenza di numeri in cui ogni numero è la somma dei due numeri precedenti. Inizia con 0 e 1, quindi i numeri successivi sono 1, 2, 3, 5, 8, 13, e così via.

Un algoritmo ricorsivo è un algoritmo che si chiama da solo per risolvere parti più piccole dello stesso problema.

La complessità asintotica di un algoritmo descrive come il tempo di esecuzione dell'algoritmo cresce al crescere della dimensione dell'input. Ad esempio, un algoritmo con complessità lineare cresce linearmente in tempo al crescere dell'input.

Un albero di chiamate è una rappresentazione visiva delle chiamate ricorsive in un algoritmo. Ogni nodo nell'albero rappresenta una chiamata alla funzione ricorsiva.

La memoizzazione è una tecnica di ottimizzazione che memorizza i risultati intermedi di un calcolo per evitarne il ricalcolo.

Fib-Memoization è una versione dell'algoritmo di Fibonacci che utilizza la memoizzazione per migliorare la sua efficienza. Memorizza i risultati intermedi del calcolo per evitare il ricalcolo.

Fib-BottomUp è una versione bottom-up dell'algoritmo di Fibonacci che costruisce la soluzione passo dopo passo, partendo dai primi termini della sequenza.

Fib-Iter è una versione iterativa dell'algoritmo di Fibonacci che utilizza un ciclo per calcolare la sequenza.

La massima sottosequenza comune (LCS) è la sequenza più lunga che è sottosequenza di due o più sequenze.

Due sequenze di DNA possono essere confrontate per trovare la massima sottosequenza comune di basi che hanno in comune.

Una sottosequenza è una sequenza che può essere ottenuta da un'altra sequenza eliminando alcuni elementi (non necessariamente consecutivi).

Una massima sottosequenza comune è la sottosequenza più lunga che è comune a due o più sequenze.

Un prefisso di una sequenza è una sottosequenza che contiene tutti gli elementi dalla prima posizione fino a una posizione data nella sequenza originale.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e l'ultimo elemento di 𝑍 è 𝑥, allora 𝑍 è anche la LCS del prefisso di 𝑋 che termina con 𝑥 e di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e l'ultimo elemento di 𝑍 è 𝑥, allora 𝑍 è anche la LCS dei prefissi di 𝑋 e 𝑌 che terminano rispettivamente con 𝑥 e con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e l'ultimo elemento di 𝑍 è 𝑥, e 𝑥 è uguale all'ultimo elemento di 𝑌, allora 𝑍 è anche la LCS dei prefissi di 𝑋 e 𝑌 che terminano rispettivamente con 𝑥 e con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e 𝑥 è diverso dall'ultimo elemento di 𝑌, allora 𝑍 è la LCS del prefisso di 𝑋 che termina con 𝑥 o del prefisso di 𝑌 che termina con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e 𝑥 è uguale all'ultimo elemento di 𝑌, allora 𝑍 è anche la LCS del prefisso di 𝑋 che termina con 𝑥 e del prefisso di 𝑌 che termina con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e 𝑥 è diverso dall'ultimo elemento di 𝑌, allora 𝑍 è la LCS del prefisso di 𝑋 che termina con 𝑥 o del prefisso di 𝑌 che termina con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e 𝑥 è uguale all'ultimo elemento di 𝑌, allora 𝑍 è anche la LCS del prefisso di 𝑋 che termina con 𝑥 e del prefisso di 𝑌 che termina con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e 𝑥 è diverso dall'ultimo elemento di 𝑌, allora 𝑍 è la LCS del prefisso di 𝑋 che termina con 𝑥 o del prefisso di 𝑌 che termina con l'ultimo elemento di 𝑌.

Se 𝑍 è la LCS di 𝑋 e 𝑌, e 𝑥 è uguale all'ultimo elemento di 𝑌, allora 𝑍 è anche la LCS del prefisso di 𝑋 che termina con 𝑥 e del prefisso di 𝑌 che termina con l'ultimo elemento di 𝑌.