Lego: un gioco di costruzioni I processi iterativi per la...

Lego: un gioco di costruzioniI processi iterativi per la modellizzazione

del quotidiano

Primo Brandi

Dipartimento di Matematica ed Informatica

Università degli Studi di Perugia

http://www.matematicaerealta.it

mateas@unipg.itSan Pellegrino Terme, 6 settembre 2006

Summer School - Incontriamo la Matematica

P.Brandi (Univ. Perugia) - Lego: un gioco di costruzioni, San Pellegrino 6 settembre 2006

Lego: un gioco di costruzioni - I processi iterativi per la modellizzazione del quotidiano

Cosa è un processo iterativo

Processi iterativi nella simulazione della realtà

La dinamica della geometria frattale

Il progetto MATEMATICAC&REALTA’

Mondo reale & mondo matematico

“azione ripetuta più volte”

processo iterativo

Zoom di una fotocopiatrice

Processo iterativoun secondo esempio

diffusore-microfono-amplificatore-diffusore

segnale

rumore bianco

10 cicli 50 cicli

1250 cicli 6250 cicli

Schema di processo iterativo

Approccio numerico Formalizzazione analitica

0,1, 2,...

( )n n

x start

x T x+

(xn)n è detta successione delle iterate

Perchè gli algoritmi iterativi?… per almeno 6 buone ragioni:

sono uno strumento elementare

utilizzati sin dagli albori della modellizzazione

di costante attualita’

di crescente interesse (computers)

offrono una vasta gamma di applicazioni

propongono spunti di riflessione ed approfondimento multidisciplinare

Alcuni problemi della vita reale

Depurazione di carburante

Le leggi federali USA prescrivono di depurare il kerosene utilizzato come carburante dei jet.

L’operazione avviene mediante filtraggio attraverso un’apposita condotta contenente argilla.

Se 1 foot di filtro elimina il 20% di impurità, quanto deve essere lunga la condotta per abbattere gli inquinanti del 75%?

Problemi di vita reale

Caratteristiche conformi

Detersivo residuo

ogni risciacquo finale

25/109

in economynormaleLavaggio

13 l0 g21 l0 grisciacquo13 l50 g21 l80 glavaggio

H2OdetersivoH2Odetersivo

Piani di investimento a confronto

12,50% sugli interessi

Ritenute di legge

100€ annuali posticipati

100€ sem. anticipati

Spese fisse

4% annuale2% sem.Tasso di interesse

Piano BPiano A

L’agente finanziario afferma che il Piano A è più conveniente per investimenti superiori a 10.000 €. VERO O FALSO?

Prescrizione medica

Iodio131 è somministratoa pazienti ipertiroidei

Non è prudente prendere in braccio i bambini fin

quando l’attività radioattiva non si è ridotta del 70%

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Tempo di emi-vita 8 giorni

Quale sarà il consiglio del medico?

Datazione di sostanze organiche

Castello di Winchester

E’ la leggendaria tavola rotonda di re Artù ?

datazione con C14 : alberi tagliati nel secolo XIII

Diametro 5.5 m 25 settori

I problemi presentati sono suscettibili di una medesima

formulazione matematica

attraverso la struttura di

processo iterativo

Depurazione di carburante

Le leggi federali USA prescrivono di depurare il kerosene utilizzato come carburante dei jet.

L’operazione avviene mediante filtraggio attraverso un’apposita condotta contenente argilla.

Se 1 foot di filtro elimina il 20% di impurità, quanto deve essere lunga la condotta per abbattere gli inquinanti del 75%?

Depurazione di carburante –Costruzione del modello

Start: quantità iniziale di inquinanti

1 foot di filtro elimina il 20% di impurità, quanto deve essere lunga la condotta per abbattere gli inquinanti del 75%?

( )2 10.8P P=

( ) 10.8n nP P −=

Stadio 1: ( )1 00.8P P=

Stadio 2:

Stadio 3: ( )3 20.8P P=

Stadio n:

Start: quantità iniziale di inquinanti

( ) ( ) ( ) ( )2

2 1 0 00.8 0.8 0.8 0.8P P P P= = =

( ) ( )1 00.8 0.8n

n nP P P−= =

Stadio 1: ( )1 00.8P P=

Stadio 2:

Stadio 3: ( ) ( )( ) ( )2 3

3 2 0 00.8 0.8 0.8 0.8P P P P= = =

Stadio n:

( ) 0 1 2

00 8 n , , , ...n

P start

P . P =

Sequenza delle iterate

( ) 0 1 2

1 00 8 n , , , ...n

P start

P . P =+

Sequenza delle iterate

Depurazione di carburante –Risposta ai quesito

( ) 0 1 2

1 00 8 n , , , ...n

P start

P . P =+

( ) ( )0

0.8 0.8 0.25n

