Lez. 81 Universita' di Ferrara Facolta' di Scienze Matematiche, Fisiche e Naturali Laurea...

Lez. 8 1

Universita' di FerraraFacolta' di Scienze Matematiche, Fisiche e Naturali

Laurea Specialistica in Informatica

Algoritmi Avanzati

Grafi e Alberi

Copyright © 2006-2009 by Claudio Salati.

2

GRAFI

• Un grafo e' una coppia G = (V, E ) dove

• V = insieme non vuoto e finito di vertici (o nodi)

• E = insieme di lati

• Se il grafo e' orientato

• un lato e' una coppia ordinata di vertici (v, w), dove v e' chiamato coda e w testa

• un lato orientato puo' essere rappresentato come: v w

• e' (v, w) (w, v)

• possono esistere lati v v

• Se il grafo e' non orientato

• un lato e' una coppia non ordinata di vertici {v, w}

• un lato non orientato puo' essere rappresentato come: v w

• e' (v, w) = (w, v)

• non possono esistere lati v v

3

GRAFI

• Qui indicheremo comunque un lato come (v, w) indipendentemente dal fatto che il grafo sia o meno orientato

• E' POSSIBILE ASSOCIARE UN COSTO A CIASCUN LATO

• SE (v, w) E ALLORA SI DICE CHE w E' adiacente A v

• IN_DEGREE(v) E' IL NUMERO DI NODI A CUI v E' ADIACENTE

• OUT_DEGREE(v) E' IL NUMERO DI NODI ADIACENTI A v

• SE UN GRAFO E' NON ORIENTATO, PER TUTTI I SUOI NODI E':

IN_DEGREE = OUT_DEGREE

• Esercizio:

Quanti sono al massimo i lati di un grafo orientato con n nodi?

Quanti sono al massimo i lati di un grafo non orientato con n nodi?

4

GRAFI

• PATH: SEQUENZA DI NODI DELLA FORMA

(v[1], v[2]), (v[2], v[3]), ..., (v[n-1], v[n])

dove (vj, vk) e' un lato del grafo

• PATH DA v[1] A v[n]

• PATH DI LUNGHEZZA (n-1)

• TRA UN NODO E SE STESSO C'E' SEMPRE UN PATH DI LUNGHEZZA 0

• PATH SEMPLICE:

• SENZA CICLI, O AL MASSIMO CON v[1]=v[n],

• SENZA PASSARE 2 VOLTE SULLO STESSO LATO/NODO

• CICLO: PATH SEMPLICE CON v[1]=v[n] E LUNGHEZZA 1

• LUNGHEZZA MINIMA DI UN CICLO IN UN GRAFO NON ORIENTATO: 3

5

RAPPRESENTAZIONE DI GRAFI - 1'

• MATRICE DELLE ADIACENZE:

• BOOLEAN adjacency [# V ][# V ]

• int adjacency [# V ][# V ]

PER TENERE CONTO DEL COSTO DEI LATI

• COMPLESSITA' SPAZIALE: (# V )2

• QUALUNQUE SIA IL NUMERO DEI LATI,

• CHE POTENZIALMENTE E' <<(# V )2

• N.B.: la struttura della matrice delle adiacenze e' congruente con il fatto che il numero massimo di lati in un grafo orientato e' pari a (# V )2

• ANCHE LA COMPLESSITA' TEMPORALE DI QUALSIASI ALGORITMO CHE USI QUESTA STRUTTURA DATI SARA' (# V )2

SE DEVE INIZIALIZZARE L'ARRAY!

6

RAPPRESENTAZIONE DI GRAFI - 1"• Se voglio scandire tutti e soli i lati uscenti dal nodo j basta che

cerchi nella riga j gli elementi con valore TRUE: l'operazone ha costo O(# V )

• Se voglio scandire tutti e soli i lati entranti nel nodo j basta che cerchi nella colonna j gli elementi con valore TRUE: l'operazone ha costo O(# V )

• Matrice delle adiacenze per un grafo non orientato:

• la matrice e simmetrica:

il lato (j, k) e' presente (adjacency[j][k]=TRUE) se e solo se e' presente anche il lato ((k, j) (adjacency[k][j]=TRUE)

• tutti gli elementi della diagonale principale sono FALSE:

il lato (k, k) non puo' essere presente

• questo conferma che in un grafo non orientato con n nodi ci sono al massimo n*(n-1)/2 lati: gli elemeti diagonali e quelli della parte inferiore sono non significativi!

7

RAPPRESENTAZIONE DI GRAFI - esempio

BOOLEAN adjacency [4][4] =

{ { 0, 1, 0, 1 }, // lati 0 x { 0, 0, 1, 0 }, // lati 1 x { 0, 0, 0, 0 }, // lati 2 x { 0, 1, 1, 0 }, // lati 3 x };

0 1

3 2

8

RAPPRESENTAZIONE DI GRAFI - 2'

• INSIEME DEI NODI

• CIOE' LISTA DEI NODI

• INSIEME DEI LATI,

• CIOE' LISTA DEI LATI,

• CIOE' LISTA DELLE COPPIE (vj, vk)

• COMPLESSITA' SPAZIALE: O(# V + # E )

• IN UN GRAFO INDIRETTO OGNI LATO COMPARE 2 VOLTE, SIA COME (v, w) CHE COME (w, v)

• NELLA MATRICE DELLE ADIACENZE I DUE LATI SONO COLLEGATI ALGORITMICAMENTE:

E[v][ w] == E[w][v]

• NELLA LISTA DELLE ADIACENZE LA CORRELAZIONE DEVE ESSERE REALIZZATA CON UN RIFERIMENTO ESPLICITO

9

RAPPRESENTAZIONE DI GRAFI - 2"

• IN UN GRAFO E' SPESSO CONVENIENTE POTERE CANCELLARE LATI E NODI

• PERCIO' E' CONVENIENTE CHE NELLA RAPPRESENTAZIONE A LISTA DI ADIACENZE CI SIA IL DOPPIO LINK AVANTI E INDIETRO,

COSI' DA POTERE CANCELLARE ELEMENTI RANDOM IN TEMPO COSTANTE

(SPECIE NEL CASO DI GRAFI NON ORIENTATI DOVE OGNI LATO HA IL DUALE, E QUESTI SONO TRA LORO CORRELATI)

10

RAPPRESENTAZIONE DI GRAFI - esempiotypedef struct node *refNode;

typedef struct edge *refEdge;

struct node { char *name; refNode lLink; // doppio link della lista refNode rLink; // dei nodi refEdge fromOf; // lista dei lati uscenti refEdge toOf; // lista dei lati entranti };

struct edge { refNode fromNode; // rif. al nodo coda del lato refNode toNode; // rif. al nodo testa del lato refEdge lLink; // doppio link della lista refEdge rLink; // dei lati refEdge fromListLLink; //doppio link lista lati usc- refEdge fromListRLink; //enti dallo stesso nodo coda refEdge toListLLink; // doppio link lista lati entr- refEdge toListRLink; // anti nello stesso nodo testa };

11

RAPPRESENTAZIONE DI GRAFI - esempio

nodi

"0"

"1"

"2"

"3"

lati

NULL

NULL

12

ALBERO

• UN ALBERO (NON ORDINATO) E':

• UN INSIEME DI VERTICI O NODI: V

• UNA FUNZIONE TOTALE CHILD: V POWERSET( V )

TALE CHE: n1n2 CHILD(n1) CHILD(n2)=

! NODO n0 (DETTO RADICE) | n V : n0 CHILD(n)

• ( n V | nn0) ! m V | n CHILD(m)

n V ( {m1, ..., mN} n = m1 mN = m

mi+1 CHILD(mi)

n CHILD(m))

• UN NODO n PER CUI CHILD(n) = E' DETTO FOGLIA

13

ALBERI E GRAFI

• UN ALBERO E' UN GRAFO IN CUI ESISTE IL LATO (n, m) SE

m CHILD(n)

• Un albero e' un grafo

• ORIENTATO

• ACICLICO

• IN CUI IN OGNI NODO DIVERSO DALLA RADICE ENTRA UNO ED UN SOLO LATO

n V | n n0 : IN_DEGREE(n)=1

• MENTRE IN_DEGREE(RADICE)=0

(la radice e' l'elemento minimo del grafo)

• C'E' UNO ED UN SOLO PATH TRA LA RADICE ED OGNI ALTRO NODO

Esercizio: come si dimostra?

• FORESTA: UN GRAFO CHE E' UN INSIEME DI ALBERI

14

ALBERO: relazioni tra i nodi

• SE m CHILD(n) ALLORA

• m E' FIGLIO DI n

• n E' PADRE DI m

• SE C'E' UN PATH DA n A m ALLORA

• m E' UN DISCENDENTE DI n

• n E' UN ANTENATO DI m

• OVVIAMENTE UN NODO E' SEMPRE DISCENDENTE ED ANTENATO DI SE STESSO, PERO' E' UNA RELAZIONE NON PROPRIA

• UN NODO E TUTTI I SUOI DISCENDENTI SONO DETTI UN SOTTOALBERO

15

ALBERO: profondita', altezza, livello

• LA PROFONDITA' (DEPTH ) DI UN NODO E' LA LUNGHEZZA

DEL PATH DALLA RADICE AL NODO

• L'ALTEZZA DI UN NODO E' LA LUNGHEZZA DEL PATH PIU'

LUNGO DAL NODO AD UNA FOGLIA SUA DISCENDENTE

• L'ALTEZZA DI UN ALBERO E' L'ALTEZZA DELLA RADICE

• IL LIVELLO DEL NODO n E' L'ALTEZZA DELL'ALBERO MENO

LA PROFONDITA' DI n

• N.B.:

• La profondita’ di un nodo e’ determinata solo dalla parte di

albero che costituisce il path dalla radice al nodo.

• L’altezza di un nodo e’ determinata solo dalla parte dell’albero

costituita dal sottoalbero che ha il nodo come radice.

• Il livello di un nodo dipende da tutto l’albero!

16

ALBERO: profondita', altezza, livello

4

3 2

2 0 1

0 1 0 0

0 0

Profondita' Livello

4 0

3 1

2 2

1 3

0 4

All'interno dei nodi e' indicata la loro altezza

17

ALBERO BINARIO

• UN ALBERO E' ORDINATO SE I FIGLI DI OGNI NODO SONO ORDINATI (e.g. DA SINISTRA A DESTRA)

• UN ALBERO BINARIO E':

• UN ALBERO ORDINATO

• OGNI NODO HA AL PIU' 2 FIGLI

• I FIGLI DI UN NODO SONO DISTINTI IN

• FIGLIO SINISTRO

• FIGLIO DESTRO

E UN NODO HA NON PIU' DI UN FIGLIO SINISTRO E NON PIU' DI UN FIGLIO DESTRO

• IN UN ALBERO BINARIO SI POSSONO OVVIAMENTE DISTINGUERE SOTTOALBERI DI SINISTRA E DI DESTRA

• se un nodo ha un unico figlio si puo' distinguere se questo e' di sinistra o di destra

18

ALBERO BINARIO - visione ADT

albero binario (definizione ricorsiva):

un albero vuoto

una radice con al piu' due figli

radici di sottoalberi binari

distinguibili come di-sinistra e di-destra

un albero binario sara' denotato come la tripla ordinata

[e, ts, td]

dove

e indica l'elemento (il valore) associato al nodo radice dell'albero

ts indica il sottoalbero di sinistra (della radice) dell'albero

td indica il sottoalbero di destra (della radice) dell'albero

ts e/o td possono ovviamente essere un albero vuoto

19


operazioni primitive sull'ADT albero binario:

costruttori

NULL o EMPTYTREE Tree

denota un albero vuoto.

constree()

Element Tree Tree Tree

dato un elemento E e due alberi T1 e T2 (eventualmente vuoti) restituisce l'albero [E, T1, T2]

precondizioni: nessuna

20


operazioni primitive sull'ADT albero binario (continua):

predicati

emptyt()

Tree BOOLEAN

dato un albero T, restituisce TRUE o FALSE a seconda che T sia o meno vuoto

precondizioni: nessuna

selettori

root()

Tree Element

dato un albero non vuoto T=[E, T1, T2] ne restituisce l'elemento radice E

precondizioni: !emptyt(T)

21


operazioni primitive sull'ADT albero binario (continua):

selettori (continua)

left()

Tree Tree

dato un albero non vuoto T=[E, T1, T2] ne restituisce il sottoalbero di sinistra T1 (eventualmente vuoto)


right()

Tree Tree

dato un albero non vuoto T=[E, T1, T2] ne restituisce il sottoalbero di destra T2 (eventualmente vuoto)


22

ALBERO BINARIO - visione ADT assiomi

1. ├ emptyt(EMPTYTREE) o emptyt(NULL)2. ├ !emptyt(constree(e, t1, t2))

3. ├ root(constree(e, t1, t2)) == e

4. ├ left(constree(e, t1, t2)) == t1

5. ├ right(constree(e, t1, t2)) == t2

la definizione dell'ADT e' funzionale e costruttiva (vedi assiomi 4 e 5):

un valore Tree non viene mai modificato da nessuna operazione (infatti non ci sono trasformatori)

ovviamente avremmo potuto definire un ADT albero binario in modo diverso

23

ALBERO BINARIO - visione ADT: implementazione

struct Node {elemento value; struct Node *sin; struct Node *des; };

typedef struct Node *Tree;

#define EMPTYTREE NULL

Boolean emptyt (Tree t) { return (t == EMPTYTREE);}

elemento root (Tree t) { assert(!emptyt(t)); return (t->value);}

24

ALBERO BINARIO - visione ADT: implementazione

Tree left (Tree t) { assert(!emptyt(t)); return (t->sin);}

Tree right (Tree t) { assert(!emptyt(t)); return (t->des);}

Tree constree (elemento el, Tree t1, Tree t2) { Tree t = malloc(sizeof(struct Node)); t->value = el; t->sin = t1; t->des = t2; return t;}

25

ALBERO BINARIO - visione ADT: esempio d'uso

• Scrivere una funzione che ritorna il numero di nodi contenuto nell'albero passatole in ingresso

int findWeight(Tree t) { return( emptyt(t) ? 0 : findWeight(left(t)) + findWeight(right(t)) + 1 );}

26

ALBERO BINARIO - visione ADT: esempio d'uso

• Inserisce in-ordine un nuovo elemento in un albero in cui tutti gli elementi sono registrati in-ordine

• Un elemento e' presente nell'albero al piu' una volta.

Tree insord(Tree t, elemento el) { // P = { el t } if (emptyt(t)) return constree(el, EMPTYTREE, EMPTYTREE); else if (lessThan(el, root(t))) return constree(root(t), insord(left(t), el), right(t)); else // greaterThan(el, root(t)) return constree(root(t), left(t), insord(right(t), el));}

27

ALBERO BINARIO - visione ADT: esercizi

• Consideriamo (come nell'esempio della funzione insord()) un albero binario in cui gli elementi sono registrati nei nodi in in-ordine

• scrivere 3 funzioni:

elemento min(Tree t);

elemento max(Tree t);

Boolean isPresent(elemento el, Tree t);

• la prima che ritorna l'elemento minimo di un albero non vuoto,

• la seconda che ritorna l'elemento massimo di un albero non vuoto, e

• la terza che verifica se un elemento dato e' presente o meno nell'albero (non necessariamente non vuoto)

28

ALBERO BINARIO - visione ADT: esercizi

• Consideriamo un albero binario in cui gli elementi sono registrati nei nodi in in-ordine

• scrivere 3 funzioni:

Tree deleteMin(Tree t);

Tree deleteMax(Tree t);

Tree delOrd(elemento el, Tree t);

• la prima che cancella l'elemento minimo di un albero non vuoto,

• la seconda che cancella l'elemento massimo di un albero non vuoto, e

• la terza che cancella un elemento dato presente nell'albero

• In ogni caso ogni funzione ritorna un albero in-ordine con gli stessi elementi di quello in input ma privo dell'elemento cancellato

29

Rappresentazione di Alberi (n-ari)

• E' BENE CHE OGNI NODO SIA RAPPRESENTATO DA UN DESCRITTORE DI STRUTTURA FISSA, INDIPENDENTEMENTE DAL NUMERO DEI SUOI FIGLI.

• IN UN ALBERO N-ARIO OGNI NODO RIFERISCE:– UN SOLO FIGLIO, il primogenito (un solo elemento di

CHILD)– UN SOLO FRATELLO, il successivo

• per realizzare il doppio link avanti-indietro occorre:– MANTENERE IN OGNI NODO L'INVERSO DELLA

RELAZIONE CHILD– MANTENERE LA LISTA DEI FRATELLI COME UNA LISTA

DOPPIAMENTE LINKATA

• IN QUESTO MODO E' POSSIBILE:– MUOVERSI LUNGO L'ALBERO IN ENTRAMBE LE

DIREZIONI (alto/basso)– INSERIRE E CANCELLARE UN NODO (foglia) IN UN

ALBERO IN TEMPO COSTANTE

30

Rappresentazione di Alberi (n-ari): esempio

1

2 3

6 7 8 9 10 11

4 5

12 13 14

figlio (relazione logica, rappresentata in modo indiretto)

figlio primogenito

fratello

31


figlio-1 (parent)

figlio primogenito

fratello

1

2 3

6 7 8 9 10 11

4 5

12 13 14

32


typedef struct node *tree;struct node { char *name; tree firstChild; tree parent; tree lBrother; tree rBrother; };

• la struttura dati e' molto semplificata rispetto al caso generale di un grafo

• esiste un punto di ingresso primario nell'albero: la radice

• ogni nodo ha un solo lato entrante

• la descrizione dei lati puo' essere collassata dentro quella dei nodi:

ogni nodo coda tiene la lista dei nodi testa dei lati che escono da lui (la relazione child)

33

Rappresentazione di Alberi Binari

• SI PUO' MIGLIORARE ANCORA LA RAPPRESENTAZIONE RISPETTO A QUELLA DEGLI ALBERI N-ARI, PERCHE' IN QUESTO CASO SI PUO' DARE UN LIMITE A PRIORI AL NUMERO DI FIGLI,

• CIO' E' ANCHE NECESSARIO PERCHE' I FIGLI DEVONO ESSERE DISTINTI IN SINISTRI E DESTRI

• E SE C'E' UN SOLO FIGLIO BISOGNA DISTINGUERE SE QUESTO E' UN FIGLIO SINISTRO O DESTRO

typedef struct binNode *binTree;

struct binNode { char *name; binTree leftChild; binTree rightChild; binTree parent; };

34


• MA IN REALTA', PER ALBERI COMPLETI (O QUASI) SI PUO' FARE ANCHE DI MEGLIO, ELIMINANDO OGNI RIFERIMENTO ESPLICITO:

• L'ALBERO E' RAPPRESENTATO IN UN ARRAY LINEARE

node binTree[n]

• I FIGLI DEL NODO DI INDICE i SI TROVANO NELLE POSIZIONI: 2*i+1 E 2*i+2

• IL FIGLIO DI SINISTRA IN POSIZIONE 2*i+1, E QUELLO DI DESTRA IN POSIZIONE 2*i+2

• IL PADRE DEL NODO DI INDICE i SI TROVA IN POSIZIONE: (i-1)/2 (divisione intera!)

• LA RADICE E' NELLA POSIZIONE 0

35


• UN ALBERO BINARIO E' COMPLETO SE ESISTE UN NUMERO k PER CUI

– TUTTI I NODI DI PROFONDITA' <k HANNO ENTRAMBI I FIGLI

– I NODI DI PROFONDITA' k SONO FOGLIE

• UN ALBERO BINARIO COMPLETO DI PROFONDITA' k HA 2k+1 - 1 NODI E, DI QUESTI, 2k SONO FOGLIE

(la dimostrazione per induzione matematica e` facile, specie partendo dal secondo punto, ed e' lasciata per esercizio)

• LA RAPPRESENTAZIONE IN ARRAY LINEARE E' BUONA PURCHE' L'ALBERO SIA ALMENO QUASI PIENO:

– ESISTONO FOGLIE ANCHE DI PROFONDITA' k-1

– LE FOGLIE DI PROFONDITA' k-1 SONO I NODI PIU' A DESTRA DI QUELLA PROFONDITA'

36

ALBERI BINARI: DIMENSIONE E PROFONDITA'

• ALTEZZA E PROFONDITA' SONO LEGATE AL NUMERO DI ELEMENTI DELL'ALBERO DALLA RELAZIONE "logaritmo"

• CIO' SIGNIFICA CHE POSSIAMO RAGGIUNGERE UNA FOGLIA IN UN TEMPO LOGARITMICO RISPETTO AL NUMERO DI NODI DELL'ALBERO

• E' PER QUESTO CHE GLI ALBERI SONO COSI' EFFICIENTI PER RAPPRESENTARE INSIEMI E/O SEQUENZE DI OGGETTI QUANDO LE OPERAZIONI CHE VOGLIAMO COMPIERE SU TALI INSIEMI E/O SEQUENZE SONO OPERAZIONI SUL SINGOLO ELEMENTO:

• INSERZIONE

• CANCELLAZIONE

• RICERCA

• RICERCA DEL MINIMO O DEL MASSIMO

37

VISITA DI UN ALBERO

• LA VISITA DI UN ALBERO E' DEFINITA RICORSIVAMENTE PER LA RADICE ED I SUOI SOTTOALBERI.

• PUO' AVVENIRE SECONDO DIVERSE DISCIPLINE

• PRE-ORDINE:

VISITO PRIMA LA RADICE POI, SEQUENZIALMENTE (e ricorsivamente), CIASCUNO DEI SUOI SOTTOALBERI

• POST-ORDINE:

VISITO PRIMA, SEQUENZIALMENTE (e ricorsivamente), CIASCUN SOTTOALBERO DELLA RADICE, E POI LA RADICE STESSA DELL'ALBERO

• IN-ORDINE (SOLO PER ALBERI BINARI):

VISITO PRIMA IL SOTTOALBERO SINISTRO DELLA RADICE, POI LA RADICE, POI IL SUO SOTTOALBERO DESTRO

38

VISITA DI UN ALBERO

• DURANTE LA VISITA POSSO NUMERARE I NODI DELL'ALBERO:

1

2 6

3 5 7

4 8

8

4 7

2 3 6

1 5

5

3 8

1 4 6

2 7

pre-ordine post-ordine in-ordine

39

PROPRIETA' DELLE NUMERAZIONI

• PRE-ORDINE:

• TUTTI I DISCENDENTI HANNO NUMERO MAGGIORE DEI LORO ANTENATI

• SE IL NODO n HA d DISCENDENTI, QUESTI SONO NUMERATI DA n+1 A n+d

• SE SI CONOSCE IL NUMERO DI UN NODO ED IL NUMERO DEI SUOI DISCENDENTI SI PUO' DECIDERE IN TEMPO COSTANTE SE UN NODO QUALSIASI E' DISCENDENTE DI QUEL NODO

(cioe' SE IL SUO NUMERO E' COMPRESO TRA n+1 E n+d)

• POST-ORDINE:

• VALGONO PROPRIETA' DUALI

40


• IN-ORDINE:

• OGNI DISCENDENTE SINISTRO HA NUMERO MINORE DEL NODO,

• OGNI DISCENDENTE DESTRO HA NUMERO MAGGIORE DEL NODO.

• Un nodo del sottoalbero sinistro del nodo N ha numero compreso tra N-1 e N-#(sottoalbeto sinistro).

• Un nodo del sottoalbero destro del nodo N ha numero compreso tra N+1 e N+#(sottoalbeto destro).

41


• IN-ORDINE:

E' UNA MANIERA TIPICA DI MEMORIZZARE STRINGHE

INSERENDOLE NELL'ALBERO IN MODO CHE RISPETTINO L'IN-ORDINE

SE POI VISITIAMO IN IN-ORDINE L'ALBERO RITROVIAMO LE STRINGHE IN ESSO REGISTRATE IN ORDINE ALFABETICO

SE VOGLIO CERCARE IL NODO i NELL'ALBERO (NON SO SE C'E') GUARDO LA RADICE r:

1. SE r=i HO TROVATO

2. SE r>i DEVO CERCARE i NEL SOTTOALBERO SINISTRO DI r, SE QUESTO NON E' VUOTO. COMUNQUE, SE NON E' LI' NON E' NELL'ALBERO

3. SE r<i DEVO CERCARE i NEL SOTTOALBERO DESTRO DI r, SE QUESTO NON E' VUOTO. COMUNQUE, SE NON E' LI' NON E' NELL'ALBERO

42

PROCEDURE DI VISITA: pre-order

typedef struct binNode *binTree;

struct binNode { int givenNo; int size; binTree leftChild; binTree rightChild; binTree parent; };

int preOrder (binTree root, int number) { // root : radice del sottoalbero non vuoto che // si vuole visitare assert(root!=NULL); // preorder numera in preordine i nodi dell' // albero root (nel campo givenNo) a // partire dal numero number, e ritorna la // dimensione dell'albero // continua alla prossima pagina

43

PROCEDURE DI VISITA: pre-order

root->givenNo = number; int kids = (root->leftChild != NULL) ? preOrder(root->leftChild, number+1) : 0; kids += (root->rightChild != NULL) ? preOrder(root->rightChild, number+1+kids) : 0; return (root->size = kids + 1);}

44

PROCEDURE DI VISITA: post-order

int postOrder (binTree root, int number) {

assert(root!=NULL);

int kids =

(root->leftChild != NULL) ?

postOrder(root->leftChild, number)

: 0;

kids +=

(root->rightChild != NULL) ?

postOrder(root->rightChild,

number+kids)

: 0;

root->givenNo = number + kids;

return (root->size = kids + 1);

}

45

PROCEDURE DI VISITA: in-order

int inOrder (binTree root, int number) {

assert(root!=NULL);

int kids =

(root->leftChild != NULL) ?

inOrder(root->leftChild, number)

: 0;

root->givenNo = number + kids;

kids +=

(root->rightChild != NULL) ?

inOrder(root->rightChild,

number+kids+1)

: 0;

return (root->size = kids + 1);

}

46

RICORSIONE

• QUANTO COSTA?

• QUANTO COSTA UNA CHIAMATA DI PROCEDURA?

• DI PER SE STESSA L'ISTRUZIONE CALL HA COSTO COSTANTE

• POI DIPENDE DAI PARAMETRI CHE SONO PASSATI:

• SE UNO PASSA OGGETTI DI DIMENSIONE COSTANTE CON LA DIMENSIONE DEL PROBLEMA (e.g. INDIRIZZI DI ARRAY) LA CHIAMATA E' IN TEMPO COSTANTE,

• MA SE PASSA OGGETTI DI DIMENSIONE CORRELATA CON LA DIMENSIONE DEL PROBLEMA LA CHIAMATA STESSA E' DI COMPLESSITA' LINEARE CON LA DIMENSIONE DEL PROBLEMA

• IL COSTO DELLA CHIAMATA E' ADDEBITATO AL CHIAMANTE

• POI C'E' IL COSTO DI ESEGUIRE LA PROCEDURA CHIAMATA

• SE QUESTA NON E' RICORSIVA LA COMPLESSITA' SI CALCOLA FACILMENTE,

MA SE E' RICORSIVA?

47

COMPLESSITA' DELLA VISITA DI UN ALBERO

• VISITO UN ALBERO BINARIO DI ALTEZZA n.

IL COSTO T(n) DI QUESTA VISITA E'

T(n) = 2 * T(n-1) + C

CIOE' 2 VOLTE IL COSTO DI VISITARE UN (SOTTO-) ALBERO DI ALTEZZA (n-1) PIU' IL COSTO (COSTANTE) DELLA VISITA DELLA RADICE

• SE L'ALBERO HA ALTEZZA 0 DEVO VISITARE SOLO LA RADICE E

T(0) = C

• ALLORA IL COSTO DELLA VISITA E' ESPRIMIBILE CON UNA RELAZIONE RICORSIVA:

T(n) = 2*T(n-1) + C

T(0) = C{

48

COMPLESSITA' DELLA VISITA DI UN ALBERO

• COME FACCIO A RISOLVERE LA RELAZIONE RICORSIVA DANDO LA FORMA CHIUSA DI T(n)?

• NEL NOSTRO CASO NOI SAPPIAMO CHE

• OGNI NODO E' VISITATO UNA SOLA VOLTA, E CHE

• UN ALBERO DI ALTEZZA n HA 2n+1-1 NODI (in realta' O(2n+1-1) nodi),

ERGO SARA'

T(n) = (2n+1 - 1) * C

• INFATTI, PER INDUZIONE MATEMATICA:

• T(0) = C

• T(n+1) = 2 * ((2n+1 - 1) * C) + C

= 2n+2 * C - 2 * C + C

= (2(n+1)+1 - 1) * C

49

CORRETTEZZA DELLE VISITE

• CONSIDERIAMO AD ESEMPIO PREORDER

• PER INDUZIONE SULL'ALTEZZA DELL'ALBERO

• HP INDUTTIVA: la radice e` numerata correttamente secondo il "numero" dato e la funzione ritorna la dimensione del sotto-albero

• SE L'ALTEZZA DELL'ALBERO E' 0 ALLORA LA RADICE E' NUMERATA CON IL VALORE number E LA FUNZIONE RITORNA 1 PERCHE' LA RADICE E' UNA FOGLIA (ALTRIMENTI NON SAREBBE AD ALTEZZA 0)

• SE L'ALTEZZA DELL'ALBERO E' (H+1) E SI SUPPONE CHE LA PROCEDURA OPERI CORRETTAMENTE PER TUTTI GLI ALBERI DI ALTEZZA H ALLORA;

• LA RADICE E' NUMERATA CORRETTAMENTE A number

• SE C'E' IL SOTTOALBERO SINISTRO E' NUMERATO CORRETTAMENTE DA number+1 E kids E' LA SUA DIMENSIONE (PER INDUZIONE MATEMATICA DATO CHE IL SOTTOALBERO E' DI ALTEZZA H, E number E' STATO INCREMENTATO DI 1 NELLA CHIAMATA RICORSIVA)

• ANALOGAMENTE PER IL SOTTOALBERO DESTRO

• E QUINDI ANCHE PER L'ALBERO DI ALTEZZA (H+1)

50

ESERCIZIO• Scrivere le procedure per la visita in pre- ed in post-ordine di un

albero n-ario descritto tramite la seguente struttura dati:

typedef struct node *tree;

struct node { char *name; int givenNo; int size; tree firstChild; tree nextBrother; };

• Si possono implementare 2 versioni delle procedure indicate:• la prima versione si basa solo sulla ricorsione, anche per la scansione

della lista dei fratelli;• la seconda si basa sulla ricorsione per la visita di ciascun (sotto-)

albero, ma sull'iterazione per la scansione della lista dei fratelli

• In ogni caso, ogni funzione ritorna il numero complessivo di nodi del o dei sotto-alberi che ha visitato

51

ESERCIZIO: pre-order - 1

int preOrder_1 (tree root, int number) {

assert(root != NULL);

root->givenNo = number;

root->size =

1 +

(root->firstChild != NULL ?

preOrder_1(root->firstChild, number+1)

: 0);

return(root->size +

(root->nextBrother != NULL ?

preOrder_1(root->nextBrother,

number + root->size)

: 0);

}

52


int preOrder_2 (tree root, int number) {

// visita un nodo e tutto e solo il suo

// sottoalbero


root->givenNo = number;

root->size =

1 +


preOrderF(root->firstChild, number+1)

: 0);

return(root->size);

}

53


int preOrderF(tree root, int number) {

// visita un nodo che e' figlio primogenito,

// tutto il suo sottoalbero, e tutti

// i sottoalberi suoi fratelli

int nodes = preOrder_2(root, number);

tree t = root->nextBrother;

while (t != NULL) {

nodes += preOrder_2(t, number + nodes);

t = t->nextBrother;

}

return(nodes);

}

54

ESERCIZIO: post-order - 1

int postOrder_1 (tree root, int number) {


root->size =

1 +


postOrder_1(root->firstChild, number)

: 0);

root->givenNo = number + root->size - 1;

return(root->size +

(root->nextBrother != NULL ?

postOrder_1(root->nextBrother,

number + root->size)

: 0);

}

55

ESERCIZIO : post-order - 2

int postOrder_2 (tree root, int number) {

// visita un nodo e tutto e solo il suo

// sottoalbero


root->size =

1 +


postOrderF(root->firstChild, number)

: 0);

root->givenNo = number + root->size - 1;

return(root->size);

}

56

ESERCIZIO : post-order - 2

int postOrderF(tree root, int number) {

// visita un nodo che e' figlio primogenito,

// tutto il suo sottoalbero, e tutti

// i sottoalberi suoi fratelli

int nodes = postOrder_2(root, number);

tree t = root->nextBrother;

while (t != NULL) {

nodes += postOrder_2(t, number + nodes);

t = t->nextBrother;

}

return(nodes);

}

57

VISITE ITERATIVE

• visita in preordine dell'albero

iterativa

• come ricordarsi le informazioni che nel caso della ricorsione sono memorizzate nello stack dei record di attivazione?

• su uno stack!

• quale informazione occorre ricordarsi?

• il sotto-albero che rimane da scandire al termine della scansione del sottoalbero che si inizia a scandire in questo momento

• ci si basa sull'utilizzo del dato astratto stack

58

Dato astratto Stack operazioni

StackInit stack inizializza lo stack a stack vuoto (StackEmpty()=TRUE) precondizioni: nessuna

StackEmpty stack BOOLEAN ritorna TRUE se e solo se lo stack e' vuoto precondizioni: nessuna

StackPush stack elemento stack dato l'elemento E lo inserisce sullo stack precondizioni: nessuna

StackPop stack elemento estrae l'elemento sul top dello stack e lo ritorna al cliente precondizioni: !StackEmpty()

59

Dato astratto Stack assiomi:

– ├ StackInit(); StackEmpty() == TRUE;– ├ StackPush(e); StackEmpty() == FALSE;– ├ StackPush(e); e == StackPop();

interfaccia programmatica (API)

– void StackInit(void);– Boolean StackEmpty(void);– void StackPush(elemento e);– elemento StackPop(void);

per la nostra applicazione elemento deve coincidere con il tipo Tree

ogni operazione ha un parametro implicito: lo stack stesso stackInit() e' definita come: stack, e non come: stackstack,

perche' e' di norma utilizzata per inizializzare uno stack. Prima di essere inizializzato uno stack non e' uno stack ma solo un ammasso di byte

60

VISITE ITERATIVE: pre-ordine

void preorder (Tree t){ while (!(emptyt(t) && StackEmpty())) { if (!(emptyt(t)) { writeVal(root(t)); StackPush(right(t)); t = left(t); } else { t = StackPop(); } }}• come si dimostra la correttezza?

• e se si dovesse anche numerare i nodi dell'albero e registrare in ogni nodo la dimensione del sottoalbero di cui e' la radice?

61

VISITE ITERATIVE: esercizio

• Scrivere le procedure iterative per la visita

• in post-ordine

• in in-ordine

ad un albero binario.

• Queste procedure devono basarsi sull'utilizzo del dato astratto stack, ma il tipo elemento dovra' essere definito opportunamente a seconda dei casi.

• Vedi anche le dispense di Universita' di Bologna (Cesena)

62

Ricorsione vs. Iterazione

• Quando e' importante sfruttare la ricorsione?

• Quando il chiamante, al momento della chiamata ricorsiva, deve tenere memorizzate molte informazioni

• variabili locali• stato di avanzamento della propria esecuzione (Program

Counter)

• Confrontare ad esempio:• scansione di una lista• scansione di un albero binario ordinato per identificarne

l'elemento minimo• visita di un albero binaro in pre-ordine• visita di un albero binaro in post-ordine

• La quantita' di informazione da tenere memorizzata e' via via crescente (dopo i primi due casi) e quindi l'utilizzo della ricorsione sempre piu' conveniente

Lez. 81 Universita' di Ferrara Facolta' di Scienze Matematiche, Fisiche e Naturali Laurea...

Documents

Transcript of Lez. 81 Universita' di Ferrara Facolta' di Scienze Matematiche, Fisiche e Naturali Laurea...