Andrew Yao
| Naissance | |
|---|---|
| Nationalités |
américaine (jusqu'en ) chinoise |
| Formation |
Université Harvard Université de l'Illinois à Urbana-Champaign Université nationale de Taïwan Taipei Municipal Chien Kuo High School (en) |
| Activités | |
| Conjoint |
| A travaillé pour | |
|---|---|
| Membre de |
Association for Computing Machinery () Académie américaine des sciences (- Académie américaine des sciences () Division des sciences informatiques de l'Académie chinoise des sciences (d) () Académie américaine des arts et des sciences Academia sinica |
| Directeur de thèse |
Chung Laung Liu (en) |
| Site web | |
| Distinctions |
Prix Turing () Liste détaillée Prix George-Pólya () Bourse Guggenheim () ACM Fellow () Prix Knuth () Prix Turing () Docteur honoris causa de l'université chinoise de Hong Kong () Docteur honoris causa de l'université de Waterloo () IACR Fellow () Prix de Kyoto en technologies avancée () Docteur honoris causa de l'université polytechnique de Hong Kong |
Andrew Chi-Chih Yao (chinois : 姚期智; pinyin : Yáo Qīzhì), né à Shanghai le , est un chercheur en informatique. Il a reçu le prix Knuth en 1996 et le prix Turing en 2000.
Biographie
[modifier | modifier le code]Andrew Yao est né à Shanghai le . Il a vécu ses premières années à Hong Kong puis à Taïwan[1].
Il a fait son premier cycle universitaire en physique à l'université nationale de Taïwan. Il a obtenu un doctorat en physique de l'université Harvard en 1972, sous la direction de Sheldon Glashow[2] et en informatique de l'université de l'Illinois à Urbana-Champaign en 1975, sous la direction de Chung Laung Liu[3].
Il a travaillé au MIT à l'université de Californie à Berkeley et à l'université Stanford avant d'être professeur à l'université de Princeton[2] et à l'université Tsinghua.
Travaux
[modifier | modifier le code]De façon générale, il a fait avancer de très nombreux domaines de l'informatique théorique[2].
En cryptographie et en sécurité, on lui doit par exemple modèle de Dolev-Yao (en) et le problème du millionnaire (en).
En algorithmique plus classique, il a été le premier à utiliser l'algorithme minimax pour prouver ce que l'on nomme le principe de Yao, un outil permettant d'étudier les algorithmes probabilistes. Il a aussi travaillé sur les structures de données, en utilisant notamment la théorie de Ramsey dans l'article Should Table Be Sorted[4]. Il a amélioré la complexité en temps de la recherche d'un arbre couvrant de poids minimal[2],[5].
Il a aussi jeté les bases de la complexité de la communication[2], dans l'article Some Complexity Questions Related to Distributed Computing[6], et travaillé sur les circuits booléens.
Distinctions
[modifier | modifier le code]Après le prix Knuth en 1996[2], il a reçu le prix Turing en 2000 pour ses contributions en théorie de la calculabilité, génération de nombres pseudo-aléatoires, cryptographie et complexité de la communication[1].
Il reçoit le prix de Kyoto en 2021[7].
Notes et références
[modifier | modifier le code]- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Andrew Yao » (voir la liste des auteurs).
- « Andrew Chi-Chih Yao », sur Association for Computing Machinery.
- « Laudatio du prix Knuth 1996 », sur SIGACT, .
- (en) « Andrew Yao », sur le site du Mathematics Genealogy Project
- Andrew Chi-Chih Yao, « Should Tables Be Sorted? », J. ACM, vol. 28, no 3, , p. 615-628
- Andrew Chi-Chih Yao, « An O(E log log V) Algorithm for Finding Minimum Spanning Trees », Inf. Process. Lett., vol. 4, no 1, , p. 21-23
- Andrew Chi-Chih Yao, « Some complexity questions related to distributive computing », dans Proceedings of the eleventh annual ACM symposium on Theory of computing, , p. 209-213
- (en) « The 2021 Kyoto Prize Laureates Announced! »,
Liens externes
[modifier | modifier le code]
- (en) Site officiel
- Ressources relatives à la recherche :
- Notice dans un dictionnaire ou une encyclopédie généraliste :
- (en) Page personnelle
- (en) Biographie d'Andrew Yao
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
