Galvenais zinātne

Ričards Manings Karps - amerikāņu matemātiķis un datorzinātnieks

Ričards Manings Karps - amerikāņu matemātiķis un datorzinātnieks
Ričards Manings Karps - amerikāņu matemātiķis un datorzinātnieks
Anonim

Ričards Mannings Karps (dzimis 1935. gada 3. janvārī, Bostona, Masačūsetsas štats, ASV), amerikāņu matemātiķis un datorzinātnieks un 1985. gada AM Tjūringa balvas ieguvējs, kas ir augstākais datorzinātņu gods par “viņa turpmāko ieguldījumu teorijā par algoritmi, tai skaitā efektīvu algoritmu izstrāde tīkla plūsmai un citām kombinatoriskās optimizācijas problēmām, polinomālā laika salīdzināmības identificēšana ar algoritmiskās efektivitātes intuitīvo jēdzienu un, pats svarīgākais, ieguldījums NP pilnīguma teorijā. ” Viņa pētnieciskās intereses ir iekļāvušas teorētisko datorzinātni, kombinatoriskos algoritmus, diskrēto varbūtību, skaitļošanas bioloģiju un interneta algoritmus.

Karp Hārvarda universitātē ieguva bakalaura grādu (1955), maģistra grādu (1956) un doktora grādu (1959), visi matemātikā. Pēc studiju pabeigšanas viņš strādāja par matemātiķi IBM (1959–68), pirms pārcēlās uz akadēmisko vidi. Karps ieņēma amatus Kalifornijas universitātē Bērklijā (1968–1994), Vašingtonas universitātē (1995–1990) un atkal Berklijā (1999–), kur atgriezās kā universitātes profesors.

Karpa 1972. gada raksts “Redzamība starp kombinatoriskām problēmām” pierādīja, ka daudzas bieži pētītas kombinatoriskās problēmas ir vienas un tās pašas problēmas varianti, kas nozīmē, ka tās visas, iespējams, ir neatrisināmas (NP-pilnīgas problēmas - tas ir, problēmas, kurām nav zināms efektīva risinājuma algoritms). Karp ir kompānijas Complicity of Computation (1974) autors un viņam pieder patents par daudzsavienojumu komutācijas tīkla tipu.

Papildus Tjūringa balvai Karps saņēma Fulkersona balvu diskrētajā matemātikā (1979), ASV Nacionālo zinātnes medaļu (1996), Hārvarda universitātes simtgades medaļu (1997), Izraēlas Tehnoloģiju institūta Harvejas balvu (1998), Kārnegija Melona universitātes Diksona balva zinātnē (2008) un Japānas Kioto balva (2008). Viņš tika ievēlēts Ņujorkas Zinātņu akadēmijā (1980), ASV Nacionālajā zinātņu akadēmijā (1980), Amerikas Mākslas un zinātnes akadēmijā (1985), Kombinatorikas un tās pielietojuma institūtā (1990), Amerikas asociācijā zinātnes sasniegumi (1991), ASV Nacionālā inženierzinātņu akadēmija (1992), Amerikas Filozofiskās biedrība (1994), Francijas Zinātņu akadēmija (2002) un Eiropas Zinātņu akadēmija (2004).