Gödelova cena

Gödelova cena je vedecké ocenenie udeľované každoročne od roku 1993 za najlepšie vedecké články z oblasti teoretickej informatiky. Cena je pomenovaná po rakúskom matematikovi a logikovi Kurtovi Gödelovi a udeľujú ju asociácie EATCS (European Association for Theoretical Computer Science) a ACM SIGACT (Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory). Súčasťou ceny je finančná odmena vo výške 5000 amerických dolárov.

Nositelia ceny
Rok	Meno/mená	Dôvod
1993	László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran a Charles Rackoff	za vývoj interaktívnych dôkazových systémov.
1994	Johan Håstad	za exponenciálny dolný odhad zložitosti Booleovských okruhov s konštantnou hĺbkou.
1995	Neil Immerman a Róbert Szelepcsényi	za Immermanovu-Szelepcsényiho vetu o uzavretosti triedy kontextových jazykov na komplement.
1996	Mark Jerrum a Alistair Sinclair	za prácu v oblasti markovovských reťazcov.
1997	Joseph Halpern a Yoram Moses	za definíciu formálneho pojmu "poznatok" v distribuovaných systémoch.
1998	Seinosuke Toda	za Todovu vetu, ktorá ukázala súvislosť medzi PP a PH zložitosťou.
1999	Peter Shor	za Shorov algoritmus na faktorizáciu čísel v polynomiálnom čase na kvantovom počítači.
2000	Moshe Y. Vardi a Pierre Wolper	za prácu v oblasti overovania modelov pomocou konečných automatov
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 vetu a jej aplikácie v oblasti zložitosti aproximácie.
2002	Géraud Sénizergues	za dôkaz, že problém ekvivalencie deterministických zásobníkových automatov je rozhodnuteľný.
2003	Yoav Freund a Robert Schapire	za algoritmus AdaBoost.
2004	Maurice Herlihy, Mike Saks, Nir Shavit a Fotios Zaharoglou	za aplikáciu topológie v teórii distribuovaných výpočtov.
2005	Noga Alon, Yossi Matias a Mario Szegedy	za základné výsledky v oblasti algoritmov na údajových prúdoch (streamoch).
2006	Maníndra Agravál, Neeraj Kayal a Nitin Saxena	za test prvočíselnosti AKS.
2007	Aleksandr Aleksandrovič Razborov a Steven Rudich	za tzv. prirodzené dôkazy.
2008	Shanghua Teng a Daniel Spielman	za tzv. zjemnenú analýzu algoritmov.
2009	Omer Reingold, Salil Vadhan a Avi Wigderson	za tzv. zig-zag súčin grafov.
2010	Sanjeev Arora a Joseph S. B. Mitchell	za algoritmus pre riešenie eukleidovského problému
2011	Johan Håstad	za zavedenie nových analytických metód v teórii aproximácie obťažnosti pri výpočte problémov
2012	Elias Koutsoupias, Christos Papadimitriou, Tim Roughgarden, Éva Tardos, Noam Nisan a Amir Ronen	každý za základný článok o algoritmické teórii hier

Externé odkazy

Oficiálna stránka ceny

Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.