Archivio mensile:Gennaio 2016

Algoritmi antichi e curiosi

Alla scoperta di algoritmi antichi e curiosi

Se hai a che fare con la matematica frequentemente, la dimestichezza con gli algoritmi certo non ti manca 😉 Tuttavia, per mettere tutti i lettori di questo articolo su un punto di partenza più o meno equo, ho pensato di iniziare il tutto con una “definizione” di algoritmo.

Un algoritmo è un procedimento che risolve un determinato problema attraverso un numero finito di passi elementari.

Questa non è una vera e propria definizione, in quanto per essere completa dovrebbe fornire anche un bell’elenco di proprietà di cui deve godere un algoritmo. Tuttavia ritengo che, per quello che andrai a leggere nelle prossime righe, questa breve introduzione al concetto di algoritmo sia più che sufficiente.

Di algoritmi noti ve ne sono un’infinità e, ogni giorno, programmatori, matematici, fisici e ingegneri di tutto il mondo ne inventano di nuovi per risolvere i problemi che si trovano ad affrontare quotidianamente al lavoro.

Nonostante molti algoritmi siano noti ai più, ritengo che ve ne siano alcuni davvero curiosi, intriganti e per lo più finiti nel dimenticatoio.

Certamente se alcuni di questi sono stati col tempo tralasciati c’è un motivo, il principale è senz’altro la loro inefficienza (ossia incapacità di arrivare ad un risultato in pochi passi).

Tuttavia li trovo curiosi da un punto di vista teorico e metodologico.

Partiamo quindi con un semplice elenco dei 4 algoritmi antichi e curiosi che ti andrò a presentare, seppur brevemente (non escludo di trattarli in modo approfondito e esteso in articoli dedicati in futuro), nelle seguenti righe.

Lista dei 4 algoritmi antichi e curiosi trattati di seguito:

  • Moltiplicazione egizia
  • Algoritmo di Euclide per il calcolo dell’MCD
  • Algoritmo babilonese calcolo radice quadrata
  • Moltiplicazione alla russa

Andiamo ora a trattarli brevemente uno per uno 🙂

Algoritmo moltiplicazione egizia

Questo algoritmo è molto antico e anche intrigante, infatti permette di fare la moltiplicazione di due numeri naturali in una maniera che apparentemente può sembrare davvero misteriosa.

Prima di spiegare come funziona l’algoritmo, ti faccio vedere un procedimento svolto, vediamo se ti è subito chiaro 😉

Ora ti scrivo l’algoritmo in un linguaggio comprensibile (pseudocodifica):

a,b interi

z = 0

finchè (a>0):

se a dispari -> z=z+b

a=a//z (divisione intera)

b=b*2

risultato z

Se provi a tracciare o comunque ad eseguire manualmente questo algoritmo, probabilmente riesci ad accorgerti che si basa sulla notazione in base 2. Tuttavia preferisco non dimenticare informazioni importati per scrivere poco, quindi a questo, come ai seguenti algoritmi, dedicherò un intero articolo in futuro. Per ora quindi accontentati di queste informazioni, oppure ti basta digitare ‘moltiplicazione egizia’ su Google e troverai le risposte alle tue domande 😉

Algoritmo di Euclide per il calcolo dell’MCD

Questo non è per nulla un algoritmo inefficiente, infatti permette di trovare l’MCD tra due numeri in molti meno passi rispetto al comune procedimento. Infatti invece di trovare prima i divisori di un numero, trovare i divisori del secondo e cercare il più grande divisore in comune, l’algoritmo che ti sto per presentare utilizza solo somme e differenze 🙂

Partiamo, questa volta, con la pseudocodifica:

a,b naturali

finchè a!=b (!= significa diverso):

se a>b allora a=a-b

altrimenti b=b-a

risultato a

