Prof. Fabrizio Camuso www.camuso.it Diap. 1

Divina proportione …Divina proportione …

1:a=a:b

0,618

Prof. Fabrizio Camuso www.camuso.it Diap. 2

In geometria …In geometria …

Il rettangolo aureo

Prof. Fabrizio Camuso www.camuso.it Diap. 3

In geometria …In geometria …

Pentagono e pentangolo

Prof. Fabrizio Camuso www.camuso.it Diap. 4

In geometria …In geometria …

Spirale aurea

Prof. Fabrizio Camuso www.camuso.it Diap. 5

Nella natura !!Nella natura !!

Spirale aurea

• fasi di sviluppo di esseri viventi• conchiglie• parte inferiore onde marine• corna, zanne, becchi, artigli• galassie• coda comete• posizione ombelico

Prof. Fabrizio Camuso www.camuso.it Diap. 6

Fibonacci - 1Fibonacci - 1

0 1 1 2 3 5 8 13 21 34 …

Prof. Fabrizio Camuso www.camuso.it Diap. 7

Fibonacci - 2Fibonacci - 2

Sulla testa di un tipico girasole, per esempio, il numero delle spirali rientra molto spesso in questo schema:  89 spirali che si irradiano ripide in senso orario; 55 che si muovono in senso antiorario e 34 che si muovono in senso orario ma meno ripido. Questi sono tre numeri adiacenti delle sequenza di Fibonacci. Il più grande girasole che si sia mai conosciuto aveva 144, 89 e 55 spirali.

Prof. Fabrizio Camuso www.camuso.it Diap. 8

Fibonacci - 3Fibonacci - 3

In molte specie vegetali, prime fra tutte le Astaracee (girasoli, margherite, ecc.), il numero dei petali di ogni fiore è di solito un numero di Fibonacci, come 5, 13, 55 o perfino 377, come nel caso della diaccola.

Prof. Fabrizio Camuso www.camuso.it Diap. 9

Fibonacci - 4Fibonacci - 4

In molte specie vegetali, prime fra tutte le Astaracee (girasoli, margherite, ecc.), il numero dei petali di ogni fiore è di solito un numero di Fibonacci, come 5, 13, 55 o perfino 377, come nel caso della diaccola.

E le pigne ???

Prof. Fabrizio Camuso www.camuso.it Diap. 10

Fibonacci - 5Fibonacci - 5Le foglie sono disposte sui rami in modo tale da non coprisi l’una con l’altra per permettere a ciascuna di esse di ricevere la luce del sole. Se prendiamo come punto di partenza la prima foglia di un ramo e passiamo di foglia in foglia in senso orario o antiorario, il numero di giri che compiremo prima di trovare una foglia sopra quella di partenza corrisponde sempre ad un numero di Fibonacci.

Partendo da una foglia qualunque, dopo uno, due, tre o cinque giri dalla

spirale si trova sempre una foglia allineata con la prima. a seconda

delle specie, questa sarà la seconda, la terza, la quinta, l'ottava o la

tredicesima foglia.

Prof. Fabrizio Camuso www.camuso.it Diap. 11

Fibonacci – 6 Fibonacci – 6

I NUMERI DI FIBONACCI E LA BORSA DI MILANOUn’applicazione moderna dei numeri di Fibonacci si può riscontrare presso la borsa azionistica di Milano. Prendendo spunto da Leonardo Fibonacci da Pisa, uno dei più grandi protagonisti della storia della matematica, Ralph Elson Elliot elaborò una precisa teoria di previsione dei mercati finanziari con la quale in tempi recenti sono stati anticipati i più grandi rialzi e i più grandi crolli di borsa. Usando le onde di Elliot ed i numeri di Fibonacci, il docente universitario G. Migliorino ha previsto con incredibile precisione il punto minimo del drammatico ribasso dell’estate ‘98. .

Prof. Fabrizio Camuso www.camuso.it Diap. 12

Fibonacci – 7 Fibonacci – 7

