Home » Știință » 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

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.
Publicat: 31.08.2020

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?

Urmărește DESCOPERĂ.ro pe
Google News și Google Showcase
Cele mai noi articole
Pentru prima oară în ultimii 130 de ani, Muntele Fuji nu are zăpadă
Pentru prima oară în ultimii 130 de ani, Muntele Fuji nu are zăpadă
(P) Brazii de Crăciun albi și înzăpeziți evocă o atmosferă magică în fiecare casă
(P) Brazii de Crăciun albi și înzăpeziți evocă o atmosferă magică în fiecare casă
Fosila unei păsări de pradă uriașe oferă noi informații despre fauna din America de Sud de acum 12 milioane de ani
Fosila unei păsări de pradă uriașe oferă noi informații despre fauna din America de Sud de acum 12 milioane de ani
De ce alegerile din SUA au loc mereu marțea?
De ce alegerile din SUA au loc mereu marțea?
Educația, ocupația și averea influențează riscul de deteriorare cognitivă
Educația, ocupația și averea influențează riscul de deteriorare cognitivă
Test de cultură generală. Cât cântărește atmosfera Pământului?
Test de cultură generală. Cât cântărește atmosfera Pământului?
Invenția neobișnuită care extrage CO2 din atmosferă și îl transformă în combustibil
Invenția neobișnuită care extrage CO2 din atmosferă și îl transformă în combustibil
Afirmație rară din partea unui fost oficial de la Pentagon. Ce a dezvăluit despre o fotografie cu un OZN din București?
Afirmație rară din partea unui fost oficial de la Pentagon. Ce a dezvăluit despre o fotografie cu un OZN din București?
ANM anunță temperaturi anormale pentru luna noiembrie
ANM anunță temperaturi anormale pentru luna noiembrie
Motivul pentru care autoritățile suedeze anulează proiectele eoliene din Marea Baltică
Motivul pentru care autoritățile suedeze anulează proiectele eoliene din Marea Baltică
Cum s-a vândut comuniştilor masonul şi marele scriitor Sadoveanu. Apoi a asistat impasibil la închiderea în puşcării „a fraţilor săi”
Cum s-a vândut comuniştilor masonul şi marele scriitor Sadoveanu. Apoi a asistat impasibil la închiderea în puşcării ...
Universitățile din Anglia cresc taxele pentru studenți pentru prima oară în aproape un deceniu
Universitățile din Anglia cresc taxele pentru studenți pentru prima oară în aproape un deceniu
Cum explică oamenii de știință legătura dintre depresie și temperatura corpului?
Cum explică oamenii de știință legătura dintre depresie și temperatura corpului?
Ucraina acuză Google că ar fi dezvăluit poziția unor obiective militare
Ucraina acuză Google că ar fi dezvăluit poziția unor obiective militare
Un nou tratament promițător pentru cel mai mortal tip de cancer cerebral
Un nou tratament promițător pentru cel mai mortal tip de cancer cerebral
Un fizician susține că un alt univers ar fi existat înainte de Big Bang
Un fizician susține că un alt univers ar fi existat înainte de Big Bang
Quincy Jones, omul care știut să facă totul mai bine decât oricine altcineva din divertisment. Producătorul lui Michael Jackson și al lui Frank Sinatra
Quincy Jones, omul care știut să facă totul mai bine decât oricine altcineva din divertisment. Producătorul lui Michael ...
Consumul de alcool la animale ar fi mai frecvent decât s-a crezut până acum
Consumul de alcool la animale ar fi mai frecvent decât s-a crezut până acum