Provare per credere 😉 con questi semplici conti arriverai a trovare facilmente l’MCD tra due numeri. E’ certamente meno intuitivo del procedimento che comunemente fai per trovare il massimo comune divisore tra due numeri, tuttavia nella scrittura di codici (programmazione) questo algoritmo risulta spesso molto utile.

Prova a capire come fa a ‘funzionare’ e scrivilo nei commenti! Comunque nelle prossime settimane pubblicherò un articolo dedicato a questo specifico algoritmo.

Ti consiglio quindi di iscriverti alla newsletter per rimanere aggiornato sulle nuove pubblicazioni, ricevere anteprime e contenuti riservati! Ti basta compilare i due seguenti campi:



Algoritmo babilonese calcolo radice quadrata

Se te lo sei perso, mi interessa informarti che in passato ho scritto un articolo illustrante l’algoritmo (comunemente indicato) per calcolare la radice quadrata. Lo puoi trovare qui.

Ora però te ne illustro un altro, più banale da apprendere, facile da applicare e molto efficiente ma sostanzialmente in disuso. Fu introdotto dai babilonesi, pensa che storia che ha questo algoritmo alle spalle! 😉 Perchè dimenticarlo?

Ecco la sua pseudocodifica:

x,a naturali (x è il numero di cui si vuole estrarre la radice, a un’approssimazione per difetto                    che si intuisce, in caso non se ne abbia idea a=1 )

finchè non è abbastanza preciso il risultato:

t=x

r=(t+a)/2 (media aritmetica)

s=x/r (media armonica)

t=r

a=s

risultato s

 

Le operazioni dopo il finchè puoi anche decidere a priori di eseguire 3-4 volte, tanto la velocità con cui s converge alla radice effettiva di x è davvero elevata. Prova per esempio con la radice di 2, vedrai che già dopo 3 iterazioni avrai una precisione di 5-6 cifre dopo la virgola.

Moltiplicazione alla russa

Un algoritmo relativo alla moltiplicazione, te l’ho già presentato, tuttavia trovo interessante ed intuitivo anche un secondo algoritmo per eseguire i prodotti tra due numeri naturali. Sto parlando della moltiplicazione alla russa. Sostanzialmente il metodo si basa sul raddoppiare il primo fattore e dimezzare il secondo, finchè questo non diventa 1. In caso di numero dispari, ad essere diviso sarà n-1. Il risultato del prodotto è infine la somma dei numeri disposti sotto il primo fattore, corrispondenti ai numeri  dispari della seconda colonna.

Immagine presa da http://www.aliperlamente.it/ED/Moltiplicazioni/Molt.russa.pdf

 

Bene, spero di averti incuriosito ed interessato con questi cenni a 4 algoritmi antichi e curiosi. Se ne conosci altri degni di nota, ti prego di contattarmi nei commenti, sulla pagina Facebook o nel modulo per contattarmi raggiungibile da qui.

Spero possano nascere discussioni interessanti 😉

Paradosso del compleanno

Quante persone ci devono essere in una stanza perchè la probabilità che due di loro siano nate lo stesso giorno sia maggiore al 50% ?

Se sei già iscritto alla newsletter, hai già ricevuto una mail in cui ti ho introdotto al Paradosso del compleanno. Se non sei ancora iscritto, intanto ti invito a farlo compilando il modulo qui sotto, poi ti consiglio di aspettare a proseguire la lettura e provare a trovare una risposta alla domanda qui sopra.

[optin_box style=”7″ alignment=”center” disable_name=”Y” email_field=”email” email_default=”Inserisci la tua email” email_order=”0″ integration_type=”mailchimp” list=”aeff8c6727″ name_field=”FNAME” name_default=”Enter your first name” name_order=”0″ name_required=”Y” opm_packages=””][optin_box_field name=”headline”]Here’s The Headline For The Box[/optin_box_field][optin_box_field name=”paragraph”][/optin_box_field][optin_box_field name=”privacy”][/optin_box_field][optin_box_field name=”top_color”]undefined[/optin_box_field][optin_box_button type=”0″ button_below=”Y”]Iscriviti subito![/optin_box_button] [/optin_box]

