Ричард Карп: Американдық математик және компьютерлік ғылымның дамуына зор үлес қосушы
Richard M. Karp
Ричард Карп – көрнекті американ математигі, NP-толықтығы, алгоритмдер және ықтималдық әдістер саласындағы ғылыми еңбектерімен танымал. Биографиясы мен жетістіктері.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Америкалық математиктер
American mathematician
Фейт Эллен
Салли Флойд
Филип Гиббонс
Дэн Гасфилд
Нарендра Кармаркар
Валерия Кинг
Майкл Люби
Раджив Мотвани
Ноам Нисан
Раймонд Райтер
Юнис Сантос
Томас Дж. Шефер
Рон Шамир
Барбара Симонс
Эрик Синг
Норман Заде
Faith Ellen
Sally Floyd
Phillip Gibbons
Dan Gusfield
Narendra Karmarkar
Valerie King
Michael Luby
Rajeev Motwani
Noam Nisan
Raymond Reiter
Eunice Santos
Thomas J. Schaefer
Ron Shamir
Barbara Simons
Eric Xing
Norman Zadeh
Карп 1992 жылы Ұлттық инженерлік академиясының мүшесі болып сайланды, себебі ол NP-толықтығының теориясы мен қолданылуына, тиімді комбинаторлық алгоритмдерді құруға және компьютер ғылымында ықтималдық әдістерді қолдануға зор үлес қосты.
Karp was elected a member of the National Academy of Engineering (1992) for major contributions to the theory and application of NP completeness, constructing efficient combinatorial algorithms, and applying probabilistic methods in computer science.
Өмірбаян
Бостон қаласында (Массачусетс штаты) Абрахам мен Роза Карптың отбасында дүниеге келген Карптың үш кіші сіңілісі бар: Роберт, Дэвид және Кэролин. Оның отбасы еврей болған, ол Бостонның Дорчестер ауданында, сол кезде көбіне еврейлер тұратын шағын пәтерде өсті. Оның ата-анасы екеуі де Гарвардты бітірген (анасы кешкі курстарда оқып 57 жасында Гарвард дипломын алды), ал әкесі Гарвардты бітіргеннен кейін медициналық институтқа түсуді армандаған, бірақ медицина оқу ақысын төлей алмағандықтан математика пәнінің мұғалімі болды. Вашингтон университетінде 4 жыл профессор болып жұмыс істегеннен басқа, ол Берклиде қалды. 1988-1995 жылдары және 1999 жылдан қазірге дейін ол Берклидегі Халықаралық компьютерлік ғылым институтында ғылыми қызметкер болып жұмыс істейді, қазіргі таңда алгоритмдер тобын басқарады. Ричард Карп Ұлттық ғылым медалімен марапатталды, сонымен қатар Технионның Харви сыйлығын және 2004 жылғы Бенджамин Франклиннің компьютерлік және танымдық ғылымдар саласындағы медалін есептеу күрделігіне түсінігін жеткізгені үшін алды. 1994 жылы ол Компьютерлік машиналар қауымдастығының мүшесі болып сайланды. 2002 жылы ол Операциялық зерттеулер және басқару ғылымдары институтының стипендиялық бағдарламасына қабылданды. Ол бірнеше құрметті дипломдардың иегері және АҚШ Ұлттық ғылым академиясының, Америка өнер және ғылым академиясының және Америка философиялық қоғамының мүшесі. 2012 жылы Карп Берклидегі Калифорния университетінің Саймонс есептеу теориясы институтының алғашқы директоры болды.
Born to parents Abraham and Rose Karp in Boston, Massachusetts, Karp has three younger siblings: Robert, David, and Carolyn. His family was Jewish, and he grew up in a small apartment, in a then mostly Jewish neighborhood of Dorchester in Boston. Both his parents were Harvard graduates (his mother eventually obtaining her Harvard degree at age 57 after taking evening courses), while his father had had ambitions to go to medical school after Harvard, but became a mathematics teacher as he could not afford the medical school fees. Apart from a 4 year period as a professor at the University of Washington, he has remained at Berkeley. From 1988 to 1995 and 1999 to the present he has also been a research scientist at the International Computer Science Institute in Berkeley, where he currently leads the Algorithms Group. Richard Karp was awarded the National Medal of Science, and was the recipient of the Harvey Prize of the Technion and the 2004 Benjamin Franklin Medal in Computer and Cognitive Science for his insights into computational complexity. In 1994 he was inducted as a Fellow of the Association for Computing Machinery. He was elected to the 2002 class of Fellows of the Institute for Operations Research and the Management Sciences. He is the recipient of several honorary degrees and a member of the U. S. National Academy of Sciences, the American Academy of Arts and Sciences, and the American Philosophical Society. In 2012, Karp became the founding director of the Simons Institute for the Theory of Computing at the University of California, Berkeley.
Жұмыс
Карп компьютерлік ғылым, комбинаторлық алгоритмдер және операциялық зерттеу саласында көптеген маңызды жаңалықтар ашты. Қазіргі кезде оның басты ғылыми қызығушылықтары биоинформатикаға қатысты. 1962 жылы ол Майкл Хелдпен бірлесіп, саяхатшы сатушы мәселесін шешетін нақты экспоненциалды уақыт алгоритмі – Хелд-Карп алгоритмін жасады. 1971 жылы Джек Эдмондспен бірге желілердегі максималды ағын мәселесін шешу үшін Эдмондс-Карп алгоритмін әзірледі, ал 1972 жылы күрделілік теориясы бойынша "Комбинаторлық мәселелердің арасындағы азайту" атты маңызды мақала жариялады, онда ол 21 мәселенің NP-толық екенін дәлелдеді. 1973 жылы Джон Хопкрофтпен бірлесіп, екі бөлікті графиктерде максималды кардиналды сәйкестіктерді табудың ең жылдам әдісі – Хопкрофт-Карп алгоритмін жариялады. 1980 жылы Ричард Дж. Липтонмен бірге Карп Карп-Липтон теоремасын дәлелдеді (егер SAT логикалық қақпалардың полиномдық саны бар Буль тізбектерімен шешілсе, онда полиномдық иерархия өзінің екінші деңгейіне дейін ыдырайды). 1987 жылы Майкл О. Рабинмен бірлесіп, Рабин-Карп тізбектік іздеу алгоритмін жасады.
Karp has made many important discoveries in computer science, combinatorial algorithms, and operations research. His major current research interests include bioinformatics. In 1962 he co developed with Michael Held the Held–Karp algorithm, an exact exponential time algorithm for the travelling salesman problem. In 1971 he co developed with Jack Edmonds the Edmonds–Karp algorithm for solving the maximum flow problem on networks, and in 1972 he published a landmark paper in complexity theory, "Reducibility Among Combinatorial Problems", in which he proved 21 problems to be NP complete. In 1973 he and John Hopcroft published the Hopcroft–Karp algorithm, the fastest known method for finding maximum cardinality matchings in bipartite graphs. In 1980, along with Richard J. Lipton, Karp proved the Karp–Lipton theorem (which proves that if SAT can be solved by Boolean circuits with a polynomial number of logic gates, then the polynomial hierarchy collapses to its second level). In 1987 he co developed with Michael O. Rabin the Rabin–Karp string search algorithm.