Algoritmi - Programmazione I

Algoritmi di programmazione

Algoritmi di ordinamento

• Algoritmo di ordinamento per inserimento
• Algoritmo di ordinamento per selezione del minimo
• Algoritmo di ordinamento per selezione di massimo
• Algoritmo di fusione

String matching

Algoritmo matching migliore

Ricorsione in C

• Primo esempio: Fattoriale
• Secondo esempio: Algoritmo incrementale di somma dei primi numeri primi n numeri naturali
• Fibonacci

Algoritmo di ricerca

Algoritmo ricerca binaria, versione iterativa e versione ricorsiva

Complessità e memorizzazione

• Complessità di spazio e tempo
• Mappa di memorizzazione

Algoritmo ricorsivo

Somma array, approccio incrementale e approccio divide et impera

Algoritmo di ordinamento per inserimento

Lo scopo è quello di ordinare in senso crescente un array di dati. Per essere possibile questo ordinamento bisogna che ci sia una relazione di ordine tra gli elementi dell'array. Come input abbiamo l'array e il suo size. Come output abbiamo lo stesso array ma ordinato. L'AOINS è basato sull'approccio incrementale al problema dell'ordinamento. Infatti, ad ogni passo risolve un'istanza del problema, ossia ordina una porzione per volta di array. Ad ogni passo risolve il problema di inserire un elemento dell'array nella porzione già ordinata alla sua sinistra, in modo che la lunghezza della porzione ordinata aumenti di 1. Il primo elemento è sempre ordinato (nel caso base infatti, quando abbiamo un array di size 1 è sempre ordinato). Quindi il primo passo è ordinare i primi 2 elementi dell'array. Se l'elemento a sinistra è maggiore allora avviene uno shift a destra dell'elemento maggiore, altrimenti l'elemento da inserire viene inserito a destra dell'elemento minore. La giusta posizione avviene con un procedimento iterativo a ritroso (si controllano quindi gli elementi a sinistra e li si confrontano). La struttura è costituita da un ciclo for per i passi e da un ciclo while innestato per il procedimento a ritroso di individuazione della giusta posizione. L'implementazione è la seguente:

void ord_inser(char array[], int n) {
    int i, j;
    char el_da_ins;
    for (i=1; i<n; i++) { // gestisce i gli n-1 passi dell'algoritmo
        el_da_ins = array[i];
        j = i-1;
        while (j >= 0 && el_da_ins < array[j]) { // processo a ritroso
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = el_da_ins;
    }
}

L'uscita dal ciclo while è determinata dall'aver trovato la giusta posizione e che gli elementi maggiore di el_da_ins sono stati spostati a destra di tale posizione.

Complessità di spazio e tempo

Complessità di spazio: N, poiché lavora in "place".

Complessità di tempo: Dobbiamo considerare sia gli scambi sia i confronti nel caso peggiore. I confronti sono determinati dall'attivazione del ciclo while, che viene attivato n-1 volte poiché il while è interno al for. Il caso peggiore è quando si esce ogni volta dal ciclo while perché j < 0, ovvero quando la giusta posizione è sempre la prima. Il caso peggiore è ossia quando l'array è ordinato in senso decrescente. Al primo passo quindi il confronto ne è uno, al secondo 2, al terzo tre e via dicendo fino ad arrivare ad n-1. Per ottenere il numero totale di confronti bisogna sommare i numeri dei confronti ad ogni passo, cioè (1 + 2 ... (n-2) + (n-1)) ma questo non corrisponde altro che alla somma dei primi numeri naturali che per la formula di Gauss si ha: n*(n-1)/2. Per quanto concerne il numero di scambi, o meglio di shift a destra, basta osservare che si ha uno spostamento ogni volta che è vero il predicato del while, quindi scambi e confronti saranno, nel caso peggiore uguali.

T(n)=n*(n-1)/2= ½(n² – n)= O(n²) confronti/scambi al più.

Il caso migliore è quando l'array è già ordinato, infatti l'AOINS effettua n-1 confronti e 0 scambi/shift. Generalmente si dice che l'AOINS è in grado di accorgersi con (n-1) confronti del fatto che un array sia già ordinato.

Algoritmo di ordinamento per selezione del minimo

Lo scopo è ordinare in senso crescente un array di dati. I dati possono essere numeri, stringhe di caratteri o un qualsiasi altro insieme che abbia una relazione di ordine. L'AOSMIN ha come dati di input un array e il suo size. E come output ha lo stesso array con i dati ordinati. Ad ogni passo (i passi sono n-1 ossia il size meno 1) effettua la ricerca dell'elemento minimo e la sua posizione, tale elemento viene scambiato con l'elemento che si trova al primo posto della porzione che si sta considerando. Al passo successivo si considera una nuova porzione di array, che avrà un numero di elementi diminuito di una unità rispetto alla precedente. E si continua così finché non si ha l'array ordinato. L'implementazione è la seguente:

void ord_sel_min(char array[], int n) {
    int i;
    char min_array;
    for(i=0; i<n-1;i++) { // gestisce i passi da 0 a n-2
        min_val_ind(&array[i], n-i, &min_array, &indice_min);
        scambiare_c(&array[i], &array[indice_min+i]);
    }
}

void min_val_ind(char array[], int n, char *min_array, int *i_min) {
    int i;
    *min_array = array[0];
    *i_min = 0;
    for (i=1; i<n; i++)
        if (array[i] < *min_array) {
            *min_array = array[i];
            *i_min = i;
        }
}

void scambiare_c(int *x, int *y) {
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

Complessità di spazio e tempo

Complessità di spazio: N poiché lavora in "place".

Complessità di tempo: Consideriamo come operazioni dominanti scambi e confronti. Entrambi sono determinati rispettivamente gli scambi da scambiare_c e i confronti da min_val_ind. L'attivazione di scambiare_c avviene ad ogni iterazione del ciclo for ossia da 0 a n-2 elementi (per un totale di n-1 iterazioni). Quindi effettua sempre n-1 scambi, è una complessità assoluta poiché indipendente dal valore degli elementi dell'array. I soli confronti sono determinati da min_val_ind, che è chiamata n-1 volte (una per ogni iterazione del ciclo for). Il size della porzione non è costante ma diminuisce di 1. Alla prima iterazione, la porzione passata alla function min_val_ind coincide con l'intero array e ha lunghezza n, quindi la function effettua n-1 confronti. Alla seconda iterazione, ha la lunghezza diminuita di 1 quindi effettua n-2 confronti e così via fino ad arrivare a un numero di confronti pari a 1. Per ottenere il numero totale di confronti bisogna sommare i numeri dei confronti ad ogni passo, così abbiamo la somma dei primi numeri n