레오니드 레빈
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
레오니드 레빈은 컴퓨터 과학자이자, 계산 복잡도 이론, 알고리즘 분석, 정보 이론 분야의 연구로 알려져 있다. 그는 스티븐 쿡과 독립적으로 NP-완전성 문제를 발견했으며, 이 결과는 쿡-레빈 정리로 불리며 밀레니엄 문제 중 하나의 기반이 되었다. 레빈은 1970년 모스크바 대학교에서 석사 학위를 받았으며, 1979년 매사추세츠 공과대학교에서 박사 학위를 취득했다. 2012년에는 NP-완전성 발견과 평균 사례 복잡성 개발로 크누스 상을 수상했으며, 현재 보스턴 대학교 컴퓨터 과학 교수로 재직 중이다.
더 읽어볼만한 페이지
- 커누스상 수상자 - 크리스토스 파파디미트리우
크리스토스 파파디미트리우는 전기 공학 및 컴퓨터 과학 분야의 학자로서, 계산 복잡성 이론, 데이터베이스 이론, 조합 최적화 분야에 기여했으며, 다수의 상을 수상했다. - 커누스상 수상자 - 앤드루 야오
앤드루 야오는 중국 태생의 이론 전산학자로, 계산 복잡성 이론에 대한 공헌으로 2000년 튜링상을 수상했으며, 국립 타이완 대학, 하버드 대학교, 일리노이 대학교 어배너-샴페인에서 학위를 받고 스탠퍼드 대학교와 프린스턴 대학교 교수를 거쳐 칭화 대학교에서 활동하며, 2015년 중국 국적을 취득 후 중국 과학원 원사, 미국 과학 아카데미 회원 등으로 활동하고 있다. - 정보 이론가 - 클로드 섀넌
클로드 섀넌은 정보 이론의 창시자이자 디지털 회로 설계의 선구자로, 정보 엔트로피 개념을 도입하여 정보 이론을 개척하고 디지털 회로 설계의 이론적 기반을 마련했으며, 암호학, 인공지능, 컴퓨터 체스 연구에도 기여하여 현대 디지털 시대의 기반을 구축했다. - 정보 이론가 - 리처드 해밍
리처드 해밍은 정보 이론과 오류 정정 부호 분야에 기여하고 해밍 거리, 해밍 부호 등의 개념을 도입한 미국의 수학자이자 컴퓨터 과학자이다. - 드니프로 출신 - 미하일로 코한
미하일로 코한은 역사, 정치, 경제, 사회문화적 측면을 포괄적으로 다루며, 한국과의 관계 및 한국 사회에 미친 영향, 긍정적 및 부정적 영향, 비판과 논란을 함께 다룬다. - 드니프로 출신 - 헬레나 블라바츠키
헬레나 블라바츠키는 러시아 출신 신비주의자이자 신지학협회 창립자로, 동양 철학과 신비주의를 서구에 소개하는 데 기여했으나 표절, 사기, 인종차별 논란에 휩싸이기도 했다.
| 레오니드 레빈 - [인물]에 관한 문서 | |
|---|---|
| 기본 정보 | |
 | |
