計算機を用いた分析
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2014/02/12 03:28 UTC 版)
計算機科学者のドナルド・クヌースは、計算機を用いて5文字の単語のことば梯子について調べた。彼は、3文字の単語では簡単すぎるし、6文字の単語では解の存在するペアが少なすぎて面白くない、と考えた。クヌースは、非常によく使われる5757個の5文字の英単語(固有名詞は含まないが、語尾変化は許す)について調べ、どの組み合わせに解が存在するかを完全に調べた。その結果、多くの組み合わせで解が存在する一方、671個の単語は1回も変形できないことが分かった。クヌースは、このような単語を "aloof"(よそよそしい)と呼んだ。実際、aloof という単語自身がそのような性質を持つ。 数学的には、グラフ理論におけるグラフを調べることに帰着される。単語を頂点とし、1回の変形で移り合える単語同士を辺で結んだグラフを考えるのである。クヌースは、5757個の頂点と14135個の辺を持ったグラフを調べたことになる。パズルを解くことは、2つの頂点を結ぶ道を見つけることに対応し、計算機を用いれば一瞬の作業である。aloof が671個あることは、孤立点が671個あることに対応する。また、2つの頂点のみからなる連結成分は103個であった。例えば、odium(憎悪)と opium(アヘン)のペアがそうであり、これらは他の単語に変形することができない。さらに、頂点の次数の最大値は25であった。すなわち、2つの単語 bares と cores が25個の他の単語と隣接しており、これより多くの単語と隣接する単語はない。
※この「計算機を用いた分析」の解説は、「ことばの梯子」の解説の一部です。
「計算機を用いた分析」を含む「ことばの梯子」の記事については、「ことばの梯子」の概要を参照ください。
- 計算機を用いた分析のページへのリンク