Didattica e Fondamenti degli Algoritmi e della Calcolabilità

(1)

Didattica e Fondamenti degli Algoritmi e della

Calcolabilità

Quarta giornata

Risolvere efficientemente un problema in P: la sequenza di Fibonacci

Guido Proietti

Email: guido.proietti@univaq.it

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

(2)

Riepilogo: gerarchia delle classi

2

Decidibili

ExpTime

(ARRESTO(k)) P (ricerca)

NP NP-completi (SAT)

Congettura P ≠ NP

(3)

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

(4)

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

(5)

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”

(6)

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

(7)

Un problema numerico «giocattolo»:

i numeri di Fibonacci

(8)

8

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?

(9)

• 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

(10)

10

L’albero dei conigli

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

(11)

• 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 F_n il numero di coppie all’inizio dell’anno n, abbiamo la seguente relazione di ricorrenza:

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

(12)

12

Il problema

Come calcoliamo F

_n

?

Primi numeri della sequenza di Fibonacci:

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

(13)

Digressione: la sezione aurea

Rapporto  fra due grandezze disuguali a>b, in cui a è medio proporzionale tra b e a+b

(a+b) : a = a : b

a b

e ponendo a=b ^b

a

(14)

14

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 ¹

lim

(15)

Algoritmo fibonacci1

(16)

16

• 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 F_n

3 1.99992 2 2

16 986.698 987 987

18 2583.1 2583 2584

(17)

Algoritmo fibonacci2

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:

(18)

18

• 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?

(19)

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

(20)

20

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

(21)

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

(22)

22

• 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

(23)

Calcolare T(n)

In totale le linee di codice eseguite sono

Lemma 1:

Il numero di foglie dell’albero della ricorsione di fibonacci2(n) è pari a F_n

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 -1

dim

(da fare a casa, per induzione sul numero di nodi interni dell’albero)

(24)

24

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

T(n) ≈ F

_n

≈ 

ⁿ

Osservazioni

n = 8

Alcuni esempi di linee di codice eseguite T(n)=3 · F₈ – 2= 3 · 21 – 2 = 61

n = 45 T(n) =3·F₄₅ – 2 = 3·1.134.903.170 – 2 = 3.404.709.508 n = 100… con le attuali tecnologie, calcolare F₁₀₀ richiederebbe circa 8000 anni!

Possiamo fare di meglio?

(25)

• 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

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]

Correttezza? !

(26)

26

• 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

(27)

• 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) = 90 Per n=45, circa 38 milioni di volte più veloce dell’algoritmo fibonacci2!

T(100) = 200

(28)

28

• 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

(29)

• 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

(30)

• fibonacci3 usa un array di dimensione n prefissata

• In realtà non ci serve mantenere tutti i valori di F_n

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

Algoritmo fibonacci4

algoritmo fibonacci4(intero n)  intero a  b  1

for i = 3 to n do c  a+b

a  b b  c return b

(31)

• 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 n3: 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!]

Correttezza?

Corretto per definizione!

Efficienza?

(32)

• 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

(33)

• 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

(34)

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)





 

 L L

n g

n f

n , 0

) (

) lim (

(35)

Esempi:

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

Sia f(n) = n² – n log n, allora f(n)=Θ(n²) Sia f(n) = n³ -2n²+3n, allora f(n)=Θ(n³) Sia f(n) = 23, allora f(n)=Θ(1)

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

(36)

• Fibonacci2 T(n)=3F_n-2  T(n)=Θ(F_n)  T(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

 

1 5

lim ^







n

n n

n 



 ^