Guida di Programmazione Avanzata




SEZIONE I - Analisi di Algoritmi e Complessità

Lezione 1 - Tecniche di Progettazione di Algoritmi
Secondo una concezione che può essere fatta risalire ad Euclide e che è stata ampiamente formalizzata in una delle opere di Cartesio il concetto di problema rispecchia una struttura ben definita.

Un problema consta dei seguenti elementi:

Possiamo così individuare, ad esempio, fra i vari tipi di problemi, le seguenti classi:


Lezione 2 - Introduzione alla Complessità di Calcolo
Si può definire un'ALGORITMO una procedura computazionale ben definita che prende un valore, o un insieme di valori, come INPUT e produce un valore, o un insieme di valore, come OUTPUT.
Generalmente l'input necessario per fornire un risultato al problema computazionale viene chiamato istanza di un problema.

Il problema più comune da affrontare è il "Problema di Ordinamento" (detto anche SORTING PROBLEM) che consiste nell'ordinare in ordine crescente un insieme di valori. L'importanza di questo problema è che risulta un'operazione fondamentale nel campo dei computer.

Se si pensa che l'algoritmica (intesa come studio della complessita e dell'ottimizzazione di algoritmi) abbia un'applicazione limitata conviene dare un'occhiata alla carrellata dei maggiori campi di applicazione di questa materia.
Inoltre questi problemi hanno delle caratteristiche in comune:

Generalmente per ottimizzare un problema di ordinamento bisogno ricorrere a particolari Strutture Dati (o DATA STRUCTURES) che servono per organizzare i dati in maniera da facilitare (e velocizzare) l'accesso e la modifica.

Lezione 3 - Ordine di Grandezza delle funzioni

Dimensione dell'input
Per rendere significativo il concetto di complessita computazionale è necessario determinare in funzione di cosa viene espresso il consumo di risorse da parte di un determinato programma. Ci conviene adottare come parametro la quantità di memoria utilizzata per rappresentare i dati di ingresso.
Molto spesso, tuttavia, anzichè considerare la dimensione complessiva della rappresentazione dei dati si può assumere, per semplicità, un parametro caratterizzante la lunghezza dell'input.

Se W è la rappresentazione del polinomio

Operazioni Dominanti
Diciamo che un'operazione in un algoritmo è dominante quando (n), cioè il numero di volte che essa viene ripetuta durante l'esecuzione dell'algoritmo in funzione della dimensione dell'input, verifica

c • (n) ≥ T(n)

dove "c" è una opportuna costante e "T" è il costo di esecuzione.


L'analisi Asintotica

Regole di Semplificazione
- Dei fattori costanti: k • O(f(n)) = O(k • f(n))
- Della somma: Se f(n) O(g(n)), allora f(n) + g(n) O(g(n))
- Del prodotto: Se f(n) è O(f1(n)) e g(n) è O(g1(n)), allora f(n)g(n) è O(f1(n)g1(n))
- Dei polinomi: Un polinomio amnm + ... + a1n + a0 è O(nm)
- Transitiva: Se f(n) è O(g(n)) e g(n) è O(h(n)), allora f(n) è O(h(n))


Confronto tra Classi di Complessità
Posto n=60 ed esprimendo il tempo in secondi,

O(1) COSTANTE k (~ 0,000001)
O(logn) LOGARITMICA 0,000018
O(n) LINEARE 0,00006
O(n • logn) N-LOGN 0,001
O(n2) QUADRATICA 0,0036
O(n3) CUBICA 0,216
O(n5) ALLA QUINTA 13 mesi
O(2n) ESPONENZIALE 366 secoli


Lezione 4 - Complessità dei programmi iterativi
In questa lezione daremo una regola per calcolare la complessità del tempo di esecuzione dei programmi non ricorsivi e in cui non vi siano cicli nelle chiamate di funzione (ricorsione nascosta). La regola è definita per induzione sulla sintassi dei costrutti del linguaggio relativi alle espressioni ed ai comandi: la complessità viene definita direttamente sui costrutti elementari, mentre la complessità dei costrutti composti è definita in base alla complessità dei costrutti componenti (definizione composizionale).
Nel seguito viene definita una grammatica che definisce la sintassi delle espressioni e dei comandi di un linguaggio di programmazione, che è un sottoinsieme del C++ (e molto simile al Java). I simboli nonterminali della grammatica sono le lettere maiuscole: E genera le espressioni e C i comandi; inoltre assumiamo che V generi un qualsiasi valore elementare, I un qualsiasi identificatore e O un qualsiasi operatore. Indichiamo con I(E,...,E) una chiamata di funzione, mentre I[E] è l'operatore di selezione di un array. Per semplicità, la notazione non è del tutto esatta nelle produzioni che riguardano le chiamate di funzione. Ç è il simbolo utilizzato per rappresentare la complessità.

