Appunti Algoritmi e strutture dati

HeapSort() {

BuildHeap(A);

for(i = A.length down to 2) { // Ordina partendo dal fondo

swap(A, 1, i);

A.heapsize --;

Heapify(A, 1);

}

}

// Complessità : O(log n) (che equivale al numero di volte che viene eseguito il

while)

MaxHeapInsert(H, k) {

if(H.heapsize < H.length) {

H.heapsize ++ ;

H[heapsize] = k;

i = H.heapsize;

if(i>0 && H[heapsize] > H[ Parent(i) ]) {

swap(H, i, Parent(i));

i = Parent(i);

}

}

}

// Complessità O(log n)

// Restituisce il massimo della heap, ovvero l'elemento che sta in posizione 1.

// Richiama la procedura Heapify per risistemare la Heap correttamente

MaxHeapExtract(H) {

max = H[1];

i = H.heapzize;

swap(H, 1, i);

H.heapzize --;

Heapify(H, 1); // Sistema al posto giusto la chiave

return max;

}

MaxHeapInsert(H, k) {

if(H.heapsize < H.length) {

H.heapsize ++ ;

H[heapsize] = k;

i = H.heapsize;

if(i>0 && H[heapsize] > H[ Parent(i) ]) {

swap(H, i, Parent(i));

i = Parent(i);

}

}

}

Heapify(H, i) {

p = max( H[Left(i)], H[Right(i)] ); // procedura che restituisce l'indice del

massimo tra i due figli

if(H[i] < H[p]) {

swap(H, i, p);

Heapify(H, p);

}

}

BuildHeap(A) {

A.heapsize = A.length;

for(i = A.heapsize/2 down to 1) { // O(log n) * Θ(n)

Heapify(A, i); // Heapify eseguita circa n/2 volte, quindi

Θ(n)

}

}

QuickSort(A, p, q) {

if(p < q) {

r = Partition(A, p, q); // r è l'indice di dove viene posizionato il perno

QuickSort(A, p, r); // T(m) : Non so con esattezza come viene partizionato

(difficilmente esattamente a metà)

QuickSort(A, r+1, q); // T(n-m-1)

}

}

Partition(A, p, q) {

i = p-1 // i punta all'ultimo elemento <= x

perno = A[q];

for( j=p to q ) {

if(A[j] <= perno) { // l'= mi permette di posizionare il perno in posizione

i (al termine)

i++;

swap(A, i, j);

}

}

return i; // Restituisce la posizione aggioranta del perno

}

/ Complessità: Θ(nlogn)

MergeSort(A, p, q) {

if(p < q) {

r = (p + q) / 2;

MergeSort(A, p, r);

MergeSort(A, r+1, q);

Merge(A, p, r, q);

}

}

// Si suppone che il vettore parta dall'indice 1

Merge(int[] A, int p, int r, int q) {

int[] B;

int i = p;

int j = r + 1;

int n = 0;

// Esrtrapolo gli elementi da A e li ordino in B

while( i <= r || j <= q ) {

if(A[i] < A[j]) {

B[n] = A[i];

i++;

} else {

B[n] = A[j];

j++;

}

n++;

}

// Copio le restanti chiavi in B

while(i <= r) {

B[n] = A[i];

n++;

}

while (j <= q) {

B[n] = A[j];

n++;

}

i = p;

// Copio il vettore B ordinato in A

for(int y = 0; y < B.length; y++) {

// if(i <= q) {

A[i] = B[y];

i++;

// }

}

}

Appunti Algoritmi e Strutture Dati

Red Black Tree :

Sono BST Bilanciati, dunque altezza Θ(log n). Grazie all’uso di rotazioni e ricolorazioni.

Inserimento, Ricerca e cancellazione costo O(log n)

Specifiche:

Ogni nodo ha un campo aggiuntivo color che può essere RED o BLACK.

- Le foglie sono NIL e sono tutte BLACK

- Ogni nodo RED ha due figli BLACK

- Per ogni nodo x lungo ogni cammino x – foglia si trova sempre lo stesso numero di

