Algoritmi - Programmazione I

Complessità di tempo

Consideriamo come operazioni dominanti gli scambi e i confronti. Entrambi sono determinati rispettivamente dagli scambi da effettuare (scambiare_c) e dai confronti per trovare il valore minimo (min_val_ind).

L'attivazione della funzione 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, ed è una complessità assoluta poiché indipendente dal valore degli elementi dell'array.

I soli confronti sono determinati dalla funzione min_val_ind, che viene chiamata n-1 volte (una per ogni iterazione del ciclo for). Il size della porzione non è costante ma diminuisce di 1 ad ogni iterazione. Alla prima iterazione, la porzione passata alla funzione min_val_ind coincide con l'intero array e ha lunghezza n, quindi la funzione 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 ad 1.

Per ottenere il numero totale di confronti, dobbiamo sommare il numero di confronti effettuati ad ogni iterazione. Possiamo notare che il numero di confronti effettuati ad ogni iterazione è dato dalla somma dei numeri da 1 a n-1, che è uguale a (n-1)(n-2)/2. Quindi il numero totale di confronti è (n-1)(n-2)/2.

di confronti bisogna sommare inumeri dei confronti ad ogni passo, così abbiamo la sommadei primi numeri naturali che per la formula di Gauss è:n*(n-1)/2- T(n)= n*(n-1)/2 = ½(n^2 – n) = O(n^2) confronti- T(n)= n = O(n) scambi- Poiché non dipende dal valore dei dati, l’AOSMIN assume lostesso costo anche nel caso in cui l’array sia ordinato, quindinon si accorge di essere ordinato

Algoritmo di ordinamento per selezione di massimo- Lo scopo è ordinare un array di dati in modo crescente- Come input abbiamo un array e il suo size- Come output abbiamo l’array ordinato- L’algoritmo effettua n-1 passi per ordinare l’array- Ad ogni passo l’algoritmo risolve il sottoproblema dellaricerca del massimo e del suo indice- Una volta trovato il massimo e il suo indice lo scambia conl’elemento n-1- Alla seconda iterazione avremo l’array ma con indicediminuito quindi il prossimo massimo che troveremo lotroveremo su

una nuova porzione di array e lo scambieremo con l'elemento alla posizione n-2 e così dicendo fino all'elemento di indice 0- L'implementazione è la seguente:

void ord_sel_max(char array[], int n){
    int i, indice_max;
    char array_max;
    for (i=n-1; i>0; i++){
        max_val_ind(&array[0], i+1, &max_array, &indice_max);
        scambiare_c(&array[i], &array[indice_max]);
    }
}

void max_val_ind(char a[], int n, char *max_array, int *i_max){
    int i;
    *max_array = a[0];
    *i_max = 0;
    for (i-1; i<n; i++)
        if(a[i] > *max_array){
            *max_array = a[i];
            *i_max = I;
        }
}

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

Complessità di spazio: n poiché lavora in place

Complessità di tempo: Determinata da scambi e confronti (le operazioni dominanti) Gli scambi sono determinati dalla funzione scambiare_c L'attivazione di scambiare_c viene fatta per ogni iterazione (n-1) La complessità è assoluta poiché non dipende

Dagli elementi- Invece i confronti sono determinati da max_val_ind la cui attivazione avviene per attivazione del ciclo for. Alla prima iterazione avremo n-1 confronti, alla seconda n-2 (poiché la porzione è diminuita) fino ad arrivare ad uno- Per avere il numero dei confronti dobbiamo sommare i confronti di ogni passo ossia (n-1)+(n-2)…(1)- Sappiamo che questa è la somma di primi numeri naturali e quindi per la formula di Gauss abbiamo: n*(n-1)/2- T(n)=n*(n-1)/2 = ½ *(n^2 -n) = O(n^2) confronti- T(n) = n =O(n) scambi- Possiamo dire che non si accorge di essere ordinato poiché non dipende dagli elementi (complessità assoluta)

