I ricercatori di informatica dell'Università di Copenaghen e dell'Università tecnica della Danimarca (DTU) pensavano che mancassero cinque anni alla soluzione di un indovinello di matematica degli anni '80. In realtà, e senza saperlo, avevano quasi risolto il problema e avevano appena rivelato gran parte della soluzione in un articolo di ricerca. La soluzione potrebbe essere utilizzata per migliorare i telefoni ei computer di domani.

Jacob Holm ed Eva Rotenberg

Un vero e proprio rompicapo. Ecco come si può tranquillamente descrivere questo problema matematico nella disciplina della teoria dei grafi. Due matematici del Dipartimento di Informatica dell'Università di Copenaghen e DTU hanno ora risolto un problema con cui i più veloci e intelligenti del mondo si sono trovati alle prese dagli anni '80.

I due informatici, L'assistente professore Jacob Holm dell'UCPH e la professoressa associata Eva Rotenberg del DTU hanno quasi dato via la loro soluzione nell'estate del 2019, dopo aver presentato un articolo di ricerca che è diventato il precursore dell'articolo in cui hanno finalmente risolto l'enigma di matematica.

"Avevamo quasi rinunciato a prendere l'ultimo pezzo e a risolvere l'enigma. Pensavamo di avere un risultato minore, uno che era interessante, ma in nessun modo risolto il problema. Pensavamo che ci sarebbero stati altri cinque anni di lavoro, nella migliore delle ipotesi, prima di poter risolvere l'enigma, " spiega Jacob Holm, chi fa parte di BARC, la sezione algoritmi presso il Dipartimento di Informatica dell'UCPH.

Il problema delle tre utilità

Nel 1913, un precursore dell'enigma matematico ora risolto è stato pubblicato in La rivista Strand come "Il problema delle tre utilità". Ha indotto i lettori della rivista a grattarsi la testa ea riflettere. Nel problema, ognuno dei tre cottage deve avere l'acqua, gas ed elettricità, mentre le "linee" tra le case e l'acqua, elettricità e gas potrebbero non incrociarsi, il che non è possibile.

Una soluzione tra le righe

In poche parole, il puzzle riguarda come collegare un numero di punti in un grafico senza consentire alle linee che li collegano di incrociarsi. E come, con un calcolo matematico, un algoritmo, è possibile apportare modifiche a un'ampia "rete di grafi" per garantire che nessuna linea si intersechi senza dover ricominciare da capo. Proprietà che possono essere utilizzate per, tra l'altro, costruendo immense reti stradali o minuscole interiora di computer, dove i circuiti elettrici sui circuiti stampati non possono incrociarsi.

Jacob Holm si interessa all'enigma matematico dal 1998, ma la risposta è stata rivelata solo mentre i due ricercatori stavano leggendo il loro articolo di ricerca già presentato. Intanto, i ricercatori hanno sentito parlare di una nuova tecnica matematica che si sono resi conto che potrebbe essere applicata al problema.

"Durante la lettura del nostro articolo di ricerca, improvvisamente ci siamo resi conto che la soluzione era davanti ai nostri occhi. La nostra reazione successiva è stata "oh no, ci siamo sparati ai piedi e abbiamo dato via la soluzione, ', afferma la professoressa associata Eva Rotenberg di DTU.

Sulla teoria dei grafi

Un grafico è una costruzione molto semplice utilizzata per modellare cose che possono essere descritte come oggetti e le connessioni tra di loro. La teoria dei grafi è sia un'area della matematica che uno strumento importante nell'informatica.

In tale contesto, un grafico può essere illustrato da un diagramma costituito da più punti (nodi, vertici) associati a un numero di linee (bordi). Ciascun bordo è illustrato come una linea (o un pezzo curvo) con nodi come due estremità.

Sulla soluzione

Esistono due tipi di aggiornamenti nei grafici dinamici:uno può eliminare uno spigolo e tu puoi inserirne uno nuovo. Queste due operazioni devono essere eseguite dall'utente, mentre un algoritmo tiene traccia in ogni momento del disegno della rete. Questo è l'algoritmo per il quale i ricercatori hanno trovato la ricetta.

Potrebbe essere utilizzato per l'elettronica del computer

Questo è stato il momento in cui i due ricercatori si sono impegnati a scrivere il documento di ricerca e a risolvere le questioni in sospeso per risolvere l'enigma su cui Holm aveva lavorato a intermittenza dal 1998.

"Abbiamo lavorato all'articolo senza sosta, per cinque-sei settimane. E, ha finito per riempire più di 80 pagine, "dice Eva Rotenberg.

Fortunatamente, nessuno li ha preceduti alla soluzione e i due ricercatori hanno potuto presentare i loro risultati alle principali conferenze di informatica teorica, che si sarebbero dovuti tenere a Chicago, ma finì per essere trattenuto virtualmente.

Così, per cosa può essere utilizzata la soluzione a questo enigma matematico? I due ricercatori non lo sanno per certo, ma hanno alcuni suggerimenti.

"La nostra ricerca è ricerca di base, quindi raramente sappiamo per cosa finirà per essere usato. Anche dall'inizio, troviamo applicazioni difficili da immaginare, "dice Jacob Holm, chi aggiunge, "La progettazione di microchip e circuiti stampati, presente in tutta l'elettronica, potrebbe essere un'area in cui il nostro risultato finisce per essere utilizzato. Quando si disegnano fili su un circuito, non devono mai intersecarsi. Altrimenti, si verificheranno cortocircuiti. Lo stesso vale per i microchip, che contengono milioni di transistor e per i quali bisogna avere un disegno grafico."