数学で犯罪を解決する ([著]キース・デブリン, ゲーリー・ローデン, [版]ダイヤモンド社)

数学なしには暮らせない

「数学なんて、日常生活で何の役に立つんだよ」と問われれば、「われわれは数学なしには暮らせない。知らないだけで、いつだって数学を使っているんだ」とチャーリーなら答えるだろう。チャーリーとは海外ドラマ「ナンバーズ」の主人公で、数学の天才。彼は著名な応用数学者にして、FBI の犯罪捜査に関するアドバイザーだ。

なんだ、フィクションの話か、と思われるかもしれない。もちろんドラマ自体はフィクションだが、登場する数学(のかけら)はフィクションではないし、実際に犯罪捜査に応用されている事実もあるようだ。

キース・デブリンによる「数学で犯罪を解決する」は、「ナンバーズ」で使われている数学を説明したものだ。これを読めば「ナンバーズ」自体はフィクションであっても、数学が犯罪捜査に役立つ(役立っている)ことがわかる。

数学は魔術？

ドラマの中で FBI の捜査官たちが求めるのは、数学を適用することで得られた分析の結果だ。犯人が誰なのか、どこに潜んでいるのか、どこを通って逃げようとするのか。つまりは、犯人を捕えるための決め手となる情報だ。それがどうやって導かれたものかは気にしない。劇中の捜査官たちは数学者(チャーリー)の説明を聞いて「魔術(ブードゥー)だ」とつぶやく。

シーズン 2 のあるエピソードでは、FBI が霊能力者を協力者として使う様子が描かれる。チャーリーはそれに強く反発するが、(チャーリーの兄をふくめた)捜査官たちにとっては数学者も霊能力者も同じに見えているのだ。どちらも彼らには理解できない仕組みで隠された情報を暴く。

充分に発達した科学技術は魔術と見分けがつかない、と言ったのはクラーク(→「クラークの三法則」)だが、数学はその最たるものかもしれない。

数学とはパターンを見つける方法

なぜ、数学を用いることで人の行動(犯罪者の逃走経路とか潜伏場所とか)を予測したり、言い当てることができるのだろう？

「画像エンハンス」(Chapter 5) のように犯罪捜査(と裁判)の直接的な証拠となる応用例もあるが、「ナンバーズ」で用いられる数学の多くは人の行動を分析し予測するものだ。典型的なのはドラマの第1話の連続殺人犯の活動拠点(自宅と勤務先)の場所を絞り込む手法だろう(Chapter 1)。

このエピソードでは、スプリンクラーから飛び出す水滴が落ちた場所からスプリンクラーの位置をつきとめる、という例え話で説明されている。同様に、複数の犯行現場から犯人の活動拠点をつきとめられる、というのがチャーリーの主張だ。物理法則だけにしたがう水滴と、自らの意思を持つ人の行動を同列に扱うことができるのはなぜだろう？

その根拠となるのは人の行動には(たとえ本人がランダムに見せかけようとしたとしても)パターンが現れる、というものだ。加えて、人は「ランダム＝バラバラ」という偏見を持っている。犯行を重ねれば重ねるほどその場所は拠点の中心として同心円状に散らばっていく(実際の地理では地形や建物の状況、交通事情もあり円にはならない)。

完全にランダムなデータからはどんなパターンも読み取ることはできない。けれど、人の行動は(そこに意思がからむ以上)完全なランダムにはなりえない。そこには必ずパターンが生まれる。そして数学はパターンを見つけることに長けた人々が築き上げてきた体系だ。パターンを見つけ、記述するための道具がそこにはある。

数学を知らなくても暮らせる

たしかにチャーリーの言うように、現代の生活では様々な面で数学が使われている。けれど、その恩恵を享受するだけなら数学を知る必要はない。インターネットで買い物をするのに暗号の仕組みを知る必要はない。微分方程式が解けなくたってクルマの運転に支障はない。これは数学に限らず、人類がこれまで蓄積してきたあらゆる知識体系について言えることだ。iPhone のアプリを使うのにプログラミングの技術が必要ないのも同じ理屈だ。

