Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

CORRETTEZZA DI PROGRAMMI

(1) small=i; small=i

(2) for(j=i+1, j<n, j++) j=i+1

(3) if (A[j]<A[small]) small=j; Falso, ESCI

Invariante di ciclo. j<n

S(k): Se si raggiunge il test “j<n” con vero

valore di j pari a k, i+1<k<n, allora (3)

A[small] contiene il min. di A[i..k-1].

BASE + PASSO Ind. j++

S(k) vera per ogni k=i+1,…, n.

Correttezza ciclo: si esce dal ciclo quando si raggiunge

il test “j<n” con valore di j pari a n.

L’invariante S(n) per k=n ci dice che

A[small] contiene il min. di A[i..n-1].

CORRETTEZZA del SelectionSort i=0

(1) For (i=0,i<n-1,i++){

(2) “small=indice min A[i..n-1]; Falso

(3) scambia A[i] ed A[small;} i<n-1

vero

Si vuole mostrare la Correttezza del ciclo, (2), (3)

cioè che quando si esce dal ciclo l’array

A[0..n-1] è ordinato. i++

Invariante di ciclo.

T(m): Se si raggiunge il test “i<n-1” con

valore di i pari a m, 0<m<n-1, allora

1) A[0..m-1] è ordinato

2) Ogni elemento di A[0..m-1] è < ogni

elemento di A[m..n-1].

CORRETTEZZA del SelectionSort

(1) For (i=0,i<n-1,i++) Invariante. T(m): Se si raggiunge il

{ test “i<n-1” con i pari a m, 0<m<n-1,

(1) “small=indice min A[i..n-1]; 1) A[0..m-1] è ordinato

(2) scambia A[i] ed A[small;ù 2) Ogni elemento di A[0..m-1] è < ogni

} elemento di A[m..n-1].

T(n-1) vera CORRETTEZZA DEL CICLO

Quando si raggiunge il test con i pari a n-1 si esce dal

ciclo.

T(n-1) vera 1) A[0..n-2] è ordinato

 2) Ogni elemento di A[0..n-2] è < A[n-1].

Quindi (A[0]<A[1] < … < A[n-2]) < A[n-1]

A[0..n-1] è ordinato

 CORRETTEZZA del SelectionSort

(1) For (i=0,i<n-1,i++) Invariante. T(m): Se si raggiunge il

{ test “i<n-1” con i pari a m, 0<m<n-1,

(1) “small=indice min A[i..n-1]; 1) A[0..m-1] è ordinato

(2) scambia A[i] ed A[small;ù 2) Ogni elemento di A[0..m-1] è < ogni

} elemento di A[m..n-1].

Mostriamo per induzione che T(m) vera per ogni m>0.

CORRETTEZZA del SelectionSort

(1) For (i=0,i<n-1,i++) Invariante. T(m): Se si raggiunge il

{ test “i<n-1” con i pari a m, 0<m<n-1,

(1) “small=indice min A[i..n-1]; 1) A[0..m-1] è ordinato

(2) scambia A[i] ed A[small;ù 2) Ogni elemento di A[0..m-1] è < ogni

} elemento di A[m..n-1].

BASE. m=0. Array A[0..m-1] è vuoto, niente da provare

CORRETTEZZA del SelectionSort

For (i=0,i<n-1,i++) Invariante. T(m): Se si raggiunge il

{ test “i<n-1” con i pari a m, 0<m<n-1,

(2) “small=indice min A[i..n-1]; 1) A[0..m-1] è ordinato

(3) scambia A[i] ed A[small]; 2) Ogni elemento di A[0..m-1] è < ogni

} elemento di A[m..n-1].

PASSO.

Ipotesi induttiva (i.i.):T(m) vera. Mostriamo T(m+1) vera.

Eseguiamo (2) e (3) con i pari a m. Abbiamo

(2) A[small]=min A[m..n-1]

(3) A[m]=min A[m..n-1]

Usando 1) e 2) in i.i. A[0]<A[1]<…<A[m-1]<A[m]

Quindi A[0..m-1] ordinato 1) vale per m.

Inoltre elemento A[m+1..n-1] > elemento A[0..m-1]

A[m]

Quindi elemento in A[m+1..n-1] > elemento in A[0..m]

2) vale per m.

 CORRETTEZZA CICLI WHILE

Possiamo nuovamente provare la correttezza per induzione

sul numero di volte per cui il ciclo è stato eseguito.

Però può non esistere variabile che conta numero di

esecuzioni.

Inoltre bisogna anche provare che il ciclo termina.

CORRETTEZZA CICLI WHILE

Possiamo nuovamente provare la correttezza per induzione

sul numero di volte per cui il ciclo è stato eseguito.

Però può non esistere variabile che conta numero di

esecuzioni.

Inoltre bisogna anche provare che il ciclo termina.

(1) i=1; Si vuole provare che al termine del ciclo la

(2) s=0; variabile s contiene la somma dei primi n

(3) while (i<n) { interi, cioè 1+2+…+n.

(4) s=s+i;

(5) i=i+1; } CORRETTEZZA CICLI WHILE

(1) i=1;

(2) s=0;

(3) while (i<n) {

(4) s=s+i;

(5) i=i+1; }

Terminazione. Ad ogni iterazione la variabile i è incrementata di

1, quindi raggiungerà il valore n+1 ed il ciclo termina.

CORRETTEZZA CICLI WHILE

(1) i=1;

(2) s=0;

(3) while (i<n) {

(4) s=s+i;

(5) i=i+1; }

Invariante di cilclo T(j):Se si raggiunge il test “i<n” con i pari a j

allora il valore di s è pari alla somma dei primi j-1 interi.

Base. j=1. Quando j=1 si ha s=0. Quindi T(0) vera.

Passo. Assumiamo per i.i. che T(j) vera. Proviamo T(j+1) vera.

Se i vale n+1 si esce dal ciclo, altrimenti iteriamo il ciclo

Eseguendo il ciclo con i pari a j, il valore di s è incrementato di j.

Usando l’i.i. s vale (1+…+j-1)+j =1+…+j

Inoltre i viene incrementata a j+1. Quindi quando si arriva al test

con i pari a j+1 s vale 1+…+j T(j+1) vera.

CORRETTEZZA CICLI WHILE

(1) i=1;

(2) s=0;

(3) while (i<n) {

(4) s=s+i;

(5) i=i+1; }

Invariante di cilclo T(j):Se si raggiunge il test “i<n” con i pari a j

allora il valore di s è pari alla somma dei primi j-1 interi.

Correttezza.

Usciamo dal ciclo quando eseguiamo il test con i pari a n+1.

T(n+1) valore di s è pari alla somma dei primi n interi.

 RICORSIONE: DEFINIZIONI RICORSIVE

Definizione ricorsiva: definizione di una classe di

“oggetti” in termini di una

sottoclasse degli “oggetti” stessi.

Consiste di due fasi

1) BASE. Si definiscono uno o più “oggetti”

2) PASSO Induttivo. Si definiscono altri “oggetti” a

partire da quelli già definiti.

Es. n fattoriale: n!=1x2x…xn= prodotto dei primi n interi

Definizione ricorsiva di n fattoriale, f(n):

. f(1)=1

BASE . f(n)=f(n-1) n, per n>1

PASSO X

Applicando successivamente il passo induttivo a partire da

f(1) otteniamo:

f(2)=f(1)x2=2, f(3)=f(2)x3=2x3=6, f(4)=f(3)x4=6x4=24,…

Definizione ricorsiva di n fattoriale, f(n):

. f(1)=1

BASE . f(n)=f(n-1) n

PASSO X

Mostriamo che la definizione data è corretta, cioè

consideriamo la seguente affermazione

S(n): f(n)=n!

e dimostriamo che S(n) vera per ogni n>1.

Definizione ricorsiva di n fattoriale, f(n):

. f(1)=1

BASE . f(n)=f(n-1) n

PASSO X

Mostriamo che la definizione data è corretta, cioè

consideriamo la seguente affermazione

S(n): f(n)=n!

e dimostriamo che S(n) vera per ogni n>1.

Dimostrazione per induzione.

BASE. n=1. Si ha f(n)=1=1! S(1) vera

Definizione ricorsiva di n fattoriale, f(n):

. f(1)=1

BASE . f(n)=f(n-1) n

PASSO X

Mostriamo che la definizione data è corretta, cioè

consideriamo la seguente affermazione

S(n): f(n)=n!

e dimostriamo che S(n) vera per ogni n>1.

Dimostrazione per induzione.

BASE. n=1. Si ha f(n)=1=1! S(1) vera

PASSO. Assumiamo come i.i. che S(n) vera (f(n)=n!).

Vogliamo mostrare che S(n+1) è vera.

Definizione ricorsiva di n fattoriale, f(n):

. f(1)=1

BASE . f(n)=f(n-1) n

PASSO X

Mostriamo che la definizione data è corretta, cioè

consideriamo la seguente affermazione

S(n): f(n)=n!

e dimostriamo che S(n) vera per ogni n>1.

Dimostrazione per induzione.

BASE. n=1. Si ha f(n)=1=1! S(1) vera

PASSO. Assumiamo come i.i. che S(n) vera (f(n)=n!).

Vogliamo mostrare che S(n+1) è vera.

Si ha

f(n+1)=f(n) (n+1)=n! (n+1) (per i.i.)

x x

=(1 … n) (n+1)=1 … (n+1)= (n+1)!

x x x x x

Quindi S(n+1) è vera.

Definizione ricorsiva dell’ordine lessicografico

Definiamo in modo ricorsivo coppie di stringhe W ed X

tali che W<X

la stringa vuota.

Indichiamo con 

BASE. 1. per ogni stringa W non vuota

<W,

2. se c<d (c,d caratteri) allora per ogni coppia