Se non sai che cosa sia un paradosso, ti consiglio di leggerti l’articolo: Che cos’è una paradosso?

Bene, spero che tu abbia provato a trovare una risposta alla domanda del Paradosso del compleanno:) .

Ho pensato che fosse meglio illustrare la spiegazione passo per passo, basandomi su un ragionamento ad esclusione che penso sia naturale seguire.

Quindi…partiamo!

Per semplificare leggermente la situazione, non considero la possibilità che un anno possa essere bisestile. Prendiamo quindi come riferimento un anno di 365 giorni. Comunque, se vuoi essere più preciso, puoi risolvere il paradosso del compleanno anche considerando la possibilità dell’anno bisestile, non si complicherà nulla di molto 😉 .

Il primo numero che facilmente ti è saltato in mente è 366. Infatti necessariamente se ci sono 366 persone, con 365 compleanni disponibili, due di queste sono certamente nate lo stesso giorno. Tuttavia qui siamo di fronte ad una probabilità che l’evento si verifichi che è pari a 100%. Il problema ci dice di trovare il numero sufficiente ad avere una probabilità maggiore al 50%.

Iniziamo quindi a fare qualche taglio sul numero di persone…

Per evitare di perdersi in inutili conti, mi avvicino un po’ alla soluzione, senza però dirti ancora il risultato finale. Ti sembrerà strano infatti, ma con sole 57 persone si ha già il 99% di probabilità che due persone siano nate lo stesso giorno. Strano, vero? Si chiama paradosso del compleanno per qualcosa 😉

Tuttavia per avere poco più del 50% di probabilità ne bastano molte meno…

Ma ora veniamo al ragionamento matematico da seguire per arrivare alla soluzione. C’è infatti un piccolo accorgimento da seguire: non ragionare sulla singola persona ma ragionare a coppie. Infatti non ci interessa in che giorno sono nati i singoli, ci interessa che due dei presenti siano nati lo stesso giorno.

Iniziamo quindi a considerare il numero di coppie possibili con persone presenti.

Partiamo dal caso in cui vi siano tre persone, mettiamo che siano P1, P2, P3. Le coppie possibili sono quindi (P1,P2), (P1,P3) e (P2,P3). Ora con un ragionamento analogo, si può arrivare a dire che con 4 persone (P1, P2, P3, P4) si possono formare al massimo 6 coppie. Se non te ne sei ancora accorto, si può trovare il numero delle coppie possibili applicando una semplice formula, che coinvolge l’utilizzo del fattoriale (!).

La formula in questione è la seguente:

dove nel nostro caso n è il numero delle persone presenti e k è 2, ovvero la dimensione dei gruppi in cui vogliamo combinare le persone.

Non mi soffermo più di tanto sull’aspetto teorico (magari in futuro potrei dedicare un po’ di articoli a questi argomenti..), quindi se non ti riesci a spiegare questi risultati, ti consiglio di ricercare su Google “Combinazioni semplici”, troverai le risposte a tutte le tue domande 🙂 .

Ora prova a calcolare quante coppie possibili ci sono con 57 persone…

Adesso inizia a sembrarti un po’ più plausibile che con 57 persone ci sia quasi la certezza che due siano nate lo stesso giorno?

Ma veniamo finalmente agli ultimi passaggi, quelli che ci porteranno ad arrivare al risultato esatto.

Ora diventa un fatto di puri calcoli, infatti la strategia da adottare te l’ho già spiegata. Devi sostanzialmente cominciare con una coppia, continuare ad aggiungere gente (il nostro n) e vedere come cambia la probabilità. Tuttavia c’è un ultimo consiglio che posso darti. Non ti consiglio di controllare la probabilità di condividere un compleanno, ma ti suggerisco di calcolare la probabilità che ogni nuova persona abbia un compleanno diverso da quelle già presenti.

