Riassunto Algoritmi e strutture dati

Complessità e analisi ammortizzata

Ata worst(n) = max ({Ta(x) | x € I^|x| =n}) (caso peggiore)
Ta best (n)= min (Ta(x) | x € I^|x| =n}) (caso migliore)
Se si considera la distribuzione di probabilità che le istanze siano effettivamente date in input all’algoritmo (Pr(x)) allora si può definire Ta avg(n)= somm Ta(x) x Pr(x) (caso medio)

Definizione complessità intrinseca
Dato un problema P e una funzione g , si dice che P ha complessità intrinseca Ω(g) se tutti gli algoritmi risolutori di P hanno complessità Ω(g). In altre parole, in qualsiasi modo si risolva il problema, meno di Ω(g) non si può andare.

Tecnica dell’avversario
Questa tecnica consiste nel supporre che un dato algoritmo, che risolve un dato problema a un certo costo, possa essere battuto, cioè dando in input dei dati d’ingresso fatti appositamente per mettere in crisi l’algoritmo.

Analisi ammortizzata
L’analisi ammortizzata studia le prestazioni medie di una

Sequenza di operazioni su una collezione di dati, piuttosto che su una singola esecuzione. Per caratterizzare le prestazioni in media di un algoritmo, si parla di costo ammortizzato che è definito come: Ta(n)= T(n,k) = tempo totale richiesto dall'algoritmo nel caso peggiore per tutte le k operazioni su un input di dimensione n. k = numero di operazioni fatte da una sequenza di un algoritmo

Divide et Impera

Il principio su cui si basa la tecnica divide-et-impera consiste nel dividere i dati in ingresso in due o più sottoinsiemi (DIVIDE), risolvere ricorsivamente i sotto problemi e poi ricombinare le soluzioni dei sotto problemi e ottenere la soluzione globale del problema originario (IMPERA).

Tecnica golosa

Questa tecnica viene utilizzata per risolvere problemi di ottimizzazione, ovvero problemi per cui è necessario trovare la migliore soluzione possibile.

Nella situazione generale avremo a che fare:

• un insieme c di candidati possibili (insieme di possibili

Il problema consiste nel trovare un insieme di candidati che rappresentano una soluzione, ottimizzando il valore della funzione obiettivo. Per fare ciò, vengono utilizzati algoritmi di ordinamento con divide et impera.

Di seguito è riportato il metodo principale che richiama il mergeSort:

public static void mergeSort(int[] v){
    if (v != null)
        mergeSort(v, 0, v.length-1);
}

private static void mergeSort(int[] v, int in, int fin) {
    if (fin <= in)
        return;
    
    int med = (in + fin) / 2;
    mergeSort(v, in, med);
    mergeSort(v, med+1, fin);
    merge(v, in, med, fin);
}

Le funzioni ammissibile e ottimo verificano se un insieme di candidati fornisce una soluzione non ottima o ottima al problema, rispettivamente.

La funzione seleziona viene utilizzata per estrarre un elemento dall'insieme dei candidati possibili, che non è ancora stato selezionato per far parte di una soluzione parziale.

Infine, la funzione obiettivo restituisce il valore di una soluzione.

med+1,fin);
merge(v,in,med,fin);
}

//mergeSort
private static void merge(int[] v, int in, int med, int fin) {
    int[] stage = new int[fin-in+1];
    int i=in,j=med+1, st=0;
    while((i<=med)&(j<=fin)){
        if(v[i]<v[j])
            stage[st++]=v[i++];
        else 
            stage[st++]=v[j++];
    }
    for(;i<=med;i++)
        stage[st++]=v[i];
    for(;j<=fin;j++)
        stage[st++]=v[j];
    for(int k=0; k<stage.length;k++)
        v[in+k]=stage[k];
}

//mergeComplessità spaziale
Ad ogni chiamata alloco una memoria pari allo spazio di allocazione di n/2 elementi.
S(n)= s(n/2) + b(merge)
S(1)= b
Quindi la complessità sarà O(log n +n)

//Complessità temporale
O(n log n) in tutti i casi

//Quick sort
private static void quickSortOriginale( int [] v , int in , int fin ) {
    if(fin<=in)
        return;
    partiziona(v,in,fin);
    int p=quickSortOriginale(v,in,p-1);
    quickSortOriginale(v,p+1,fin);
}

private static int partiziona(int[] v, int in, int fin) {
    Math.floor(Math.random()*(fin-in+1));
    int rnd = (int)int tmp = v[in]; 
    v[in]= v[rnd]; 
    v[rnd]= tmp;
    int p=in;
    int inf=in+1,

^fin; while(inf<sup){ for(;(inf<=fin)&&(v[inf]<v[p]); inf++); for(;(sup>=in)&&(v[p]<=v[sup]);sup--); if(inf<sup){ int t = v[inf]; v[inf]= v[sup]; v[sup]= t; } } int t = v[p]; v[p] = v[inf-1]; v[inf-1] = t; return inf-1;}

Complessità Temporale nel caso migliore O(n log n)²

Temporale nel caso peggiore O(n ) (quando prendo come pivot il min o il max oppure quando il vet è ordinato in modo decrescente)

Temporale caso medio O(n log n)

Spaziale in tutti i casi O(n)

Ricerca binaria

public static int ricercaBinariaRic(int[] v, int x) { ricercaBinariaRic(v,x,0,v.length-1); return; } private static int ricercaBinariaRic(int[] v, int x, int inf, int sup) { if(sup>inf) return -1; int med = (inf+sup)/2; if (v[med]==x) return med; if (v[med]>x) ricercaBinariaRic(v,x,inf,med-1); return else ricercaBinariaRic(v,x,med+1,sup); return; }

