CONOSCERE CONOSCERSI
COMUNICARE
Joseph Ceres
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
2
Problema
Dato un grafo non orientato trovare un
sottoinsieme, albero, che raggiunga tutti i
vertici al minor costo
Parte Quarta
Conoscere, conoscersi, comunicare
Sonia Fiori
3
Albero
Grafo non orientato connesso senza circuiti.
Quale tra questi è un albero?
No! circuito
Parte Quarta
No! non connesso
Conoscere, conoscersi, comunicare
Sonia Fiori
Si! albero
4
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
5
L’algoritmo di Dijkstra fornisce un albero che
raggiunge tutti i vertici ma non al costo minimo
C
B
7
2
3
2
E
F
3
A
D
2
6
2
1
2
G
4
C
B
H
7
2
peso tot=
2+2+1+7+2+2+20=18
6
trovarne uno di peso minore
(14)
3
2
E
2
A
Parte Quarta
3
F
D
2
1
G
4
Conoscere, conoscersi, comunicare
Sonia Fiori
2
H
6
Albero generatore minimo
Peso = 14
C
B
7
2
3
2
E
2
A
D
2
1
6
G
Parte Quarta
3
F
4
Conoscere, conoscersi, comunicare
Sonia Fiori
2
H
7
Algoritmi
Esistono 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
8
Algoritmo di Prim
1. Si parte da un qualsiasi nodo e si scrivono i pesi
sui nodi ad esso collegato
2. si sceglie il peso minore e si colora il nodo da
cui siamo partiti
3. si scrivono i pesi, solo quello attuale, sui nodi ad
esso collegato se minore del precedente
4. si ripetono i punti 2 e 3 finché tutti i nodi non
sono colorati
Esempio:
Parte Quarta
Conoscere, conoscersi, comunicare
Sonia Fiori
9
Esempio Prim
C
B
7
2
3
2
E
2
A
3
F
D
6
G
Parte Quarta
2
1
4
Conoscere, conoscersi, comunicare
Sonia Fiori
2
H
10
Passo 1
C
B
7
2
2
3
2
E
2
A
3
F
D
6
2
1
2
6
G
Parte Quarta
4
Conoscere, conoscersi, comunicare
Sonia Fiori
H
11
Passo 2
C
B
7
7
2
2
3
2
E
A
2
3
F
2
6
D
2
1
2
6
G
Parte Quarta
4
Conoscere, conoscersi, comunicare
Sonia Fiori
H
12
Passo 3
C
B
7
7
2
2
3
2
E
A
2
2
6
3
F
D
2
2
1
2
1
G
Parte Quarta
4
Conoscere, conoscersi, comunicare
Sonia Fiori
H
13
Passo 4
C
B
7
7
2
2
3
2
E
A
2
2
6
3
F
D
2
2
1
2
1
G
Parte Quarta
4
Conoscere, conoscersi, comunicare
Sonia Fiori
H
14
Passo 5
C
B
7
7
2
2
3
2
E
A
2
2
6
3
F
2
2
2
1
1
G
Parte Quarta
D
2
4
4
Conoscere, conoscersi, comunicare
Sonia Fiori
H
15
Passo 6
C
B
7
3
2
2
3
2
E
A
2
2
6
3
F
2
2
2
1
1
G
Parte Quarta
D
2
4
4
Conoscere, conoscersi, comunicare
Sonia Fiori
H
16
Passo 7 Fine
C
B
7
3
2
2
3
2
E
A
2
2
6
3
F
2
2
2
1
1
G
D
2
4
4
H
peso = 2+2+1+2+4+2+3 = 16 non è il minimo!
Parte Quarta
Conoscere, conoscersi, comunicare
Sonia Fiori
17
Robert C. Prim
Robert 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
18
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
19
Esempio ricerca M.S.T
C
B
7
2
3
2
E
2
A
3
F
D
6
G
Parte Quarta
2
1
4
2
•
•
•
•
•
•
1
2,2,2,2,2
3,3
4
6
7
H
Conoscere, conoscersi, comunicare
Sonia Fiori
20
Passo 1
C
B
7
2
3
2
E
2
A
3
F
D
6
G
Parte Quarta
2
1
4
2
H
Conoscere, conoscersi, comunicare
Sonia Fiori
•
•
•
•
•
•
1
2,2,2,2,2
3,3
4
6
7
21
Passo 2
C
B
7
2
3
2
E
2
A
3
F
D
6
G
Parte Quarta
2
1
4
2
H
Conoscere, conoscersi, comunicare
Sonia Fiori
•
•
•
•
•
•
1
2,2,2,2,2
3,3
4
6
7
22
Passo 3
C
B
7
2
3
2
E
2
A
3
F
D
6
G
Parte Quarta
2
1
4
2
H
Conoscere, conoscersi, comunicare
Sonia Fiori
• 1
• 2,2,2,2,2
• 3,3
• 4
• 6
• 7
Peso = 14
Minimo!!
23
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
24
Joseph Ceres
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 megl io
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.
Parte Quarta
Conoscere, conoscersi, comunicare
Sonia Fiori
25
Parole chiave
•
•
•
•
•
Albero
Albero generatore
Minimum Spanning Tree
Algoritmo Prim
Algoritmo Kruskal
Parte Quarta
Conoscere, conoscersi, comunicare
Sonia Fiori
26
Fine
quarta parte
Parte Quarta
Conoscere, conoscersi, comunicare
Sonia Fiori
27