n nPP P <= ⇔ <

Risposta al quesito:

Il primo intero che soddisfa la disuguaglianza è 7n =La condotta deve essere lunga almeno 7 feet

Decadimento radiattivo

Gli isotopi radiattivi decadono: % ad ogni stadio λ

Start step 1 step 2 step 3 …

Successione decrescente

1 1,2,(1 )

= − = − K

Classi di Processi iterativi elementari

( )T x x q= + una traslazione genera un processo lineare

Progressione aritmetica, capitalizzazione semplice…

diagramma di Web

( )T x m x=Progressione geometrica, capitalizzazione composta, lavatrice, decadimento radioattivo, …

una omotetia genera un processo exp

diagramma di Web

( )T x m x q= +una trasformazione lineare genera un processo exp

( )T x m x=

( )T x x q= + una traslazione genera un processo lineare

Progressione aritmetica, capitalizzazione semplice…

Progressione geometrica, capitalizzazione composta, lavatrice, decadimento radioattivo, …

( )T x m x q= +

una omotetia genera un processo exp

una trasformazione lineare genera un processo exp

Processi iterativi associati a trasformazioni punto-punto

1 1| ( ) ( ) | | |n n n nT x T x x x+ +− = −

1 1| ( ) ( ) | | |n n n nT x T x x x+ +− > −

1 ( )n nx T x+ =

1 1| ( ) ( ) | | |

0 1n n n nT x T x K x x

K+ +− ≤ −

P. isometrico

P. di espansione

P. di contrazione

Teorema di Renato Caccioppoli per le contrazioni

Ogni contrazione ammette un unico punto fisso

Fissato comunque un punto start, il processo

ammette come attrattore . L’approssimazione dell’attrattore migliora ad ogni pass o

( )x T x=

1 0 1 2n n n , , ,

x start

x T x+ =

1 0 1 2n n n , , ,...| x x | | x x |+ =− ≤ −

Il caffè versato in una tazzina si raffredda secondo la legge di Newton: la diminuzione della temperatura è proporzionale all a differenza di temperatura tra il caffè e l’ambiente

Raffreddamento di una tazzina di caffè

Processo iterativo del raffreddamento

Ta la temperatura ambiente

T0 la temperatura del caffè appena versato

Tn la temperatura del caffè dopo n stadi

Ta la temperatura ambiente

T0 la temperatura del caffè appena versato

Tn la temperatura del caffè dopo n stadi

0,1, ...

( ) 0 1a

n n n a

T T start

T T k T T k+

− > − = − − < <

Una opportuna semplificazione

Introduciamo una nuova variabile

la differenza termica tra caffè e ambiente

Sn=Tn-Ta

( ) ( )1 1 ( )

1 ( ) 1n n a n n a a

S T T T k T T T

k T T k S+ += − = − − −

− − = −

0,1, ...0 1

(1 )n n

S start

S k S+

> = −

Il processo è generato dalla trasformazione

T(x) = (1-k) x

si tratta di un processo di contrazione

0,1, ...0

(1 ) 0 1nn

nS start

S k S k+=

> = − < <

Formula chiusa

0 .0,1,..(1 )nn nS k S == −

01 (1 )S k S= −2 1 0 0

2(1 ) (1 ) (1 ) (1 )S k S k k S k S= − = − − = −..................................

0 .0,1,..(1 ) ( )na an nT T k T T =− = − −

Il processo evolve verso l’ attrattore, punto fisso di T T(x) = (1-k) x = x

0nS →

n aT T→

Verifica e messa a punto del modello

Esperimento con sensore di temperatura collegato ad un CBL

0 5 10 15 20 25 30 35 40 45 50

tempo [minuti]

valori osservati

1 368 735 1102 1469 1836 2203 2570 2937 3304 3671 4038 4405 4772

Confronto

1 363 725 1087 1449 1811 2173 2535 2897 3259 3621 3983 4345 4707

valori osservati

valori teorici

Differenza max: 1.5 gradi errore ma x 2,5%�

Prato di erba medica

Famiglia R: seme da incrocio

Famiglia V: seme da auto impollinazione

i Rossi diventano parte Verdi e parte restano Rossi secondo un rapporto fisso

i Verdi diventano Rossi

Evoluzione della popolazione al trascorrere delle generazioniStimare il rapporto fra le due popolazioni in un prato naturale

Prati di erba medicaInterazione tra ROSSI e VERDI: ad ogni stadio

VERDI ROSSI

% ROSSI VERDE

Start step 1 step 2 step 3 …

1 1, 2, 3,

V Rλ+ +

+ = = − = K

Prati di erba medica

Formula chiusa

12 30 1, 2, ...

V Rλ λ λ λ+=

+ = = −

= − + + + − L

• L’evoluzione tende a stabilizzarsi dopo un certo numero di generazioni

