Appunti Corso Algoritmi e Programmazione

01.ALGORITMI E CLASSI DI PROBLEMI

Algoritmo: sequenza finita di istruzioni per risolvere un problema.

Tipologie di Problemi:

• Decisione: nei quali la risposta è binaria (si o no).

o Decidibili: esiste algoritmo risolutivo.

▪ Trattabili: risolvibili in tempo ragionevole. Allora esiste un algoritmo polinomiale in

grado di risolvere questa sottocategoria di problemi (tesi di Edmonds-Cook-Karp).

Questi problemi si dicono di classe P.

▪ Intrattabili: non risolvibili in tempo ragionevole. [Torri di Hanoi per n elevato].

Solitamente in questa categoria ricadono quelli di classe NP.

o Indecidibili: non esiste algoritmo risolutivo. [congettura di Goldbach]

• Ricerca: nei quali si cerca la soluzione valida tra le n soluzioni possibili [n=0,1,…infinito].

• Verifica: nei quali si stabilisce se la risposta data sia valida.

• Ottimizzazione: nei quali si cerca la soluzione migliore ad un dato problema.

Classi di Problemi:

• P: sono problemi Polinomiali.

• NP: sono problemi Non-deterministico Polinomiali, ovvero

quelli per i quali non si può escludere che vi sia una

soluzione polinomiale anche se non si sia ancora trovata.

• NP-Completo: sono problemi costruiti in modo tale che

ogni altro problema NP sia riducibile ad esso attraverso

trasformazioni polinomiali.

• NP-Hard: un problema è di questa classe se ogni problema

NP è riducibile ad esso in tempo polinomiale.

02.ANALISI DI COMPLESSITA DEGLI ALGORITMI

Analisi di Complessità: indipendentemente dalla macchina e dalla tipologia o contenuto dei dati, è la

previsione delle risorse richieste dall’algoritmo per la sua esecuzione, tramite metodi empirici e analitici.

Classificazione degli Algoritmi:

• : costante.

• (): logaritmico.

• : lineare.

• (): linearitmico.

•

: quadratico.

•

: cubico.

•

: esponenziale.

Analisi Asintotica di Caso Peggiore: si fa allo scopo di avere una stima per un limite superiore all’algoritmo

() su n dati nel caso peggiore (algoritmo compie il numero massimo di passi possibile per la risoluzione).

→ ∞,

Si dice asintotica perché si stima la complessità per in quanto per n piccoli la complessità è irrilevante

Notazione asintotica O:

() = (()) ↔ ∃ > 0, ∃ > 0 → ∀ > ≤ () ≤ ()

0 0

In parole povere, g(n) è limite superiore lasco dell’algoritmo T(n) se,

superata la soglia , T(n) non supera mai g(n) moltiplicata per una

0

costante. [Come simbolo di Landau di analisi 1].

Notazione asintotica Ω:

() = (()) ↔ ∃ > 0, ∃ > 0 → ∀ > ≤ () ≤ ()

0 0

In questo caso l’algoritmo non sarà mai di complessità minore di g(n),

perché questa, moltiplicata per una costante, sarà il suo limite inferiore

lasco. Sempre oltre un certo numero di dati .

0

Notazione asintotica Θ:

() = (()) ↔ ∃ , > 0, ∃ > 0 → ∀ >

1 2 0 0

≤ () ≤ () ≤ ()

Questo sta a voler dire che g(n) è sia limite superiore che inferiore e

quindi la complessità dell’algoritmo ha lo stesso andamento di g(n).

Problema della Connettività (Algoritmi Union-Find):

Tra i numerosi problemi di programmazione che esistono, quello della connettività si ripropone in diverse

forme ed è bene conoscerlo: il problema consiste nell’acquisizione di istruzioni in forma “p-q”, che indicano

che l’oggetto p è connesso con l’oggetto q, e allora controllare che la coppia sia già connessa, in caso

negativo stabilire la nuova connessione, altrimenti procedere con la nuova coppia. Per grandi quantità di dati

questi controlli sarebbero impossibili senza algoritmi efficienti.

È bene definire 3 proprietà di connessione fondamentali: 1. Riflessiva: p è connesso con sé stesso. 2.

Simmetrica: se p è connesso a q, allora q è connesso a p. 3. Transitiva: se p è connesso con q e q è connesso