Algoritmo di fusione- Risolve il problema della fusione- Funziona solo su due array ordinati di dati- Ha come input due array che chiamiamo A e B e i loro size n_a e n_b- Ha come output un array che chiamiamo C, il cui size è la somma= n_a+ n_b- L'AFUS è basato sull'effettuare n_a+n_b passi- Ad

Ogni passo si determina un elemento dell'array C, quindi in generico passo i_C (che sarebbe l'indice di C) lo scopo è determinare l'elemento di C indice i_C.

Indichiamo i_A e i_B (sono gli indici di A e B rispettivamente) e al primo passo i_A e i_B indicano il primo elemento dei rispettivi array.

Al passo i_C sono possibili 3 scenari:

1. Quello normale, cioè c'è almeno un elemento di A e un elemento di B da considerare, ovvero ancora non inseriti nell'array C. Gli indici i_A e i_B indicano l'elemento di A e l'elemento di B che devono essere considerati al fine di determinare quale deve essere inserito in C. Il più piccolo tra A(i_A) e B(i_B) è inserito in C nella posizione i_C (nel caso siano uguali se ne inserisce uno qualunque).
2. Secondo caso in cui tutti gli elementi di A sono inseriti in C (quindi bisogna inserire quelli di B e i_b deve essere incrementato).
3. Terzo caso in cui gli elementi di B sono inseriti in C.

C(quindibisogna inserire quelli di A e i_a deve essereincrementato)- Quella seguente è l’implementazione in C dell’AFUS:


void fusioneC(char a[], int n_a, char b[], int n_b, char c[]){
    int i_a=0, i_b=0, i_c;
    for(i_c=0; i_c< n_a+n_b; i_c++){
        if(i_a<n_a && i_b<n_b) //primo caso
        {
            if (a[i_a] < b[i_b]){
                c[i_c] = a[i_a];
                i_a++;
            }else {
                c[i_c] = b[i_b];
                i_b++;
            }
        }else if (i_b>=n_b){ //secondo caso
            c[i_c] = a[i_a];
            i_a++;
        }else { //terzo caso
            c[i_c] = b[i_b];
            i_b++;
        }
    }
}


Implementazione con il while:


void fusioneC(char a[], int i_a, char b[], int i_b, char c[]){
    int i_a=0, i_b=0, i_c;
    while (i_a < n_a && i_b < n_b){
        if (a[i_a] < b[i_b])
            c[i_c++] = a[i_a++];
        else
            c[i_c++] = b[i_b++];
    }
    while (i_a < n_a)
        c[i_c++] = a[i_a++];
    while (i_b < n_b)
        c[i_c++] = b[i_b++];
}


Complessità di spazio:

- Se chiamiamo n dimensione computazionale (n= n_a+n_b) del problema allora la complessità di spazio è 2n, poiché l’array costruisce un terzo array

di size n. Complessità di tempo:

• L'AFUS effettua n = n_a+n_b passi
• Nel primo scenario fare 1 confronto per determinare 1 elemento di C
• Se si è nello scenario 2 o 3 non bisogna effettuarne
• Quindi la complessità di tempo è determinata da n che è ancora la complessità computazionale
• n = n_a+n_b
• T(n)=T(n_a+n_b)= n = O(n) confronti al più

String Matching

Lo scopo è di risolvere il problema del matching, ovvero l'individualizzazione di una stringa chiave in una stringa testo

Ha come input la stringa chiave, la stringa testo

Ha come output il numero di occorrenze (ossia le volte in cui la stringa chiave compare nella stringa testo)

Ha come base l'idea di effettuare tanti passi quando la lunghezza della stringa testo, o meglio della stringa testo meno la lunghezza di quella chiave, così da evitare confronti inutili nelle iterazioni finali

L'implementazione è la seguente:

int string_matching (char chiave[],

char testo[]){int m, n, i, conta_chiave;
n = strlen(chiave); //determinazione della lunghezza
m = strlen(testo); //determinazione della lunghezza
conta_chiave = 0;
for(i=0; i <= m-n; i++)
if(strncmp(chiave, &testo[i], n) == 0) //utilizzo strncmp per
confrontarle, se esce 0 trova una compatibilità, un numero
negativo se la prima precede la seconda in ordine alfabetico e
positivo se la seconda precede la prima in ordine alfabetico
conta_chiave++;
return conta_chiave;}
Complessità di spazio:
- La dimensione computazionale è individuata dalle quantità
m e n, rispettivamente la lunghezza della stringa testo e
della stringa chiave. La complessità sarà n+m poiché lavora
in “place”
Complessità di tempo:
- L’operazione dominante è il confronto che è determinato da
strncmp. Il numero di confronti per ogni chiamata è la
lunghezza n delle sottostringhe in input. La function strncmp
è chiamata una sola volta

Per ogni passo del ciclo for, che effettua (m-n+1) passi. Quindi al più avremo (m-n+1)n confronti. T(m, n) = (m - n + 1)*n = O(m*n)

Algoritmo matching migliore. La funzione matching migliore implementa l'algoritmo di best matching che risolve il problema di determinare la sottostringa di una stringa che ha più caratteri in comune con una stringa chiave.

int matching_migliore(char *chiave, char *testo){
    int i, n, m, punteggio_max, punteggio, indice=0;
    n = strlen(chiave);
    m = strlen(testo);
    punteggio_max = 0;
    for(i=0; i<m-n; i++){
        punteggio = punteggio_matching(chiave, &testo[i],n);
        if (punteggio > punteggio_max){
            punteggio_max = punteggio ;
            indice = i;
        }
    }
    return indice;
}

int punteggio_matching(char *a, char *b, int n){
    int i, n_caratteri_uguali;
    for (i=0; i<n; i++)
        if(a[i] == b[i])
            n_caratteri_uguali++;
    return n_caratteri_uguali;
}

Ricorsione in C. In C, le funzioni possono essere usate in modo ricorsivo; cioè una funzione può richiamare se stessa direttamente.

oindirettamente.- Permette così di avere una soluzione elegante senzal’utilizzo di cicli.- Un programma ricorsivo richiede una quantità di memoria inpiù perché è necessario memorizzare uno stack di valori daprocessare relativi alle autoattivazioni finché non si arrivaall’istanza banale e quindi alla ricostruzione della soluzionefinale.

Primo esempio: Fattoriale- Dato un numero intero n il fattoriale è calcolato come n=n*(n-1)*(n-2)….*1- La funzione è:

int fattoriale(int n){
    if(n <=1)
        return 1; /*soluzione caso base*/
    else
        return n* fattoriale(n-1); /*autoattivazione*/
}

Secondo Esempio: Algoritmo incrementale di somma dei primi numeri primin numeri naturali

int somma_ric(int n){
    if(n <= 1)
        return 1;
    else
        return n+somma_ric(n-1);
}

Terzo esempio: Ricerca del massimoint massimo_a_ricAI(int a[], int n){ if(n==1) return a[0]; else return max_I(a[n-1], massimo_a_ricAI(a, n-1)); }

- Lo stesso problema può essere risolto da

Una funzione ricorsiva basata sull'approccio divide et impera:

int massimo_a_ricDI(int a[], int n) {
    int max;
    
    // Caso base: se l'array ha un solo elemento, restituisce quel valore
    if (n == 1) {
        return a[0];
    }
    
    // Altrimenti, divide l'array in due parti
    int mid = n / 2;
    
    // Richiama la funzione ricorsivamente sulla prima metà dell'array
    int max1 = massimo_a_ricDI(a, mid);
    
    // Richiama la funzione ricorsivamente sulla seconda metà dell'array
    int max2 = massimo_a_ricDI(a + mid, n - mid);
    
    // Confronta i massimi delle due metà e restituisce il massimo tra di essi
    if (max1 > max2) {
        max = max1;
    } else {
        max = max2;
    }
    
    return max;
}