Francesco Fassò, Andrea Giacobbe

Università degli studi di Padova

Note del corso di
Laboratorio Computazionale
A.A. 2009—2010

Capitolo 3: i frattali

3.1 Frattali per svuotamento od iterazione

La teoria è stata spiegata in classe, per approfondimenti esistono molti libri, uno completo è H.O. Peitgen, H Jurgens, D.Saupe, Chaos and Fractals - New Frontiers of Science, Springer (1992)

Vogliamo scrivere una funzione che disegna l'approssimazione all'ordine n dell'insieme ternario di Cantor.

Un modo di produrre il disegno è di scrivere una procedura funzionale—iterativa:
■ si scrive una funzione elementare che prende un segmento e ne produce due,
■ si applica iterativamente questa funzione.

3.1 Frattali per svuotamento od iterazione

Un segmento è costituito da due estremi, è dato come primitiva grafica Line[{(Subscript[p, 1]),(Subscript[p, 2])}] oppure come lista di due punti {(Subscript[p, 1]),(Subscript[p, 2])}. L'insieme di Cantor è dato da una lunga lista di Lines che uniscono i punti degli intervallini di lunghezza (1/(3^k))

Dobbiamo quindi definire una funzione che lavora o su liste di Lines, o su liste dei punti, e che, ad un segmento {(Subscript[p, 1]), (Subscript[p, 2])} associa la coppia di segmenti

{{(Subscript[p, 1]), (Subscript[p, 1])+(((Subscript[p, 2])-(Subscript[p, 1]))/3)},{(Subscript[p, 2])-(((Subscript[p, 2])-(Subscript[p, 1]))/3), (Subscript[p, 2])}}.

Questa operazione prende un segmento e produce due segmenti, ognuno di lunghezza (1/3) della lunghezza di {(Subscript[p, 1]),(Subscript[p, 2])}

Si procederà poi per iterazioni successive della funzione elementare:
■ la si mappa con Map su liste di coppie di punti,
■ si usa poi Nest per iterare il processo

3.1 Frattali per svuotamento od iterazione

Esercizio 3.1.1: scrivere la funzione Cantor[n] che produce l'oggetto grafico che mostra l'insieme di Cantor a profondità n

Ci sono molti modi di farlo. Viene subito voglia di definire una funzione elementare

sdoppia[sgm_]:={{sgm[[1]],sgm[[1]]+((sgm[[2]]-sgm[[1]])/3)},{sgm[[2]]-((sgm[[2]]-sgm[[1]])/3),sgm[[2]]}}

Il problema è che la "funzione elementare" parte da una lista di due numeri reali (ovvero un punto), ed arriva su di una lista che contiene due liste di due numeri reali (ovvero due punti).

3.1 Frattali per svuotamento od iterazione

È evidente che questa funzione non è pronta ad essere iterata, perché dominio e codominio non sono uguali.

Bisogna quindi definire una "funzione elementare 2" che crea delle nested lists, che bisogna poi "sciogliere" con Flatten

Poi si produce la Figura. Basta trasformare la lista di coppie di punti in una lista di segmenti, mappandogli sopra la primitiva grafica Line

Infine si crea l'oggetto grafico usando Graphics

3.1 Frattali per svuotamento od iterazione

Abbiamo definito la funzione sdoppia, vediamo cosa produce

segmento={{0,0},{1,0}};
sdoppia[segmento]

TreeForm[%,2]

3.1 Frattali per svuotamento od iterazione

Ma se si mappa di nuovo la funzione sdoppia, sballano le parentesi

TreeForm[Map[sdoppia,%%],3]

3.1 Frattali per svuotamento od iterazione

Per rimediare si deve "appiattire" la lista

Flatten[Map[sdoppia,sdoppia[segmento]],1]

Definiamo quindi una nuova mappa Cantor2 che fa queste due cose

sdoppia2[lista_]:=Flatten[Map[sdoppia,lista],1]

3.1 Frattali per svuotamento od iterazione

Per ottenere l'insieme di Cantor ad una certa profondità, dobbiamo iterare l'applicazione della funzione Cantor2

sdoppia2[{{{0,0},{1,0}}}];
sdoppia2[%]
sdoppia2[%]
sdoppia2[%]

3.1 Frattali per svuotamento od iterazione

Gli oggetti che abbiamo generato hanno effettivamente la profondità giusta

TreeForm[%%%,2]

3.1 Frattali per svuotamento od iterazione

TreeForm[%%%,2]

Dimensions[%%%]

3.1 Frattali per svuotamento od iterazione

Scriviamo infine la famiglia di intervalli come funzione di n.

Per farlo, introduciamo il comando Nest. Basta scrivere il comando per capire cosa fà

Nest[f,x,3]

Visto che ci siamo, mostriamo la differenza tra Nest e NestList.

