David S. Johnson
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Circle-icons-computer.svg/35px-Circle-icons-computer.svg.png)
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
![Page d’aide sur l’homonymie](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a9/Logo_disambig.svg/20px-Logo_disambig.svg.png)
Pour les articles homonymes, voir David Johnson et Johnson.
![une illustration sous licence libre serait bienvenue](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f7/Defaut_2.svg/langfr-260px-Defaut_2.svg.png)
Naissance | ![]() Washington ![]() |
---|---|
Décès | ![]() |
Nationalité | américaine ![]() |
Formation | Massachusetts Institute of Technology Amherst College ![]() |
Activités | Informaticien, ingénieur, professeur d'université ![]() |
A travaillé pour | |
---|---|
Membre de | |
Directeur de thèse | Michael J. Fischer ![]() |
Distinctions |
modifier - modifier le code - modifier Wikidata
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 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
- ↑ (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
- In memoriam : David S. Johnson
Liens externes
- Ressources relatives à la recherche
:
- Digital Bibliography & Library Project
- Google Scholar
- Mathematics Genealogy Project
- Notices d'autorité
:
- VIAF
- ISNI
- BnF (données)
- IdRef
- LCCN
- GND
- CiNii
- Pays-Bas
- Israël
- NUKAT
- Suède
- Tchéquie
- WorldCat
- (en) Page personnelle de David S. Johnson
- (en) Page ACM pour le prix Knuth 2010
Portail de l'informatique théorique