I NUMERI DI FIBONACCI NEL PROCESSORE PENTIUMI numeri di Fibonacci sono utilizzati anche nel sistema informatico di molti computer. In particolare vi è un complesso meccanismo basato su tali numeri, detto "Fibonacci heap" che viene utilizzato nel processore Pentium della Intel per la risoluzione degli algoritmi.

Prof. Fabrizio Camuso www.camuso.it Diap. 13

Fibonacci – 8 Fibonacci – 8 Anche la musica non sfugge al fascino del rapporto aureo. Anzitutto le note: in una scala completa (compreso il do della scala successiva) i rapporti fra le note corrispondono molto precisamente ai numeri di Fibonacci …

Un ambiente d' ascolto, ma anche una cassa acustica, minimizzerà le risonanze se le dimensioni sono in rapporto aureo tra loro. 

Ancora oggi la sezione aurea è ampliamente utilizzata: le dimensioni standard di carte di credito, tessere telefoniche, badge per ogni applicazione, corrispondono (salvo tolleranze di fabbricazione) al rettangolo aureo. 

Prof. Fabrizio Camuso www.camuso.it Diap. 14

Fibonacci – 9 Fibonacci – 9

George Cardas decide di sfruttare il concetto di rapporto aureo per la costruzione di cavi audio ad alte prestazioni e questa trovata e' protetta da ben due brevetti (US Pat. 4.628.151 e 4.980.517).

Prof. Fabrizio Camuso www.camuso.it Diap. 15

FibonacciFibonacci(Versione Iterativa)(Versione Iterativa)

/* versione iterativa */int fib_ite(int num){ int i=0, prossimo=0, unoIndietro=0,dueIndietro=0;

if (num==1) return 0; else if (num==2) return 1 else; { dueIndietro=0; unoIndietro=1; for (int i=3; i<=num; i++) { prossimo=unoIndietro+dueIndietro; dueIndietro=unoIndietro; unoIndietro=prossimo; } return prossimo } }

0 1 1 2 3 5 8 13 …

dueIndietro unoIndietro

prossimo

0 1 1 2 3 5 8 13 ? …

dueIndietro

unoIndietro

prossimo

Prof. Fabrizio Camuso www.camuso.it Diap. 16

FibonacciFibonacci(Versione Ricorsiva)(Versione Ricorsiva)

/* versione ricorsiva */int fib_ric(int num){ if (num==1) return 0; else if (num==2) return 1; else return fib_ric(num-2)+fib_ric(num-1); }

NienteVar locali !!

Base della ricorsione

Passo ricorsivo

Prof. Fabrizio Camuso www.camuso.it Diap. 17

La torre di Hanoi - 1La torre di Hanoi - 1

* Di cosa si tratta …(videolezione ‘Ricorsione’ - minuto19.45)

Prof. Fabrizio Camuso www.camuso.it Diap. 18

La torre di Hanoi – 2La torre di Hanoi – 2(versione iterativa)(versione iterativa)

????????????

protected void iterativeSolve(int n, int da, int a, int per) {int[] pioli = {da, a, per};int dim;int n_mvs;int from;int to; for (int i = 0; i < mvlist.length; i++) {dim = calcDim(i + 1);n_mvs = i / (int)Math.pow(2, dim) + 1 / 2;if ((n - dim + 1) % 2 == 1) { from = (int)(n_mvs % 3); to = (from + 1) % 3;} else { from = (int)(-(n_mvs % 3 - 3) % 3); to = (from + 2) % 3;}mvlist[i] = new HanoiMove(pioli[from], pioli[to]);}} private int calcDim(int mv) {int pos = 0;while (mv > 0) { pos++; if (mv % 2 == 1) mv = 0; else mv /= 2;}return pos;}

Prof. Fabrizio Camuso www.camuso.it Diap. 19

La torre di Hanoi – 3La torre di Hanoi – 3(versione ricorsiva) (versione ricorsiva)

