David S. Johnson

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir David Johnson et Johnson.

David Stifler Johnson, né le à 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[modifier | modifier le code]

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

Travaux[modifier | modifier le code]

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[modifier | modifier le code]

Annexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]