Algoritmi e strutture dati

Fondamenti algoritmo

Informalmente, un algoritmo è una procedura di calcolo bene definita che prende un certo valore, o un input output; insieme di valori, come e genera un valore, o un insieme di valori, come un algoritmo è quindi una sequenza di passi computazionali che trasforma l'input in output.

Possiamo anche considerare un algoritmo come uno strumento per svolgere un problema computazionale ben definito; la definizione del problema specifica in termini generali la relazione di input/output desiderata.

L'istanza di un problema è formata dall'input, che soddisfa tutti i vincoli importi nella definizione del problema, richiesto per calcolare una soluzione del problema.

Un algoritmo si dice corretto se, per ogni istanza di input, termina con l'output corretto; diciamo che un algoritmo corretto risolve il problema computazionale dato. Un algoritmo errato potrebbe non terminare con qualche istanza di input o potrebbe terminare fornendo un risultato errato.

1. Notazione asintotica

Notazione o-grande

• F O(g) c n n > n f(n) < c g(n).

La funzione è in se e solo se esistono due numeri positivi e tali che per ogni, 0 0.

O(g) = f c, n > 0 tali che per ogni n > n si ha f(n) < c g(n) { | esistono } 0 0.

La notazione o-grande rappresenta un limite superiore per la funzione data.

Notazione omega-grande

• F (g) c n n > n f(n) > c g(n).

La funzione è in se e solo se esistono due numeri positivi e tali che per ogni, r 0 0.

(g) = f c, n > 0 tali che per ogni n > n si ha f(n) > c g(n) { | esistono } 0 0.

La notazione omega-grande rappresenta un limite inferiore per la funzione data.

Notazione theta-grande

• F O(g) c, c n n > n.

La funzione è in se e solo se esistono tre numeri positivi e tali che per ogni 1 2 0 0.

C g(n) < f < c g(n) 1 2.

O(g) = f | esistono c, c e n tali che per ogni n > n si ha c g(n) < f < c g(n) { } 1 2 0 0 1 2.

Si può dedurre che f è in O(g) se e solo se f è in O(g) e f è in r n.

2. Divide et impera

Nel metodo divide et impera un problema viene risolto in modo ricorsivo, applicando tre passi ad ogni livello di ricorsione:

• Divide: questo passo divide il problema in un certo numero di sottoproblemi, che sono istante più piccole dello stesso problema.
• Impera: i sottoproblemi vengono risolti in modo ricorsivo; quando i sottoproblemi hanno una dimensione sufficientemente piccola, essi vengono risolti direttamente.
• Combina: le soluzioni dei sottoproblemi vengono combinate per generare la soluzione del problema originale.

Una ricorrenza è un'equazione che descrive una funzione in termini del suo valore con input più piccoli.

Metodo di sostituzione

Il metodo di sostituzione per risolvere le ricorrenze richiede due passi:

• Ipotizzare la forma della soluzione.
• Usare l'induzione matematica per trovare le costanti e dimostrare che la soluzione funziona.

Il nome del metodo deriva dalla sostituzione della soluzione ipotizzata al posto della funzione quando l'ipotesi induttiva viene applicata a valori più piccoli.

Questo metodo è potente, ma ovviamente può essere applicato soltanto nei casi in cui sia facile immaginare la forma della soluzione.

Metodo dell'albero di ricorsione

Sebbene il metodo di sostituzione possa fornire una prova della correttezza di una soluzione di una ricorrenza, a volte è difficile formulare una buona ipotesi per la soluzione; disegnare un albero di ricorsione è una tecnica semplice per ideare una buona ipotesi.

In un albero di ricorsione ogni nodo rappresenta il costo di un singolo sottoproblema nell'insieme delle chiamate ricorsive di funzione.

Sommiamo i costi all'interno di ogni livello per ottenere un insieme di costi per livello; poi sommiamo tutti i costi per livello per determinare il costo totale di tutti i livelli della ricorsione.

Metodo dell'esperto

Il metodo dell'esperto rappresenta un ricettario per risolvere equazioni alle ricorrenze della forma a b f(n) dove e sono costanti >1 e è una funzione asintoticamente positiva. n a.

La ricorrenza descrive il tempo di esecuzione di un algoritmo che divide un problema di dimensione in n/b, a b sottoproblemi, ciascuno di dimensione dove e sono costanti positive.

