Auszeichnung: Der Turing Award geht an Avi Wigderson
Die Association for Computing Machinery (ACM) hat bekanntgegeben, dass der Turing Award dieses Jahr an den Informatiker und Mathematiker Avi Wigderson verliehen wird. Wigderson ist der Professor an der School of Mathematics des Institute for Advanced Studies an der Princeton Universität in New Jersey, USA. Den Preis bekommt er für seine "wegweisenden Erkenntnisse über Zufälligkeit" und sein Lebenswerk in der theoretischen Informatik.
Mit seiner Arbeit formte Wigderson das Verständnis für die Rolle von Zufälligkeit in der Komputation neu und trieb damit die Theory of Computation (Theorie der Berechnung/Komputation) weiter voran. Alan Turing, der Namensgeber des Preises, gilt als einer der Pioniere in diesem Forschungsfeld, genauso wie John von Neumann und Kurt Gödel, die beide neben Albert Einstein Professuren am Institute for Advanced Studies in Princeton inne hatten.
Komputation ist ein grundlegender Begriff – auch außerhalb von Computern
Dem ZDNet(öffnet im neuen Fenster) sagte Widgerson "Komputation ist ein wirklich grundlegender Begriff." Und weiter: "Es sind nicht nur Algorithmen in Computern: Everything computes (auf Deutsch etwa: Alles berechnet)."
Widgerson gab auch ein Beispiel für diese Aussage: "Wenn Sie eine Muschel am Strand sehen mit einem bemerkenswerten Muster, wurde dieses durch äußerst einfache Schritte berechnet: Sie wuchs aus einem Korn. Lokal haben diese Körner benachbarte Körner berechnet und verbunden." Dieser "einfache Prozess" , weiterentwickelt, bringe einige erstaunliche Muster hervor.
Computer sind deterministisch, die Natur enthält Zufälligkeit
Wigderson und seine Kollegen verwendeten diese Untersuchungen der Zufälligkeit, um das Verständnis von der Unterscheidung zwischen effizienter und nicht-effizienter Berechenbarkeit voranzutreiben. In der Welt der Algorithmen bedeutet dies Berechenbarkeit in polynomialer statt exponentialer Zeit. Im Zuge der drei in der Auszeichnung genannten Paper konnten die Forscher nachweisen, dass jeder probabilistische Algorithmus mit polynomieller Zeit zu einem deterministischen Algorithmus mit ebenfalls polynomieller Zeit entwickelt werden kann. Dies bedeutet, der Zufall kann eliminiert werden und der Algorithmus wird durch deterministische Maschinen berechenbar.
- Anzeige Hier geht es zu NVIDIA-Grafikkarten bei Alternate Wenn Sie auf diesen Link klicken und darüber einkaufen, erhält Golem eine kleine Provision. Dies ändert nichts am Preis der Artikel.