Algoritmica Ricreativa

Nella vita di tutti i giorni ognuno di noi applica algoritmi in modo consapevole o inconsapevole:

• come fare meglio un'attività, 
• come organizzare, in sequenza e/o in parallelo, delle attività (pianificazioni), 
• come massimizzare ottimizzare delle risorse (tempo, memoria, spiccioli, probabilità, ricchezza, etc),
• come individuare gruppi di informazioni nascoste rispetto a determinate dimensioni (clustering), 
• come individuare relazioni e reti di comportamento (organizzazioni, mercati, etc)
• come individuare gerarchi ad albero (es: parentele etc)
• etc.

I nostri algoritmi vengono "implementati" meccanicamente, intuitivamente.

Possono essere algoritmi deterministici o non deterministici. Quelli deterministici si sviluppano facilmente basandosi su delle regole esprimibili matematicamente, quelli non deterministici spesso si devono basare su probabilità e/o su euristica.

Molti sono i problemi matematici-informatici non ancora soddisfacentemente risolti. Molti di essi fanno parte del problema del millennio "P=NP?". I problemi P sono problemi che si risolvono in un tempo polinomiale, ovvero in un tempo al più potenza dell'input. I problemi NP sono, invece, quelli "non polinomiali", molto spesso NP-completi (vedi Wikipedia).

Fanno parte della famiglia NP la fattorizzazione di un numero con molte cifre (su cui si basa l'inviolabilità del RSA), il problema del logaritmo discreto, il problema del commesso viaggiatore, il problema dell'ottimizzazione  del sacco, delle pesate etc.

Non crediate che solo i problemi famosi sono di questo tipo. Pensate al fastidio degli innumerevoli spiccioli che dobbiamo portarci dietro, questa estate, nel piccolo taschino dei pantaloni.

E' ovvio che chiunque che debba pagare un caffè, cercherà di levarsi quanti più spiccioli è possibile.

Ecco un problema ricreativo: "Come lavora un algoritmo per massimizzare il numero di monete in centesimi ed euro con cui pagare il bar?"

Supponiamo di avere:

S  la somma da pagare
Q1 monete da taglio T1 (1 cent)
Q2 monete da taglio T2 (5 cent)
Q3 monete da taglio T3 (10 cent)
Q4 monete da taglio T4 (20 cent)
Q5 monete da taglio T5 (50 cent)
Q6 monete da taglio T6 (1 euro)
     
Dopo vari tentativi è sufficiente in ciclo individuare il valore dell'indice i tale che Sum(Qi*Ti) > S e in tal modo individuiamo la prima moneta di taglio Ti da usare.

A questo punto si ripete come se la somma da pagare nuova è Sn= S - Ti. Se Sn= S- Ti è positivo si ripete il ciclo per individuare un'altro taglio di moneta Ti e così via; se invece S - Ti < 0 significa che occorre ricevere resto e l'algoritmo si arresta.

In tal caso col resto ricevuto si cercherà di farsi cambiare dalla cassa le ulteriori monetine rimaste con poche altre monete di taglio maggiore.

Supponiamo S=85 centesimi, Q1=9, Q2=3, Q3=6, Q4=3, Q5=2, Q6=1. Allora se provate ad applicare più volte l'algoritmo, otterrete che ci possiamo liberare in prima battuta di 13 monetine su 28: una da 20 c, cinque da 10 c, due da 5 c, cinque da 1c.

Stesso problema, altra prospettiva: "Dobbiamo pagare una lavatrice, non abbiamo assegni ma contante e spiccioli".

Se dobbiamo pagare 400 euro con l'algoritmo di sopra ci linciano! L'algoritmo in questo caso è simile a quello di sopra ma tenta di prendere prima le monete di taglio maggiore (es: 500 euro, 100 euro, 50 euro, 10 euro) in assoluto.

I due problemi di sopra sono semplici e usano una tecnica lineare per trovare la soluzione. Se pensiamo, invece, allo stesso problema da un punto di vista ulteriore le cose si possono complicare un poco soprattutto per l'efficienza perchè si passa ad un problema esponenziale.

Problemi inutili? Pensate all'algoritmo "intelligente" che deve avere un distributore bancomat. Sa  che dispone di una somma totale iniziale che varia ad ogni cliente, sa che in generale ha tagli da 10 euro, 20 e 50 con una certa quantità iniziale (anche nulla per certi tagli nel tempo), deve cercare di dare la somma richiesta dal cliente rispetto al massimo consentitogli (esempio 250 euro) cercando di dare diversi  tagli  e di proporre le somme che si avvicinano alla somma in denaro richiesta.

Corrispondenza esatta
Analizzate il problema: "Trovare le monete che paghino esattamente 85 centesimi". L'algoritmo in tal caso deve fare tutte le somme possibili tra 1 o più combinazioni di monete disponibili e vedere quali somme danno 85 come risultato; certamente è un algoritmo esponenziale.

Spesso il trucco, se non ci sono vincoli al problema, è di massimizzare o minimizzare una risorsa per portarsi in un problema lineare, ma in alcuni casi non è nemmeno semplice, come nel caso del problema del commesso viaggiatore: in tale problema il commesso viaggiatore deve fare in modo di fare il minimo percorso tale che si passi per una stessa strada una sola volta, partendo da casa e passando per ogni strada dove deve fare la commissione, e poi ritornare alla fine del percorso di nuovo a casa.

Purtroppo in questo caso occorre verificare tutti i percorsi, marcarli con un peso e alla fine trovare decidere il percorso migliore; esistono anche dei trucchi per ridurre tale ricerca, ma in ogni caso un algoritmo efficiente non di natura esponenziale finora non è stato individuato.


Alla prox

Numeri Creazionali, la metafora dell'aquilone e la sequenza di Collatz, gli automi cellulari

Introduzione
In questo blog introduciamo prima una problematica ancora vicina alla Teoria dei Numeri, poi successivamente problemi di settori apparentemente diversi ma dove la struttura sottostante è sempre guidata da modelli matematici.


Numeri creazionali

Il numero creazionale di un numero n, che indichiamo col simbolo C(n), è il minor numero di cifre che occorre usare per costruire n.

Facciamo delle "ipotesi creazionali di base":
1) è possibile usare le operazioni +,*,-,/,^
2) è possibile usare i digit D=1,2 ma non necessariamente da usare insieme

