Richard M. Karpi

Richard Karp 2009

Richard Manning Karp (nato il 3 gennaio 1935 a Boston ) è un informatico americano . È responsabile di scoperte significative nella teoria della complessità . Nel 1985 ha ricevuto il Premio Turing per il suo lavoro di ricerca nel campo della teoria degli algoritmi e nel 2008 ha ricevuto il Premio Kyoto .

Vita

Dopo la Boston Latin School , ha frequentato la Harvard University , dove ha conseguito la laurea in lettere nel 1955 , il master in matematica nel 1956 e il dottorato di ricerca nel 1959. nella matematica applicata . Ha poi lavorato presso l' IBM Thomas J. Watson Research Center fino al 1968 . Inoltre, è stato assistente di ricerca part-time presso la New York University nel 1962, professore associato in visita di ingegneria elettrica all'Università del Michigan dal 1964 al 1965, professore associato in visita e professore ordinario in visita di ingegneria elettrica al Politecnico Institute of Brooklyn (part-time) dal 1967 al 1968 e dal 1967 al 1968 Professore Associato di Ingegneria Industriale e Ingegneria Gestionale presso la Columbia University (part-time). Nel 1968 è diventato Professore di Informatica , Matematica e Ricerca Operativa presso l' Università della California, Berkeley . Oltre a un periodo di quattro anni come professore all'Università di Washington (dal 1995 al 1999 come professore di informatica e docente di biotecnologia molecolare), da allora è rimasto a Berkeley, dove, oltre all'università, ha anche lavorato presso l' International Computer Science Institute e talvolta anche presso il Mathematical Sciences Research Institute è o è stato attivo.

Karp ha lavorato o ha fatto parte dei comitati editoriali di numerose riviste, tra cui Journal of Computer and System Sciences e Proceedings of the National Academy of Sciences . È stato anche nel comitato consultivo del Max Planck Institute for Computer Science e ha consigliato IBM Research , Hewlett-Packard , Computer Professionals for Social Responsibility , International Institute for Applied Systems Analysis e Center for Discrete Mathematics and Theoretical Computer Science . È stato membro del consiglio di sorveglianza del Weizmann Institute for Science e dell'Institute for Mathematics and its Applications , nonché del consiglio di amministrazione del Miller Institute for Basic Research in Science e, tra l'altro, è stato a capo. lo Science Planning Group computer del del Consiglio Nazionale delle Ricerche e il Computer e scienze Sezione della National Academy of Sciences .

Nel 1971 Karp e Jack Edmonds svilupparono l' algoritmo di Edmonds-Karp per risolvere il problema del flusso massimo nelle reti. Nel 1972 pubblicò un articolo in cui dimostrò la NP-completezza di una serie di problemi di teoria dei grafi, tra cui il problema del ciclo di Hamilton , il problema della cricca e il problema dello zaino . Questi divennero noti come Karps 21 NP-Problemi completi . Nel 1973 sviluppò con John Hopcroft l' algoritmo Hopcroft-Karp per la determinazione di un accoppiamento massimo in grafi bipartiti . Nel 1987 ha sviluppato l' algoritmo Rabin-Karp per la ricerca di stringhe insieme a Michael O. Rabin . I suoi principali interessi di ricerca includono algoritmi combinatori e paralleli, bioinformatica e reti.

I circa 40 studenti di dottorato di Karp includono Narendra Karmarkar ( Premio Fulkerson 1988), Phillip Gibbons ( Premio Paris Kanellakis 2019) e Rajeev Motwani ( Premio Gödel 2001).

Premi (selezione)

• 1977: Premio Frederick W. Lanchester (con Gérard Cornuéjols , Marshall Fisher e George Nemhauser ) Premio Frederick W. Lanchester
• 1979: Premio Fulkerson
• 1980: Membro della National Academy of Sciences e della New York Academy of Sciences
• 1983: Invited Speaker al Congresso Internazionale dei Matematici di Varsavia ( L'analisi probabilistica degli algoritmi combinatori ).
• 1985: Premio Turing e membro dell'American Academy of Arts and Sciences
• 1986: Laurea honoris causa dall'Università della Pennsylvania
• 1989: Dottorato honoris causa dal Technion
• 1990: John von Neumann Theory Prize , dottorato onorario dall'Università del Massachusetts e membro fondatore dell'Istituto di Combinatoria e sue applicazioni
• 1991: membro dell'American Association for the Advancement of Science
• 1992: Membro della National Academy of Engineering e dottorato onorario della Georgetown University
• 1994: Membro dell'American Philosophical Society e Fellow dell'ACM
• 1996: Medaglia Nazionale della Scienza
• 1997: Medaglia del Centenario di Harvard
• 1998: Premio Harvey
• 2000: Premio EATCS
• 2001: Dottorato Honoris Causa dalla University of Central Florida
• 2002: Membro straniero dell'Académie des sciences , dottorato honoris causa dalla Carleton University e Fellow dell'Institute for Operations Research and the Management Sciences
• 2003: Dottorato honoris causa dall'ETH di Zurigo
• 2004: Benjamin Franklin Medal for Computer Science and Cognitive Science , nonché dottorato honoris causa dal Weizmann Institute for Sciences e membro dell'Accademia europea delle scienze
• 2008: Premio Kyoto
• 2008: Premio Dickson per la scienza

caratteri

• Riducibilità tra problemi combinatori (PDF; 10.9 MB) . In: RE Miller, JW Thatcher (a cura di): Complessità dei calcoli informatici . Plenum Press, New York 1972, pp. 85-103.

link internet

• Letteratura di e su Richard M. Karp nel catalogo della Biblioteca nazionale tedesca
• Intervista e biografia ( ricordo del 18 giugno 2008 in Internet Archive )
• Sito web (inglese)

Evidenze individuali

1. ^ Premio Frederick W. Lanchester. (Non più disponibile online.) Informs.org ( Institute for Operations Research and the Management Sciences ), archiviato dall'originale il 2 ottobre 2015 ; accesso il 16 febbraio 2016 . Info: Il collegamento all'archivio è stato inserito automaticamente e non è stato ancora verificato. Si prega di controllare il collegamento originale e archivio secondo le istruzioni e quindi rimuovere questo avviso. @1@ 2Modello: Webachiv / IABot / www.informs.org 
2. ^ Lauree honoris causa dal 1954 - Senato. carleton.ca, consultato il 12 marzo 2015 .