CONOSCERE CONOSCERSI COMUNICARE Joseph Ceres. Parte QuartaConoscere, conoscersi, comunicare Sonia...

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?


3

ProblemaDato un grafo non orientato trovare un

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


4

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

No! circuito No! non connesso Si! albero


5

Albero costo minimo

(Albero generatore minimo)

Minimum Spanning Tree:

albero che raggiunge tutti i vertici con un costo minimo


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


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


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:


10

Esempio PrimB

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3


11

Passo 1

B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

6


12

Passo 2B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

6

7

2


13

Passo 3B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

7

2


14

Passo 4B

G

AE F

C

H

D

2

22

22

7

6 1

4

3

3

2

1

2

7

2


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


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


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


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.


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


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


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


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


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


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.


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


26

Parole chiave

• Albero

• Albero generatore

• Minimum Spanning Tree

• Algoritmo Prim

• Algoritmo Kruskal


27

Fine

quarta parte

CONOSCERE CONOSCERSI COMUNICARE Joseph Ceres. Parte QuartaConoscere, conoscersi, comunicare Sonia...

Documents

Transcript of CONOSCERE CONOSCERSI COMUNICARE Joseph Ceres. Parte QuartaConoscere, conoscersi, comunicare Sonia...