• T(n/b) i sottoproblemi vengono risolti in modo ricorsivo, ciascuno nel tempo.
• F(n) la funzione comprende il costo di dividere il problema e combinare i risultati dei sottoproblemi.

E naftam'Yb.

Se allora 0Fln.

• Tin 8Dm'YbFln.

Se allora Tin.

• N lognEnlofts.

Se e se.

• TrenoFlnffin fr 1c ca eperallora finiTin e.

Algoritmi di ordinamento

Insertion sort

INSERTION-SORT (A)

For to 1 j=2 A.length.

2 key = A[ j ].

3 // inserisce A[ j ] nella sequenza ordinata A[1...j-1].

4 i=j-1 while.

5 i>0 and A[ i ] > key.

6 A[i+1] = A[ i ].

7 i--.

8 A[i+1] = key.

L'indice j for identifica l'elemento corrente da inserire negli altri.

All'inizio di ogni iterazione del ciclo con indice j, A[1...j-1] il sottoarray formato dagli elementi è ordinato, mentre il sottoarray A[ j+1...n] sono gli elementi non ancora ordinati.

• Complessità temporale O(n).
• Caso ottimo, elementi già ordinati: 2O(n ).
• Caso pessimo, elementi in ordine decrescente: 2O(n ).
• Caso generale: O(1).
• Complessità spaziale: O(1).

Merge sort

MERGE-SORT (A, p, r)

If 1 p<r then.

2 q = (p+r) / 2.

3 MERGE-SORT (A, p, q).

4 MERGE-SORT (A, q+1, r).

5 MERGE (A, p, q, r) for.

All'inizio di ogni iterazione del ciclo, righe 11-16, il sottoarray A[p...k-1] contiene ordinati i k-p elementi più ti piccoli di L[1...n1+1] e R[1...n2+1].

L[ i ] e R[ j ] sono i più piccoli elementi dei loro array non copiati in A.

• Divide: n n/2 divide la sequenza degli elementi da ordinare in due sottosequenze di elementi ciascuna.
• Impera: merge_sort ordina le due sequenze in modo ricorsivo utilizzando l'algoritmo.
• Combina: merge fonde le due sottosequenze ordinate per generare la sequenza ordinata, usando merge.
• Complessità temporale D(n) = O(1).
• Divide, calcola il centro del sottoarray: tempo costante.
• N/2: T(n/2) Impera, risolve in modo ricorsivo i 2 sottoproblemi 2.
• Merge C(n) = O(n) Combina, la procedura richiede un tempo lineare.
• T(n) = 2T(n/2) + O(n) = O(n logn).

Quick sort

QUICK-SORT (A, p, r)

If 1 p<r then.

2 q = PARTITION (A, p, r).

3 QUICK-SORT (A, p, q).

4 QUICK-SORT (A, q+1, r).

All'inizio di ogni iterazione del ciclo, righe 3-6, per qualsiasi (A, p, r) PARTITION k indice dell'array.

1 x = A[r].

• P < k < i A[k] < x se allora.

2 i = p-1.

• I+1 < k < j-1 A[k] > x se allora.

For to 3 j=p r-1.

• K = r A[k] = x se allora.

If 4 A[ j ] < x.

5 i++.

Le ultime due righe inseriscono il pivot al suo posto nel 6 scambia A[ i ] con A[ j ] mezzo dell'array, scambiandolo con l'elemento più a 7 scambia A[i+1] con A[r] x, sinistra che è maggiore di e poi restituiscono il nuovo return 8 i+1 indice del pivot. tiP r22h22am xil XxEX sx.

(A, p, r) PARTITION-HOARE.

1 x = A[p].

2 i = p-1.

3 j = r+1 loop.

4 repeat.

5 6 j-- until.

7 A[ j ] < x repeat.

8 9 i++ until.

10 A[ i ] > x if.

11 i < j.

12 scambia A[ i ] con A[ j ].

Else return 13 j.

Il partizionamento costa O(n) in termini di tempo.

Il tempo di esecuzione del quick-sort dipende dal fatto che il partizionamento sia bilanciato o sbilanciato e questo, a sua volta, dipende da quali elementi vengono utilizzati per il partizionamento.

• Partizionamento nel caso peggiore n-1.

Si verifica quando la routine "partition" produce un sottoproblema con elementi e uno con 0 elementi.