Se n=80, D=1 allora C(80) <= 13

Difatti:

80=5*4*4=(1+1+1+1+1)*(1+1+1+1)*(1+1+1+1)

Abbiamo usato solo il digit 1, ma se usassimo anche il 2?
Esempio:
n=81, D=1,2 allora C(81)<=5
81=(2^(2+1)+1)^2

n = 20 D=1,2 C(20) <= 5
20 = 2^(2+2)+2+2

n=120 D=1,2 C(120)<=6
120 = ((2+1)^2+2)^2-1

n=567 D=1,2 C(567)<=8
567 = (2^(2+2+2)-1)*(2+1)^2

Una strategia algoritmica semplice è:
a) ritenere il massimo valore pari al numero n stesso (come somma di 1);
b) individuare il minimo valore possiamo con la potenza k di 2 più grande ma tale che il tutto sia minore o uguale a n stesso (2^k <= n), con k trasformato come somma di 2 e/o 1 o anche prodotti o potenze di 2, sommando, infine, se necessario 1 o altre potenze di 2.

Ad esempio:
C(21)<=6
21 = 2^(2^2) + 2^2 + 1

C(27)<=8
27 = 2^(2^2) + 2^(2+1) + 2 + 1

E' possibile per un fissato n, D=1,2 e le 5 operazioni considerate poter calcolare direttamente, senza algoritmo ma con una formula, il numero minimo di cifre necessarie a creare n?

Sequenza di Collatz
Un problema di interesse in ambito studio del chaos è quello suggerito dalla metafora dell'aquilone o dei chicchi di grandine.

Immaginiamo che ci siano folate di vento che portano verso l'alto oggetti leggeri come i chicchi di grandine o aeroplanini di carta, meglio ancora degli aquiloni.

Immaginiamo che l'aquilone parta da una altezza h (un numero), scende in basso in picchiata e poi una folata di vento lo riporta in alto, poi di nuovo scende in basso e così via fino ad atterrare al suolo (suolo = 1).

Ebbene il problema di Collatz o la sequenza di Collatz si genera a partire da un numero n, se n è pari lo si divide per 2, se n è dispari lo si moltiplica per 3 e si somma 1. Il procedimento si itera sul risultato.

La sequenza termina sempre a 1? E' ciclica, aciclica o convergente a 1?

Un lavoro su questo argomento è al link http://www.rudimathematici.com/Bookshelf/notes/RTC03.pdf
Il software è disponibile su www.gruppoeratostene.com

Solo oggi si sta iniziando ad usare la "computer graphic" per comprendere la struttura esistente dietro la matematica.Perchè ci sono schemi nascosti?

I numeri che si ottengono come output sono le traettorie seguite dall'aquilone prima di giungere al suolo (=1); ma alcuni numeri si presentano più frequentemente e il valore massimo raggiungibile nella traettoria o glide è un numero abbastanza interessante (gli autori presentano una Congettura sul Massimo nella glide); ad esempio 9232 è un massimo che si presenta in più di 350 numeri tra i gli iniziali 1000 interi.

Ma perchè nell'ambito della glide alcuni numeri sono più frequenti e ci sono determinati raggruppamenti?

Il problema di Collatz è scollegato dalla Teoria dei numeri? Gli autori mostrano anche un possibile legame con i numeri di Mersenne ed indagano su diversi teoremi.

Il problema di Collatz rientra in settori tipici molto importanti: Automi Cellulari (AC), Social Network Analisys, Chaos, Frattali, Robotica, batrachioni, Sistemi complessi  etc. settori oggi molto studiati.

