Eccoci arrivati all’approfondimento del secondo algoritmo citato nell’articolo precedente, l’algoritmo per la moltiplicazione utilizzato nell’antico Egitto.
L’articolo in cui l’ho introdotto è il seguente (se non l’hai ancora letto ti consiglio di darci un’occhiata) : Algoritmi antichi e curiosi .
Ecco qui la pseudocodifica dell’algoritmo di cui andremo a parlare tra poco:
a,b interi
z = 0
finchè (a>0):
se a dispari -> z=z+b
a=a//z (divisione intera)
b=b*2
risultato z
Prima di cominciare con un breve approfondimento dedicato, ho pensato di introdurre l’argomento con un video in cui ci sono alcuni esempi. I passaggi seguiti non sono proprio evidenti ma ti assicuro che è esattamente ciò che viene definito dall’algoritmo scritto qui sopra.
Penso che possa anche risultarti più chiaro il funzionamento.
Andiamo ora a vedere il funzionamento dell’algoritmo “ragionando in base 2”. Ti dico questo perchè il codice prima citato può essere adattato ad una qualsiasi base.
I due casi che si possono presentare in prima battuta sono i seguenti:
a pari
a dispari
Scriviamo quindi a=2a’ nel primo caso e a=2a”+1 nel secondo.
Analizziamo ora il primo caso.
In tali condizioni z diventerà uguale alla seguente espressione: (2a’)b = a’ (2b) in quanto moltiplicare a*b o o (a/2)*(2b) è la stessa cosa.
Pertanto le operazioni da eseguire dopo il “finchè” nel primo caso non sono rilevanti più di tanto.
Ma andiamo ora ad analizzare il secondo caso, ossia con a dispari.
z=ab=(2a”+1)b=2a”b + b = a” (2b) +b
Ora quindi siamo nelle stesse condizioni del caso precedente per il primo addendo, abbiamo però una addendo “b” in più. Per cui possiamo dire di fare (a/2)*(2b) ed assegnare tale espressione alla variabile z, ricordandoci però di quel “+b” che compare nell’espressione prima citata.
Per cui nel caso a sia dispari, mi vado a ricordare di b e lo sommo a priori a z.
Andando quindi a riassumere il tutto, che probabilmente non ti è ancora del tutto chiaro (è difficile spiegare un algoritmo scrivendo 🙂 ), diciamo che l’algoritmo della moltiplicazione egizia si basa su un un principio unico.
Esso è il seguente: A * B = (A/2) * (2B).
Questo è infatti ciò che viene eseguito a priori in questo algoritmo.
Tuttavia nel caso A sia dispari, nel dividere per 2 (con la divisione intera) si andrebbe a perdere qualcosa. Pertanto, siccome so che succede sempre così, mi faccio trovare pronto e sommo a priori B a z. Così da non perdermi nulla nella divisione intera di a.
Spero di averti chiarito abbastanza il comportamento di questo algoritmo.
In caso tu abbia dubbi, critiche o suggerimenti (come al solito) non esitare a commentare o contattarmi.
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.
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 n 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!
Hai letto attentamente la frase citata qui sopra? Non sembra essere una frase molto complicata, giusto? 😉 Questo è quello che viene chiamato il paradosso del mentitore.
Ora ti faccio un piccola domanda e ti chiedo uno sforzo un po’ più grande: Sapresti dimostrarmi se la frase sopra citata è vera o falsa?
Hai provato a pensare ad una possibile dimostrazione/spiegazione?
Bene 🙂 sono contento che, incuriosito, hai deciso di proseguire la lettura. Purtroppo però devo dirti che non c’è alcun modo per rispondere alla domanda che ti ho posto. Analizziamo quindi i due casi possibili relativi alla proposizione prima citata, il caso in cui sia vera e quello in cui sia falsa.
Se fosse vera, allora la frase non sarebbe veramente falsa (la verità della proposizione non invalida la falsità espressa nel contenuto della proposizione).
Se invece la proposizione fosse falsa, allora il contenuto si capovolgerebbe (è come se dicesse “Questa frase è vera“) quando abbiamo appena affermato il contrario.
Spero che tu non ci sia rimasto male…comunque sono sicuro che ci hai pensato almeno un attimo alla possibilità che non vi sia risposta a tale domanda. Dopotutto…il titolo dell’articolo contiene la parola paradosso 🙂
Questo è conosciuto come paradosso del mentitore, o meglio antinomia del mentitore. Talvolta puoi trovarlo anche sotto un nome ancor più suggestivo: Paradosso di autoreferenzialità.
Questo paradosso è stato di particolare interesse per molti personaggi illustri nel corso della storia, alcuni di essi hanno anche provato a fornire un’elaborata e spesso poco lineare soluzione al problema che ti ho posto prima. Ti lascio la possibilità di documentarti liberamente su tali soluzioni, se vuoi a questo link ne potrai leggere alcune 😉
Spero che l’articolo ti abbia incuriosito e che ti abbia lasciato un po’ perplesso, perchè in fondo è questo il bello di un teorema, di un paradosso e della matematica, subito non sono del tutto chiari, ma dopo sono affascinanti 🙂 Lascia pure un commento se hai dubbi, suggerimenti o critiche da pormi, sarò lieto di risponderti.
Il paradosso di Russell, formulato dall’omonimo Bertrand Russell tra il 1901 e il 1902, è una delle antinomie più importanti della storia della filosofia e della logica. E’ anche conosciuto dai più come il paradosso del barbiere.
In questa sede ho pensato che fosse più appropriato farne una trattazione più generalizzata, limitandomi quindi ad una semplice enunciazione del paradosso in termini della teoria degli insiemi.
Il paradosso di Russell dice quindi che:
L’insieme di tutti gli insiemi che non appartengono a se stessi appartiene a se stesso se e solo se non appartiene a se stesso. Formalmente,
Ora, ho pensato di limitarmi ad enunciare tale paradosso in maniera formale, perchè credo che a fini divulgativi sia più interessante presentarlo proprio come il paradosso del barbiereche, senza particolari sforzi, può essere ricondotto all’enunciato sopra citato.
Il paradosso del barbiere è il seguente:
Un certo Villaggio ha tra i suoi abitanti un solo barbiere. Egli è un uomo ben sbarbato che rade tutti – e unicamente – gli uomini del villaggio che non si radono da soli. Questi sono i fatti. La domanda è: << Chi rade il barbiere?? >>
Ora potresti pensare, se per caso non avessi mai sentito parlare di questa antinomia, che il barbiere si rada da solo. Tuttavia in tal caso, essendo che lui stesso è un barbiere, lui non dovrebbe essere in grado di radersi da solo in quanto si fa radere dal barbiere. Nel caso in cui invece lui supponga di non essere in grado di radersi e decida di andare a farsi radere dal barbiere, lui stesso, sarebbe necessariamente in grado di radersi da solo.
Forse non ti è proprio chiaro, tuttavia questo è evidentemente un paradosso, una situazione senza alcuna via d’uscita. Sostanzialmente è una contestualizzazione ad una situazione verosimile dell’effettivo paradosso di Russell prima citato.
Per adesso ritengo sufficiente averti introdotto a questo paradosso, quindi ti lascio qui di seguito qualche riferimento nel caso tu voglia approfondire personalmente l’argomento, comunque penso proprio che in futuro ci ritornerò su questo tema, dato che mi attrae parecchio.
Per una spiegazione video del paradosso del barbiere clicca qui
Per un topic dedicato alla spiegazione formale ma non troppo complicata del paradosso di Russel clicca qui
Bene, spero di esserti stato utile e di averti stimolato almeno un po’ di stupore e curiosità. Questo articolo non aveva infatti lo scopo di trattare ogni tematica relativa all’argomento, ma semplicemente vuole metterti a conoscenza di questa bizzarra situazione e stimolarti a pensarci su.
Se ti è stato utile o comunque se ritieni l’articolo interessante mi renderesti molto felice se lasciassi un tuo commento qui sotto e/o condividessi l’articolo con i tuoi amici 😉
Detto ciò ti saluto, spero che possa nascere qualche discussione interessante qui o sulla pagina Facebook MATHONE.
