Efter kapløb med tiden: Danske forskere løser gammel matematisk gåde fra 1980'erne

Illustration: Københavns Universitet

En gammel matematisk gåde fra 1980'erne er blevet løst af to danske forskere, efter de med fuld fart over computertasterne skyndte sig at skrive en 40 tætskrevne sider lang forskningsartikel på blot fem-seks uger. Tiden var knap, for de havde nemlig allerede ved en fejl offentliggjort ‘nøglen’ til at løse gåden.

Det skriver Datalogisk Institut på Københavns Universitet i en pressemeddelelse.

Før løsningen officielt blev præsenteret i deres seneste forskningsartikel, havde Jacob Holm, datalog og adjunkt ved Københavns Universitet (KU), og Eva Rotenberg, datalog og lektor ved DTU Compute, forsøgt at løse problemet sidste år i en tidligere artikel.

»Vi havde næsten opgivet at komme det sidste stykke og løse gåden. Vi tænkte, at vi havde et lille resultat, der var interessant, men som på ingen måde løste problemet. Vi gættede på, at der ville være fem års arbejde endnu, før vi i bedste fald kunne løse gåden,« fortæller Jacob Holm, der har arbejdet on-off på problemet siden 1998, i pressemeddelelsen.

En meget forsimplet forklaring: Gåden handler om, hvordan man kan forbinde en række punkter i en graf, uden at stregerne krydser hinanden, og derudover hvordan man med en algoritme kan håndtere, at en bruger ændrer forbindelserne i et kompliceret graf-netværk uden risiko for, at nogle linjer begynder at krydse over hinanden, medmindre sådanne kryds er uundgåelige.

Efter en grundig gennemlæsning af sidste års tekst opdagede forskerne, at en velkendt matematisk teknik kunne bruges til at løse problemet, og derfor skulle det gå stærkt med at skrive igen, inden andre gjorde samme opdagelse. Ifølge Eva Rotenberg viste det sig, at teknikken ikke kunne stå alene, og derfor måtte forskerne opfinde nye teknikker, som er beskrevet i forskningsartiklen, for at komme i mål.

Illustration: Københavns Universitet

Algoritmer holder styr på kanterne

Forskerne har udviklet en algoritme, der kan ‘holde styr’ på, at kanterne så vidt muligt ikke krydser hinanden i et graf-netværk, selvom man laver ændringer i det. Hvis man forsøger at lave en ændring i netværket, som ikke kan lade sig gøre, uden at kanterne krydser, så kan algoritmen gøre opmærksom på det.

Det er grundforskning, fortæller Jakob Holm, og derfor er der ikke et helt præcist svar på, hvad man egentlig kan bruge løsningen til i praksis, men han har alligevel nogle ideer:

»Men design af mikrochips og printplader, som findes i al vores elektronik, kan være et område, hvor man kan bruge vores resultat. Når man tegner ledningerne på en printplade, så er de pinedød nødt til at ligge sådan, at de ikke krydser hinanden, for ellers får man kortslutninger mellem tingene. Det samme gælder mikrochips, som rummer millioner af transistorer, som man bliver nødt til at have en graf-tegning over,« fortæller han i pressemeddelelsen.

Forskerne har netop talt ved konferencen ‘Symposium on Theory of Computing’ (STOC), der blev afholdt virtuelt grundet corona, hvor de præsenterede gådens løsning, der måske kan være med til at forbedre fremtidens elektronik - og som de næsten forærede væk.

sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først

Jo det er rigtigt nok, men jeg tror at algoritmen har sin eksistensberettigelse fordi det er interessant at sikre at man har den bedst mulige 2D routing muligt, før man tilføjer endnu et lag. Tilsvarende er den interessant i andre real world scenarier, hvor der f.eks. bygges veje eller anden primært overordnet 2D infrastruktur.

Kan man i enkelte tilfælde spare at bygge en bro uden at omvejen bliver for stor, kan det være interessant, specielt når der skal designes helt nye bydele i eksisterende infrastruktur.

Det kan måske også bruges i rute planlægning ved udrykningskørsler eller andre slige situationer, hvor man ønsker at undgå at krydse bestemte veje.

  • 17
  • 0

Nej, det løser ikke det grundlæggende problem. Og der er masser af steder hvor "gennemplettering" som på en printplade, ikke er mulig. F.eks. kompliceres chip design væsentlig hvis niveauet af vias øges.

Enig i det.

