Le lingue
Pagine
Legale
0
1
0
1
1
0
0110
Gli alberi binari sono contenitori efficienti
0
1
0
1
1
0
0110
Da notare la ricorsione:quello che si fa per 0110
lo si ripete per 110
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLA
DANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ALBERO BINARIO DI RICERCA
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLA
DANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ELENA
ALBERO BINARIO DI RICERCA
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLA
DANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ELENA
ALBERO BINARIO DI RICERCA
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLA
DANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ELENA
ALBERO BINARIO DI RICERCA
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLA
DANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ELENA
ALBERO BINARIO DI RICERCA
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLA
DANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ELENA
ALBERO BINARIO DI RICERCA
MARIO
SANDRA
VALERIO
STEFANO
UGO
ELISA
PAOLO
ROBERTOMINO
MICHELENICOLADANIELA
FABIO
FRANCO
FILIPPO
EMILIA
ALBERTO
ANDREA
ANNA
BRUNO
CARLO
ELENA
ALBERO BINARIO DI RICERCA
F
R
E
H
TM
C
BNZP
F
M
B
P
E
H
B
E
B
B
F
R
E
H
TM
C
BNZP
F
M
B
P
E
H
B
E
B
B
Dati n giocatori, come costruire il tabellone ?
Dati n giocatori, quante sono le partite ?
Disponendo di molti campi, quanto dura il torneo ?
Disponendo di m campi, quanto dura il torneo ?
Dati n giocatori, quante sono le partite ?
trovare un invariante
per ogni partita c’è una vittoria e una sconfitta
ogni giocatore (tranne il vincitore del torneo) perde esattamente una volta
il numero di partite è uno meno del numero di giocatori
F
R
E
H
TM
C
BNZP
F
M
B
P
E
H
B
E
B
B
foglie = giocatori
nodi interni = partite
# nodi interni =# foglie - 1
e le vittorie come sono distribuite ?
esiste una qualche regolarità o no?
il vincitore vince sempre
c’è qualcuno che non vince mai (cioè gioca una sola volta e perde)?
partite = vittorie
almeno uno che non vince esiste
A
BC
DE
BC
D
E
esattamente uno?
e le vittorie come sono distribuite ?
esiste una qualche regolarità o no?
il vincitore vince sempre
c’è qualcuno che non vince mai (cioè gioca una sola volta e perde)?
nessuno vince (tranne uno)
A
BC
DE
AA
A
A
partite = vittorie
D
EF
G
H
B
B
B
B
C
C
data una distribuzione arbitraria di vittorie, esiste un tabellone che la rappresenta ?
8 giocatori 7 vittorie in totale
A, B - 3 vittorie; C - 1 vittoria; D, E, F, G, H 0 vittorie
A
C
D
E
F
G
A A A A
B
AA
A
A
DC
CE
BB
BB
H
GF
H
Disponendo di molti campi, quanto dura il torneo ?
7+11+5+13+6+8+4+10+9+15+12+6+8+16
711 513 6 8
410
91512 6
8
16
18
18
14
14
24
18
36
28
42
24
64
66
130
tempo logaritmico con sufficienti processori
35
22 19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6 12
5 6 3
22 19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6 12
5 6 3
Rimozione del massimo
7 4
22 19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6 12
5 6
3
7 4
Rimozione del massimo
22
19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6 12
5 6
3
7 4
Rimozione del massimo
22
19
10
21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6 12
5 6
3
7 4
Rimozione del massimo
22
19
10
21
7 9
6 1 8 1
15
3
7 9 2 2
17 8
6 12
5 6
3 7 4
Rimozione del massimo
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5 63
costo log n
7 4
Rimozione del massimo
18
35
22 19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6 12
5 6 3
Aggiungere un elemento
7 4
18
35
22 19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
17 8
6
125 6 3
7 4
Aggiungere un elemento
17
35
22 19
10 21
7 9
6 1 8 1
15 3
7 9 2 2
18 8
6
125 6 3
costo log n
7 4
Aggiungere un elemento
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5 63
35
7 4
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5 63
35
7 4
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5
6
3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5
6
3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5
6
3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
3
7
9
2 2
17 8
6 12
5
6
3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
37
9
2 2
17 8
6 12
56 3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
37
9
2 2
17 8
6 12
5
6 3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
37
9
2 2
17 8
6 12
5
6 3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
37
9
2 2
17
8
6 12
5
6 3
35
7 4
22
19
10
21
7 9
6 1 8 1
15
37
9
2 2
17
8
6
12
5
6 3
35
7 4
alberi genealogici
padre madre
nonno nonno nonnanonna
piccolo conto
3 generazioni per secolo
30 generazioni fino all’anno 1000
un miliardo !
non esistevano tanti abitanti
?1) molti antenati sono la stessa persona2) abbiamo tutti antenati comuni
A B C D
G H I
K M
E F
J
N
A B C D
E F G H
I L
M
Codice Morse (apparentemente) binario
A 01 N 10 B 1000 O 111C 1010 P 0110D 100 Q 1101E 0 R 010F 0010 S 000G 110 T 1H 0000 U 001I 00 V 0001J 0111 W 011K 101 X 1001L 0100 Y 1011M 11 Z 1100
Codice Morse (apparentemente) binario
A 01 N 10 B 1000 O 111C 1010 P 0110D 100 Q 1101E 0 R 010F 0010 S 000G 110 T 1H 0000 U 001I 00 V 0001J 0111 W 011K 101 X 1001L 0100 Y 1011M 11 Z 1100
A 01 N 10 B 1000 O 111C 1010 P 0110D 100 Q 1101E 0 R 010F 0010 S 000G 110 T 1H 0000 U 001I 00 V 0001J 0111 W 011K 101 X 1001L 0100 Y 1011M 11 Z 1100
Codice Morse (apparentemente) binario
A 01 N 10 B 1000 O 111C 1010 P 0110D 100 Q 1101E 0 R 010F 0010 S 000G 110 T 1H 0000 U 001I 00 V 0001J 0111 W 011K 101 X 1001L 0100 Y 1011M 11 Z 1100
Codice Morse (apparentemente) binario
A 01 N 10 B 1000 O 111C 1010 P 0110D 100 Q 1101E 0 R 010F 0010 S 000G 110 T 1H 0000 U 001I 00 V 0001J 0111 W 011K 101 X 1001L 0100 Y 1011M 11 Z 1100
Codice Morse (apparentemente) binario
arrivo domani
01010010000001111 100111110110000101001000000111110011111011000entelesomitongi
00
0100 0101
011 100
10101011
110 111
010100100000011111001111101100
Codice di Huffman
a 16e 25m 12p 6r 10t 8z 2
Codice di Huffman
a 16e 25m 12p 6r 10t 8z 2
minimi
z p
t
Codice di Huffman
a 16e 25m 12(pz) 8r 10t 8
minimi
z p
Codice di Huffman
a 16e 25m 12(pzt) 16r 10
minimi
z p
t m r
a
Codice di Huffman
a 16e 25(mr) 22(pzt) 16
minimi
z p
t m r
e
Codice di Huffman
(apzt) 32e 25(mr) 22 minimi
z p
t m r
a
Codice di Huffman
(apzt) 32(emr) 47
z p
t m r
a e
a 16 00e 25 11m 12 100p 6 0101r 10 101t 8 011z 2 0100
Top Related