Supponendo che questo partizionamento si verifichi in ogni chiamata ricorsiva, la ricorrenza per T(n) è a T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n) = O(n ).

• Partizionamento nel caso migliore, molto vicino al caso medio, n/2.

Si verifica quando la routine "partition" produce due sottoproblemi con elementi ciascuno.

Supponendo che questo partizionamento si verifichi per ogni chiamata ricorsiva, la ricorrenza per T(n) è T(n) = 2 T(n/2) + O(n) = O( n logn ).

Heap sort

Un heap è una struttura dati composta da un array che possiamo considerare come un albero binario quasi completo; ogni nodo dell'albero corrisponde ad un elemento dell'array, e tutti i livelli dell'albero sono completamente riempiti, tranne eventualmente l'ultimo che può essere riempito solo parzialmente.

Un array A che rappresenta un heap è un oggetto con due attributi:

• A.lenght, che indica il numero di elementi nell'array.
• A.heap-size, che indica il numero degli elementi dell'heap che sono registrati nell'array.

Cioè, anche se ci possono essere dei numeri memorizzati in tutto l'array A[1...A.lenght], soltanto i numeri in A[1...A.heap-size] sono elementi validi dell'heap.

Se i è l'indice di un nodo, gli indici di suo padre, del figlio sinistro e del figlio destro possono essere calcolati LEFT ( i ) RIGHT ( i ) PARENT ( i ) return return return 2i 2i+1 i/2.

In un max-heap, la proprietà è che per ogni nodo i si ha A[ PARENT(i) ] > A[ i ], ovvero il valore di un nodo è al massimo il valore di suo padre.

Quindi l'elemento più grande di un max-heap è memorizzato nella radice e il sottoalbero di un nodo contiene valori minori o uguali di quello contenuto nel nodo stesso.

In un min-heap, la proprietà è che per ogni nodo i si ha A[ PARENT(i) ] < A[ i ], ovvero il valore di un nodo è al minimo il valore di suo padre.

Quindi l'elemento più piccolo di un max-heap è memorizzato nella radice e il sottoalbero di un nodo contiene valori maggiori o uguali di quello contenuto nel nodo stesso.

Conservare la proprietà dell'heap

• MAX-HEAPIFY, quando viene chiamata, assume che gli alberi con radici LEFT(i) e RIGHT(i) siano max-heap, ma A[ i ] possa essere più piccolo dei suoi figli.

MAX-HEAPIFY (A, i).

l = LEFT(i).

r = RIGHT(i).

La procedura fa "scendere" il valore A[ i ] nel max-heap in modo che il sottoalbero con radice i diventi un max-heap.

If l < A.heap-size and A[ l ] > A[ i ].

Max = l.

Else max = i.

If r < A.heap-size and A[ r ] > A[max].

Ad ogni passo, viene determinato il più grande tra gli elementi A[ i ], A[left(i)] e A[right(i)]; il suo indice viene memorizzato in max.

Max = r.

If max != i.

Scambia A[i] con A[max].

MAX-HEAPIFY (A, max).

Se A[ i ] è più grande, allora il sottoalbero con radice nel nodo i è un max-heap e la procedura termina.

Altrimenti, uno dei due figli ha l'elemento più grande e viene scambiato con A[ i ] A[max]; in questo modo, il nodo i ed i suoi figli soddisfano la proprietà del max-heap.

Il nodo con indice massimo, però, adesso ha il valore originale A[ i ] e quindi il sottoalbero con radice in max potrebbe violare la proprietà del max-heap; di conseguenza, deve essere chiamata ricorsivamente la routine MAX_HEAPIFY per questo sottoalbero.

• Complessità temporale: O( logn ).

Costruire uno heap

• MAX-HEAPIFY.

Possiamo utilizzare la procedura dal basso verso l'alto, bottom-up, per convertire un array A[1...n], con n = A.lenght, in un max-heap.

Essendo un albero binario, tutti gli elementi nel sottoarray A[n/2...n] sono foglie dell'albero; la procedura BUILD-MAX-HEAP attraversa i restanti nodi dell'albero ed esegue MAX-HEAPIFY in ciascuno di essi.

BUILD-MAX-HEAP (A).

A.heap-size = A.lenght.

For down to i = A.lenght/2 1.

MAX-HEAPIFY (A,i).

• Complessità&agrav