• La configurazione asintotica non dipende dalla configurazione iniziale, ma solo dal parametro

λλλλ

Nei nostri prati si è stimato λ = 40%λ = 40%λ = 40%λ = 40% 71%R ≅n

Preda-predatori

Il tasso di accrescimento di due popolazioni isolate è proporzionale al numero di individui di ciascuna

n n n n

x x ax by

y y cx dy+

− = + − = +

Modello lineare

Preda-predatori

Il tasso di accrescimento di due popolazioni isolate è proporzionale al numero di individui di ciascuna

n n nn

x x ax

y kx yd+

− = + − = +

Modello non lineare

Modello preda predatore

lepri e volpi

Le lepri senza le volpi esploderebbero

Le volpi senza le lepri scomparirebbero

invece la loro interazione …

I Premio - Migliore comunicazione

Tommaso Bientinesi

Tutor Prof. Mara Massarucci

Classe V Liceo scientifico Donatelli, Terni

III convegno Esperienze a confronto

Perugia, 10-11 aprile 2001

Processi iterativi

Trasformazionipunto-punto

modelli lineari

eco-sistemi isolatiregimi di coop/comp mod. preda-predatori

modelli non lineari

crescita logisticaeffetto farfalla

Trasformazionifigura-figura

geometria frattale

crescita dentritica in una cellula elettrolitica

fluttuazioni di un titolo azionario

dithering di stampa

percolazione di liquidi

paesaggi virtuali

strutture frattali in anatomia, astronomia, botanica

compressione immagini

Trasformazionifunzionali

Algoritmi di approssimazione

algoritmo babilonese quadratura del cerchio e rettificazione della circonferenza

processo di esaustionesecondo Archimede

metodi di linearizzazioneper il calcolo degli zeri(corde, secanti, regula

falsi, tangenti)

Processi iterativi

automi cellulari

A new kind of science di Wolfram

Life-game

automi a stati finiti

geometria frattale

crescita dentritica in una cellula elettrolitica

fluttuazioni di un titolo azionario

dithering di stampa

percolazione di liquidi

paesaggi virtuali

strutture frattali in anatomia, astronomia, botanica

compressione immagini

falsi, tangenti)

Processi iterativi

tecniche diInterpolazione frattale

per lo studio di seriestoriche

falsi, tangenti)

automi cellulari

Life-game

Processi iterativi

modelli continui in dinamica delle popolazioni

equazioni diff. ordinarie

teorema di punto fisso di Banach

metodo delle approssimaz. successive

automi cellulari

Life-game

tecniche diInterpolazione frattale

per lo studio di seriestoriche

Introduzione alla geometria frattale

•Crescita dentritica in una cellula elettrolitica

•Fluttuazioni di un titolo azionario

•Dithering nel processo di stampa computerizzata

•Percolazione di liquidi

•Paesaggi virtuali

•Strutture frattali in anatomia, astronomia, botanica

•Algoritmi di compressione delle immagini

•Interpolazione frattale

Processi iterativi associati a trasformazioni figura-figura

La geometria frattale introduce una dinamica nella geometria Euclidea.

I frattali sono definiti attraverso algoritmi che, pur agendo sugli usuali elementi della geometria classica, introducono un processo dinamico.

Questa teoria, proprio perché espressione della complessità della natura, si presta a numerose applicazioni.

Processi iterativi su figure

alcuni esempi

F0 startF1

Gerla di Sierpinski

F1F0 start

Tappeto di Sierpinski

Il merletto a trina

Helge von Koch (1904)

CODICE GENETICO di un IFS

Il generatore della curva di Koch è governato dallatrasformazione geometrica T(w 1,w2.w3,w4)

T=(w1,w2,w3,w4)

=′ω

3)4 yy

=′ω

Trasformazioni geometriche

Contrazione

Contrazione+ traslazione

Contrazione + traslazione + rotazione

Curva di Koch

Koch classico

Metodo del codice genetico

L-system

Principali caratteristiche dei frattali

� dimensione frazionaria

curva di Koch D= 1.2619

interpolanti frattali in Idrologia 1.2 < D < 1.4

� invarianza per scala (autosimiglianza)

se si esaminano i frattali su scale diverse, si

osservano sempre gli stessi elementi fondamentali

Frattali con condensing

alberi

Maila Agostini – Valeria Fabbri – Jonathan Monti

Classe IV

Prof. Maria Vittoria Buzzi

Liceo scientifico Galilei, Terni

IV convegno Innovamatica

Esperienze a confronto

Perugia, 10-11 aprile 2002

Il concetto di modello e … il Lego

Mediante strutture semplici combinate possiamo modellare fenomeni complessi

Matematica e mondo reale

Una possibile interazione…

Educazione alla modellizzazione