E ::= V | E O E | O E | I(E,...,E) | I | I[E]
C ::= I = E | I[E] = E | If(E) C | If(E) C else C | for(I=E;E;I=E) C
        |while(E) C | do C while(E) | I(E,...,E) | {C...C} | return E;

Complessità delle espressioni
1) Ç[V] = Ç[I] = O(1)
2) Ç[E1 O E2] = Ç[E1] + Ç[E2]
3) Ç[I[E]] = Ç[E]
4) Ç[I(E1,...,En)] = Ç[E1] + Ç[E2] + ... Ç[En] + Ç[{C...C}]

Complessità dei comandi
1) Ç[I=E] = Ç[return E] = Ç[E]
2) Ç[I[E1]=E2] = Ç[E1] + Ç[E2]
3) Ç[If(E) C] = Ç[E] + Ç[C]
4) Ç[If(E) C1 else C2] = Ç[E] + O(max(f(n),g(n)))
5) Ç[while(E) C] = Ç[E] + (Ç[E] + Ç[C]) • O(g(n))
6) Ç[do C while(E)] = (Ç[E]+Ç[C]) • O(g(n))
7) Ç[{C1...Cn}] = Ç[C1] + Ç[C2] + ... + Ç[Cn]
8) Ç[for(I=E1; E2; I=E3) C] = Ç[E1] + Ç[E2] + (Ç[C] + Ç[E2] + Ç[E3]) • O(g(n))

NB: Quando si studia la complessità di una funzione (g) che ne chiama un'altra (f) bisogna porre attenzione al risultato di f (istruzione return) e non tanto alla sua complessità.

Analisi del Caso Medio
Il principale motivo per lo studio del comportamento medio di un algoritmo è legato al fatto che in molte circostanze non è necessario che un algoritmo operi con una quantità limitata di risorsa su ogni possibile input, ma è importnate che sia "generalmente efficiente", anche se in alcuni casi la sua esecuzione richiede costi elevati. In alcuni casi è ragionevole fare la seguente ipotesi di equi-probabilità sull'input del problema: per ogni fissato N assumiamo che tutte le possibili istanze aventi dimensione n abbiano la stessa probabilità di essere fornite come input. Comunque a volte è necessario fare altre ipotesi sulla distribuzione di probabilità dell'input basate sulle caratteristiche del problema.

Lezione 5 - Insertion Sort (iterativo)

Uno dei metodi più semplici per ordinare un array è l'insertion sort [ordinamento per inserimento]. Nella vita quotidiana si ha un esempio di insertion sort giocando a carte. Per ordinare le carte che tenete in mano, ne estraete una, scorrete le restanti, e inserite la carta estratta nella posizione corretta. Questo processo viene ripetuto finché tutte le carte saranno nella sequenza corretta. La complessità sia del caso medio che del caso peggiore è O(n2).
Se l'array contiene n elementi, dobbiamo indicizzarne n - 1. Per ogni elemento, dobbiamo esaminarne e spostarne, al più, altri n - 1. Questo porta ad un algoritmo di complessità O(n2). Insertion sort è un algoritmo di ordinamento di tipo in-place. Questo significa che l'array viene ordinato "sul posto", senza utilizzare memoria ulteriore. Insertion sort è anche un ordinamento stabile. Gli ordinamenti stabili mantengono l'ordinamento originale quando vi sono elementi uguali nei dati in input.

void InsertionSort(int a[], int n) {
  for(j = 2; j < n+1; j++) {
    int k = a[j];
    for(int i = j-1; (i>O) && (a[i]>k); i--) {
      a[i+1] = a[i];
    }
    a[i+1] = k;
  }
}

COMPLESSITA' NEL CASO MIGLIORE: O(n)
COMPLESSITA' NEL CASO PEGGIORE: O(n2)
COMPLESSITA' NEL CASO MEDIO: O(n2)


Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

Insertion Sort Shell Sort

L'applet :: Algoritmo di ordinamento generico :: Algoritmo Insertion Sort :: Algoritmo Shell Sort

APPROFONDIMENTO: Shell sort, ideato da Donald L. Shell, è un algoritmo di ordinamento non-stabile e in-place. Shell sort migliora l'efficienza dell'insertion sort spostando velocemente gli elementi nelle loro destinazioni. La complessità media è O(n1.25), mentre quella del caso peggiore diventa O(n1.5).


