Richard karp

Richard karp Bilgi Kutusu'ndaki görüntü. Richard Karp, 2009. Biyografi
Doğum 3 Ocak 1935
Boston
Ana dilde isim Richard Manning Karp
Milliyet Amerikan
Eğitim Harvard
Harvard Mühendislik ve Uygulamalı Bilimler Okulu ( in )
University of California, Berkeley
Aktiviteler Matematikçi , bilgisayar bilimcisi , üniversite profesörü
Diğer bilgiler
İçin çalıştı University of California at Berkeley , University of Washington
Alanlar Hesaplanabilirlik teorisi ( in ) , biyoinformatik
Üyesi Bilgisayar Makineleri Derneği
American Academy of Arts and Sciences
American Philosophical Society American
Association for the Advancement of Science
American Academy of Sciences (1980)
Amerika Birleşik Devletleri Ulusal Mühendislik Akademisi (1992)
Bilimler Akademisi (2002)
Süpervizör Anthony Oettinger
Ödüller Turing Ödülü (1985)
Birincil işler
Akışları ve torbalarda sık elemanları bulmak için basit bir algoritma ( d )

Richard Manning Karp (doğdu3 Ocak 1935içinde Boston bölgesindeki Massachusetts ) bir araştırmacı Amerikan yaptığı araştırmalarıyla tanınan kombinatoryal optimizasyon ve karmaşıklık teorisi . O alınan Turing Ödülü de 1985 çalışmaları için.

Biyografi

Richard Karp, Abraham ve Rose Karp'ın oğludur.

O girilen Harvard University onun aldığı, lisans derecesini de 1955 , onun Master derecesi içinde 1956 ve onun Doktora içinde uygulamalı matematik içinde 1959 .

Daha sonra IBM için Thomas J. Watson Araştırma Merkezi'nde çalıştı .

In 1968 , o bilgisayar bilimleri ve matematik profesörü oldu Berkeley'deki Kaliforniya Üniversitesi'nde profesör olarak dört yıllık bir süre için hariç, o bundan sonra kalan, Washington Üniversitesi .

Narendra Karmarkar , Noam Nisan ve Rajeev Motwani'nin tez direktörlüğünü yaptı .

İşler

Richard Karp, ağırlıklı olarak algoritmalar ve karmaşıklık teorisinde çalıştı . Önemli katkıları arasında şunlar yer almaktadır.

Şu anda biyoinformatik ile ilgileniyor .

Ödüller ve Takdir

Turing Ödülü'nde şu şekilde alıntı yapıldı: "Ağlar ve diğer kombinasyonel optimizasyon problemleri için verimli algoritmaların geliştirilmesi, polinom zamanda hesaplanabilirliğin sezgisel verimli algoritma nosyonuyla belirlenmesi ve daha fazlası dahil olmak üzere algoritma teorisine yaptığı sürekli katkılarından dolayı. hepsi, NP-tamlık teorisine katkıları . Karp, bir problemin NP-tamamlandığını kanıtlamak için artık klasik olan metodolojiyi tanıttı ve bu, birçok pratik ve teorik problemin hesaplanması zor olarak tanımlanmasını mümkün kıldı. "

Kaynak

Notlar ve referanslar

  1. https://www.kyotoprize.org/wp/wp-content/uploads/2016/02/24kA_lct_EN.pdf
  2. "  Turing Prize Citation  " , Association for Computing Machinery
  3. (tr) “  Richard Karp  ” , üzerinde Matematik Şecere Projesi web sitesi
  4. Jack Edmonds ve Richard M. Karp , "  Ağ akış problemleri için algoritmik verimlilikte teorik gelişmeler  ", Journal of the ACM , Association for Computing Machinery (ACM), cilt.  19, n o  21972, s.  248–264 ( DOI  10.1145 / 321694.321699 )
  5. (in) Richard M. Karp, Kombinatoryal Problemler Arasında indirgenebilirlik . In Bilgisayar Hesaplamaları karmaşıklığı , Proc. Güzel. IBM Thomas J. Watson Res. Merkez, Yorktown Heights, NY. New York: Plenum, s. 85-103. 1972.
  6. John Hopcroft ve Richard Karp, "  İki parçalı grafiklerde maksimum eşleşmeler için bir n 5/2 algoritması  ", SIAM Journal on Computing , cilt.  2, n, o  , 4, 1973, s.  225-231 ( DOI  10.1137 / 0202019 )
  7. Richard M. Karp ve Richard J. Lipton, "Düzgün olmayan ve tek tip karmaşıklık sınıfları arasındaki bazı bağlantılar" , Bilgi İşlem Teorisi Sempozyumu'nda , 1980( DOI  10.1145 / 800141.804678 ) , s.  302-309.
  8. Richard M. nom2 = Rabin Karp , "  Verimli rastgele desen eşleştirme algoritmaları  ", IBM Araştırma ve Geliştirme Dergisi , cilt.  31, n o  2Mart 1987, s.  249–260 ( DOI  10.1147 / rd.312.0249 , çevrimiçi okuyun ).
  9. "  Richard Karp Ödülü  " üzerine, Yöneylem Araştırmaları Enstitüsü ve Yönetim Bilimleri

Dış bağlantılar