Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl1

Capitolo 1Un’introduzione informale

agli algoritmi

Algoritmi e Strutture Dati

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl2

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

Dim: Per induzione su n:

– Caso base n=1: in questo caso l’albero della ricorsione è costituito da un unico nodo, che è quindi anche una foglia; poiché F1=1, il lemma segue.

– Caso n>1: supposto vero fino ad n-1, dimostriamolo vero per n; osserviamo che l’albero della ricorsione associato ad n è formato da una radice etichettata F(n) e da due sottoalberi etichettati F(n-1) e F(n-2). Per l’ipotesi induttiva, tali sottoalberi hanno rispettivamente Fn-1 ed Fn-2 foglie, e quindi l’albero della ricorsione associato ad n avrà Fn-1 + Fn-2 = Fn foglie, come volevasi dimostrare. □

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl3

Approfondimento: Dimostrazione del Lemma 2Lemma 2: Il numero di nodi interni di un albero in cui ogni nodo interno ha esattamente due figli è pari al numero di foglie -1

Dim: Per induzione sul numero di nodi interni, sia detto k:

– Caso base k=1: se c’è un solo nodo interno, poiché per ipotesi deve avere due figli, tali figli saranno foglie, e quindi il lemma segue.

– Caso k>1: supposto vero fino a k-1, dimostriamolo vero per k; osserviamo che poiché k>1, abbiamo due possibilità:

1. Uno dei due sottoalberi della radice è una foglia: in tal caso l’altro sottoalbero contiene k-1 nodi interni, e quindi per ipotesi induttiva avrà k foglie; allora, il numero totale di foglie è k+1, da cui segue il lemma;

2. Entrambi i sottoalberi contengono nodi interni, in numero totale di k-1=k1+k2; ma allora, per ipotesi induttiva, conterranno rispettivamente k1+1 e k2+1 foglie, e quindi il numero totale di foglie è k1+k2+2=k+1,

come volevasi dimostrare.

□

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl4

• Stiamo cercando di calcolare efficientemente l’n-esimo numero della sequenza di Fibonacci

• Abbiamo progettato 3 algoritmi:– fibonacci1, non corretto in quanto approssima la soluzione – Fibonacci2, che impiega tempo esponenziale in n– fibonacci3, che impiega tempo proporzionale ad n

Punto della situazione

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

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

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

• 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

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

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

• 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!)

Correttezza? Corretto per definizione!

Efficienza?

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

• 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

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

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

Notazione asintotica

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Supponiamo che

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

Notazione asintotica (definizione informale)

LLng

nfn

0,)(

)(lim

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Esempi:

Sia f(n) = 2n2 + 3n, 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)

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

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

• Fibonacci3 T(n)=2n T(n)=Θ(n)

• Fibonacci4 T(n)= 4n-6 T(n)=Θ(n)

Andamento asintotico per i Fibonacci

5

151

lim

n

nn

n

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Possiamo sperare di calcolare Fn in tempo inferiore a Θ(n)?

Un nuovo algoritmo

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

• fibonacci4 non è il miglior algoritmo possibile

• E’ possibile dimostrare per induzione la seguente proprietà di matrici:

Potenze ricorsive

1 11 0

n= Fn+1

Fn

Fn Fn-1

• Useremo questa proprietà per progettare un algoritmo più efficiente

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

…prodotto di matrici

nnn

n

aa

aa

A

,1,

,11,1

nnn

n

bb

bb

B

,1,

,11,1

(AB)i,j= ai,k bk,jk=1

n

i=1,…, n j=1,…, n

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Dimostrazione per induzione

Base induzione: n=2

1 11 0

2

= F3 F2

F2 F1

1 11 0

1 11 0

= 2 11 1

=

Fn+1 Fn

Fn Fn-1

Hp induttiva: 1 11 0

n-1

= Fn Fn-1

Fn-1 Fn-2

1 11 0

n

= Fn Fn-1

Fn-1 Fn-2

1 11 0

Fn + Fn-1

Fn-1+ Fn-2

= = Fn

Fn-1

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Algoritmo fibonacci5

• Osserva che il ciclo arriva fino ad n-1

• Il tempo di esecuzione è T(n)=2+2(n-1)=Θ(n)

• Possiamo migliorare?

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

• Possiamo calcolare la n-esima potenza elevando al quadrato la (

└n/2

┘)-esima potenza

• Se n è dispari eseguiamo una ulteriore moltiplicazione

• Esempio:

32=9 34 =(32)2= (9)2 =81 38=(34)2= (81)2 =6561

Calcolo di potenze

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Algoritmo fibonacci6

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

• Tutto il tempo è speso nella procedura potenzaDiMatrice– All’interno della procedura si spende tempo costante– Si esegue una chiamata ricorsiva con input n/2

• L’equazione di ricorrenza è pertanto:

Tempo di esecuzione

T(n) = Θ(1) + T(n/2)

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Metodo dell’iterazione

Si può dimostrare che

T(n) ≤ c log2 n + T(1) = Θ(log2 n )

Infatti: T(n)=T(n/2)+Θ(1)=[T(n/4)+Θ(1)]+Θ(1)=

=[{T(n/8)+Θ(1)}+Θ(1)] +Θ(1)=…

=((…(T(1)+Θ(1))+…+Θ(1))+Θ(1))+Θ(1)=Θ(log n)fibonacci6 è quindi esponenzialmente più

veloce di fibonacci5!

Camil Demetrescu, Irene Finocchi, Giuseppe F. ItalianoAlgoritmi e strutture dati

Copyright © 2004 - The McGraw - Hill Companies, srl

Riepilogo

fibonacci6

fibonacci5

fibonacci4

fibonacci3

fibonacci2

Θ(log n)

Θ(n)

Θ(n)

Θ(n)

Θ(n)

Θ(log n)

Θ(1)

Θ(1)

Θ(n)

Numero di linee di codice

Occupazione di memoria

fibonacci1 Θ(1)Θ(1)

Θ(n)