Z Wikipedie, otevřené encyklopedie
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 .
Nositelé ceny
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
Obrázky, zvuky či videa k tématu Gödelova cena na Wikimedia Commons 