Parte 9
Elementi di Informatica di base
Dott.ssa Elisa Tiezzi
1
Programmi ricorsivi
Secondo lo stile ricorsivo un programma
risolve un problema facendo ricorso a chiamate
dello stesso programma che risolvono un
problema sui dati originali opportunatamente
ridotti. I risultati ottenuti con le singole
chiamate vengono poi combinati per ottenere il
risultato finale.
2
E’ responsabilità di chi formula l’algoritmo
porvi in posizione opportuna la clausola di
chiusura per assicurarsi che le chiamate
successive della procedura abbiano termine.
E’ responsabilità del sistema di elaborazione
organizzare i calcoli richiesti dalla procedura
che devono essere eseguiti aggregando man
mano dati elementari.
3
Ogni parametro di una procedura ricorsiva
può assumere allo stesso tempo valori
indipendenti. Il valore impiegato in
un’esecuzione muore con il completamento
di questa ed è sostituito dal valore relativo
all’ultima esecuzione lasciato in sospeso.
Tali assegnazioni come i problemi lasciati in
sospeso sono i problemi dell’elaboratore.
4
Il programmatore formula l’algoritmo dal
generale al particolare descrivendo la funzione
sulla globalità dei dati in termini della funzione
stessa sui dati disgregati.
L’algoritmo viene poi eseguito dal particolare
al generale. Vengono infatti lasciate in sospeso
le operazioni globali e il calcolo vero e proprio
inizia dai dati atomici.
5
Possiamo pensare alle operazioni effettuate
prima e dopo le chiamate ricorsive come ad un
LAVORO DI COMBINAZIONE dei risultati
parziali in cui si fa confluire l’eventuale lavoro
di preparazione dei dati per le chiamate ricorsive
stesse.
6
RELAZIONI DI RICORRENZA
Quando un algoritmo è scritto in maniera
ricorsiva può risultare relativamente facile
caratterizzare in modo compatto e semplice le
funzioni di complessità. Le relazioni di
ricorrenza nascono infatti quando un elemento
generico di una sequenza può essere espresso
in funzione dei termini precedenti.
Si usa classificare le più importanti relazioni di
ricorrenza anche in base alla forma del lavoro
di combinazione.
7
Fibonacci
Una delle prime relazioni di ricorrenza fu posta da
Fibonacci .
Problema dei conigli:
Al tempo 1, origine dei tempi, c’è una coppiua di
conigli neonati. Al tempo successivo la coppia
diventata adulta, inizia il processo di
riproduzione: ogni coppia genera una nuova
coppia ogni mese, ma ogni nuova coppia non è in
grado di procreare durante il primo mese.
Quante coppie vi sono al mese n?
Il numero cercato è l’n-esimo numero di
8
Fibonacci.
F1=1 al mese 1 c’è solo una coppia
F2=1 al mese 2 ancora la prima coppia non può procreare
Condizioni
iniziali
F3=2 la prima coppia procrea una seconda
•
•
Fn=Fn-1+Fn-2
Relazione di ricorrenza
al mese n vi sono le coppie del mese precedente, Fn-1, più quelle generate
nell’ultimo mese che sono quelle esistenti nel mese ancora precedente, Fn-2.
9
Cerchiamo di esprimere Fn in funzione di n,
cercando quindi una soluzione per la
relazione di ricorrenza.
La legge generale conterrà delle costanti da
determinare imponendo delle condizioni
iniziali.
Ipotizziamo che ci sia una soluzione del tipo
Fn=czn
dove c e z sono costanti.
10
Sostituiamo in Fn=Fn-1+Fn-2 la soluzione
ipotizzata.
cz  cz
n 1
 cz
n2
cz  cz
n 1
 cz
n2
n
n
0
n 1
cz
cz
cz ( n  2  n 2  1)  0
cz
cz
n 2
n  n 2
n 1n  2
cz (z
z
 1)  0
n
n 2
cz
n 2
(z  z  1)  0
2
11
Possiamo quindi affermare che czn è una
soluzione della relazione di ricorrenza in uno
dei seguenti tre casi:
c0
banale, si avrebbe Fn  0
z0
1 5
z  z 1  0  z1,2 
2
2
12
Quindi Fn ammette le due soluzioni
Fn=c1z1n
Fn=c2z2n
Purtroppo non generano tutti i numeri di
Fibonacci al variare di n dato che nessuna
delle due è in grado di soddisfare le due
condizioni iniziali.
In virtù della linearità di Fn=Fn-1+Fn-2 una
combinazione lineare delle due soluzioni è
ancora una soluzione della relazione.
In particolare consideriamo:
Fn= c1z1n +c2z2n
13
Imponendo le condizioni iniziali:
1
1
c1 (1  5)  c2 (1_ 5)  1
2
2
1
1
2
c1 (1  5)  c2 (1_ 5)2  1
4
4
Si ottiene dopo facili calcoli :
1
c1 
5
1
c2  
5
14
Si ottiene quindi:
1 1  5 
1 1  5 
Fn 

 


5  2 
5  2 
n
n
E' prevalente dato
che z >1 mentre z 1
1
2
detta formula di Binet
15
Si ha quindi :
1 1  5 1 1  5
F1 



 
5  2  5  2 
1

1  5  1  5  1
2 5
2
2
1 1  5
1 1  5
F2 

 

 
5  2 
5  2 
1