di stringhe W,X risulta

cW<dX

PASSO. Date le stringhe W ed X, se W<X allora per c

ogni carattere c risulta

cW<cX

Definizione ricorsiva dell’ordine lessicografico

BASE. 1. per ogni W non vuota

<W,

2. se c<d cW<dX, per ogni W,X

PASSO. W<X cW<cX, per ogni carattere c

Esercizio. Mostrare che se X<Y secondo la definizione

ricorsiva data, allora X precede Y in ordine lessicografico.

[Suggerimento: procedere per induzione sulla lunghezza del

prefisso comune alle due stringhe]

Ricorda: Ordine lessicografico

Data una coppia di sequenze c1c2 …ck, d1d2…dm risulta

c1c2 …ck < d1d2…dm

1) se k<m e c1=d1,…,ck=dk

(la prima è l’inizio della seconda)

2) oppure c1=d1,..,ci-1=di-1, ci<di per qualche i.

(ordine dato dal primo simbolo in cui le due sequenze differiscono)

Definizione ricorsiva dell’ordine lessicografico

BASE. 1. per ogni W non vuota

<W,

2. se c<d cW<dX, per ogni W,X

PASSO. W<X cW<cX, per ogni carattere c

Esercizio. Mostrare che se X<Y secondo la definizione

ricorsiva data, allora X precede Y in ordine

lessicografico.

[Suggerimento: procedere per induzione sulla lunghezza

del prefisso comune alle due stringhe]

Affermazione S(n): Date due stringhe X,Y con prefisso

comune lungo n, se X<Y allora X precede Y in ordine

lessicografico

Si vuole provare che S(n) vera per ogni n>0.

Definizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni

aritmetiche

PASSO. Se E ed E sono espressioni aritmetiche allora

1 2 - (

(E +E ) (E E ), E *E ), (E1/E2), (-E )

1 2 , 1 2 1 2 1

sono espressioni aritmetiche.

Definizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni

aritmetiche

PASSO. Se E ed E sono espressioni aritmetiche allora

1 2 - (

(E +E ) (E E ), E *E ), (E1/E2), (-E )

1 2 , 1 2 1 2 1

sono espressioni aritmetiche.

Es. (y (-(x+9)) è una espressione aritmetica.

*

Definizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni

aritmetiche

PASSO. Se E ed E sono espressioni aritmetiche allora

1 2 - (

(E +E ) (E E ), E *E ), (E1/E2), (-E )

1 2 , 1 2 1 2 1

sono espressioni aritmetiche.

Es. (y (-(x+9)) è una espressione arirmetica.

*

Verifica:

Usando la BASE: x,y e 9 sono espressioni aritmetiche

Definizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni

aritmetiche

PASSO. Se E ed E sono espressioni aritmetiche allora

1 2 - (

(E +E ) (E E ), E *E ), (E1/E2), (-E )

1 2 , 1 2 1 2 1

sono espressioni aritmetiche.

Es. (y (-(x+9)) è una espressione arirmetica.

*

Verifica:

Usando la BASE: x,y e 9 sono espressioni aritmetiche

Usando il PASSO: x e 9 sono e.a. (x+9) è e.a.

Definizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni

aritmetiche

PASSO. Se E ed E sono espressioni aritmetiche allora

1 2 - (

(E +E ) (E E ), E *E ), (E1/E2), (-E )

1 2 , 1 2 1 2 1

sono espressioni aritmetiche.

Es. (y (-(x+9)) è una espressione arirmetica.

*

Verifica:

Usando la BASE: x,y e 9 sono espressioni aritmetiche

Usando il PASSO: x e 9 sono e.a. (x+9) è e.a.

Usando il PASSO: (x+9) è e.a. (-(x+9)) è e.a.

Definizione ricorsiva di espressioni aritmetiche

BASE. Singole variabili, interi e reali sono espressioni

aritmetiche

PASSO. Se E ed E sono espressioni aritmetiche allora

1 2 - (

(E +E ) (E E ), E *E ), (E1/E2), (-E )

1 2 , 1 2 1 2 1

sono espressioni aritmetiche.

Es. (y (-(x+9))) è una espressione arirmetica.

*

Verifica:

Usando la BASE: x,y e 9 sono espressioni aritmetiche

Usando il PASSO: x e 9 sono e.a. (x+9) è e.a.

Usando il PASSO: (x+9) è e.a. (-(x+9)) è e.a.

Usando il PASSO: y e (-(x+9)) e.a. (y (-(x+9))) è e.a.

 *

FUNZIONI RICORSIVE

All’interno della funzione P c’è una chiamata a P (su input

diverso). FUNZIONI RICORSIVE

All’interno della funzione P c’è una chiamata a P (su input

diverso).

Funzioni ricorsive Definizioni ricorsive

Es. Calcolo di n! usando la definizione ricorsiva di

fattoriale. Base. 1!=1

Passo. n!= (n-1)! n

X

FUNZIONI RICORSIVE

All’interno della funzione P c’è una chiamata a P (su input

diverso).

Funzioni ricorsive Definizioni ricorsive

Es. Calcolo di n! usando la definizione ricorsiva di

fattoriale. Base. 1!=1

Passo. n!= (n-1)! n

X

Int fact(int n)

{ if(n<=1) return 1 /*Base*/

else return n fact(n-1); /*Passo*/

*

}

Int fact(int n)

{ if(n<=1) return 1 /*Base*/

else return n fact(n-1); /*Passo*/

*

}

n=1: fact(1) termina e restituisce 1!=1

Int fact(int n)

{ if(n<=1) return 1 /*Base*/

else return n fact(n-1); /*Passo*/

*

} n=1: fact(1) termina e restituisce 1!=1

chiama

n=2: fact(2) fact(1)

1

Int fact(int n)

{ if(n<=1) return 1 /*Base*/

else return n fact(n-1); /*Passo*/

*

}

n=1: fact(1) termina e restituisce 1!=1

chiama

n=2: fact(2) fact(1)

1

chiama chiama

n=3: fact(3) fact(2) fact(1)

2 1

Int fact(int n)

{ if(n<=1) return 1 /*Base*/

else return n fact(n-1); /*Passo*/

*

}

n=1: fact(1) termina e restituisce 1!=1

chiama

n=2: fact(2) fact(1)

1

chiama chiama

n=3: fact(3) fact(2) fact(1)

2 1

chiama chiama chiama

n: fact(n) fact(n-1) … fact(1)

(n-1)! (n-2)! 1

SelectionSort RICORSIVO

Idea alla base del SelectionSort:

Array A diviso in due parti

A[0..i-1] ordinato

A[i..n-1] elementi più grandi da ordinare

1. Trova min A[i..n-1], sia A[small]

Scambia A[i] ed A[small]

2. Ordina la parte non ordinata, cioè A[i+1..n-1]

SelectionSort RICORSIVO

Idea alla base del SelectionSort:

Array A diviso in due parti

A[0..i-1] ordinato

A[i..n-1] elementi più grandi da ordinare

1. Trova min A[i..n-1], sia A[small]

Scambia A[i] ed A[small]

2. Ordina la parte non ordinata, cioè A[i+1..n-1]

. Se i=n-1, la parte da ordinare è A[n-1], ok.

BASE . Se i<n-1, trova min A[i..n-1], scambialo con A[i];

PASSO ordina (ricorsivamente) A[i+1..n-1]

SelectionSort RICORSIVO

. Se i=n-1, la parte da ordinare è A[n-1], ok.

BASE . Se i<n-1, trova min A[i..n-1], scambialo con A[i];

PASSO ordina (ricorsivamente) A[i+1..n-1]

void Rec- SelectionSort(int A[], int i, int n)

int j,small,temp;

{ if (i<n-1) /* Base: i=n-1, Esci*/

{ /*Esegui Passo*/

small=i;

for(j=i+1, j<n,j++) if (A[j]<A[small]) small=j;

trova min

/* */

temp=A[small]; A[small]=A[i]; A[i]=temp;

scambia

/* */

Rec-SelectionSort(A,i+1,n)

}

} Numeri di FIBONACCI

. fib(0)=fib(1)=1;

BASE . fib(n)=fib(n-1)+fib(n-2)

PASSO Numeri di FIBONACCI

. fib(0)=fib(1)=1;

BASE . fib(n)=fib(n-1)+fib(n-2)

PASSO

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

} Numeri di FIBONACCI

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

}

n=0, oppure n=1: restituisce 1

Fib(1)

n=2: Fib(2) Numeri di FIBONACCI

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

}

n=0, oppure n=1: restituisce 1

Fib(1)

n=2: Fib(2) Fib(0)

Numeri di FIBONACCI

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

}

n=0, oppure n=1: restituisce 1

Fib(1)

n=2: Fib(2) Fib(0) Fib(1)

Fib(2)

n=3: Fib(3) Fib(0)

Numeri di FIBONACCI

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

}

n=0, oppure n=1: restituisce 1

Fib(1)

n=2: Fib(2) Fib(0) Fib(1)

Fib(2)

n=3: Fib(3) Fib(0)

Fib(1)

Numeri di FIBONACCI

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

} Fib(1)

Fib(2)

n=3: Fib(3) Fib(0)

Fib(1) Fib(1)

Fib(2)

Fib(3)

Fib(0)

n=4: Fib(4) Fib(1)

Numeri di FIBONACCI

int Fib (int n)

