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:

1.   k = 1P k1. è vera per (Base) n
2. 2. è vera per un generico valore di (Ipotesi)P       kP 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 > n0 0
2. Limite inferiore asintotico:              Ω Ω     g n2. g n = f n | c, n ;0 c g n f n , n > n0 0
3. Limite asintotico stretto:   Θ g n3.             Θ       g n = f n | c , c , n ;0 c g n f n c g n , n > n1 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 .

1. Fattore costante:       Θ  k, f n , k f n = f n
2. Transitivà:               Θ Θ Θf n = g n , g n = h n f n = h n
3. Somma:            Θ Θ Θf n + g n = max f n , g n
4. Prodotto:           Θ Θ Θ f n g n = f n g n

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 nn   1 2 2T + c se n > 1  22 

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 cn   1 22 T + c se n > 1  22 

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 cn   1 2T + n c se n > 1  22 

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 cn   1 2 2 2 T + n c se n > 1  22 

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

Dicotomica:  ΘT = 1 b         Θ Θ Θ T = log n 1 + 1 = log n a 2 2   ΘT = log n w 2, la ricerca dicotomica necessita di un array già ordinato.

nn = 1n = 1 numero di elementi da esaminare, numero totale di elementi. , quindi n =i i i2i all'aumentare di diminuisce n cioè, diminuisce il numero di elementi dai  ii  esaminare, . Se 2 = n i = log n , quindi, il numero di iterazioni n = 0 2 > n 2i  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