ラベル 数学 の投稿を表示しています。 すべての投稿を表示
ラベル 数学 の投稿を表示しています。 すべての投稿を表示

2019-12-01

2つの操作のみで全順列を列挙する:対称群のグラフ上のハミルトン路にもとづく順列生成の紹介と実装

データ構造とアルゴリズム Advent Calendar 2019の1日目の記事です。
2日目は@yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です。

6月にグレッグ・イーガン氏のHPで見つけた順列生成アルゴリズムについてブログを書きました。
そのあとに元ネタの論文1を読んでいたのですが、おもしろい順列生成アルゴリズムを含んでいたのでGoでライブラリ化してみました。

deltam/perm: Permutation generator based on group theory written in Go

自分のベンチマークでは再帰関数で実装したナイーブなアルゴリズムより33%ほど早いですが、高速さが売りというよりも「順列への最小限の操作セットのみを駆使して順列生成できないか?」という研究の流れから出てきた副産物的なアルゴリズムです。

ただその最小限の操作セットを駆使するアイデアが面白く、最終的に出来るルールが非常にシンプルで実装も短くできるのでアドベントカレンダーに乗じて紹介しようと思います。

まずアルゴリズムの背景となる論文の内容を紹介し、その結果をルール化して順列生成のプログラムを作ります。



2019-06-29

グレッグ・イーガン経由で知った順列生成アルゴリズム

SF作家のグレッグ・イーガンさんは最小超置換文字列の分散探索プロジェクトを主催しています。それ自体も興味深いんですが、解説ページで紹介されていた副産物の順列を列挙するアルゴリズムが面白かったので紹介&実装してみます。

Local Ruleのセクションで解説されている内容の紹介です。)

