2人のチューリング賞受賞者との思い出 ― Don KnuthとBob Tarjan ―

摘要

ACMチューリング賞の歴代の受賞者は60数名おり，そのうちのアルゴリズム研究者を中心に12名の方々と知り合いである.本コラムでは，お二人Donald ("Don") E. KnuthとRobert ("Bob") E. Tarjanとの思い出を記す.Don Knuthは1938年生まれで，1つ上の世代に属する.筆者は大学院生時代にはグラフ理論を用いて電気回路網の研究をしていたが，1974年に博士課程を修了した後に研究を情報の分野に変えようとしていた.当時日本の情報の理論分野では形式言語とオートマトンの研究が全盛であつたが,あえてアルゴリズムの研究を始めようと決心した.その頃アルゴリズム全般を扱う著書は世の中に存在しなかった.最初に読んだのがKnuthの例の大作のシリーズ"The Art or Computer Proeramming"のつちの1冊"Vol.3, Sorting and Searching" (1973年）である.最初からほぼ最後まで熟読したが，辞典のように巨大な本で，詳細な解析が数多く含まれ，アルゴリズムの設計法や解析手法の修得には大いに役立ったが，正直なところ離散アルゴリズムの全体像の理解には不向きだった.でも,一生涯かけてもこの1冊すら書けそうもなく,Knuthの偉大さはよく分かった.この本が出版された1年後の1974年にチューリング賞を受賞している.このシリ一ズの執筆や改訂の校正で苦労したことがTEXを開発するきつかけになっている.Knuthの著書や論文を読んではいたが，直接会つたり，手紙のやりとりをする機会はなかった.そんな中1996年に突然電子メールをいただいた.それも5, 6ページに渡る長いメールで，Obamaの次の米国大統領の単純な英語とは異なり，格調は高くきわめて難解な英語で書かれていて，意図を理解するのに長時間を要した.でも結論は単純で，「京都賞の授賞式に出席するので，京都と東京以外の仙台に行きたい.できたら温泉に行きたい」ということだった.東北大学で講演していただき，翌日に山形県米沢市の山奥にある秘湯白布高湯温泉に御夫妻をお連れし，Knuth先生と一緒に力ラオケを歌つたり，同じ湯舟に入つた思い出がある.