浅野哲夫：計算幾何学

感想

最初に計算幾何学関係で手に入れたのがこの本だった。 私はこの本を十分の一も理解していないが、 アルゴリズムの不思議さについてだけは分かった気になっている。 なので、この本になぜか載っていた、計算幾何学とは直接の関係がない（と思う）、 あるアルゴリズムについて感想を述べる。

`n` 個の数の中で `k` 番目に大きな要素を求める速いアルゴリズムが紹介されているのが、 他のアルゴリズムの教科書にない、珍しい物だと思う。 なんだか難しいことが記述されていて、学者とはとかく難しいことを考えたがるものだという、 妙な感想しか出てこなかった。事実、このアルゴリズムは「悪魔のように巧妙な」という形容詞が ついているのをどこかで聞いたことがある。 それで、このアルゴリズムが実際に役に立つかどうか、少し考えてみた。 このアルゴリズムは、「15 個のデータのソートには 42 回の比較で十分であることが知られている」 という事実に基づいて組み立てられている。この「」内の事実をどのように証明するのだろうか。 ずっと気になっていたのだが、今回この稿を書くにあたって Knuth の本を調べてみた。 さすが Knuth 、この事実について詳しく調べていた。なんだか妙な図式（ダイアグラム）を書いて 漸化式を導出していた。ならば、本当なのだろう。では、 高々 42 回の比較でソートを完了するプログラムはどのようなものだろうか。 そこまで Knuth の本にはなかった。 きっと、「」内を実装したプログラムはないのだろう。そして「悪魔のように巧妙な」プログラムも 役に立たないのだろう。最後に、石畑清が書いた「アルゴリズムとデータ構造」の中からの一文を引用する。 「整列のため比較回数の下限を `n` の値それぞれについて調べる研究がある。（中略） ただし、このような最小手数の整列法を実際のプログラムに利用することはまずない。（後略）」

書誌情報

まりんきょ学問所 ＞ コンピュータの部屋 ＞ コンピュータの本 ＞ 計算幾何学 ＞ 浅野哲夫：計算幾何学