Appunti di Ingegneria degli Algoritmi

Appunti di ingegneria degli algoritmi

Cavallari Gianmarco

Docente: Filippone Salvatore - Anno 2021/2022

Nota

Questo documento contiene collegamenti web a risorse ed appunti su siti esterni. In caso di malfunzionamento dei collegamenti, inviare una segnalazione scansionando il codice QR, includendo nel messaggio il link in questione. In caso di problemi di visualizzazione o refusi, segnalare tramite QR. Dopo la correzione riceverete una copia PDF aggiornata.

Indice dei contenuti

• Sezione 1: Complessità computazionale......................................................................3
• Sezione 2: Strutture di dati................................................................................................12
• Sezione 4: Strutture ad albero........................................................................................16
• Sezione 5: Numeri reali..........................................................................................................20
• Sezione 6: Il problema dell’ordinamento..................................................................23
• Sezione 7: Tabelle.....................................................................................................................34
• Sezione 8: Grafi..........................................................................................................................39
• Sezione 9: Problemi di flusso e di accoppiamento in un grafo.......................52
• Sezione 10: Matrici sparse.....................................................................................................54
• Sezione 11: Progettazione algoritmi.............................................................................58
• Sezione 12: Le classi P ed NP.................................................................................................61
• Sezione 13: Recap esecutivo degli algoritmi............................................................64

Appunti di ingegneria degli algoritmi – Cavallari Gianmarco - 2021/2022

Sezione 1: Complessità computazionale

Un algoritmo è una procedura per risolvere un problema, ossia produrre una risposta a partire dai dati, che rispetta le caratteristiche di:

• Definitezza
• Input
• Output
• Finitezza
• Efficacia, ciascun passo è eseguibile in un tempo finito

Per definizione un algoritmo risponde sempre in un tempo finito. Vediamo alcuni importanti esempi storici di algoritmi:

Binary search

Input: Array ordinato A[i] con i=1,...,n, chiave v, estremi del sottovettore i,j.

Si esegue un confronto con il valore medio della successione e poi per ricorsione lo si itera sull’intero vettore.

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 BinarySeach(A,v,i,m-1)

• Se il vettore è vuoto i>j, allora la procedura risponde con il valore 0, cioè la chiave non è stata trovata
• Altrimenti se la chiave è uguale all'elemento mediano allora viene trovata correttamente
• Altrimenti se la chiave è maggiore dell'elemento mediano, si trova nel sottovettore destro, che è più piccolo del vettore corrente e per induzione viene trovata correttamente
• Se la chiave è minore dell'elemento mediano si trova nel sottovettore sinistro che è più piccolo del vettore corrente e per induzione la chiave viene trovata correttamente.

Algoritmo di Euclide

Il massimo comune divisore di due numeri si indica con MCD(m,n) > 1 è il più grande numero intero che divida entrambi i numeri dati. L'algoritmo funziona poiché il resto delle divisioni successive è una quantità discendente che all'ultimo passo diventa zero.

Input: m ed n numeri interi positivi con m > n.

while n =/= 0 do

(q,r) <-- m/n (quoziente e resto);

m <-- n;

n <-- r;

Result: m

Complessità computazionale

Spesso si seleziona e conta un sottoinsieme delle operazioni, assumendo che tutte le operazioni richiedano uno stesso tempo per la loro esecuzione. Questa assunzione ovviamente produce solo una approssimazione del primo ordine. Per valutazioni accurate vanno considerate anche le condizioni e le proprietà dell'hardware.

Un esempio in Matlab:

a = [1,2,3]

b = [4,5,6]

--> a+b = [5,7,9]

Si tratta di una specifica istanza del problema di sommare tra di loro due vettori di lunghezza 3, che a sua volta è un caso particolare del problema di sommare due vettori di dimensione n.

Notazioni asintotiche per il tempo di esecuzione

Si introducono ora le notazioni asintotiche per il tempo di esecuzione di un programma T(n) su input di dimensione n:

