Riassunto degli argomenti di teoria

Ricorsione:

 Diretta:

La procedura richiama se stessa

 Indiretta:

La procedura viene richiamata attraverso la chiamata di un'altra procedura

Induzione matematica:

Sia P una proposizione, supponiamo che:

  k = 1

P k

1. è vera per (Base) n

2. è vera per un generico valore di (Ipotesi)

P       k

P n P n + 1 P k

Se a partire da riusciamo a dimostrare che anche è vera allora è vera per ogni

Divide-Et-Impera:

Affonda le sue radici nel principio di induzione matematica:

 Metodo:

1. Divide: Suddividere un problema P in sottoproblemi fino a quando il sottoproblema è

risolubile facilmente

2. Impera: Si ritiene per ipotesi di saper risolvere ciascun sottoproblema

3. Combina: Si ricombinano le ipotesi delle sottosoluzioni per ottenere la soluzione

principale

Classificazione degli algoritmi ricorsivi:

1. Ricorsione lineare: Se c'è una sola chiamata a se stesso

2. Ricorsione in coda: Se la chiamata ricorsiva è alla fine della funzione (la chiamata è eseguita

come ultima istruzione)

3. Ricorsione multipla: Se ci sono più chiamate a se stesso

4. Ricorsione mutua: Una prima funzione chiama una seconda funzione che a sua volta

richiama la prima

5. Ricorsione innestata: Se ha come argomento una chiamata a se stessa

 Svantaggi:

1. In alcuni casi la ricorsione risulta essere meno efficiente di una procedura iterativa

2. Le chiamate ricorsive possono riempire lo stack frame

3. Lo spazio di stack frame è minore di quello di heap

4. Spreco di memoria per la memorizzazione di tutte le variabili locali

 Vantaggi:

1. La scrittura di codice ricorsivo è più semplice ed elegante

2. Spesso alcuni problemi possono essere risolti solo attraverso procedure ricorsive e

quindi la soluzione ricorsiva risulta essere naturale

Complessità computazionale:

 Notazione asintotica:   



O g n

1. Limite asintotico superiore :

  

        

    

O g n = f n | c, n ;

0 f n c g n , n > n

0 0

  

   

        

Ω Ω     

g n

2. Limite inferiore asintotico : g n = f n | c, n ;

0 c g n f n , n > n

0 0

  



Θ g n

3. Limite asintotico stretto :

  

          

Θ       

g n = f n | c , c , n ;

0 c g n f n c g n , n > n

1 2 0 1 2 0

 Proprietà delle notazioni: Θ Ω

NOTA: Le proprietà sono scritte in termini di ma valgono ugualmente sia in termini di che in

O

termini di .       



Θ

  

k, f n , k f n = f n

1. Fattore costante:

    

     

     



Θ Θ Θ



f n = g n , g n = h n f n = h n

2. Transitività:

  

   

      





Θ Θ Θ

f n + g n = max f n , g n

3. Somma:   

   

     



Θ Θ Θ

 

f n g n = f n g n

4. Prodotto:

 Complessità di funzioni ricorsive:

1. Divisione della struttura dati in due parti, invocazione ricorsiva su una sola delle due

parti e tempo di combinazione e divisione costante:

c se n = 1

 1



     

 

T n = T n = c + c log n

n

   1 2 2

T + c se n > 1

 

 2

2

 



2. Divisione della struttura dati in due parti, invocazione ricorsiva su entrambe le parti e

tempo di combinazione e divisione costante:

c se n = 1

 1



     

  

T n = T n = n c + n 1 c

n

   1 2



2 T + c se n > 1

 

 2

2

 



3. Divisione della struttura dati in due parti, invocazione ricorsiva una sola delle due parti e

tempo di combinazione e divisione lineare:

c se n = 1

 1



   

 

T n = T n = c + 2n c

n

   1 2



T + n c se n > 1

 

 2

2

 



4. Divisione della struttura dati in due parti, invocazione ricorsiva su entrambe le parti e

tempo di combinazione e divisione lineare:

c se n = 1

 1



     

   

T n = T n = n c + n log n c

n

   1 2 2

 

2 T + n c se n > 1

 

 2

2

 



5. Divisione della struttura dati in due parti, una di dimensione 1 ed una di dimensione n-1,

effettuata con un'unica ricorsione e tempo di combinazione e divisione costanti:

c se n = 1



     

1   

T n = T n = c + n 1 c

   1 2



T n 1 + c se n > 1

 2

Algoritmi di ricerca:  

Θ

T = 1

 b

 n n

  

       

 Lineare: Θ Θ Θ Θ Θ



T = 1 + 1 = + 1 = n

 

 a 2 2

 

  

 Θ

T = n

 w  

Θ

T = 1

 b

         



Θ Θ Θ

 

Dicotomica: , la ricerca dicotomica necessita di un

T = log n 1 + 1 = log n

 a 2 2

   



Θ

T = log n

 w 2

array già ordinato. n

n = 1

n = 1 numero di elementi da esaminare, numero totale di elementi. , quindi

n =

i i i

2

i

all'aumentare di diminuisce n cioè, diminuisce il numero di elementi da

i  

i

i 

 

esaminare, . Se 2 = n i = log n , quindi, il numero di iterazioni

n = 0 2 > n 2

i  

i log n

compiute vale .

2

Algoritmi di ordinamento:

 Tipologie:

1. Ordinamento interno: se la struttura dati è interamente contenuta nella memoria centrale

2. Ordinamento esterno: se le struttura dati è contenuta, almeno in parte, in un file

3. Ordinamento sul posto: sfrutta la struttura dati iniziale

4. Ordinamento non sul posto: sfrutta strutture dati di appoggio

5. Ordinamento stabile: si aggiunge il vincolo che nella struttura dati finale gli elementi

equ