O Prémio EATCS é um prémio atribuído pela European Association for Theoretical Computer Science (EATCS) a um investigador para homenagear a sua brilhante carreira em ciência da computação teórica .
O Prêmio EATCS é concedido anualmente desde 2000. Ele recompensa um pesquisador por um trabalho extenso e amplamente reconhecido em ciência da computação teórica ao longo de uma carreira científica. O prêmio é entregue por ocasião da conferência ICALP . É acompanhado por uma quantia de 1000 euros.
Ano | Destinatário | Local da conferência | Trabalho premiado |
---|---|---|---|
2021 | Toniann pitassi | Por suas contribuições para a teoria da complexidade , incluindo a complexidade da evidência , a introdução de novos modelos, o desenvolvimento de novas técnicas e o estabelecimento de novas conexões entre diferentes campos. O seu trabalho incide na aprendizagem e otimização informática , verificação e resolução de problemas SAT, a complexidade do circuito e a complexidade das comunicações e suas aplicações. | |
2020 | Mihalis Yannakakis | Por suas muitas e variadas contribuições para algoritmos, teoria da complexidade, otimização combinatória, bancos de dados e verificação. Em particular sobre as limitações da otimização linear , a introdução das classes de complexidade max-SNP (ver APX (complexidade) ) e PLS (en) , trabalho em torno do teorema PCP e trabalho fundamental na verificação de modelos . | |
2019 | Thomas Henzinger | ICALP Patras | Verificação formal e síntese de sistemas reativos , em tempo real e híbridos, e aplicação de métodos formais a sistemas biológicos. |
2018 | Noam Nisan | ICALP ( Praga ) | Teoria da complexidade ( complexidade da comunicação , aprendizagem, paralelismo, teoria da aleatoriedade ...) e teoria dos jogos algorítmicos |
2017 | Eva Tardos | ICALP ( Varsóvia ) | Algoritmos fortemente polinomiais, programação linear e algoritmo de projeto , de aproximação algoritmos , teoria dos jogos algorítmica . |
2016 | Dexter Kozen | ICALP ( Roma ) | Completude da lógica dinâmica proposicional, máquina de Turing alternada , lógica modal , álgebra de Kleene , complexidade das teorias algébricas reais, decomposição de Kozen-Landau no cálculo formal , semântica probabilística. Autor de livros didáticos fundamentais em ciência da computação teórica. |
2015 | Christos Papadimitriou | ICALP ( Kyōto ) | Algoritmos , teoria da complexidade , teoria dos jogos algorítmica , teoria de banco de dados , otimização , robótica . "Christos Papadimitriou combina um grande, influente e variado corpo de descobertas científicas com os dons de um professor inspirador e grande comunicador." |
2014 | Gordon plotkin | ICALP ( Copenhague ) | Semântica operacional estrutural (SOS), semântica denotacional , teoria de tipo, teoria de domínio e análise categórica, mais geralmente em teoria da prova , semântica de linguagens naturais, álgebras de processo . |
2013 | Martin Dyer | ICALP ( Riga ) | Algoritmos lineares no tempo para programas lineares em baixa dimensão, com aplicações em geometria computacional . Análise probabilística de algoritmos. Algoritmo de tempo polinomial randomizado para aproximar o volume de um objeto convexo de grande dimensão. Complexidade de problemas de satisfação de restrição de contagem . |
2012 | Moshe Vardi | ICALP ( Warwick ) | Aplicação da lógica à ciência da computação, teoria do banco de dados, teoria dos modelos finitos, modelagem do conhecimento em sistemas multiagentes, verificação de modelos . Moshe Vardi é co-autor de Reasoning about Knowledge and Finite Model Theory and its Applications . |
2011 | Boris Trakhtenbrot | ICALP ( Zurique ) | Um dos fundadores da informática teórica, visionário, pioneiro em várias direções: na teoria da complexidade , o “teorema do gap” ou “teorema do gap”; na teoria dos modelos, o teorema Trakhtenbrot . Trakhtenbrot por um lado, J. Büchi e C. Elgot por outro lado demonstram independentemente a equivalência entre autômatos finitos e lógica monádica de segunda ordem (MSO), um resultado chamado teorema de Büchi-Elgot-Trakhtenbrot. |
2010 | Kurt mehlhorn | ICALP ( Bordéus ) | Autor de vários livros. Contribuições fundamentais em estruturas de dados , geometria computacional , álgebra , computação paralela , tecnologia VLSI e teoria da complexidade , otimização combinatória e algoritmos de gráfico , complexidade de comunicação . Criação com Stefan Näher da LEDA . |
2009 | Gerard Huet | ICALP ( Rodes ) | Unificação de termos digitados do cálculo Lambda . Teoria dos tipos . Reescrever e completar Knuth-Bendix . Assistente de prova Coq . |
2008 | Leslie Valiant | ICALP ( Reykjavik ) | Introdução da aula de complexidade #P , teorema Vazirani-Valiant, aprendizagem de máquina , em particular aprendizagem PAC , algoritmos holográficos. Famílias de autômatos pushdown determinísticos ; computação distribuída e paralela . |
2007 | Dana S. Scott | ICALP ( Wroclaw ) | Teoria dos autômatos , semântica das linguagens de programação , lógica modal , topologia e teoria das categorias . Sua colaboração com Christopher Strachey lançou as bases para abordagens modernas à semântica das linguagens de programação . |
2006 | Mike Paterson | ICALP ( Veneza ) | Desenho e análise de algoritmos e teoria da complexidade . Teoria das linguagens , algoritmos distribuídos, teoria dos autómatos . Coautor de livro sobre grupos automáticos . Conhecido como o inventor dos jogos, como as minhocas ou brotos de Paterson . |
2005 | Robin Milner | ICALP ( Lisboa ) | Prova de lógica para funções computáveis ou teoremas LCF . Linguagem de programação ML com inferência de tipos polimórficos e um sistema de tratamento de exceções tipadas. Calculus of Communicating Systems (CCS) para a análise de sistemas concorrentes . pi-cálculo e bisimulação . |
2004 | Arto Salomaa | ICALP ( Turku ) | linguagens formais , teoria dos autômatos , combinatória de palavras e criptografia . Ele é, em particular Maurice Nivat e Grzegorz Rozenberg , um dos fundadores da ciência da computação teórica europeia. Autor e editor de vários livros, iniciador e facilitador em todos os níveis de pesquisa. |
2003 | Grzegorz Rozenberg | ICALP ( Eindhoven ) | Teoria das linguagens formais e autómatos , reescrita de grafos, sistemas de Lindenmayer , redes de Petri , teoria dos traços . Ele foi o promotor e arauto da computação natural e da computação de DNA , deu seu nome atual e esboçou seus contornos. Ele é o fundador do International Journal on Natural Computing . Autor e editor de vários tratados. |
2002 | Maurice Nivat | ICALP ( Málaga ) | Com Arto Salomaa e Grzegorz Rozenberg , um dos fundadores da informática teórica europeia. Ele se tornou o porta-estandarte da ciência da computação no sentido de Marcel-Paul Schützenberger . Teoria das linguagens e autômatos, semântica das linguagens de programação, ele está na origem de uma importante escola francesa de ciência da computação teórica. |
2001 | Corrado Böhm | ICALP ( Creta ) | Cientista da computação e lógico, autor do teorema do programa estruturado em “programação sem Goto”. Lambda-cálculo , incluindo a comparação de β-conversão e η-conversão . Máquina abstrata CUCH. Codificação Böhm-Berarducci. Um dos fundadores da escola italiana de ciência da computação teórica e programação funcional. |
2000 | Richard Karp | ICALP ( Genebra ) | Classe de problemas NP-completos . Numerosos algoritmos: algoritmo de Edmonds-Karp para o problema de fluxo máximo ; Algoritmo de Hopcroft-Karp para um problema de acoplamento ; o teorema de Karp-Lipton na teoria da complexidade; Algoritmo de pesquisa do padrão Rabin-Karp . Teste de primalidade probabilística. Um pilar da ciência da computação teórica. |
" Página de prêmios EATCS " , no EATCS