Definizione – Notazione O (limite asintotico superiore):

Sia g(n) una funzione di costo; indichiamo con O(g(n)) l’insieme delle funzioni f(n) tali per cui esiste un coefficiente C (cost. Moltiplicativa) ed M tali che: f(n) ≤ C * g(n) per ogni n ≥ m. Diciamo che g(n) è un limite asintotico superiore per f(n) e dunque f(n) cresce al più come g(n).

Vediamo che per gli n maggiori di 3, T(n) è di ordine 2n e che per n maggiori di 2 T (n) è di ordine 4n -> O(N). Per T (n) l'ordine, dopo n = 2 è di 2*n -> O(N). 22 2T (n)è dunque l'ordine maggiore tra i tre. (Intendendo T(n) = f(n))3

Definizione – Notazione Omega Ω (limite asintotico inferiore):

Sia g(n) una funzione di costo; indichiamo con Ω(g(n)) l’insieme delle funzioni f(n) tali per cui esiste un coefficiente C (cost. Moltiplicativa) ed M tali che: f(n) ≥ C * g(n) per ogni n ≥ m. Adesso g(n) è limite asintotico inferiore: questo significa che f(n) cresce almeno come g(n).

Definizione – Notazione Theta θ:

Sia g(n) una funzione di costo; indichiamo con θ(g(n)) l’insieme delle funzioni f(n) tali per cui esistono dei coefficienti C , C , M tali per cui:1 2 C * g(n) ≤ f(n) ≤ C * g(n) per ogni n ≥ m. f(n) cresce esattamente come g(n).1 2

Inoltre f(n) = θ(g(n)) se e solo se f(n) = O(g(n)) e f(n) = Ω(g(n)).

Nel precedente esempio Matlab, il costo è lineare nel numero degli elementi, quindi ci aspettiamo una complessità del tipo O(n) con n elementi.

A volte questa affermazione non è vera. A parità di lunghezza, alcune somme o operazioni potrebbero richiedere più tempo di altre e non sarà possibile sommarle in maniera unitaria.

Tempi di esecuzione

Cosa succede se la dimensione n non è sufficiente a determinare completamente il tempo di esecuzione? Definiamo T(n) il tempo di esecuzione del nostro programma.

• Worst Case: T(n) è O(f(n)) per qualunque input possibile di dimensione n
• Caso Medio: T(n) è O(f(n)) in media su tutti gli input possibili di dim. n
• Best Case: T(n) è Omega(f(n)) e questo valore viene raggiunto per alcuni degli input di dimensione n, ovvero l'algoritmo è molto efficiente e viene rallentato solo per alcuni, pochi e particolari input di dimensione n.

Tornando all'esempio precedente, possiamo ragionevolmente assumere che l'algoritmo per la somma di due vettori di dimensione n sia TETA(n) e che non ci sia differenza tra caso peggiore, migliore e caso medio. Lo scopo è quello di far avvicinare tutti i tempi di esecuzione per il nostro programma.

Casi comuni di complessità

• O(1): algoritmo che richiede tempo costante
• O(log(n)): algoritmo logaritmico
• O(n): algoritmo lineare
• O(n^k): algoritmo polinomiale [PREFERITO, CON GRADO MINORE POSSIBILE]
• O(aⁿ): algoritmo esponenziale [DA EVITARE, LENTO O INTERMINABILE]

Normalmente preferiamo un algoritmo con complessità asintotica inferiore. Un algoritmo O(n²) supererà prima o poi un algoritmo O(n³) anche quando i suoi coefficienti saranno più grandi. Gli algoritmi esponenziali sono estremamente pesanti. I problemi con algoritmo di risoluzione esponenziale vengono definiti intrattabili, sulle architetture correnti.

Complessità di algoritmi e problemi

• Complessità algoritmo: complessità di un particolare metodo per la soluzione di un problema
• Complessità di un problema: complessità del MIGLIORE algoritmo che risolve quel problema