| 출생 이름 | Leonid Anatolievich Levin |
| 출생일 | 1948년 11월 2일 |
| 출생지 | 드니프로페트로우스크, 우크라이나 소비에트 사회주의 공화국, 소비에트 연방 |
| 분야 | 수학, 컴퓨터 과학 |
| 직장 | 보스턴 대학교 |
| 모교 | 모스크바 대학교, 매사추세츠 공과대학교 |
| 박사 지도교수 | 안드레이 콜모고로프, 앨버트 R. 메이어 |
| 알려진 업적 | 쿡-레빈 정리, 평균-케이스 복잡도, 복잡성, 무작위성, 정보 연구 |
| 수상 | 크누스 상 (2012년) |
| 이름 (표기) | |
| 영어 발음 | /ˌleɪ.oʊˈniːd ˈlɛvɪn/ |
| 로마자 표기 | Leonid Anatolievich Levin |
| 러시아어 | Леони́д Анато́льевич Ле́вин (레오니트 아나톨리예비치 레빈) |
| 우크라이나어 | Леоні́д Анато́лійович Ле́він (레오니드 아나톨리요비치 레빈) |
2. 생애
레오니드 레빈은 1970년 모스크바 대학교에서 석사 학위를 받았으며, 안드레이 콜모고로프의 지도하에 공부했다. 1972년 학위 후보 학위 요건을 완료했다.[1][2] 1972년부터 1973년까지 러시아 과학 아카데미의 모스크바 정보 전송 연구소에서 정보 이론의 알고리즘 문제를 연구했고, 1973년부터 1977년까지 석유/가스 산업을 위한 모스크바 국립 통합 자동화 연구소에서 선임 연구 과학자 직책을 맡았다. 1978년 미국으로 이민을 갔고, 1979년 매사추세츠 공과대학교(MIT)에서 앨버트 R. 메이어 교수의 지도 하에 박사 학위를 받았다.[1]
그는 컴퓨팅의 무작위성, 알고리즘 복잡성 및 난해성, 평균 사례 복잡성,[3] 수학 및 컴퓨터 과학의 기초, 알고리즘 확률, 계산 이론, 그리고 정보 이론 분야의 연구로 잘 알려져 있다. 그의 삶은 책 ''Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists''의 한 챕터에 묘사되어 있다.[4]
스티븐 쿡과 독립적으로 발견했다 NP-완전성 문제의 존재를. 이 NP-완전성 정리는 종종 쿡-레빈 정리라고 불리며, 클레이 수학 연구소에서 100만 달러의 상금을 내걸고 발표한 7개의 밀레니엄 문제 중 하나의 기반이 되었다. 쿡-레빈 정리는 컴퓨터 과학의 획기적인 발견이었으며 계산 복잡도 이론의 발전에 중요한 단계였다. 이 정리에 대한 레빈의 논문은 1973년에 출판되었으며,[5] 그는 그 이전 몇 년 동안 이 아이디어에 대해 강의를 했었다(트라흐텐브로트의 조사를 참조).[6] 쿡의 출판 이후에야 결과에 대한 완전한 공식 서술이 이루어졌다.
NP-완전성 발견과 평균 사례 복잡성의 개발로 2012년에 크누스 상을 수상했다.[7] 그는 현재 보스턴 대학교의 컴퓨터 과학 교수로, 1980년부터 가르치기 시작했다.
2. 1. 초기 생애 및 교육
레오니드 레빈은 1970년 모스크바 대학교에서 석사 학위를 받았으며, 안드레이 콜모고로프의 지도하에 공부했다. 1972년 학위 후보 학위 요건을 완료했다.[1][2] 1972년부터 1973년까지 러시아 과학 아카데미의 모스크바 정보 전송 연구소에서 정보 이론의 알고리즘 문제를 연구했고, 1973년부터 1977년까지 석유/가스 산업을 위한 모스크바 국립 통합 자동화 연구소에서 선임 연구 과학자 직책을 맡았다. 1978년 미국으로 이민을 갔고, 1979년 매사추세츠 공과대학교(MIT)에서 앨버트 R. 메이어 교수의 지도 하에 박사 학위를 받았다.[1]2. 2. 소련에서의 연구 활동 (1972-1978)
1970년 모스크바 대학교에서 석사 학위를 받았으며, 안드레이 콜모고로프의 지도하에 공부했으며, 1972년 학위 후보 학위 요건을 완료했다.[1][2] 1972년부터 1973년까지 러시아 과학 아카데미의 모스크바 정보 전송 연구소에서 정보 이론의 알고리즘 문제를 연구했고, 1973년부터 1977년까지 석유/가스 산업을 위한 모스크바 국립 통합 자동화 연구소에서 선임 연구 과학자 직책을 맡았다.[1]그는 컴퓨팅의 무작위성, 알고리즘 복잡성 및 난해성, 평균 사례 복잡성,[3] 수학 및 컴퓨터 과학의 기초, 알고리즘 확률, 계산 이론, 그리고 정보 이론 분야의 연구로 잘 알려져 있다. 그의 삶은 책 ''Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists''의 한 챕터에 묘사되어 있다.[4]
스티븐 쿡과 독립적으로 발견했다 NP-완전성 문제의 존재를. 이 NP-완전성 정리는 종종 쿡-레빈 정리라고 불리며, 클레이 수학 연구소에서 100만 달러의 상금을 내걸고 발표한 7개의 밀레니엄 문제 중 하나의 기반이 되었다. 쿡-레빈 정리는 컴퓨터 과학의 획기적인 발견이었으며 계산 복잡도 이론의 발전에 중요한 단계였다. 이 정리에 대한 레빈의 논문은 1973년에 출판되었으며,[5] 그는 그 이전 몇 년 동안 이 아이디어에 대해 강의를 했었다(트라흐텐브로트의 조사를 참조).[6] 쿡의 출판 이후에야 결과에 대한 완전한 공식 서술이 이루어졌다.
NP-완전성 발견과 평균 사례 복잡성의 개발로 2012년에 크누스 상을 수상했다.[7]
2. 3. 미국 이민 및 학문적 성과 (1978-)
레빈은 1978년 미국으로 이민을 갔고, 1979년 매사추세츠 공과대학교(MIT)에서 앨버트 R. 메이어 교수의 지도하에 박사 학위를 받았다.[1]그는 컴퓨팅의 무작위성, 알고리즘 복잡성 및 난해성, 평균 사례 복잡성,[3] 수학 및 컴퓨터 과학의 기초, 알고리즘 확률, 계산 이론, 그리고 정보 이론 분야의 연구로 잘 알려져 있다. 그의 삶은 ''Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists'' 책의 한 챕터에 묘사되어 있다.[4]
스티븐 쿡과 독립적으로 NP-완전성 문제의 존재를 발견했다]]. 이 NP-완전성 정리는 종종 쿡-레빈 정리라고 불리며, 클레이 수학 연구소에서 100만 달러의 상금을 내걸고 발표한 7개의 밀레니엄 문제 중 하나의 기반이 되었다. 쿡-레빈 정리는 컴퓨터 과학의 획기적인 발견이었으며 계산 복잡도 이론의 발전에 중요한 단계였다. 이 정리에 대한 레빈의 논문은 1973년에 출판되었으며,[5] 그는 그 이전 몇 년 동안 이 아이디어에 대해 강의를 했었다(트라흐텐브로트의 조사를 참조).[6] 쿡의 출판 이후에야 결과에 대한 완전한 공식 서술이 이루어졌다.
NP-완전성 발견과 평균 사례 복잡성의 개발로 2012년에 크누스 상을 수상했다.[7]
현재 보스턴 대학교의 컴퓨터 과학 교수로, 1980년부터 가르치기 시작했다.
3. 주요 업적
레오니드 레빈에 대한 자세한 이야기는 데니스 샤샤(Dennis Shasha)와 캐시 라저(Cathy Lazere)가 함께 쓴 ''Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists'' 책의 한 챕터에서 다루고 있다. 한글판으로는 세종연구원에서 1998년에 출간된 "컴퓨터를 만든 15인의 과학자"가 있다.
3. 1. 쿡-레빈 정리 (NP-완전성)
3. 2. 평균 사례 복잡도
3. 3. 기타 연구 분야
4. 수상 경력
레빈은 스티븐 쿡과 NP-완전성 문제의 존재를 독립적으로 발견했다]].[5] 이 NP-완전성 정리는 쿡-레빈 정리라고 불리며, 클레이 수학 연구소에서 100만 달러의 상금을 내걸고 발표한 7개의 밀레니엄 문제 중 하나의 기반이 되었다.[5] 쿡-레빈 정리는 컴퓨터 과학의 획기적인 발견이었으며 계산 복잡도 이론의 발전에 중요한 단계였다. 레빈의 논문은 1973년에 출판되었으며, 그는 그 이전 몇 년 동안 이 아이디어에 대해 강의를 했었다.[5][6]
레빈은 NP-완전성 발견과 평균 사례 복잡성의 개발로 2012년에 크누스 상을 수상했다.[7]
5. 저서
레오니드 레빈에 대한 자세한 이야기는 다음 책의 한 장(chapter)에 걸쳐 설명하고 있다.
- ''Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists''
- 한글판: 컴퓨터를 만든 15인의 과학자한국어. 데이스 샤사 지음. 세종연구원. 1998년
참조
[1]
웹사이트
Levin's curriculum vitae
http://www.cs.bu.edu[...]
[2]
논문
1971 Dissertation
http://www.cs.bu.edu[...]
[3]
논문
Average-case complete problems
http://epubs.siam.or[...]
[4]
서적
Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists
https://archive.org/[...]
Springer Science+Business Media
1995-09
[5]
논문
Universal search problems (Russian: Универсальные задачи перебора, Universal'nye perebornye zadachi)
http://www.mathnet.r[...]
[6]
논문
A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
https://www.computer[...]
Institute of Electrical and Electronics Engineers
[7]
뉴스
ACM press release, August 22, 2012
http://www.acm.org/p[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com