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