Bill Gates' videnskabelige bidrag
Her i agurketiden kniber det lidt med egntlige nyheder, så jeg vil i stedet trække en 30 år gammel historie frem: Bill Gates' eneste publicerede videnskabelige artikel.
I 1978 studerede Bil Gates på Harvard. Han gennemførte aldrig sit studium, men inden han droppede skrev han sammen med sin vejleder Christos Papadimitriou en artikel om pandekageproblemet.
Problemet er som følgende: Du har en stabel pandekager, allesammen af forskellig størrelse. For at stakken skal se pæn ud, vil du gerne sortere dem, så de ligger i orden efter størrelse, med den mindste i top og den største i bund. Som værktøj har du en spatel, som du kan stikke ind mellem to vilkårlige pandekager og derefter vende hele toppen af stakken om. Denne operation kaldes et "flip".
Det er forholdsvis nemt at se, at man altid kan klare sig med 2N flip, hvis der er N pandekager: Man finder den største pandekage, der ikke ligger på sin plads, stikke rspatelen ind under den og flipper. Dernæst sætter man spatelen ind lige over den pandekage, som den skal ligge på, og flipper igen. Dermed er pandekagen kommet på plads.
Men kan det gøres bedre? Det var det spørgsmål, som Gates og Papadimitriou besvarede ved at finde en ny øvre grænse, som er (5N+5)/3, altså lidt over 1,666N.
Denne grænse holdt i mange år, indtil Hal Sudborough og hans studerende sidste år fandt en bedre grænse på 18/11N, altså lidt over 1,636N, hvilket han præsenterede på en workshop på DIKU til ære for Neil Jones, som var gået på pension. Det skal dog bemærkes, at denne grænse ikke er hård – der er formodninger om, at det kan gøres med maksimalt 3/2N flips, men det er ikke bevist.
Man kan diskutere den praktiske betydning af resultatet, men da det tog næsten 30 år at forbedre det, er det ikke noget helt skeløjet arbejde.
Om Torben MogensenKommentarer (9)
Nu kunne jeg jo være fræk og påstå at den eneste grund til Bill's succes på dette område er problemets manglende udbredelse ;-)
-
0 -
0
Eller det kunne også være at Bill Gates som har været verdens rigeste mand i 17 år og har et firma som har den software der er installert på 90% af alle computere måske er lidt klog...
-
0
-
0
Enten det eller brugte han nogle ulovlige og mafialignende metoder... Nej, vent blev hans firma ikke fundet skyldig i dette i et par retssager?
-
0
-
0
Nu udelukker brug af mafialignende metoder ikke at man er klog, erfaringsmæssigt nærmest tværtimod...
-
0
-
0
En meget stor del af al databehandling er sortering.
Bill Gates arbejde giver en bedre måde at sortere på.
Ikke helt uinteressant.
-
0
-
0
De nævnte tal er antal præfiksvendinger (flip), som ikke er et direkte mål for køretiden. For det første kan der været et ubegrænset antal læsninger af data mellem hvert flip, og for det andet kan et flip næppe implementeres i konstant tid uden at det går ud over tilgangstiden til elementerne.
Så der er ikke tale om en praktisk sorteringsalgoritme -- medmindre dit hardware er en spatel og en stak pandekager.
-
0
-
0
Så der er ikke tale om en praktisk sorteringsalgoritme -- medmindre dit hardware er en spatel og en stak pandekager.
Deraf spørgsmålet fra Jørgen i første kommentar :o)
-
0
-
0
Deres artikel slutter med
Note added in proof Ervin Gyoriof the Hungarian Academy of Sciences and Gy6rgy Tunln of J. Atilla University have independently discovered a proof of Theorem 1. Their algorithm and proof are essentially the same as ours.
Hvad man skal ligge i det lader jeg stå frit ;o)
-
0
-
0
