Algoritmi - Appunti

Introduzione alla parte algoritmica

La parte algoritmica è l'ex "Strutture dati". Si occupa della definizione di un modello per l'analisi degli algoritmi – ossia la determinazione della velocità di un algoritmo, che sia indipendente dalle specifiche del calcolatore. È uno dei criteri determinanti per la scelta della tipologia di risoluzione di un problema. Si riflette nella domanda: "Analizza questo algoritmo". Per la valutazione vengono effettuate analisi asintotiche.

Ricorsione e strutture dati

Il primo strumento di progettazione è la ricorsione; gli algoritmi vengono progettati ricorsivi. Esistono diversi schemi ricorsivi, alcuni elementari, altri sofisticati. Implementare un algoritmo ricorsivo in un programma può non essere banale ed è importante saper fare debugging. Alcuni problemi hanno una formulazione intrinsecamente ricorsiva e non possono essere risolti diversamente.

Si useranno strutture di dati non lineari. Una lista nodi è una struttura collegata lineare; una lista multiplamente collegata (es. albero) è una struttura collegata non lineare. Fanno parte di questa categoria anche le heap (code con priorità), le tabelle hash, i grafi (generalizzazione degli alberi). Gli algoritmi di base sono invece la ricerca binaria e gli algoritmi di ordinamento.

Uno strumento teorico permette di provare che non esiste algoritmo di ricerca migliore della ricerca binaria, il cui costo è log(n).

Modelli e teoria della calcolabilità

I problemi reali dell'informatica sono al più relativi ai modelli. La base della parte di modelli risiede nella logica matematica e in alcuni formalismi quali la prova di un teorema. Si procederà poi con la teoria dei linguaggi e degli automi di Chomsky. La sua sistematizzazione è valida per i linguaggi informatici. Gli automi sono macchine astratte che simulano il ragionamento, e si prestano alla traduzione in algoritmi. I linguaggi possono essere divisi in livelli da 0 a 3, di cui si approfondirà il 3 e si tratterà parte del 2.

La teoria della calcolabilità determina quanti problemi possono essere risolti da un computer e quanti non possono esserlo. Esistono problemi la cui inesistenza della soluzione è stata anche dimostrata formalmente. I risolvibili sono inferiori in numero. La teoria della complessità determina quanto tempo di calcolo impiega la risoluzione di un algoritmo. Alcuni algoritmi risolvibili richiedono talmente tanto tempo da non essere molto lontani dagli irrisolvibili.

Algoritmi e ricorsione

Costi di un algoritmo

