Appunti di Algoritmi e strutture dati

COUNTING-SORT

È un algoritmo di ordinamento basato sul conteggio e non su confronti. Ha il vincolo di conoscre il range di

valori da ordinare contenuti nel vettore A.

Come si procede?

1. Si contano le occorrenze di ogni valore del range e si mette questo conteggio in un vettore B, in modo

da sapere il numero di elementi che precedono ogni valore del range nell’ordine

2. Si scorrono gli elementi del vettore di partenza A, dall’ultimo e si inseriscono nella corretta posizione

i base alle informazioni ottenute nello step precedente (info scritte in B)

Procedo contando quante volte sono presenti i vari valori . -Input: A[1...n] dove A[j] {0,1,…,k} per j=1,2,…,n.

∈ -Output: B[1...n], ordinati dove B è un array preventivamente allocato. -Memoria aggiuntiva C[0,…,k]

Correttezza

Tramite invarianti di ciclo

Costo: → ( + )

Il costo di Counting-Sort è lineare entro un certo valore di k

Per ovviare al problema della decisione della grandezza di k si introduce il Radix-Sort.

Di seguito è mostrato un esempio completo di Counting-sort.

RADIX-SORT

L’idea è quella di andare ad ordinare i valori partendo dalla cifra meno significativa.

Es: Counting-sort

Il concetto è il seguente: esempio

Esempio:

Costo: (( + ))

La complessità è pari ad dove è la base della rappresentazione e è il numero di cifre.

().

Dato che e sono costanti avrò quindi una complessità pari a

RIEPILOGO COMPLESSITÀ ALGORITMI VISTI IN PRECEDENZA

ALGORITMO CASO MIGLIORE CASO MEDIO CASO PEGGIORE

2 2

() ) )

Insertion-Sort ( (

( ) ( ) ( )

Merge-Sort 2

( ) ( ) )

Quick-Sort (

( + ) ( + ) ( + )

Counting-Sort (( + ))

Radix-Sort (( + )) (( + ))

TABELLE

Fa parte degli insiemi dinamici, le tabelle hash sono una implementazione efficiente del dizionario.

Una tabella hash è una sequenza di elementi ciascuno dei quali è costituito da due parti:

• ,

Una chiave costituita da un gruppo di caratteri (o più generale di bit), per distingue un elemento

dagli altri

• ,

Informazione associata alla chiave ,

Lo scopo della tabella è memorizzare delle informazioni mentre quello della chiave è quello di individuare

le dall’esterno.

Lo Scopo della chiave è l’individuazione delle dall’esterno.

Le operazioni possibili sono: Ricerca, Eliminazione, Inserimento.

Esistono due possibili metodologie di implementazione delle tabelle:

1. Tabelle ad indirizzamento diretto

2. Tabelle Hash

1 - TABELLE AD INDIRIZZAMENTO DIRETTO:

Questa tecnica funziona bene se il numero delle chiavi è

piccolo.

m = numero delle chiavi.

Supponiamo di dover gestire un insieme dinamico i cui

elementi abbiamo una chiave in U = {0, . . ., m − 1};

Supponiamo inoltre che due elementi non possono avere

la stessa chiave.

Rappresentiamo l’insieme dinamico utilizzando un array, o

tabella ad indirizzamento diretto,

[0, . . . , − 1], in cui ogni posizione (slot) corrisponde

||).

( =

ad una chiave dell’universo Abbiamo una corrispondenza biunivoca tra chiavi e posizioni della

.

tabella: l’elemento con chiave è memorizzato nella cella

Le operazioni di ricerca, inserimento e cancellazione sono facili da implementare ed hanno un costo

(1).

computazionale costante

Tuttavia con questa modalità se è molto grande, implementare questa tabella può essere impraticabile, se

non addirittura impossibile. Di seguito sono riportati gli svantaggi:

Svantaggi:

• Preservare memoria sufficiente per quante sono le possibili chiavi

• Non si utilizza quando l’insieme U è troppo grande

• →

Se le chiavi usate sono una piccola parte di U memoria sprecata

• Prima di utilizzare una tabella ad indirizzamento diretto bisogna inizializzare tutti gli elementi a NIL

→ ()

Tempo

Grado di riempimento di una tabella ||

= / =

Misuriamo il grado di riempimento di una tabella introducendo il fattore di carico: dove

||

=

(dimensione della tabella) e (numero di chiavi effettivamente utilizzate)

Esempio: 6

= 100, = 10

tabella con nomi di studenti indicizzati da numeri di matricola a 6 cifre

→ = 0, 0001 = 0, 01%

Grande spreco di memoria!

Potrei ridurre l’occupazione di spazio con l’utilizzo di liste collegate. Tuttavia ciò comporterebbe un aumento

significativo del tempo richiesto per le operazioni viste precedentemente (inserimento, cancellazione e

(||) (1).

ricerca), infatti costerebbero invece che

Soluzione

L’utilizzo di tabelle Hash permette di trovare il giusto compromesso tra spazio e tempo.

2 - TABELLE HASH

Metodologia di implementazione che ha l’obiettivo di dimensionare (stabilire il valore della tabella) la tabella

in base al numero di elementi attesi utilizzando una speciale funzione (funzione hash) per indicizzare la

tabella stessa. ∈

Una funzione hash è una funzione che data una chiave restituisce la posizione della tabella in cui

l’elemento con chiave viene memorizzato. ||

||, <

N.B: la dimensione m della tabella può non coincidere con la anzi in generale (spazio minore

rispetto alla tabella ad indirizzamento diretto)

ℎ().

Con l’hashing un elemento con chiave viene memorizzato nella cella In questo modo riduciamo lo

spazio occupato dalla tabella, tuttavia perdiamo la corrispondenza tra indici e chiavi e introduciamo la

possibilità di avere delle collisioni.

Funzione hash:

Una buona funzione hash dovrebbe soddisfare l’ipotesi dell’HASHING UNIFORME SEMPLICE:

Ogni elemento ha la stessa probabilità di andare in ogni cella indipendentemente da dove vanno gli altri

elementi.

Metodi per creare buoni funzioni hash:

1. Metodo delle divisioni:

Consiste nell’inserire una chiave k in uno degli m slot della tabella calcolato come resto della divisione

di k per m.

() = (k numero naturale e m è la dimensione della tabella, la tabella va da 0 a m-1)

• Vantaggio: è un metodo veloce perché esegue solo un’operazione

• Svantaggio: evitare alcuni valori di m:

o Evitare potenze intere di 2 sarebbe meglio un numero primo non troppo vicino a

→

una potenza esatta di 2

2. Metodo delle moltiplicazioni

Alterativa al metodo delle divisioni

Consiste in 2 passi: (valore (0 < < 1)

1. Moltiplicare la chiave naturale) per una costante estraendo la parte

( ∗ )

frazionario di

2. Moltiplicare la parte frazionaria per m e prendere la parte inferiore del risultato

⌊(

() = ∗ )⌋

• Vantaggio: il valore di m non è critico, per esempio si può avere un m pari che esegue lo

stesso un hash uniforme e semplice

• Svantaggio: più lento del metodo delle divisioni

Problema delle collisioni:

Due chiavi e collidono quando corrispondono alla stessa posizione della tabella, ossia quando

1 2

) ).

