I microchip, le CPU[1] e più in generale i componenti principali ed essenziali per un computer sono tutti basati su queste sottile wafer di silicio. Bisogna progettarli, disegnarli e poi con sofisticate tecniche costruirli. In un microchip abbiamo il condensato di millenni di storia scientifica e soprattutto tutta la matematica sviluppata dall’uomo nel corso dei secoli. Una parte interessante e che riguarda il nostro articolo è senz’altro quella matematica che va sotto il nome di “trasformazioni geometriche topologiche” o meglio definita come TOPOLOGIA[2].
Senza addentrarci in questo argomento, affascinante ma complesso, possiamo affermare che con i principi e le regole della topologia è possibile disegnare i complicatissimi circuiti che faranno parte dei chip!
Quando si studia il “Mondo digitale” non sai mai quale strada prendere per iniziare a spiegare, trovando poi, facilmente, percorsi imprevedibili e astrusi.
I ponti di Königsberg è un problema sorto nel 1700 e fa parte della “mitologia” dell’informatica. Sono rimasto affascinato come da un semplice problema derivato dal semplice diletto della gente che passeggiava la domenica nella propria città (Königsberg) attraverso sette ponti che collegavano due isolette formate dal fiume Pregel situate nel centro della città, abbia creato un presupposto il cui studio diventerà così importante e fondamentale nell’evoluzione del pensiero informatico!
Nella storia dell’evoluzione scientifica ci sono innumerevoli esempi su come alcune scoperte abbiano condotto a risultati e applicazioni al di là di ogni più fertile immaginazione!
Piccolo quadro sinottico per inquadrare il periodo storico:
| 1700 | Rivoluzione Industriale |
| 1800 | Rivoluzione Scientifica |
| 1900 | Rivoluzione della Fisica con la Meccanica quantistica |
Propongo un esempio di come una rilevante scoperta scientifica dell’inizio del novecento, abbia avuto i suoi sviluppi quasi un secolo dopo:
Nel 1905 venne annunciato da Einstein la scoperta dell’effetto fotoelettrico[3] per il quale ricevette il Nobel nel 1921.
In una conferenza stampa sulla scoperta, venne incalzato dai giornalisti che gli domandarono quali applicazioni si poteva avere nel futuro utilizzando questo effetto fotoelettrico. Lui rispose candidamente che non lo sapeva e aggiunse che lui era un fisico e il suo compito era quello di scoprire i fenomeni, alle applicazioni ci avrebbero pensato poi gli ingegneri.
Oggi le applicazioni dell’effetto fotoelettrico sono innumerevoli, dal telecomando della TV, alle macchine fotografiche digitali, alla chiusura e apertura delle porte di un ascensore, sistemi d’allarme ecc. ecc.
Dopo questa digressione torniamo ai ponti di Königsberg. Siamo nel 1700 e la città di Königsberg è la capitale della Prussia Orientale. Attualmente è un oblast[4] della Russia e la città ora si chiama Kaliningrad, in onore di un luogotenente di Stalin. E’ stata annessa all’URSS nel 1945 e “russificata” facendo emigrare gli abitanti tedeschi e rimpiazzandoli con popolazione di origine russa.
La “Montagna del re” è stata la città natale del caro vecchio Immanuel Kant ma anche di vecchie volpi matematiche quali David Hilbert, Christian Goldbach e Rudolph Otto Sigismund Lipschitz.
L’aria del mar Baltico sembra proprio fare bene a un certo tipo di pensiero, ma anche la struttura della città sembra voler solleticare la curiosità matematica dei suoi abitanti.
Il fiume Pregel crea nella topografia della città due isole, che sono unite alla terraferma per mezzo di sei ponti, mentre un ponte unisce tra loro le due isole, come illustrato, totale ponti: sette.
Figura 1: Mappa di Königsberg con i ponti evidenziati [4]
Il problema che stuzzica la curiosità degli abitanti di Königsberg durante le loro passeggiate domenicali riguarda proprio i suoi sette ponti:
è possibile trovare un percorso a piedi per la città in modo tale da attraversare una e una sola volta tutti e sette i ponti?
“Sono il signor Eulero, risolvo problemi”
Al problema dei ponti di Königsberg è possibile rispondere solo e soltanto in due modi: o tale percorso esiste o non esiste.
E in Matematica ogni affermazione deve essere supportata da una dimostrazione.
Nel primo caso bisognerà esibire una soluzione, mentre nel secondo occorrerà mostrare che ogni possibile percorso non fornisce una soluzione adeguata.
La domanda arrivò irrisolta alle orecchie di Leonhard Euler. Il buon Eulero è uno di quei matematici che per rispondere a un problema getta le fondamenta di una nuova branca, bendato e con un braccio legato dietro la schiena.
In questo caso, decide di pubblicare nel 1736 “Solutio problematis ad geometriam situs pertinentis” (“Soluzione a un problema relativo alla geometria di posizione”), ponendo le basi per la moderna Teoria dei Grafi e fornendo una risposta al quesito.
Un grafo è un oggetto costituito da dei puntini (chiamati vertici) collegati tra loro attraverso delle linee (chiamate archi), in modo da ridurre all’osso le proprietà topologiche davvero importanti di un problema. Nel nostro caso, non abbiamo bisogno di una cartina dell’intera Königsberg, ma solo di quattro vertici che rappresentano le due sponde di terraferma e le due isolette (A; B; C; D) e di sette archi (a; b; c; d; e; f; g) che rappresentano i ponti (7).
Forza bruta vs Colpi di fioretto
Una volta ridotto il problema dei ponti di Königsberg al suo scheletro, sono possibili due possibili strategie di risoluzione.
La prima è la forza bruta: dal momento che il numero di possibili combinazioni di percorso è finita, è possibile trovare tutte le possibili passeggiate e verificare se ci sono soluzioni. Proviamo a fare una passeggiata: partiamo da A, attraverso, rientro attraverso d, e passo per e arrivando in D. Il ponte g se lo attraverso mi riporta in in C e da lì riattraverso c o d per arrivare in A.
Questo approccio ha il vantaggio di poter essere eseguito da un computer, ma ha lo svantaggio di non farci capire meglio la natura del problema.
Se un domani volessimo risolvere il problema dei ponti di Vladivostok o di Castrovillari dovremmo per forza ricominciare da capo.
L’alternativa è la finezza dei colpi di fioretto dell’intelletto umano.
Si definisce grado di un vertice di un grafo il numero di archi che si connettono a tale vertice.
Nell’esempio di Figura 2, il vertice A è collegato con cinque archi/ponti, quindi è di grado 5, mentre i vertici B, C, e D sono di grado 3.
Arrivato a questo punto il buon Eulero tira fuori dal cilindro il suo Teorema:
È possibile passare dal vertice X al vertice Y (diverso da X) attraversando una e una sola volta tutti gli archi se e solo se gli unici vertici di grado dispari sono proprio X e Y.
Se X coincide con Y, è possibile passare una e una sola volta tutti gli archi se e solo se tutti i vertici sono di grado pari.
La soluzione del problema dei ponti di Königsberg è allora a portata di mano: ogni vertice del grafo di Figura 2 è di grado dispari, quindi la risposta è no, non esiste un tale percorso.
Con buona pace dei passeggiatori della domenica che con monocoli e ombrellini camminano a braccetto del LungoPregel, sperando di riuscire un giorno a compiere l’impresa per poi vantarsene con gli amici al successivo tè in salotto.
[1] Sigla di central processing unit, la componente di un calcolatore (detta anche processore) che carica le istruzioni dei programmi in memoria, le interpreta e manipola i dati di conseguenza. I componenti minimali di una CPU sono l’unità di controllo, l’unità aritmetico-logica (ALU) e i registri.
[2] La topologia si occupa delle figure che cambiano grandezza e forma e ha per proprietà invarianti: Il tipo di linea. La continuità della linea. La topologia è una branca della geometria che studia le proprietà delle figure, e in generale degli oggetti matematici, che non cambiano quando viene effettuata una deformazione senza “strappi”, “sovrapposizioni” o “incollature”. È una delle più importanti branche della matematica moderna.
[3] Nella fisica dello stato solido l’effetto fotoelettrico è il fenomeno fisico di interazione radiazione-materia caratterizzato dall’emissione di elettroni da una superficie, solitamente metallica, quando questa viene colpita da una radiazione elettromagnetica, ossia da fotoni aventi una certa lunghezza d’onda.
[4] Il termine oblast‘ può essere tradotto in italiano come “provincia” o “regione”, e attualmente ci sono 46 oblast‘. Esse sono il tipo più comune degli 85 soggetti federali della Russia.
Fonti
[1]- Béla Bollobás, Modern Graph Theory, New York, Springer–Verlag, 1998
[2]- Rudi Mathematici Numero 060 – «Wir müssen wissen, wir werden wissen».
[3]- Tim Räz – Euler’s Königsberg: The Explanatory Power of Mathematics, European Journal for Philosophy of Science volume 8, pages331–346(2018) [4]-Wikipedia – Problema dei ponti di Königsberg
Matematico, ricercatore e sbadato professionista.
Non chiedetegli di fare i conti al ristorante, non è capace: vi ritroverete a dover pagare quantità immaginarie ed essere costretti a lavare i piatti per qualche settimana.
cosa ne pensi?