Appunti Ingegneria degli algoritmi

Complessità computazionale

Complessità computazionale è risolvere algoritmo ossia produrre risposta per un problema, una procedura a partire dai dati, che rispecchia le caratteristiche: definitezza; input; output; finitezza; efficacia. È eseguibile in tempo finito: ciascun passo in tempo finito; un algoritmo dà sempre una risposta.

Esempio Binary Search

Binary Search: input una chiave e un array A[1..n], con i e j estremi del sottovettore. Si esegue il controllo sul valore medio per ricorsione, ossia sull'intero vettore. Se il vettore è vuoto ritorna 0, cioè la chiave non è stata trovata; se la chiave è uguale all'elemento medio, ritorna l'elemento medio; se la chiave è maggiore dell'elemento medio, si trova nel sottosettore destro; se la chiave è minore dell'elemento medio, si trova nel sottovettore sinistro.

Procedura: BinarySearch(A, v, i, j). If i > j then Result: 0. Else m ← [(i + j)/2]. If A[m] = v then Result: m. Else if A[m] < v then Result: BinarySearch(A, v, m+1, j). Else Result: BinarySearch(A, v, i, m-1).

Esempio algoritmo di Euclide

Algoritmo di Euclide: indica il massimo divisore comune tra due numeri m ed n. Il MCD è il più grande numero intero che divide entrambi i numeri dati. L'algoritmo funziona perché la quantità dei resti nelle divisioni successive è discendente e all'ultimo passo diventa 0.

Input: interi positivi m e n con m > n. Procedura: Euclide(m, n). While n ≠ 0 do (q, r) ← m/n, quoziente e resto; m ← n; n ← r. Result: m.

Tempi di calcolo

Spesso per il calcolo dei tempi si seleziona un sottoinsieme delle operazioni e si conta, assumendo che tutte richiedono lo stesso tempo di esecuzione. Questa produce solo un'approssimazione di primo ordine.

Esempio: a = 7, b = 5, a = a + b, b = 6, 4, 5, 2, 3, 1, 9. Si tratta di una specifica istanza del problema di calcolare la somma di due vettori di lunghezza particolare, caso del problema sommare due vettori di dimensione n.

Esempio di tempo di calcolo iterativo di min

Tempo iterativo di calcolo di min: l'indice nel for è ripetuto n volte e non n - 1, perché la condizione deve essere verificata una volta in più per poter uscire dal ciclo.

ITEM min(ITEM[], integer n). ITEM min ← A[1], costo c1, 1 volta. For i ← 2 to n do, costo c2, n volte. If A[i] < min then, costo c3, n - 1 volte. Min ← A[i], costo c4, n - 1 volte. Return min, costo c5, 1 volta.

Il tempo T(n) si ottiene sommando il prodotto di ciascuna operazione, cioè costo dell'istruzione per il numero di volte che viene eseguita: T(n) = c1 + c2n + c3(n - 1) + c4(n - 1) + c5 = n(c2 + c3 + c4) + c1 - c3 - c4 + c5. T(n) = an + b nel caso peggiore e anche nel caso medio.

Notazioni asintotiche

Notazioni asintotiche: valutare la complessità computazionale in ordine di numero di operazioni, cioè tendere all'infinito della grandezza n, esprimendo la limitazione della funzione T(n), trascurando costanti additive e moltiplicative.

Notazione asintotica di tempo di esecuzione: per T(n) è Θ(f(n)) se esistono C e C' tali che C f(n) < T(n) < C' f(n), per n > n0. È finita. T(n) è O(f(n)) se esiste C tale che T(n) < C f(n), per n > n0. T(n) è Ω(f(n)) se esiste C tale che T(n) > C f(n), per n > n0. Questa su un grafico è una retta semplice proporzionata.

Nell'esempio precedente venivano sommati vettori, numero di vettori che erano sommati. Quella di somma è il tempo di esecuzione uniforme per un elemento particolare; il tempo totale di esecuzione dipende unicamente dalla dimensione del vettore. Parità del vettore: alcune operazioni potrebbero essere così a volte e non a lunghezza, o richiedere più tempo, e non sarà possibile richiederle in maniera unitaria.

Tempi di esecuzione e casi

Tempi di esecuzione: cosa succede se la dimensione sua non determina completamente il tempo di esecuzione? Risposta: si considerano tutti i casi.

• Worse case: T(n) è possibile per qualunque input di dimensione n, O(n).
• Average case: T(n) è la media su tutti gli input possibili di dimensione n.
• Best case: valore di T(n) viene raggiunto per alcuni degli input di dimensione n; questo algoritmo è molto efficiente, ovvero viene rallentato solo per alcuni valori.

Nell'esempio precedente dell'algoritmo di somma per due vettori possiamo assumere che per dimensione n il caso peggiore e il caso medio coincidano. Lo scopo è far avvicinare il tempo di esecuzione del nostro programma per tutti i casi.

Complessità comuni

• O(1): algoritmo che richiede tempo costante.
• O(log n): algoritmo logaritmico.
• O(n): algoritmo lineare.
• O(n^k): algoritmo polinomiale, con grado n, minore preferito.
• O(aⁿ): algoritmo esponenziale, lento, da evitare, interminabile.

Complessità di un algoritmo = metodo di soluzione di un particolare problema. Complessità del problema: complessità del miglior algoritmo che risolve quel problema.

Avvertenze

Avvertenze: alcuni algoritmi ottimi sono efficaci solo per dimensioni astronomiche, quindi inutili in pratica; il tempo di sviluppo del programma diventa importante se verrà usato una sola volta; può essere giusta la scelta di un algoritmo semplice. In alcuni casi l'algoritmo più veloce ha costo di memoria eccessivo. Un algoritmo può essere migliore nel caso medio e lo stesso algoritmo peggiore nel caso peggiore.