Quindi, partendo da una persona sola, puoi vedere facilmente come la probabilità che la seconda persona non sia nata lo stesso giorno della prima sia del 364/365. La terza persona ora avrà un giorno in meno (disponibile) rispetto alla precedente, quindi ha a disposizione 363 giorni. Tuttavia essendo la nascita di una persona non influenzata del compleanno degli altri, nella teoria della probabilità si impara che due eventi del genere, affinchè accadano insieme hanno una probabilità del 364/365*363/365=0,9918, cioè del 99,18%.

Ricapitolando il ragionamento, quindi, con tre persone si ha la probabilità del 99,18% che queste tre siano nate in giorni diversi.

Procedendo analogamente, aggiungendo persone, magari evitando di fare troppi conti per niente (quindi provando ad aggiungere 4-5 persone ogni volta), dovresti arrivare a scoprire il numero di persone sufficiente per avere una probabilità maggiore al 50% che due di questa siano nate lo stesso giorno.

Dai conti, dovrebbe risultarti che sono necessarie 23 persone per avere una probabilità maggiore al 50%. Infatti moltiplicando le prime 23 frazioni (rappresentanti le probabilità che l’evento non si verifichi), come abbiamo fatto prima, si giunge a dire che con 23 frazioni il prodotto è 0,493. Ossia con 23 persone c’è il 49,3% di probabilità che due non siano nate lo stesso giorno.

Quindi in questa situazione ci sarà il 50,7% di probabilità che due siano nate lo stesso giorno, proprio come volevamo noi.

Bene, il percorso che abbiamo dovuto fare per arrivare alla soluzione non è stato molto breve, tuttavia le analisi fatte non hanno nulla di complicato al loro interno.

Quindi se nella lettura hai accumulato dubbi, richieste o suggerimenti, ti invito a commentare o a contattarmi con l’apposito form disponibile qui. Anche una rilettura potrebbe esserti utile ;).

Ti sarei molto grato anche se condividessi l’articolo con i tuoi amici.

Se vuoi un’ulteriore spiegazione puoi guardare anche questo video che trovo molto ben fatto:

Spero di essere stato abbastanza chiaro, alla prossima!

 

 

I 5 migliori film sulla matematica

A me la matematica è sempre piaciuta. Secondo me i film che hanno essa come tema centrale sono bellissimi, un po’ perchè illustrano la vita e la genialità di personalità particolari, un po’ perchè ti prendono a tal punto da farti dimenticare di ciò che sai effettivamente fare e ti fanno pensare in grande. Nel corso degli anni ne sono usciti parecchi e io ne ho visto la gran parte, per questo ho pensato di raccogliere i 5 migliori film sulla matematica che ho visto. Magari non tutti li hai già visti! 🙂

Se ti interessano i film sulla matematica senz’altro non ti guasterà sapere che ho preparato anche una lista dei 50 migliori libri di matematica

Intanto li elenco qui di seguito, senza però metterli in un ordine preciso, non sono dal migliore al peggiore 🙂

Lista dei migliori film sulla matematica:

  • A BEAUTIFUL MIND
  • The imitation game
  • 21 – BlackJack
  • Will Hunting – genio ribelle
  • La teoria del tutto

Ora fornirò un mio parere, non troppo dettagliato, di ciascuno di questi 5 film sulla matematica. Se hai qualche aggiunta da fare o qualche parere differente dal mio, ti invito a commentare, si aprirebbe una discussione davvero interessante 😉

A BEAUTIFUL MIND

Questa è la storia di John Nash. Lui era uno tra i matematici più brillanti e originali del Novecento, Nash ha rivoluzionato l’economia con i suoi studi di matematica applicata alla teoria dei giochi, vincendo il Premio Nobel per l’economia nel 1994. La storia mi ha appassionato molto, soprattutto perchè mi ha fatto conoscere questo gran personaggio, facendomi immedesimare pienamente in lui e nelle difficoltà che ha dovuto superare per diventare quello che è diventato. Spesso infatti le grandi capacità comportano gran responsabilità, che nel suo caso hanno minato anche la vita personale e la salute. Lo rivedrei altre 100 volte questo film, è sempre bello 🙂 Ah…dimenticavo! Se ti interessa la teoria dei giochi ecco un articolo che avevo scritto a riguardo: Introduzione teoria dei giochi

