Gå til hovedindhold
Version2 it for professionelle
Forsiden

Hovedmenu

  • It-nyheder
  • Blogs
  • It-job
  • It-firmaer
  • Whitepapers
  • Opret bruger
  • Log ind
Du kan logge ind med din e-mail-adresse
Der er forskel på store og små bogstaver i adgangskoden.
Glemt adgangskode?
Se kommentarer (9)
Emner

Bill Gates' videnskabelige bidrag

Af Torben Mogensen 28. juli 2008 kl. 10:05

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.

Send Tweet
Udskriv
Billede af Torben MogensenOm Torben Mogensen

Kommentarer (9)

Opret en konto eller log ind for at følge indhold på Version2 - og bliv opdateret via e-mail eller rss

Følg kommentarer
Jørgen Henningsen 28. jul. 2008 - 12.03
 
Hmm

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 ;-)

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Henrik Eiriksson 28. jul. 2008 - 14.51
 
Re: Hmm

Bill har garanteret hugget algoritmen fra Rasmus Klumps mor ;-)

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Lasse Borchert 28. jul. 2008 - 18.52
 
Eller

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...

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Jarle Knudsen 29. jul. 2008 - 10.13
 
Re: Eller

Enten det eller brugte han nogle ulovlige og mafialignende metoder... Nej, vent blev hans firma ikke fundet skyldig i dette i et par retssager?

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Julian Hollingbery 29. jul. 2008 - 11.36
 
Re: Eller

Nu udelukker brug af mafialignende metoder ikke at man er klog, erfaringsmæssigt nærmest tværtimod...

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Michael Deichmann 29. jul. 2008 - 21.46
 
Sortering

En meget stor del af al databehandling er sortering.
Bill Gates arbejde giver en bedre måde at sortere på.
Ikke helt uinteressant.

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Torben Mogensens billede
Torben Mogensen 30. jul. 2008 - 11.46
 
Re: Sortering

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.

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Martin Hansen 30. jul. 2008 - 20.31
 
Re: Sortering
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)

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer
Martin Hansen 30. jul. 2008 - 20.42
 
sjov slutning

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)

  • Stem op 0
  • Stem ned 0
  • Log ind eller opret en konto for at skrive kommentarer

Tilføj kommentar

Opret en konto eller log ind for at følge indhold på Version2 - og bliv opdateret via e-mail eller rss

Følg kommentarer
Log ind herunder eller opret en bruger for at skrive kommentarer
Du kan logge ind med din e-mail-adresse
Der er forskel på store og små bogstaver i adgangskoden.
Glemt adgangskode?

Seneste nyt

Danske internetudbydere nægter at blokere 12 pokersites

Udgivet 24. maj 13.58Opdateret 24. maj 13.58

Dokumentation: Her er Spillemyndighedens krav - og 12 ulovlige pokersider

Udgivet 24. maj 13.58Opdateret 24. maj 13.58

Ny blog: Offentlige it-projekter set indefra

Udgivet 24. maj 13.19Opdateret 24. maj 13.30

De 170 fyrede hos IBM Danmark får 30.000 kroner i hånden

Udgivet 24. maj 12.19Opdateret 24. maj 12.19

Google vinder patentsagen om Android: Brød ikke Oracles Java-patenter

Udgivet 24. maj 11.30Opdateret 24. maj 11.30

Flere it-nyheder »

Tilmeld dig Version2's it-nyhedsbrev og vind den nye iPad.

Seneste debat

  1. Meego-afløseren Tizen klar til at tage kampen op med Android

    9 comments.
    Last update 8 minutter 3 sekunder
    Skrevet af Dennis Krøger
  2. Oracle tabte, vandt Google Java ?

    13 comments.
    Last update 26 minutter 44 sekunder
    Skrevet af Casper Bang
  3. Das NemID trojaner - paranoia eller rettidig omhu?

    25 comments.
    Last update 28 minutter 11 sekunder
    Skrevet af Gert Madsen
  4. HTML5 – det nye sort?

    16 comments.
    Last update 32 minutter 43 sekunder
    Skrevet af Jesper Brunholm
  5. GOTO - programming with the stars (F#)

    8 comments.
    Last update 43 minutter 4 sekunder
    Skrevet af Torben Mogensen
  6. DanID: Du kan sagtens bruge NemID på MacOS X 10.5

    29 comments.
    Last update 55 minutter 10 sekunder
    Skrevet af Thue Kristensen
  7. Danske HP-ansatte er fyringstruede: Indkaldt til stormøde

    1 comment.
    Last update 1 time 4 minutter
    Skrevet af Martin R. Ehmsen
  8. Google vinder patentsagen om Android: Brød ikke Oracles Java-patenter

    1 comment.
    Last update 1 time 42 minutter
    Skrevet af Thomas Løcke

Mere debat »

Information

  • Kontakt redaktionen
  • Job- og annoncesalg
  • Teknisk support
  • Om Version2
  • Brugerbetingelser
  • Privatlivspolitik

Aktuelle emner

  • Agil udvikling
  • Android
  • Bruttolønsordning
  • Business Intelligence
  • Cloud computing
  • Download Windows 8
  • HTML5
  • Harddisk-priser
  • IE9
  • Intranet
  • It-sikkerhed
  • Kindle Fire
  • Multimedieskat
  • NemID
  • OS X Mountain Lion
  • Open source CMS
  • Projektledelse
  • Scrum
  • Sharepoint intranet
  • Storage
  • Ubuntu 11.10
  • Virtualisering
  • Windows 8
  • Windows Phone 7
  • iOS 5
  • iPhone 4S

Tjenester

  • Android-app
  • iPhone-app
  • RSS-feeds
Følg @version2dk
Tilmeld dig Version2's it-nyhedsbrev og vind den nye iPad.

Version2 udgives af

  • Mediehuset Ingeniøren A/S work Skelbækgade 4 1717 København V
  • Tlf. work 33265300