Riassunto esame Analysis of algorithms and data structures, Prof. Merlini Stefano, libro consigliato The art of computer programming , D.E knuth

Sequenza di Fibonacci: −1 −2 0 1

Consideriamo la S.d.F. shiftata di 2 posizioni:

→

= + ricorrenza lineare a coefficienti costanti

+2 +1

Applico a entrambi i membri la funzione generatrice:

( )− − * ( )− 2

0 1 0

( ) = ( ) + ( ) → = + ( ) →... → (1 − − ) * ( )

2

+2 +1

→

→ ( ) = in generale se ho una ricorrenza lineare a coefficienti costanti

2

1−−

la funzione generatrice è una razionale fratta.

Es.:

= + + → ( ) → = + +

+3 +2 +1 +3 +2 +1

2

( )− − *− * ( )− − * ( )−

0 1 2 0 1 0

= + + ( ) →

3 2

2 2 3

( ) − − = * (( ) − ) + * ( ) + * ( ) →

Es.: 1 →

= calcolo il rapporto dell’elemento i+1-esimo con l’elemento i-esimo:

!

! 1 →

+1 = = → ( + 1) * = non è una ricorrenza lineare a

(+1)! (+1) +1

coefficienti costanti! →

(( + 1) * ) = ( ) sia spostamento perché la sequenza è a sia

n+1

+1

derivazione perché ho un coefficiente che dipende da n e non è = 1.

= ( + 1) * → = * , = 0

+1 +1 0

( )− (* ) *(( )) →

0

= = () = = (( )) porto tutto a sinistra dell’=

+

'() '()

= 1→∫ = ∫ 1 → (()) = + → () = il che implica

() ()

() =

che c = 0, e quindi

Es.: 1 →

= = 0 rapporto tra due termini consecutivi:

0

→

+1 = → ( + 1) * = * ma questo non è vero, perché il principio

+1

di identità vale solo nel caso in cui la regola sia valida per tutti gli n. Qui per n=0 non

= 0 = 1

si ha la proprietà verificata, in quanto: , ma chiaramente quindi non

1 1

posso usarla così semplicemente.

→

( + 1) * = * + δ questa vale per ogni n. La funzione applicata vale 0

,0

per tutti gli n tranne che per k = n, in cui vale 1. Quindi ora risulta correttamente

= 1

.

1 1

(( + 1) * ) = ( * ) + (δ ) → (( )) = * (( )) + 1 → (( )) = 1−

,0

1 1

→ '() = ⇒∫ = − (1 − ) + imposta usando il fatto che

1− 1−

= 0

, quindi:

0 −1 1

() = − (1 − ) + = (1 − ) + = ( )

con c=0

1−

necessariamente, perché se 1

= 0 = 0 ⇒ ( ) = 0

allora .

1−

0

Es.: 1

= ∑

=1

Per questa dobbiamo adattare la quarta proprietà (convoluzione) e usarla in questo

modo (formula di Eulero):

1

( ∑ ) → = 1 → ( ∑ * 1) = (1) * ( ) = * ( )

1−

−

=0 =0

{ }

1 1

= ∑ = ∑ = 0 = 0, > 0

con

=1 =0

Quindi si ha che:

1 1 1

= ∑ → ( ) = * ( )

1− 1−

=1 = (0, 1, 1, 2, 3, 5, 8, 13, 21,...)

Consideriamo ora la sequenza di Fibonacci e

supponiamo che vogliamo considerare solo i termini di indice pari:

= (0, 1, 3, 8, 21,...) allora questa è ottenuta tramite una trasformazione

particolare della funzione generatrice:

( )+(− ) ( )−(− )

( ) = ( ) =

2

2 2+1 2*

Nel caso di Fibonacci si ha: ( )

( )

− 1 +− − ++ 1 2

= + * = * = =

2 2 2

2 2

1−− 1−+ (1−) − 2(1−2+ −) 1−3+

28/10/2019 QS: confronti e scambi

Riprendiamo ora il caso medio del quicksort, cercando di risolvere le due ricorrenze di

