David Stifler Johnson

David Stifler Johnson

David Stifler Johnson (* 9. Dezember 1945 in Washington D. C.) ist ein US-amerikanischer Informatiker.

Johnson studierte Mathematik am Amherst College (Bachelor 1967 summa cum laude) und am Massachusetts Institute of Technology, wo er 1968 bei Seymour Papert seinen Master-Abschluss machte (Look ahead strategies in one person games with randomly generated game trees) und 1973 bei Michael J. Fisher (MIT) promoviert wurde (Near optimal bin-packing algorithms). Nach dem Dienst in der US-Armee 1969 bis 1971 war er ab 1973 bei den ATT Bell Laboratories. 1988 bis 1996 leitete er dort die Abteilung Mathematical Foundations of Computing und danach die Abteilung Algorithms and Optimization. 1978 war er Gastprofessor an der Rutgers University und 1980/81 an der University of Wisconsin.

1996 bis 2004 war er im Rat der Association for Computing Machinery (ACM) (deren Fellow er seit 1994 ist) und stand 1987 bis 1991 der ACM SIGACT vor, deren Distinguished Service Award er 1997 erhielt. 1983 bis 1987 war er Herausgeber des Journal of the ACM und von 1991 bis 2006 von ACM Transactions on Mathematical Software (TOMS). 1979 bis 2004 war er Herausgeber des Journal of Algorithms, seit 1984 von Algorithmica und von 1980 bis 1997 von Mathematical Programming und von Mathematics of Operations Research. Seit 2004 ist er Mitherausgeber der ACM Transactions on Algorithms. Im Journal of Algorithms hatte er 1982 bis 1992 eine Kolumne über Algorithmen, fortgesetzt in den ACM Transactions on Algorithms[1]. Er ist Gründer des ACM-SIAM-Symposiums on Discrete Algorithms (SODA).

1979 erhielt er den Lanchester-Preis der Operations Research Society of America. 2005 wurde er ATT Fellow und 2009 SIAM Fellow. 1983 erhielt er den Distinguished Technical Staff Award der ATT Bell Laboratories.

2010 erhielt er den Knuth-Preis. Er erhielt den Preis für frühe Arbeiten über NP-Vollständigkeit und Approximierungsalgorithmen für Optimierungs- und Suchaufgaben, darunter NP-harte Probleme wie das Problem des Handlungsreisenden und das Behälterproblem (Bin-Packing). Er schrieb darüber auch ein Standardwerk mit Michael Garey. Er untersuchte die Algorithmen für Optimierungsaufgaben nicht nur theoretisch, sondern entwickelte auch Testverfahren, um ihre Leistung beurteilen zu können.

Er ist verheiratet und hat ein Kind.

Schriften

  • mit Michael Garey Computers and Intractability: a guide to the theory of NP completeness, Freeman, San Francisco 1979

Weblinks

Einzelnachweise

  1. The NP Completeness Column

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • David S. Johnson — For other people named David Johnson, see David Johnson (disambiguation). David Stifler Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. He is currently the head of the Algorithms and… …   Wikipedia

  • Johnson (Familienname) — Johnson ist ein Familienname. Herkunft und Bedeutung Johnson ist eine patronymische Namensbildung, abgeleitet vom englischen Vornamen John (deutsch: Johannes). Namensträger Inhaltsverzeichnis A B C D E F G H I J K L …   Deutsch Wikipedia

  • David Johnson — ist der Name folgender Personen: David Johnson (Politiker) (1782–1855), amerikanischer Politiker (South Carolina) David Johnson (Komponist) (* 1940), amerikanischer Komponist David Johnson (Hornist), Hornist David Johnson (Fußballspieler, 1951)… …   Deutsch Wikipedia

  • Seann William Scott — Pour les articles homonymes, voir Scott. Seann William Scott …   Wikipédia en Français

  • McBurney School — was a college preparatory school in Manhattan run by the YMCA of Greater New York. Among its alumni are actors Henry Winkler [1] and Richard Thomas [2], novelist J. D. Salinger[1], physician Lewis Thomas …   Wikipedia

  • Seann William Scott — (2008) Seann William Scott (* 3. Oktober 1976 in Cottage Grove, Minnesota als Sean William Scott) ist ein US amerikanischer Schauspieler. Inhaltsverzeichnis …   Deutsch Wikipedia

  • List of Seinfeld minor characters — The television show Seinfeld was known for featuring many characters, each with their own special quirks. Contents 1 Secondary characters 1.1 Character frequency 1.2 Other characters appearing in 5 or more episodes …   Wikipedia

  • Typecasting (acting) — For other meanings, see typecasting. Typecasting is the process by which a film, TV, or stage actor is strongly identified with a specific character, one or more particular roles, or characters with the same traits or ethnic grouping.There have… …   Wikipedia

  • Damien Boisseau — est un acteur français de théâtre, de cinéma et de télévision, spécialisé et plus particulièrement connu comme comédien de doublage. Il est notamment la voix française attitrée d’Edward Norton et de Matt Damon ainsi que la voix régulière de… …   Wikipédia en Français

  • Alexis Victor — est comédien. Il joue beaucoup au théâtre et est également la voix française de Bradley Cooper dans la plupart de ses films. Sommaire 1 Théâtre 2 Voxographie 2.1 Cinéma 2.1.1 Film …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”