Sviluppare un’attitudine sperimentale nei confronti della matematica evidenziando il suo ruolo chiave nella modellizzazione della realtà

PROGETTO INNOVAMATICAUniversità di Perugia

MATEMATICA & REALTA’

www.matematicaerealta.itprogettomr@dipmat.unipg.it

CENTRO PRISTEMUniversità Bocconi

Il progetto Matematica & Realtà è nato con l’intento di offrire una gamma di opportunità:

per un insegnamento più tradizionale , mettendo a disposizione numerosi modelli di supporto da svilup pare alla voce “saper fare” come “esercizi”

per un insegnamento più aperto alla innovazione tecnologica , fornendo un ampio ventaglio di modelli (per il cui sviluppo è indispensabile il ricorso alle nuove tecnologie)

per un insegnamento aperto all’innovazione didattica , proponendo un percorso di educazione alla modellizzazione.

Educare alla modellizzazione comporta un modo diverso di proporre lo studio della matematica, riv olto alla descrizione e comprensione del mondo reale.

Punto centrale della proposta è una

interazione dinamica tra mondo reale e mondo matematico

azione principale

LABORATORI DIDATTICIsvolti presso la propria scuola o all’Università

… abbiamo raccolto una sfida …

E’ possibile introdurre ai modelli matematici con strumenti elementari

Riavvicinare alla matematica … chi si sente indifferente al sentore scientifico

… e nutriamo una speranza …

Grazie per l’attenzione

Lego: un gioco di costruzioni I processi iterativi per la...

Documents

Transcript of Lego: un gioco di costruzioni I processi iterativi per la...

Fondamenti di Algoritmi: Esercizimilazzo/teaching/AA1011-ALG/esercizi-algoritmi.pdf · 1 Esercizi sulla complessit a degli algoritmi iterativi 1.1 Preliminari Lo scopo di questi esercizi

Epifania Dio Bambino, finalmente ti incontriamo a conclusione del lungo nostro cammino!

UN’AVVENTURA SENZA FINE: PARADOSSI, VERITA’ E …matnet.unibg.it/fileadmin/user_upload/Summer_school_11/Lab4... · filosofo greco Zenone di Elea nel Vsecolo a. C. Achille insegue

Algoritmi e diagrammi di flusso Classi secondegallinigenova.altervista.org/algoritmi2.pdf · Algoritmi iterativi (loop): ... i passi costituenti sono elementari (non ulteriormente

Il PA negli Orientamenti “Incontriamo Gesù” Diocesi di Lucera-Troia.

“INCONTRIAMO GLI ESPERTI” 2° INCONTRO DI AGGIORNAMENTI IN O.R.L. Le emorragie delle VADS

METODI ITERATIVI PER LA SOLUZIONE DI EQUAZIONI …alvise/CS_2011/2011/METODIITERATIVI_2011_PDF… · METODI ITERATIVI PER LA SOLUZIONE DI EQUAZIONI LINEARI ∗ A. SOMMARIVA† Conoscenze

Algoritmi iterativi per la risoluzione di sistemi lineari

Scripting - Esecuzione condizionale - Costrutti iterativi - Variabili (quoting, espansione)

Metodi iterativi su spazi di Krylov G. Puppo. Riassunto Metodo Ortomin Metodo del gradiente Metodo del gradiente coniugato Metodo GMRES Metodo GMRES con.

Ci incontriamo in un libro?

Dispense di Metodi Numerici per le Equazioni Differenziali ...profs.scienze.univr.it/~caliari/aa1213/equazioni_differenziali/... · I metodi iterativi per la soluzione del sistema

Scenari Digitali ProgrammazioneVisuale - icragazzideuropa.it · secondo tutorial incontriamo i più famosi strumenti online per l'introduzione del ... alla programmazione con le ...

Guardando al futuro… …incontriamo…ci… per scegliere insieme.

Incontriamo il jazz 2016 Il ritmo del Jazz - CDpM ritmo del jazz.pdf · 2016-02-06 · 1 Incontriamo il jazz 2016 Il ritmo del Jazz Il jazz patrimonio UNESCO dell’umanità L’UNESCO,

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Costrutti iterativi Marco D. Santambrogio – marco.santambrogio@polimi.it Ver. aggiornata al 9 Agosto 2013.

Il PA negli Orientamenti “Incontriamo Gesù”

DIPARTIMENTO DI ELETTRONICA E INFORMAZIONE Costrutti iterativi Marco D. Santambrogio – marco.santambrogio@polimi.it Ver. aggiornata al 20 Marzo 2013.

SISTEMI LINEARI QUADRATI: METODI ITERATIVI

Dip. Matematica, U. Milano-Bicocca & Progetto Lagrange ...matnet.unibg.it/fileadmin/user_upload/Summer_school_07/San... · Funzioni del materiale genetico Replicazione: il materiale