Riassunto Algoritmi e Strutture dati

Algoritmi e strutture dati 2016

Jason Ravagli

Algoritmi di ordinamento

Concentriamo inizialmente il nostro studio su di una serie di algoritmi atti a risolvere il problema dell’ordinamento, che può essere formulato nel seguente modo:

Input: una sequenza di numeri <a₁, a₂, …, aₙ>

Output: una permutazione della sequenza in input tale che a₁ ≤ a₂ ≤ ... ≤ aₙ

Insertion sort

È l’algoritmo più semplice per il risolvere il problema dell’ordinamento, e risulta efficiente per input di piccole dimensioni. Riceve in input un array A, i cui numeri sono ordinati sul posto: ossia in ogni istante ci sono al più un numero costante di valori memorizzati all’esterno di A.

Codice

INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 i = j-1
4 while i > 0 and key < A[i]
5 A[i + 1] = A[i]
6 i = i - 1
7 A[i + 1] = key

Correttezza

Dimostriamo la correttezza di INSERTION-SORT attraverso la seguente invariante di ciclo: All’inizio di ogni iterazione del ciclo for (riga 1) l’array A[1 … j-1] è ordinato ed è formato dagli stessi elementi che originariamente erano in A[1 … j-1].

Per utilizzare questa invariante di ciclo dobbiamo dimostrare che essa è vera prima della prima iterazione, che ogni iterazione conserva l’invariante e che l’invariante fornisce un’utile proprietà per dimostrare la correttezza dell’algoritmo (il concetto è molto simile alla dimostrazione tramite induzione matematica).

Inizializzazione: l’invariante è banalmente dimostrata; l’elemento A[1] forma un array ordinato e A[1] occupa la stessa posizione che occupava nell’array originario.

Conservazione: supponiamo che ad una certa iterazione l’array A[1 … j-1] sia ordinato e che contenga gli stessi elementi che originariamente erano in A[1 … j-1]. Nel corso dell’iterazione memorizziamo l’elemento A[j] in key e nel ciclo while (riga 4) facciamo scorrere di una posizione verso destra tutti gli elementi che sono maggiori di key fino a quando non incontriamo il primo elemento minore o uguale a key, che avrà indice i. A questo punto il sottoarray A[1… i] contiene (ordinati) gli elementi minori o uguali di key e A[i+2 … j] contiene (sempre ordinati) quelli maggiori di key: inserendo key nella posizione i+1 l’array A[1 … j] contiene ordinati gli elementi che originariamente erano in A[1 … j] e l’invariante è valida per la successiva iterazione.

Conclusione: alla fine del ciclo for (riga 1) j vale A.length + 1, quindi A[1 … A.length] contiene ordinati gli elementi che originariamente erano in A[1 … A.length]. L’intero array di input è stato dunque ordinato.

Analisi

Indichiamo con n la dimensione dell’array di input e analizziamo i vari casi che si possono presentare.

• Caso migliore: Il caso migliore per INSERTION-SORT si verifica quando l’array in input è già ordinato. Il ciclo while (riga 5) non viene infatti mai eseguito, dato che A[i] è immediatamente minore o uguale a key, e di conseguenza il costo di un’iterazione del ciclo for (riga 1) è O(1). Dato che il numero di iterazioni è n - 1, il costo di INSERTION-SORT nel caso migliore è O(n).
• Caso peggiore: Il caso peggiore si verifica quando A è inversamente ordinato. All’iterazione j del ciclo for, il ciclo while esegue esattamente j - 1 iterazioni (tutti gli elementi del sottoarray A[1 ... j-1] sono maggiori di key e dunque devono scorrere tutti verso destra) con costo per iterazione di O(1). Sommando quindi i costi di ogni iterazione si viene a creare una serie aritmetica: il costo di INSERTION-SORT nel caso peggiore è O(n²).
• Caso medio: Nel caso medio ci aspettiamo che ad ogni iterazione del ciclo for circa la metà degli elementi di A[1 … j-1] sia più grande di A[j], dunque il ciclo while eseguirà all’incirca j/2 iterazioni. Il caso medio forma una serie aritmetica come il caso peggiore (con un fattore costante minore), con un costo pari a O(n²).

Algoritmi ricorsivi e paradigma divide et impera

Esistono vari modi per progettare algoritmi. Ad esempio, INSERTION-SORT è un algoritmo iterativo (ossia che utilizza cicli per risolvere il problema) con un approccio incrementale (si ordina un sottoarray di dimensione crescente per ottenere l’ordinamento dell’intero array).

