Riassunto Algoritmi e strutture dati

Definizione di problema

Dato un problema P e un insieme X di possibili input di P e un insieme Y di possibili output P, P è una funzione che associa ad ogni elemento x ∈ X un elemento y ∈ Y → y=P(x).

Definizione di algoritmo risolutore

Dato un algoritmo A e un problema P, con P: x→y. Si dice che A è un algoritmo risolutore di P se per ogni x ∈ X, l’esecuzione di A(x) restituisce un elemento y ∈ Y tale che y=P(x) dopo un numero finito di passi.

(2) Dato un problema P: I → O {I = insieme dei possibili input, O = insieme dei possibili ∀output}, un algoritmo è risolutore di P se i ∈ I A(i)=P(i).

(3) Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi, chiari e non ambigui.

Definizione di algoritmo ottimale

Dato un problema P avente complessità intrinseca (g(n)), un algoritmo A risolutore di P si dice ottimale per P se A ha complessità O(g(n)) nel caso peggiore.

Criteri di costo

Costo uniforme
Considero ciascuna operazione avente costo unitario, senza considerare la dimensione dell’input.

Costo logaritmico
In questo modello per ciascuna operazione si paga un costo pari a log n, dove n è la dimensione dell’input.

Notazioni di complessità

O-grande, Ω, Theta

Caso peggiore, caso migliore e caso medio

Il concetto è quello di analizzare il tempo di esecuzione di un algoritmo a parità di dimensione di input. Sia T(x) il costo di esecuzione di A su x e con |x| la dimensione di X.

T_{a worst}(n) = max ({T_a(x) | x ∈ I^|x| =n}) (caso peggiore)
T_{a best}(n) = min (T_a(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 T_{a avg}(n) = somm T_a(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: T_a(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 per 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 con:

• Un insieme c di candidati possibili (insieme di possibili algoritmi risolutori).
• Insieme dei candidati che sono stati enunciati, tra cui si distinguono quali sono stati scartati e quelli che sono stati selezionati per far parte di una soluzione parziale S.
• Una funzione ammissibile che verifica se un insieme di candidati fornisce una soluzione anche non ottima al problema.
• Una funzione ottimo che verifica se c fornisce una soluzione ottima.
• Una funzione seleziona per estrarre un elemento dall’insieme dei candidati possibili non ancora scelti.
• Una funzione obiettivo che fornisce il valore di una soluzione.

Per risolvere il problema è necessario trovare un insieme di candidati che sia soluzione e ottimizzi il valore della funzione obiettivo.

Algoritmi di ordinamento con divide et impera

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);
}

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];
}

Complessità 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, sup = 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;
        }
    }
}