Lezione 6 - Selection Sort (iterativo)
Il problema dell'ordinamento è quello di ordinare in modo crescente o decrescente, in base ad una qualche definizione di relazione d'ordine, un insieme di elementi. In queste due lezioni presentiamo due algoritmi di ordinamento non ricorsivi. Nelle lezioni successive torneremo sul problema e definiremo altri algoritmi più efficienti. Consideriamo il caso in cui l'insieme sia memorizzato in una array. Il primo algoritmo che consideriamo, chiamato SelectionSort è il seguente, dato un array di n elementi si cerca l'elemento più piccolo e lo si mette al primo posto. Poi si cerca il più piccolo fra i rimanenti n-1 elementi e lo si mette al secondo posto, e così via. Ecco qui di seguito presentato il codice dell'algoritmo; l'algoritmo si appoggia ad una funzione che scambia due elementi di un array.

void SelectionSort(int a[], int n) {
  for(int i=0; i<n-1; i++) {
    int min=i;
    for(int j=i+1; j<n; j++)
      if(a[j] < a[min]) min=j;
    Scambia(a,i,min);
  }
}

void Scambia(int a[], int x, int y) {
  int temp;
  temp=a[x];
  a[x]=a[y];
  a[y]=temp;
}

La complessità di tale programma è O(n2), infatti T(n) = (n-1)•n/2. Anche il numero di confronti è uguale a (n-1)•n/2 e quindi O(n2), mentre il numero di scambi risulta O(n), perchè "Scambia" è richiamata solo dal primo for.

Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

Selection Sort

L'applet :: Algoritmo di ordinamento generico :: Algoritmo Selection Sort


Lezione 7 - Bubble Sort (iterativo)
Il secondo metodo di ordinamento che consideriamo, il BubbleSort, consiste nello scorrere l'array da "destra" verso "sinistra", scambiando due elementi contigui se non sono nell'ordine giusto. Ogni volta un elemento risale fino che non incontra un elemento più piccolo. Alla fine della iterazione i-esima del ciclo più esterno, gli elementi sono ordinati dal primo fino all'i-esimo.

void BubbleSort(int a[], int n) {
  for(int i=0; i<n-1; i++)
    for(int j=n-1; j>=i+1; j--)
      if(a[j] < a[j-1]) Scambia(a,j,j-1);
}

void Scambia(int a[], int x, int y) {
  int temp;
  temp=a[x];
  a[x]=a[y];
  a[y]=temp;
}

Anche questo programma ha complessità O(n2), sia nel caso medio sia nel peggiore. Se gli elementi da ordinare hanno una grossa dimensione, meglio il Selection-Sort che fa meno scambi ( O(n) ); infatti il Bubble-Sort fa in media O(n2) scambi (per la precisione n2/4), questo perchè la chiamata di "Scambia" si trova nel ciclo for più interno.

Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

Bubble Sort Bubble Sort Bidirezionale

L'applet :: Algoritmo di ordinamento generico :: Algoritmo Bubble Sort :: Algoritmo Bubble Sort Bidirezionale

APPROFONDIMENTO: Il Bubble Sort Bidirezionale è una variante del Bubble Sort che scorre gli elementi in ambedue le direzioni.


Lezione x - Complessità dei programmi ricorsivi
Per calcolare l'ordine di tempo T(n) di una funzione ricorsiva, non possiamo applicare direttamente il ragionamento che abbiamo adottato per i programmi iterativi. Cercheremo quindi di definire T(n) in modo induttivo. Data una funzione ricorsiva, la studiamo in due casi: il caso in cui la funzione non effettua nessuna chiamata ricorsiva (caso base della ricorsione) e quelli in cui la effettua. Nel primo caso facciamo la valutazione della complessità del tempo di esecuzione direttamente come per le funzioni iterative. Nel secondo caso definiamo la funzione incognita T(n) in funzione del tempo T(k) di ogni chiamata ricorsiva. Ovviamente, perchè la definizione induttiva sia corretta, è necessario assumere k ≤ n. Non possiamo però semplificare completamente le espressioni O-grande così ottenute, perchè esse in generale contengono funzioni concrete oltre a classi di funzioni. Quindi è necessario a questo punto rimpiazzare le classi di funzioni che compaiono in una espressione con funzioni contrete, anche se espresse mediante costanti simboliche; per esempio, al posto di O(1), possiamo considerare una costante c e al posto di O(n) una funzione cn. In generale, al posto di O(f(n)) possiamo considerare cf(n), dove c è una costante. Questa definizione iduttiva di T(n) si chiama relazione di ricorrenza. Essa deve essere risolta per trovare la funzione incognita T(n).