Alternativamente si possono progettare algoritmi ricorsivi, ossia algoritmi che chiamano sé stessi più volte (invece di utilizzare cicli) per risolvere sottoproblemi del problema originario. Gli algoritmi ricorsivi generalmente usano un approccio divide et impera, che si basa su tre passi ad ogni livello di ricorsione:

• Divide: il problema viene suddiviso in sottoproblemi, istanze più piccole del problema originale
• Impera: i sottoproblemi vengono risolti, ricorsivamente (se troppo grandi) o direttamente (se sono sufficientemente piccoli, ossia se si è raggiunto il cosiddetto caso base, per cui conosciamo già la soluzione)
• Combina: le soluzioni dei sottoproblemi vengono combinate per formare la soluzione del problema originale

Un algoritmo ricorsivo può essere descritto attraverso la sua (dis)equazione di ricorrenza, un’espressione matematica che descrive una funzione (nel caso degli algoritmi, la funzione costo) in termini del suo valore per input più piccoli.

Esempio: { T(n) = Θ(1) se n = 1 2T(n/2) + Θ(n) se n > 1 }

Risolvere una ricorrenza significa trovare un limite asintotico per la funzione che la ricorrenza descrive. Di seguito presentiamo tre metodi utili alla risoluzione di ricorrenze.

Metodo di sostituzione

Il metodo di sostituzione per risolvere le ricorrenze si basa su due passi:

• Ipotizzare la forma della soluzione
• Usare l’induzione matematica per trovare le costanti che dimostrano che la soluzione è esatta.

Si tratta essenzialmente di sostituire la soluzione ipotizzata al posto della funzione espressa in termini di input più piccoli, e verificare tramite una disequazione che questa soluzione costituisce un limite superiore o inferiore per la funzione. Consideriamo come esempio la ricorrenza T(n) = 2T(n/2) + n ed ipotizziamo che la soluzione sia T(n) = O(n*lg(n)).

Dobbiamo dunque verificare che T(n) ≤ c*n*lg(n) per qualche costante c > 0. Supponiamo che la soluzione sia valida per n/2 (ipotesi induttiva), ossia che T(n/2) ≤ c*(n/2)*lg(n/2) e verifichiamo che lo è anche per n:

T(n) ≤ 2*c*(n/2)*lg(n/2) + n ≤ c*n*lg(n) – c*n + n = c*n*lg(n) ≤ c*n*lg(n) che è vero per c ≥ 1.

A voler essere rigorosi la soluzione andrebbe verificata anche per le condizioni al contorno di una ricorrenza, ma dato che stiamo trattando limiti asintotici ciò risulta trascurabile. Talvolta può accadere che la soluzione ipotizzata sia giusta, ma che non la disequazione non venga verificata a causa di un termine di ordine inferiore. In questi casi dobbiamo affinare la soluzione sottraendovi un termine di ordine inferiore e rieffettuando la verifica. Ad esempio con una soluzione ipotizzata di O(n), l’espressione da sostituire sarà cn – d dove d è una costante maggiore di 0.

Metodo dell’albero di ricorsione

Il problema del metodo di sostituzione è formulare buone soluzioni da verificare. Il metodo dell’albero di ricorsione viene incontro proprio a questa necessità: fornisce uno strumento per ipotizzare soluzioni di ricorrenze, che verranno successivamente verificate con il metodo di sostituzione.

L’albero di ricorsione di una ricorrenza è un albero in cui ogni livello identifica un livello di ricorsione, ed ogni nodo identifica il costo del sottoproblema generato dal corrispettivo nodo padre. Sommando il costo di tutti i livelli dell’albero otterremo un valore in funzione di n (dimensione del problema) che ci aiuterà a ricavare un limite asintotico.

Metodo dell’esperto

Il metodo dell’esperto permette di risolvere direttamente ricorrenze della forma T(n) = a*T(n/b) + f(n) con le costanti a ≥ 1 e b > 1, cioè, facendo riferimento al metodo divide et impera, problemi che generano a sottoproblemi di dimensione n/b e aventi un costo f(n) per i passi divide e combina.

Il metodo si basa sul seguente teorema:

Teorema dell’esperto

Data la ricorrenza T(n) = a*T(n/b) + f(n), se a ≥ 1, b > 1 e f(n), allora T(n) può essere asintoticamente limitata in uno dei seguenti modi:

