Allan Borodin
Pour les articles homonymes, voir Borodine (homonymie).
| Naissance | |
|---|---|
| Nationalité |
 Canada |
| Domaines | Informatique théorique |
|---|---|
| Institutions | Université de Toronto |
| Diplôme | Université Rutgers, Institut de technologie Stevens, Université Cornell |
| Directeur de thèse | Juris Hartmanis |
| Distinctions | prix CRM-Fields-PIMS (2008) ; FRSC |
Allan Bertram Borodin est un chercheur en informatique américano-canadien né en 1941, à la retraite après avoir enseigné à l'Université de Toronto[1] l'Informatique ainsi que les réseaux sociaux et économiques[2].
Biographie modifier
Borodin effectue ses études à l'Université Rutgers, où il obtient son bachelor en mathématiques en 1963. Après son diplôme de master à l'Institut de technologie Stevens en 1966, époque où il travaillait en parallèle comme programmeur aux Laboratoires Bell, il continue ses études à l'Université Cornell, où il obtient son doctorat en 1969 sous la direction de Juris Hartmanis. Il rejoint la faculté de Toronto en 1969 et il est promu professeur en 1977. Il est titulaire de la chaire du département de 1980 à 1985, puis devient Professeur d'université en 2011[1],[2],[3].
Prix et récompenses modifier
Borodin est élu membre en 2000 de la Société royale du Canada en 1991. En 2008, il reçoit le Prix CRM-Fields-PIMS[2],[4]. Il devient membre en 2011 de l'Association américaine pour l'avancement des sciences[5] et membre en 2014 de l'Association for Computing Machinery « Pour ses contributions à l'informatique théorique en complexité, l'algorithme online, les échanges de ressources et les modèles de paradigmes algorithmiques. (For contributions to theoretical computer science in complexity, on-line algorithms, resource tradeoffs, and models of algorithmic paradigms) »[6].
Sélection de publications modifier
- Articles de recherche
- Allan Borodin, « Computational complexity and the existence of complexity gaps », Journal of the ACM, vol. 19, no 1, , p. 158–174 (DOI 10.1145/321679.321691)
- Allan Borodin, « On relating time and space to size and depth », SIAM Journal on Computing, vol. 6, no 4, , p. 733–744 (DOI 10.1137/0206054, MR 0461984)
- S. Ben-David, A. Borodin, R. Karp, G. Tardos et A. Wigderson, « On the power of randomization in on-line algorithms », Algorithmica, vol. 11, no 1, , p. 2–14 (DOI 10.1007/BF01294260, MR 1247985)
- (en) Allan Borodin, Ronald Fagin, John E. Hopcrofts et Martin Tompa, « Decreasing the Nesting Depth of Expressions Involving Square Roots », J . Symbolic Computation, vol. 1, , p. 169-188 (lire en ligne)
- Ouvrages
- (en) Allan Borodin et Ian Munro, The Computational Complexity of Algebraic and Numeric Problems, vol. 1, New York, London, Amsterdam, American Elsevier Publishing Co., Inc., coll. « Elsevier Computer Science Library; Theory of Computation Series », (MR 0468309)
- Borodin, A. et El-Yaniv, R., Online Computation and Competitive Analysis, Cambridge/New York/Melbourne, Cambridge University Press, , 414 p. (ISBN 0-521-56392-5, lire en ligne)
Voir aussi modifier
- Gap theorem
- algorithmes online
- Théorie de la complexité
Liens externes modifier
Références modifier
- Borodin nommé Professeur d' Université, U. Toronto Computer Science, retrieved 2012-03-17.
- Past prizes and awards, PIMS, retrieved 2012-03-17.
- Fiche sur le Mathematics Genealogy Project
- Allan Borodin: Recipient of the 2008 CRM-Fields-PIMS Prize, retrieved 2012-03-17.
- AAAS Members Elected as Fellows in 2011, retrieved 2012-03-17.
- ACM Names Fellows for Innovations in Computing, ACM, January 8, 2015, retrieved 2015-01-08.
