Richard Manning Karp 미국 수학자 및 컴퓨터 과학자

Richard Manning Karp (1935 년 1 월 3 일, 미국 매사추세츠 보스턴에서 태어남), 미국 수학자이자 컴퓨터 과학자이자 컴퓨터 과학 분야의 최고 명예 인 1985 AM Turing Award 수상 네트워크 흐름 및 기타 조합 최적화 문제를위한 효율적인 알고리즘 개발, 알고리즘 효율의 직관적 개념을 통한 다항식 시간 계산 가능성 식별, 특히 NP- 완전성 이론에 대한 기여 등을 포함한 알고리즘” 그의 연구 관심 분야에는 이론적 컴퓨터 과학, 조합 알고리즘, 이산 확률, 계산 생물학 및 인터넷 알고리즘이 포함되었습니다.

Karp는 하버드 대학교에서 수학으로 학사 학위 (1955), 석사 학위 (1956) 및 박사 학위 (1959)를 취득했습니다. 학업을 마친 후에는 IBM (1959–68)에서 수학자로 일하기 전에 학계로 옮겼습니다. Karp는 University of California, Berkeley (1968-94), Washington University (1995-99), Berkeley (1999-)에서 다시 대학 교수로 재직했습니다.

Karp의 1972 년 논문“조합 문제들 사이의 감소 성”은 일반적으로 연구되는 조합 문제들 중 다수가 동일한 문제의 변형이며, 이는 아마도 다루기 힘들다는 것을 암시한다 (NP- 완전 문제, 즉 효율적인 솔루션 알고리즘이 알려지지 않은 문제). Karp는 Complexity of Computation (1974)의 저자이며 일종의 다중 연결 스위칭 네트워크에 대한 특허를 보유하고 있습니다.

튜링 상 외에도 Karp는 이산 수학 (1979), 미국 과학 메달 (1996), 하버드 대학교 센 테니얼 메달 (1997), 이스라엘 기술 하 비상 (1998), Carnegie Mellon University Dickson 과학상 (2008), 일본 교토 상 (2008). 그는 뉴욕 과학 아카데미 (1980), 미국 국립 과학 아카데미 (1980), 미국 예술 과학 아카데미 (1985), 조합 및 응용 연구소 (1990), 미국 협회에 선출되었습니다. 과학 발전 (1991), 미국 국립 공학 아카데미 (1992), 미국 철학 협회 (1994), 프랑스 과학 아카데미 (2002) 및 유럽 과학 아카데미 (2004).