The imitation game

Sono le persone che nessuno immagina che possano fare certe cose, quelle che fanno cose che nessuno può immaginare.

Partendo da questa frase, che secondo me è fenomenale, vorrei dire che Alan Turing è un personaggio da scoprire. Lui è diventato famoso per varie ragioni, dal motivo meno importante (il logo della apple è un omaggio a Turing che morì mangiando una mela), a quelli più rilevanti. Basti pensare ai suoi contributi nel campo della crittografica, con il progetto enigma. Questo film è molto recente, per cui anche la qualità è eccellente e ciò permette di gustarsi pienamente la storia di questo straordinario personaggio. L’ho trovato molto ben fatto e soprattutto in grado di raccontare in modo diretto e chiaro anche alcuni aspetti della sua vita non ovunque così espliciti.

21 Vittoria, Grande Baldoria!

Questo film è molto avvincente, almeno secondo me. Differentemente dai precedenti e dai successivi film citati, questo è leggermente slegato dalla matematica in sè, ma coinvolge un tema molto caro a vari appassionati di matematica: IL GIOCO. In questo caso si parla di Blackjack. Vi invito a guardarlo anche se, come me, non capite “una mazza” di Blackjack. Il film è infatti ricco di emozioni, sorprese e storie che coinvolgono al di là del gioco in sè. Per cui se hai un paio d’ore di tempo libero, ti consiglio fortemente di guardarlo. Sappimi dire se ti è piaciuto! 😉

Se avessi ordinato i film citati in questa lista, in base ad una mia preferenza, probabilmente questo film sarebbe al secondo posto, dopo “A beautiful mind”. Trovo infatti che questo sia un grandissimo film, un po’ grazie ai bravissimi attori che l’hanno messo in atto, ma soprattutto grazie alla grandissima storia di Will Hunting. Viene raccontata la storia di Matt Damon, un problematico ragazzo prodigio e autodidatta con molti piccoli crimini alle spalle, che fa le pulizie al Massachusetts Institute of Technology (MIT). Questo film è stato molto utile per me, non solo perchè mi è piaciuto in quanto film, ma soprattutto perchè ricco di dialoghi, citazioni e situazioni cariche di ispirazione. Mi sentirei, quasi quasi, di dirti di smettere di fare quello che stai facendo (prima condividi questo articolo 🙂 ) e guardartelo.

Avrai dei momenti difficili, ma ti faranno apprezzare le cose belle alle quali non prestavi attenzione.

Non penso che questo film necessiti di troppe presentazioni, come “The imitation game” del resto. E’uscito a gennaio 2015 e racconta la storia di un genio, questa volta della fisica. Non parla di un fisico qualunque, ma del più grande e celebrato fisico della nostra epoca, Stephen Hawking. E’ un film molto interessante, non solo perchè fa conoscere la storia travagliata di questo grande personaggio, ma perchè fa capire che non bisogna fermarsi di fronte alle difficoltà, fa riflettere e in alcune situazioni è pure simpatico 🙂

Con questo quinto film, la mia lista con i Migliori film sulla matematica termina. Spero vivamente di averti fatto conoscere qualche film nuovo o magari di averti fatto venire la voglia di riguardarne qualcuno. Se ne hai visti altri inerenti a questa tematica, che ritieni degni di essere citato in questa lista (o anche no 🙂 ), ti prego di inserirlo nei commenti che sarò felice di guardarlo.

Detto ciò ti saluto, spero che possa nascere qualche discussione interessante qui o sulla pagina Facebook MATHONE.