Complessità Temporale caso migliore O(1)

Temporale caso peggiore O(log n)

Spaziale caso migliore O(1)

Spaziale caso peggiore O(log

n) Alberi

Gli alberi sono utili per i fini di ricerca in quanto hanno complessità logaritmica. Ci sono alberi i cui nodi possono avere un numero limitato di figli.

Visita anticipata: radice -> sottoalbero sinistro -> sottoalbero destro

Visita posticipata: sottoalbero sinistro -> sottoalbero destro -> radice

Entrambe hanno costo temporale: O(n) poiché faccio al più una chiamata per ogni nodo. Ω(n) perché faccio almeno una chiamata per ogni nodo. Quindi Theta(n).

Lo spaziale è uguale al numero di chiamate sospese + quelle attive.

Da ciò consegue che la complessità è pari all'altezza. L'altezza coincide con il maggior numero di chiamate ricorsive. Molto importante: alberi con lo stesso numero di nodi possono avere altezze diverse.

In un albero degenere il numero di nodi è uguale all'altezza.

Visita per livelli: si visita prima la radice (livello 0), poi i figli (livello 1) e così via.

Complessità

quella del padre- ogni nodo ha al massimo due figli BST (Binary Search Tree) Un BST è un tipo di ABR in cui ogni nodo ha al massimo due figli e la chiave di ogni nodo è maggiore di tutte le chiavi dei nodi nel suo sottoalbero sinistro e minore di tutte le chiavi dei nodi nel suo sottoalbero destro. Heap Un heap è un albero binario completo in cui il valore di ogni nodo è maggiore o uguale al valore dei suoi figli (nel caso di un max-heap) o minore o uguale (nel caso di un min-heap). AVL (Adelson-Velskii e Landis) Un AVL è un tipo di ABR bilanciato in cui la differenza di altezza tra il sottoalbero sinistro e il sottoalbero destro di ogni nodo è al massimo 1. RB (Red-Black) Un RB è un tipo di ABR bilanciato in cui ogni nodo è colorato di rosso o nero e soddisfa le seguenti proprietà: - Ogni nodo è rosso o nero - La radice è nera - Tutte le foglie (NIL) sono nere - Se un nodo è rosso, entrambi i suoi figli sono neri - Per ogni nodo, tutti i cammini che conducono alle foglie contengono lo stesso numero di nodi neri.

quella del padre

Permette di effettuare in maniera efficiente operazioni come: ricerca, inserimento e cancellazione O(n)

Tutte le visite hanno costo Theta(n)

Visita preordine: si visita prima la radice, poi ricorsivamente il figlio SX e DX

Visita simmetrica: prima sotto albero SX, poi la radice, poi il DX.

Visita post-ordine: prima sotto albero SX , poi il DX , poi la radice.

Albero AVL

Nel caso peggiore l'altezza di un ABR può essere proporzionale al numero di nodi (degenere). Se fosse bilanciato avrebbe altezza logaritmica, migliorandone l'efficienza.

Per questo motivo vengono usati gli alberi AVL.

Un albero è bilanciato se le altezze dei sotto alberi sx e dx di ogni nodo differiscono al più di una unità.

Fattore di bilanciamento: Il fattore di bilanciamento di un nodo è la differenza tra l'altezza del sotto albero sx e quella del dx.

Per mantenere il bilanciamento di un albero AVL si operano delle rotazioni a seguito di operazioni di inserimento

O cancellazione. Un albero si dice bilanciato in altezza se ogni nodo ha fattore di bilanciamento in valore assoluto <=1. Le operazioni di rotazione vengono effettuate sui nodi il cui fattore di bilanciamento è in valore assoluto >=2.

Rotazione sinistra-sinistra: Quando un nodo a coefficiente di bilanciamento +2 e il figlio dx ha coefficiente pari a 0 o +1.

Rotazione destra-sinistra: Quando un nodo ha coefficiente -2 e il figlio sx ha coefficiente pari a -1 o 0.

Tabelle Hash. Sono strutture dati realizzate mediante vettore che permettono nel caso medio di eseguire operazioni in tempo costante.

Fattore di carico: Il fattore di carico di una tabella Hash è definito come n/m, dove n= elementi memorizzati, m= dimensione struttura dati.

Funzione Hash. Una funzione hash è una funzione h:U -> {0…m-1} che trasforma chiavi in indici di tabella. Una funzione hash è perfetta se è iniettiva (per ogni chiave è associato un solo indice). Se una funzione hash non è

uguale a quella dei propri figli- L'elemento radice dell'Heap è il minimo (o il massimo nel caso di max-Heap) degli elementi presenti nell'Heap- L'operazione di inserimento di un elemento nell'Heap viene chiamata "heapify up"- L'operazione di estrazione del minimo (o del massimo) dall'Heap viene chiamata "heapify down"Per implementare un Heap si utilizza un array, dove l'elemento in posizione i ha come figli gli elementi in posizione 2i e 2i+1.

uguale a quella dei propri figli.

Un Heap viene realizzato utilizzando un vettore. Per un generico nodo in posizione i si ha:

• padre in [i/2]
• figlio sx in [i*2]
• figlio dx in [i*2+1]

Un Heap con n nodi ha altezza log n

Una coda con priorità è un tipo di dato che permette di mantenere il minimo (o il massimo) in un insieme di chiavi in cui è definita una relazione d’ordine totale.