NestList[f,x,3]

3.1 Frattali per svuotamento od iterazione

cantor[segmento_,n_]:=Nest[sdoppia2,{segmento},n]

cantor[segmento,0]

cantor[segmento,1]

cantor[segmento,2]

cantor[segmento,3]

3.1 Frattali per svuotamento od iterazione

Disegnamo le immagini. Proviamo prima a scegliere una "profondità"

n=3;
Map[Line,cantor[segmento,n]]
n=.

Definiamo ora la mappa che ha la "profondità" come variabile. Usiamo il segmento [0,1] come default

Cantor[n_]:=
Graphics[Map[Line,cantor[{{0,0},{1,0}},n]],
PlotRange->{{0,1},{-1/100,1/100}}, 
AspectRatio->(1/100),ImageSize->{500,Automatic}]

3.1 Frattali per svuotamento od iterazione

Facciamo i disegni

GraphicsGrid[Transpose[{Table[Cantor[i],{i,1,7}]}]]

3.1 Frattali per svuotamento od iterazione

Passiamo ora a costruzioni un pò più complicate.

Costuiamo la curva di Koch, che è continua ma non è differenziabile in alcun punto

3.1 Frattali per svuotamento od iterazione

Per produrla, si può procedere come per il Cantor.

Invece di creare un "buco" in un segmento, lo si trasforma in una poligonale

3.1 Frattali per svuotamento od iterazione

l'Autosimilarità è evidentissima.

È istruttivo ingrandire molto la sesta o settima o ottava iterazione: appare con evidenza la struttura locale del koch

3.1 Frattali per svuotamento od iterazione

Esercizio 3.1.2i: scrivere la funzione Koch[n] che produce l'oggetto grafico che mostra l'insieme di Koch a profondità n

Suggerimento: Questo esercizio si può risolvere applicando ad un oggetto grafico una funzione che lo trasforma in un altro oggetto grafico del medesimo tipo. Infatti Ogni curva di Koch è una spezzata del tipo Line[{{(Subscript[P, 0]),(Subscript[P, 1])},...{(Subscript[P, n-1]),(Subscript[P, n])}}]

3.1 Frattali per svuotamento od iterazione

Una variante alla curva di Koch è  il fiocco di neve di Koch. Si inizia non con un segmento, ma con un triangolo.

Ad ogni lato del triangolo si agisce come si è fatto con il segmento.

Esercizio 3.1.2ii: scrivere la funzione FioccoKoch[n] che produce l'oggetto grafico che mostra il fiocco di neve di Koch a profondità n

3.1 Frattali per svuotamento od iterazione

Esercizio 3.1.2iii: scrivere la funzione Gasket[n] che produce l'oggetto grafico che mostra il setaccio di Sierpinski a profondità n

Si procede come per Koch, ma l' oggetto è un triangolo (un Polygon), che viene diviso in 4 triangoli di cui uno viene scartato

Suggerimento: si tratta di fare quanto già fatto in passato. Invece di avere una funzione  che prende una spezzata Line[{lista di punti}] e porge un'altra spezzata , vogliamo una funzione che prende una lista di triangoli {Polygon[{VA, VB, VC}],...} e porge una lista di  triangoli {Polygon[{VA', VB', VC'}], ...}

3.1 Frattali per svuotamento od iterazione

Esercizio 3.1.2iv: scrivere la funzione Carpet[n] che produce l'oggetto grafico che mostra il tappeto di Sierpinski a profondità n

Si procede come per il setaccio, ma l' oggetto è un quadrato (sempre un Polygon), che viene diviso in 9 quadrati ed uno (quello centrale) viene scartato

3.1 Frattali per svuotamento od iterazione

Con lo stesso procedimento, dal cubo si tolgono 3 "carote" di base un cubicino di lato 1/3. Dopo 2 iterazioni...

Esercizio 3.1.2v: scrivere la funzione Monge[n] che produce l'oggetto grafico che mostra la spugna di Monge a profondità n

3.2 Gli L–sistemi

Perché strutture complesse, magari di tipo frattale, sono così frequenti in natura? Come è possibile che la complessità emerga da regole semplici, per esempio da una dinamica semplice?

Gli L–sistemi sono un metodo per generare strutture complesse a partire dall'iterazione di regole semplici.

Possono essere usati per costruire insiemi frattali, con un procedimento dierso da quello visto finora.

Introdotti dal biologo A.Lindenmayer alla fine degli anni 60  per descrivere la crescita delle piante.

3.2 Gli L–sistemi

Che tipo di regole devono governare lo sviluppo di un albero, per portare alla sua struttura finale?

Idea: processi che possono essere descritti in termini di pochi stati, che si replicano secondo regole semplici.

