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 Andrew Yao est né à Shanghai le . Il a vécu ses premières années à Hong Kong puis à Taïwan.
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. et en informatique de l'université de l'Illinois à Urbana-Champaign en 1975, sous la direction de Chung Laung Liu.
Il a travaillé au MIT à l'université de Californie à Berkeley et à l'université Stanford avant d'être professeur à l'université de Princeton et à l'université Tsinghua.
Travaux De façon générale, il a fait avancer de très nombreux domaines de l'informatique théorique.
En cryptographie et en sécurité, on lui doit par exemple et le .
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 Tables Be Sorted. Il a amélioré la complexité en temps de la recherche d'un arbre couvrant de poids minimal.
Il a aussi jeté les bases de la complexité de la communication, dans l'article Some Complexity Questions Related to Distributed Computing, et travaillé sur les circuits booléens.
Distinctions Après le prix Knuth en 1996, 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..
Il reçoit le prix de Kyoto en 2021.
Notes et références
Liens externes
Page personnelle Biographie d'Andrew Yao
Catégorie:Personnalité taïwanaise de l'informatique Catégorie:Personnalité en sécurité informatique Catégorie:Personnalité en informatique théorique Catégorie:Étudiant de l'université nationale de Taïwan Catégorie:Docteur en physique de l'université Harvard Catégorie:Docteur de l'université de l'Illinois Urbana-Champaign Catégorie:Professeur à l'université de Californie à Berkeley Catégorie:Professeur à l'université Stanford Catégorie:Professeur à l'université de Princeton Catégorie:Professeur à l'université Tsinghua Catégorie:Boursier Guggenheim Catégorie:Docteur honoris causa de l'Université de Waterloo Catégorie:Docteur honoris causa de l'université chinoise de Hong Kong Catégorie:Lauréat du prix Turing Catégorie:Lauréat du prix Knuth Catégorie:Lauréat du prix Kyoto Catégorie:Lauréat du prix Georges-Polya Catégorie:Membre de l'Académie chinoise des sciences Catégorie:Membre de l'Academia sinica Catégorie:Membre de l'Académie nationale des sciences Catégorie:Membre de l'Académie américaine des arts et des sciences Catégorie:Membre de l'Association américaine pour l'avancement des sciences Catégorie:Naissance en décembre 1946 Catégorie:Naissance à Shanghai