Lezione 9 - Selection Sort (ricorsivo)

void RSelectionSort(int a[], int n, int i=0) {
  if(i<n-1) {
    int min=i;
    for(int j=i+1; j<n; j++)
      if(a[j] < a[min]) min=j;
    Scambia(a,i,min);
    RSelectionSort(a,n,i+1);
  }
}

void Scambia(int a[], int x, int y) {
  int temp;
  temp=a[x];
  a[x]=a[y];
  a[y]=temp;
}

Calcoliamone la complessità:

  T(1) = a
  T(n) = bn + T(n-1)   n > 1, quindi
  T(n) = (bn(n-1))/2 - b + a O(n2)

Quindi ha la stessa complessità della versione iterativa.

Lezione 8 - Metodo del "Divide et Impera"
Quasi tutti gli algoritmi ricorsivi che abbiamo visto sono basati su una tecnica di progetto di algoritmi chiamata Divide et Impera (o Command and Conquer), cioè per risolvere un problema per un certo insieme di dati, lo si affronta applicando ricorsivamente su sottoinsiemi dei dati del problema (Partizioni) e ricomponendo poi i risultati (lavoro di Combinanzione).

void DividEtImpera(S) {

  if(|S| <= m) {
    <risolvi direttamente il problema>
    // m è la dimensione che permette una risoluzione immediata
  }
  else
  {
    <dividi S in B sottoinsiemi S1, S2, ..., Sb>
    DividEtImpera(SI1); // 1≤I1...Ia≤b
    DividEtImpera(SI2);
    ...
    ...
    DividEtImpera(SIa);
    <combina i risultati ottenuti>
  }

}

Se i sottoinsiemi sono bilanciati, posta d una costante che indica il tempo per risolvere il problema quando il numero dei dati è minore di m; b è il numero di sottoinsiemi, a indica su quanti di questi insiemi la procedura è richiamata ricorsivamente, allora valgono le seguenti relazioni:

T(n) = d n ≤ m
T(n) = aT(n/b) + hnk n > m
   
T(n) O(nk) a < bk
T(n) O(nklogn) a = bk
T(n) O(nlogba) a > bk


Lezione 10 - Merge Sort (ricorsivo)
L'algoritmo di ordinamento MergeSort (ordinamento per fusione), oltre che su array, è applicato spesso alle liste. Consideriamo perciò la sua versione "su lista". L'algoritmo è definito induttivamente nel modo seguente. Data una lista, se la sua lunghezza è 0 o 1 allora MergeSort restituisce la lista inalterata. Altrimenti, si divide la lista in due sottoliste uguali (o quasi uguali se il numero di elementi è dispari). Queste vengono ordinate ricorsivamente con MergeSort. Alla fine le liste risultanti sono fuse in un'unica lista ordinata. La funzione MergeSort utilizza due funzioni, una Split per dividere la lista in due liste, e l'altra Merge per fare la fusione ordinata di due liste.

La funzione Split divide la lista in ingresso in due sottoliste di uguale dimensione. Una possibile implementazione di Split è la seguente: data una lista lista1, Split costruisce una seconda lista lista2 contenente gli elementi di lista1 con posizione pari ed inoltre modifica lista1 in modo che questa alla fine contenga soltanto gli elementi che erano in posizione dispari.
La complessità di Split, prendendo come dimensione il numero di elementi della è O(n). Per la precisione, il ciclo viene eseguito un numero di volte uguale a n/2.

La funzione Merge riceve in ingresso due liste già ordinate e le fonde in modo da ottenere una lista ordinata, scorrendo contemporaneamente le due liste. Con più precisione, date le due liste lista1 e lista2, se una delle due liste è vuota, allora Merge restituisce l'altra. Altrimenti, se il primo elemento di lista1 è minore o uguale al primo elemento di lista2, Merge restituisce la lista che ha come primo elemento il primo elemento di lista1 e come resto il risultato del Merge applicato a lista1 senza il primo elemento e lista2. Altrimenti Merge restituisce la lista che ha come primo elemento il primo elemento di lista2 e come resto il risultato del Merge applicato a lista1 e lista2 senza il primo elemento.