Esempi:
■ divisione cellulare in organismi multicellulari–le cellule non si dividono una alla volta, ma molte possono dividersi allo stesso tempo,
■ crescita di una pianta: ogni ramo genera altri rami, secondo un certo schema più o meno predefinito.

3.2 Gli L–sistemi

Modellizazione:
■ gli stati possibili: sono stringhe formate da 2 o più caratteri a, b di qualunque lunghezza: a ,a b ,a b b , a b b a, etc.

■ le regole di riscrittura: se a->b e  b->a b,  allora a b andrà in b a b, che a sua volta andrà in a b b a b,  e poi in b a b a b b a b,  e così via. Questa regola di riscrittura si dice in parallelo.

■ rappresentazione grafica/geometrica di L–sistemi semplici: in termini di un turtle–walk. Nel

Nel nostro caso specifico:

1. ci sono 3 simboli: P, d, s

2. c'è una regola di riscrittura: eg, P va sostituito con P d P s P P (o quel che si voglia)

3. vogliamo rappresentare ogni stato, cioè ogni stringa P P s P d P in modo grafico

3.2 Gli L–sistemi

Idea: una stringa P P s P d P P s viene rappresentata come una passeggiata di una tartaruga che si muove in accordo alle seguenti regole:

■ Simbolo P: la tartaruga fa un passo avanti
■ Simbolo d: la tartaruga ruota in senso orario di un angolo prefissato, che è un parametro del sistema (per es. π/2)
■ Simbolo s: la tartaruga ruota in senso antiorario dello stesso angolo

NB: Decidiamo che, in una stringa agiscono prima i caratteri a sinistra. È il contrario della composizione di funzioni, ma ci riuscirà più semplice scrivere le stringhe che fanno una determinata azione.

3.2 Gli L–sistemi

PPsPd

PsPsPsP

3.2 Gli L–sistemi

Vogliamo rappresentare il turtle walk. Implementiamo l'idea al computer

Al solito, ci sono molti modi di farlo. Un modo per farlo richiede di

■ Scrivere un algoritmo che produce le stringhe, applicando iterativamente la rewriting rule ad una stringa di partenza

■ Trasformare una data stringa in una poligonale (lista di punti) per mezzo delle regole del moto delle tartarughe

■ Produrre il disegno di questa poligonale.

La sola parte un pò delicata è la seconda

3.2 Gli L–sistemi

Il nostro alfabeto è costituito dalle lettere P d ed s

Cominciamo con lo scrivere una funzione rr[stringa] che esegue una regola di riscrittura: 
ad esempio: P->P d P s P

La regola dipende dal tipo di problema. Usiamo questa regola solo per testare le funzioni.

3.2 Gli L–sistemi

Si deve prendere una stringa di caratteri e sostituire ogni P con PdPsP.

In Mathematica, la sostituzione di caratteri in una stringa si fa con

StringReplace[stringa, "P"-> "...."]

rr[stringa_]:=StringReplace[stringa, "P"->"PdPsP"]

rr["PPd"]

3.2 Gli L–sistemi

Scriviamo poi una funzione rr[stringa, n] che itera rr per n–volte, e ci da solo il risultato finale

rr[stringa_,n_]:=Nest[rr,stringa,n]

rr["P",2]

3.2 Gli L–sistemi

Dobbiamo ora trasformare una stringa "PdPs..." nella corrispondente lista di simboli 
{P, d, P, s, ...}

La differenza è che adesso P,d,s sono simboli, non più caratteri. Il vantaggio è che poi a questi simboli potremo associare delle funzioni (avanza, ruota orario, ruota antiorario)

Come si fa?

■ trasformiamo la stringa nella lista dei suoi caratteri: Characters[stringa]
■ siccome questi sono ancora caratteri (cioè la loro Head è String), dobbiamo trasformarli in simboli, cioè in oggetti che hanno per Head il tipo Symbol

Characters["abc"]

3.2 Gli L–sistemi

%//FullForm

{a,b,c}//FullForm

Head/@%%
(* come Map[Head,%%] *)

Head/@%%

Come detto, la lista non è fatta di simboli, ma di stringhe.

La funzione che trasforma una stringa nella corrispondente lista di simboli è Symbol

3.2 Gli L–sistemi

Se applichiamo la funzione Symbol ad una String allora la String diviene un Symbol

"a"//Head
Symbol["a"]//Head

Definiamo quindi una funzione che prenda la stringa e restituisce una lista di simboli

symb[stringa_]:=Map[Symbol,Characters[stringa]]

Vediamo se funziona

symb["abc"]

Vediamo se è davvero una lista di simboli

Map[Head,%]

3.2 Gli L–sistemi

Così non abbiamo più una lista di stringhe ma una lista di simboli