Faktisk er det er i næsten alle forhold her i verden det mest effektive, hvis man kan løse sine udfordringer så "tidligt" i systemerne som muligt fremfor at bygge nye fix ovenpå. Begrænse støj i stedet for støjdæmpning, begrænse CO2 i stedet for CO2-fangst, forebygge sygsomme i stedet for at behandle. Det kan ikke altid lade sig gøre, men det bør altid være den første overvejelse. Skattesystemet med dets utallige lappeløsninger er et eksempel på, hvad den modsatte strategi kan føre til af komplicitet.

  • 13
  • 0

Udover de gode argumenter der ellers er brugt i tråden, så bliver det dyrere at producere printpladerne jo flere lag de har. Det har nok en del at sige rent økonomisk for f. eks samsung hvis der kan spares et lag i alle de printplader de porducerer.

Og jeg ved godt at et lag i en printplade ikke fylder ret meget, men i f.eks telefoner hvor der er en enorm kamp om at lave dem så tynde så muligt har det nok også interesse at spare på lagene.

  • 8
  • 0

Som jeg forstår de første minutter af videoen, handler dette ikke om at løse et ellers uløseligt problem, men om at reducere beregningstiden for datasæt med mange noder. Så hvis fx teknikernes computer har været på overarbejde når der skulle rykkes rundt på designet i en microchip, bliver beregningstiden nu Væsentligt kortere. Man rykker til poly-logaritmic time. Det er især nyttigt når man laver realtime-beregninger på store datasæt.

  • 2
  • 0

Ved printdesign er forbrugt areal ofte et større problem end krydsning af baner ligesom andre forhold som capacitiv og induktiv mistilpasning gør det umuligt at bruge lange baner for at undgå vias. Løsningen vil utvivlsomt alligevel være til stor hjælp for printdesignere og mange andre områder.

  • 1
  • 0

Ved printdesign er forbrugt areal ofte et større problem end krydsning af baner ligesom andre forhold som capacitiv og induktiv mistilpasning gør det umuligt at bruge lange baner for at undgå vias. Løsningen vil utvivlsomt alligevel være til stor hjælp for printdesignere og mange andre områder.

Håber snart der kommer et printudlægningsprogram som udnytter princippet. Selv manuel routing tror jeg bliver nemmere. Det, at få svarene hurtigt på resultatet af en flytning, er alfa og omega ved manuel routing.

Der findes desuden ikke mange printudlægningsprogrammer som kan optimere routingen i et lag.

Måske kan teknikken også bruges i free-style routers. Jeg har aldrig prøvet at bruge sådan en router, men jeg syntes resultaterne ser cool ud! Der påstås også, at de har bedre støjegenskaber, fordi at støjen "flades ud". Og transmissionslinjer har ikke skarpe knæk - det gør de ikke får samme støjspikes når de går om hjørner.

Her er et par eksempler her på noget routing:

https://en.wikipedia.org/wiki/TopoR#/media...

https://en.wikipedia.org/wiki/TopoR#/media...

BGA routing: https://wiki2.org/en/TopoR#/media/File:Top...

  • 0
  • 0

Her har vi et par meget kløgtige mennesker, der har kombineret talent og flid og løst et spændende matematisk problem.

Skal vi ikke kippe med hatten, inden der gerådes fuldstændig i inferiør printpladesnak?

  • 6
  • 0

Nu er det jo Jakob Holm selv, der nævner printplader, som et område, der måske kan drage fordel af den matematiske løsning omtalt her. Hvorfor det giver mening at påpege inferiøre problemer, som er velkendte for printdesignere; men åbenbart ikke for Jakob Holm. Nogle bidragydere til debatten synes også at have begrænset kendskab til problemerne ved printdesign, som jeg derfor beskedent påpeger. Det gør ikke matematisk grundforskning mindre værdifuld hvorfor hattekipning er på sin plads, omend debatsporet bliver noget udpint, hvis kipning er det eneste anerkendte bidrag her.

  • 1
  • 0

Ved printdesign er forbrugt areal ofte et større problem end krydsning af baner ligesom andre forhold som capacitiv og induktiv mistilpasning gør det umuligt at bruge lange baner for at undgå vias. Løsningen vil utvivlsomt alligevel være til stor hjælp for printdesignere og mange andre områder.

Det vigtigste for at opnå et lille areal er oftere placeringen af komponenterne, end selve udlæget. Afhængigt af teknologien, så kan gennempletteringer optage plads, og derfor være en fordel at undgå. Jeg har endnu ikke set programmer, der kan lave en fornuftig komponentplacering automatisk. Måske kan algoritmen også hjælpe her da krydsninger tager en del plads og medfører et mindre regulært layout, hvor busser ikke føres parallelt.

  • 0
  • 0
Bidrag med din viden – log ind og deltag i debatten