Programmazione Dinamica PDF

25/03/2021 Programmazione dinamica Algoritmi e strutture dati Ugo de’Liguoro, Andras Horvath 1 Sommario obiettivi: – migliorare la comprensione della complessità deg...

25/03/2021 Programmazione dinamica Algoritmi e strutture dati Ugo de’Liguoro, Andras Horvath 1 Sommario obiettivi: – migliorare la comprensione della complessità degli algoritmi ricorsivi e del modo di riutilizzare la soluzione di sottoproblemi del problema dato argomenti – Fibonacci con ricorsione, memoization e bottom-up – la programmazione dinamica – problema LCS (longest common subsequence) 2 1  25/03/2021 Programmazione dinamica (PD) versus Divide-et-Impera (DI) PD e DI si basano sulla scomposizione ricorsiva di un problema in sottoproblemi DI è efficiente se i sottoproblemi sono indipendenti tra loro se i sottoproblemi non sono indipendenti tra loro, DI può richiedere tempi più lunghi del necessario (spesso esponenziali) mentre PD (ove applicabile) riesce a ridurli (spesso a polinomiali) 3 Condizioni di applicabilità per applicare PD occorre siano verificate le proprietà: 1. sottostruttura della soluzione (ottima nel caso di problemi di ottimizzazione): deve esserci una relazione fra le soluzioni (ottimali) degli sottoproblemi e la soluzione (ottimale) del problema 2. sottoproblemi ripetuti 4 2  25/03/2021 Fasi di sviluppo 1. caratterizzazione della struttura di una soluzione 2. definizione ricorsiva della soluzione 3. eliminare le ripetizioni mediante annotazione dei risultati più semplici (memoization) 4. sviluppo di un approccio bottom-up, e dunque iterativo 5 Successione di Fibonacci Quante coppie di conigli nascono dopo n generazioni a partire da una coppia, se ogni coppia genera una coppia per la gen. succ. ed una per quella ancora succ. e poi muore? 6 3  25/03/2021 Successione di Fibonacci Quante coppie di conigli nascono dopo n generazioni a partire da una coppia, se ogni coppia genera una coppia per la gen. succ. ed una per quella ancora succ. e poi muore? definita come 𝑓 = 0, 𝑓 = 1, 𝑓 =𝑓 +𝑓 per 𝑛 > 1 fase 1 e fase 2 già fatte perché la definizione stessa della quantità che si vuole calcolare e ricorsiva 7 Algoritmo ricorsivo complessità asintotica della soluzione ricorsiva? (differisce leggermente dalla definizione classica: calcola correttamente solo per n > 0) 8 4  25/03/2021 Albero delle chiamate il numero di nodi al livello soddisfa: 𝑁 = 1, 𝑁 = 1, 𝑁 =𝑁 +𝑁 + 1 per 𝑛 > 2 9 Albero delle chiamate il numero di nodi soddisfa una ricorsione a simile a quella della sequenza di Fibonacci ma è facile vedere che: 𝑁 >𝑓 formula di Binet: 𝑓 = Φ − −1 Φ con Φ = Φ > 1, −1 < −1 Φ < 1 𝑁 ∈ Ω(Φ ), quindi ha crescita esponenziale dunque il tempo di calcolo di Fib è almeno esponenziale 10 5  25/03/2021 Albero delle chiamate Fib ci mette cosi tanto perché ci sono tanti calcoli ripetuti fase3: annotiamo (memoizziamo) i risultati ottenuti strada facendo 11 Fib con memoization spazio utilizzato da Fib-Memoization per l'array memo è Θ(𝑛) 12 6  25/03/2021 Fib con memoization 2 l'albero ha un sviluppo "lineare verso sinistra" e dunque sia tempo sia spazio di Fib-Memoization sono Θ(𝑛) 13 Fib bottom-up con array tempo di Fib-BottomUp è Θ(𝑛) spazio utilizzato da Fib-BottomUp è Θ(𝑛) 14 7  25/03/2021 Fib bottom-up senza array tempo di Fib-Iter è Θ(𝑛) spazio utilizzato da Fib-Iter è Θ(1) 15 Massima sottosequenza comune - LCS obiettivo: Dati due filamenti di DNA vogliamo misurare la loro somiglianza calcolando la più lunga sottosequenza di basi che hanno in comune 16 8  25/03/2021 Massima sottosequenza comune - LCS date due sequenze 𝑆 e 𝑆 : la massima sottosequenza comune è 𝑆 17 Definizioni date due sequenze 𝑋 e 𝑍: 𝑍 ⊑ 𝑋, cioè 𝑍 è sottosequenza di 𝑋, se 𝑍 prende elementi non necessariamente consecutivi da 𝑋 una sottosequenza 𝑍 è LCS(𝑋, 𝑌), cioè 𝑍 è massima sottosequenza comune, se 𝑍 ⊑ 𝑋 ∧ 𝑍 ⊑ 𝑌 ∧ 𝑍 ha lunghezza massima 𝑍 in generale non è unica 18 9  25/03/2021 Definizioni prefissi: esempi: 19 Proprietà della sottostruttura date due sequenze 𝑋 = 𝑥 , … , 𝑥 e 𝑌 = 𝑦 , … , 𝑦 proviamo a mettere in relazione LCS(𝑋, 𝑌) e la soluzione di problemi LCS che coinvolgono anche prefissi di 𝑋 e 𝑌 distinguiamo due casi: 𝑥 = 𝑦 e 𝑥 ≠ 𝑦 𝑥 =𝑦 : – se 𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌) allora quale sarà l'ultimo elemento di 𝑍? – l'ultimo elemento di 𝑍 dovrebbe essere 𝑥 – se z = 𝑥 allora 𝑍 è LCS di quali prefissi di 𝑋 e 𝑌? – 𝑍 è LCS(𝑋 ,𝑌 ) 20 10  25/03/2021 Proprietà della sottostruttura date due sequenze 𝑋 = 𝑥 , … , 𝑥 e 𝑌 = 𝑦 , … , 𝑦 proviamo a mettere in relazione LCS(𝑋, 𝑌) e la soluzione di problemi LCS che coinvolgono anche prefissi di 𝑋 e 𝑌 distinguiamo due casi: 𝑥 = 𝑦 e 𝑥 ≠ 𝑦 𝑥 ≠𝑦 : – se 𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌) allora il suo ultimo elemento può essere 𝑥 o 𝑦 o qualcosa altro – di sicuro o 𝑥 o 𝑦 non serve per formare 𝑍 – 𝑍 è LCS(𝑋 , 𝑌) oppure 𝑍 è LCS(𝑋, 𝑌 ) (o tutti e due) 21 Proprietà della sottostruttura Lemma 1. Siano 𝑋 = 𝑥 , … , 𝑥 e 𝑌 = 𝑦 , … , 𝑦 ; se 𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌) e 𝑥 = 𝑦 allora 𝑍 è LCS(𝑋 ,𝑌 ) e z = 𝑥. dimostrazione per assurdo di 𝑍 è LCS(𝑋 ,𝑌 ): assumiamo che 𝑍 non è LCS(𝑋 ,𝑌 ) 𝑍 è LCS(𝑋, 𝑌) e quindi 𝑍 ⊑ 𝑋 ∧ 𝑍 ⊑ 𝑌 e quindi 𝑍 ⊑𝑋 ∧𝑍 ⊑𝑌 se 𝑍 non è LCS(𝑋 , 𝑌 ) allora esiste 𝑍′ = 𝑧′ , … , 𝑧′ che è LCS(𝑋 , 𝑌 ) e 𝑍 = ℎ > 𝑘 − 1 ma allora se 𝑥 = 𝑦 abbiamo 𝑧′ , … , 𝑧 , 𝑥 ⊑ 𝑋 ∧ 𝑧 ,…,𝑧 ,𝑥 ⊑ 𝑌 ∧ 𝑧 ,…,𝑧 ,𝑥 >𝑘 e questo contradice al "𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌)" 22 11  25/03/2021 Proprietà della sottostruttura Lemma 1. Siano 𝑋 = 𝑥 , … , 𝑥 e 𝑌 = 𝑦 , … , 𝑦 ; se 𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌) e 𝑥 = 𝑦 allora 𝑍 è LCS(𝑋 ,𝑌 ) e z = 𝑥. dimostrazione per assurdo di z = 𝑥 : assumiamo per assurdo 𝑧 ≠𝑥 allora 𝑧 ,…,𝑧 ,𝑥 ⊑ 𝑋 ∧ 𝑧 ,…,𝑧 ,𝑥 ⊑ 𝑌 ∧ 𝑧 ,…,𝑧 ,𝑥 >𝑘 e questo contradice al "𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌)" 23 Proprietà della sottostruttura Lemma 2. Siano 𝑋 = 𝑥 , … , 𝑥 e 𝑌 = 𝑦 , … , 𝑦 ; se 𝑍 = 𝑧 , … , 𝑧 è LCS(𝑋, 𝑌) e 𝑥 ≠ 𝑦 allora 𝑍 è LCS(𝑋 , 𝑌) oppure 𝑍 è LCS(𝑋, 𝑌 ). ) è evidente che sia cosi perché se 𝑥 ≠ 𝑦 allora l'ultimo elemento di 𝑍 o non è 𝑥 o non è 𝑦 e quindi l'ultimo elemento di 𝑋 o l'ultimo elemento di 𝑌 non serve per trovare il loro LCS 24 12  25/03/2021 Proprietà della sottostruttura segue da Lemma 1 e Lemma 2 suggerisce anche una procedura ricorsiva usando k = 𝑋 + 𝑌 = 𝑚 + 𝑛 la relazione di ricorrenza 𝑇 𝑘 = 2𝑇 𝑘 − 1 + 1 fornisce un limite superiore per l'ordine di grandezza del tempo di calcolo 𝑇 𝑘 ∈Θ 2 = Θ(2 ) 25 Definizione ricorsiva 26 13  25/03/2021 Algoritmo bottom-up 27 Algoritmo bottom-up 28 14  25/03/2021 Algoritmo bottom-up Complessità: Θ(𝑚 ⋅ 𝑛) 29 Algoritmo bottom-up Complessità: Θ(𝑚 ⋅ 𝑛) 30 15