1. Se f(n) = O(n^log_ba-ε) per qualche costante ε > 0, allora T(n) = Θ(n^log_ba).
2. Se f(n) = Θ(n^log_ba), allora T(n) = Θ(n^log_ba * lg(n)).
3. Se f(n) = Ω(n^log_ba+ε) per qualche costante ε > 0 e f(n/b) ≤ c*f(n) per qualche costante c < 1 e per ogni n sufficientemente grande, allora T(n) = Θ(f(n)).

Merge sort

Risolve il problema dell’ordinamento su un array A di n numeri adottando un approccio divide et impera:

• Divide: divide l’array A in due sottoarray di dimensione n/2.
• Impera: ordina i due sottoarray ricorsivamente.
• Combina: unisce i due sottoarray ordinati di dimensione n/2 in un unico array ordinato di dimensione n.

La ricorsione tocca il fondo quando n = 1 (caso base): in questo caso l’array contiene un solo elemento ed è quindi già ordinato.

Codice

MERGE-SORT(A, p, r)
1 if p < r
2 q = ⌊(p + r) / 2⌋
3 MERGE-SORT(A, p, q)
4 MERGE-SORT(A, q + 1, r)
5 MERGE(A, p, q, r)

MERGE(A, p, q, r)
1 n₁ = q – p + 1
2 n₂ = r – q
3 // copia i due sottoarray in array ausiliari
4 crea due nuovi array L[1 … n₁ + 1] e R[1 … n₂ + 1]
5 for i = 1 to n₁
6 L[i] = A[p + i – 1]
7 for j = 1 to n₂
8 R[j] = A[q + j]
9 // pone in fondo ai due array ausiliari sentinelle che facilitano i controlli nel ciclo
10 L[n₁ + 1] = ∞
11 R[n₂ + 1] = ∞
12 i = j = 1
13 for k = p to r
14 if L[i] ≤ R[j]
15 A[k] = L[i]
16 i = i + 1
17 else
18 A[k] = R[j]
19 j = j + 1

Gli input p ed r per MERGE-SORT sono rispettivamente l’indice d’inizio e l’indice di fine del sottoarray di A da ordinare (per ordinare l’intero array si effettua la chiamata MERGE-SORT(A, 1, A.length)). Se p < r si ha il caso ricorsivo, altrimenti si ha il caso base e l’array (di un solo elemento) è già ordinato. È fondamentale il passo combina, realizzato tramite la procedura MERGE. Essa prende in input due sottoarray di A determinati dagli indici p, q ed r, A[p … q] e A[q+1 … r], che si suppone siano ordinati e li fonde per creare l’array ordinato A[p … r].

Correttezza

La correttezza di MERGE-SORT è determinata dalla correttezza della procedura ausiliaria MERGE. Per verificare quest’ultima definiamo la seguente invariante di ciclo per il ciclo for (riga 14): All’inizio di ogni iterazione l’array A[p … k – 1] contiene, ordinati, i k – p elementi più piccoli di L e di R. Inoltre, L[i] e R[j] sono gli elementi più piccoli dei rispettivi array a non essere stati ancora copiati in A.

Dimostriamo che essa è valida prima della prima iterazione del ciclo, che ogni iterazione del ciclo conserva l’invariante e che l’invariante fornisce un’utile proprietà per dimostrare la correttezza quando il ciclo termina.

Inizializzazione: prima della prima iterazione k = p, quindi l’array A[p … k – 1] è vuoto. Essendo inoltre gli array L ed R ordinati e i = j = 1, L[i] e R[j] sono i più piccoli elementi dei rispettivi array che non sono ancora stati copiati in A e l’invariante è banalmente dimostrata.

Conservazione: supponiamo che L[i] ≤ R[j] (la dimostrazione nell’altro caso è analoga). L[i] è il più piccolo elemento a non essere ancora stato copiato in A, inserendolo quindi nella posizione k otteniamo l’array A[p … k] che conterrà ordinati i k – p + 1 elementi più piccoli di L e di R. Incrementando gli indici i e k si mantiene l’invariante per la successiva iterazione.

Conclusione: alla fine del ciclo k = r + 1, dunque l’array A[p … r] conterrà ordinati i r – p + 1 elementi più piccoli di L e R. L e R hanno in totale n₁ + n₂ = r – p + 3 elementi: i 2 elementi che non sono stati copiati in A sono le sentinelle di valore infinito aggiunte in coda agli array. I sottoarray sono stati dunque fusi in un unico array ordinato.

Analisi

