David S. Johnson
David S. Johnson
| Naissance | Washington |
|---|---|
| Décès |
(à 70 ans) |
| Nationalité |
américaine |
| Formation |
Institut de technologie du Massachusetts Amherst College |
| Activités |
Informaticien, professeur d'université, ingénieur, mathématicien |
| A travaillé pour |
Université Columbia |
|---|---|
| Membre de |
Association for Computing Machinery () Society for Industrial and Applied Mathematics () |
| Directeur de thèse |
Michael J. Fischer |
| Distinctions | Liste détaillée Prix Frederick W. Lanchester () ACM Fellow () Membre honoraire de la Society for Industrial and Applied Mathematics () Prix Knuth () |
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].
Biographie
Johnson a obtenu son PhD en 1973 au MIT[3]. Il est mort le [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
- ↑ (en) Liste des lauréats du prix Knuth sur la page de Sigact
- ↑ (en) Page ACM pour le prix Knuth 2010
- ↑ (en) « David S. Johnson », sur le site du Mathematics Genealogy Project.
- ↑ (en) « In memoriam: David S. Johnson », sur université Columbia.
- ↑ (en) Richard Lipton et KW Regan, « David Johnson: 1945-2016 », .
- ↑ Lance Fortnow (en), « David Johnson (1945-2016) », .
Annexes
Hommage
Liens externes
- Ressources relatives à la recherche :
- (en) Page personnelle de David S. Johnson
- (en) Page ACM pour le prix Knuth 2010
Portail de l'informatique théorique