elem* MergeSort(elem* lista1) {
  if((lista1 == null) || (lista1->pun == null)) {
    return lista1;
  }
  elem* lista2=null;
  Split(lista1, lista2);
  return Merge(MergeSort(lista1), MergeSort(lista2));
}

void Split(elem* &lista1, elem* &lista2) {
  if((lista1 == null) || (lista1->pun == null)) {
    return;
  }
  elem* l = lista1->pun;
  lista1->pun = l->pun;
  l->pun = lista2;
  lista2 = l;
  Split(lista1->pun, lista2);
}

void Merge(elem* lista1, elem* lista2) {
  if(lista1 == null) return lista2;
  if(lista2 == null) return lista1;
  if(lista1->inf <= lista2->inf) {
    lista1->pun = Merge(lista1->pun, lista2);
    return lista1;
  } else {
    lista2->pun = Merge(lista1, lista2->pun);
    return lista2;
  }
}

La complessità di questo programma è O(nlogn), sia nel caso migliore sia nel caso medio sia nel caso peggiore. Il Merge e lo Split hanno complessità O(n). Il MergeSort può essere esperesso dalla relazione di ricorrenza:

  T(n) = 2T(n/2) + bn    n > 1

La cui soluzione è,

  T(n) = an + bn(log2n)     (nota bene: manca un passaggio)

Poichè la funzione T(n) è crescente anche per valori di n che non sono potenze di 2, abbiamo che T(n) è O(nlogn). Notiamo inoltre che il tempo di esecuzione di MergeSort non dipende dalla disposizione iniziale dei dati nella lista da ordinare, e quindi O(nlogn) è la complessità del tempo sia nel caso migliore che nel medio che nel peggiore. Può essere definitivo facilmente anche sugli array (con le opportune modifiche), quindi il MergeSort è migliore degli algoritmi quadratici visti precedentemente.

Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

Merge Sort

L'applet :: Algoritmo di ordinamento generico :: Algoritmo Merge Sort


Lezione 11 - Numeri di Fibonacci
I numeri di Fibonacci sono definiti in maniera induttiva nel modo seguente:

  f0 = 1
  f1 = 1
  fn = fn-1 + fn-2    per n > 1

Il codice della funzione è:

int Fibonacci(int n) {
  if(n < 2) {
    return 1;
  } else {
    return(Fibonacci(n-1) + Fibonacci(n-2));
  }
}

La relazione di ricorrenza è:

T(n) = d n ≤ 1
T(n) = b + T(n-1) + T(n-2) n > 2

Che ha soluzione ESPONENZIALE, ma esiste un algoritmo iterativo che risolve lo stesso problema in tempo lineare.

int Fibonacci(int n) {
  int k;
  int j = 1;
  int f = 1;

  for(int i = 2; i < n-1; i++) {
    k = j;
    j = f;
    f = k + j;
  }

  return f;
}

ed il corrispondente algoritmo ricorsivo, sempre con complessità lineare.

int Fibonacci(int n, int a = 1, int b = 1) {
  if(n == 0) {
    return a;
  } else {
    return Fibonacci(b, a+b, n-1);
  }
}


Lezione 12 - Ricerca Binaria
L'algoritmo di ricerca binaria è quello che viene usato, ad esempio, quando vogliamo consultare un elenco telefonico. Un algoritmo lineare dovrebbe ricercare tutti gli elementi partendo dal primo e arrivando all'ultimo (complessità O(n)); un'altra soluzione è quella di dividere l'elenco a metà e verificare se l'elemento sta a destra o sinistra, quindi si sceglie la metà che contiene il numero e si verifica ricorsivamente fino alla soluzione; la complessità totale risulta essere O(logn).

RicBinaria(z, a, i, j) {
  if(i>j) return false;
  m = ((i+j)/2);
  if(z == a[m]) return true;
  if(z < a[m]) {
    RicBinaria(z, a, i, m-1);
  } else {
    RicBinaria(z, a, m+1, i);
  }
}


Lezione 13 - Moltiplicazione rapida di Interi
La moltiplicazione di interi ha generalmewnte complessità O(n2); esiste un metodo per eseguire in maniera migliore tale compito ed è quello della moltiplicazione rapida. Supponiamo di avere due numeri A e B con n cifre:

  A = A1 x 10n/2 + A2 ,   B = B1 x 10n/2 + B2

Abbiamo quindi, semplificando,

  A x B = A1B110n + ((A1 + A2)(B1 + B2) - A1B1 - A2B2)10n/2 + A2B2

Quindi esprimibili come tre moltiplicazioni tra numeri di n/2 cifre.