nodi BLACK (proprietà dei cammini neri)

- La radice è BLACK (opzionale)

Relazione : h < = 2bh

Inserimento:

- Si procede come nei BST. Si inseris ce il nuovo nodo “in basso”, foglia, sarà un

nodo con due figli nil.

- Attribuisco al nodo il colore RED.

- Se il nodo è figlio di un altro nodo RED cerco di risolvere il problema con rotazioni

e ricolorazioni.

- In ogni istante o risolvo il problema o sporto il problema verso l’alto, al più fino alla

radice. In quel caso semplicemente la ricoloro di nero e fine.

- Costo per 1 discesa (inserimento) + 1 salita per sistemare e bilanciare quindi Θ (log

n)

Cancellazione:

- Si procede come nei BST. Cerco il successore/predecessore.

- Tuttavia, se tolgo un nodo da dov’era (successore), se questo era BACK, ho creato un

problema nell’altezza nera.

Se RED era lo ricoloro BLACK e fine

o Se era BLACK devo colorarlo Double Black. Da quel lato ora ho POCO PESO,

o dunque devo eseguire una rotazione per portare del peso li e ribilanciare il tutto

B Tree:

Sono una generalizzazione dei BST e dei BRT. Sono una struttura dati per memorizzare

grandi quantità di dati e dunque non sta interamente in memoria centrale. Infatti necessità

di operazioni di Read e Write da memoria secondaria per accedere ai dati al suo interno.

Ogni nodo x ha le seguenti specifiche:

- x.n – intero, quante chiavi sono memorizzate in x

- x.leaf – bool, VERO sse x è una foglia

- x.key – vettore, contiene x.n chiavi

- x.c – vettore, contiene x.n + 1 puntatori ai figli di x

t è il grado del albero. Dipende dalla RAM

- Se x è la radice: 1 <= x.n <= 2t – 1

- altrimenti t - 1 <= x.n <= 2t – 1

Le chiavi che sono memorizzate nel vettore sono in ordine crescente

Tutte le foglie si trovano allo stesso livello

Altezza B Tree di grado t che contiene n chiavi?

h = logt (n + 1) / 2

Nei B Tree ci sono operazioni di:

- Lettura/Scrittura da memoria secondaria

- Di CPU (in memoria centrale)

Search : CPU O (t log n) – R/W O (log n)

Inserimento:

Quando scendo per inserire una chiave, se trovo un nodo troppo pieno (2t - 1) eseguo uno

Split. La chiave centrale sale sul nodo precedente e i due nodi che restano saranno di t – 1

chiavi, agganciati al nodo soprastante.

Lo split aumenta l’altezza dell’albero di 1 solo se viene splittata la radice, perché crea un

nuovo nodo sopra di se.

CPU O (t log n) - R/W Θ (log n)

Cancellazione:

duale dell’inserimento. Mentre scendo, se incontro un nodo con poche chiavi (t – 1) cerco

di aggiungergli chiavi. Controllo i suoi fratelli. Se hanno più di t – 1 chiavi, gli si toglie

una chiave, la passano al padre e il padre ne passa una al nodo con poche chiavi. Se nessun

fratello può fornire chiavi devo eseguire una Fusione. Due nodi vengono uniti e la chiave

del padre che sta tra i due scende diventando il mediano del nodo.

Per la cancellazione si procede come di consueto, con il predecessore o il successore.

CPU O (t log n) – R/W O (log n)

Insiemi Disgiunti:

- Make(x) : Costruisce un insieme singoletto

- Find(x) : Restituisce il rappresentante al quale x è collegato

- Union(x) : Unisce due insiemi

1. Implementazione con Liste di Adiacenza - Campi:

- x.key

- x.rap (puntatore al rappresentante)

- x.next

- x.last (solo nel rappresentante)

Costo : O(m + n^2)

Weighted Union:

Per evitare il caso peggiore si aggiunge un campo x.length (solo nel

rappresentante). Quando eseguo una union, accodo la lista più corta a quella più

lunga

Costo: O(m + n log n)

2. Implementazione con Alberi - Campi:

- x.parent

- x.key

O(n * m) e nel caso peggiore Θ (n * m)

Union by Rank:

Ottimizzazione. Memorizzo il rango dell’albero, in modo da unire l’albero più

piccolo al più grande. Un po’ come la weighted union. Così facendo faccio in modo

che gli alberi non si sbilancino e faccio cvrescere l’altezza solo se serve (se i due

alberi hanno la stessa altezza).

- x.rank (in ogni nodo)

Ora non si verificherà il caso peggiore

Utilizzando Union by Rank a partire da n operazioni make si ottengono alberi aventi

altezza O(log n)

Complessivamente: O(m) * O(h) = O(m * log n)

Path Compression:

Si fa in modo che le Find successive costino Θ (1). Quando eseguo una find, per i

nodi che incontro nel cammino x – radice, li faccio puntare alla radice. Si

comprime solo il cammino x – radice

Costo con Union by Rank e Path Compression: O(m * α(m, n))

( α(m, n)) cresce poco più di una costante )

Rango:

- Senza PC : Altezza dell’albero

- Con PC : Rango >= Altezza

BFS - O(| V | + | E | ) (Liste) --- O (V^2) (Matrici ADJ)

VISITA PER LIVELLI.

Algoritmo di ricerca per grafi che partendo da una sorgente cerca il cammino ad un altro

nodo. Espande il raggio d’azione, esaminando tutti i nodi del grafo sistematicamente.

Procedimento:

- Togliere dalla coda (nella prima iterazione il nodo s) ed esaminarlo

Se l’elemento cercato viene trovato lo restituisce (oppure si tiene traccia dei nodi

o visitati e dei predecessori) – si devono marcare i nodi visitati e non

Altrimenti mette in coda tutti i successori

o

- Se la coda è vuota significa che sono stati visitati tutti gli elementi altrimenti si ripete

il passo 2

Componenti:

- Lista Adj [u] che contiene la lista dei nodi adiacenti al nodo u

- color[u] indica lo stato del nodo (visitato, in corso, da visitare)

- d[u] distanza di u dalla sorgente s

BFS(G, s) {

for(each v appartenente V) {

d[v] = inf

PI[v] = NIL

}

Q = 0

color[s] = Grigio

Enqueue(Q, s)

while(Q != 0) {

u = head(Q)

for(each v appartenente ADJ(u)) {

if(color[v] == Bianco) {

color[v] = Grigio

d[v] = d[u] + 1

Enqueue(Q, v)

}

}

color[u] = Nero

Dequeue(Q, u)

}

}

DFS - Θ (| V | + | E |)

Generalizzazione VISITA Post Ordine

Parto da s. Seguo un cammino in Profondità e faccio back tracking quando mi serve (torno

indietro). Percorro un cammino più in profondità possibile, finche’ mi permette di scoprire

qualcosa di nuovo.

Devo memorizzare i tempi di inizio e fine visita.

Implemento con una pila (RICORSIONE). Quado non trovo più nulla guardo risalgo e

guardo in cima alla pila.

Il ciclo for della chiamata principale mi garantisce che comunque andrò a scandire tutti i

nodi del grafo.

DFS(G) {

for(each v appartenente V) {

d[v] = inf

PI[v] = NIL

}

TIME = 0

for(each v appartenente a V) {

if(color[v] == Bianco) {

TIME = DFS_Visit(G, v, TIME)

}

}

}

DFS_Visit(G, v, TIME) {

color[v] = Grigio

i[v] = TIME

TIME++

for(each u appartenente ADJ(v)) {

if(color[u] == Bianco) {

PI[u] = v

TIME = DFS_Visit(G, u, TIME)

}

}

f[v] = TIME

TIME++

color[v] = Nero

return TIME

}

La visita DFS permette di studiare particolari caratteristiche dei grafi come la presenza di

cicli.

- Back – Edge : arco da Grigio a Grigio

- Forward – Edge : arco da Grigio a Nero

- Cross – Edge

Minimum Spanning Tree (MST )

Minimizza il peso totale per connettere tutti i nodi.