void move(int N, int start, int final, int temp) { if (count > 0) { move(N-1,start,temp,final); cout << "Muovi da {0} a {1}\n“ << start << final; move(N-1,temp,final,start); } }

Passo ricorsivo

Passo ricorsivo

Dov’è la base della ricorsione ?

Prof. Fabrizio Camuso www.camuso.it Diap. 20

Strutture ad albero – 1Strutture ad albero – 1Radice (root)

nodo

arco

foglia

figlio

fratelli

Struct Nodo{ string info; sx: Nodo *; dx: Nodo *; }

Prof. Fabrizio Camuso www.camuso.it Diap. 21

Strutture ad albero – 2Strutture ad albero – 2

void stampa(Nodo * albero){ if (albero!=null) { stampa(albero->sx); cout << albero->info << endl; stampa(albero->dx) }}

StampaAlbero(inizio)

StampaAlbero(inizio^.sx) StampaAlbero(inizio^.dx)

StampaAlbero(inizio^.sx^.sx)StampaAlbero(inizio^.dx^.dx)

……

StampaAlbero(nil)StampaAlbero(nil) StampaAlbero(nil)

Ma non è

tutto oroquelloche

luccica …

Prof. Fabrizio Camuso www.camuso.it Diap. 22

Altre applicazioniAltre applicazionialgoritmi importanti prontialgoritmi importanti prontiper le architetture paralleleper le architetture parallele

int binsearch(int a[], int sx, int dx, int el) { int x; if (dx < sx) return -1;

x = (dx + sx)/2; if (el < a[x]) return binsearch(a,sx,x-1,el); else if (el == a[x]) return x; else return binsearch(a,x+1,dx,el); }

Prof. Fabrizio Camuso www.camuso.it Diap. 23

Altre applicazioni - quicksortAltre applicazioni - quicksort

Prof. Fabrizio Camuso www.camuso.it Diap. 24

Altre applicazioni – XML parsingAltre applicazioni – XML parsing

Prof. Fabrizio Camuso www.camuso.it Diap. 25

Altre applicazioni – backtrackingAltre applicazioni – backtracking

Una tecnica classica consiste nell'esplorazione di strutture ad albero e tenere traccia di tutti i nodi e i rami visitati in precedenza, in modo da poter tornare indietro al più vicino nodo che conteneva un cammino ancora inesplorato nel caso che la ricerca nel ramo attuale non abbia successo.

Esiste addirittura un famoso linguaggio di programmazione usatissimo per risolvere problemi di intelligenza artificiale basato interamente per il suo funzionamento sul backtracking: il prolog

Prof. Fabrizio Camuso www.camuso.it Diap. 26

Riassumendo …Riassumendo …

La base della ricorsione: è il caso più semplice, quello per il quale sappiamo subito ‘calcolare’ il risultato. Quello a cui il meccanismo ricorsivo tenta di ricondursi un poco alla volta, passo dopo passo.

Il passo ricorsivo: quando non siamo di fronte al caso più semplice dobbiamo tentare di esprimerlo attraverso una ‘formula’ che richiama lo stesso sottoprogramma che stiamo scrivendo ma con argomenti semplificati che ci avvicinano al caso che rappresenta la base della ricorsione

Prof. Fabrizio Camuso www.camuso.it Diap. 27

Fattoriale …Fattoriale …

1 se N =0

N * Fatt(N-1) se N>0

Fatt( N ) =

Prof. Fabrizio Camuso www.camuso.it Diap. 28

xxy y , con x e y interi positivi, con x e y interi positivi

1 se y =0

x * XallaY(x,y-1) se y>0

XallaY(x,y) =

Prof. Fabrizio Camuso www.camuso.it Diap. 29

X * YX * Y

x se y =1

x + XperY(x,y-1) se y>0

XperY(x,y) =

Prof. Fabrizio Camuso www.camuso.it Diap. 30

FibonacciFibonacci

0 se N =1, 1 se N=2

Fib(N-2)+Fib(N-1) se N>2

Fib(n) =