con r, allora p è connesso con r.

Per i problemi di connettività si adoperano 2 operazioni fondamentali: la union sostituisce i 2 insiemi che

contengono 2 oggetti con l’unione dei due insiemi, la find trova l’insieme che contiene un dato oggetto.

SI

Input della FIND: elementi nello Prossima

coppia p-q stesso insieme? coppia

UNION: unione degli

NO insiemi che li contengono

E dato questo problema l’ottimizzazione non è solo l’algoritmo, ma anche l’organizzazione del dato. Infatti

consideriamo un approccio dove non vengono memorizzate tutte le connessioni. Vediamo gli algoritmi di

Quick-find e Quick-union.

Quick-find: questo algoritmo prevede un vettore di n elementi, dove n corrisponde al numero di nodi da

connettere. L’indice di ogni casella di questo vettore corrisponde all’i-esimo nodo. Il vettore è inizializzato

come v[i]=i. Ogni nuova connessione p-q ricevuta in input implica la sostituzione su ogni nodo di p con q (o

viceversa). [se rileggi e non capisci vai a pagina 12 di Sedgewick].

Quick-union: questo algoritmo prevede che ogni nodo abbia un puntatore a suo “padre” o a sé stesso. Quindi

per sapere se 2 nodi sono connessi bisogna risalire attraverso i puntatori di entrambi finché non si trova la

radice di entrambi (nodo che punta sé stesso). Se esiste i 2 elementi sono connessi, altrimenti si fa puntare

uno dei 2 all’altro. -> Quick-union pesata: aggiungendo un controllo e facendo puntare l’albero più piccolo a

quello più grande si abbatte la complessità.

Complessità di QF, QU, WQU:

• QF: per ognuna delle operazioni (M) di union, iteriamo un ciclo for per N volte. QF(N)=O(M*N) =O(N).

In questo caso la (quick) find ha costo unitario e la complessità dipende dalla union.

• QU: nel peggiore dei casi abbiamo N-1 puntatori e nel migliore 1 solo, quindi mediamente N/2

invocazioni di find. Dunque QU(N) = O(M*N/2) = O(N). Qui la (quick) union ha costo unitario.

•

2

WQU: in questo caso la distanza massima di un nodo dalla radice in un albero da nodi è n, e se 2

+1

2 2

alberi da nodi si uniscono, si genererebbe un albero da nodi nel quale la distanza massima

tra nodo e radice è n+1. Si dimostra (probabilmente con l’approssimazione di Stirling) che WQU(N) =

O(2*log(N)) = O(log(N)). La union ha costo unitario.

03.ALGORITMI DI ORDINAMENTO

Classificazione degli algoritmi di ordinamento:

• Ord. Interno: su dati in memoria centrale ai quali si ha accesso diretto.

o In loco/non in loco: l’ordinamento si dice “in loco” quando oltre agli n dati da ordinare si ha

un numero fisso di locazioni di memoria ausiliarie. “non in loco” se le locazioni ausiliarie

dipendono dal numero di dati da ordinare.

o Stabili/instabili: l’ordinamento si dice “stabile” se rimane invariato l’ordinamento relativo

dei dati se si cambia la chiave di ordinamento. “instabile” se non viene mantenuto questo

ordine, poi si capisce attraverso gli esempi.

• Ord. Esterno: su dati in memoria di massa ai quali si ha accesso sequenziale (non li tratteremo).

Limite inferiore degli algoritmi basati sul confronto: se ogni confronto ha un costo unitario, costruiamo un

albero binario la cui altezza è h ed è pari al numero di dati da ordinare. Dunque le foglie (quindi soluzioni)

ℎ

2

sono esattamente , che per l’approssimazione di Stirling, possiamo paragonare in questo modo:

ℎ

2 ≥ ! > ( ) , → ℎ > ln ( ) = ln − ln = Ω( ln )

Scan Lineare: uno scan lineare è una ricerca su un array di un determinato dato. Intuitivamente compie al

più N (numero di dati) controlli. Quindi ha complessità O(N).

Algoritmi di ordinamento e relative complessità: [Sedgewick da p228]

//per ognuno dei successivi codici, definiamo qualche macro

#define less(A, B) (A<B) //ritorna un valore booleano

