Didattica e Fondamenti degli Algoritmi e della Calcolabilità Quarta giornata Risolvere...

Didattica e Fondamenti degli Algoritmi e della

Calcolabilità

Quarta giornataRisolvere efficientemente un problema in P: la sequenza di

FibonacciGuido Proietti

Email: [email protected]:

www.di.univaq.it/~proietti/index_personal

1

http://www.di.univaq.it/~proietti/index_personal

Riepilogo: gerarchia delle classi

2

Decidibili

ExpTime(ARRESTO(k))P (ricerca)

NP

NP-completi (SAT)

Congettura P ≠ NP

Progettare un algoritmo

Vogliamo ora progettare algoritmi (per problemi calcolabili!) che:– Producano correttamente il risultato

desiderato– Siano efficienti in termini di tempo di

esecuzione ed occupazione di memoria

3

Le quattro proprietà fondamentali di un algoritmo (oltre l’efficienza)

• La sequenza di istruzioni deve essere finita • Essa deve portare ad un risultato corretto • Le istruzioni devono essere eseguibili

materialmente • Le istruzioni non devono essere ambigue

4

Algoritmi e strutture dati

• Concetto di algoritmo è inscindibile da quello di dato

• Da un punto di vista computazionale, un algoritmo è una procedura che prende dei dati in input e, dopo averli elaborati, restituisce dei dati in output

I dati devo essere organizzati e strutturati in modo tale che la procedura che li elabora sia “efficiente”

5

Analisi di algoritmi Correttezza:

– dimostrare formalmente che un algoritmo è corretto

Complessità:– Stimare la quantità di risorse (tempo e

memoria) necessarie all’algoritmo– stimare il più grande input gestibile in tempi

ragionevoli– confrontare due algoritmi diversi– ottimizzare le parti “critiche”

6

Copyright © 2004 - The McGraw - Hill Companies, srl7

Un problema numerico «giocattolo»:

i numeri di Fibonacci


Leonardo da Pisa (anche noto come Fibonacci) [1170-1240] si interessò di molte cose, tra cui il seguente problema di dinamica delle popolazioni:

L’isola dei conigli

Quanto velocemente si espanderebbe una popolazione di conigli sotto appropriate condizioni?

In particolare, partendo da una coppia di conigli in un’isola deserta, e data una certa regola di riproduzione, quante coppie si avrebbero nell’anno n?


• Una coppia di conigli concepisce due coniglietti di sesso diverso ogni anno, i quali formeranno una nuova coppia

• La gestazione dura un anno

• I conigli cominciano a riprodursi soltanto al secondo anno dopo la loro nascita

• I conigli sono immortali (!)

Le regole di riproduzione


L’albero dei conigli

La riproduzione dei conigli può essere descritta in un albero come segue:


• All’inizio dell’anno n, ci sono tutte le coppie dell’anno precedente, e una nuova coppia di conigli per ogni coppia presente due anni prima

La regola di espansione

• Indicando con Fn il numero di coppie all’inizio dell’anno n, abbiamo la seguente relazione di ricorrenza:

1 se n=1,2Fn-1 + Fn-2 se n≥3Fn =


Il problema

Come calcoliamo Fn ?

Primi numeri della sequenza di Fibonacci:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, F18=2584,…


Digressione: la sezione aureaRapporto fra due grandezze disuguali a>b, in

cui a è medio proporzionale tra b e a+b

(a+b) : a = a : ba b

e ponendo a=bb

a


Keplero [1571-1630] osservò che

da cui si può dimostrare che la soluzione in forma chiusa della sequenza di Fibonacci, nota come formula di Binet [1786-1856], è:

Un approccio numerico

n

n

n F

F 1

lim


Algoritmo fibonacci1


• Molto efficiente: una sola linea di codice mandata in esecuzione (sebbene stiamo trascurando la complessità dell’operazione in essa contenuta)!

• Ma siamo sicuri che sia corretto? Sulla RAM (modello astratto) con celle di memoria infinite sì, ma su un modello di calcolo reale, con quale accuratezza devo fissare e per ottenere un risultato corretto?

• Ad esempio, con 3 cifre decimali:

