Computerwetenschappelijke onderzoekers van de Universiteit van Kopenhagen en de Technische Universiteit van Denemarken (DTU) dachten dat ze vijf jaar verwijderd waren van het oplossen van een wiskundig raadsel uit de jaren tachtig. In werkelijkheid, en zonder het te weten, ze hadden het probleem bijna opgelost en hadden net een groot deel van de oplossing weggegeven in een onderzoeksartikel. De oplossing kan worden gebruikt om de telefoons en computers van morgen te verbeteren.

Jacob Holm en Eva Rotenberg

Een echte hersenkraker. Zo kan men dit wiskundige probleem veilig beschrijven in het vakgebied van de grafentheorie. Twee wiskundigen van de afdeling Computerwetenschappen van de Universiteit van Kopenhagen en DTU hebben nu een probleem opgelost waarmee de snelste en slimste ter wereld al sinds de jaren '80 worstelen.

De twee computerwetenschappers, Universitair docent Jacob Holm van UCPH en universitair hoofddocent Eva Rotenberg van DTU gaven hun oplossing bijna weg in de zomer van 2019, na het indienen van een onderzoeksartikel dat de voorloper werd van het artikel waarin ze uiteindelijk het wiskundige raadsel hebben opgelost.

"We hadden het bijna opgegeven om het laatste stuk te pakken en het raadsel op te lossen. We dachten dat we een klein resultaat hadden, een die interessant was, maar loste het probleem op geen enkele manier op. We vermoedden dat er nog vijf jaar werk zou zijn, op zijn best, voordat we de puzzel zouden kunnen oplossen, " legt Jacob Holm uit, die deel uitmaakt van BARC, de sectie algoritmen van de afdeling Computerwetenschappen van het UCPH.

Het probleem met de drie hulpprogramma's

1913, een voorloper van het nu opgeloste wiskundige raadsel werd gepubliceerd in Het Strand Magazine als "The Three Utilities Problem". Het zorgde ervoor dat de lezers van het tijdschrift hun hoofd krabden en nadenken. Bij het probleem, elk van de drie huisjes moet water hebben, gas en elektriciteit, terwijl de "lijnen" tussen de huizen en het water, elektriciteit en gas mogen elkaar niet kruisen, wat niet kan.

Een oplossing tussen de regels

Simpel gezegd, de puzzel gaat over hoe je een aantal punten in een grafiek kunt verbinden zonder dat de lijnen die ze verbinden elkaar kruisen. En hoe, met een wiskundige berekening - een algoritme - kunt u wijzigingen aanbrengen in een uitgebreid "grafiekennetwerk" om ervoor te zorgen dat er geen lijnen elkaar kruisen zonder dat u helemaal opnieuw hoeft te beginnen. Eigenschappen die kunnen worden gebruikt voor, onder andere, het bouwen van immense wegennetwerken of de kleine ingewanden van computers, waar elektrische circuits op printplaten elkaar niet mogen kruisen.

Jacob Holm is al sinds 1998 geïnteresseerd in het wiskundige raadsel. maar het antwoord werd pas onthuld terwijl de twee onderzoekers hun reeds ingediende onderzoeksartikel aan het doorlezen waren. Ondertussen, de onderzoekers hoorden over een nieuwe wiskundige techniek waarvan ze zich realiseerden dat deze op het probleem kon worden toegepast.

"Tijdens het lezen van ons onderzoeksartikel, we realiseerden ons plotseling dat de oplossing voor onze ogen lag. Onze volgende reactie was 'oh nee - we hebben onszelf in de voet geschoten en de oplossing weggegeven, ', zegt universitair hoofddocent Eva Rotenberg van DTU.

Over grafentheorie

Een grafiek is een zeer eenvoudige constructie die wordt gebruikt om dingen te modelleren die kunnen worden beschreven als objecten en de verbindingen daartussen. Grafentheorie is zowel een gebied van wiskunde als een belangrijk hulpmiddel in de informatica.

In deze context, een grafiek kan worden geïllustreerd met een diagram dat bestaat uit een aantal punten (knopen, hoekpunten) geassocieerd met een aantal lijnen (randen). Elke rand wordt geïllustreerd als een lijn (of gebogen stuk) met knooppunten als twee eindpunten.

Over de oplossing

Er zijn twee soorten updates in dynamische grafieken:men kan een rand verwijderen en u kunt een nieuwe rand invoegen. Deze twee handelingen moeten door de gebruiker worden uitgevoerd, terwijl een algoritme te allen tijde de tekening van het netwerk bijhoudt. Dit is het algoritme waar de onderzoekers het recept voor hebben gevonden.

Kan worden gebruikt voor computerelektronica;

Dit is het moment waarop de twee onderzoekers bezig waren met het schrijven van het onderzoekspaper en het aan elkaar knopen van losse eindjes om het raadsel op te lossen waar Holm sinds 1998 met tussenpozen aan werkte.

"We hebben non-stop aan het artikel gewerkt, gedurende vijf tot zes weken. En, het vulde uiteindelijk meer dan 80 pagina's, ', zegt Eva Rotenberg.

Gelukkig, niemand versloeg hen voor de oplossing en de twee onderzoekers konden hun resultaten presenteren op de belangrijkste theoretische computerwetenschappelijke conferenties, die in Chicago zouden worden gehouden, maar werd uiteindelijk virtueel vastgehouden.

Dus, waar kan de oplossing voor dit wiskundige raadsel voor worden gebruikt? De twee onderzoekers weten het niet zeker, maar ze hebben een paar suggesties.

"Ons onderzoek is fundamenteel onderzoek, dus we weten zelden waarvoor het uiteindelijk zal worden gebruikt. Zelfs vanaf het begin we vinden toepassingen moeilijk voor te stellen, " zegt Jacob Holm, wie voegt eraan toe, "Het ontwerp van microchips en printplaten, gevonden in alle elektronica, zou een gebied kunnen zijn waar ons resultaat uiteindelijk wordt gebruikt. Bij het tekenen van draden op een printplaat, ze mogen elkaar nooit kruisen. Anders, kortsluiting zal optreden. Hetzelfde geldt voor microchips, die miljoenen transistors bevatten en waarvoor men een grafiektekening moet hebben."