symb["P"//rr]

symb["P"//rr//rr]

Meglio

symb[rr["P",2]]

3.2 Gli L–sistemi

Preliminarmente, come rappresentiamo lo stato della tartaruga?

Abbiamo bisogno di specificare

■ la posizione della tartaruga: x∈(ℝ^2)

■ la sua orientazione: v∈(ℝ^2), |v|=1

Dunque, lo stato della tartaruga è una coppia (x, v).

Dobbiamo ora specificare come (x,v) cambia durante il moto

Cioè come cambia sotto l'effetto dei simboli–operatori P, d, s

3.2 Gli L–sistemi

Definiamo quindi tre funzioni P[stato], d[stato], s[stato] che muovono la tartaruga

La funzione P fa avanzare la tartaruga nella direzione della sua orientazione.

{x, v}->{x + v, v}

Definiamola e proviamola

P[{x_,v_}]:={x+v,v}
P[{{0,0},{1,0}}]

Conviene che la funzione sia a valori reali, non interi od in ℚ+(Sqrt[2]) ℚ o così via. In questo modo le operazioni di somma e prodotto sono più veloci!!! Il risultato lo si otterrà dando dati iniziali reali ({0.,0.} piuttosto che {0,0})

3.2 Gli L–sistemi

Per le funzioni d ed s ci servirà la matrice di rotazione di angolo θ, che ormai conosciamo bene

R[theta_]:={{Cos[theta],-Sin[theta]},{Sin[theta],Cos[theta]}}

R[θ]//MatrixForm

NB : Per semplicità, omettiamo di indicare la dipendenza delle funzioni da θ.

Lo passiamo come parametro e ne cambieremo il valore quando servirà.  Fissiamo innanzittutto l'angolo θ di cui d e s fanno ruotare la tartaruga, per esempio π/2.

theta=N[(π/2)];

Anche in questo caso, osservate la N

3.2 Gli L–sistemi

la funzione d è la rotazione oraria di angolo θ della tartaruga

{x,v}->{x,R v}

Definiamola e proviamola

d[{x_,v_}]:={x,R[-theta].v}
d[{{0,0},{1,0}}]

3.2 Gli L–sistemi

Infine, la funzione s è la rotazione antioraria di angolo θ della tartaruga

{x, v}->{x, (R^(-1)) v}

Definiamola e testiamola

s[{x_,v_}]:={x,R[theta].v}
s[{{0,0},{1,0}}]

3.2 Gli L–sistemi

I numeri molto prossimi a zero che compaiono sono in realtà zero

Diciamo che sono zero a meno della precisione della macchina

È il prezzo da pagare quando si vogliono fare conti veloci con numeri reali.

Per ovviare al problema, si può usare il comando Chop (che riconosce se qualcosa di quasi zero è zero), oppure potremmo usare Round, che arrotonda

3.2 Gli L–sistemi

La tartaruga parte da uno stato ((Subscript[x, 0]),(Subscript[v, 0])), che sarà ovviamente {{0,0},{1,0}}.

Seguendo le istruzioni codificate in una stringa "(Subscript[C, 1]),(Subscript[C, 2]),...", la  tartaruga si metterà in modo e si genererà una successione di punti  ((Subscript[x, 0]),(Subscript[v, 0])), ((Subscript[x, 1]),(Subscript[v, 1]))  ...

Come si fa? La stringa "(Subscript[C, 1]),(Subscript[C, 2]),..." è stata trasformata in una lista di funzioni {(Subscript[F, 1]),(Subscript[F, 2]),...}.

3.2 Gli L–sistemi

C'è un comando che lo fa:  ComposeList

La funzione ComposeList ha bisogno di:

■ una lista di operatori {(Subscript[F, 1]),(Subscript[F, 2]),...}

■ un dato iniziale z.

Una volta applicata, produce la lista {z,(Subscript[F, 1])[z],(Subscript[F, 2])[(Subscript[F, 1])[z]],...}

ComposeList[{f,g,h},z]

3.2 Gli L–sistemi

Scriviamo ora una funzione path[stringa, stato] che crea il cammino (ovvero la successione di stati)

path[stringa_,stato_]:=ComposeList[symb[stringa],stato]

Testiamo il funzionamento

path["P",{{0,0},{1,0}}]

path["d",{{0,0},{1,0}}]

path["s",{{0,0},{1,0}}]

3.2 Gli L–sistemi

Se adesso voglio vedere la lista delle posizioni della tartaruga associati al primo evoluto del mio L–sistema a partire dallo stato P, devo scrivere

path["P"//rr,{{0,0},{1,0}}]

path["dP"//rr,{{0,0},{1,0}}]

3.2 Gli L–sistemi

Finora abbiamo costruito un cammino, cioè una lista {{(Subscript[x, 0]), (Subscript[v, 0])}, {(Subscript[x, 1]), (Subscript[v, 1])}, {(Subscript[x, 2]), (Subscript[v, 2])}, ... ....}

Per disegnarlo nello spazio delle posizioni  x∈(ℝ^2) bisogna

■ eliminare le seconde componenti (Subscript[v, 0]), (Subscript[v, 1]), (Subscript[v, 2]), ....
■ appiattire la lista in modo da restare con una lista di punti {(Subscript[x, 0]),,(Subscript[x, 1]),(Subscript[x, 2]),...}
■ trasformare questa lista di punti in una poligonale usando la primitiva grafica Line.
■ trasformare in oggetto grafico con Graphics

3.2 Gli L–sistemi

Eliminare la seconda componente di una lista di due componenti: si mappa un  Drop con i parametri opportuni, oppure si mappa la funzione #[[1]] &

path1[stringa_,stato_]:=Map[#[[1]]&,path[stringa,stato]]
path2[stringa_,stato_]:=Flatten[Drop[path[stringa,stato],0,-1],1]

path["PsP",{{0,0},{1,0}}]

path1["PsP",{{0,0},{1,0}}]

3.2 Gli L–sistemi

Manca solo fare il disegno

drawpath[stringa_,stato_]:=Graphics[Line [path1[stringa,stato]]]

Per evitare di cambiare ogni volta l'AspectRatio ed altre caratteristiche grafiche, possiamo settare i parametri per default:

SetOptions[Graphics,AspectRatio->Automatic];

drawpath["P",{{0,0},{1,0}}]

3.2 Gli L–sistemi

Per vedere l' evoluto al "primo anno"

drawpath["dP"//rr,{{0,0},{1,0}}]

3.2 Gli L–sistemi

Per gli anni sucessivi

drawpath["dP"//rr//rr,{{0,0},{1,0}}]

drawpath[rr["dP",2],{{0,0},{1,0}}]

3.2 Gli L–sistemi

Esercizio 3.2.0: scrivere una funzione turtle[regola,n][stringa] che, data una regola di sostituzione del tipo "P"->"PdPsP", un naturale n ed una stringa iniziale costituita dalle lettere P,d,s, accresce la stringa in accordo con la regola e la disegna in accordo con la tecnica della turtle–walk. 

In molti casi, la stringa iniziale è un segmento, associato alla lettera P. Ci sono casi anche molto complicati

Esercizio 3.2.1: determinare la regola di riscrittura che genera la curva di Peano e quella di Koch

3.2 Gli L–sistemi

Una volta scritta la funzione turtle, provate con le seguenti scelte di stringa iniziale e regola di sostituzione

turtle["P"->"PdPsPsPdP",5]["PsPsPsP"]

turtle["P"->"PPdPsPdPdPP",5]["PdPdPdPd"]

turtle["P"->"PdPsPsPPdPdPsP",5]["PsPsPsP"]

turtle["P"->"PdPsPsPdP",5]["Pd"]

turtle["P"->"PPdPdPdPdPP",5]["PdPdPdP"]

3.2 Gli L–sistemi

E con questa, che richiede l'introduzione di un altro simbolo che, sulla tartaruga, ha lo stesso effetto di P, ma viene riscritto in modo diverso

R[{x,v}]:={x+v,v}; theta=-Pi/3.;
turtle[{ "P"->"RsPsR","R"->"PdRdP"},8]["P"]

3.3 Il gioco del Chaos

Trattiamo ora il più semplice esempio di sistema dinamico stocastico

Fissiamo tre punti nel piano P[1],P[2] ,P[3] (per esempio, il triangolo isoscele di vertici 
{0, 0}, {2, 0}, {1, 1})

P[1]={0,0};P[2]={2,0};P[3]={1,1};

Scegliamo un punto Q[0] all'interno del triangolo di vertici P[1],P[2],P[3]

Gettiamo un dado con tre facce, numerate 1, 2 o 3.  Se il risultato è k disegnamo il punto Q[1] che è il punto di mezzo nel segmento di estremi Q[0] e P[k]

3.3 Il gioco del Chaos

Iteriamo il gioco infinite volte: se alla n-esima prova il risultato è (Subscript[k, n]) allora (Subscript[Q, n]) sarà il punto di mezzo del segmento di estremi Q[n-1] e P[(Subscript[k, n])] ((Subscript[k, n]) è sempre 1, 2 o 3)

Domanda 1: come si distribuiscono i punti nel triangolo? La distribuzione limite può avere proprietà di regolarita?

Domanda 2: cosa succede se si prende il dato iniziale esterno al triangolo?

3.3 Il gioco del Chaos

Ricordiamo che i numeri (pseudo) casuali si generano con Random"Tipo"[range].

RandomReal[{-1,1}]
RandomComplex[{-1+I, 1+I}]
RandomInteger[{1,3}]

Quindi, i primi tre lanci di dadi porgono

l1=RandomInteger[{1,3}]
l2=RandomInteger[{1,3}]
l3=RandomInteger[{1,3}]

3.3 Il gioco del Chaos

Se partiamo con un punto iniziale Q[0]={1,.5}:

Q[0]={1,0.5}

Il punto Q[1] sarà

Q[1]=((Q[0]+P[l1])/2)

3.3 Il gioco del Chaos

I punti seguenti saranno

Q[2]=((Q[1]+P[l2])/2)

Q[3]=((Q[2]+P[l3])/2)

3.3 Il gioco del Chaos

Disegnamo il triangolo ed i punti Q[i]

Graphics[{Thickness[0.01],Line[{{0,0},{2,0},{1,1},{0,0}}],
PointSize[0.02],Point[Q[0]], Point[Q[1]], Point[Q[2]], Point[Q[3]]}]

3.3 Il gioco del Chaos

La "dinamica" non è deterministica, infatti se rifaccio l'esperimento allora

l1=RandomInteger[{1,3}];Q[1]=((Q[0]+P[l1])/2)

l2=RandomInteger[{1,3}];Q[2]=((Q[1]+P[l2])/2)

l3=RandomInteger[{1,3}]; Q[3]=((Q[2]+P[l3])/2)

Graphics[{Thickness[0.01],Line[{{0,0},{2,0},{1,1},{0,0}}],
PointSize[0.02],Point[Q[0]], Point[Q[1]], Point[Q[2]], Point[Q[3]]}]

3.3 Il gioco del Chaos

Per giocare a questo gioco del chaos si possono

1. definire i tre vertici come componenti di una lista P={P[1],P[2],P[3]}.

E quindi una mano del chaos game manda Q nel punto medio del segmento di  estremi P[[numero casuale estratto]].

3.3 Il gioco del Chaos

2. in alternativa, come fatto prima, si possono definire i tre vertici  come valori di una funzione P[i], dove P[1]=..., P[2]=..., P[3]=...

E quindi, una mano del chaos si fa calcolando Q[i+1]= (( Q[i] + P[RandomInteger[{1,3}]])/2)

3.3 Il gioco del Chaos

Una volta definita una funzione gioca[Q], che preso un punto Q genera il punto ottenuto con le regole sopra

Basta creare una lista di punti con un NestList della funzione che genera il punto Q[i+1],

E visualizzarla con un ListPlot

3.3 Il gioco del Chaos

Esercizio 3.3.1: scrivere una funzione play[n,Q] che, ad un dato iniziale Q ed un numero di "mani" n produce la lista dei punti {Q=Q[0], Q[1],...,Q[n]} e li disegna.

Il risultato di questo gioco è il Sierpinski gasket.

Ovvero, il Sierpinski gasket è un attrattore per la dinamica. Un po' come un punto di equilibrio asintoticamente stabile per un'equazione differenziale.

Tutte le soluzioni vi tendono asintoticamente. Qui, però, l'insieme limite ha una struttura frattale

5.3 Il gioco del Chaos

Esercizio 3.3.2i:  inventare un IFS che disegni l'insieme di Cantor

Esercizio 3.3.2ii:  inventare un IFS che disegni una Sierpinski carpet

Esercizio 3.3.2iii:  inventare un IFS che disegni una spugna di Monge

Una simpatica applet Java si trova alla pagina web http://math.bu.edu/DYSYS/applets/chaos-game.html

Esercizio 3.3.3:  riuscite a capire la strategia per vincere il gioco?

Un'analisi del problema si trova, per esempio, in Chaos and Fractals–New Frontiers of Science Capitolo 6: "The chaos game: how randomness creates deterministic shapes" (È un bel libro - voluminoso ma molto bello. Il livello matematico è elementare, ma completo, ed inoltre è spiegato come "fare")

3.4 La dimensione box counting

Ricordiamo brevemente cosa sia la dimensione box–counting. Dato un frattale ℱ, Sia N[δ,ℱ] la funzione che ad ogni δ>0 associa il numero minimo di aperti di diametro al più δ che servono a ricoprire ℱ

La dimensione frattale è l'unico reale s tale che (lim_(δ->0)) (δ^s)N[δ,ℱ ]=v≠0

3.4 La dimensione box counting

Cosa vuol dire che il limite tende a v≠0?

Assumiamo esista un s tale che  (Subscript[Lim, δ->0])(δ^s)N[δ,ℱ]=v≠0  e prendiamo il logaritmo dell'espressione

Allora w=Log[v]=(Subscript[Lim, δ-> 0])Log[(δ^s)N[δ,ℱ]]=(Subscript[Lim, δ-> 0]) -s(- Log[δ])+ Log[N[δ,ℱ]]

ovvero, per δ ≈0 vale w+s(- Log[δ])≈ Log[N[δ,ℱ]]

3.4 La dimensione box counting

Questo vuol dire che la curva parametrizzata da δ->{-Log[δ],Log[N[δ,ℱ]} è, per δ molto vicino a zero, molto vicina alla retta di equazione y=w+s x

Ovviamente, quando δ tende a zero, allora -Log[δ] tende a +∞, e quindi l'asintotica dice che dobbiamo guardare cosa fa il grafico di quella curva quando le sue ascisse vanno verso +∞

Concludendo: disegnando il grafico della funzione N[δ,ℱ] ed usando, invece che l'usuale convenzione per gli assi, quella che usa -Log[δ] in ascissa e Log[N[δ,ℱ]] in ordinata, si dovrebbe produrre una curva con una asintotica verso una retta obliqua con pendenza s quando ci avviciniamo verso +∞

Questo, a meno del fatto che usiamo -Log[δ] invece che Log[δ], si dice comunemente: "plottare un grafico in scala Log–Log"

3.4 La dimensione box counting

Problema: sarà una definizione ben posta, ma come facciamo a calcolare N[δ,𝔉]? Possiamo contare gli aperti necessari a ricoprire 𝔉 usando alcuni ricoprimenti, ma sicuramente non tutti i ricoprimenti

Risposta: si opera una drastica semplificazione : invece di N[δ, 𝔉] si usa M[δ, 𝔉], dove M[δ, 𝔉] la funzione che a (δ,ℱ) associa il  numero di quadrati della quadrettatura di lato  δ dello spazio che contengono elementi di 𝔉.

3.4 La dimensione box counting

Questo definisce una funzione M[δ, 𝔉] che è certo ≥ della originale N[δ, 𝔉], ma se siamo fortunati ci farà lo stesso servizio.

Ci prefiggiamo ora di trovare quella s tale che (δ^s)M[δ,ℱ]-> v ≠ 0 quando δ->0

Ovvero, ci prefiggiamo di guardare la asintotica nel ritratto (-)Log–Log della funzione M[δ,ℱ]

3.4 La dimensione box counting

In altre parole, scriviamo la tabella {δ,M[δ,ℱ]}, applichiamo (più o meno) il logaritmo ad entrambe le entrate di questa tabella, così da produrre {-Log[δ],Log[M[δ,ℱ]}, lo disegnamo in un piano cartesiano, e controlliamo se, verso la direzione +∞ nelle ascisse riconosciamo il grafico di una retta y=w+s x

Vediamo come adattare questo fatto ad un calcolo numerico fatto al computer. Un modo naturale per discretizzare la famiglia di δ che tende a 0 è quello di porre δ=(1/n).  Così si ha che n->+∞ quando δ->0

Scrivendo M[n, 𝔉] invece che M[(1/n),𝔉], ed osservando il fatto banale che Log[(1/n)]=-Log[n], si ha che la cosa da fare è:

3.4 La dimensione box counting

scriviamo la tabella n->{Log[n],Log[M[n,ℱ]]}, la disegnamo in un piano cartesiano, e controlliamo se, verso la direzione +∞ nelle ascisse riconosciamo il grafico di una retta y=w+s x

Questo vuol dire esattamente disegnare il ritratto Log–Log della funzione n->M[n,ℱ]

3.4 La dimensione box counting

Osservazione: se avete una funzione F[x] e vi aspettate che questa cresca, quando x->+∞ come un polinomio con termine di grado massimo (x^n), disegnate il grafico in scala Log–Log e cercate un comportamento lineare: x->{Log[x],Log[(x^n)]}={Log[x],n Log[x]}={y,n y}

LogLogPlot[{x^2,x^3,x^4},{x,1,2}, PlotStyle->{Red,Green,Blue}]

3.4 La dimensione box counting

Osservazione: se avete invece una funzione F[x] e vi aspettate che questa cresca, quando x->+∞, come un'esponenziale di base a, disegnate il grafico in formato Log e cercate un comportamento lineare: x->{x,Log[(a^x)]}={x,x Log[a]}

LogPlot[{2^x,3^x,4^x},{x,0.1,4}, PlotStyle->{Red,Green,Blue}]

3.4 La dimensione box counting

Definizione:  la dimensione box—counting di 𝔉 è il numero s ottenuto calcolando la pendenza al limite per n->∞ della funzione M[n, 𝔉] definita sopra in un diagramma Log–Log

Parafrasando questa definizione, ci si ritrova quindi a disegnare il grafico della curva nel piano parametrizzata da n->{Log[n], Log[M[n, 𝔉]]}  ed a calcolare la pendenza asintotica del grafico così ottenuto

3.4 La dimensione box counting

C'è un ultimo problema, che viene dal fatto che i frattali che tratteremo sono oggetti  numerici e non frattali matematici astratti, ovvero sono sottoinsiemi di una regione limitata di ℝ (od (ℝ^2) od (ℝ^3)) dati come liste finite di punti

Ciò che prima chiamavamo pendenza asintotica dovrà essere rimpiazzato da pendenza media della curva in una regione in cui questa appare rettilinea

3.4 La dimensione box counting

I grafici associati alla curva n->{Log[n],Log[M[n, 𝔉]]} che otterremo, tenderanno ad essere

■ erratici per n molto piccolo,

■ a diventare orizzontali per n molto grande,

3.4 La dimensione box counting

Tratteremo frattali in ℝ ed in (ℝ^2). Quindi i frattali che consideriamo sono oggetti del tipo 
■ {{(Subscript[a, 1])},{(Subscript[a, 2])},...}, oppure 
■ {{(Subscript[a, 1]), (Subscript[b, 1])}, {(Subscript[a, 2]), (Subscript[b, 2])}, ...}
■ {{(Subscript[a, 1]), (Subscript[b, 1]),(Subscript[c, 1])}, {(Subscript[a, 2]), (Subscript[b, 2]),(Subscript[c, 2])}, ...}

Per usare quelli assegnati, depositati nella pagina web del corso, dobbiamo prima importarli come liste, il comando giusto è Import["frattale.dat"] (il nome del file va virgolettato). Fate attenzione ad assegnare il frattale ad una variabile, ed a mettere un ; (punto e virgola) dopo il comando per evitare che il notebook cerchi di visualizzare lunghe liste (potrebbe non farcela).  I frattali sono oggetti che non vanno visualizzati come liste di punti, servono troppe schermate e possono bloccare un computer con poca RAM.

Una volta ottenuta la lista di punti bisogna definire la funzione M[n,𝔉]

3.4 La dimensione box counting

Il modo più semplice per definire M[n,ℱ] è usare la seguente, banale osservazione: se il frattale 𝔉 è contenuto nel cubo di lato 1, allora usando l'omotetia di ragione n (ovvero calcolando n 𝔉) si ottiene un insieme contenuto nel cubo di lato n

Floor[{1.1,2.1}]

Mappando la funzione Floor agli elementi di n 𝔉, ogni elemento n {x, y, z} con {x, y, z} ∈ 𝔉 finisce nel vicino punto di coordinate intere. (Floor è listable, non occorre usare Map)

Questa operazione ha l' effetto di collassare l'insieme n 𝔉 sui vertici di una suddivisione del cubo di lato n in (n^dimensione) cubi di lato 1, che è ovviamente equivalente alla suddivisione del cubo di lato 1 in (n^dimensione) cubi di lato (1/n)

3.4 La dimensione box counting

A questo punto basta usare il comando Union per accertarsi che le ripetizioni vengano cancellate

Il modo migliore per visualizzare il plot della tabella {Log[n], Log[M[n, 𝔉]]} è quello di usare il comando ListLogLogPlot applicato alla lista {n, M[n, 𝔉]}.

Una volta visualizzato il plot diventa possibile selezionare l'intervallo [(Subscript[n, min]), (Subscript[n, max])] dei valori di n nei quali il grafico log–log assomiglia ad una retta. Fatto questo rimane solo da calcolare la pendenza di tale retta

3.4 La dimensione box counting

Ci sono modi poco sofisticati di farlo (ma comunque efficaci), ad esempio calcolare il rapporto

((Log[M[nmax, 𝔉]] - Log[M[nmax, 𝔉]])/(Log[nmax]-Log[nmin]))

Un modo più sofisticato usa il best Fit: algoritmi per interpolare una lista di punti usando funzioni date in modo da minimizzare le distanze tra la curva ed i punti dati. Il comando che determina le interpolazioni si chiama Fit. Il comando Fit[{coppie_di _punti}, {1, x}, x] porge un polinomio di grado 1, del tipo a + b x che interpola la lista di coppie di punti

Dovremo quindi applicare questo comando alla lista di coppie di numeri {Log[n], Log[M[n, 𝔉]}

3.4 La dimensione box counting

Esercizio 3.4.1:  Scrivere la funzione M[n,insieme] che prende un naturale n ed un insieme frattale insieme e che restituisce il numero di quadratini di lato (1/n) occupati da punti del frattale

Esercizio 3.4.2:  Usando il comando ListLogLogPlot, disegnare il log—log plot della lista {n,M[n,𝔉]}. Plottare il grafico per ciascuno dei frattali assegnati determinando la regione in cui il regime del grafico è lineare, calcolare poi la pendenza della parte lineare (e quindi la dimensione frattale) usando il comando Fit applicato alla lista {Log[n],Log[M[n,𝔉]}.