Costo computazionale

Costo computazionale: valutare il costo di un algoritmo. Le espressioni scalari hanno costo O(1). Il costo di una sequenza di istruzioni è dato dalla somma dei costi delle singole istruzioni. Il costo di un ciclo è la somma dei costi delle singole istruzioni. Un'istruzione condizionale ha costo nel caso peggiore massimo tra i costi del ramo if e del ramo else. Per stimare il costo medio occorre valutare il costo di ciascun ramo e la probabilità della condizione.

Esempio: 52 assignments. Often cost of := is ignored. b = a + 2; floating point operations. Have point operations: 1. b = b * c; floating point operations: 2. For this is executed K times, n = n + 1; independent. Cost b c @ K = + endif. If Integer Mod 2 is random with probability 50%, K == 0. Branch IF worse cost is C + 2b; average case costs 1.5 plus cost of evaluating MOD. For ciclo: bisogna calcolare i dati; i è un'iterazione; L è l'insieme di tutte le iterazioni; i-esima iterazione; il costo dell'i-esima iterazione. Spesso è facile trovare il costo costante per i cicli for, ma non per while; cicli innestati corrispondono a somme multiple.

Complessità notevoli

• Prodotto scalare di due vettori di dimensione n: 2n.
• Somma scalata di due vettori di dimensione n: 2n.
• Prodotto matrice vettore: 2mn.
• Prodotto matrice matrice: 2mnK.

Insertion sorting

Insertion Sort: insertion sort in un vettore int A[], int n. For ciclo per scorrere vettore elemento per elemento, j = 2 to n. Elemento Clem appoggio per salvare elemento da inserire con assegnazione per una variabile. Indice i = j - 1 per effettuare confronti. While è il ciclo per accettare i confronti e per capire quello più piccolo; condizioni condizionali quando si trova un elemento più piccolo nel vettore. A[i + 1] = A[i], shift per fare spazio nella posizione successiva. I = i - 1, porto indietro l'indice dei confronti. A[i + 1] = Clem, inserisco nello spazio corretto l'elemento che sto esaminando.

Best case: la sequenza è già ordinata, tempo di esecuzione lineare D(n). Worst case: la sequenza è ordinata al contrario, tempo di esecuzione n². Average case: D(n²). Impraticabile per ordinare grandi sequenze.

Equazioni di ricorrenza e ricerca binaria

Equazioni di ricorrenza dell'algoritmo di ricerca binaria. RicercaBinario V Ric(se, lunghezza n). If n == 0 return -1. i = n/2. If V[i] == se return i. Else if V[i] > se return RicercaBinario(V, se, i - 1). Else return RicercaBinario(V, se, n - i - 1).

Calcolando la complessità computazionale: T(0) = O(1); T(n) = T(n/2) + O(1). Il costo ricorsivo è il costo speso all'interno della funzione chiamata. Metodo iterazione: si srotola la ricorsione, ottenendo una sommatoria dipendente dalla sola dimensione n.

T(n) = O(1) se n = 0; T(n) = T(n/2) + O(1). Se T(n/2) = T(n/4) + O(1), allora T(n) = T(n/4) + O(1) + O(1), e così fino a T(1). T(n) = O(log n). Mi fermo quando n/2^k = 1, quindi n = 2^k, k = log₂ n.

Esempio 2: T(n) = T(n/2) + n - 1 se n > 1; T(1) = 1. T(n) = T(n/2) + n. T(n/2) = T(n/4) + n/2; T(n/4) = T(n/8) + n/4; la somma è n + n/2 + n/4 + ... + 1. Mi fermo quando n/2^k = 1, quindi k = log₂ n. Sapendo che la somma geometrica è n + n/2 + n/4 + ... + 1 = 2n - 1, T(n) = O(n).

Metodo della sostituzione

Metodo della sostituzione per ricerca lineare ricorsiva: dato l'input, si vuole ricercare un elemento in un vettore V e tornare la posizione dell'elemento se presente. Ricorsivamente si può scrivere la funzione cercando di volta in volta, considerando una unità di lunghezza più piccola ad ogni chiamata ricorsiva. Si esegue il confronto con l'ultimo elemento del vettore.

RicRicercalineare(V, POS, se). If POS < 0 return -1; non ho trovato l'elemento nel vettore. If V[POS] == se return POS. Return RicercaRiclineare(V, POS - 1, se).

Equazione di ricorrenza per algoritmo di ricerca ricorsiva lineare: T(n) = O(1) se n = 1; T(n) = T(n - 1) + O(1) se n > 1.

Il metodo della sostituzione ha come idea quella di intuire la soluzione di una ricorrenza e dimostrare per induzione matematica che la soluzione intuita è effettivamente quella. Riscrivo la notazione asintotica senza usare T(n): T(n) = a se n = 1; T(n) = T(n - 1) + c se n > 1.

Dobbiamo dimostrare che T(n) <= Kn, ovvero che T(n) = O(n). Caso base n = 1: vero, perché a <= K. Passo induttivo: ipotesi induttiva vera per n - 1. Devo dimostrare che T(n) <= Kn. Per T(n) = T(n - 1) + c <= K(n - 1) + c = Kn - K + c. Se K >= c, allora T(n) <= Kn. Quindi T(n) = O(n).

Esempio 2: T(n) = T(n/2) + n se n > 1; T(1) = 1. Ipotizzo che T(n) = O(n), cioè T(n) <= cn. Caso base n = 1: 1 <= c. Passo induttivo: ipotizzo che sia vero per n/2; T(n) = T(n/2) + n <= c(n/2) + n. Devo scegliere c tale che c(n/2) + n <= cn, quindi n <= cn/2, dunque c >= 2.