Algoritmi e strutture dati

F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E

Tali elementi vanno inseriti nell'ordine in cui sono proposti, e dovranno risultare ordinati (ossia in ordine alfabetico)

Insiemi

Un insieme è una collezione i elementi dove ciascun elemento è un insieme oppure un atomo (elemento di tipo base)

NON ci sono mai elementi uguali

In genere gli elementi sono tutti dello stesso tipo (soprattutto gli atomi)

E vale una relazione d'ordinamento.

Operazioni base Algoritmi e strutture dati Pagina 21

Operazioni base

Union(A,B)

Intersection(A,B)

Difference(A,B)

Merge(A,B)

Member(x,A)

Insert(x,A)

Delete(x,A)

Min(A)

Max(A)

Find(x)

Implementazione di insiemi

Si può implementare un insieme in 2 modi:

1. Bit vector

2. Liste ordinate

Bit Vector

Un insieme può essere implementato tramite bit vector sono se l'insieme U (universo) è di piccole dimensioni e

rappresentabile con l'insieme {0,1,2,3….n}

Costruiamo un array S che rappresenta il nostro insieme Universo:

Metteremo uno 0 in ogni casella in cui il numero non è presente nel nostro insieme ed un 1 in ogni casella incui il

numero è presente all'interno del nostro insieme.

Costo operazioni elementari:

• Insert, delete, member

• Max, min

Union -> OR bit a bit

Intersection -> AND bit a bit

Differenza -> AND + NOT

Implementazione con liste linkate

Elenchiamo vantaggi e svantaggi di questo tipo di implementazione:

• Lo spazio occupato è proporzionale al numero di elementi nell'insieme

• Non è necessario avere un insieme universo di riferimento e se c'è ed è grande non è un problema

Svantaggi:

• Alcune operazioni sono meno efficienti

Possiamo implementare un insieme in due tipi di liste, in una lista ordinata o una lista non ordinata.

Lista non ordinata

In un insieme implementato in una lista non orientata, le seguenti operazioni si effettuano così:

• Unione: Basta accodare le due liste: il next dell'ultimo elemento di A punta a B.head

• Intersezione: per ogni elemento in A bisogna cercare se compare anche in B, scorrendo tutta b, e se lo trova,

inserirlo in C

• Differenza: opera come l'intersezione, solo che inserisce in C gli elementi di A non trovati in B

• Member: Scorre tutta la lista alla ricerca dell'elemento x di interesse (lo stesso vale per delete, insert, max, min)

Lista ordinata

• Unione, intersezione, differenza: Si scorrono le lista di A e B in parallelo, fermandosi appena il valore di una è

uguale o supera quello dell'altra per eseguire l'operazione di interesse sul risultato C

Tabelle di Hash Algoritmi e strutture dati Pagina 22

Tabelle di Hash

Una tabella di hash è un vettore dove alloco i miei valori con un criterio dato dalla funzione di hash.

Ha 2 vantaggi principali:

1. Mantiene una dimensione occupata su k

2. Mediamente il costo di insert, delete, e member è O(1)

Nelle tabelle di Hash non vi è nessuna relazione d'ordine.

Funzione di hash

Nello spazio K avremo un certo valore h(v) il quale risultato della funzione sarà l'indirizzo della cella nella tabella di ha sh

dove trovare il dato.

Quindi, per trovare la posizione di un certo elemento v, ci basta fare h(v), e troveremo l' indice di v all'interno della

tabella T.

La migliore funzione di hash fa in modo che v non centri nulla con w: per ciò serviranno funzioni matematiche complesse

Open Hashing

L'open hashing serve per risolvere le colisioni utilizzando il "chaining": tutti gli elementi che collidono in un valroe di

hash sono inseriti in una lista linkata puntata dall'elemento della tabella di hash che corrisponde al valore di hash su cui

si verifica la collisione

Per implementare le operazioni di memeber, insert, delete basta utilizzare le operazioni omonime definite per le liste

linkate, considerando come head il puntatore T[h(key)] dove key è il valore da cercare

In questo caso, per evitare che due elementi in k vengano inseriti in una stessa casella, nella casella di T verrà inserita u n

insieme di puntatori che puntano ad una lista che conterrà i vari elementi. In questo modo evitiamo la collisione.

Funzioni di hash

Una buona funzione hash distriuisce in modo piuttosto uniforme ciascuna chiave.

• Metodo della divisione: ciascun valore k viene mappato al resto della sua divisione per il numero B di bucket

h(K) = k mod B

Pro: è molto veloce da calcolare

Contro: attenzione a scegliere il valore di B

• Metodo della moltiplicazione = diviso in due fasi: la prima moltiplica k per una costante A compresa tra 0 e 1,

estraendo la parte frazionaria del risultato, e poi modifica il risultato per B e considera l'intero rispetto al risultato

ottenuto

H(k) = [B(kA mod 1)]

Closed hashing (open addressing)

Nel closed hashing non vengono utilizzate strutture esterne per gestire le collisioni, ma tutti i valori sono memorizzati in

una cella nT, che può quindi diventare piena.

Il load factor (non può mai eccedere 1)

Algoritmi e strutture dati Pagina 23

Il load factor (non può mai eccedere 1)

Non vengono utilizzati i puntatori fra le celle di T, bensì un metodo di re-hosting, un metodo per trovare, per ciascuna

chiave tutti i blocchi dove potesse essere memorizzata

• Probe sequence: per una chiave K è la permutazione dei valori <0,1 ..B-1> che corrisponde nell'ordine in cui viene