ESEMPIO: Supponiamo di avere a disposizione un sistema di calcolo ed un programma che implementa un certo algoritmo: il sistema è in grado di risolvere un certo problema di dimensione N in un tempo T. Tuttavia, sappiamo che i sistemi di calcolo diventano sempre più veloci nel tempo. Se ora acquisisco un sistema due volte più veloce, quale dimensione N riesco a gestire nello stesso2 tempo?

Come si vede dalla tabella, se la velocità raddoppia, non raddoppia la dimensione calcolabile. La nuova dimensione calcolabile è sempre data da N' = N*SQRT(2).

Cose da tenere a mente

• Se abbiamo a che fare con istanze piccole, può essere che l'algoritmo O(n )3 sia migliore: 5n < 100n per tutti gli n minori di 20. Alcuni algoritmi "ottimi"3 2 sono efficaci solo per problemi di dimensioni astronomiche e quindi inutili in pratica.
• Se un programma verrà usato solo una volta o due allora il tempo di sviluppo diventa molto importante: un algoritmo semplice (e magari sviluppato in un linguaggio di scripting) può essere la scelta giusta.
• In alcuni casi l'algoritmo più veloce ha un costo di memoria eccessivo e dunque si deve ripiegare su algoritmi più lenti.
• In alcuni casi lo stesso algoritmo può essere il migliore nel caso medio ma anche il peggiore nel caso peggiore.
• Mai tentare di migliorare un programma senza prima misurare e verificare le sue prestazioni

Algoritmo di insertion sorting

C'è un insieme di oggetti, chiamati record (che potrebbero benissimo essere strutture). Ogni oggetto contiene almeno una chiave. Queste chiavi ammettono un ordinamento che segue alcune leggi:

• Tricotomia: confrontando 2 chiavi, 1 sarà minore, uguale o maggiore dell'altra. Questo vale ad esempio per i numeri interi.
• Transitività: se il primo numero è più piccolo del secondo ed il secondo del terzo, allora anche il primo sarà minore del terzo.

Un buon esempio è l’insieme dei numeri interi. L'insieme si definisce ordinato nel caso in cui le due proprietà precedenti sono verificate. Vogliamo modificare l’insieme delle chiavi in modo tale che dato i<j → K <= K .i j

Costo computazionale di un algoritmo

• Le espressioni scalari hanno un costo O(1)
• Il costo di una sequenza di istruzioni è dato dalla somma dei singoli costi
• Il costo di un ciclo è la somma del costo delle singole iterazioni
• Una istruzione condizionale ha costo nel caso peggiore che è il massimo tra i costi del ramo if e del ramo else. Per il costo medio occorre stimare la probabilità di ciascun ramo. In più bisogna stimare il costo della valutazione della condizione.

Esempio

a = 2.5; % 0 or 1: Cost of assignment is often ignored;

b = a*a+1; % Here we have 2 floating point operations;

c = b³; % b³ is b*b*b, so again 2 operations;

for k=n1:n2 % This is executed (n2-n1+1) times

c=a+b % Cost here is 1 independent of K

end % total cost: 1*(n2-n1+1)

if (mod(k,2) == 0) % If K is a random integer 50% prob.

c=a*b+c; % worst case is IF branch of cost 2

else % average case costs 1.5

b=b+1; % plus 2 for evaluating (MOD()==0)

end

Complessità notevoli

• Prodotto scalare di due vettori di dimensione n: 2n
• Somma scalata di vettori di dimensione n: 2n
• Prodotto matrice/vettore: 2mn
• Prodotto matrice/matrice: 2mnk

Analisi dell’algoritmo di insertion sorting

