Algoritmi e strutture dati - Appunti

Riassunti di Algoritmi e Strutture Dati

Notazioni asintotiche

:

1. indica la spesa massima, è collegata al caso peggiore

() ≤ ()

a. dove g(n) è la funzione più semplice

() = (())

b. che indica il valore massimo di f;

Ω:

2. è collegata al caso migliore, indica la spesa minima:

() ≥ ()

a. () = Ω(())

b. che indica il valore minimo di f

:

3. è collegata ai casi precedenti ed indica il costo costante

() ≤ () ≤ ()

a. () (() Ω(()

b. Quando la funzione è sia che

()

: = (() lim =0

4. ()

→∞ ()

~( ): ()~() lim =1

5. ()

→∞

Grafi orientati (detti anche diretti)

Un grafo orientato è un grafo in cui sono presenti archi orientati, ossia che ha una direzione e quindi una testa e

una coda. A A B

B ≠

Grafi non orientati 2

∗

Il collegamento tra i vertici non ha un orientamento. Il numero massimo di combinazioni tra i vertici è 2

A A B

B =

Caratteristiche dei grafi ()

Un grafo sparso è un grafo che ha in cui n è il numero di vertici.

(è

( = ° ° ).

)

Un grafo denso è un grafo che ha 1

Il cammino di un grafo G è una successione di vertici, in cui ogni coppia di vertici appartiene all’insieme dei lati:

 Cammino semplice: quando non si passa mai sugli stessi nodi;

 Ciclo: è un cammino in cui si inizia e si finisce con lo stesso nodo;

 Ciclo semplice: è un ciclo in cui non si ripetono i nodi, tranne il primo e l’ultimo (che devono coincidere).

Un grafo è “connesso” quando tutti i vertici sono collegati da almeno un lato, quindi non esistono vertici isolati.

Un grafo “non connesso” è quando almeno un vertice è isolato.

La partizione del grafo è detta anche “componente del grafo” ed è la somma o unione di componenti connesse.

Visite sui grafi

La visita in ampiezza è una procedura di attraversamento del grafo, consiste nell’inserimento di una coda (che è una

pila a doppia entrata) da un lato i nodi raggiunti (partendo da un nodo sorgente) e dall’altro lato i nodi adiacenti a

quello raggiunto ma non ancora presenti nella coda. Questa procedura produrrà in uscita un albero di copertura che

indicherà uno dei tanti cammini possibili per visitare il grafo (cambia in base al nodo sorgente).

inserimento dei nodi visitati ins. dei nodi adiacenti a

Coda quello visitato

La visita in profondità è una procedura di attraversamento del grafo, consiste nell’ inserimento dei nodi visitati (che

hanno più percorsi) in una pila, quindi partendo da un nodo sorgente trova un cammino verso il nodo più lontano e,

una volta raggiunto questo nodo (il quale ha tutti i nodi adiacenti già aggiunti), procede a ritroso inserendo nuovi

cammini (sui bivii incontrati) per raggiungere tutti gli altri nodi non ancora inseriti. In questo caso viene a formarsi una

foresta di copertura del grafo di ingresso. 8

4

1 6

2 3 5 7

Ordine visita: 1, 2, 3, 5(aggiunto alla pila), 6(aggiunto alla pila), 7(ultimo), tolgo 6 dalla pila e visito 8(ultimo), tolgo 5

dalla pila e visito 4(ultimo); la pila è vuota quindi ogni nodo è stato inserito.

Liste di adiacenza

E’ una rappresentazione dei grafi. Si mettono tutti i vertici in colonna e a fianco di ognuno di essi si mettono tutti i

vertici adiacenti a quello incolonnato. Vi sono tre casi:

 ()

Migliore: quando abbiamo un solo collegamento con la lista;

 ( + )

Medio: sia in tempo che in spazio;

 2 )

(

Peggiore: quando tutto è collegato con tutti.

4

2

1 3

1

2 1 4

2

2

3 4 3

4 1

3 2

Matrice di adiacenza ∗

Serve per rappresentare un grafo di n lati, è la dimensione della matrice. La matrice ha come indici i vertici e la

loro intersezione indica il cammino dei due:

 2 )

(

Il costo in spazio della matrice è

 (1)

Il costo in tempo è costante è

Alberi

Un albero è un grafo non orientato che è aciclico e connesso. È connesso con n nodi e n-1 lati. Esso ammette uno e

un solo cammino tra una qualunque coppia di nodi. L’albero è anche un grafo sparso.

 La radice è il primo nodo dell’albero;

 Il livello sono i passi che bisogna fare da un nodo per raggiungere la radice;

 Il padre è il nodo che sta sopra a quello considerato;

 Il figlio è il nodo che sta sotto al nodo considerato;

 Si distinguono due categorie:

o Nodi interni: quelli che hanno figli;

o Foglie: quelli che non hanno figli;

 L’altezza di un nodo è il cammino da quel nodo alla foglia più lontana;

 La profondità di un nodo è il cammino da quel nodo alla radice;

 L’altezza dell’albero corrisponde alla distanza dalla radice alla foglia più lontana;

 L’altezza accettabile di un albero è ≤ O(log n)

 L’albero è bilanciato se tutte le foglie sono sullo stesso livello;

 La lunghezza è divisa in 3 tipi:

o : =

la lunghezza del cammino interno di un albero è la somma dei livelli di tutti i nodi interni

(1 + 2 + 3 + 3)

o (2

: = + 3 + 4 + 4) =

la lunghezza del cammino esterno è la somma dei livelli di tutte le foglie

13

o = + .

Alberi Ordinati (binari)

Possono essere visitati in 3 modi:

 Pre-order (visita la radice e poi ricorsivamente in pre-ordine tutti i nodi)

sequenza visita: 1,2,3,4,5,6,7

 Post-order (visita prima i nodi dal basso verso l’alto e per ultima la radice)

seq. Visita: 3,4,2,6,7,5,1

 In-order (si visita in ordine il sottoalbero sx, poi la radice, poi il sottoalbero dx) 3

sequenza visita: 3,2,4,1,6,5,7

Alberi binari

Un albero binario è un albero con radice ordinato in cui:

 I nodi possono avere al massimo 2 figli;

 I figli di un nodo sono distinti in destro e sinistro.

Un albero binario si dice pieno se tutti i livelli sono saturi. Un albero binario si dice completo se è pieno e i nodi

ℎ+1

2 − 1).

sull’ultimo livello sono più a sinistra possibile (n° vertici alb. Comp.

Alberi binari di ricerca

Ricerca(v,x): 

v=NULL return NULL;

1. Se 

x=key(v) return v;

2. Se 

x<key(v) return Ricerca(sx(v),x) return Ricerca(dx(v),x).

3. Se else

Remove(v): NULL;

1. Se v è una foglia rimpiazzi v con

a. Altrimenti se a sinistra di v c’è un figlio assegni ad u il figlio sinistro di v, altrimenti assegni ad u il figlio

destro di v; Replace(v,u).

b. Se il padre di v non c’è allora assegni a v la u appena trovata altrimenti richiami

Replace(v):

 Se v è figlio sinistro, assegni u a v, altrimenti al padre di v assegni u come figlio destro;

 Se u ha figli assegni al padre di u il padre di v.

Alberi 2-3

È un albero che può avere 2 o 3 figli. Ogni nodo può avere al massimo 2 etichette (valori al suo interno) e le sue

foglie sono sullo stesso livello. Un albero di questa tipologia non può essere formato da un solo dato.

Alberi 2-3-4

È un albero vuoto oppure è un albero che contiene 3 tipi di nodi:

 Singoli: aventi una chiave, un collegamento a sinistra a un albero con chiavi minori e un collegamento a destra

a un albero contenente chiavi maggiori;

 Doppi: aventi due chiavi, un link a sinistra per il sottoalbero con chiavi minori, un link in mezzo per le chiavi

comprese e un link a destra per il sottoalbero contenente chiavi maggiori;

 Tripli: aventi tre chiavi e 4 link contenenti chiavi i cui valori stanno negli intervalli definiti dalle 3 chiavi.

( ).

Per definizione gli alberi 2-3-4 sono bilanciati e hanno sempre altezza = Inoltre,

 I nodi singoli hanno obbligatoriamente 2 figli;

 I nodi doppi hanno obbligatoriamente 3 figli;

 I nodi tripli hanno obbligatoriamente 4 figli;

 Tutte le foglie stanno sullo stesso livello.

Non si usano etichette, evitando quindi la questione degli aggiornamenti, come avviene invece negli alberi 2-3. 4

Alberi Red-Black (RB)

Partendo da un albero 2-3-4 si possono rappresentare più tipi di RB (per sapere quanti bisogna contare quanti nodi

doppi ci sono nel 2-3-4). Partendo invece da una lista di nodi esiste un’unica implementazione.

Non si possono avere 2 link rossi consecutivi, se si verifica bisogna effettuare una rotazione (o più rotazioni). Il numero

di link rossi deve essere sempre lo stesso sia nel lato sinistro che nel lato destro, se ciò non si verifica, sarà necessario

cambiare i colori in modo opportuno.

Algoritmi di ordinamento

- Esistono due classi generali degli algoritmi di ordinamento:

o Classi confronti e scambi: svolgono operazioni di confronto e scambio tra i dati;

o Classi digitali: le operazioni possono riguardare singoli bit o gruppi di bit di ciascun dato.

- Ogni algoritmo di ordinamento può essere:

o Stabile: se rispetta l’ordine relativo degli elementi di ugual valore (es. un elenco di alunni ordinati per

ordine alfabetico, se si crea un algoritmo che li ordinerà per anno di corso, questo sarà stabile solo se

dopo l’ordinamento per anno di corso gli alunni dello stesso anno saranno in ordine alfabetico e non

sparsi);

o Adattivo: se i confronti effettuati dipendono dai dati (altrimenti l’algoritmo sarà non-adattivo).

- Record imbattibile: qualunque algoritmo di tipo confronti e scambi nel caso peggiore dovrà eseguire almeno

log ( log )

+ confronti per ordinare una sequenza di n dati.

2 2

Selection sort

Costo:

 2

( );

N° di confronti:

 ();

N° di scambi:

 2 ).

(

N° complessivo di operazioni:

Lavora con 2 cicli innestati.

1. Il ciclo for più esterno incrementa la i e assegna il valore della i all’indice min:

2. Il secondo ciclo for, quello più interno, incrementa la j che di partenza è i+1 e ad ogni incremento della j

confronta l’elemento in posizione j con l’elemento in posizione min. Se l’elemento in posizione j è minore

dell’elemento in posizione min assegna a min il valore di j. Quando la j ha raggiunto la n termina il ciclo for

interno, scambia l’elemento in posizione i con l’elemento in posizione min e poi si incrementa la i e si riprende

il ciclo interno.

public class Selection{

public static void sort(Comparable[] a)

{int N = a.lenght;

for(int i=0; i<N; i++)

{int min =