もちろん、日常の生活の中でもパターンは生まれる。自分と自分の周囲のできごとを分析することでパターンを見つけ、将来に起きることを予測できるはずだ。しかし、そうする人は少ない。というか、そんな人はほとんどいないだろう。なぜなら、コストに見合わないから。データを収集し、分析し、パターンを見つけ、将来を予測する。どのステップにもコストがかかる。個人の生活では、そのコストに見合うだけの予測が必要になる場面はほとんどない。

(チャーリーのような)数学の天才は別として、「数学が役に立つ」ではなくて「(自分で)数学を知っていることが役に立つ」場面というのは、日々の暮らしの中では見つけられないだろう。数学はオモシロイんだけどな。

参考文献

数学で犯罪を解決する

キース・デブリン, ゲーリー・ローデン
ダイヤモンド社 ( 2008-04-11 )
ISBN: 9784478004203

物読みファイル (別館)で詳細を見る

「ナンバーズ」は DVD で観ることもできる。以下は「数学で犯罪を解決する」に数学的あらすじが解説されているシーズン 3 までのもの。シーズンを重ねるごとに数学風味が薄れてくるように思う。ま、それは仕方ないことか。

ナンバーズ 天才数学者の事件ファイル シーズン1

ロブ・モロー, デビッド・クラムホルツ, ジャド・ハーシュ, アリミ・バラード, サブリナ・ロイド / パラマウント ホーム エンタテインメント ジャパン ( 2009-06-12 )

物読みファイル (別館)で詳細を見る

ナンバーズ 天才数学者の事件ファイル シーズン2 コンプリートDVD-BOX

ロブ・モロー, デビッド・クラムホルツ, ジャド・ハーシュ, アリミ・バラード, サブリナ・ロイド / パラマウント ホーム エンタテインメント ジャパン ( 2009-08-07 )

物読みファイル (別館)で詳細を見る

ナンバーズ 天才数学者の事件ファイル シーズン3 コンプリートDVD-BOX Part 1

ロブ・モロー, デビッド・クラムホルツ, ジャド・ハーシュ, アリミ・バラード, ナビ・ラワット / パラマウント ホーム エンタテインメント ジャパン ( 2010-06-11 )

物読みファイル (別館)で詳細を見る

ナンバーズ 天才数学者の事件ファイル シーズン3 コンプリートDVD-BOX Part 2

ロブ・モロー, デビッド・クラムホルツ, ジャド・ハーシュ, アリミ・バラード, ナビ・ラワット / パラマウント ホーム エンタテインメント ジャパン ( 2010-07-09 )

物読みファイル (別館)で詳細を見る

関連リンク

• クラークの三法則 (Wikipedia:ja)

素数を列挙する #2

前回の続き。

素数表の検索にバイナリサーチを使う

前回、素数の判定法としてはもっとも素直な「√n 以下の整数で割る」よりは割り算が少なくなると考え、素数表を使った「√n 以下の素数で割る」方法を実装してみた。ところが、列挙範囲の素数表が完成している場合であっても(つまり割り算は一度も行わない)、「√n 以下の整数で割る」方が速いという結果になった。

その原因は Array#include? を使った素数表の検索にあるのではないかと考え、今回は検索に「バイナリサーチ(二分検索)」を使ってみることにした。

(listprimes_binsearch.rb より)
def ($primes).binsearch(n)
  len = self.size
  first = 0
  last = len - 1
  while len > 0
    mid = first + len / 2
    v = self[mid]
    if n == v
      return true
    elsif n < v
      last = mid - 1
    else
      first = mid + 1
    end
    len = last - first + 1
  end
  false
end

結果として、Array#include? を使ったものより高速になったことはもちろん、(素数表が完成していれば)列挙する範囲によっては「√n 以下の整数で割る」ものよりも速くなった。とはいえ、やはり素数表を生成しながらの場合は、比較にならないほど遅い。

• listprimes_binsearch.rb

エラトステネスの篩

素数表の生成でもう少し速そうな方法を試してみることにした。有名な「エラトステネスの篩」だ。コードを以下に示す。

「√n 以下の素数で割る」版、「篩」版、そして「シンプルに √n 以下の整数で割る」版を実行してみた結果は以下のようになった。

