Introduzione agli algoritmi e strutture dati

Con il termine algoritmo si intende un metodo per la soluzione di un problema adatto a essere implementato sotto forma di programma.
Il termine deriva dal nome del matematico persiano Muhammad ibn Mūsa 'l-Khwārizmī. Un algoritmo è un procedimento di azioni specificate per mezzo di regole precise e non ambigue, tali che è possibile eseguire l'algoritmo "automaticamente", cioè applicando le regole senza pensare al significato, oppure direttamente da una macchina.
Vi sono molti modi per descrivere un algoritmo (da quelli più astratti a quelli più particolareggiati). Un problema algoritmico è, invece, costituito da:

• Precondizione: una specifica precisa dei tipi dei dati di partenza (input) e delle condizioni cui essi devono soddisfare.
• Postcondizione: una specifica precisa delle condizioni cui devono soddisfare i dati di arrivo (output), e in particolare della relazione che vi deve essere fra l'input e l'output. Ossia una specifica R(x,y) che definisca qual è, per ogni istanza x dell'input, la risposta o l'insieme delle possibili risposte y che si vogliono ottenere.

Ad esempio:

Problema della ricerca del massimo di una sequenza.

• Dati di partenza :
  • Una sequenza $a_{1},a_{2},...,a_{n}$ di elementi appartenenti ad un dominio D, su cui è definita una relazione d'ordine <= .
  • precondizione: la sequenza deve contenere almeno un elemento.
• Risposta :
  • un elemento appartenente alla sequenza, quindi anche al dominio D.
  • postcondizione: l'elemento restituito R è tale che, per ogni elemento $a_{x}$ della sequenza di input, $R>=a_{x}$ .

L'enunciazione di un problema algoritmico non specifica come ottenere l'output dall'input, ma soltanto come verificare se la risposta è corretta.
Come ottenere l'output dall'input costituisce la soluzione del problema: cioè l'algoritmo. Dunque l'algoritmo è una soluzione di un problema algoritmico. Lo stesso problema può essere risolto da algoritmi diversi, ognuno di questi algoritmi ha una propria efficienza, data in termini di spazio e tempo occupati (vedi lezioni successive). È importante notare che per risolvere un problema è indispensabile conoscere le strutture (o i tipi) di dati che sono presenti, dunque lo studio degli algoritmi è inseparabile dallo studio delle strutture-dati.

L'invariante di ciclo

