Wiskundemeisjes

De beste algoritmes van de 20ste eeuw

Ik ben dol op het maken van top 10-lijstjes, maar ik was nooit op het idee gekomen om een lijst met mijn favoriete algoritmes te maken (ik heb trouwens wel een top 3 van favoriete bewijsmethodes). Jack Dongarra en Francis Sullivan kwamen wel op dat idee en maakten een lijst van de beste algoritmes van de 20ste eeuw, zie deze pdf. Klassiekers als Monte Carlo, fast Fourier transform en (wie gebruikt hem niet) quicksort worden genoemd. Ik kan me min of meer vinden in de genoemde algoritmes, maar er is natuurlijks niets leuker dan verzinnen welke dingen ook op de lijst hadden gemoeten. Ik mis bijvoorbeeld het LLL-algoritme, het prachtige basis reductie algoritme dat door Jan en alleman gebruikt wordt.
(Ionica)

9 reacties op “De beste algoritmes van de 20ste eeuw”

1. Arjen:
   donderdag 23 november 2006 om 22:20

   De meeste algoritmen in het artikel hebben wel een beetje een informatica-smaakje (niet dat daar iets mis mee is). Wie wat meer algebraische algoritmen wil kan inderdaad moeilijk om LLL heen, al is het feitelijke algoritme naar mijn smaak nnu niet echt bijzonder.

   Ik ben zelf erg gecharmeerd van Schoof's algoritme voor het bepalen van het aantal punten op een elliptische kromme. Bijzonder fraai is de truc om een geheel getal te bepalen door het vinden van een onder- en bovengrens en vervolgens het getal uit te rekenen modulo kleine priemen. Met de Chinese reststelling vind je dan wat het getal is.

   Ook de deterministisch polynomiale priemtest verdient een speciale vermelding. Het is toch wonderbaarlijk dat het zo eenvoudig is om vast te stellen of een getal delers heeft, zonder ook maar iets over die delers te weten te komen.

2. Franklin:
   vrijdag 24 november 2006 om 03:05

   Ik mis zelf ook een algoritme in die top 10, en wel het kortste pad-algoritme van Dijkstra. :)

3. Eline:
   vrijdag 24 november 2006 om 09:42

   Nu ben ik natuurlijk wel heel benieuwd naar die top drie van bewijsmethodes geworden.

4. Ionica:
   vrijdag 24 november 2006 om 09:50

   Ionica's bewijsmethode top drie:
   1. Volledige inductie (ah, kon dat maar altijd),
   2. Uit het ongerijmde (ook fijn),
   3. Net zo lang doorbikkelen tot het eindelijk lukt (meest gebruikt).

5. Eline:
   zaterdag 25 november 2006 om 08:17

   Eline's variatie op Ionica’s bewijsmethode top drie:
   1. Een goddelijke ingeving (ah, kon dat maar altijd),
   2. Volledige inductie (ook fijn),
   3. Uit het ongerijmde (ook handig).

   ;-)

6. Jan B:
   zondag 26 november 2006 om 15:59

   Hallo, beetje off-topic hier maar ik zou graag een wiskundig probleem willen droppen maar zie nergens op jullie site een mogelijkheid daartoe. Of is dat überhaupt ook helemaal niet de bedoeling? Hopenlijk berichtje hierover?
   Mooie site overigens; prima gedaan.

7. Camiel:
   zondag 26 november 2006 om 21:22

   Misschien kun je het hier proberen.

8. wiskundemeisjes:
   maandag 27 november 2006 om 07:48

   Of je kunt ons een email sturen!

9. han:
   maandag 27 november 2006 om 13:18

   Ik ben benieuwd naar het wiskundig probleem.
   ps.
   7:48?
   dit wiskundemeisje is al vroeg uit de veren!

Plaats een reactie