Loading article…
レオニード・レヴィン | |
|---|---|
 2010年のレビン | |
| 生まれる | レオニード・アナトリエヴィッチ・レヴィン 1948年11月2日 ドニプロペトロフスク、ウクライナSSR、ソビエト連邦 |
| 母校 | モスクワ大学 マサチューセッツ工科大学 |
| 知られている | クック・レビン定理 平均ケースの複雑性 複雑性、ランダム性、情報に関する研究 |
| 受賞歴 | クヌース賞 (2012) |
| 科学者としてのキャリア | |
| フィールド | 数学 コンピュータサイエンス |
| 機関 | ボストン大学 |
| 博士課程の指導教員 | アンドレイ・コルモゴロフ、アルバート・R・マイヤー |
レオニード・アナトリエヴィチ・レヴィン( / ˌ l eɪ . oʊ ˈ n iː d ˈ l ɛ v ɪ n / LAY -oh- NEED LEV -in ;ロシア語: Леони́д Анато́льевич Ле́вин [lʲɪɐˈnʲit ɐnɐˈtolʲjɪvʲɪtɕ ˈlʲevʲɪn]ウクライナ語: Леоні́д Анато́лійович Ле́він [leoˈn⁽ʲ⁾id] [ ɐnɐˈtɔl⁽ʲ⁾ijowɪtʃ ˈlɛwin]（1948年11月2日生まれ）は、ソビエト系アメリカ人の数学者、コンピュータ科学者である。
彼は、コンピューティングにおけるランダム性、アルゴリズムの複雑性と扱いにくさ、平均ケースの複雑性、[1]数学とコンピュータサイエンスの基礎、アルゴリズムの確率、計算理論、情報理論に関する研究で知られています。彼は1970年にモスクワ大学でアンドレイ・コルモゴロフに師事して修士号を取得し、 1972年に学位候補生の学業要件を満たしました。 [2]
彼とスティーブン・クックは 独立してNP 完全問題の存在を発見した。この NP 完全性定理はクック＝レビン定理とも呼ばれ、クレイ数学研究所が 100 万ドルの賞金をかけて宣言した 7 つのミレニアム懸賞問題のうちの 1 つの基礎となった。クック＝レビン定理はコンピュータ サイエンスにおける画期的な進歩であり、計算複雑性の理論の発展における重要な一歩であった。
レヴィンはNP完全性の発見と平均ケース複雑性の開発により2012年にクヌース賞を受賞しました[3] 。彼は米国科学アカデミーの会員であり、アメリカ芸術科学アカデミーのフェローでもあります。
バイオグラフィー
1970年にモスクワ大学でアンドレイ・コルモゴロフに師事し、1972年に修士号を取得。[2] [4] 1972年から1973年まで国立科学アカデミーのモスクワ情報伝送研究所で情報理論のアルゴリズム問題を研究し、1973年から1977年までモスクワ国立石油ガス産業統合オートメーション研究所で上級研究員を務めた後、 1978年に米国に移住し、1979年にマサチューセッツ工科大学（MIT）で博士号を取得した。[2] MITでの指導教官はアルバート・R・マイヤーであった。
彼は、コンピューティングにおけるランダム性、アルゴリズムの複雑性と扱いにくさ、平均ケースの複雑性、[1]数学とコンピュータサイエンスの基礎、アルゴリズムの確率、計算理論、情報理論の研究でよく知られています。
彼の生涯については、『Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists』という本の一章で説明されている。[5]
レビンとスティーブン・クックは独立して NP完全問題の存在を発見した。このNP完全性定理はクック＝レビンの定理とも呼ばれ、クレイ数学研究所が100万ドルの賞金をかけた7つのミレニアム懸賞問題のうちの1つの基礎となった。クック＝レビンの定理はコンピュータサイエンスにおける画期的な発見であり、計算複雑性理論の発展における重要な一歩であった。この定理に関するレビンの学術雑誌論文は1973年に出版された。[6]彼はそれより数年前からこの定理のアイデアについて講義していたが（トラクテンブロートの調査を参照）、[7]結果の完全な正式な記述はクックの出版後に行われた。
レヴィンはNP完全性の発見と平均ケース複雑性の開発により2012年にクヌース賞を受賞した[3]。
彼は1980年にボストン大学で教鞭をとり、現在は同大学のコンピューターサイエンスの教授を務めている。
注記
- ^ ab Levin, Leonid (1986). 「平均ケース完全問題」SIAM J. Comput . 15 (1): 285–6. doi :10.1137/0215020.
- ^ abc レビンの履歴書
- ^ ab ACM プレスリリース、2012 年 8 月 22 日 2016 年 3 月 3 日にアーカイブ、Wayback Machineより
- ^ 1971年博士論文（ロシア語）; arXivの英訳
- ^ シャシャ、デニス、キャシー・ラゼール（1995年9月）。『Out of Their Minds: The Lives and Discoveries of 15 Great Computer Scientists 』。シュプリンガー。ISBN 0-387-97992-1。
- ^ レビン、レオニード (1973)。 「ユニバーサル検索問題 (ロシア語: Универсальные задачи перебора, Universal'nye perebornye zadachi)」。情報伝達の問題 (ロシア語: Проблемы передачи информации、問題のあるペレダチ情報ii)。9 (3): 115–116。(pdf)
- ^ Boris A. Trakhtenbrot (1984). 「ペレボル (ブルートフォース検索) アルゴリズムに対するロシアのアプローチの調査」Annals of the History of Computing . 6 (4). IEEE : 384–400. doi :10.1109/MAHC.1984.10036. S2CID 950581.
参考文献
- 「レオニード・A・レビン」。数学系譜プロジェクト。
外部リンク
ウィキメディア・コモンズには、レオニード・レヴィンに関連するメディアがあります。
- ボストン大学のレビンのホームページ。
- 2012年クヌース賞はレオニード・レヴィン氏に授与される