Correttezza ed efficienza

ˆ

n fibonacci1(n) arrotondamento Fn

3 1.99992 2 2

16 986.698 987 987

18 2583.1 2583 2584



algoritmo fibonacci2(intero n) intero if (n ≤ 2) then return 1 else return fibonacci2(n-1) + fibonacci2(n-2)

Poiché fibonacci1 non è corretto, un approccio alternativo consiste nell’utilizzare direttamente la definizione ricorsiva:


• Per valutare il tempo di esecuzione, calcoliamo il numero di linee di codice T(n) mandate in esecuzione

• Se n≤2: una sola linea di codice• Se n=3: quattro linee di codice, due per la

chiamata fibonacci2(3), una per la chiamata fibonacci2(2) e una per la chiamata fibonacci2(1), cioè

T(3)=2+T(2)+T(1)=2+1+1=4

Correttezza? Corretto per definizione!

Efficienza?


Relazione di ricorrenza

Per n ≥3, in ogni chiamata si eseguono due linee di codice, oltre a quelle eseguite nelle chiamate ricorsive

T(n) = 2 + T(n-1) + T(n-2) n ≥ 3

In generale, il tempo di esecuzione di un algoritmo ricorsivo è pari al tempo speso all’interno della chiamata più il tempo speso nelle chiamate ricorsive


Albero della ricorsione di fibonacci2

• Utile per risolvere la relazione di ricorrenza T(n)• Ogni nodo corrisponde ad una chiamata ricorsiva• I figli di un nodo corrispondono alle sottochiamate


Alberi: qualche definizione

d=2 albero binario

albero d-ario: albero in cui tutti i nodi interni hanno (al più) d figli

Un albero è strettamente binario se tutti nodi interni hanno esattamente 2 figli


• Etichettando i nodi dell’albero con il numero di linee di codice eseguite nella chiamata corrispondente:– I nodi interni hanno etichetta 2– Le foglie hanno etichetta 1

Calcolare T(n)

• Per calcolare T(n):– Contiamo il numero di foglie– Contiamo il numero di nodi interni


Calcolare T(n)

In totale le linee di codice eseguite sono

T(n) = Fn + 2 (Fn-1) = 3Fn-2

Lemma 1:Il numero di foglie dell’albero della ricorsione di fibonacci2(n) è pari a Fn

dim (da fare a casa, per induzione su n)

Lemma 2:Il numero di nodi interni di un albero strettamente binario (come l’albero della ricorsione di fibonacci2(n)) è pari al numero di foglie -1dim (da fare a casa, per induzione sul numero di nodi interni dell’albero)


fibonacci2 è un algoritmo lento, perché esegue un numero di linee di codice esponenziale in n:

T(n) ≈ Fn ≈ n

Osservazioni

n = 8

Alcuni esempi di linee di codice eseguite

T(n)=3 · F8 – 2= 3 · 21 – 2 = 61n = 45 T(n) =3·F45 – 2 = 3·1.134.903.170 – 2 = 3.404.709.508

n = 100… con le attuali tecnologie, calcolare F100 richiederebbe circa 8000 anni!

Possiamo fare di meglio?


• Perché l’algoritmo fibonacci2 è lento? Perché continua a ricalcolare ripetutamente la soluzione dello stesso sottoproblema. Perché non memorizzare allora in un array le soluzioni dei sottoproblemi?


algoritmo fibonacci3(intero n) intero sia Fib un array di n interi Fib[1] Fib[2] 1 for i = 3 to n do Fib[i] Fib[i-1] + Fib[i-2] return Fib[n]



• Il vettore o array è una struttura dati utilizzata per rappresentare sequenze di elementi omogenei

• Un vettore è visualizzabile tramite una struttura unidimensionale di celle; ad esempio, un vettore di 5 interi ha la seguente forma

• Ciascuna delle celle dell'array è identificata da un valore di indice

• Gli array sono (generalmente) allocati in celle contigue della memoria del computer

La struttura dati vettore o array

5 23 1 12 5


• Linee 1, 2, e 5 eseguite una sola volta• Linea 3 eseguita n – 1 volte (una sola volta per n=1,2)• Linea 4 eseguita n – 2 volte (non eseguita per n=1,2)• T(n): numero di linee di codice mandate in