[imac] mnbi% rm primes.txt
[imac] mnbi% time ./listprimes_binsearch.rb 100000 100
START (99991):
100003 (66)
100019 (66)
100043 (66)
100049 (66)
100057 (66)
100069 (66)
Elapsed: 0.000275
./listprimes_binsearch.rb 100000 100  17.60s user 0.02s system 100% cpu 17.601 total
[imac] mnbi% time ./listprimes_sieve.rb 100000 100
100003
100019
100043
100049
100057
100069
Elapsed: 0.019148
./listprimes_sieve.rb 100000 100  0.02s user 0.00s system 83% cpu 0.033 total
[imac] mnbi% time ./listprimes_simple.rb 100000 100
100003 (158)
100019 (158)
100043 (158)
100049 (158)
100057 (158)
100069 (158)
Elapsed: 0.00028
./listprimes_simple.rb 100000 100  0.01s user 0.01s system 89% cpu 0.020 total

「篩」版は確かに速いが、「シンプル」版はさらに速い。

もっとも、これは表示させる領域を大きな数を基点として「狭めて」いるから起きることだ。1 から 100000 までの範囲の素数を列挙するなら「シンプル版」の方が遅くなる。

一番、速いのは

範囲(それも比較的大きな数から始まるものを)を指定して列挙させる場合、速いのは「√n 以下の整数で割る」方法をシンプルに実装したものだ。2 から始まる素数表を生成する方式では、範囲の上限に至るまでのすべての素数を生成する分不利になる。

たとえば、画面に一定範囲にふくまれる素数を表示する(だけの)アプリを作るとしたら、素数表を作る方式は適さないことになる。画面に表示できる範囲は限られているのだから、素数表を(作って)保持しておくより、見えている分だけをシンプルな方法(√n 以下の整数で割る)で判定する方がずっと素早く表示できるはずだ。

関連リンク

• エラトステネスの篩 (Wikipedia:ja)
• 二分探索 (同上)

関連記事

• 素数を列挙する

素数を列挙する

プログラミングの練習。指定された範囲にある素数を列挙するプログラムを作ってみる。

素数表を使った判定

利用するアルゴリズムは自明のもの。つまり、正整数 n に対して √ n を超えない素数で割り切れるかどうかをチェックしている。初回の実行では 2 (最小の素数)から始めて素数表を作っている。実行中に作った素数表は最後にファイルに書き出す。2 回目以降の実行では、以前に作った素数表を読み込んでいる。

列挙した素数の後にカッコ付きで表示する数字は計算回数だ。

検証

念には念を入れて、listprimes.rb で作られた primes.txt を検証する。以下がそのプログラムだ。素数を判定するアルゴリズムは大して変わっていない(素数表を使わず √ n 以下の整数で割り切れるか否かをチェック)から、どちらかと言えばプログラムのバグを確認するためのものというべきだ。

実行結果

[imac] mnbi% ls primes.txt
ls: primes.txt: No such file or directory
[imac] mnbi% ./listprimes.rb 1000 50
START (2):
1009 (12)
1013 (12)
1019 (12)
1021 (12)
1031 (12)
1033 (12)
1039 (12)
1049 (12)
Elapsed: 0.00011
[imac] mnbi% tail primes.txt
991
997
1009
1013
1019
1021
1031
1033
1039
1049
[imac] mnbi% ./listprimes.rb 1000 50
START (1049):
1009 (0)
1013 (0)
1019 (0)
1021 (0)
1031 (0)
1033 (0)
1039 (0)
1049 (0)
Elapsed: 0.000444

初回の listprimes.rb の実行で、primes.txt が作られ、2 回目の実行では、(素数判定のための)計算がされていないことが(計算回数の表示から)読み取れる。意外なことに計算のない 2 回目の方が時間がかかっている。

「√ n 以下の整数」を使うより「√ n 以下の素数」の方が計算回数がぐっと少なくなると考えて素数表を使うようにしたんだが、実際のところでは素数表(配列)の操作にかかる時間の方が律速段階になっているようだ。素数表を使う方法で 2 回目以降の実行(つまり割り算は一切ない)でも、Time で計測してもわかるほどの差が出る。

素数表の検索を工夫すれば逆転するだろうか？

関連リンク

• 素数 (Wikipedia:ja)

2^64 (2 の 64 乗) って、どれぐらい？ (続き)

概算で良ければ、こんな方法で桁数を知ることもできる。2¹⁰ (= 1024) ≒ 10³ (= 1000) だという事実を使う。