1  5  2 5  1  5  2 5  1
4 5
16
RELAZIONI DI RICORRENZA CON LAVORO di
COMBINAZIONE COSTANTE E COEFFICIENTI
COSTANTI
Quelle relazioni in cui il lavoro di combinazione é
indipendente dalla dimensione dei dati :
a) Relazioni lineari di ordine hcioé del tipo
C(1)  c1
C(h)  ch
C(n) = a1C(n  1)   ahC(n  h)  b
con n intero, n  h, h  1 e almeno 2 degli ai  1
17
b)Relazioni lineari di ordine h
( con a h = 1 e a j = 0 j con 1  j  h - 1)
C(1)  c1
C(h)  ch
C(n) = C(n  h)  b
c) Relazioni con partizioni di dati
C(1)  c
 
C(n) = aC n p  b
con n  p e m intero, n  1
m
18
RELAZIONI DI RICORRENZA CON LAVORO di
COMBINAZIONE LINEARE E COEFFICIENTI
COSTANTI
Quelle relazioni in cui il lavoro di combinazione é
dipendente dalla dimensione dei dati :
d) Relazioni lineari di ordine h
C(1)  c1
C(h)  ch
C(n) = C(n  h)  bn + d
con n intero, n  h, h  1
19
e) Relazioni con partizioni di dati
C(1)  d
 
C(n) = aC n b  c1n  c2
k
con n  b e k intero, n  1
20
a)
b)
c)
Soluzioni
C(n) O(k )
C(n) O(n)
C(n) O(log n) se a = 1
n
C(n) O(n
d)
e)
log a
p
) se a  1
C(n) O(n )
C(n) O(n) se a  p
C(n) O(nlog n) se a  p
2
C(n) O(nn
log a
p
) se a  p
21
Esempio: PRIMSEC algoritmo ricorsivo che
determina il primo e il secondo elemento di un
insieme secondo un ordine assegnato.
Sia A un vettore di n elementi distinti con un
ordine prefissato.
Si divide in due metà il vettore e si applica
ricorsivamente l’algoritmo fino a che non si
arriva a due coppie alle quali si applica il
confronto.
22
Sotto l’ipotesi che n=2h i due insiemi iniziali si
dividovo esattamente in due ad ogni passo
finché dopo h-1 suddivisioni si ottengono
insiemi elementari di due elementi.
Valutiamo il numero di confronti eseguiti per
calcolare la funzione di complessità.
Avremo che:
C(n)=1 per n=2
C(n)=2C(n/2)+2 per n>2
Questo modo di impostare l’algoritmo si chiama
DIVIDE ET IMPERA (prossima lezione)
23
Non abbiamo il numero esatto dei confronti
ma abbiamo l’ordine di grandezza della
nostra funzione di complessità che essendo
nel caso c) con a>1 risulta essere
C(n) O(n
log 2
2
) = O(n)
24
Soluzione di c) per sostituzioni successive
 
 n  
n
C(n)  aC p  b  a aC 2   b  b 
  p  
  n   
 aa aC p 3  b  b b 
  
  
   n  
 aa  aC p m   b 
 
   
 a m c  ba m1  a m 2 
 
 b  b 
 
 1
25
Quindi abbiamo
C(n)  a c  ba
m
m1
a
m 2

 1
Se a  1
C(n) = c + b(1+
+ 1)
m volte
Dato che n  p si ha che logp n = m per cui
m
C(n) = c + blogp n O(log n)
26
Osservazione :
Se n  p  n1 e n2 t.c. n1  n  n2 e n1  p e n2  p
m
m
m 1
Dato che C(n) é crescente in n si ha che
C(n) O(logp n2 ).
Ma n2  n1  p da cui
logp n2  logp pn1  logp pn  1  logp n
Quindi C(n) O(log p n  1)
27
Se a > 1
Partiamo sempre da C(n)  a c  ba
m
m 1
a
m 2

 1
a 1
Osserviamo che i= 0a 
a 1
Dato che m  logp n  logp a  loga n si ha che
m-1
m
i
m

a  1
m
C(n) = a c  b
 
 a  1 
log alog n 
b  b
p
a
a
c 


 a  1 a  1
log p a 
log p a
b  b
n
c 

O n
 a  1 a  1
 
28
Osservazione :
Se n  p  n1 e n2 t.c. n1  n  n2 e n1  p e n2  p
m
m
m 1
Dato che C(n) é crescente con n si ha che :
C(n1 )  C(n)  C(n2 )
log a
per cui C(n) < n2
p
con n2  n1  p
log a
Di conseguenza C(n) < n2
p
 (n1 p)
log p a
 n1
log p a
an
log p a
a
29
Abbiamo quindi dimostrato che n
Se a  1 C(n) O(log n 1)
p
Se a  1 C(n) O(n
log a
p
1) dove :
Se a<p la funzione di complessità è
SOTTOLINEARE.
Ciò avviene per quei problemi ove è possibile
scartare (ricorsivamente ad ogni passo) alcuni
dati sui quali non si dovrà mai operare. Es: se
a=2 e b=3 sarà sufficiente considerare solo 2
sottoinsiemi contenenti ciascuno un terzo dei dati
e non considerare mai il rimanente terzo. Ciò
vuol dire ridurre i dati ad ogni chiamata
30
Se a=p la funzione di complessità è LINEARE.
Ed infine se a>p la funzione è SOPRALINEARE
anche se non cresce in genere come un
polinomio di grado elevato a causa della
funzione logaritmica che appare all’esponente.
Ciò avviene quando si deve operare più volte
sugli stessi dati. Es: se a=3 e b=2 si avrà bisogno
di tre chiamate su sottoinsiemi di n/2 dati e cioè
sovrapposizione.
31