z Wikipédie, slobodnej encyklopédie
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