Int MoltRapida(A, B, n) {
  if(n == 1) reutrn A*B;

  // dividi A in A1A2 e B in B1B2 di n/2 cifre

  int x = MoltRapida(A1, B1, n/2);
  int y = MoltRapida(A2, B2, n/2);
  int z = MoltRapida(A1+A2, B1+B2, n/2)- x - y;
  return x*10n + z*10n/2 + y;
}

La complessità risulta,

  T(1) = d
  T(n) = 3T(n/2) + V(n)

  T(n) O(nlog23) ~ O(n1,59) < O(n2)

Lezione 14 - Limiti inferiori alla Complessità
Gli algoritmi presentati danno per il problema dell'ordinamento un limite superiore di O(n2). Prima di chiederci se esistono algoritmi che anche nel caso peggiore richiedono un numero di confronti minore di n2 vediamo dunque quale sia la delimitazione inferiore dell'ordinamento. Studiando un albero di decisione, se abbiamo un vettore di n elementi, i possibili ordinamenti totali sono n! e quindi il numero minimo di confronti è logn! che, in base all'approsimazione di Stirling, è ~ nlogn. Quindi esiste il limite inferiore Ω(nlogn).
Quindi l'HeapSort (che faremo più avanti) e il MergeSort sono due algoritmi ottimali per l'ordinamento, poichè richiedono nel caso peggiore O(nlogn) confronti e altrettanti scambi.

  APPROSIMAZIONE DI STIRLING:     n! ~ (n/2)n ~ nlogn

Lezione 15 - Altre tecniche di progettazione
Esistono altre tecniche di progettazione di algoritmi che possono rivelarsi utili nel prosequo di questa guida.



SEZIONE II - Progetto di Algoritmi e Strutture Dati

Lezione 16 - Alberi Binari e Alberi Generici

ALBERI BINARI
Un albero binario è un insieme di nodi; se l'insieme non è vuoto, un nodo è chiamato radice e i restanti sono suddivisi in due sottoinsiemi disgiunti che sono a loro volta alberi binari e sono detti SOTTOALBERI SINISTRO e DESTRO della radice.

La struttura di un ALBERO BINARIO è definita come segue:

Struct Albero {
  Tiponome nome; // in genere Tiponome è INT
  Albero* sinistro;
  Albero* destro;
}

Le visite su questo tipo di albero sono:

  - ANTICIPATA:    NOME, SINISTRO, DESTRO
  - DIFFERITA:       SINISTRO, DESTRO, NOME
  - SIMMETRICA:    SINISTRO, NOME, DESTRO



ALBERI GENERICI
Un albero generico è un insieme non vuoto di nodi, di cui uno è chiamato RADICE, e i restanti sono suddivisi in sottoinsiemi disgiunti che sono a loro volta alberi e sono detti sottoalberi della RADICE.

Struct Albero {
  Tiponome nome; // in genere Tiponome è INT
  Albero* figlio;
  Albero* fratello;
}

Visite possibili:

  - VISITA IN ORDINE ANTICIPATO:    RADICE, TUTTI I SOTTOALBERI
  - VISITA IN ORDINE DIFFERITO:       TUTTI I SOTTOALBERI, RADICE

Lezione 19 - HeapSort

 - CODA
Filosofia FIFO (First In First Out)


 - PILA
Filosofia LIFO (Last In First Out)


 - HEAP E HEAPSORT
Adesso introduciamo un algoritmo di ordinamento chiamato HeapSort. Come il MergeSort, ma diversamente dall'InsertionSort, l'HeapSort ha complessità O(nlogn). Come l'InsertionSort, ma diversamente dal MergeSort, l'HeapSort ordina i dati in locale. Quindi l'HeapSort combina le due caratteristiche migliori degli algoritmi discussi. L'HeapSort utilizza la struttura dati dell'Heap.


 Struttura dati dell'Heap
L'Heap è un array di oggetti che possono essere visti come un albero binario bilanciato (o semibilanciato).
Un array A che rappresenta un Heap ha due attributi:

  - Length[A]: che è il numero di elementi nell'array;
  - Heap-Size[A]: che è il numero di elementi nell'heap dentro l'array A.

La radice dell'albero è A[1] e dato l'i-simo nodo si può trovare il nodo genitore ed i nodi figli affidandosi alle seguenti operazioni:

  - PARENT(i) -> RETURN i/2
    Si ottiene sciftando a destra di uno la rappresentazione binaria di i. Complessità O(1).

  - LEFT(i) -> RETURN 2i
    Si ottiene sciftando a sinistra di uno la rappresentazione binaria di i. Complessità O(1).

  - RIGHT(i) -> RETURN 2i+1
    Come il left, ma in aggiunta si pone ad 1 il bit meno significativo. Complessità O(1).

