CONOSCERE CONOSCERSI COMUNICARE

Joseph Ceres

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

2

Affitto rete telefonica

Se una nuova azienda telefonica vuole inserirsi su una rete già esistente,

quali collegamenti le conviene affittare per raggiungere i clienti col minor costo?

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

3

ProblemaDato un grafo non orientato trovare un

sottoinsieme, albero, che raggiunga tutti i vertici al minor costo

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

4

AlberoGrafo non orientato connesso senza circuiti.Quale tra questi è un albero?

No! circuito No! non connesso Si! albero

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

5

Albero costo minimo

(Albero generatore minimo)

Minimum Spanning Tree:

albero che raggiunge tutti i vertici con un costo minimo

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

6

L’algoritmo di Dijkstra fornisce un albero che raggiunge tutti i vertici ma non al costo minimo

peso tot=2+2+1+7+2+2+20=18trovarne uno di peso minore(14)

B

G

AE F

C

H

D

2

22

22

7

6 1

4

33

B

G

AE F

C

H

D

2

6

2

1

4

2

7

3

2

3

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

7

Albero generatore minimoPeso = 14

B

G

AE F

C

H

D

2

22

22

7

6 1

4

33

8Conoscere, conoscersi, comunicare Sonia Fiori

Parte Quarta

AlgoritmiEsistono algoritmi anche per trovare gli

M.S.T (Minimum Spanning Tree):

• Algoritmo di Prim per gli alberi generatori

• Algoritmo di Kruskal per M.S.T

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

9

Algoritmo di Prim1. Si parte da un qualsiasi nodo e si scrivono i pesi

sui nodi ad esso collegato2. si sceglie il peso minore e si colora il nodo da

cui siamo partiti3. si scrivono i pesi, solo quello attuale, sui nodi ad

esso collegato se minore del precedente4. si ripetono i punti 2 e 3 finché tutti i nodi non

sono coloratiEsempio:

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

10

Esempio PrimB

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

11

Passo 1

B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

6

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

12

Passo 2B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

6

7

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

13

Passo 3B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

7

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

14

Passo 4B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

7

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

15

Passo 5B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

7

2

4

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

16

Passo 6B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

3

2

4

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

17

Passo 7 Fine

peso = 2+2+1+2+4+2+3 = 16 non è il minimo!

B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

3

2

4

2

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

18

Robert C. PrimRobert Clay Prim (nato 1921 in Sweetwater, Texas) è un matematico e

informatico americano.

Nel 1941, a 21 anni, si laurea in ingegneria elettronica all’Università di Princeton. Dopo nel 1949, riceve l’Ph.D. in matematica. Robert Prim ha lavorato all’ Università di Princeton dal 1948 al 1949 come ricercatore associato.

Durante il periodo della seconda guerra mondiale (1941 – 1944), Prim lovorò come ingegnere per la General Electric.

Dal 1944 fino al 1949, fu assunto dai laboratori dell’Artiglieria Navale degli Stati Uniti come ingegnere e successivamente come matematico. Fu direttore della ricerca matematica alla Bell Labobratories dal 1958 al 1961. Qui, Prim sviluppò nel 1957 il famoso Algoritmo di Prim. Dopo Bell Laboratories, Prim diventò vice presidente della ricerca al Sandia National Laboratories.

Durante la sua carriera al Bell Laboratories, Robert Prim collaborò con Joseph Kruskal sviluppando due differenti algoritmi, detti algoritmi ingordi (greedy) per trovare il minimum spanning tree in grafo connesso. Successivamente questi furono riscoperti da Dijkstra nel 1959.

 

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

19

Algoritmo di Kruskal• Si scrive una lista dei pesi in ordine

crescente

• Si colora il lato con il peso minore se non si forma un circuito

• Si termina quando si sono raggiunti tutti i nodi

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

20

Esempio ricerca M.S.TB

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

• 1• 2,2,2,2,2• 3,3• 4• 6• 7

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

21

Passo 1

• 1• 2,2,2,2,2• 3,3• 4• 6• 7

B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

22

Passo 2

• 1• 2,2,2,2,2• 3,3• 4• 6• 7

B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

23

Passo 3

• 1• 2,2,2,2,2• 3,3• 4• 6• 7

Peso = 14

Minimo!!

B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

24

Joseph Kruskal Joseph Bernard Kruskal, nato

nel 1929 a New York City è un statistico matematico. Studiò alle Università di Chicago e di Princeton; in quest'ultima conseguì nel 1954 il PhD. Nell'ambito dell'informatica contribuì con l'albero minimo di un grafo pesato, l'algoritmo di Kruskal nel 1956.

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

25

Due parole su Joseph Ceres

Sin dalla nascita, avvenuta a Port Kembla (Australia) nel settembre 1966 si e' dedicato al disegno, facendo di esso il veicolo espressivo della condizione umana e delle proprie forti emozioni.

La sua carica energetica ha coinvolto nell'infanzia molti dei suoi amici che ora svolgono anch'essi la professione artistica.

Tra le varie espressioni artistiche ha preferito la pittura ad olio, la quale meglio riesce a trasmettere la sua carica vitale, mediante la luce dei colori, che sono sempre vivi e caratterizzati da forti contrasti.

Lo stile dei quadri ricorda quello di Vincent Van Gogh, il suo artista preferito.

Naturalmente gli studi scolastici hanno seguito la strada artistica, prima con l'Istituto d'arte e poi con l'Accademia delle belle arti.

Attualmente vive e lavora a Bologna.

Joseph Ceres

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

26

Parole chiave

• Albero

• Albero generatore

• Minimum Spanning Tree

• Algoritmo Prim

• Algoritmo Kruskal

Parte Quarta Conoscere, conoscersi, comunicare Sonia Fiori

27

Fine

quarta parte