Andrew Yao

Andrew Yao Bilde i infoboks. Andrew Yao i 2005. Biografi
Fødsel 24. desember 1946
Shanghai
Nasjonaliteter Kinesisk
amerikansk (til2015)
Opplæring Harvard
University National Taiwan
University University of Illinois i Urbana-Champaign
Aktiviteter Informatiker , universitetsprofessor
Ektefelle Frances yao
Annen informasjon
Jobbet for Princeton University , Tsinghua University , Stanford University , University of California i Berkeley , University of California i San Diego
Områder Informasjonsvitenskap ( in ) , datamaskin
Medlem av Academia sinica
American Academy of Arts and Sciences
Association for Computing Machinery
American Academy of Sciences (1998-2015)
American Academy of Sciences (2015)
Akademisk avdeling for informasjonstekniske vitenskaper ved det kinesiske vitenskapsakademiet ( d ) (2017)
Veileder Chung Laung Liu ( i )
Nettsted itcs.tsinghua.edu.cn/yao
Utmerkelser Turing-prisen (2000)
Primærverk
Yao-prinsippet

Andrew Chi-Chih Yao ( kinesisk  : 姚 期 智; pinyin  : Yáo Qīzhì), født i Shanghai den24. desember 1946, er informatiker . Han mottok Knuth-prisen i 1996 og Turing-prisen i 2000.

Biografi

Andrew Yao ble født i Shanghai den 24. desember 1946. Han bodde sine første år i Hong Kong og deretter i Taiwan .

Han gjorde sin lavere grad i fysikk ved National Taiwan University . Han fikk doktorgrad i fysikk fra Harvard University i 1972, under veiledning av Sheldon Glashow, og i informatikk fra University of Illinois i Urbana-Champaign i 1975, under veiledning av Chung Laung Liu.

Han jobbet ved MIT ved University of California i Berkeley og Stanford University før han var professor ved Princeton University og Tsinghua University .

Virker

Generelt har han avansert mange områder innen teoretisk informatikk .

I kryptografi og sikkerhet skylder vi ham for eksempel modellen til Dolev-Yao  (in) og millionærproblemet  (in) .

I mer klassiske algoritmer var han den første til å bruke minimax-algoritmen for å bevise det som kalles Yao-prinsippet , et verktøy som muliggjør studier av sannsynlighetsalgoritmer . Han jobbet også med datastrukturer , spesielt ved bruk av Ramseys teori i artikkelen Should Table Be Sorted . Det har forbedret tidskompleksiteten til å finne et spennende tre med minimal vekt .

Han la også grunnlaget for kompleksiteten i kommunikasjon , i artikkelen Some Complexity Questions Related to Distributed Computing , og jobbet med boolske kretser .

Utmerkelser

Etter Knuth-prisen i 1996 mottok han Turing-prisen i 2000 for sine bidrag til beregningsteori, pseudo-tilfeldig tallgenerering, kryptografi og kommunikasjonskompleksitet .

Han mottar Kyoto-prisen i 2021.

Merknader og referanser

  1. “  Andrew Chi-Chih Yao  ” , om Association for Computing Machinery .
  2. "  1996 Knuth Prize Laudatio  " , på SIGACT ,1996.
  3. (i) "  Andrew Yao  " på nettstedet Mathematics Genealogy Project
  4. Andrew Chi-Chih Yao, “  Bør bordene sorteres?  », J. ACM , vol.  28 n o  3, nitten åtti en, s.  615-628
  5. Andrew Chi-Chih Yao, “  An O (E log log V) Algorithm for Finding Minimum Spanning Trees  ”, Inf. Prosess. Lett. , vol.  4, n o  1, 1975, s.  21-23
  6. Andrew Chi-Chih Yao , “Noen spørsmål om kompleksitet knyttet til distributiv databehandling” , i Proceedings of the ellevde årlige ACM-symposium om teori om databehandling ,1979, s.  209-213
  7. (in) "  Kyoto-prisvinnerne i 2021 ble kunngjort!  " ,18. juni 2021

Eksterne linker