(追記:順列生成アルゴリズムをライブラリ化しました deltam/perm: Permutation generator based on group theory written in Go.

順列生成アルゴリズム

まず順列の順番を入れ替える写像sigma、deltaを次のように定義します。

sigma: (2,3,4,...,n-1,n,1)
delta: (3,4,5,...,n-1,n,2,1)

始点の順列を(n-2, n-3, ..., 3, 2, n, 1)として、それに対して次のルールAを繰り返し適用します。

ルールA
以下の条件をすべて満たすなら現在の順列にdeltaを適用し、そうでないならsigmaを適用する。

  1. 左端の数字がnではない。
  2. 順列中のnの右隣の数字をrとする(nが右端なら左から2番めをrとする)。左端の数字をfとし、r が 1+(f-2) mod (n-1) と等しい。
  3. 現在の順列が(1, n, n-1, ..., 3, 2)ではない。

(2番めの条件が分かりにくいので具体例を挙げると、順列(3, 1, 2, 4) ならf=3かつr=1で、1+(3-2) mod (4-1) = 1+1 = 2なので r = 1 ≠ 2となります)

始点からルールAを繰り返し適用した系列はすべての順列が一回だけ登場するものになっています。

実験

2015-08-27

SICP問題1.45の回答と説明(SICP1.3.4, ex1.45)

この記事の対象読者:『計算機プログラムの構造と解釈』を読んだことがあって、問題1.45に納得がいってないひと



1.3.4 値として返される手続き (計算機プログラムの構造と解釈 第二版)

SICPの読んでたときにけっこう苦労した練習問題。
n乗根を求めるための平均緩和法の適用回数を「実験して確かめよ」って書いてあるけど、たぶん実験だけでは分からない。回答自体はカンニング(検索)して見つけたけど、なぜそうなのかをちゃんと説明しているのを見つけられなかったので、この記事で説明してみる。


平均緩和法、不動点探索の復習


回答のまえに平均緩和法や不動点探索についておさらいしておきます。

2015-04-19

AND、ORだけではNOT回路は作れないのか

「コンピュータシステムの理論と実装」読書会のときの疑問を追っかけて考えてみました。

NotとAnd/Orからならすべての論理回路が作れることは分かりました。ではAnd、OrのみからNot回路は作れないのでしょうか?
直感的に「作れない」って感じるんですが、きちんと論理的に説明するのはけっこう難しい気がします。

ではどうやったら説明できるか。

Notは1入力1出力の回路です。まずは入力をaとおきます。最初の入力の可能性としてはa、定数0、定数1のどれかしかありません。
最初の入力から次の出力の可能性は次の表の通りです。やっぱりa,0,1のどれかになってしまいます。

入力1 入力2 And出力 Or出力
a 0 0 a
a 1 a 1
a a a a
0 0 0 0
0 1 0 1
1 1 1 1


つぎに1出力ってことを考えます。And、Orのみで回路を作るならケーブルをまとめる最後の素子はAndまたはOrのどっちかになります。そして回路の最初の入力も次の出力もa,0,1になってるので、最後の出力もやっぱりa,0,1になってしまう。
雑に図解するとこんな感じ。


途中の回路がどんな複雑でもAnd/Orのみなら中間出力も変わらないので、最後の論理素子の入力も変わらない。だから最後までNot aを作ることはできない。


……という説明を考えてみたけど、なんだかすっきりしない。背理法か何かでさっぱりと証明する方法はないのかなー。




追記:ツイートしたら@chiralさんが速攻で返信くれました。だいぶすっきりした!

2014-12-30

素数腕立て伏せ Advent Calendar 30日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ


これまでのまとめ記事を書こうと思ったけどクソメンドイっすね、書くけど。

30日目
33回で負け(合成数)


あと10回は行けたはず。TV見ながらやるのは止めよう。19日目の38.7度の熱を出してた時と同じ記録なのはアカン。

33 is the smallest number with 9 representations as a sum of 3 primes:
33 = 2+2+29 = 3+7+23 = 3+11+19 = 3+13+17 = 5+5+23 = 5+11+17 = 7+7+19 = 7+13+13 = 11+11+11
33 - Wolfram|Alpha

33は9通りの方法で3つの素数の和として表せる最小の数だと。
素数の和といえば「4以上のすべての偶数は2個の素数の和で表せる」というゴールドバッハの予想が有名ですね。
もともとゴールドバッハさんが述べたのは「5より大きな任意の自然数は3つの素数の和で表せる」という命題だったそうです。3素数の和で表せたとして、そのパターン数を求める定理は無いのかな?


ほかにWikipediaにある数学的性質ではこれが面白かった。

33 = 1! + 2! + 3! + 4!
33 - Wikipedia


素数腕立て伏せ一言メモ
明日で素数腕立て伏せACは終わりです。できれば53以上の素数で終わりたいなぁ(フラグ)。

2014-12-27

素数腕立て伏せ Advent Calendar 26日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ


忘年会に出て年を忘れてたら筋トレの習慣も忘れてたわ〜(かなり大爆笑)

26日目
48回で負け(合成数)


またしても53まで行かなかった。スポーツ的な面もあるから今度は精神統一してからやろう。掛け声とかも。
$ 48 = 4^2 + 4^2 + 4^2$、ゾロ目でキレイ。


WolframさんとこのAlphaちゃんに訊いたところ正48角形は定規とコンパスで作図可能だとのことです。

A regular 48-gon is constructible with straightedge and compass.
48 - Wolfram|Alpha

ガウスはさらに1801年に出版した『整数論の研究』において、正 n 角形が作図可能であるための必要十分条件が、n が2の冪と相異なるフェルマー素数の積、すなわち
n = 2^mFaFb…Fc(Fa , Fb , … ,Fc は全て異なるフェルマー素数、m は非負整数)
の形であることを示した[6]。
定規とコンパスによる作図 - Wikipedia

フェルマー素数は $ p = 2^{2^m} + 1 $ と書ける素数のこと。

うーんと、$ 48 = 2^4 * 3 = 2^4 * (2^{2^0} + 1) $ か。たしかに条件は満たしてますね。

ところでWikipediaにあったモール-マスケローニの定理が気になるぞ(内容と語感がいい)。





素数腕立て伏せ一言メモ
素数腕立て伏せに必要不可欠となってきているWolframAlphaですが、Wolframおじさんの孫娘Alphaちゃんと考えると非常に癒やされることに気づきました。
「WolframAlpha 萌え擬人化」で検索しても出てこないから誰か描いちゃってもいいのよ。
ちなみにMathematicaは個人的には数学ガールのミルカさんのイメージ。


2014-12-23

素数腕立て伏せ Advent Calendar 22日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ


ねむい!

22日目
29回で勝ち(素数)


いつもよりゆっくり目に腕立て伏せをしてみたらこんな記録になってしまった。
普段は勢いに任せてやってたところもあったみたい。


ところで昨日の2通りの方法で2つの平方数の和で表せる数についてごりごり計算して考えてみました。



(本屋のブックカバーを広げてミウラ折りにしておくと計算用紙として便利。ほどほどに大きい)


結局よくわかんなーい、だったですが途中まで確認した事実をアウトプットしておきましょう。自分でも忘れそうだし。

$ x = a^2 + b^2 = c^2 + d^2$ とします。まずはそれぞれの大小関係を考えてみます。

$ a \le b かつ c \le d $としておいて、b,dを考えます。b=d はありえない(2通りじゃなくて1通りになるから)。なので b<d とできる(逆でもいいけど分かりやすい順にした)。
それでこんなふうに式変形してみると c<a ってこともわかる。

\[
\begin{eqnarray}
a^2 + b^2 = c^2 + d^2 \nonumber \\
a^2 - c^2 = d^2 - b^2 \nonumber
\end{eqnarray}
\]

b<d から右辺は正数、左辺も同様なので $a^2 - c^2 > 0 $ から c<a がわかるという寸法です。
これらの条件を組み合わせると次の大小関係がわかります(ねむい、tex調べながら書くのだるい)。

\[
\begin{equation}
c < a \le b < d
\end{equation}
\]

これで大小関係はひとまず分かった。つぎは、、、最初の式をもう少し変形してみようかな。

\[
\begin{eqnarray}
a^2 + b^2 & = & c^2 + d^2 \nonumber \\
a^2 - c^2 & = & d^2 - b^2 \nonumber \\
(a - c) ( a + c ) & = & (d-b)(d+b) \nonumber \\
\frac{a + c}{d - b} & = & \frac{ d + b} {a -c}
\end{eqnarray}
\]

(2)は、、、なんかこれからもう少し何か言えそうなんだけど。
あと平方数同士の差って連続する奇数の和と等しいから、異なる範囲の連続する奇数の和が等しくなる条件は何かって問題は同値だよなぁ、とか思ったけどなむい。今日はここまでだ。


あとオンライン整数列大辞典で50,65,85を検索したらいくつか登録されてましたね。これとかそのまま。
A118882 Numbers which are the sum of two squares in two or more different ways.


素数腕立て伏せ一言メモとかどうでもいいや
ねむい

2014-12-22

素数腕立て伏せ Advent Calendar 21日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ


風邪を引いても熱が出ても構わず素数腕立て伏せやってて結局治ったわけだから、素数のお陰で全快したと言えまいか。
素数腕立て伏せ健康法、イケまいか。

21日目
50回で負け(合成数)


体力も戻ってきたみたいです。59を目指してたけど53にも届かなかったよ。


ところで50は2通りの方法で2つの平方数の和に表せす最小の数字らしいですね。(smallestttってバグってるのかななな)

50 is the smallesttt number with 2 representations as a sum of 2 squares:
50 = 1^2+7^2 = 5^2+5^2
50 - Wolfram|Alpha

ではこの条件に叶う2番めに小さい数字ってなんだろう?
まず$ x = a^2 + b^2 = c^2 + d^2 $として、a,b,c,dはそれぞれ異なる数でないといけない。(←追記:コレ違う)
では50のときは$ a = 1, b = 7 $ だったから$ a = 2 $ で幾つか計算してみよう。
2つの数の組合せを計算しないといけないけど、奇偶を考えればチェックする数が減らせますね。

\[
\begin{eqnarray}
2^2 + 7^2 & = & 53 \nonumber \\
3^2 + 6^2 & = & 45 (ダメ) \nonumber \\
5^2 + 6^2 & = & 61 (ダメ) \nonumber \\
4^2 + 5^2 & = & 41 (ダメ) \nonumber
\end{eqnarray}
\]

うーん、だめだった。では次は和の大きさも考えて候補を減らそう。和の大きい順に抑えていって目標の数より下回ったら終わりということ。

\[
\begin{eqnarray}
2^2 + 8^2 & = & 68 \nonumber \\
5^2 + 7^2 & = & 74 (最大の組合せはダメ) \nonumber \\
3^2 + 7^2 & = & 58 (残ってる組合せで最大の組合せもダメ) \nonumber
\end{eqnarray}
\]

これもダメすね。はい次!

\[
\begin{eqnarray}
2^2 + 9^2 & = & 85 \nonumber \\
7^2 + 8^2 & = & 113 (最大の組合せはダメ) \nonumber \\
6^2 + 7^2 & = & 85 (残ってる中で最大の組合せはビンゴ!)\nonumber
\end{eqnarray}
\]


おぉ、85が2番めに小さな(省略)な数らしいぞ!
たまには地道に計算してみるのもいいものだね〜。

念のため、プログラムで検算してみよう(もちろん使うのはClojure)。

user> (def squares (map (fn [x] (* x x)) (range 1 10)))
#'user/squares
user> (filter (fn [[k v]] (>= (count v) 4))
              (apply merge-with concat
                     (for [x squares, y squares :while (<= y x)] {(+ x y) [x y]})))
([65 (49 16 64 1)] [50 (25 25 49 1)] [85 (49 36 81 4)])
あれれ、85は正しいけど3番目だったみたいだ。(1,7)から(2,7)じゃなくて、(1,6)を調べれば65に行き当たってたのになー。 ということで、2通りの方法で2つの平方数の和で表せる2番めに小さい自然数は65でした(ついでに3番めは85)。


2014-12-04

素数腕立て伏せ Advent Calendar 4日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ



大寒波が来るみたいですが、あいも変わらず素数腕立て伏せを続けていきますよ。


4日目
32回で負け(合成数)


3日目は31回を目指して30回で潰れましたが、今日は31回を越えて気が緩んでしまったようです。次の37まで続ける素数力が足りなかったぜ......。




ところで3日目記事で「自然数を3つの平方数の和で表せる条件ってなんなんだろね」と書きましたが識者より情報を頂きました!



自然数$N$が三個の平方数の和で表されるための必要十分条件は、$n\ge0,k\ge0,a\in\{1,2,3,5,6\}$により、$N=4^n(8k+a)$と表されることである。逆に、$N=4^n(8k+7)$で表される自然数は三個の平方数の和で表されない。これはディオファントスの時代から研究されてきた[1]ことであるが、1798年、ルジャンドルによって証明された。

三個の平方数の和 - Wikipedia

$30=4^0(8*3+6)$となるので3平方和で表せるということですね。今日の32は$32=4^2(8*0+2)$となるので3平方和に表せる。毎度WolframAlpha先生に聞くのもアレなので3つの平方数を計算してみます。

32未満の平方数は$\{1,4,9,16,25\}$ですね。……あっれー、0を含めないと3平方和で表せなくね???

\[32=0^2+4^2+4^2\]

WolframAlpha先生も3平方和は出してくれないし...。
32 - Wolfram|Alpha

自然数に0を含めるうんぬんのアレなんですかねぇ。時間がギリになったので一旦棚上げしますが。


[2014-12-07追記]
これって単純に平方数に$0^2$を含めてなかっただけですね、自然数と0は関係ない。筋トレ直後の酸欠で脳みそがアレだったから間違えちゃった(・ω<)☆

2014-12-02

素数腕立て伏せ Advent Calendar 2日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。
素数腕立て伏せについて : サルノオボエガキ



MathJaxを導入して数式がキレイに表示できるようにしてみた。昨日のAC1日目の記事もちょいと修正してみました。すこしTeXの書き方を覚えるだけでLife Changingだなこりゃ。


2日目
37回で勝ち(素数)


昨日の素数腕立て伏せの筋肉痛のせいか、腕の曲げ角がすこし鈍角になっていたように思う。今回は素数回までいけたが、回数が多いほうが良いわけではなく限界まで続けるのがキモなので、明日は回数の多さにこだわらず鋭角に腕を曲げよう。


今日もWolframAlpha先生に37について聞いてみよう。
37 - Wolfram|Alpha

37は原子ピタゴラス数の斜辺の数であるとのこと。

\[37^2 = 12^2 + 35^2\]

斜辺が37で1辺が35ってことは、かなり鋭角な直角三角形ですね。……まさか腕をこの直角三角形の斜辺のごとく鋭角に曲げよとの啓示なのか!



素数腕立て伏せ一言メモ
最後は床に伏せることになるんで床が汚いとツライ。素数腕立て伏せを続ければクイックルワイパーする習慣がつくのでは。




【MathJax参考サイト】
Irreducible representation: MathJax in Blogger (II)
BloggerでMathJaxを使ってTeXっぽく数式を入れる方法 - Ichiro Maruta Homepage

2014-12-01

素数腕立て伏せ Advent Calendar 1日目 #prime_num_pushups

素数腕立て伏せってなんじゃ?という方はまずこちらをどうぞ。

素数腕立て伏せについて : サルノオボエガキ
素数腕立て伏せ進行状況 - Togetterまとめ

このアドベントカレンダーでは今日から毎日、素数腕立て伏せをしてその実施報告をしていきます。誰が得をするのか分からないけど、今日の昼頃に急に思い立ったのでしょうがない。インターネットでは誰かが得をすることはもう誰かがやっているので、私がやる必要はないのです。

1日目
28回で負け(合成数)。

1日目から負けとは悔しい。23回あたりで「29回までならイケるやろ」と気を抜いたのがダメだったみたい。ひさしぶりだったせいか、素数力(素数回目までがんばろうという気力)の出し方を忘れているようだ。

負けだけど、せっかくなので28をWolframAlpha先生に聞いてみよう。
28 - Wolfram|Alpha
28は3通りの方法で4つの平方数の和で表せる最小の数字。だけど3つの平方数の和で表すのは不可能だそうです。なんでだろね?(※)


素数腕立て伏せ一言アドバイス
メガネは外しておきましょう。力尽きた時に刺さります。(危なかった)


なおこのACは29日か31日まで続けます。25は5*5だからヤダ。




※ 長風呂してちょっと考えてみた。
二乗して28より小さい自然数は1〜5。28は偶数だから3つの平方数は$(偶,偶,偶)$か$(偶,奇,奇)$の組み合わせになるはず。つまり最低一つは偶数が含まれる。その偶数を$2a$として表そう。$b,c$を3つ組みの残りとして次のように式変形してみる。

\[
\begin{eqnarray}
28 = 2^2*7 & = & (2a)^2+b^2+c^2 \nonumber \\
2^2(7-a^2) & = & b^2+c^2 \nonumber
\end{eqnarray}
\]

$2a = 2 \ or\ 4$ だから $a=1\ or\ 2$。ということは次の2つの場合が不可能と言えればOKそう。

\[
\begin{eqnarray}
2^2(7-1^2) = 2^3 *3 & = & b^2+c^2 \\
2^2(7-2^2) = 2^2 *3 & = & b^2+c^2
\end{eqnarray}
\]

ここまで考えてよく分かんなくなってきたので、Wikipediaのこのページでカンニングした。
二個の平方数の和 - Wikipedia

(1)の場合は合成数についての証明に「素因数として3を平方以外で持ってる数は二平方和で表せない」とあるので大丈夫。
(2)も同じ理由で不可能。
これで証明終了できた...っぽい。

2010-09-05

素数腕立て伏せについて

「落ち着け………… 心を平静にして考えるんだ…こんな時どうするか……
2… 3 5… 7… 落ち着くんだ…『素数』を数えて落ち着くんだ…
『素数』は1と自分の数でしか割ることのできない孤独な数字……
わたしに勇気を与えてくれる」

最近やっている筋トレ法。自分で思いついたけど、わりと普通の発想だからすでにやってる人も多いかも。

もともとの疑問は「なぜ筋トレって10や5の倍数で終わらせることが多いの?」だった。5の倍数ってあんまり好きじゃないし、なんか必然性がねーよ、という感覚でした。だったら数学的に大きな意味を持つ素数の回数を単位にしたほうが自然じゃないのか、と思い至りました。

やり方
  • 普通に腕立て伏せをやる。1から順に数えながら。
  • もう限界、腕が上がらない! というとこまでやる。
  • 潰れたときの回数が素数だったら勝ち、合成数だったら負け。
  • 何に対して勝ち負けとか関係ない。勝ちを喜び、負けは猛省。

効能
  • 限界までやるので常に限界越えを目指す必要があり、筋肉増強の効果が望める
  • 腕に限界が来ていても「あと数回で素数に達する!」と思うと少しだけ力が湧いてくる(私はこれを素数力と名付けている)
  • 素数間の距離は不規則に広がっていく傾向があるので、これを続けた場合でも常に達成困難な目標を持ち続けられる


とりあえず素数腕立て伏せということで、このアイデアを実装しましたが、素数腹筋、素数背筋、素数ダッシュなどいろいろ実装例は思い浮かびますね。ただし素数スクワットは最後にこけることになるので注意が必要です(実験済み)。

Twitterでは#prime_num_pushupsというハッシュタグで実施報告をしてますが、このタグはまったくバズる気がしない。

誰とは言いませんが、「素数腕立て伏せって何なんじゃ」と問われたのでいちいちTwitterで説明するのも面倒くさいなーとおもってブログ記事にしてみました。


【追記2011.02.24】
Togetter - 「素数腕立て伏せ進行状況」
「素数腕立て伏せ」とは何か 「素数力」が腕立て回数を伸ばす - モジログ

2010-08-17

第0回『ガロアの群論』読書会、第1-3章読書ノート公開

第0回『ガロアの群論(ブルーバックス)』読書会 まとめ - ツルマウソフト

第0回『ガロアの群論』読書会というのに参加しました。もうひと月前の事なんですが、読書ノートをちゃんとまとめて無かったので、ざっくりまとめたPDFを公開します。
たぶん『ガロアの群論』を読んでないと意味不明ですが、最後の「方程式の係数」「対称式」などの相関図は読んだあとに見直すと頭の中が整理できるかなーと思います。

ガロアの群論(1−3章)読書ノート(PDFリンク)


あ、『ガロアの群論』は講談社ブルーバックスの群論初心者向け解説書です。ふつうの数学書では省いてしまうような具体的計算を丁寧にしてくれて、私のような凡人には有難い本です。数学好きで「ガロアが五次方程式に解の公式が無いことを証明して、その過程で群論が発明されたってことは知ってるけど、いまいち詳細が分からなくてすっきりしない」って人にはおすすめです。

明日(18日)、第1回『ガロアの群論』読書会があるので、急いでまとめてみました。気分は8月31日の小学生。

【定期】明日18日、第1回『ガロアの群論(ブルーバックス)』読書会を開催します!場所は前回と同じエクセルシオールカフェ赤羽東口店にて、時間は13〜15時です。飛び入り参加も歓迎です。第0回のまとめ→ http://bit.ly/9GBaxu
Twitter
追記:PDF内の相関図だけキャプチャして載せときます。あくまでザックリ。
『ガロアの群論』1−3章 各概念の相関図



2010-08-04

秀吉とMapReduce

高校のとき数学の先生がよく授業の合間に雑談をしてくれた。そのなかで聞いた豊臣秀吉の話しが面白かったのでいろいろ絡めて紹介。

あなたはいきなり鬱蒼とした森に連れてこられて、「あの山に生えている樹の本数を可能なかぎり正確に数えてこい」って命令されたらどうしますか? もちろん秀吉の話しなので部下はそれなりにたくさん居るとします。

山の表面積を計測して、ランダムに区画を選んでその中の樹を数えて、ひと山の概算をしますか?
それとも部下を何グループかに分けて麓から地道に樹の本数を数えながら登らせますか?
秀吉はどっちの方法もとらず、さらに精度が良い方法で樹の本数を部下たちに数えさせました。

それはこんな話し。

豊臣秀吉はあるとき、一つの山に何本の樹が生えているか調べるという任務を仰せつかった(理由は建築資材の見積もりだったかな?)。ひと山は広い。いちいち数えていたのでは何日経っても終わらないし、重複して数えるミスも出てくるだろう。

秀吉はどうしたか。

まずたくさんの紐を用意した。そしてその紐を部下たちに配りこう言った。
あの山にある樹に紐を縛り付けてこい、ただし一本の樹に紐は一本だけしか縛ってはいけない
たくさんの部下たちを動員してもう縛り付ける樹が見つからないほどその作業を続けた後、今度はこう言った。
樹に縛り付けた紐を解いて持ってきなさい
そして秀吉は集めた紐の数を数えてひと山の樹の本数を調べた。

これは数学における1対1対応の応用である。秀吉はとても数学的な思考力を持った武将であった」と数学の先生は最後に付け加えた。



これってMapReduceの考え方とも似てないだろうか?

MapReduceっていうのは、Googleが膨大なサーバ群で分散処理を実行するときに使われているプログラミングフレームワーク。

MapReduceでは処理するデータをKey-Valueの組みとして扱い、それをプログラマが書いたMap関数とReduce関数で処理していきます。
ラフに説明するとMap関数では「Keyの値ごとにValueをどう処理するか」を書いて、Reduce関数では「処理結果を各Keyに対してどのように集計するのか」書く感じ。


MapReduce論文(PDF)
のP.3, Figure 1の処理手順を書き出して、それに上記の秀吉の数え方を対応させてみよう。処理の詳細は同論文の”3.1 ExecutionOverview”から抜粋。
  • Input files
    • MapReduce(以下MP):処理するデータを一定サイズに切り分ける
    • 秀吉: 兵たちに紐を配る
  • Map phase
    • MR : 複数のWorkerがUser Programに従って切り分けたデータを処理する
    • 秀吉: 兵たちが山に登って木に紐を縛り付ける
  • Intermediate files
    • MR: Map phaseで処理した結果を保持する
    • 秀吉: 縛り付けられた紐(でいいのかな?)
  • Reduce phase
    • MR: Keyごとに保持された結果を集計する
    • 秀吉: 兵に命じて縛り付けた紐を回収すると同時に本数を集計。
  • Output files
    • MR: 集計結果
    • 秀吉: 紐の数すなわちひと山にある樹の本数

秀吉の方法が優れているのは動員する部下を増やせば増やすほど早く数えられるというところだろう。つまり作業の並列化によるスケールアウトができる。サーバを増やせば性能が比例して上がるWebのバックグラウンドシステムみたい。
1、2、3と数えて行く方法は並列化しづらいし、間違い防止やらで末端作業者の負担が大きい。
秀吉の方法では、末端の作業者には単純なルールを守らせるだけでミスを減らすことが出来る(一本の樹に一本の紐)。だから人員の調達も低コストで行える。
さすが後に天下を取る男、素晴らしく頭が切れて無駄がないですね。

ということで、
「豊臣秀吉は戦国時代からMapReduceを駆使する関数型武将だったんだよ!」「な、なんだってー!!」
というエントリでした。



・・・・・・正直言いまして、上記のリストがMapReduceの説明に本当に合っているのか自信がありません。あと秀吉の逸話もソースが不明です。そこらへん、コメントで教えてくれる方がいたら有難いです。m(__)m

2009-08-05

『モンティ・ホール問題』を図で解説してみる

最近、数学付いているので調子に乗って、以下で出題されていたモンティ・ホール問題という確率の問題を考えてみました(問1のノーマルなやつだけですが)。

はてな民に確率の問題を出してみよう - Pashango’s Blog
【回答編】はてな民に確率の問題を出してみよう - Pashango’s Blog


一応、問題文をWikipediaより転載。
プレイヤーは、3つのドアを見せられる。ドアの1つの後ろにはプレイヤーが獲得できる景品があり、一方、他の2つのドアにはヤギ(景品がなく、ハズレであることを意味している)が入っている。ショーのホストは、それぞれのドアの後ろに何があるか知っているのに対し、プレイヤーはドアの後ろの様子はもちろん知らない。

プレイヤーが第1の選択をした後、ホストのモンティは他の2つのドアのうち1つを開け、ヤギを見せる。そしてホストはプレイヤーに、初めの選択のままでよいか、もう1つの閉じているドアに変更するか、どちらかの選択権を提供する。プレイヤーは、選択を変更すべきだろうか


もうすでに回答が出てるんですけど、自分自身の理解を深めるために図に描いてそれぞれ計算してみました。自分も含めて数学が苦手な人って、言葉で説明されると納得いかないけど、図で説明されるとなぜかあっさり理解できてしまうことが多いような気がします(右脳左脳タイプ?)。

(Powered by ZeptoPad)

上の図では、問題のなかのクイズ回答者が取り得るすべての場合分けを樹形図で描いています。矢印の上の数字は、その先の選択をする確率を表しています。左側から、回答者が最初のドアを選んだときの場合分け(自動車、ヤギ、ヤギがそれぞれ1/3)、次に司会者が開けるドアの場合分け(最初のドアが自動車の場合は1/2になるが、ヤギだった場合は選択の余地なくヤギのドアが開けられる)、最後に選択したドアを変更するか否かの場合分け(それぞれ1/2で結果はその横に)。

図をざっと見てみてどうでしょう? 何か納得がいかないところがあるでしょうか(絵が下手というのはおいといてw)? それぞれの矢印上の確率は独立なので問題ないと思います。最初にヤギを選んだ場合、司会者が開けるドアは必ずもう一つのヤギのドアだからそれは確率1になりますね。思うにこれがモンティホール問題のミソなんじゃないですかねー。


じゃぁ、気合いを入れて計算します。
まずは右端の結果について、それぞれが起こる確率を全部計算しちゃいましょうか。左端の支点から結果に続くルート上の確率を単純に乗算すれば良いはずです(それぞれ独立な事象が同時に起こる確率だから)。

(選択したドア,開けられたドア、結果)=確率とすると、
  1. (自動車,ヤギ、変更=ヤギ)=(1/3) * (1/2) * (1/2) = 1/12
  2. (自動車,ヤギ、不変=自動車)=(1/3) * (1/2) * (1/2) = 1/12
  3. (自動車,ヤギ、変更=ヤギ)=(1/3) * (1/2) * (1/2) = 1/12
  4. (自動車,ヤギ、不変=自動車)=(1/3) * (1/2) * (1/2) = 1/12
  5. (ヤギ、ヤギ、変更=自動車)=(1/3) * 1 * (1/2) = 1/6
  6. (ヤギ、ヤギ、不変=ヤギ)=(1/3) * 1 * (1/2) = 1/6
  7. (ヤギ、ヤギ、変更=自動車)=(1/3) * 1 * (1/2) = 1/6
  8. (ヤギ、ヤギ、不変=ヤギ)=(1/3) * 1 * (1/2) = 1/6
ふー、メンドクセ。


えぇと、話しを元に戻すと、分かりたいことは「自動車を当てるためには司会者がドアを開けたときに選択を変更すべきなのか」ということ。だから計算しなきゃいけないのは「図の結果で”変更”したときに自動車が当たる確率」です。そのためには「変更=自動車の確率/(変更=自動車の確率+変更=ヤギの確率)」を計算する必要があります。

(1/6+1/6) / (1/6+1/6 + 1/12+1/12) = (1/3) / (1/2) = 2/3

ようやく答えが出ましたね。2/3です。変更した方が確率が上がるみたいですね。「変更しなかったときに自動車が当たる確率」はこれの逆(余事象)なので1-2/3=1/3で出るんですが、折角全パターンを計算したので、これも泥臭く計算してみましょう。

(1/12 + 1/12) / (1/12+1/12 + 1/6+1/6) = (1/6)/(1/2) = 1/3

出ました。やっぱり変更しないと1/3のまんまです。

結論:モンティ・ホール問題では司会者がドアを開けたあとにクイズ回答者はドアの選択を変更すべきである。


間違えないようにかなり丁寧に計算したので、自分としては納得できました。ちなみに最初のこの問題を出題されている記事の問2の場合は、場合分けの樹形図が「選択したドア=ヤギ」→「開けられたドア=ヤギ」のルートが二股に分かれちゃって、それぞれ1/2になってしまうので、最終的にドアの選択を変更しようがしまいが関係なくなっちゃうみたいですね。


こういう場合分けの樹形図は、以下の統計学の教科書でベイズの定理の条件付き確率を説明するときに出されていました。このエントリの説明はその教科書に習ったかたちになります。大学で使ってたけど、この教科書は分かりやすかったな~。

統計学の基礎
統計学の基礎
posted with amazlet at 09.08.05
J.C. ミラー
培風館
売り上げランキング: 329889



確率論はバクチの裏技から始まって、近代になってからきちんと数学的な理論付けがされて、今では金融取引からGoogleページランクまでいろいろ使われてますが、確率論が現実生活においてどのように対応しているのかということは、未だ解決されていない哲学的問題だそうです。このあいだ読んだ『統計学を拓いた異才たち』という本に書いてありました。何だかここらへんにはカイブツが潜んでそうな気配がするな-。

統計学を拓いた異才たち―経験則から科学へ進展した一世紀
デイヴィッド サルツブルグ
日本経済新聞社
売り上げランキング: 80676
おすすめ度の平均: 4.0
3 どっちつかずで煮えきらず
4 未来を予測する科学の成り立ち
3 最初と最後が面白かった
5 人間味溢れる研究者たちの横顔
4 おもしろくない統計学がおもしろく



出題されていたブログでは次にベイズの定理について解説するらしいので、楽しみに待ってます。ベイズの定理には大学の研究でだいぶお世話になったのでw

2009-08-03

Mathematical Monday

なんだか数学付いた一日でした。


最近なぜか自分の中で数学熱が再燃してます。いろいろ図書館で本を借りてきてうんうん唸りながら読んでます。今日、読み終えたのは『ファインマンさん、力学を語る』という本。




物理の本なんですが、惑星軌道のケプラーの法則を幾何学的に証明する、というファインマンさんが実際に行った講義を収録した本です。よく知らないけれど、普通は大学でこれを教えるときは微積分を使って証明するらしいんです。しかしファインマンさんはニュートンの『プリンキピア』に習って幾何学的に証明することにチャレンジしたそうです。さて微積分と幾何学とどっちが分かりやすいか? それはこの本の一節が物語っています。
「簡単なことには簡単な証明がある」と、ファインマンはその講義ノートに書きました。それから彼は、二番目の「簡単」を消して、それを「初等的」と書き直しました。
証明の筋を追うのが正直大変でした。幾何学の証明を文章で説明されると軽く混乱します。でも最後まで読んで、最初の方を読み直すとすごく分かりやすい。それに図形による説明が、なんだか奇跡のようにぴったり符合する様子が美しいと思いました。

本当をいうと、この本を読むのはこれが5,6回目で、今までは途中で挫折していました。でも今日改めて読んでみたらようやく分かった(ような気がする)。
なんだか27歳になっても分からなかったことが分かるようになるという成長の証を感じ取れると嬉しいですね。
でももう一回ぐらい読み直して見ようかな。




あともう一つ。「4で割って1あまる素数は2つの平方数の和で表される」という定理があります。たとえば、13=4*3+1=2^2+3^2、17=4*4+1=1^2+4^2、29=4*7+1=2^2+5^2などなど。
これにはDon Zagierさんのワンセンテンス証明(one-sentence proof)があります。私はこれを数学セミナーの2000年9月号の記事で初めて知ったんですが、あまりに簡潔すぎてびびりました。実際の証明はWikipediaのこの記事(一文証明の項)を参照。

実際の証明はWikipediaやこちらのテキストで確認できたんですが、なぜそうなるのかちゃんと理解できてませんでした。それで今日はガシガシ計算してようやく全部納得できました(最初記号を写し間違えて計算が合わなくて困ったのは内緒だ!)。

結果だけいうと、最初の変換の不動点はx=yですね。あと変換の場合分けを(1)、(2)、(3)と順番に名付けると、(2)→(2)または(2)→(1)→(3)→(1)→(3)→・・・という変換の順序になります。不等式を計算してみれば分かりますよ-。

いやー、計算しててちょうど上手くいくのが奇跡的に思えましたね~。それにしても謎なのはZagierさんがどうやってこれを思いついたか。世の中には恐ろしく天才な人がいるもんですねー。
ちなみにZagierさんのご尊顔はWikipedia記事で見られます。髭がプリチー。




そんなこんなで数学に頭を使った一日でした。脳が疲れたので今日はよく眠れそうですw