L'algoritmo solitamente ordina la sequenza sul posto. Si assume che la sequenza da ordinare sia partizionata in una sottosequenza già ordinata, all'inizio composta da un solo elemento, e una ancora da ordinare. Alla k-esima iterazione, la sequenza già ordinata contiene k elementi. In ogni iterazione, viene rimosso un elemento dalla sottosequenza non ordinata (scelto, in generale, arbitrariamente) e inserito (da cui il nome dell'algoritmo) nella posizione corretta della sottosequenza ordinata, estendendola così di un elemento.

Per fare questo, un'implementazione tipica dell'algoritmo utilizza due indici: uno punta all'elemento da ordinare e l'altro all'elemento immediatamente precedente. Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito. Il primo indice punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

Il caso ottimo per l'algoritmo è quello in cui la sequenza di partenza sia già ordinata. In questo caso, l'algoritmo ha tempo di esecuzione lineare, ossia Θ(n)Theta (n). Infatti, in questo caso, in ogni iterazione il primo elemento della sottosequenza non ordinata viene confrontato solo con l'ultimo della sottosequenza ordinata. Il caso pessimo è invece quello in cui la sequenza di partenza sia ordinata al contrario. In questo caso, ogni iterazione dovrà scorrere e spostare ogni elemento della sottosequenza ordinata prima di poter inserire il primo elemento della sottosequenza non ordinata. Pertanto, in questo caso l'algoritmo di insertion sort ha complessità temporale quadratica, ossia Θ(n ) Theta n .2 2

Anche il caso medio ha complessità quadratica, il che lo rende impraticabile per ordinare sequenze grandi. Pur avendo complessità elevata, tuttavia, risulta essere l'algoritmo di ordinamento più veloce per array piccoli.

Analisi algoritmo della ricerca binaria

In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca che individua l'indice di un determinato valore presente in un insieme ordinato di dati. La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare.

L'algoritmo è simile al metodo usato per trovare una parola sul dizionario: sapendo che il vocabolario è ordinato alfabeticamente, l'idea è quella di iniziare la ricerca non dal primo elemento, ma da quello centrale, cioè a metà del dizionario. Si confronta questo elemento con quello cercato:

• Se corrisponde, la ricerca termina indicando che l'elemento è stato trovato;
• Se è superiore, la ricerca viene ripetuta sugli elementi precedenti (ovvero sulla prima metà del dizionario), scartando quelli successivi;
• Se invece è inferiore, la ricerca viene ripetuta sugli elementi successivi (ovvero sulla seconda metà del dizionario), scartando quelli precedenti.

Se si arriva al punto che tutti gli elementi vengono scartati, la ricerca termina indicando che il valore non è stato trovato. Ad ogni iterazione la dimensione n si dimezza. Nel caso peggiore servono k >= log (n) passi.2 L’ordine di complessità di questo algoritmo è dunque O(log(n)).

Complessità computazionale delle funzioni ricorsive – dimostrazione limiti

Sono funzioni ricorsive quelle funzioni che chiamano se stesse ogni volta, sullo stesso problema di dimensione n, il quale decresce in dimensione ad ogni esecuzione. Un buon esempio è la risoluzione della sequenza di Fibonacci.

Ciascuna istanza di una funzione ricorsiva applicata ad un problema o è una istanza base n = 1 (di cui quindi possiamo calcolare il costo separatamente), oppure suddivide il problema corrente di dimensione n in un certo numero di sotto-problemi di dimensione più piccola, le cui soluzioni saranno poi combinate per costruire la soluzione complessiva.

Nella analisi delle funzioni ricorsive si usano spesso delle relazioni di ricorrenza, ossia delle equazioni del tipo:

T(n) = G(T(n-n ),T(n-n ),T(n-n ),…,T(n-n )) con n < n. Ad esempio:1 2 3 k j

Espandendo la relazione precedente, è possibile scrivere la generale formula 3 possibili casi del teorema Master, per le ricorrenze del tipo aT(n/b) + n α

La relazione lineare va Notare a e b . In baseα riscritta nel seguente al loro rapporto, modo -----------------> otteniamo limiti diversi

Queste formule di ricorrenza valgono solo per forme del tipo precedentemente definito. Se ci sono pi