2⁶⁴ = 2⁴ * 2⁶⁰
= 16 * (2¹⁰)⁶
≒ 16 * (10³)⁶
= 16 * 10¹⁸
= (6 + 10) * 10¹⁸
= 6 * 10¹⁸ + 10 * 10¹⁸
= 6 * 10¹⁸ + 10¹⁹

前半は 19 桁の数、後半は 20 桁の数(それも 1 の後に 0 が 19 個続くもの)なので、足しても 20 桁になる。なので、2⁶⁴ の方も、(少なくとも) 20 桁だとわかる。これなら、対数のことなんて思い出さなくても計算できる。

この程度で十分、実用になることもある。20 桁で最小の数は 10¹⁹だ。なら、1 から始めてここまで数えるのに必要な時間は何年か？

10000000000000000000 seconds
-> 2777777777777777 hours
-> 115740740740740 days
-> 317097919837 years

317,097,919,837 年。3100 億年以上。前回、正確な 2⁶⁴ の値で計算した 5800 億年以上にくらべたらかなり差があるけれど、どちらにせよ、宇宙が終わるぐらいの時間が必要だってことはわかる。1 億人で分担して並列に数えても、3100 年、10 億人で 310 年、...。これだけのスケール感がわかれば実用的には十分だ。

ところで、IT の世界では、これよりもっと大きな数を割り当てているものがある。それは IPv6 のアドレス。アドレスを 128 ビットで表すから、実に 2¹²⁸ 個もあることになる。

じゃ、2¹²⁸ って、どれぐらい？

関連リンク

• IPv6 (Wikipedia:ja)

関連記事

• 2^64 (2 の 64 乗) って、どれぐらい？

2^64 (2 の 64 乗) って、どれぐらい？

現行の Mac に搭載されている OS、Snow Leopard は 64 ビット OS だと言われる。この 64 ビットって、いったいどれぐらいの数なんだろう？

64 ビットの「ビット」は 2 進数で 1 桁のこと。普段、わたしたちが日常生活で使う 10 進数では 1 桁で 0 〜 9 までの整数を表現できる。2 桁なら 99 まで、3 桁なら 999 まで、...。一般に、10 進 n 桁で 10ⁿ - 1 までの整数を表現できる。同様に、2 進 n 桁では 2ⁿ -1 までだ。つまり、64 ビットなら 2⁶⁴ - 1 が最大の数となる(符号なしの場合)。

では、この 2⁶⁴ (あるいは 2⁶⁴ - 1) って、いったいどれぐらいの大きさなんだろう？

(プログラマじゃない)普通の人々は 2 進数を扱うことがほとんどないから、2ⁿ と言われてもピンとこないだろう。いや、普通じゃない人(プログラマ)だって、2⁸ や 2¹⁶ ならともかく、2⁶⁴ の大きさは実感できない。わたしたちが数の大きさを実感するには、扱い慣れた 10 進数でなければならない。10 進数なら、桁を千、万、億、それに兆(英語ではちょっとスケールがずれるけど、thousand、million、billion、trillion といったところか)と読んでいくことで(それなりに)実感できる。

では、2⁶⁴ が 10 進数で何桁になるかを求めてみよう。それには「対数」を使う(底を10とする常用対数)。基本となるのは、(10進数で) n 桁の数 A に対して以下が成り立つこと。

10^n-1 ≦ A ＜ 10ⁿ ⇔ n-1 ≦ log₁₀ A ＜ n ...... (1)

つまり log₁₀A が計算できれば、その桁数がわかる。今の場合、log₁₀(2⁶⁴) を求めれば良いことになる。

さあ、受験数学を思い出しつつ、計算してみよう。

対数: 底の変換

計算に必要なのはこの公式だ。

log_ax = log_bx / log_ba

この特別な場合として、b -> x (ただし x ≠ 1)とすれば、以下の公式も導ける。

log_ax = 1 / log_xa

なぜ、底の変換を行うか、と言うと、2⁶⁴ に対して底が 2 の対数を求めることは簡単だからだ。対数の定義から、log₂(2⁶⁴) というのは、2 を何乗すれば 2⁶⁴ になるか、という数のことだ。つまり、これは 64。一方で、log₁₀2 なら対数表に載っている。

これで材料がそろった。

log₁₀(2⁶⁴) を計算する

