David S. Johnson

David Stifler Johnson, né le à Washington, mort le , est chercheur en informatique américain. Il est connu pour ses travaux en algorithmique et en optimisation combinatoire. Il a reçu le prestigieux prix Knuth en 2010[1],[2].

Pour les articles homonymes, voir David Johnson et Johnson.

David S. Johnson
Biographie
Naissance
Décès
(à 70 ans)
Nationalité
Formation
Activités
Autres informations
A travaillé pour
Membre de
Dir. de thèse
Distinctions

Biographie

Johnson a obtenu son PhD en 1973 au MIT[3]. Il est mort le 8 mars 2016[4].

Travaux

Johnson est connu pour son travail en algorithmique, et notamment pour la création de challenges pour comparer et améliorer les heuristiques et les algorithmes[5].

Il est l'auteur avec Michael Garey de l'ouvrage Computers and Intractability (en), l'un des livres importants à la base de la théorie de la complexité et de l'algorithmique. Il est considéré comme le livre le plus important sur la NP complétude[6].

Notes et références
  1. (en) Liste des lauréats du prix Knuth sur la page de Sigact
  2. (en) Page ACM pour le prix Knuth 2010
  3. (en) « David S. Johnson », sur le site du Mathematics Genealogy Project.
  4. (en) « In memoriam: David S. Johnson », sur université Columbia.
  5. (en) Richard Lipton et KW Regan, « David Johnson: 1945-2016 », .
  6. Lance Fortnow (en), « David Johnson (1945-2016) », .

Annexes

Hommage

Liens externes
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.