C e S con l’operatore funzione generatrice.

n n

- Confronti. +1 −1

2

= + 1 + ∑ → → = ( + 1) + 2 ∑

=0 =0

( ) = ()

Applico quindi la funzione geratrice a entrambi i termini, considerando

: ( )

−1

( ) = (( + 1)) + 2 ∑

=0

notando in particolare che, per spostamenti negativi invece che dividere per t, io

( ) = ( )

moltiplico per t: . Si ha quindi:

−

2 2

'() = ( ) + () + 2( ∑ ) → ( ) () →

=0

2 2 2

+ 1 + +− 2

'() = + + 2 () = + () = '() → →

3 2 3

1− 1−

(1−) (1−) (1−)

2

'() = +

3

(1−)

Equazione differenziale del primo ordine:

Primo passo: studiare l’eq. differenziale senza il termine noto, soluzione particolare

dell’equazione omogenea associata. ( )

2 ς'() 2 1

ς'() = ς() → = → (ς()) = − 2(1 − ) → (ς()) = →

2

1− ς() 1− (1−)

1

ς() = 2

(1−) () ς()

Secondo passo: studiare la derivata del rapporto tra e .

'

( ) 2 2

() '()ς()−ς'()() 1 ς'() 2

⎡ ⎤ ⎡ ⎤

= = '() − () = (1 − ) '() − () = (1 − )

⎣ ⎦ ⎣ ⎦

2

ς() ς() ς() 1−

ς() (1

Si ha quindi:

'

( )

() 2 ()

= = − 2(1 − ) +

e

ς() 1− ς()

( )

1 1 2 1 1 1 1

() = 2 + = =2

2 2

1− 1− 1− 1− 1−

(1−) (1−) 1 1

( ) =

Dove riconosco chiaramente 1− 1−

( )

1 1 1

() = 2 = 2 * () * ( ) = 2 ∑ → () = 2 ∑ = 2( + 1)(

1− 1− 1−

=0 =0

Moltiplico tutto per n:

−1

(−2)

= + 2 ∑ nel caso in cui n=0 si ha 0=0, nel caso in cui n=1 si ha

6

=0

1

0= − 6 −1

6 = ( − 2) + 12 ∑

=0

Problema! Dobbiamo aggiungere un termine che vale 1 solo nel caso in cui n=1, in

modo da risolvere il mio problema.

−1

6 = ( − 2) + 12 ∑ + δ

+1

=0

Applico quindi ora l’operatore funzione generatrice:

( )

−1 2

2 +

6( ) = ( ) − 2() + 12 ∑ + (δ ) = 6'() = −2 + 12

3 2 1−

+1 (1−) (1−)

=0

2 2 3 3

+ −2+2 +(1−) () (3−) ()

= + 12 = + 12

3 3

1− 1−)

(1−) (1−)

Divido da entrambi i lati per t:

2

(3−) ()

'() = +2

3 1−

6(1−)

Di nuovo, primo passaggio studiare l’equazione differenziale omogenea associata

senza il termine noto:

2 ς'() 2 1

ς'() = ς() → = → (ς()) = − 2(1 − ) → ς() = 2

1− ς() 1− (1−)

() ς()

Secondo passaggio, studio la derivata del rapporto tra e :

' 2

( ) 2 2

() '()ς()−()ς'() 1 ς'() 2 (1

⎡ ⎤ ⎡ ⎤

= = '() − () = (1 − ) '() − () = (1 − )

⎣ ⎦ ⎣ ⎦

2

ς() ς() ς() 1−

ς() 6(1

Si ha quindi:

' 2 2

( ) 2

() (1−3) (1−3)

= → (1 − ) () = ∫

ς() 6(1−) 6(1−)

Semplifico il polinomio nell’integrale in modo che sia semplice integrare:

2 2 3 2 3

(1−3) −3 (1−) 2

= = − → (1 − ) 2 →

6(1−) 6(1−) 6(1−) 6(1−)

2 3 2 2

(−1)(+1)+

= − → → − = +

6 3(1−