L'Heap può essere "di massimo" o "di minimo", in cui l'elemento massimo (o minimo) rispetto a quelli contenuti è nella radice (in A[1] quindi). Per l'algoritmo HeapSort useremo il Max-Heap, ovvero quello con l'elemento massimo in A[1].

Le procedure usate sono presentate di seguito, con una piccola descrizione e la loro complessità:

  - Max-Heapify, è una procedura che mantiene la proprietà del MaxHeap ed ha complessità O(logn).

  - Build-Max-Heap, produce un Max-Heap da un array non ordinato. Complessità O(n).

  - Max-Heap-Insert / Heap-Extract-Max / Heap-Increase-Key / Heap-Maximum: Queste procedure permettono le operazioni
    di inserimento, modifica ed interrogazione di un Heap. Hanno complessità O(logn).

  - HeapSort è la procedura che ordina un array in locale. Ha complessità O(nlogn).

Max-Heapify(int A[], int i) {
  l = LEFT(i);
  r = RIGHT(i);

  if((l <= Heap-Size[A]) && (A[l] > A[i])) {
    largest = l;
  } else {
    largest = i;
  }

  if((r <= Heap-Size[A]) && (A[r] > A[largest])) {
    largest = r;
  }

  if(largest != i) {
    Scambia(A, i, largest);
    Max-Heapify(A, largest);
  }
}

Esamina l'elemento i-simo con i suoi figli e pone (se esiste) l'elemento maggiore in i e l'elemento minore in uno dei suoi figli. Infine si richiama su l'eventuale nodo figlio con il quale è stato fatto lo scambio e quindi contiene l'elemento minore.
La complessità di Max-Heapify è esprimibile nella forma:

  T(n) ≤ T(2n/3) + O(1)

quindi a = 1, b = 3/2, e k = 0, da cui T(n) O(logn).

La procedura Max-Heapify può essere usata per convertire un qualsiasi array A di lunghezza n in una struttura di Heap massimo. Tale nuova procedura, chiamata Build-Max-Heap, viene spiegata di seguito.

Build-Max-Heap(A) {
  Heap-Size[A] = Length[A];
  for(i = Length[A]/2; i > 1; i--) {
    Max-Heapify(A, i);
  }
}

Il limite superiore di questa procedura sarebbe,

  TBuild-Max-Heap = n • O(logn)Max-Heapify = O(nlogn)

ma in realtà ogni volta il "peso" dell'albero cambia, quindi facendo complessi calcoli matematici la complessità è O(n).

HeapSort(A) {
  Build-Max-Heap(A);
  for(i = Length[A]; i > 2; i--) {
    Scambia(A, 1, i);
    Heap-Size[A] = Heap-Size[A] - 1;
    Max-Heapify(A, 1);
  }
}

La complessità risulta essere,

  THeapSort = O(n)Build-Max-Heap + nciclo FORO(logn)Max-Heapify = O(nlogn)

In sostanze l'HeapSort prende il primo elemento (il più grande) e lo scambia con l'ultimo. L'ultimo finendo in prima posizione "corrompe" la struttura dell'Heap, quindi viene chiamato Heapify per ricomporre l'Heap di (n-1) elementi. Ricorsivamente questa procedura ordina "dal fondo" e quindi alla fine l'array è ordinato.

Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

HeapSort

L'applet :: Algoritmo di ordinamento generico :: Algoritmo HeapSort


Lezione 20 - QuickSort
Il QuickSort, come il MergeSort, ordina un array in locale con una complessità media O(nlogn); nel caso peggiore però il QuickSort ha complessità O(n2), però viene spesso utilizzato se non si riscontrano particolari inefficienze.

La prima chiamata è QuickSort(A, 1, Length[A])

QuickSort(A, p, r) {
  if(p < r) {
    q = Partition(A, p, r);
    QuickSort(A, p, q-1);
    QuickSort(A, q+1, r);
  }
}

Partition(A, p, r) {
  x = A[r];
  i = p-1;
  for(j = p; j = r-1; j--) {
    if(A[j] <= x) {
      i = i+1;
      Scambia(A, i, j);
    }
  }
  Scambia(A, i+1, r);
  return i+1;
}

