ジョン・ホップクロフト：分野を育てた教科書

何百万人もの計算機科学の学生は、ジョン・ホップクロフトが研究誌に書いた文章を読んだことがないかもしれないが、彼らはほぼ全員、彼から学んでいる。ジェフリー・ウルマンやアルフレッド・エイホと名を連ねるオートマトン理論やアルゴリズムの教科書を通じてであり、それらの本は標準的なカリキュラムとして広く採用され、この分野がどのように教えられるかを形作ってきた。

管理人の息子からスタンフォードへ

ジョン・エドワード・ホップクロフトは1939年10月7日、ワシントン州シアトルで労働者階級の家庭に生まれた。父は第一次世界大戦のイギリス軍退役軍人で管理人として働いており、両親とも高校を卒業していなかった。彼はまた、シアトル・タコマ・ボックス・カンパニーの創設者であるジェイコブ・ニストの孫でもあった。限られた学歴にもかかわらず、両親は彼の知的好奇心を奨励し、彼は1961年にシアトル大学で電気工学の学士号を取得し、続いて1962年に修士号、1964年に博士号（いずれも電気工学）をスタンフォード大学で取得した。純粋数学や計算機科学の背景ではなく、この工学的な訓練が、理論的にエレガントであるだけでなく、実際に実行効率の高いアルゴリズムを生み出す彼の後の直感を形作った。

分野の教科書を構築する

ホップクロフトはプリンストン大学で助教授として学術的キャリアをスタートさせ、その後コーネル大学に移り、そこでキャリアの大半を過ごした。最終的には工学・応用数学のIBM教授の称号を保持し、学科長や工学部長などの指導的役割を務めた。コーネル大学で、彼はジェフリー・ウルマン、後にアルフレッド・エイホと共同で、形式言語、オートマトン理論、アルゴリズム設計に関する一連の教科書を執筆し、世界中の計算機科学の学生にとってデフォルトの教育テキストとなった。これらの本は既存の知識を要約する以上のことを行った。それらは漸近的複雑性解析と形式言語理論を、今日でも入門理論コースで教えられている形に体系化し、その語彙が他の場所で完全に存在する前に、この分野に共通の語彙を与えたのである。

今日も動いているアルゴリズム

教科書を超えて、ホップクロフト自身の研究は現在も活発に使用されているツールを生み出した。リチャード・カープと共に開発されたホップクロフト・カープのアルゴリズムは、二部グラフにおける最大マッチングをそれまでのどの手法よりも高速に見つけるものであり、ネットワークフローや割り当て問題における標準的な手法であり続けている。彼はまた、決定性有限オートマトンを最小化するための効率的なアルゴリズムを開発し、これはコンパイラ設計や形式検証における基礎的なツールとなった。しかし、彼の最も有名な成果はロバート・タージャンとの共同研究であり、1974年に発表された、グラフが平面であるかどうか（エッジが交差することなく平面上に描けるかどうか）をテストするための最初の線形時間アルゴリズムである。二人は深さ優先探索の体系的な使用を中心にアルゴリズムを構築し、それまで遅く場当たり的だった問題を、グラフのサイズに比例する時間で解ける問題に変えた。

チューリング賞とその共有された性質

1986年、ホップクロフトとタージャンは、「アルゴリズムとデータ構造の設計と分析における基礎的な業績」に対して、計算機科学の最高栄誉であるACM A.M.チューリング賞を共同受賞した。受賞理由は両名を共に指名しており、単一の個人のブレークスルーではなく、共同的かつ並行的な一連の業績を評価している。平面性アルゴリズムがその業績の筆頭であり、それに加えてアルゴリズム設計というより広い分野へのそれぞれの独立した貢献が評価された。

中国での第二のキャリア

チューリング賞受賞後の数十年間、ホップクロフトはそのエネルギーの多くを、アメリカ国外、特に中国における計算機科学教育の強化に向けた。彼は北京大学の計算研究フロンティアセンターの共同ディレクターとなり、上海交通大学や華中科技大学で自身の名を冠したセンターを率い、学生を指導し、アルゴリズムや、より最近ではディープラーニングの研究プログラムの構築を支援している。中国は2016年に彼に友好賞を授与した。これは、国の発展に傑出した貢献をした外国人専門家に贈られる認識であり、賞を獲得した仕事からすでに数十年が経過したチューリング賞受賞者にとっては異例の第二の人生である。

認識

ホップクロフトは1989年に全米工学アカデミーに選出され、1994年にACMフェローとなり、1986年のチューリング賞と2016年の中国友好賞に加え、計算機科学と工学における傑出した業績に対して2010年にIEEEジョン・フォン・ノイマン・メダルを受賞した。

ジョンが天才と呼ばれる理由

ホップクロフトの天才性の根拠は、単一の眩い証明にあるのではなく、より稀な組み合わせにある。分野の最高賞を受賞するほど実質的な研究貢献と、その分野の基礎を教えられる形に蒸留する比類のない才能である。平面性アルゴリズムとホップクロフト・カープのマッチングアルゴリズムは、計算機科学の理論家が真に賢いと指摘する結果であり、構造的な洞察を通じて、力ずくの探索を必要とするように見えた問題を線形または線形に近い時間へと削減している。しかし、チューリング賞の受賞理由自体が明示している正直な枠組みは、彼の最も有名な結果は彼とロバート・タージャンの共同のものであるということである。どちらの男性の受賞理由も単独では成立せず、賞はソロのブレークスルーではなく、共有された一連の業績に対して与えられた。共有されることが少なく、「天才」として称賛されることも少ない彼の第二の才能は、3つの別々の共著教科書であり、それらはあまりによく構成されていたため、分野全体がその基礎を教えるためのデフォルトの方法となった。これは個人の発明というよりは、マスターティーチングに近い知的貢献の形である。

遺産

ホップクロフトの遺産は、一つのキャリアで一致することが稀な二つの並行する軌道を走っている。アルゴリズムにおけるチューリング賞を受賞した研究記録と、中国で計算機科学教育のインフラを構築する数十年にわたる第二の人生である。この分野の歴史の中で、最も広く割り当てられた教科書の著者ほど直接的に、あるいは長く、その教え方を形作った人物はほとんどいない。1960年代から70年代にかけて計算理論の形式化を助けた男が、2010年代には北京大学でディープラーニングの学生を指導していたという事実は、彼の労働人生の異例の長さと幅について何かを物語っている。真空管に近い電気工学の時代に始まり、ニューラルネットワークの時代へと続いたキャリアでありながら、次世代に分野の基礎構造を教えるという一貫した筋道を失うことはなかった。