Analizziamo da prima la complessità di MERGE. Indicando con n = r – p + 1 la dimensione dell’input, osserviamo che i due cicli che copiano i sottoarray in L e R eseguono n₁ + n₂ = Θ(n) iterazioni, ciascuna in un tempo costante. Il ciclo for (riga 14) esegue esattamente n iterazioni, ciascuna in un tempo costante, quindi anch’esso avrà un costo Θ(n). In conclusione, la procedura MERGE viene eseguita nel tempo Θ(n).

Passiamo ora a definire la ricorrenza di MERGE-SORT, e supponiamo che n sia una potenza di 2, così da ottenere sempre due sottoproblemi di dimensione uguale dal passo divide. Nel caso base viene eseguito solo il controllo alla riga 1, quindi il costo è Θ(1). Nel caso ricorsivo, il passo divide impiega un tempo O(1) e genera due sottoproblemi di dimensione n/2 da passare al passo impera; abbiamo inoltre già dimostrato che il passo combina impiega un tempo Θ(n).

La ricorrenza risultante è dunque la seguente:

{ T(n) = Θ(1) se n = 1 2T(n/2) + Θ(n) se n > 1 }

Utilizziamo il Teorema dell’Esperto. Abbiamo a = b = 2 da cui Θ(n) = Θ(n), perciò T(n) = Θ(n lg n), migliore rispetto al tempo quadratico di INSERTION-SORT. (Allo stesso risultato si arriva costruendo l’albero di ricorsione (che avrà lg(n) + 1 livelli perché ogni problema viene suddiviso in 2 sottoproblemi, ed ogni livello avrà un costo pari a c*n, con c costante), ipotizzando che il risultato sia Θ(n*lg(n)) e verificando il limite superiore e inferiore con il metodo di sostituzione.

Analisi probabilistica e algoritmi randomizzati

Introduciamo un nuovo problema computazionale per studiare un metodo di analisi degli algoritmi ed un nuovo approccio alla realizzazione di algoritmi ad esso correlato. Supponiamo di dover assumere una nuova persona per un posto di lavoro, e di voler assumere il migliore impiegato possibile da una lista di n candidati. I candidati sono forniti da un’agenzia di lavoro, che richiede un piccolo compenso per ogni colloquio con un candidato, ed un compenso molto più sostanzioso per ogni assunzione. Non sappiamo nulla di un candidato finché non veniamo a colloquio con lui, perciò se a seguito di un colloquio questi si dimostra migliore dell’attuale impiegato, licenziamo quest’ultimo ed assumiamo il nuovo candidato.

Codice

HIRE-ASSISTANT(n)
1 migliore = 0 // crea candidato fittizio
2 for i = 1 to n
3 colloquio con candidato i
4 if candidato i migliore dell’impiegato migliore
5 migliore = i
6 assumi candidato i

Siamo dunque interessati a sapere quale sarà il costo totale da sostenere. Osserviamo che dobbiamo sempre effettuare n colloqui, ed un numero variabile m di assunzioni dipendenti dalla lista di candidati fornita dall’agenzia e dall’ordine in cui essi arrivano. Indicando con c_c il costo di un colloquio e c_a il costo di un’assunzione, il costo totale della procedura è O(n*c_c + m*c_a). Dato che il numero di assunzioni è fisso e comunque c_c è molto minore di c_a concentriamo la nostra analisi sul costo derivante dalle assunzioni.

Il caso peggiore si verifica quando i candidati arrivano in ordine crescente di competenza: in tal caso dovrà essere effettuata un’assunzione ad ogni iterazione, ed il costo sarà di O(n*c_a). Siamo però interessati a sapere quale sarà il costo sostenuto nel caso medio. Possiamo usare l’analisi probabilistica per effettuare una media sul tempo di esecuzione di tutti gli input possibili, e ricavare un tempo di esecuzione medio. L’analisi probabilistica consiste nell’uso della probabilità per analizzare un problema. Per utilizzare l’analisi probabilistica però dobbiamo avere informazioni sulla distribuzione degli input o almeno fare ipotesi su di essa. Nel nostro caso possiamo supporre che la distribuzione in input sia casuale. Dato che siamo in grado di determinare, dati due candidati, qual è il più qualificato, (esiste un ordine totale nei candidati) supponiamo di assegnare un numero d’ordine da 1 a n, detto rango, ad ogni candidato, con la convenzione che maggiore è il rango maggiore è la qualifica. La lista in input <rango(1), rango(2), …, rango(n)> sarà una permutazione della lista <1, 2, …, n>. Supporre che l’input sia casuale equivale a supporre che la lista in input si...