David S. Johnson

Biographie
Naissance	9 décembre 1945; Washington
Décès	8 mars 2016 (à 70 ans)
Nationalité	américaine
Formation	Institut de technologie du Massachusetts; Amherst College
Activités	Informaticien, ingénieur, professeur d'université
A travaillé pour	Université Columbia
Membre de	Association for Computing Machinery (1995); Society for Industrial and Applied Mathematics (2009)
Directeur de thèse	Michael J. Fischer
Distinctions	Liste détaillée Prix Frederick W. Lanchester (1979); ACM Fellow (1995); Membre honoraire de la Society for Industrial and Applied Mathematics (2009); Prix Knuth (2010)

Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

David Stifler Johnson, né le 9 décembre 1945 à Washington, mort le 8 mars 2016, 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].