레오니드 레빈

Leonid Levin
레오니드 아나톨리에비치 레빈
LeonidLevin2010.jpg
2010년 레오니드 레빈
태어난 (1948-11-02) 1948년 11월 2일 (73세)
드니프로페트로프스크, 우크라이나 SSR, 소비에트 연방
모교모스크바 대학교
매사추세츠 공과대학교
로 알려져 있다.쿡-레빈 정리
평균 사례 복잡성
복잡성, 무작위성, 정보에 대한 연구
수상크누스상 (2012)
과학 경력
필드수학
컴퓨터 사이언스
기관보스턴 대학교
박사학위 자문위원안드레이 콜모고로프, 알버트 R. 마이어

Leonid Anatolievich Levin (/leɪ.oʊˈniːd ˈlɛvɪn/ lay-oh-NEED LEV-in; Russian: Леони́д Анато́льевич Ле́вин; Ukrainian: Леоні́д Анато́лійович Ле́він; born November 2, 1948) is a Soviet-American mathematician and computer scientist.

그는 컴퓨터, 알고리즘 복잡성과 난해성, 평균 사례 복잡성,[1] 수학 및 컴퓨터 과학의 기초, 알고리즘 확률, 계산 이론, 정보 이론에서의 무작위적인 연구로 유명하다. 그는 1970년 모스크바 대학에서 석사학위를 취득하여 안드레이 콜모고로프 밑에서 공부했고 1972년 후보 학위 취득 요건을 마쳤다.[2]

그와 스티븐 쿡은 NP-완전 문제의 존재를 독자적으로 발견했다. 흔히 쿡-레빈 정리라고 불리는 이 NP-완전성 정리는 클레이수학연구소가 100만 달러의 상금을 내걸고 선언한 7대 밀레니엄상 문제 중 하나의 기초였다. 쿡-레빈 정리는 컴퓨터 과학의 획기적인 발전이었고 계산 복잡성 이론의 발전에 중요한 단계였다.

레빈은 NP완전성의 발견과 평균사례 복잡성의 발달로 2012년[3] 크누스상을 받았다. 그는 미국 국립과학원 회원이며 미국 예술과학원 동료다.

전기

그는 1970년 모스크바 대학에서 석사학위를 취득하여 안드레이 콜모고로프 밑에서 공부했고 1972년 후보 학위 취득 요건을 마쳤다.[2][4] 1972~1973년 모스크바 국립과학원 정보전송연구소에서 정보이론의 알고리즘 문제를 연구하고 1973~1977년 모스크바 국립석유·가스산업 통합자동화연구소에서 선임연구과학자로 활동한 뒤 1978년 미국으로 이민했다. 또한 1979년 매사추세츠 공과대학(MIT)에서 박사학위를 받았다.[2] MIT의 그의 고문은 Albert R이었다. 마이어.

그는 컴퓨터, 알고리즘 복잡성과 난해성, 평균 사례 복잡성,[1] 수학 및 컴퓨터 과학의 기초, 알고리즘 확률, 계산 이론, 정보 이론 등에서 그의 업적으로 잘 알려져 있다.

그의 생애는 '그들의 마음에서'라는 책의 한 장에 묘사되어 있다. 15명의 위대한 컴퓨터 과학자들의 삶과 발견.[5]

Levin과 Stephen Cook은 NP-완전한 문제의 존재를 독자적으로 발견했다. 흔히 쿡-레빈 정리라고 불리는 이 NP-완전성 정리는 클레이수학연구소가 100만 달러의 상금을 내걸고 선언한 7대 밀레니엄상 문제 중 하나의 기초였다. 쿡-레빈 정리는 컴퓨터 과학의 획기적인 발전이었고 계산 복잡성 이론의 발전에 중요한 단계였다. 이 정리에 대한 레빈의 저널 기사는 1973년에 출판되었다.[6] 그는 쿡의 출판 이후 결과에 대한 완전한 공식적인 쓰기가 이루어졌지만,[7] 그 전에 몇 년 동안 그 안에 있는 아이디어에 대해 강의했었다(Trachtenbrot의 조사 참조).

레빈은 NP완전성의 발견과 평균사례 복잡성의 발달로 2012년[3] 크누스상을 받았다.

그는 현재 보스턴 대학교의 컴퓨터 과학 교수로 재직하고 있으며, 그곳에서 1980년에 가르치기 시작했다.

메모들

  1. ^ a b Levin, Leonid (1986). "Average-case complete problems". SIAM J. Comput. 15 (1): 285–6. doi:10.1137/0215020.
  2. ^ a b c 레빈의 이력서
  3. ^ a b 2012년 8월 22일 ACM 보도 자료 2016년 3월 3일 웨이백 기계에 보관
  4. ^ 1971년 논문(러시아어); arXiv에서 영어 번역
  5. ^ Shasha, Dennis; Cathy Lazere (September 1995). Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists. Springer. ISBN 0-387-97992-1.
  6. ^ Levin, Leonid (1973). "Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (Russian: Проблемы передачи информации, Problemy Peredachi Informatsii). 9 (3): 115–116. (pdf)
  7. ^ Boris A. Trakhtenbrot (1984). "A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms". Annals of the History of Computing. IEEE. 6 (4): 384–400. doi:10.1109/MAHC.1984.10036. S2CID 950581.

참조

외부 링크