ℎ( = ℎ(

1 2

SOLUZIONE: Esistono 2 approcci per risolvere le collisioni

1. Concatenamento

2. Indirizzamento aperto

1 – Concatenamento (1°modo per risolvere collisioni):

• Gli elementi che collidono vengono inseriti nella stessa posizione della tabella in una lista

concatenata.

• Si memorizza un puntatore alla testa della lista nello slot A[h] della tabella hash

• Operazioni:

o (1)

Insert: iserimento in testa, il tempo di esecuzione nel caso peggiore è

o Search: scandisce la lista per trovare la chiave. Viene eseguita nel caso peggiore nel tempo

→

() tutte le chiavi sono associate allo stesso slot.

o Delete: si presume che la chiave dell’elemento che si vuole eliminare sia presa con l’utilizzo

(1).

della Search() . Nel caso peggiore il tempo di esecuzione è

Problema tabella hash con concatenamento:

è una struttura dati che cambia spesso

Esempio di esercizio – concatenamento con metodo delle divisioni:

Analisi di hash con concatenamento:

Dobbiamo considerare il fattore di carico della tabella (α):

→

= indica il numero medio degli elementi memorizzati nella catena.

è il numero di elementi memorizzati nella tabella e è il numero di slot della tabella (numero di liste

collegate).

Alfa è il umero medio di elemnti in ogni lista collegata e si può avere i seguenti valori: α < 1, α=1 o α>1

Caso peggiore

Tutt le n chivi hanno hash nello stesso slot, si ha quindi una singola lista di lunghezza n

⇒ tempo: Θ(1) + Θ(n) = Θ(n)

Caso medio

Dipende dalla funzione hash, ogni elemento ha la stssa probabilità di andare in una delle m-1 posizioni

(1).

nell’ipotesi di hash uniforme e semplice. Si ha un calcolo della funzione hash in Verifichiamo i casi di

ricerca senza successo e con successo

• Ricerca senza successo (ricerco un valore che non è presente)

Bisogna accedere alla lista concatenata e scorrerla tutta fio alla fine. Ci interessa quindi sapere la

lunghezza della lista. Per esempio nell’esercizio sopra possiamo avere la fortuna di capitare nella lista

3 e scorro solo una volta ma se ho sfortuna posso capitare nella lista 8 e devo scorrere tutti i valori

concatenati.

⇒ (1 + ), con alfa lunghezza attesa

• Ricerca con successo

La probabilità di andare a cercare in una lista con successo è proporzionale al numero di elementi

nella lista. Piu elementi ci sono e piu è complicato cercare l’elemento.

(2 + − ) = (1 + )

Tempo totale (con calcolo funzione hash): 2 2

= () ⇒ = (1) ⇒ (1)

Se

IDIRIZZAMENTO APERTO (2° metodo per risolvere collisioni)

• Gli elementi sono memorizzati tutti nella stessa tabella hash (non si utilizza una lista concatenata)

• Ogni slot della tabella contiene una chiave o NIL

• →

Svantaggio: la tabella può riempirsi impedendo altri inserimenti fattore di carico non sarà mai α>1

• →

Vantaggio: si esclude i puntatori più memoria dedicata alla tabella; questo comporta