底の変換公式と log₁₀2 ≒ 0.30103 (これは常用対数の対数表から読み取る) から、log₁₀(2⁶⁴) の値を計算すると、

log₁₀(2⁶⁴) = log₂(2⁶⁴) / log₂10
= log₂(2⁶⁴) * log₁₀2
≒ 64 * 0.30103
= 19.26592

この結果と式 (1) をあわせると、2⁶⁴ が(10進数で表すと) 20 桁の数になることがわかる。それより 1 少ないだけの 2⁶⁴ - 1 も同じく 20 桁の数だ。

ここまでは、紙と鉛筆があれば計算できる(log₁₀2 の値さえ覚えていれば)。けれど、20 桁の数とわかったところで、まだその大きさはピンとこない。

理性の限界 -- 不可能性・不確定性・不完全性([著]高橋昌一郎, [版]講談社現代新書) #2

(第三章; p.227)
当時の数学者にとっては、不完全性定理が「完全犯罪」の証明のように見えたかもしれません。
　実際に、ゲーデルの方法は、真犯人だとわかっていながら、いかなる司法システム S も立証できない犯罪 G を生み出したイメージに近いのです。(…中略…)
　これをいくら繰り返して新たな司法システムを作っても、ゲーデルの方法を用いて、そのシステム内部でとらえきれない犯罪を構成できるのです。

ホームズがいくら経験を積んでも、常にモリアティ教授の方が一枚上手だってことですね。わかります。

不完全性定理の説明として、これほどイメージが捉えやすいものはないな。どれほど巧妙にシステムを構築したとしても、スルリとその網を抜けてしまうヤツがいる。

理性の限界――不可能性・不確定性・不完全性 (講談社現代新書)

高橋 昌一郎
講談社 ( 2008-06-17 )
ISBN: 9784062879484
おすすめ度:

物読みファイル (別館)で詳細を見る

MediaMarker

ところで、(ゲーデルの)不完全性定理の説明について、これまでこう思ってきた(↓)

「とはいえ、これは自然数論の話じゃん。他のシステム(たとえばヒトの知能)とかには関係ないよねえ」

世の中、そんなに甘くないらしい。

手書きメモはスキャンして貼る

数式が混じったメモやノートを Mac や PC で作るのはメンドウだ。ワープロを使ったり、TeX に頼るっていう手もあるけど、どうしても入力のスピードで手書きに劣る。本を書くとかなら手間に見合うと思うけど。

いっそ、手書きでも良いじゃないか。今はスキャンという手段があるのだ。紙と鉛筆(ペンの方がスキャンに向いている)で、じゃかじゃか書いて、ささっとスキャン。あとは Picasa に上げてブログに貼り付け。検索の手は届かないけど、どうせ数式なんて検索できない。計算の目的や理由をブログのテキストで書くなり、画像の説明に付ければ十分だろう。

そんなわけで、ちょっと手書きの計算メモを貼りつけるテスト。Picasa だと画像の説明が埋め込まれないんだよな。改良を希望するぞ > Google

送信者 taocp

関連記事

• スキャナは楽し

Mac mini に Maxima をインストール

ふと思い立って、Maxima をインストールしてみることにした。 まずは Mac mini (Server) でやってみた。

ちなみに、Maxima っていうのは GPL で配布されているフリーな数式処理システムだ。「はじめてのMaxima」によれば、

Maxima は 1960 年代の MIT の MACSYMA プロジェクトで開発された「MACSYMA」(MAC's SYmbolic Manipulation system) の「DOE(エネルギー省)版」を、Texas 大学のシェルター氏 (Schelter) が「Common Lisp: The language 第一版」に対応した「gcl」に移植したものです。

ということだ。手元にあるかなり古い雑誌(「インターフェイス」増刊の「archive」No.12) によれば、Maxima の前身である Macsyma の作成が開始されたのが 1966 年。1972 年に ARPA ネット(!) を通じて全米で使用可能となって、さらに一般で購入可能となったのが 1982 年だとのこと(ちなみに、同誌によれば現在数式処理ソフトとして有名な Mathematica の最初の版ができたのが 1988 年だそうな)。なかなかに歴史のあるソフトだ。

インストールを始める前はつまづくとは思っていなかった。MacPorts でインストールできるだろうと思っていたから。sudo port install maxima で後は待つだけ、そう高をくくっていた。世の中、そうそう甘くない。