Home » Stiinta » Doi informaticieni au găsit soluția unei dileme matematice, veche de zeci de ani

Doi informaticieni au găsit soluția unei dileme matematice, veche de zeci de ani

Adrian Popovici 08.31.2020
Doi informaticieni au găsit soluția unei dileme matematice, veche de zeci de ani
O echipă de matematicieni danezi a descoperit soluția unui caz derivat din teoria grafurilor.

O echipă de matematicieni danezi a descoperit soluția unui caz derivat din teoria grafurilor.

Teoria grafurilor este folosită, în general, pentru jocurile logice și pentru testarea capacității de a inova. Cu toate aceste, unele cazuri ale acestei teorii s-au confruntat de-a lungul timpului cu o serie de probleme, matematicienii făcând progrese minime de-a lungul timpului.

În 1913, a fost făcută publică „problema celor trei utilități”, în sine problema se dovedește a fi una simplă, dar care are nevoie de un răspuns extrem de complicat. Imaginați-vă trei case care trebuie conectate la utilități: apă, gaze și electricitate. Condiția care trebuie îndeplinită în acest caz spune că conductele acestora nu trebuie să se întâlnească.

În sensul cel mai convențional – pe o foaie de hârtie obișnuită, bidimensională, ca exemplu de graf planare, nu este posibilă rezolvarea problemei celor trei utilități. Din nefericire, nu toate casele își pot primi conexiunile în aceste condiții.

Matematicienii explică faptul că această problemă nu este un puzzle ci, mai degrabă, un exemplu despre modul în care unele tipuri de rețele grafice nu sunt plane, adică capabile să aibă muchii, linii, care leagă diversele vârfuri, case și utilități, fără ca liniile să fie traversate.

Din această cauză a fost dezvoltată în anii 1970 teorema lui Kuratowski, care are rolul de a determina dacă un graf este sau nu planar. În timp, algoritmii creați de către oamenii de știință au reușit să reducă considerabil timpul necesar acestor calcule, notează Science Alert.

Anul 1990 și blocajul care i-a urmat

Cu toate acestea, după un ultim progres al algoritmilor a avut loc în anii 90 și nu s-au înregistrat progrese substanțiale în acest domeniu de zeci de ani, cel puțin nu în ceea ce privește algoritmii care pot rezolva grafii dinamici.

Anul trecut, informaticienii Jacob Holm, de la Universitatea din Copenhaga, si Eva Rotenberg, de la Universitatea Tehnică din Danemarca, și-au îndreptat atenția către problemă. Accidental și-au dat seama că au rezolvat deja cea mai mare parte a problemei într-o altă cercetare , o lucrare despre concepte planare înrudite, pe care perechea a publicat-o online în 2019.

Cu soluția deja publicată, perechea s-a agitat în săptămânile următoare, redactând o demonstrație formală a îmbunătățirii lor la algoritmul grafurilor, care nu mai văzuse îmbunătățiri încă din anii ’90. Cei doi cercetători explică faptul că munca lor s-a întins de-a lungul a mai multe săptămâni. Munca lor oferă un algoritm care necesită cel mai puțin timp de calcul pentru a afla dacă un grafic dinamic, fiind supus inserțiilor și ștergerilor de muchii care leagă vârfurile, poate suporta o integrare plană.

Studiul a fost publicat în volumul STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing.

Citește și:

Matematica poate fi folosită pentru a identifica cel mai bun loc de parcare

Omul care a revoluţionat matematica. Cum a reuşit Leonhard Euler să schimbe ştiinţele exacte – VIDEO

Nu trebuie creier mare pentru inteligenţă. Dovada o reprezintă albinele, care pot rezolva probleme de matematică

Ciudăţenia din matematică în ceea ce priveşte numărul 10. Este acesta unic?

Cele mai noi articole
Amuletă antică pentru protecție împotriva deochiului și a demonilor, redescoperită după 40 de ani
Amuletă antică pentru protecție împotriva deochiului și a demonilor, redescoperită după 40 de ani
Un pescar a fost aproape înghițit de viu de o balenă cu cocoașă. „Până aici mi-a fost, o să mor”
Un pescar a fost aproape înghițit de viu de o balenă cu cocoașă. „Până aici mi-a fost, o să mor”
Un vaccin împotriva maladiei Alzheimer, primul de acest fel, a trecut de ultimul stadiu al studiilor clinice umane
Un vaccin împotriva maladiei Alzheimer, primul de acest fel, a trecut de ultimul stadiu al studiilor clinice umane
Evaluare Națională 2021. Reguli de organizare și sfaturi pentru elevi. Cum să îţi gestionezi emoţiile?
Evaluare Națională 2021. Reguli de organizare și sfaturi pentru elevi. Cum să îţi gestionezi emoţiile?
Cipul cu energie solară, dezvoltat de ingineri din Elveția
Cipul cu energie solară, dezvoltat de ingineri din Elveția
Ollie, robotul foarte simpatic care calcă pe urmele roboților de la Boston Dynamics
Ollie, robotul foarte simpatic care calcă pe urmele roboților de la Boston Dynamics
ONU avertizează: „Următoarea pandemie” este aproape
ONU avertizează: „Următoarea pandemie” este aproape
Trei schelete uriașe de mamuți lânoși, descoperite de mineri în teritoriul Yukon din Canada
Trei schelete uriașe de mamuți lânoși, descoperite de mineri în teritoriul Yukon din Canada
Oamenii evoluează mai repede ca niciodată, iar cauza nu este genetică. Ce spune un nou studiu
Oamenii evoluează mai repede ca niciodată, iar cauza nu este genetică. Ce spune un nou studiu
Aleksandr Kerenski – politicianul rus care ar fi putut schimba cursul istoriei, abolind monarhia, consolidând democrația și  oprind bolșevismul
Aleksandr Kerenski – politicianul rus care ar fi putut schimba cursul istoriei, abolind monarhia, consolidând democrația ...
Misterul din jurul întunecării stelei Betelgeuse a fost rezolvat
Misterul din jurul întunecării stelei Betelgeuse a fost rezolvat
Sportul după pandemie. Actorul Will Smith îşi reaminteşte exerciţiile la sală într-un clip viral
Sportul după pandemie. Actorul Will Smith îşi reaminteşte exerciţiile la sală într-un clip viral
Prestigiul său a fost nemaiîntâlnit în perioada Renascentistă. El a scris primul tratat modern de politică
Prestigiul său a fost nemaiîntâlnit în perioada Renascentistă. El a scris primul tratat modern de politică
Teama de ac, mai des întâlnită la bărbați decât la femei
Teama de ac, mai des întâlnită la bărbați decât la femei
Grenade și cartușe din Al Doilea Război Mondial, găsite într-o pădure din Neamț
Grenade și cartușe din Al Doilea Război Mondial, găsite într-o pădure din Neamț
Arcul de Triumf, simbolul victoriei României din Primul Război Mondial
Arcul de Triumf, simbolul victoriei României din Primul Război Mondial
SOLSTIŢIUL DE VARĂ 2021, cea mai lungă zi din an. Totul despre debutul verii astronomice şi tradiţiile din această zi
SOLSTIŢIUL DE VARĂ 2021, cea mai lungă zi din an. Totul despre debutul verii astronomice şi tradiţiile din această zi
Creierul uman are foarte multe în comun cu testiculele. Ce au aflat cercetătorii despre aceste organe
Creierul uman are foarte multe în comun cu testiculele. Ce au aflat cercetătorii despre aceste organe