2014年4月30日水曜日

数学徒ではなくプログラマ向きの「数学ガール/乱択アルゴリズム」

このエントリーをはてなブックマークに追加
Pocket

数学ガールのシリーズの中で一つ異質な副題を持つのが、「数学ガール/乱択アルゴリズム」だ。乱択アルゴリズムは著名な数学の予想問題ではないし、聞きなれない単語だと感じる数学徒が多いと思う。実際に、シリーズの他のタイトルが理学的な内容であるのに対して、本書は工学的な側面が強いものとなっている。数学の部分はシリーズ中もっとも易しく、数学徒向けと言うより、プログラマもしくはプログラマ志望者向きと言えるであろう。

内容は条件を満たす論理値を求める命題論理式の充足可能性問題を解くランダム・ウォークのアルゴリズムと乱択クイック・ソートの二つの乱択アルゴリズムの計算量を求めるものとなっている。プログラムの話になっているため抽象プログラミング言語などが定義されたりしており、数学徒向けではないと思う。しかし、プログラマから見れば、知っておいた方が良い知識が入っている。

アルゴリズムの計算量を求めるのに必要な知識は初歩的なものから説明される。確率はモンティ・ホール問題、二項定理、二項分布、期待値などから説明されている。そして、離散問題なので微積も使わないし、モーメント母関数など確率論らしい話題は無い。解が与えられたときに多項式時間で解が正しいか分かるNP問題が、多項式時間で解を割り出せるP問題にはならないと言うP≠NP予想*1に触れているのも、プログラマの気を引きそうだ。2×2の行列の記述が浮いている感じがするのだが、これもウェブ系からモバイル端末に移りたいプログラマなどには役立つかも知れない。

読んでいて謎が残る部分は少しある。P.426でクイック・ソートと乱択クイック・ソートの計算量の表現で「平均実行ステップ数」と「実行ステップ数の期待値」を使い分けているが、クイック・ソートの計算量も乱数をソート対象とするのだから期待値であるような気がしなくも無い*2。また、乱択クイック・ソートが「どんな入力」でもn log nのオーダーとなるのは不正確であろう。全て1が並んでいるような入力がされた場合、話が変わるはずだ。これは謎ではないが、2×2の行列で話を進めるのであれば、図形を使って行列式や固有値の直観的な意味を説明しても良いように思えた。そう言えば行列の対角化できるのは実数になると思うのだが、そういう記述は無かった。

小説部分は赤毛の女の子が出てきた事以外は意外に、もう慣れてしまったのか違和感が無かった。饒舌才媛のような設定メモをコピペしてきたような描写は見られるが、今まで読んだ巻と比較すると数は少ない。多少は、伏線の類も盛り込められている。

*11971年にNPと言う問題群が定義されたので比較的新しい分野で、暗号や経路選択などコンピューターの応用に密接に関わる分野となっている(数学セミナー/2013年12月)。

*2強調されているので、著者は表現を分けた説明できるのかも知れない。

0 コメント:

コメントを投稿