Quando si scrive un ciclo (un while o un for ad esempio) è importante immaginare cosa succede al passo generico: ossia in un momento qualsiasi del ciclo (spesso è fondamentale considerare il caso particolare, ma è, cronologicamente, l'ultima cosa da fare). Descritta la realtà al passo generico è sempre possibile rintracciare degli invarianti, ossia proprietà delle (o relazione tra) variabili che valgono:

• subito prima venga eseguita l'operazione da iterare
• alla fine di ogni ripetizione del ciclo

In particolare vale alla fine dell'intero ciclo.
Solitamente per ottenere un'invariante (che può anche essere considerato una dettagliata descrizione della memoria) si può indebolire la postcondizione del ciclo.

Ad esempio in un algoritmo per trovare il minimo la postcondizione è : "Il risultato è il minimo dell'intera sequenza". Un modo per ottenere l'invariante, indebolendo la postcondizione, è riformulare la frase in questo modo: "La variabile min è il minimo della sequenza, fino all'indice i escluso". Ovviamente, questo è un esempio banale, ma l'invariante è fondamentale in algoritmi più complicati.

Dalla definizione si può comprendere che l'invariante non è unico: esistono infiniti invarianti (qualsiasi tautologia è un invariante), ma soltanto pochi sono utili per la realizzazione di un ciclo.

È utile, quindi, prima di realizzare un ciclo (o una procedura), cercare l'invariante che faciliti il più possibile la scrittura del codice. È poco sensato (e spesso difficile) cercare un invariante dopo aver scritto il codice.

Un esempio: la ricerca binaria

La ricerca binaria è un algoritmo che risolve il problema della ricerca di un elemento all'interno di una lista ordinata.
Quindi rifacendoci allo schema precedente il problema si può riassumere così:

• Dati di partenza:
  • Una sequenza (eventualmente vuota) $a_{1},a_{2},...,a_{n}$ di elementi appartenenti ad un dominio D, su cui è definita una relazione d'ordine <= .
  • Un elemento d di tale insieme D
  • precondizione: La sequenza deve essere ordinata secondo la relazione precedente, dal valore minimo a quello massimo.
• Risposta:
  • tipo di dato: un valore booleano TRUE o FALSE
  • Postcondizione: il valore di ritorno è vero se e solo se d è presente nella sequenza ordinata.

Questo problema potrebbe risolversi con una banale ricerca sequenziale: si controlla dal primo elemento in poi verificando che è uguale o meno all'elemento d che si sta ricercando. Ma tale procedimento è mediamente molto più lento della ricerca binaria (vedi lezione successiva).

Una descrizione astratta (e quindi imprecisa) della ricerca binaria è la seguente: Si confronta inizialmente l'elemento cercato con l'elemento di metà dell'array (m): se m è maggiore di quello considerato significa che: se d è presente, è nella prima metà dell'array (viceversa se d è più grande). Si prosegue quindi a seconda dei due casi confrontando l'elemento da cercare con l'elemento centrale della porzione-metà e di conseguenzsa ci si restringe a una porzione di lunghezza dimezzata, ecc... La ricerca termina o quando m è uguale a d oppure quando non ci sono più elementi da considerare.

Dalla descrizione appena fatta capiamo che sono necessari almeno due indici per sapere quale parte dell'array stiamo considerando. Ad esempio all'inizio consideriamo l'array nella sua totalità e quindi l'estremo sinistro compreso (sx) sarà 0 (o 1 in linguaggi come Pascal) e l'estremo destro compreso (dx) l'indice dell'ultimo elemento. A questo punto si può recitare l'invariante dell'algoritmo:

se d è presente è compreso tra sx e dx inclusi.

La situazione al passo generico

La situazione nel primo caso

La situazione nel secondo caso

Dopo il primo confronto si presentano 3 possibilità:

1. d è più grande di m.
2. d è più piccolo di m.
3. d è uguale a m. (si pensi ora come trovare m dati sx e dx).

Nel primo caso, come detto, bisogna spostarsi sulla destra, quindi bisogna modificare sx e dx in modo tale da considerare la parte di destra. L'indice destro rimane uguale, quello sinistro invece deve cambiare, in particolare sx diventa uguale a m+1 (non a m, perché m è sicuramente diverso da d). Analogamente nel secondo caso sx rimane invariato e dx cambia valore in m-1. Nel terzo caso abbiamo trovato il valore della risposta, ossia True.

Resta ora solo da capire quando termina il ciclo nel caso in cui d non è presente nell'array. In questo caso, si termina solo quando non c'è più nessun elemento da controllare ossia quando sx e dx sono tali da descrivere una partizione vuota. E ciò avviene non quando sx=dx ma quando sx>dx, ossia bisogna continuare finché sx<=dx.

Detto ciò ne possiamo scrivere una realizzazione in Java:

public static boolean binSearch(int[] array, int d){
     int sx = 0;
     int dx = a.length-1;
     while(sx<=dx){
        int m = (sx+dx)/2; //attenzione! non (dx-sx)/2 
        if (d>a[m]) sx = m+1;
        else if (d<a[m]) dx= m-1;
        else return true;
     }
     return false;
}

Esistono versioni leggermente più raffinate e che ritornano l'indice dove si trova l'elemento, ma tali implementazioni non sono molto più difficili e si lasciano allo studente.

Esiste inoltre una versione ricorsiva, più breve, ma in quanto ricorsiva occupa maggiore spazio in memoria. Di tale versione ne diamo un esempio in C:

int binSearch(int array[], int d, int sx, int dx){
    /*Supponiamo sia stata chiamata per la prima volta con sx=0 a dx=lunghezza dell'array-1*/
    if (sx>dx) return 0;
    int m = (sx+dx)/2;
    if (array[m]==d) return 1;
    return (array[m]>d) ? binSearch(array,d,sx,m-1) : binSearch(array,d,m+1,dx);
}

Senza voler entrare nei dettagli, che saranno presenti nelle prossime lezioni, possiamo analizzare la complessità asintotica temporale dell'algoritmo.

Ad ogni confronto tra d e l'elemento di posizione m la parte da controllare dell'array (di lunghezza iniziale n) si divide per 2, quindi nel caso peggiore il numero di volte che bisogna ripetere il controllo è $\log _{2}{n}$, che è nettamente migliore del caso peggiore della ricerca sequenziale che è n (se l'elemento cercato è l'ultimo nell'array).

Per dare un'idea possiamo pensare di avere un dizionario della lingua italiana (che immaginiamo sia di circa 120000 lemmi) e voler cercare la parola "dicotomia". Seguendo la ricerca sequenziale dovremmo sfogliare circa 30000 lemmi prima di trovare quello giusto, mentre seguendo la ricerca binaria al massimo ne controlleremmo 17.

Quando cerchiamo una parola all'interno del vocabolario, solitamente utilizziamo una ricerca leggermente più efficiente: basandoci sul fatto che le parole sono distribuite (approssimativamente) in modo omogeneo all'interno del vocabolario, se cerchiamo "Verità", apriamo il vocabolario verso la fine e non a metà!