Costi di un algoritmo: tempo (d'esecuzione) e spazio (in memoria). Gli algoritmi ricorsivi non esplicitano lo spazio occupato in memoria; nella valutazione del costo spaziale della ricorsione occorre tener presenti i meccanismi. Il principio alla base del funzionamento della ricorsione è il principio d'induzione. Nel calcolo di tutti i record di attivazione generalmente si considera il passo precedente, senza risalire a monte.

La versione iterativa del calcolo del fattoriale (cfr. file .java, primo metodo) permette un impiego migliore della memoria, eliminando numerose chiamate ricorsive (quindi meno costi). La ricorsione ha una formulazione più compatta e lo spazio occupato in memoria è proporzionalmente calato in costo nel corso degli anni, ma la risorsa tempo ha ancora il valore originariamente attribuitole, pertanto maggiore di quello associato al tempo. Le funzioni di costo vengono calcolate in maniera asintotica.

Schema della ricorsione

Lo schema della ricorsione è lineare. Vengono innanzitutto verificati i casi base, che non utilizzano la ricorsione; la chiamata ricorsiva è unica: possono esistere più tipi di chiamate ricorsive, ma ogni esecuzione del metodo ne dovrà eseguire una sola. L'errore più comune nella definizione di algoritmi ricorsivi è non usare il risultato della precedente chiamata (cfr. file .java, secondo e terzo metodo).

La ricorsione può essere pura o fare side effect. Le specifiche del problema possono richiedere o non richiedere il side effect. Salvo il caso in cui venga richiesto diversamente, è consigliabile ricorrere sempre alla ricorsione pura (in sede d'esame il side effect non richiesto viene penalizzato). In linea generale: il side effect è IL DIAULO! {Ogni riferimento a Matteo Montesi è puramente casuale}

Calcolo ricorsivo di una potenza

Il calcolo ricorsivo di una potenza (cfr. file .java, quarto metodo) ha costo O(n). Asintoticamente, sono n chiamate dello stesso algoritmo. È tuttavia possibile migliorarne il costo (cfr. file .java, quinto metodo). La seconda formulazione ha costo pari a O(log(n)): i valori di n si dimezzano ad ogni chiamata, quindi alla chiamata i corrisponde un valore pari a n/2^i-1. Tale valore sarà 1 per n = 2^i-1, quindi log(n) = log(2^i-1) = i-1. Quindi i = log(n)+1.

Esercizio: valutare il numero di chiamate ricorsive se, nel quinto metodo, si inserisse pow2*pow2 anziché memorizzare in una variabile d'appoggio il risultato.

Esercizio: scrivere un metodo iterativo che calcoli la potenza.

Ricorsione di coda e binaria

Un caso particolare è la ricorsione di coda, in cui la chiamata ricorsiva si verifica come ultimo passo del metodo. Ne sono esempi i primi tre metodi del file .java. La ricorsione di coda è particolarmente facile da tradurre in una formulazione iterativa, senza ricorrere ad alcun extra nella pila di attivazione. Altro caso particolare è la ricorsione binaria, che prevede due chiamate ricorsive per caso non-base. Un esempio è il drawTicks, che disegna le tacche di un righello inglese su schermo (cfr. file .java, metodi dal settimo al decimo). Ad ogni chiamata ricorsiva la massima dimensione del record di attivazione è pari al numero di "rami" della ricorsione, ma lo spazio occupato tiene conto anche delle ramificazioni adiacenti. L'altezza dell'albero è la pila dei recordi di attivazione.

Il primo livello dell'albero è il livello zero, dove ci sono 2⁰ = 1 nodi. Ad ogni livello ci sono 2ⁿ nodi. La somma di nodi dell'albero è Sigma(2ⁱ), ovvero (2^k+1-1)/(2-1) quindi 2^k+1-1. In tal caso k = log(n), quindi 2^log(n)+1-1 = 2*2^log(n)-1 = 2n – 1.

Esempi di implementazione

Factorial

public static int fact(int n) {
    if(n == 0 || n == 1) return 1;
    else return fact(n-1);
}

Linear sum

Input: array of n integers and an integer b >= 1, such that n >= b

Output: sum of the first b integers in the array

public static int linearSum(int[] a, int n) {
    if(n == 1) return a[0];
    else return linearSum(a, n-1) + a[n-1];
}

Reversal

Input: array a and two positive integer index numbers, i and j

Output: a reversed array from i to j

public static int[] reverse(int[] a, int i, int j) {
    if(i >= j) return a;
    else {
        int x = a[i];
        a[j] = a[i];
        a[i] = x;
        return reverse(a, i+1, j-1);
    }
}

Integer power

public static int pow(int n, int exp) {
    if(exp == 0) return 1;
    else return n * pow(n, exp-1);
}

Integer power (optimised)

public static int pow2(int n, int exp) {
    if(exp == 0) return 1;
    if(exp > 0 && n % 2 != 0) {
        int c = pow2(n, (exp-1) / 2);
        return n * c;
    } else {
        int c = pow2(n, exp / 2);
        return n * c;
    }
}

Array inversion (iterative formulation)

public static int[] reverseCyclic(int[] a, int i, int j) {
    if(i == j) return a;
    else {
        while(i < j) {
            int x = a[i];
            a[j] = a[i];
            a[i] = x;
            i++;
            j--;
        }
    }
    return a;
}

Ruler drawer

public static void drawRuler(int inches, int majorLength) {
    drawOneTick(majorLength, 0);
    for(int i = 1; i < inches; i++) {
        drawTicks(majorLength-1);
        drawOneTick(majorLength, i);
    }
}

public static void drawTicks(int tickLength) {
    if(tickLength > 0) {
        drawTicks(tickLength-1);
        drawOneTick(tickLength);
        drawTicks(tickLength-1);
    }
}

public static void drawOneTick(int tickLength) {
    return drawOneTick(tickLength, -1);
}

public static void drawOneTick(int tickLength, int tickLabel) {
    for(int i = 0; i < tickLength; i++)
        System.out.print("-");
    if(tickLabel >= 0) System.out.println(" " + tickLabel);
}

Progettazione ricorsiva e problema dei Fibonacci

La progettazione ricorsiva si basa sull'assunzione che per il caso n sia già pronta la soluzione, che si possa riutilizzare nel caso n+k per qualsiasi k. Uno stesso metodo ricorsivo può essere utilizzato in diversi modi. Una formulazione ricorsiva del calcolo della serie di Fibonacci (cfr. file .java, primo metodo) può avere un costo esponenziale, richiedendo 2^k/2 passaggi. Tale formulazione dell'algoritmo ripete molte volte gli stessi calcoli.

Esercizio: formulare Fibonacci ricorsivamente lasciando l'output a int e aggiungendo parametri in input.

La ricorsione multipla è, fra le altre cose, alla base del bruteforcing: funziona, ma è molto pesante in memoria, soprattutto per grandi quantità di dati da elaborare.

PuzzleSolver

L'algoritmo puzzleSolve(int k, sequence S, domain U) enumera ogni stringa di lunghezza k aggiunte ad S usando senza ripetizioni elementi di U. Tali stringhe vengono poi rimosse da U. Quindi: se la configurazione risolve il rompicapo, si ritorna una stringa; altrimenti, lo si reinserisce in U e lo si rimuove di nuovo dalla coda di S.

Esercizio: progettare un metodo che calcoli tutte le possibili permutazioni di una stringa. Provare ad assegnare numeri ad ogni nodo.

Data una griglia che è una matrice n*n, scegliere una casella iniziale a proprio piacimento dove inserire il numero 1. Inserire poi tutti i numeri seguenti secondo il criterio: se i è nella casella x, il numero successivo può essere solo in una casella distante 2 caselle da essa (in orizzontale, verticale o diagonale). Non si possono sovrascrivere le caselle piene. Trovare tutte le disposizioni possibili per questa formulazione.

In un albero da n+1 livelli ci sono n! nodi per livello. Nelle chiamate ricorsive ciò equivale a n! + (n-1)! + (n-2)! + [...] chiamate ricorsive.

Il tempo di output mediamente cresce proporzionalmente alla dimensione dell'input. Un array, per esempio, ha x*n dati, e dell'x più grande prende il numero di bit e codifica la dimensione massima dell'array sulla base di quel risultato. Valutando il tempo di esecuzione si prende per questo sempre il caso peggiore.

Fibonacci numbers, recursive calculation (base formula)

public static int fib(int k) {
    if(k <= 0) return 0;
    if(k <= 2) return 1;
    return fib(k-1) + fib(k-2);
}

Fibonacci numbers (linear formula)

public static int fibLinear(int k, int cap, int temp1, int temp2) {
    if(k <= 0) {
        if(k != cap) return fibLinear(k+1, cap, 0, 0);
        return 0;
    } else if(k == 1) {
        if(k != cap) return fibLinear(k+1, cap, 0, 1);
        return 1;
    } else if(k == 2) {
        if(k != cap) return fibLinear(k+1, cap, 1, 1);
        return 1;
    } else {
        if(k >= cap) return temp1 + temp2;
        return fibLinear(k+1, cap, temp2, temp1 + temp2);
    }
}

PuzzleSolver

public static Set<String> puzzleSolver(int c, Set<String> out, Set<String> in, Set<String> basic) {
    if(out.size() >= fact(in.length())) return out;
    else if(!in.equals("") && in != null) {}
}

private int fact(int n) {
    for(int i = 1; i < n; i++) n = n * i;
    return n;
}

public static void printSet(Set<String> s) {
    String[] x = s.toArray();
    for(int i = 0; i < x.length; i++)
        System.out.println(x[i]);
}

Costo di un algoritmo

Il tempo di esecuzione, o costo computazionale, è espresso in funzione della dimensione dell'input. A parità di dimensione ci possono essere tempi di esecuzione diversi, distinti in casi medi, casi migliori e casi peggiori. Il caso medio è il valore atteso del costo, ma per quantificarlo occorrerebbe conoscere la distribuzione probabilistica di ciascun caso; per questo, nella valutazione del costo, si tiene sempre presente il caso peggiore (worst case scenario).

Alcuni metodi, anche in Java, permettono di calcolare il tempo di esecuzione di un dato algoritmo tramite la differenza tra il tempo attuale a inizio metodo e il tempo attuale a fine metodo. Tuttavia, per tempi di esecuzione molto brevi, la differenza si approssima a 0. Lo svantaggio di questo metodo è il dover implementare ogni algoritmo che si vuole valutare. Inoltre, non si è mai sicuri di avere effettivamente davanti il caso peggiore, né si può provare ogni configurazione, e la misurazione è relativa al tipo di hardware della macchina di testing. Quindi è chiaro che l'approccio sperimentale non dà garanzie: per questo si ricorre solitamente all'analisi teorica di ciascun algoritmo. La fase di testing risulta utile dopo l'analisi teorica, per provare sperimentalmente i risultati ottenuti per via teorica. Le stime sono valide asintoticamente, quindi sarà impossibile scegliere tra due algoritmi asintoticamente equivalenti.

L'analisi teorica viene condotta solitamente sullo pseudocodice. for(int i = 0; i < a; i++) (c O(a) = O(2^z), come vedremo) è un ciclo che fa a iterazioni. Quindi il suo costo è a, ovvero il numero di bit usati per rappresentare a: a = 2^z; z = log(a). Distinguere tra caso peggiore e caso migliore non dipende dalla dimensione del secondo dato, idem per l'input.

Lo pseudocodice è "universale" e può essere tradotto in qualsiasi linguaggio. È fondamentale specificare se l'algoritmo fa o non fa side effect. La struttura dell'algoritmo deve essere evidente, ma non si richiede stretta osservanza della sintassi. Il modello di computer associato allo pseudocodice è il modello astratto RAM, Random Access Machine, in grado di accedere direttamente a ciascuna casella di memoria per leggerla e modificarla. Ha una CPU, infinite caselle di memoria con indice.

L'algoritmo in pseudocodice illustra una serie di azioni, ossia computazioni fondamentali. Qualunque linguaggio formalizzi l'algoritmo, esso sarà descrivibile. Diverse operazioni hanno costo unitario, ad esempio le chiamate a metodo e i ritorni.

Calcolo del massimo valore

Nello pseudocodice per calcolare il massimo valore delle n celle di un array, il costo dell'assegnazione nel ciclo for è 2n - 2, poiché si ripete n volte e ogni volta fa n assegnazioni. Chiamando a il caso migliore e b il caso peggiore, a <= T(n) <= b che sono entrambe 12x - 4. Quindi è limitato da entrambe le parti da due funzioni lineari! In tal caso possiamo affermare che il costo sia lineare. Il discorso è valido anche per le macchine reali, nonostante non sempre si conosca la pendenza (che comunque non è rilevante, ovvero a livello asintotico x e 10x sono equivalenti).

Date f(n) e g(n), si dice che f(n) è O(g(n)) se esistono c ed n₀ tali che: f(n)<= cg(n) per ogni n >= n₀. In termini semplici, O(f(n)) è definito dal grado del monomio di grado più alto presente nella funzione. Per esempio, se f(x) = x² + 1, O(f(x)) = O(x²), ma anche O(x³) e le potenze successive, ma il grado rilevante è il più alto con coefficiente non nullo. Ad esempio per f(x) = x², O(f(x)) non è O(x) ma O(x²)!

Il "contenuto" della O è detto upper bound (limite superiore) di f(x). In tal caso f(n) cresce al più come g(n), mentre per i lower bound f(n) cresce almeno come g(n). Il lower bound si indica con omega; la crescita equivalente si indica con theta, e indica l'equivalenza asintotica di due funzioni. Le costanti additive e moltiplicative, anche qui, si perdono. Nella scelta delle classi di funzioni per le O(f(n)) si sceglie sempre la più piccola.

Analisi asintotica

L'obiettivo dell'analisi asintotica è la stima della funzione di costo. Lo scopo è di rilevare sia la O(g(n)) che la Omega(g(n)). Non sempre il caso migliore e il caso peggiore hanno lo stesso andamento asintotico. In presenza di una funzione dalla complicata stima, si procede per approssimazioni successive; per esempio, se si sa che una funzione non avrà mai un costo superiore a n³, la si può porre come O(n³). Similmente, se si sa che non impiegherà mai meno di n operazioni, si può porre Omega(n). Il caso peggiore è sempre quello da tenere in considerazione.

Nell'esempio dell'arrayMax, O(n) = Omega(n) e quindi il costo asintotico dell'algoritmo è pari a n. L'ottimizzazione consente nel far sì che O e Omega corrispondano, o quantomeno fornire una stima quanto più possibile precisa di entrambe. Le costanti vengono ignorate, quindi nella valutazione del costo temporale di un algoritmo si considera di solito il numero di esecuzioni di ogni azione ripetuta frequentemente. All'interno della valutazione bisogna considerare anche le chiamate ad altre funzioni o metodi.

Upper e lower bound

Si definisce upper bound di un algoritmo la funzione f(n) di un algoritmo il cui costo di esecuzione è O(f(n)). Ne esiste uno sul tempo e uno sullo spazio. Si definisce lower bound di un algoritmo la funzione f(n) di un algoritmo il cui costo di esecuzione è Omega(f(n)). Ne esiste uno sul tempo e uno sullo spazio. Si definisce upper bound di un problema la funzione f(n) di un algoritmo il cui upper bound è O(f(n)) nel caso peggiore dell'implementazione migliore.

Si definisce lower bound di un problema la funzione f(n) di un algoritmo che consiste nello stimare il lower bound del caso peggiore dell'implementazione migliore, considerando tutte le varianti implementative dell'algoritmo.

Confronto tra algoritmi

Supponiamo di avere tre algoritmi che risolvono lo stesso problema: A1, A2 e A3.