valutato allo spot in cui k può essere memorizzato nel caso non ci siano collisioni

La funzione hash è definita come

E ritorna, data la chiave k e la posizione desiderata, il corrispondente elmento nella probe sequence

Per inserire un valore k in T, prima valuto h(k, 0): se è pieno provo ad inserirlo in h(k,1) e così via finchè non trovo (se

esiste) una posizione libera.

HASH_INSERT(T,K)

i=0;

Repeat

j= h(k,i)

If T[j] == NULL

T[j] = k

Return j;

Else i = i+1

Until i==B

Return "overflow"

Per cercare un valore proccedo in modo analogo: seguo la sequenza finchè non trovo il valore cercato o un blocco vuoto.

HASH_SEARCH(T,k)

I = 0

Repeat

j=h(k,i)

If T[j] == k return j;

i= i+1;

Until T[j] == NULL OR i == B

Return NULL

Per cancellare un valore non si può semplicemente mettere vuoto il blocco a null poiché verrebbe interrotta la probe

sequence: è necessario un valore speciale "deleted" che non blocchi la ricerca con il primo incontrato, ma al contrario

consenta di inserire un valore al suo posto quando lo incontro nella probe sequence.

• Uniform Hosting: la probe sequence di ogni chiave ha uguale probabilità di ssere una delle B! permutazioni di

<0,1,…,B-1>

• Linear probing: data una funzione di hash h' = U -> {0,1, … , B-1} detta funzione hash ausiliaria il metodo del linear

probing usa la seguente funzione hash:

(in altre parole, se ad esempio 40%7=5 viene inserito nella cella i, il valore successivo 47%7=5 verrà inserito nella

cella i+1 o, se è alla fine dell'array, all'inizio dell'array stesso.)

• Quadratic probing: data la funzione hash ausiliaria h', la funzione di hash è

Algoritmi e strutture dati Pagina 24

• Quadratic probing: data la funzione hash ausiliaria h', la funzione di hash è

Con c1,c2 costanti ausiliarie positive, e c2 != 0

Data una chiave k, prima mappa a T[h'(k)] e poi a posizione che dipendono in modo

quadratico dalla posizione i nella sequenza di probe

• Double Hashing: Il double hashing è uno dei metodi migliori disponibile per l'open hashing. Il double hashing

utilizza due funzioni ausiliarie h1 e h2, e la funzione viene definita in questo modo:

Data una chiave k, prima viene mappata a T[h1(k)] e poi a valori la cui distanza da h1(k) dipende da un'altra

funzione hash, ossia h2(k). Tramite questo metodo si arriva a permutare un numero di probe sequence pari a

Algoritmi e strutture dati Pagina 25

ALGO 7° Lezione

sabato 21 novembre 2015 13:40

Grafi

Un grafo è una coppia (V,E) dove:

• V è un insieme finito di elementi, detti nodi (o vertici o punti)

• E è un insieme di archi (orientati)

Un arco orientato è una coppia ordinata (v1,v2) dove v1 e v2

V1 è la coda dell'arco e v2 è la testa. (l'arco va da v1 a v2) in un arco non orientato non vi è questa

puntualizzazione.

Un grafo con solo archi orientati si chiama grafo orientato.

Un grafo con solo archi non orientati si chiama grafo non orientato. In questo caso, se un arco è

incidente nei vertici v1 e v2, allora questi due vertici sono neighbors.

Due vertici sono adiacenti quando essi sono collegati tra loro da un arco. Nel caso di un arco orientato si

parla di non simmetria mentre nel caso di un arco non orientato si parla di simmetria.

Il grado di un vertice in un grafo non orientato è il numero di archi in cui è coinvolto. (degree)

In un grafo orientato abbiamo l'In-degree, ossia il numero di archi che entrano nel nodo, e l' out-degree,

ossia il numero di archi che escono dal nodo. La somma di essi da il degree.

Identifichiamo un cammino: un cammino da un vertice v1 ad un vertice vi è pari al numero di archi che

si percorrono per arrivare a vi

Un cammino si dice semplici quando tutti i vertici, ad eccezione del primo o dell'ultimo, sono distinti.

Un cammino che inizia e finisce nello stesso vertice si dice ciclo.

Implementazione di un Grafo

Per implementare un grafo, si utilizzano le matrici di adiacenza e le liste di adiacenza:

Matrice di adiacenza

• Assumiamo che i vertici sono numerati, in modo arbitrario. Allora possiamo considerare la matrice

di adiacenza di un grafo come:

Lista d'adiacenza

• Per lista di adiacenza si intende un array, formato da |v| elementi, in cui ciascun elemento è una

lista di vertici, tali che esiste un arco (w,v)

Algoritmi e strutture dati Pagina 26

Vantaggi/Svantaggi

Vantaggi/Svantaggi della matrice di adiacenza:

• + determino in tempo costante se (w,v)

- richiede molto spazio, ossia

•

Vantaggi/Svantaggi delle liste di adiacenza:

• + lo spazio occupato è di

• È costoso determinare se (w,v)

In linea di massima la matrice di adiacenza è consigliata quando il grafo è molto denso (|E| ondina |V|^

2)

Le liste di adiacenza invece sono ideali quando il grafico è sparso (|E| << |V|^2)

Attraversamento di grafi

Per risolvere molto problemi legati ai grafi si utilizza un metodo di visita del grafo, chiamato

attraversamento.

Analizziamo due approcci di attraversamento:

• BFS (breadth first search - in ampiezza)

• DFS (depth first search - in profondità)