L'operazione di partizione (che è l'operazione principale del QuickSort) prende l'ultimo elemento e poi divide l'array di dimensione (n-1) in due insiemi, il primo che contiene tutti gli elementi più piccoli dell'ultimo ed il secondo che contiene tutti gli elementi più grandi dell'ultimo.
Il QuickSort non fa altro che chiamare l'operazione di partizione e poi richiamarsi ricorsivamente sui due insiemi.
Non c'è nessuna operazione di ricombinazione poichè alla fine l'array risulta ordinato.

  - Prestazioni del QuickSort

  CASO PEGGIORE: Nel caso peggiore l'algoritmo ha una complessità di O(n2); il caso peggiore si ha quando un sottoinsieme ha n-1 elementi e l'altro zero elementi. Tale situazione si presenta quando l'array è ordinato in maniera crescente o in maniera decrescente.

  CASO MIGLIORE: Nel caso migliore la chiamata ricorsiva opera su sottoinsiemi, uno di grandezza n/2 e l'altro di grandezza n/2-1, in questo caso:

    T(n) ≤ 2T(n/2) + O(n)

a = 2, b = 2 e k = 1, quindi la complessità è O(nlogn)

  CASO MEDIO: La particolarità del QuickSort è che anche con una partizione sfavorevole, esempio 9 a 1, mantiene proprietà interessanti, esempio per Partition:

    T(n) ≤ T(9n/10) + T(n/10) + cn

  In definitiva la ricorsione termina alla profondità di

    log9/10n ~ O(logn)

  per cui il QuickSort ha complessità O(nlogn) e la avrebbe anche se la partizione fosse 99 a 1.

Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

Quick Sort

L'applet :: Algoritmo di ordinamento generico :: Algoritmo Quick Sort


Lezione 21 - Ordinamento in tempo lineare
Fino ad ora abbiamo visto programmi di ordinamento che hanno come limite inferiore (nlogn), questo perchè, fondamentalmente, questi algoritmi sono comparativi. Introduciamo adesso tre algoritmi non comparativi che fanno l'ordinamento in tempo lineare, il COUNTIG-SORT, il RADIX-SORT e il BUCKET-SORT.

 - CountigSort
Il CountingSort assume che gli n elementi da ordinare siano compresi nell'intervallo da 0 a k, se k ≤ O(n) allora l'algoritmo ha complessità lineare. L'idea di base è quella di determinare, per ogni elemento x, gli elementi minori di x, in modo da piazzare l'elemento x nella sua corretta posizione; per fare ciò servono, oltre all'array A[1...n], due array B[1...n]e C[o...k], il primo per l'output ed il secondo di appoggio.

CountingSort(A, B, k) {
  for(i=0; i<=k; i++) {           //O(k)
    C[i] = 0;
  }
  for(j=1; j<=Length[A]; j++) {   //O(n)
    C[A[j]] = C[A[j]] + 1;
  }
  for(i=1; i==k; i++) {           //O(k)
    C[i] = C[i] + C[i-1];
  }
  for(j=Length[A]; j==1; j--) {   //O(n)
    B[C[A[j]]] = A[j];
    C[A[j]] = C[A[j]]-1;
  }
}                                 //T(n)=O(k+n)

 - RadixSort
Il RadixSort ordina una serie di n numeri a d cifre, ordinando dalla cifra meno significativa. In questo modo in un numero di passi da 1 a d i numeri risultano ordinati.

RadixSort(A, d) {
  for(i=1; i==d; i++) {
    // usa un algoritmo per ordinare l'i-ma cifra
  }
}

La potenza di questo algoritmo sta nello scegliere un algoritmo di ordinamento delle cifre ottimo (es. CountingSort). Di contro questo algortimo non ordina in locale e quindi consuma più memoria degli algoritmi comparativi.

 - BucketSort
Il BucketSort utilizza lo stesso principio del CountingSort, solo che i numeri sono compresi tra [0, 1); anche qui usiamo un'array di liste linkate per generare l'output. L'algoritmo ha, ovviamente, complessità O(n).

BucketSort(A) {
  n = Length[A];
  for(i=1; i==n; i++) {
    INSERT A[i] INTO LIST B[n A[i]];
  }
  for(i=0; i<n; i++) {
    SORT LIST B[i] WITH INSERTION-SORT;
  }
  CONCATENATE THE LIST B[0]...B[n-1] IN ORDER;
}

Ecco qui di seguito un applet java per testare la funzionalità
dell'algoritmo, sono disponibili anche i sorgenti dell'applet.

Radix Sort Bucket Sort

L'applet :: Algoritmo di ordinamento generico :: Algoritmo Radix Sort :: Algoritmo Bucket Sort