In ambito AC la sequenza di Collatz è in effetti  un AC monodimensionale (d=1) lineare  con raggio r=2/3 (infatti in ambito computer graphic il grafico è indicativo di chaos o di frattale) e secondo la classificazione dello studioso Stephen Wolfram è un AC di Classe 1, cioè partendo da n la sua evoluzione porta ad uno stato omeogeneo (sempre lo stesso, l'1) indipendentemente dall'input n.

Batrachioni e chaos
In una rete (Social Network o una rete di automi cellulari) l'evoluzione tiene almeno conto di quello che è accaduto nelle vicinanze, o anche NON immediatamente vicino (dipende dal problema). Il chaos, i batrachioni, i frattali, le trasformazioni lineari, le funzioni biettive e i mapping sono argomenti di notevole interesse per diverse discipline, tra cui anche la Social Network Analisys.

Una cosa che potrebbe sembrare inaspettata è la complessità che può emergere da semplici formule iterative, dando luogo a rappresentazioni di chaos, di frattali etc.

Un pò come le formule iterative di Fibonacci ne esistono altre altrettanto interessanti, come quelle delle curve dei "batrachioni". Il termine deriva dal greco batracen ovvero rana (in letteratura anche "small frog"), proprio perchè le curve che si ottengono sembrano dei saltelli all'infinito di rane che diminuiscono di altezza (ma non di ampiezza). Le curve sono tipicamente frattali perchè sul bordo presentano oscillazioni auto-somiglianti.

Una formula dovuta a Hofstadter-Conway è del tipo:

a[i]=a[a[i-1]]+a[i-a[i-1]]
con a[1]=1 e a[2]=1

Di interesse è il valore a[i]/i. Conway dimostrò che per lim n->inf a[n]=1/2.

Una sequenza caotica altrettanto interessante è:
a[i]=a[a[i-1]]+a[i-a[i-2]-1]
con a[1]=1 e a[2]=1

altre ancora che sono possibili sono:
       a[i]=a[a[i-1]]+a[i-a[i-2]-1];

L'ultima che fa riferimento ad elementi non adiacenti è:
   a[i]=a[a[i-2]]+a[i-a[i-3]-v];   con v=1,2

Vedi http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html

Interessanti sono anche le BlancMange Function Vedi http://mathworld.wolfram.com/BlancmangeFunction.html


Automi cellulari
Gli automi cellulari sono "sistemi complessi" usati per modellare gli dinamica dei flussi dei liquidi, le reazioni chimiche, incendi boschivi, la propagazione e nascita delle piante, di animali, e virus, percolazione del caffè, colata lavica, morfologia urbana e territoriale, inondazioni, diffusione degli inquinanti, etc

Sono spesso dette "strutture omogenee", "strutture cellulari" e "tabelle iterative".
 
Alcuni di questi automi cellulari si comportano in maniera strana e casuale, altri in modo ordinato, alla "frattale".

Si può avere anche una rete di automi cellulari, ognuno dei quali con regole simili ad altri (omogeneità). Di solito valgono le proprietà di Parallelismo (al tempo t parallelamente avvengono azioni su ogni cella o individuo), Omogeneità (stesse regole al tempo t per tutti i nodi della rete o individui, Località (lo stato di un individuo al tempo discreto t+1 dipende dal proprio stato e quello dei vicini). 

Il concetto di automa cellulare è nato negli anni '50 con von Neumann e Stanlislaw Ulam. Conway ideò l'automa cellulare Life (Vita). Martin Gardner pubblicizzò la cosa come un gioco su Scientific American nell'ottobre del '70.


Ogni equazione differenziale si può tradurre in un automa cellulare (equazioni a differenze finite ad esempio). Da qui ad esempio si può usare l'equazione del calore per studiare una rete (anche una Social Network), ipotizzando che per il problema in questione la diffusione del calore sia un modello matematico adatto alla rete.


Life è il punto di partenza per chi vuole apprendere gli automi cellulari.  Vedi gioco http://www.bitstorm.org/gameoflife/

Gli automi monodimensionali studiati da Wolfram sono l'altro punto di partenza.
Vedi http://alpha01.dm.unito.it/personalpages/cerruti/Az1/wolfram.html

Per Collatz come AC vedi http://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/
e l'articolo http://arxiv.org/PS_cache/nlin/pdf/0502/0502061v1.pdf   Tra l'altro si tratta di un AC "non invertibile"; difatti se per ogni n si giunge sempre a 1 è difficile risalire al valore n di partenza nella sequenza di Collatz.

Per una introduzione al Social Network Analysis Vedi http://www.slideshare.net/marcomuzza/social-network-analysis-presentation-919991

Gli AC hanno una notevole importanza anche per lo studio di difficili equazioni come le equazioni di Navier-Stokes (altro problema del millennio).


Alla prox