esecuzione da fibonacci3

Calcolo del tempo di esecuzione

T(n) = n – 1 + n – 2 + 3 = 2n n > 1

T(1) = 4

T(45) = 90Per n=45, circa 38 milioni di volte più veloce

dell’algoritmo fibonacci2!

T(100) = 200


• L’algoritmo fibonacci3 impiega tempo proporzionale a n invece che esponenziale in n, come accadeva invece per fibonacci2

• Tempo effettivo richiesto da implementazioni in C dei due algoritmi su piattaforme diverse (un po’ obsolete ):

Calcolo del tempo di esecuzione

Copyright © 2004 - The McGraw - Hill Companies, srl

• Il tempo di esecuzione non è la sola risorsa di calcolo che ci interessa. Anche la quantità di memoria necessaria può essere cruciale.

• Se abbiamo un algoritmo lento, dovremo solo attendere più a lungo per ottenere il risultato

• Ma se un algoritmo richiede più spazio di quello a disposizione, non otterremo mai la soluzione, indipendentemente da quanto attendiamo!

• È il caso di Fibonacci3, la cui correttezza è subordinata alla dimensione della memoria allocabile

Occupazione di memoria


• fibonacci3 usa un array di dimensione n prefissata• In realtà non ci serve mantenere tutti i valori di Fn

precedenti, ma solo gli ultimi due, riducendo lo spazio a poche variabili in tutto:


algoritmo fibonacci4(intero n) intero a b 1 for i = 3 to n do c a+b a b b c return b


• Per la risorsa tempo, calcoliamo il numero di linee di codice T(n) mandate in esecuzione – Se n≤2: tre sole linee di codice– Se n3: T(n) = 2+(n-1)+3·(n-2) = 4n-5 (per Fibonacci3 avevamo T(n)=2n)

• Per la risorsa spazio, contiamo il numero di variabili di lavoro utilizzate: S(n)=4 (per Fibonacci3 avevamo S(n)=n+1) [NOTA: stiamo assumendo che ogni locazione di memoria può contenere un valore infinitamente grande!]


Efficienza?


• Misurare T(n) come il numero di linee di codice mandate in esecuzione è una misura molto approssimativa del tempo di esecuzione

• Se andiamo a capo più spesso, aumenteranno le linee di codice sorgente, ma certo non il tempo richiesto dall’esecuzione del programma!

Notazione asintotica


• Per lo stesso programma impaginato diversamente potremmo concludere ad esempio che T(n)=3n oppure T(n)=5n

• Vorremmo un modo per descrivere l’ordine di grandezza di T(n) ignorando dettagli "inessenziali" come le costanti moltiplicative, additive e sottrattive

• Useremo a questo scopo la notazione asintotica Θ, simile alla notazione O che abbiamo già visto

Notazione asintotica


Supponiamo che f e g siano due funzioni definitivamente diverse da zero per n∞, e che

Allora, scriveremo che f(n) = Q(g(n)).

Notazione asintotica Q (definizione informale)

LLng

nfn

0,)(

)(lim


Esempi:

Sia f(n) = 2n2 + 3n, allora f(n)=Θ(n2)

Sia f(n) = n2 – n log n, allora f(n)=Θ(n2)

Sia f(n) = n3 -2n2+3n, allora f(n)=Θ(n3)

Sia f(n) = 23, allora f(n)=Θ(1)

Sia f(n) = 3n +2n, allora f(n)=Θ(3n)


• Fibonacci2 T(n)=3Fn-2 T(n)=Θ(Fn) T(n)=Θ(n), poiché

• Fibonacci3 T(n)=2n T(n)=Θ(n), S(n)=Θ(n)• Fibonacci4 T(n)=4n-5 T(n)=Θ(n), S(n)=Θ(1)

Andamento asintotico per i Fibonacci

5

151

lim

n

nn

n

Didattica e Fondamenti degli Algoritmi e della Calcolabilità Quarta giornata Risolvere...

Documents

Transcript of Didattica e Fondamenti degli Algoritmi e della Calcolabilità Quarta giornata Risolvere...