{

if (i<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/

} Fib(1)

Fib(2)

n=3: Fib(3) Fib(0)

Fib(1) Fib(1)

Fib(2)

Fib(3)

Fib(0)

n=4: Fib(4) Fib(1)

Fib(1)

Fib(2) Fib(0)

INDUZIONE COMPLETA

Vogliamo dimostrare che S(n) vale per ogni intero n>a.

Dimostrazione per induzione completa:

1. BASE INDUTTIVA. Si dimostra che l’affermazione è

vera per il primo valore, cioè S(a) è vera.

2. PASSO INDUTTIVO. Assumiamo che

S(a), S(a+1),…, S(n-1)

sono tutte vere e dimostriamo che anche S(n) è vera.

VALIDITA’ delle dim. per INDUZIONE Completa

Base: S(a) vera

Dim. per induzione S(n) vera, ogni

n>a Passo induttivo

Minimo controesempio. Supponiamo S(n) falsa per qualche n.

Sia b il più piccolo intero tale che S(b) falsa.

DEDUCIAMO:

Se b=a contraddiciamo la base. Quindi b>a.

Essendo b-1>a e

b = minimo intero per cui l’affermazione è falsa,

si ha S(a),…, S(b-1) vere

Per il Passo Induttivo, se S(a),…,S(b-1) sono vere allora

anche S(b) è vera.

Abbiamo una contraddizione con l’assunzione che S(b) falsa.

Quindi ipotesi è sbagliata e

non esiste intero per cui l’affermazione è falsa.

Numeri di FIBONACCI

int Fib (int n)

{ if (n<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione

S(n): il numero di chiamate fatte per calcolare Fib(n)

è maggiore di fib(n).

Per ogni n > 2 Numeri di FIBONACCI

int Fib (int n)

{ if (n<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione

S(n): il numero di chiamate fatte per

calcolare Fib(n) è maggiore di fib(n).

Per ogni n > 2

1. BASE INDUTTIVA. S(2) è vera.

2. PASSO Ind. S(2), …, S(n-1) implicano S(n) vera.

Numeri di FIBONACCI

int Fib (int n)

{ if (n<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione

S(n): il numero di chiamate fatte per

calcolare Fib(n) è maggiore di fib(n).

Per ogni n>1.

BASE. Se n=2 abbiamo 3 chiamate, fib(2)=2. S(2) è vera.

Numeri di FIBONACCI

int Fib (int n)

{ if (n<=1) return 1 /* Base*/

else return Fib(n-1)+Fib(n-2); /* Passo*/ }

Mostriamo per induzione completa l’affermazione

S(n): il numero di chiamate (ricorsive) fatte per

calcolare Fib(n) è maggiore di fib(n).

Per ogni n>1.

BASE. Se n=2 abbiamo 3 chiamate, fib(2)=2. S(2) vera.

PASSO. Assumiamo S(2), …, S(n-1) vere.

Il numero di chiamate fatte per calcolare Fib(n) è

1+(numero chiamate per Fib(n-1))

+(numero chiamate per Fib(n-2))> (per i.i.)

1+fib(n-1)+fib(n-2)=1+fib(n)>fib(n)

Quindi S(n) vera. Numeri di FIBONACCI

. fib(0)=fib(1)=1;

BASE . fib(n)=fib(n-1)+fib(n-2)

PASSO

Esercizio.

Mostrare per induzione completa l’affermazione

n

3

 

S(n): 

fib ( n )  

2

 

Per ogni n>5. Numeri di FIBONACCI

. fib(0)=fib(1)=1;

BASE . fib(n)=fib(n-1)+fib(n-2)

PASSO

Esercizio.

Scrivere un programma iterativo per il calcolo di fib(n).

Nota: è sufficiente un ciclo iterativo (con n iterazioni)

Sorting: MERGESORT

Vogliamo ordinare lista (a ,…,a ).

1 n

1. Dividi lista in 2 sottoliste aventi (quasi) la stessa

dimensione: (a ,a ,a ,…) e (a ,a ,…)

1 3 5 2 4

2. Ordina le due liste separatamente

3. Fai “merge” delle due lista ottenute (ordinate) in una

unica lista ordinata

Sorting: MERGESORT

Esempio di una tecnica generale: “Divide and Conquer ”

Sottoproblema 1

(simile, più semplice)

Sottoproblema 2

Problema ……

Sottoproblema n

Ogni sottoproblema risolto con la stessa tecnica. Finchè

non si raggiunge un sottopr. risolvibile direttamente .

Sorting: MERGESORT

Esempio di una tecnica generale: “Divide and Conquer ”

Sottoproblema 1

(simile, più semplice)

Sottoproblema 2

Problema ……

Sottoproblema n

Ogni sottoproblema risolto con la stessa tecnica. Finchè

non si raggiunge un sottopr. risolvibile direttamente .

soluzione Sottoproblema 1

soluzione Sottoproblema 2 soluzione Problema

… …

soluzione Sottoproblema n

Sorting: MERGESORT

Vogliamo ordinare lista (a ,…,a ).

1 n

1. Dividi lista in 2 sottoliste aventi (quasi) la stessa

dimensione: (a ,a ,a ,…) e (a ,a ,…)

1 3 5 2 4

2. Ordina le due liste separatamente

3. Fai “merge” delle due lista ottenute (ordinate) in una

unica lista ordinata

MERGE (di due liste ordinate L ,L M)

1 2

Es.

L =(1,2,7,7,9), L =(2,4,7,8) M=(1,2,2,4,7,7,7,8,9)

1 2

- Trova il minimo tra il primo elemento di L e di L

1 2

Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

Es.

L =(1,2,7,7,9), L =(2,4,7,8), M=(), minimo=1 in L

1 2 1

MERGE (di due liste ordinate L ,L M)

1 2

Es.

L =(1,2,7,7,9), L =(2,4,7,8) M=(1,2,2,4,7,7,7,8,9)

1 2

- Trova il minimo tra il primo elemento di L e di L

1 2

Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

Es.

L =(1,2,7,7,9), L =(2,4,7,8), M=(), minimo=1 in L

1 2 1

L =(2,7,7,9), L =(2,4,7,8), M=(1), minimo=2 in L

2 1

1 MERGE (di due liste ordinate L ,L M)

1 2

Es.

L =(1,2,7,7,9), L =(2,4,7,8) M=(1,2,2,4,7,7,7,8,9)

1 2

- Trova il minimo tra il primo elemento di L e di L

1 2

Rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

Es.

L =(1,2,7,7,9), L =(2,4,7,8), M=(), minimo=1 in L

1 2 1

L =(2,7,7,9), L =(2,4,7,8), M=(1), minimo=2 in L

2 1

1

L =(7,7,9), L =(2,4,7,8), M=(1,2), minimo=2 in L

2 2

1 MERGE (di due liste ordinate L ,L M)

1 2

L =(1,2,7,7,9), L =(2,4,7,8), M=(), minimo=1 in L

1 2 1

L =(2,7,7,9), L =(2,4,7,8), M=(1), minimo=2 in L

2 1

1

L =(7,7,9), L =(2,4,7,8), M=(1,2), minimo=2 in L

2 2

1

L =(7,7,9), L =(4,7,8), M=(1,2,2), minimo=4 in L

1 2 2

L =(7,7,9), L =(7,8), M=(1,2,2,4), minimo=7 in L

2 1

1

L =(7,9), L =(7,8), M=(1,2,2,4,7), minimo=7 in L

1 2 1

L =(9), L2=(7,8), M=(1,2,2,4,7,7), minimo=7 in L

1 2

L =(9), L2=(8), M=(1,2,2,4,7,7,7), minimo=8 in L

1 1

L1=(9), L2=(), M=(1,2,2,4,7,7,7,8), L2 vuota

Aggiungi L ad M.

2 M= =(1,2,2,4,7,7,7,8,9).

MERGESORT

BASE: Se la lista contiene 0 o 1 elemento, stop

Ind.: Split di (a ,a …) in (a ,a ,…) e (a ,a ,…)

1 2, 1 3 2 4

Mergesort delle due liste separatamente

Merge delle 2 liste ordinate

MERGESORT

7-4-2-8-9-7-7-2-1

MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7

7-1 9 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7

7-1 9

7 1 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7

7-1 9

7 1

7 1

1-7 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7

7-1 9

7 1

7 1

1-7 9

1-7-9 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7

7-1 9 2 7

7 1

7 1

1-7 2

9 7

1-7-9 2-7

1-2-7-7-9 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7 4-7 8-2

7-1 9 2 7

7 1

7 1

1-7 2

9 7

1-7-9 2-7

1-2-7-7-9 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7 4-7 8-2

7-1 9 2 7 4 7

7 1

7 1 4 7

1-7 2

9 7

1-7-9 2-7 4-7

1-2-7-7-9 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7 4-7 8-2

7-1 9 2 7 4 7 8 2

7 1

7 1 8 2

4 7

1-7 2

9 7 2-8

1-7-9 2-7 4-7 2-4-8-7

1-2-7-7-9 MERGESORT

7-4-2-8-9-7-7-2-1 4-8-7-2

7-2-9-7-1

7-9-1 2-7 4-7 8-2

7-1 9 2 7 4 7 8 2

7 1

7 1 8 2

4 7

1-7 2

9 7 2-8

1-7-9 2-7 4-7 2-4-7-8

1-2-7-7-9 1-2-2-4-7-7-7-8-9

Tempo di computazione (Running Time) di programmi

Misure del tempo: metodi principali

1. Benchmarking

2. Analisi

Benchmarking: usato per confrontare programmi.

Si cerca una collezione di input che sia rappresentativa

dell’insieme dei possibili dati reali. Il giudizio di

confronto viene espresso sugli input scelti.

Es. per algoritmi di sorting si può scegliere la collezione:

• prime 20 cifre 

• codici postali italiani

• numeri telefonici di Roma

Tempo di computazione (Running Time) di programmi

ANALISI: analizza il r.t. di un dato programma

Si raggruppano input per dimensione

(es. ordinamento: dimensione= numero elementi da ordinare,

sisteme di n equazioni in n incognite: dimensione=n)

Running time: funzione T(n), con n=dimensione input,

che rappresenta il numero di “unità di tempo” usate

dall’algoritmo

Unità di tempo varia: es. numero di istruzioni semplici in

linguaggio usato (C).

Tempo effettivo dipende da vari paramentri: velocità del

processore usato, compilatore,….

Tempo di computazione (Running Time) di programmi

Worst case (caso peggiore): su diversi input di stessa

dimensione n si possono avere r.t. differenti

T(n)=worst case r.t.

= max tempo su qualsiasi input di dimentsione n

Es. cerca min A[0..n-1] (dimensione=n)

1. small=0;

2. for(j=1; j<n; j++)

3. if(A[j]<A[small])

4. small=j;

| Linea | Numero operazioni

| 1. | 1

| 2. | 1 + n + (n-1) =2n

| 3. | n-1

| 4. | n-1 (worst case)

TOTALE: 1+2n+2(n-1)=4n-1 T(n)=4n-1

Tempo di computazione (Running Time) di programmi

Confronto di r.t. Dato un problema consideriamo 2

algoritmi A e B con r.t. T’(n) e T’’(n)

T’(n)=100n T’’(n)=2n

2

n<50, T’’(n) < T’(n)

T’’(n) n>50, T’’(n) > T’(n)

T’(n) n=100, T’’(n) = 2 T’(n)

n=1000, T’’(n) = 20 T’(n)

n

Tempo di computazione (Running Time) di programmi

T’(n)=100n T’’(n)=2n

2

Unità di tempo= 1ms (millisec) 1000 operazioni/sec

| max n per A | max n per B |

sec (1000ms) | (100n=1000*sec) | ( 2n =1000*sec) |

2

1 | 10 | 22 |

10 | 100 | 70 |

100 | 1000 | 223 |

1000 | 10000 | 707 |

Se calcolatori diventano 100 volte più veloci

(unità di tempo =1/100 di ms 100.000

operazioni/sec)

In 10 sec A passa da n=100 ad n=10000 (*100)

B passa da n=70 ad n=707 (*10)

Notazione O-grande e r.t. approssimato

Dato un programma ed un input r.t. dipende ancora da

1. Calcolatore usato (velocità di esecuzione istruzioni)

2. Compilatore (numero istruzioni macchina/istruzione C)

Quindi non ha senso parlare di tempo in sec per analizzare

un algoritmo.

Per nascondere effetti di 1. e 2. si usa la notazione

O-grande (big-Oh) che ignora le costanti

Es. 4m-1=O(m) (ignorando la costante moltiplicativa 4

e quella additiva 1)

Notazione O-grande e r.t. approssimato

Un r.t. T(n) si assume essere definito solo per n>0 e

che T(n)>0 per ogni n.

Definizione Dati il r.t. T(n) ed una funzione f(n),

definita per ogni intero n>0,

T(n)=O(f(n)) Esistono n >0 e c>0 tali che

 0

per ogni n>n risulta T(n)<cf(n)

0

N.B. Notazione Asintotica (vale per n ‘’grande’’)

Notazione O-grande e r.t. approssimato

Definizione Dati il r.t. T(n) ed una funzione f(n),

definita per ogni intero n>0,

T(n)=O(f(n)) Esistono n >0 e c>0 tali che

 0

per ogni n>n risulta T(n)<cf(n)

0

Es. Dato T(0)=0 e T(n)=(n+1)*(n+2), n>0

mostriamo che T(n)= O(n ). (cioè f(n)=n )

2 2

Prendiamo n =1, c=6:

0

T(n) =(n+1)(n+2)=n +3n+2

2

<n +3n +2n (per n>1, n =1<n<n )

2 2 2 2

0

=6n =c n = c f(n)

2 2

Notazione O-grande e r.t. approssimato

Costanti non hanno valore

T(n)=O(d T(n)), per ogni costante d

Infatti: siano n =0, c=1/d. Si ha

0

T(n)=(1/d) d T(n)= c (d T(n))

Notazione O-grande e r.t. approssimato

Low-order terms non hanno valore Dato il polinomio

T(n)=a n +a n +…+a n+a , con a >0

k k-1

k k-1 1 0 k

risulta T(n)=O(n )

k

Prova: k

    

Siano n 1

, c a (nota a c per ogni 0 i k )

0 i i

 

i 0 , a 0

i

k k

i i

 

 

Si ha T (n) a n a n

i i

  

i 0 i 0 , a 0

i

k k

 

a n (essendo 1 n )

i

 

i 0 , a 0

i k

k k k

  

n a n c cn .

i

 

i 0 , a 0

i

Notazione O-grande e r.t. approssimato

Low-order terms non hanno valore Dato il polinomio

T(n)=a n +a n +…+a n+a , con a >0

k k-1

k k-1 1 0 k

risulta T(n)=O(n )

k

5 3 2

  

Es. T(n) 10 n 3n - 2n 1

k

     

n 1

, c a 10 3 1 14

0 i

 

i 0 , a 0

i

5 3 2 5 3

     

T(n) 10 n 3n - 2n 1 10 n 3n 1

5 5 5 5 5

    

10 n 3n n 14 n c

n

Notazione O-grande e r.t. approssimato

La funzione g(n) cresce più rapidament

e di h(n) se

h ( n ) 

lim 0

g ( n )

 

n

Tasso di crescita Ha valore solo il termine che cresce

più rapidamente. Se g(n) cresce più rap. di h(n)

g(n)+h(n)=O(g(n))

Es. T(n)=2 +n =O(2 ), infatti

n 3 n 3

n 

lim 0

n

2

 

n

Verificarlo in modo diretto esibendo le costanti n e c

0

Notazione O-grande e r.t. approssimato

Transitività

Se f(n)=O(g(n)) e g(n)=O(h(n)) allora f(n)=O(h(n))

f(n)=O(g(n)) Esistono c’, n’ tali che f(n) < c’ g(n)

 per ogni n >

n’

g(n)=O(h(n)) Esistono c’’, n’’ tali che g(n) < c’’ h(n)

 per ogni n >

n’’

Quindi, prendiamo n =max { n’,n’’ } e c=c’c’’

0

Per n>n f(n) < c’ g(n) < c’ (c’’ h(n)) = c h(n)

n 0 Notazione O-grande e r.t. approssimato

Si vuole come O-grande la funzione con il minimo tasso

di crescita!!!

Es. f(n)=12n +3, si ha f(n)=O(n)

risulta anche f(n)=O(n ), f(n)=O(n ), f(n)=O(2 ), ….

2 3 n

ma non è quello che vogliamo.

Notazione O-grande e r.t. approssimato

Esercizio.Mostrare che g(n)+f(n)=O(max{f(n),g(n)})

Esercizio.Mostrare che se T(n)=O(f(n)) e S(n)=O(g(n))

allora T(n)S(n)=O(f(n)g(n))

Running Time di programmi

Trova f(n) tale che T(n)=O(f(n))

Istruzioni semplici (assegnamento, confronto,…)

tempo costante O(1)

Cicli for: for (i=1,i<=n,i++) I

1. se I=operazione semplice risulta O(n)

2. Se I ha r.t. O(f(n)) risulta O(nf(n))

es. for(i=1,i<=n,i++) A[i]=1 T(n)=O(n)

for(i=1,i<=n,i++)

for(j=1,j<=n,i++) A[i]=A[i]+A[j]

T(n)=O(n*n) =O(n )

 2

Running Time di programmi

If (C) I else I’: (normalmente C è O(1))

1. se I,I’ sono istruzioni semplici O(1)

2. se I ha r.t. O(f(n)) e I’ ha r.t. O(g(n))

O(max (f(n), g(n))

es. if (A[0]=0) for(i=1,i<=n,i++) A[i]=1;

else for(i=1,i<=n,i++)

for(j=1,j<=n,i++) A[i]=A[i]+A[j]

T(n)=O(max (n, n )) =O(n )

 2 2

Running Time di programmi

Cicli while e do while: simili al ciclo for

(non conosciamo esplicitamente il numero di iterazioni)

es. Dato un array A di n elementi

i=0;

while (x<>A[i] && i<n) i=i+1;

(caso peggiore: n iterazioni) T(n)=nO(1)=O(n)

Running Time di programmi

Sequenze di istruzioni: si devono sommare i tempi

delle singole istruzioni. Si usa la regola della somma.

O(f )

{I

Date con 1

1; O(f )

I ; 2

2 .

. .

. .

. O(f )

I } m

m;

Risulta

O(f (n)) + O(f (n))+…+ O(f (n))= O(f (n))

1 2 m i

f (n)=O(f (n)) per ogni j diverso da i.

j i Running Time di programmi

Chiamate a funzioni: si deve sommare il tempo

della funzione chiamata.

(se A chiama B: si calcola il r.t. di B e si somma al

r.t. delle altre istruzioni di A)

Chiamate ricorsive: determiniamo T(n) in modo induttivo

1. Tempo di una chiamata che non usa ricorsione = t

(=O(1))

2. Si esprime T(n) in termini del tempo T(n’) della

chiamata ricorsiva

Running Time di programmi

Chiamate ricorsive: determiniamo T(n) in modo induttivo

1. Tempo di una chiamata che non usa ricorsione=t

(=O(1))

2. Si esprime T(n) in termini del tempo T(n’) della

chiamata ricorsiva

Es. int fact(int n)

{ if (n<=1) return 1;

else return n*fact(n-1)}

T(1)=t

T(n)=T(n-1)+c Running Time di programmi

Es. int fact(int n)

{ if (n<=1) return 1;

else return n*fact(n-1)}

T(1)=t

T(n)=c+ T(n-1)

Vogliamo il valore di T(n) (non dipendente da T(n’))

Abbiamo T(n)=c+ T(n-1)

=c+ c+ T(n-2)= 2c +T(n-2)

Running Time di programmi

Es. int fact(int n)

{ if (n<=1) return 1;

else return n*fact(n-1)}

T(1)=t

T(n)=c+ T(n-1)

Abbiamo T(n)=c+T(n-1)

=c+ c+ T(n-2)= 2c +T(n-2)

=2c +c +T(n-3)=3c +T(n-3)

Running Time di programmi

Es. int fact(int n)

{ if (n<=1) return 1;

else return n*fact(n-1)}

T(1)=t

T(n)=c+ T(n-1)

Abbiamo T(n)=c+T(n-1)

=c+ c+ T(n-2)= 2c +T(n-2)

=2c +c +T(n-3)=3c +T(n-3)

=ic +T(n-i) (per i=n-1)

=(n-1)c+T(1)

=(n-1)c+t= O(n)

Running Time di programmi

Esercizio. Dimostrare per induzione su n che la

relazione di ricorrenza

T(1)=t

T(n)=c+ T(n-1)

ha come soluzione T(n)=(n-1)c + t

Base n=1. T(1)=t=(1-1)c+t. OK.

Passo. Sia n> 1. Assumiamo T(n)=(n-1)c + t.

Consideriamo T(n+1)

T(n+1)=c + T(n) (per definizione)

=c + (n-1)c + t (per i.i.)

= nc +t

Running Time di programmi

Esercizio. Considerare la relazione di ricorrenza

T(0)=T(1)= 1

T(n)=2 T(n-2)

1. Determinare T(2), T(3), T(4), T(5):

T(2)=2, T(3)=2, T(4)=4, T(5)=4

1. Determinare T(n) in termini di T(n-4): T(n)=4 T(n-4)

2. Determinare T(n) in termini di T(n-6): T(n)=8 T(n-6)

3. Determinare T(n) in termini di T(n-2i): T(n)=2 T(n-2i)

i

4. Determinare T(n):

se n pari, i=n/2, T(n-2i)=T(0) T(n)=2 T(0)=2

n/2 n/2

se n disp., i=(n-1)/2, T(n-2i)=T(1) T(n)=2 T(1) =2

(n-1)/2 (n-1)/2

Soluzioni Relazioni di ricorrenza

1. T(1)=a

T(n)= b+T(n-1), n>1 T(n)=(n-1)b+a

2. T(k)=a

T(n)=T(n-1)+g(n) T(n)=a + g(k+1)+…+g(n)

T(n) = g(n)+T(n-1)

= g(n)+g(n-1)+T(n-2)=…

= g(n)+g(n-1)+…+g(k+1)+T(k)

3. T(1)=1

T(n)=T(n-1)+n (g(i)=i) T(n)=1 + 2+…+n=n(n+1)/2

Soluzioni Relazioni di ricorrenza

log n 1

4. T(1)=a 2 j

 

T ( n ) 2 g ( ) an

n

T(n)=2T(n/2)+g(n)  2 j

j 0

  

T ( n ) g ( n ) 2

T ( n / 2 )

  

g ( n ) 2 g ( n / 2 ) 4

T ( n / 4 )

...  

i i i 1 i 1

    

g ( n ) 2 g ( n / 2 ) ... 2 T ( n / 2 ) 2 T ( n / 2 )

i   

i i 1 i 1 i 1

   

2 g ( ) 2 T ( n / 2 ) [Per i log n-

1

, 2 n ]

n i

2

j 0 

log n 1

2 j

 

2 g ( ) an

n j

2

j 0 Soluzioni Relazioni di ricorrenza

4. T(1)=a 

log n 1

2

T(n)=2T(n/2)+g j

 

 

T ( n ) 2 g an

j 0

log n 1

2 j

 

g 2 an

j 0

log n

 

g 2 an

2

   

gn an ( a g ) n

Soluzioni Relazioni di ricorrenza

log n 1

4. T(1)=a 2 j j

 

T ( n ) 2 ( n / 2 ) an

T(n)=2T(n/2)+n  

j 0

log n 1

2

 

n an

j 0

 

n (log n ) an

2

 O ( n (log n ))

2

Modello dati LISTA

LISTA: sequenza finita di 0 o più elementi

LISTA di tipo T: lista in cui tutti gli elementi sono dello

stesso tipo T.

es. lista di int

, di real

, di struct

,…

Lista che contiene elementi a ,…,a (a ,…,a )

1 n 1 n

Es. lista dei numeri primi <20 in ordine crescente

(1,2,3,5,7,11,13,17)

 Modello dati LISTA

LISTA: sequenza finita di 0 o più elementi

LISTA di tipo T: lista in cui tutti gli elementi sono dello

stesso tipo T.

es. lista di int

, di real

, di struct

,…

Lista che contiene elementi a ,…,a (a ,…,a )

1 n 1 n

Es. lista dei numeri primi <20 in ordine crescente

(1,2,3,5,7,11,13,17)

Lunghezza di una lista = numero di elementi nella lista

Es. lunghezza di (1,2,3,5,7,11,13,17) è 8

Lista vuota = = lista con zero elementi

 Modello dati LISTA

Data la lista (a ,…,a )

1 n

Head = primo elemento della lista = a 1

Tail

= lista senza head = (a ,…,a )

2 n

Sottolista : ogni lista (ai,ai+1,…, aj) 1 <

i

<

j <

n

Sottosequenza: elimina alcuni elementi dalla lista

lascandi gli altri in ordine

Es. Data (1,2,3)

sottoliste: , (1), (2), (3), (1,2), (2,3), (1,2,3)

sottosequenze: tutte le sottoliste e (1,3).

Modello dati LISTA

Data la lista (a ,…,a )

1 n

Prefisso = sottolista che inizia con a 1

Suffisso

= sottolista che finisce con an

La lista vuota è prefisso e suffisso di ogni lista

Es. Data (1,2,3,4)

prefissi: (1), (1,2), (1,2,3), (1,2,3,4)



suffissi: (4), (3,4), (2,3,4), (1,2,3,4)

 Modello dati LISTA

Data la lista (a ,…,a )

1 n

Elemento in posizione i= a i

Predecessore di a = a -1

i i

Successore di a = a +1

i i

Occorrenza di x = una posizione i tale che a =x

i

Es. Data (a,b,c,b,b)

elemento in posizione 1 = a

elemento in posizione 4 = b

occorrenza di a = 1

occorrenze di b = 2,4,5

occorrenza di c = 3

Operazioni su liste

Sorting: data la lista (a ,…a ) restituisce la lista ordinata

1 n

(b ,…,b ) contenente gli stessi elementi

1 n

Merging: date due liste ordinate restituisce una lista

ordinata contenente tutti gli elementi delle liste input

Dizionario: insieme di elementi su cui si vogliono fare le

operazioni di inserzione, ricerca e cancellazione

Concatenazione di 2 liste:

L=(a1,…,an), M=(b1,…bm) (a1,…,an,b1,…bm)

Liste a puntatori (struttura dati)

typedef struct CELL *LIST

struct CELL{

int element; /*per semplicità assumiamo elementi interi*/

LIST next}

lista: (modello) L=(a1,…,an)

(sruttura) a1 a2 an /

Liste a puntatori (struttura dati)

Dizionario su lista a puntatori (insert, delete, lookup)

Nota: dizionario contiene ogni elemento al più una volta

ordine non ha importanza, (1,3,5) equiv. (3,1,5)

Lookup: è x in D?

Metodo: Scorre celle della lista L che rappresenta D

finchè trova x oppure L finisce

Boolean lookup(int x, LIST L)

{if (L==NULL) return false

else if(L->element==x) return true

else return lookup(x, L ->next)}

Liste a puntatori (struttura dati)

Boolean lookup(int x, LIST L)

{if (L==NULL) return false

else if(L->element==x) return true

else return lookup(x, L ->next)}

R.T. T(0)=c

T(n)=b+T(n-1) T(n)=O(n)

Liste a puntatori (struttura dati)

Boolean lookup(int x, LIST L)

{if (L==NULL) return false

else if(L->element==x) return true

else return lookup(list ->next)}

Correttezza. Mostriamo per induzione

S(n): lookup(.) su una lista di n elementi restituisce

true se e solo se x in L

Base: n=0. n=0 L=NULL; risultato false; ok.

Passo: Sia S(n-1) vera. Consideriamo lista di n elementi.

Lookup(L) restituisce vero se x è il primo elemento

di L, ok!,

altrimenti restituisce vero sse (per i.i.) x è in tail

di L; ok!.

Liste a puntatori (struttura dati)

Cancellazione di x da lista L: i usa il puntatore pL

S

Elimina la cella contenente x (chiamata per referenza)

invece di L per poter

Void delete(int x, LIST *pL) modificare L.

{if (*pL!=NULL)

if(*pL->element==x) *pL=*pL ->next

else delete(x, pL->next)}

*

x x

R.T. T(n)=O(n)

Correttezza. Mostrare per induzione

S(n): delete(x,L) su una lista di n elementi restituisce

L se x non in L, elimina x da L altrimenti.

Liste a puntatori (struttura dati)

Inserzione di x nella lista L:

Inserisce, se x non in L, una cella contenente x

Void insert(int x, LIST *pL)

{if (*pL==NULL)

{/*inserisci x */

(*pl)=(LIST)malloc(sizeof(struct CELL));

(*pL)->element=x;

(*pl)->next=NULL;}

else if((*pL)->element!=x) insert(x,(*pL) ->next)}

X /

Se la lista è vuota crea cella contenente x

Altrimenti arriva a fine lista: NULL

 X /

Liste a doppi puntatori

L / a1 a2 an /

type def struct CELL *LIST

Struct CELL

{LIST previous;

int element;

LIST next}

Es. Cancella la cella puntata dal puntatore p:

delete(LIST p, LIST *pL)

Liste a doppi puntatori

Es. Cancella la cella puntata dal puntatore p

Void delete(LIST p, LIST *pL)

{if (p->next != NULL) p->next->previous=p->previous;

if (p->previous==NULL) (*pL)=p->next;

else p->previous->next=p->next;}

p

Sorting: MERGESORT

Vogliamo ordinare lista (a ,…,a ).

1 n

1. Dividi lista in 2 sottoliste aventi (quasi) la stessa

dimensione: (a ,a ,a ,…) e (a ,a ,…), (SPLIT)

1 3 5 2 4

2. Ordina le due liste separatamente (MERGESORT)

3. Fondi le due liste ottenute (ordinate) in una

unica lista ordinata (MERGE)

MERGE (di due liste ordinate L ,L M)

1 2

Algoritmo dipende dalla rappresentazione delle liste

Usiamo LISTE A PUNTATORI:

ogni elemento della lista è una struttura

typedef struct CELL *LIST

struct CELL{

int element /* elemento della lista*/

LIST next /* puntatore alla successiva

struttura

(elemento)*/ }

(a ,a ,…,a ) a a a

n 1 2 … n

1 2 MERGE (di due liste ordinate L ,L M)

1 2

-Trova il minimo tra il primo elemento di L1 e di L2,

rimuovilo dalla lista di appartenenza ed aggiungilo ad M.

- Ripeti

merge ( list1, list2)

LIST LIST LIST

{ if (list1== ) return list2

NULL

else if list2== return list1

( NULL)

else

if (list1->element <= list2 -> element)

/* entrambe le liste non vuote ed il primo

elemento di list1 è minore del primo di list2*/

list1->next=merge(list1->next, list2);

{ return list1;

} else /*entrambe le liste non vuote ed il primo

elemento di list2 è minore del primo di list1*/

list2->next=merge(list1, list2->next);

{ return list2;

}

} MERGE (di due liste ordinate L ,L M)

1 2

LIST merge (LIST list1, LIST list2) {

if (list1==NULL) return list2

else if list2== return list1

( NULL)

else if ( list1->element <= list2->element )

{/* entrambe le liste non vuote ed il primo elemento

di list1 è minore del primo di list2*/

list1->next=merge(list1->next, list2);

return list1;}

else

…} list1 a a a

1 2 … n

list2 b b … b

1 2 n

a a

2 n

list1 a merge

1 b b

1 n

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

 merge(4-7,3-5-6-9)

merge(list2)

merge(, merge(4-7, 5-6-9)

= )

merge(, merge(7, 5-6-9)

= )

merge(, merge(7, 6-9)

= )

merge(, merge(7, 9)

= ) 9

merge(NULL, merge( , 9)

= )=

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

 merge(4-7,3-5-6-9)

merge(list2)

merge(, merge(4-7, 5-6-9)

= )

merge(, merge(7, 5-6-9)

= )

merge(, merge(7, 6-9)

= ) 7

merge(, = merge(7, 9)  

= )

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

 merge(4-7,3-5-6-9)

merge(list2)

merge(, merge(4-7, 5-6-9)

= )

merge(, merge(7, 5-6-9)

= ) 6

 

merge(, merge(7, 6-9)

= )=

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

 merge(4-7,3-5-6-9)

merge(list2)

merge(, merge(4-7, 5-6-9)

= ) 5

 

merge(, = merge(7, 5-6-9)

= ) 

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

Merge(list1, list2) merge (2-4-7, 3-5-6-9)

 merge(4-7,3-5-6-9)

merge(list2) 4

 

merge(, = merge(4-7, 5-6-9)

= ) 

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

list1=merge(list1, list2) merge (2-4-7, 3-5-6-9)

 list2 3 

merge(4-7,3-5-6-9)

merge(list2)=list2

MERGE (di due liste ordinate L ,L M)

1 2

list1 2 4 7 

 

list2 3 5 6 9

   

list1=merge(list1, list2) merge (2-4-7, 3-5-6-9) list1 2

 

SPLIT (di L in due liste ordinate L ,L )

1 2

L=(a ,a , a , a , …, a ) L =(a , a , …) , L =(a , a , …)

2 3 4 n 1 1 3 2 2 4

1

LIST Split (LIST list)

{

List pSecondcell;

if (list==NULL) return NULL

else if (list->next==NULL) return NULL

else

{/* list contiene almeno 2 elementi*/

pScondcell=list->next;

list->next = pSecondcell->next;

pSecondcell->next=split(pSecondcell->next);

return pSecondcell;

}

} SPLIT (di L in due liste ordinate L1,L2)

LIST Split (LIST list)

{ List pSecondcell;

if (list==NULL) return NULL

else if (list->Next==NULL) return NULL

else {/* list contiene almeno 2 elementi*/

pScondcell=list->next;

list->next = pSecondcell->next;

pSecondcell->next=split(pSecondcell->next);

return pSecondcell;}} MERGESORT

BASE: Se la lista contiene 0 o 1 elemento, stop

Ind.: Split di (a ,a …) in (a ,a ,…) e (a ,a ,…)

1 2, 1 3 2 4

Mergesort delle due liste separatamente

Merge delle 2 liste ordinate

LIST Mergesort (LIST list)

{

List SecondList;

if (list==NULL) return NULL

else if (list->next==NULL) return list

else

{/* list contiene almeno 2 elementi (da ordinare)*/

SecondList=split(list);

return merge(mergesort(list),mergesort(ScondList));

}

} R.T. della funzione SPLIT

LIST Split (LIST list)

{ List pSecondcell;

if (list==NULL) return NULL

else if (list->Next==NULL) return NULL

else {/* list contiene almeno 2 elementi*/

pScondcell=list->next;

list->next = pSecondcell->next;

pSecondcell->next=split(pSecondcell->next);

return pSecondcell;}}

Sia n=|list|. Si ha la relazione di ricorrenza

T(0)=T(1)=O(1)

T(n)=c+T(n-2), per n>1

Quindi T(n)=O(n) R.T. del MERGE

merge ( list1, list2)

LIST LIST LIST

{ if (list1== ) return list2

NULL

else if list2== return list1

( NULL)

else

if (list1->element <= list2 -> element)

list1->next=merge(list1->next, list2);

{ return list1; }

else

list2->next=merge(list1, list2->next);

{ return list2;}

}

Siano n1=|list1|, n2=|list2|, n=n1+n2.

Si ha la relazione di ricorrenza

T(0)=T(1)=O(1) (almeno 1 lista vuota)

T(n)=c+T(n-1), per n>1

Quindi T(n)=O(n) R.T. MERGESORT

LIST Mergesort (LIST list)

{List SecondList;

if (list==NULL) return NULL

else if (list->next==NULL) return list

else /* list contiene almeno 2 elementi (da ordinare)*/

{SecondList=split(list);

return merge(mergesort(list),mergesort(ScondList));}

}

Sia n=|list|. Si ha la relazione di ricorrenza

T(0)=T(1)=O(1) (list contiene 0 o 1 elemento)

T(n)=O(n) + O(n) +T(n/2) +T(n/2)

=O(n) + 2 T(n/2), per n>1

Quindi T(n)=O(n log n)

R.T. MERGESORT

T(0)=T(1)=O(1)

T(n)=c n + 2 T(n/2), per n>1

Si assuma per semplicità che n=2 (cioè m=log n)

m

T(n)=c n + 2 T(n/2)

=c n + 2 (c n/2 + 2 T(n/4))= c n + c n +4 T(n/4)

= 2c n + 4 T(n/4)

= 2c n +4 (c n/4 + 2 T(n/8))=2c n + c n+8T(n/8)

= 3c n + 8 T(n/8)

……

= i c n + 2 T(n/2 )

i i

Scegliendo i=m=log n si ha

T(n)= m c n + 2 T(n/n)= m c n + n a=

m

= c n log n + a n = O(n log n)

Correttezza MERGESORT

LIST Mergesort (LIST list)

{List SecondList;

if (list==NULL) return NULL

else if (list->next==NULL) return list

else /* list contiene almeno 2 elementi (da ordinare)*/

{SecondList=split(list);

return merge(mergesort(list),mergesort(ScondList));}

}

Assumiamo correttezza delle funz.split e merge (esercizio)

Per induzione completa su n=|list|.

Base. Se n=0 o n=1, restituisce lista inalterata, ok.

Passo (n>1). Assumiamo per i.i. mergesort(list),

mergesort(ScondList) restituiscono liste input ordinate.

Quindi

Split divide n elementi lista input tra list e Secondlist;

mergesort(list),mergesort(ScondList) ordina le liste;

Merge fonde le liste restituendo in output una lista ordinata

contenete gli stessi n elementi della lista input.

Liste mediante array

Struttura dati: array per contenere elementi

variabile length per contare # elementi

Array A[0..MAX-1] (lista può contenere al più MAX el.)

Lista (a ,…,a ) usa prime n locazioni di A, length=n

0 n-1

a

0 0

1 Typedef struct LIST /*lista struttura con

2 campi: array e length*/

… { int A[MAX];

a

n-1 n-1 int length;

… }

MAX Liste mediante array

a

0 0

1 Typedef struct LIST /*lista struttura con

2 campi: array e length*/

… { int A[MAX];

a

n-1 n-1 int length;

… }

MAX pL: puntatore a struct LIST L

pL->A[i] = elemento i-mo della lista

pL->length = lunghezza lista

Liste mediante array

pL: puntatore a struct LIST

pL->A[i]= elemento i-mo della lista

pL->length=lunghezza lista

LOOKUP

Ricerca lineare

Boolean lookup(int x, LIST *pL)

{int i

for (i=0, i<*pL->length,i++)

if (x==*pL->A[i]) return TRUE;

return FALSE;}

R.T O(n), n=lunghezza lista

LOOKUP con RICERCA BINARIA su lista ORDINATA

Sia a ,a ,…,a una lista ordinata (a < a < …< a )

0 1 n-1 0 1 n-1

rappresentata mediante un array A[0..n-1].

Cerchiamo x.

a Se x<A[mid] continua la

0 ricerca di x in A[0.. mid-1]

a mid= Se x=A[mid], trovato x, STOP

[(n-1)/2]

mid Se x>A[mid] continua la ricerca

di x in A[mid+1.. n-1]

a

n-1

LOOKUP con RICERCA BINARIA su lista ORDINATA

Boolean BinSesarch(int x, int A[],int low, int high)

{int mid;

a low if (low > high) return FALSE;

else {

mid=(low+high)/2;

if(x<A[mid]) return BinSearch(x,A,low,mid-1);

a

mid else if (x>A[mid]) return BinSearch(x,A,mid+1,high);

else return TRUE /*x=A[mid]*/

CORRETTEZZA: restituisce true sse x in A[low..high]

a

high Per induzione completa su m=high-low+1 (ampiezza array)

Base. m=0 (high<low), array vuoto, restituisce False, ok

Passo. (esercizio)

LOOKUP con RICERCA BINARIA su lista ORDINATA

a Sia P(k)=max numero elementi su cui si può fare la

low ricerca con k confronti (chiamate ricorsive)

P(1)=1

P(2)=3 (mid, P(1)=1 elementi minori di mid,

a

mid P(1)=1 elementi maggiori di mid)

P(k)=2 P(k-1)+1 (mid, P(k-1)=1 elementi minori di mid,

P(k-1)=1 elementi maggiori di

mid)

a

high

P(k)=2 P(k-1)+1= 2( 2 P(k-2)+1)+1= 4 P(k-2)+2+1=

= 2 P(k-i) +2 +… + 2 + 1

i i-1

= 2 P(k-i) + 2 -1

i i

= 2 P(1) + 2 -1

k-1 k-1

= 2 -1

k k

Quindi ponendo n= P(k) si ha

n=2 -1 k= log (n+1) numero confronti=R.T=O(log n)

 

k CODE

CODA: struttura basata sulle liste, ma con restrizioni

sulle operazioni di inserzione e cancellazione

Inserzione: sempre da un estremo detto rear

Cancellazione: sempre da altro estremo, detto front

FIFO: First In First Out

(a , a , …, a )

0 1 n-1

front rear

Es. C=(a,b,c)

insert d in C C’=(a,b,c,d)

delete C’’=(b,c,d)

OPERAZIONI su CODA Q

•clear(Q): rendi Q vuota

•dequeue(Q,x): se Q è vuota return FALSE, altrimenti

- poni x=elemento alfront di Q

- elimina elemento al front di Q

- return TRUE

•enqueue(Q,x): se Q è piena return FALSE, altrimenti

- inserisci x al rear di Q

- return TRUE

•isempty(Q): restituisci TRUE se Q è vuota, FALSE alt.

•isfull(Q): restituisci TRUE se Q è piena, FALSE alt.

CODE mediante Liste a Puntatori

Coda lista con due puntatori: front e rear

typedef struct{

LIST front, rear

} QUEUE /

front rear

Coda piena mai, isfull(Q) restituisce sempre FALSE

Coda vuota front=NULL

BOOLEAN isEmpty(QUEUE *pQ)

{return (pQ->front=NULL);}

void clear(QUEUE *pQ)

{*pQ->front=NULL;}

CODE mediante Liste a Puntatori

BOOLEAN dequeue(QUEUE *pQ, int *px)

{if (isempty(pQ) return FALSE;

else {(*px)=pQ->front->element;

pQ->front=pQ->front->next;

return TRUE;} / rear

x vale a

CODE mediante Liste a Puntatori

BOOLEAN enqueue(QUEUE *pQ, int x)

{if (isempty(pQ)

{pQ->front=(LIST)malloc(sizeof(struct CELL));

pQ->rear= pQ->front;}

else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));

pQ->rear=pQ->rear->next;}

pQ->rear->element=x;

pQ->rear->next=NULL;

return TRUE;}

CODE mediante Liste a Puntatori

BOOLEAN enqueue(QUEUE *pQ, int x)

{if (isempty(pQ)

{pQ->front=(LIST)malloc(sizeof(struct CELL));

pQ->rear= pQ->front;}

else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));

pQ->rear=pQ->rear->next;}

pQ->rear->element=x;

pQ->rear->next=NULL;

return TRUE;}

front CODE mediante Liste a Puntatori

BOOLEAN enqueue(QUEUE *pQ, int x)

{if (isempty(pQ)

{pQ->front=(LIST)malloc(sizeof(struct CELL));

pQ->rear= pQ->front;}

else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));

pQ->rear=pQ->rear->next;}

pQ->rear->element=x;

pQ->rear->next=NULL;

return TRUE;}

/

x

front rear

CODE mediante Liste a Puntatori

BOOLEAN enqueue(QUEUE *pQ, int x)

{if (isempty(pQ)

{pQ->front=(LIST)malloc(sizeof(struct CELL));

pQ->rear= pQ->front;}

else {pQ->rear->next= =(LIST)malloc(sizeof(struct CELL));

pQ->rear=pQ->rear->next;}

pQ->rear->element=x;

pQ->rear->next=NULL;

return TRUE;} X /

front rear

Nota. Il R.T. è O(1) per tutte le operazioni

CODE mediante ARRAY

Array circolare: immaginato come se dopo la posizione

n-1 venga nuovamente la posizione 0

0 n-1 0 1

A= … Visto come In senso

2 orario

n-1 …

Front, rear: le posizioni occupate dalla coda vanno

da front a rear, front precede rear in senso orario

Typedef struct{

int A[n];

int front, rear} QUEUE

CODE mediante ARRAY

Front, rear: le posizioni occupate dalla coda vanno

da front a rear, front precede rear in senso orario

8 0 1

7

6 2

5 3

4

Front=2, rear=5 coda=(A[2],A[3],A[4],A[5])

Front=5, rear=2 coda=(A[5],…,A[8],A[0],A[1],A[2])

CODE mediante ARRAY

Front, rear: le posizioni occupate dalla coda vanno

da front a rear, front precede rear in senso orario

Coda vuota: front in posizione immediatamente successiva

al rear

es. front=3, rear=2.

Coda piena: contiene n-1 elementi

front a 2 posizioni successive al rear

es. front=3, rear=1 coda

 =(A[3],…,A[n-1],A[0],A[1])

Nota: se coda contenesse n elementi allora front in

posizione immediatamente successiva al rear,

es. front=3, rear=2 

coda=(A[3],…,A[n-1], A[0], A[1], A[2]),

si confonderebbe con coda vuota

CODE mediante ARRAY

Operazioni modulo n:

x+y mod n=resto divisine di (x+y) per n

es. x+1 mod n= x+1 se x<n-1, 0 se x=n-1.

Clear: poni front=1, rear=0 (quindi front=rear+1 mod n)

isEmpty: controlla se front=rear+1 mod n

isFull: risultato del confronto (front==rear +2 % n)

Enqueue(Q,x): se coda è piena restituisce FALSE,

altrimenti rear=(rear +1)%n; Q[rear]=x; return TRUE

Dequeue(Q,x): se coda vuota restituisce FALSE,

altrimenti x=Q[front]; front=(front+1)%n; return TRUE

CODE mediante ARRAY

8 0=rear

1=front

In una coda circolare con

n=9, inizialmente vuota: 1=front=rear

5

Inserire 5 1=front

5

Inserire 2 2=rear

2

CODE mediante ARRAY

1=front

5 2=rear

2

1=front

5

2

Inserire 6 6 3=rear

2 2=front

Cancellare 6 3=rear

STACK (o Pile)

Stack. lista (a ,…,a ) su cui vogliamo fare 2 operazioni

1 n

principali: PUSH, POP.

Tutte le operazioni principali sono fatte ad uni stesso

estremo detto TOP

Se stack=S= (a ,…,a ), assumiamo top=ultimo elemento=a

1 n n

PUSH(x,S): inserisce x al top (a ,…,a ,x)

 1 n

POP(S): elimina elemento al top (a ,…,a )

 1 n-1

Stack=Struttura LIFO (Last In First Out)

STACK (o Pile)

Es. Compilatore usa espressioni aritmetiche tradotte da

notazione infissa a postfissa (operandi precedono

operatore)

(3+4)*2 34+2*

Espressioni postfisse valutate mediante stack

Simbolo Azione Stack

3 push 3 3

4 push 4 3,4

+ pop, pop 

push 7 7

2 push 2 7,2

* pop, pop 

push 14 14

STACK (o Pile)

3*5+2*7 35*27*+

Simbolo Azione Stack

3 push 3 3

5 push 5 3,5

* pop, pop 

push 15 15

2 push 2 15,2

7 push 7 15,2,7

* pop, pop 15

push 14 15,14

+ pop, pop 

push 28 28

Operazioni su STACK

Clear(S): rende stack S vuoto

IsEmpty(S): TRUE se S vuoto, FALSE altrimenti

IsFull(S): TRUE se S pieno, FALSE altrimenti

Pop(S,x): se S è vuoto, restituisce FALSE

altrimenti pone x=elemento al top di S e

restituisce TRUE

Push(S,x): se S è pieno, restituisce FALSE

altrimenti inserisce x al top di S e

restituisce TRUE

stack mediante array

a

0 0

1 Typedef struct LIST /*lista struttura con

2 campi: array e top*/

… { int A[MAX];

a Top

n-1 n-1 int top;

… } STACK

MAX-1

Stack (a ,…,a ) usa prime n locazioni di A, length=n

0 n-1

Primo elemento inserito è a 0

Ultimo elemento inserito è a n-1

top=n-1

Stack vuoto top=-1

 stack mediante array

Passiamo stack “per referenza”, altrimenti si copia

intero array

Void clear(STACK *pS)

{ ps->top=-1}

Boolean isEmpty(STACK *pS)

{ return (ps->top<0) }

Boolean isFull(STACK *pS)

{ return (ps->top<= MAX-1) }

stack mediante array

Boolean Pop(STACK *pS, int *px)

{ if isempty(pS)) return FALSE

else { (*px)=ps->A[(ps->top)--];

return TRUE }

}

Boolean Push(STACK *pS, int x)

{ if isFull(pS)) return FALSE

else { ps->A[++(ps->top)]=x;

return TRUE }

} Stack mediante Liste a Puntatori

Stack lista a puntatori con top al front

typedef struct CELL *STACK

struct CELL {

int element;

STACK next} /

S top

Stack mediante Liste a Puntatori

/

S top

Stack pieno mai, isFull restituisce sempre FALSE

BOOLEAN isFull(STACK *pS)

{return FALSE}

Stack vuoto lista vuota

BOOLEAN isEmpty(QUEUE *pS)

{return (*pS)==NULL);}

void clear(QUEUE *pQ)

{(*pS)=NULL;}

Stack mediante Liste a Puntatori

BOOLEAN pop(STACK *pS, int *px)

{if ((*pS)==NULL) return FALSE;

else { (*px)=(*ps)->element;

(*ps)=(*ps)->next;

return TRUE }

} /

S top top /

S Stack mediante Liste a Puntatori

BOOLEAN push(STACK *pS, int *px)

{STACK newcell;

newcell=(STACK)malloc(sizeof(struct CELL));

newcell->element=x;

newcell->next=(*pS);

(*pS)=newcell;

return TRUE }

} /

S top

top

x /

S

Implementazione di Chiamate di funzioni mediante

Stack

Quando funzione F chiama P: l’ esecuzione di F è sospesa e

le variabili di F sono memorizzate

Per funzioni ricorsive si hanno piu’ chiamate attive allo

Stesso tempo della stessa funzione

int fact(int n)

{if (n<=1) return 1

else return n*fact(n-1)}

fact(10) fact(9) fact(8) …

   fact(2)

sono tutte attive (e sospese) fino al completamento di fact(1).

Ogni chiamata attiva ha diversi valori di: input, variabili, …

Implementazione di Chiamate di funzioni mediante

Stack

Esecuzione di funzione è chiamata attivazione

Record di attivazione: tutti i dati relativi all’esecuzione;

es: variabili locali, da dove riprendere esecuzione,…

STACK = record di attivazione di tutte le attivazioni non

terminate

Top A A in esecuzione

1 1

A A ha chiamato A , riprende al termine di A

2 2 1 1

A A ha chiamato A , riprende al termine di A

3 3 2 2

… …

A k

Implementazione di Chiamate di funzioni mediante

Stack

Es. Record di attivazione per fact

(n,fact) (valore input, valore output (riempito alla fine))

fact(4) crea stack (4, fact)

(3, fact )

chiama fact(3) stack

 (4, fact )

(2, fact )

Chiama fact(2) stack

 (3, fact )

(4, fact )

Implementazione di Chiamate di funzioni mediante

Stack (2, fact )

(3, fact )

Chiama fact(2) stack

 (4, fact )

(1, fact)

(2, fact )

Chiama fact(1) stack

 (3, fact )

(4, fact )

Implementazione di Chiamate di funzioni mediante

Stack

(1, fact=1)

Fact(1) termina  (2, fact ) (2, fact )

(3, fact ) (3, fact )

(4, fact ) (4, fact )

(2, fact =2)

Fact(2) termina  

(3, fact ) (3, fact )

(4, fact ) (4, fact )

Implementazione di Chiamate di funzioni mediante

Stack

(2, fact =2) 

Fact(2) termina  (3, fact ) (3, fact )

(4, fact ) (4, fact )

(3, fact =6)

Fact(3) termina  

(4, fact ) (4, fact )

(4, fact=24 )

Fact(4) termina  Modello dati ALBERO

Albero: insieme di punti chiamati NODI e linee

chiamate EDGES

EDGE: linea che unisce due nodi distinti

Radice (root): in una albero esiste un nodo distinto

chiamato radice (disegnato in cima)

Es. Albero con sette nodi n , n , n , n , n , n , n

1 2 3 4 5 6 7

la radice è n 1 n 1

n n

n 4 5

2

n n n

3 6 7

Modello dati ALBERO

Padre/figlio: ogni nodo c (tranne la radice) è

n

1 connesso mediante una linea ad un nodo p,

chiamato il padre di c; c è detto figlio di p.

n n

n 4 5

2 Es.

n n n n padre di n , n , n / n , n , n figli di n

3 6 7 1 2 4 5 2 4 5 1

n “ n / n figlio di n

2 3 3 2

n n , n / n , n figli di n

5 6 7 6 7 5

Modello dati ALBERO

Padre/figlio: ogni nodo c (tranne la radice) è

n

1 connesso mediante una linea ad un nodo p,

chiamato il padre di c; c è detto figlio di p.

n n

n 4 5

2 Es.

n n n n padre di n , n , n / n , n , n figli di n

3 6 7 1 2 4 5 2 4 5 1

n “ n / n figlio di n

2 3 3 2

n n , n / n , n figli di n

5 6 7 6 7 5

Albero è connesso: per ogni nodo n (tranne la radice) se

ci spostiamo da n al padre di n,

poi dal padre di n al padre del padre di n, …,

arriviamo alla radice.

Es. n padre di n =n padre di n =n1=radice

 

3 3 2 2

Definizione ricorsiva di ALBERO

Base: un singolo nodo n è un albero (con radice n)

Passo:Siano T ,…,T , (per qualche k>0) alberi con radici

1 k

c ,c ,…,c ,rispettivamente, tali che ogni nodo compaia

1 2 k

in uno solo degli alberi. Sia r un nuovo nodo (non in T ,

1

…,T ). Costruiamo un nuovo albero T come segue

k

1. La radice di T è r

2. Aggiungi un edge da r ad ognuna dei nodi c ,…,c (che

1 k

diventano figli di r in T) r

c c

1 k c

 T= c …

… k

1

T T

1 k T

T k

1

Definizione ricorsiva di ALBERO

Base: un singolo nodo n è un albero (con radice n)

Passo:Siano T ,…,T , (per qualche k>0) alberi con radici c ,c ,

1 k 1 2

…,c ,rispettivamente, tali che ogni nodo compaia in un solo albero.

k

Sia r un nuovo nodo. Costruiamo il nuovo albero T

1. La radice di T è r

2. Aggiungi un edge da r ad ognuna dei nodi c ,…,c (figli di r in T)

1 k

n

2

Es. n albero è albero

3 n 3

Definizione ricorsiva di ALBERO

Base: un singolo nodo n è un albero (con radice n)

Passo:Siano T ,…,T , (per qualche k>0) alberi con radici c ,c ,

1 k 1 2

…,c ,rispettivamente, tali che ogni nodo compaia in un solo albero.

k

Sia r un nuovo nodo. Costruiamo il nuovo albero T

1. La radice di T è r

2. Aggiungi un edge da r ad ognuna dei nodi c ,…,c (figli di r in T)

1 k

n

2

Es. n albero è albero

3 n 3 n

5

n n è albero

alberi 

6 7 n n

6 7

Definizione ricorsiva di ALBERO

Base: un singolo nodo n è un albero (con radice n)

Passo:Siano T ,…,T , (per qualche k>0) alberi con radici c ,c ,

1 k 1 2

…,c ,rispettivamente, tali che ogni nodo compaia in un solo albero.

k

Sia r un nuovo nodo. Costruiamo il nuovo albero T

1. La radice di T è r

2. Aggiungi un edge da r ad ognuna dei nodi c ,…,c (figli di r in T)

1 k

n

2

Es. n albero è albero

3 n 3 n

5

n n è albero

alberi 

6 7 n n

6 7 n

1

n n n alberi è albero

2 n n

4 5 n 4 5

2

n n n

3 n n n

6 7 3 7

6

Definizioni su ALBERI è

Dato T con radice r

m ,…m : è un cammino (di lunghezza k-1) in T se

1 k

m è padre di m , m è padre di m ,…, m padre di m

1 2 2 3 k-1 k.

un solo nodo è un cammino di lunghezza 0 (k=1).

n 1

n n

n 4 5

2

n n

n

3 7

6

Definizioni su ALBERI è

Dato T con radice r

m ,…m : è un cammino (di lunghezza k-1) in T se

1 k

m è padre di m , m è padre di m ,…, m padre di m

1 2 2 3 k-1 k.

un solo nodo è un cammino di lunghezza 0 (k=1).

Predecessore: m è predecessore di m’ se esiste un cammino

da m a m’ in T

Discendente: m’ è discendente di m se m è predecessore di

m’.

Fratelli: m e m’ so dicono fratelli se hanno lo stesso padre.

n 1

n n

n 4 5

2

n n

n

3 7

6

Definizioni su ALBERI è

Sottoalbero con radice n: albero formato dal nodo n con

tutti i suoi discendenti n 1

n n

n 4 5

2

n n n

3 6 7


ACQUISTATO

1 volte

PAGINE

420

PESO

3.91 MB

AUTORE

flaviael

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in informatica
SSD:
Università: Salerno - Unisa
A.A.: 2009-2010

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher flaviael di informazioni apprese con la frequenza delle lezioni di Programmazione e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Salerno - Unisa o del prof Gargano Luisa.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in informatica

Architettura degli elaboratori
Appunto
Esame programmazione 1
Appunto
Calcolo Numerico - nozioni
Appunto
Analisi matematica - Appunti
Appunto