#define scambio(A, B) { int t = A; A = B; B = t; } //scambio di A con B

#define scambioCondizionale(A, B) if(less(B, A)) scambio(A, B)

Bubble Sort: questo ordinamento consiste nell’attraversare il file, scambiando se necessario gli elementi

adiacenti (all’indietro) finché non è più necessario scambiare elementi. L’ordinamento è in loco perché sono

richiesti solo gli indici come variabili ausiliarie e stabile perché si mantiene l’ordine relativo tra elementi

uguali: se un elemento è uguale all’altro questi non si scambiano ma quello a sinistra “continua il cammino

di quello che è arrivato da destra”.

void bubbleSort(int a[],int l, int r) // l = estremo inferiore, r = estremo superiore

{int i,j;

for(i = l; i < r; i++)

for(j = r; j > i; l--)

scambioCondizionale(a[j-1],a[j]);

}

La complessità dell’algoritmo si ricava considerando che si tratta di 2 cicli annidati, quello esterno che è

eseguito n-1 volte e quello interno che è eseguito n-i-1 volte. Il numero di scambi è dello stesso ordine di

grandezza del numero di confronti, questi si ricavano con la sommatoria di Gauss:

( + 1)

( ( ()

() = − 1) + − 2) + ⋯ + 2 + 1 = ∑( − ) = = 2

=1

Essendo il numero di confronti e il numero di scambi dello stesso ordine questo ci dice che la complessità del

2

() = ( ).

Bubble Sort è

Selection Sort: questo ordinamento consiste nel sostituire al primo elemento dell’array il dato più piccolo

dello stesso, poi cerca il secondo elemento più piccolo e lo sostituisce al secondo e così via. È un tipo di

ordinamento in loco perché usa solo una variabile di supporto e instabile perché non mantiene l’ordine

relativo tra elementi che corrispondono in funzione della chiave.

void selectionSort(int a[], int l, int r) // l = estremo inferiore, r = estremo superiore

{int i, j;

for(i = l; i < r; i++)

{int min = i;

for(j = i + 1; j <= r; j++)

if( less(a[j], a[min])) min = j;

scambio(a[j], a[min]));

}

}

La complessità dell’algoritmo si ricava considerando che si tratta di 2 cicli annidati, quello esterno che è

eseguito n-1 volte e quello interno che è eseguito n-i-1 volte. Gli scambi sono al più n, quindi per la

complessità non ci interessa, ma per ogni iterazione del ciclo interno viene effettuato un confronto, la

complessità è data dal numero di confronti, e il numero di confronti si ricava con la sommatoria di Gauss:

( + 1)

( ( ()

() = − 1) + − 2) + ⋯ + 2 + 1 = ∑( − ) = = 2

=1 2

() = ( ).

Questo ci dice che la complessità del Selection Sort è

Insertion Sort: Questo è il metodo che si usa comunemente per ordinare le carte nella propria mano. Durante

il procedimento gli elementi a sinistra sono ordinati tra loro ma è possibile che un elemento sulla destra

venga messo tra gli elementi a sinistra (il fatto che non venga turbato l’ordine relativo lo rende un algoritmo

stabile)

void insertionSort(int a[],int l,int r)// l = estremo inferiore, r = estremo superiore

{int i,j,v;

//mettiamo subito l'elemento più piccolo nella prima cella

for(i = r; i > l; i--) scambioCondizionale(a[i-1],a[i]);

for(i = l+2; i <= r; i++)

{j=i; v=a[i];

while(less(v,a[j-1]))

//v non potrà mai essere più piccolo di a[0]

//quindi non serve il controllo j>1

{a[j]=a[j-1]; j--;}

//finchè v è più piccolo dell'elemento

//a sinistra viene fatto spazio

a[j]=v;

}

} 2

() = ( ).

L’algoritmo è chiaramente in loco e, sempre per gli stessi motivi, la sua complessità è

Shell Sort: lo Shell Sort è un caso particolare dell’Insertion Sort perché di fondo è lo stesso algoritmo che però

punta ad ordinare dei sotto vettori del vettore principale che sono costruiti col criterio di essere a distanza h

uno dall’altro. Ad ogni ciclo esterno il valore di h diventa più piccolo fino ad arrivare ad 1. L’algoritmo, sc