Gödelova cena
Gödelova cena je vědecké ocenění udělované od roku 1993 každoročně za nejlepší odborné články z oblasti teoretické informatiky.
Uděluje ji European Association for Theoretical Computer Science a Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory. Součástí ceny je finanční odměna ve výši 5000$. Cena je pojmenována po rakouském matematikovi a logikovi Kurtu Gödelovi.
| Rok | Jméno | Zdůvodnění |
|---|---|---|
| 1993 | László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran a Charles Rackoff | za vývoj interaktivních důkazových systémů |
| 1994 | Johan Håstad | za exponenciální odhad složitosti Booleových okruhů s konstantní hloubkou |
| 1995 | Neil Immerman a Róbert Szelepcsényi | za Immermanovu-Szelepcsényiho větu |
| 1996 | Mark Jerrum a Alistair Sinclair | za práci v oblasti markovových řetězců |
| 1997 | Joseph Halpern a Yoram Moses | za definici formálního pojmu "poznatek" v distribuovaných systémech |
| 1998 | Seinosuke Toda | za Todovu větu |
| 1999 | Peter Shor | za Shorův algoritmus na faktorizaci čísel v polynomiálním čase na kvantovém počítači |
| 2000 | Moshe Y. Vardi a Pierre Wolper | za práci v oblasti ověřování modelů pomocí konečných automatů |
| 2001 | Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Radžív Mótvání, Shmuel Safra, Madhu Sudan a Mario Szegedy | za PCP větu a její aplikace v oblasti složitosti aproximace |
| 2002 | Géraud Sénizergues | za důkaz, že problém ekvivalence deterministických zásobníkových automatů je rozhodnutelný |
| 2003 | Yoav Freund a Robert Schapire | za algoritmus AdaBoost. |
| 2004 | Maurice Herlihy, Mike Saks, Nir Shavit a Fotios Zaharoglou | za aplikaci topologie v teorii distribuovaných výpočtů |
| 2005 | Noga Alon, Yossi Matias a Mario Szegedy | za základní výsledky v oblasti algoritmů na datových proudech (streamech) |
| 2006 | Maníndra Agravál, Neeraj Kayal a Nitin Saxena | za test prvočíselnosti AKS. |
| 2007 | Aleksandr Aleksandrovič Razborov a Steven Rudich | za tzv. přirozené důkazy |
| 2008 | Shanghua Teng a Daniel Spielman | za tzv. zjemněnou analýza algoritmů |
| 2009 | Omer Reingold, Salil Vadhan a Avi Wigderson | za tzv. zig-zag součin grafů |
| 2010 | Sanjeev Arora a Joseph S. B. Mitchell | za algoritmus při řešení eukleidovského problému |
| 2011 | Johan Håstad | za zavedení nových analytických metod v teorii aproximace obtížnosti při výpočtu problémů |
| 2012 | Elias Koutsoupias, Christos Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan a Amir Ronen | za základní články o algoritmické teorii her |
| 2013 | Antoine Joux, Dan Boneh a Matthew K. Franklin | za pokrok v kryptografii |
| 2014 | Ronald Fagin, Amnon Lotem a Moni Naor | za návrh nových algoritmů |
| 2015 | Daniel A. Spielman a Shang-Hua Teng | |
| 2016 | Stephen Brookes a Peter W. O'Hearn |
Externí odkazy
Obrázky, zvuky či videa k tématu Gödelova cena na Wikimedia Commons - Oficiální stránka ceny
