2012年7月29日日曜日

二元の分割数の母関数

何日か悩んで、やっと二元の分割数の母関数が分かった。そもそも分割数も母関数もよく分かっておらず、骨が折れた。数学的素養のある人には難しくないのかもしれないが・・・
   ( 1 + b      + b^2    + … )
 * ( 1 + b^2    + b^4    + … )
 * ( 1 + b^3    + b^6    + … )
   … 
 * ( 1 +    w   +    w^2 + … )
 * ( 1 +   bw   + b^2w^2 + … )
 * ( 1 + b^2w   + b^4w^2 + … )
 * ( 1 + b^3w   + b^6w^2 + … )
   … 
 * ( 1 +    w^2 +    w^4 + … )
 * ( 1 +   bw^2 + b^2w^4 + … )
 * ( 1 + b^2w^2 + b^4w^4 + … )
 * ( 1 + b^3w^2 + b^6w^4 + … )
   … 
 * ( 1 +    w^3 +    w^6 + … )
 * ( 1 +   bw^3 + b^2w^6 + … )
 * ( 1 + b^2w^3 + b^4w^6 + … )
 * ( 1 + b^3w^3 + b^6w^6 + … )
   … 
   … 

この多項式を計算して、bnwm の係数を調べれば、n 個の 黒玉(b) と m 個の 白玉(w) を分割するパターン数が得られる。

項の数が無限だから計算できないように思えるかもしれないが(自分も母関数をいろいろ調べるまではそうだった)、必要な部分は限られているので、元の式と計算途中の式から、範囲外の項は除外していけば計算できる。

試しに黒玉、白玉、ともに 3個までに限定して手計算してみると、以下のようになる。

1bb2b3 wbwb2wb3w w2bw2b2w2b3w2 w3bw3b2w3b3w3
1+b+b2+b3 1111
1+b2 1122
1+b3 1123
1+w+w2+w3 11231123 11231123
1+bw+b2w2+b3w3 11231235 12461247
1+b2w 11231246 12581259
1+b3w 11231247 125912510
1+w2 11231247 2371224917
1+bw2 11231247 24814251121
1+b2w2 11231247 24915251223
1+b3w2 11231247 24916251224
1+w3 11231247 24916361427
1+bw3 11231247 24916371529
1+b2w3 11231247 24916371630
1+b3w3 11231247 24916371631

例えば、黒玉3個、白玉1個は b3wの係数で7パターン、黒玉2個白玉2個ならb2w2の係数で9パターン、黒玉3個白玉3個ならb3w3の係数で31パターンとなり、手作業で調べた結果と一致する。

ここまで分かれば、任意の個数の黒玉白玉について、分割パターンの数を求めるプログラムを書くのはそう難しくない。Project Euler の Problem 181 がこれで解ける。

2012年7月23日月曜日

So What テスト/Grandmother テスト

『So What』 といえば、1959 年にマイルスがモーダルなアプローチを完成させた金字塔。初めて譜面を見たメンバーから「コードが書いてないじゃないですか」と問われたマイルスは、「So What (だからどうした)?」と答えたという。

・・・という話ではなくて、プラグマティズムの話。藤井聡著『プラグマティズムの作法』から。

====
■ So What テスト

「So What ?」というシンプルな問いによって、ある仕事の意義と限界を測るというもの。この問いに対して口ごもっって答えにつまるようでは、その仕事が本当に価値があるか怪しいという事になる。

これは、ソフトウェア開発の現場でも有用だと思う。

あるツールやフレームワークやプラクティスなどをプロジェクトに取り入れようとしたとき、それは何のためなのか? それによって、何がどうなるか? 誰にとって何が嬉しいのか?

答えられるのが当たり前。そう思いたいけど、意外と現場ではそうじゃなかったりする。単なる流行りとか、スノビズムとか、権威主義とか、個人的趣味とか、自己顕示欲とか、そういった事でプロジェクトに何かが持ち込まれたり何かが決められたりする事がある。(技術が好きで勉強熱心なエンジニアもそういう病気にかかったりしがちだから面倒くさい。)

こうした良く考えてみると大した意味のない仕事に労力を使うことを、「So What ?」と問うてみる習慣によってかなり回避できるのではと思う。

また逆に、本来は非常に価値のある仕事を、「So What ?」に答えられないレベルの理解で始めてしまって、結局まともな効果が上がる前に、中途半端で打ちきる破目になる事もある。(で、自分たちの未熟さを棚に上げて、「やっぱあれはダメだった」的な薄っぺらい「経験談」が語られ始めるよくあるパターン。)

これらについても、まず最初から「So What ?」を意識することで、ブレずに方向性とモチベーションを維持できるようになると思う。

あと、プロジェクトで採用することになった物事についての「So what?」には、自分だけじゃなくプロジェクトのメンバにも答えられるようになってもらった方が良い。PMから各チームリーダ、技術的キーパーソンの辺りには、特に。

たまにプロジェクト外部の権力者から横槍が入ったりする事があるけど(「ディベロッパーテストはコスパが良くわからんから中止しようや?」等)、何を何のためにやろうとしていて、顧客や会社にとって何が嬉しいのか説明できるようにしてもらう必要がある(自身が PM なら言われる間でもなく必須)。説明に関しては、後述の Grandmother テストも関連する。

つうわけで、自分の仕事について「So what?」と自問する事、その答えをプロジェクトとして共有する事によって、いつの間にかプロジェクトが変な方向に迷走したり、いくら頑張っても不毛感に苛まれるといった事を避けられるんじゃないか、というのが So What テスト。

■ Grandmother テスト

著者によると、学会で「So What ?」を放った場合、専門用語をだらだら羅列しただけの、答えになっていない応答を威圧的な態度で返される事があるという。

こういった「不誠実な」態度は別にして、専門分野に浸っているうちに、ついつい高次の目的とどう繋がっているか見失いう事もままある。これについても、ソフトウェア開発の現場で散見されると思う。

それを防ぐための思考の道具が Grandmother テスト。お婆ちゃんでも分かるように、簡単で実感の伴った説明ができるかどうかを試すというもの。本当に有意義なアイデア/仕事ならば、専門家じゃなくても一般常識と生活感覚で理解できるはずだという考え方。

これを心がけることで、例えば、一見、技術的に高度でクールだけど、良く考えると何が嬉しいのか分からなくなってくるような状況にはまるのを予防できる。

====
つう事をいろいろ書いているうちに、自分も反省しなきゃならない事を、いろいろ思い出してきた… orz
自分も若い頃は、スキルを見せたいってのが半分以上の動機であんな事とか …

2012年7月19日木曜日

『素数入門』を読んだ

Project Euler をやっているうちに、数論を勉強してみたくなって、この本を買ってみた。

LINK
『素数入門』

同じ著者による続編、『数論入門』での著者自身による前書きによると、「初等・初等整数論」って位置づけらしいけど、初等整数論の初級入門者な自分にはちょうど良い。

Project Euler でも見かける関数(オイラーのφ関数とか約数関数とか)が出てくるので、Project Eulerをやったことがある人には、けっこう面白いんじゃないだろうか。あと、こちとら一応プログラマなので、すぐにプログラムを書いて確認できる環境とスキルがあるのはラッキー。

全9章の真ん中の第5章で合同式が扱われているけど、ここをちゃんと理解するのがキーだと思った。合同式がちゃんと分からないと、後の章はほぼちんぷんかんぷんになる。つうか、欲を言えばだけど、もうちょい例題と問題を多くしてほしかった(特に合同式の割り算のあたり)。

9章あたりになると、結構むずかしくなる。フェルマーテストやカーマイケル数なんかは、一回読んだだけじゃ理解できなかった。

正直、読み急いでしまって問題を解くのをけっこう省いたが、「計算しながら理解する」のがこの本の趣向の一つでもあるので、やっぱやっといた方が良い(「計算」というか証明問題が多い気がするが)。実際に、計算してみないと、やはり腹落ちしない。そういうものなのだと思う。

2012年7月18日水曜日

GlassFish Server 3.1.2.2 を入れてみた

GlassFish Server 3.1.2.2 がリリースされたので入れてみた。

OSFedora 16
java version1.7.0_03-icedtea
  • ダウンロードサイトに行って、glassfish-3.1.2.2-ml.zip をダウンロードする
  • glassfish-3.1.2.2-ml.zip を適当なところに展開する
    → glassfish3 フォルダが生成される
  • glassfish/bin/ フォルダに移動して、startserv を実行する
    → ずらずらとログが吐かれて、正常に起動する
  • http://localhost:8080/ をブラウザで見てみる。
    → "Your server is now running"画面が表示される。
  • "go to the Administration Console."リンクから GlassFish 管理画面に移動する。
    → domain1 の初期状態が表示される
ほぼ問題なし。(※ ダウンロードサイトで、シェルスクリプトが提供されていて、GUIベースのインストーラらしいけど、うちの環境では動かなかった。別にいいけど。)

2012年7月14日土曜日

手作業でハンガリー法 Hangarian Algorithm

project euler #345 に、割り当て問題の解き方で、名前だけ聞いたことのある「ハンガリー法(Hangarian Algorithm)」ってのが使えそうなので、勉強がてらやってみた。ほぼ手作業で。

====

下の表は、問題文中のサンプル。

753183439863 
49738356379973
28763343169583
627343773959943
767473103699303

#345 は最大値を求める問題なので、それぞれの値を1000から引いて、大小関係を逆転させておく。

993947817561137 
50361743792127
713937657831417
3736572274157
233527897301697

行ごとに、最小値を行の各要素から引く。下表のように各行に少なくとも一つ 0ができる。

8568106804240 
4765904108940
2965202404140
332616186016
029466468464

同様の操作を列ごとに行う。これで行で見ても列で見ても、最低一つの 0 ができた。

8565164944240 
4762962248940
296226544140
3323220016
0047868464

上から順に行を調べて、取り消されていない 0 がただ一個だけあれば、その 0 に仮決めの印をつける(ここでは白い太字)。仮決めした 0 と同じ列の他の行に 0 がもしあれば、取り消し印(ここでは取り消し線)をつける。

8565164944240 
4762962248940
296226544140
3323220016
0047868464

同じことを列に対して行う。つまり左から順に列を調べて、取り消されていない 0 が一個だけある列ならば、その0 に仮決め印をつけて、他の列の同じ行に 0 があれば、取り消し印をつける。

(この例では、行への操作と列への操作を一巡するだけで終わったが、もしまだ仮決めにも取り消しにもなっていない 0 が残っていれば、また行の操作からやり直す。)

8565164944240 
4762962248940
296226544140
3323220016
0047868464

仮決めの 0 を含まない行に印をつける。その行に取り消しの 0 があればその列に印をつける。さらにその列に仮決めの 0 があれば、その行に印をつける。その行に取り消しの 0 が・・・って感じで、やることが無くなるまで続ける。(言葉にすると変だけど、やってみると簡単)

8565164944240
4762962248940
296226544140
3323220016
0047868464
8565164944240
4762962248940
296226544140
3323220016
0047868464
8565164944240
4762962248940
296226544140
3323220016
0047868464

印がついていない行と、印がついた列に色をつける。ただし重なっている部分が分かるようにする。ここでは重なっていない部分を橙色、重なった部分を赤の文字色にした。

8565164944240
4762962248940
296226544140
3323220016
0047868464

色がついていない部分の最小値(ここでは54)を見つけて、色がついていない値から減算し、重なっている値には加算する。色がついているけど重なっていない部分の値はそのまま。

できたら、いったん印とか色とかをクリアして、また印をつけるところからやり直す。各行、各列に一個ずつ 0 が決まったら終わり。

以下、もう一巡したところ。

8024624403700
4222421708400
24217203600
3323220070
0047868518

さらに一巡

6322922702000
2527206700
2421720360170
33232200240
0047868 688

もっかい

63229234220072
180005980
1701000288170
332322720312
0055068 760

さらに半巡して、つまり、無色の値の最小値(72)を、それぞれの無色の値から減算したところで、やっと全ての行と列に 0 が揃った。

5602202701280 
180005980
1701000288170
332322720312
0055068760

0 になっている部分の位置関係を、そっくりそのままもとの表に当てはめると、問題文どおりの値が得られる。

    863 
 383   
  343  
   959 
767    

====
euler #345 だと 15×15 のマトリクスだけど、試しに手作業(+Excel)でやってみたら、6 巡か 7 巡で、2時間以上かかったけど、まあ一応正答がでた。正直、ハンガリー法のやり方がよくわかっていなかったのでやたらと時間がかかったが、手でやった分、なんか身についた気がする。

Youtube にもハンガリー法の実演動画がたくさんあるけど、下記リンクのインドの大学の講義が、インド訛りをのぞけば一番懇切丁寧で参考になった。 Lec-16 Assignment Problem - Hungarian Algorithm

この問題は、手作業でできてしまったので、コーディングはまた今度にすることにしたけど、project euler の thread を見ると、なんだか各人各様でかなり異なるアイデアで解いている。そのうち調べて見ようと思う。特に DP を使っているやり方とか。

2012年7月8日日曜日

ちょっとBABOK でも勉強してみようかと

PMP の期限が切れて、suspended になってしまった。

60 PDUを稼がないとならないので、とりあえず見つけたのが ネットラーニングの BABOK 講座。これで 40PDU。

キャンペーン期間に申し込めたので 34,930 円で済んだが、今現在、価格を見てみると、49,900円になっている。ラッキーだった。

PMBOK が「どのように(HOW)」プロジェクトを回していくかに着目しているのに対して、BABOK はそれ以前に 「何のために(WHY)」「何を(WHAT)」を提供するかに着目した知識体系。

思えば、「何を、何のために」作ってるのか分からないまま開発が進められて、もの凄く残念な事になったプロジェクトもあったなあ(遠い目)・・・

特にベンチャー系の開発だと、新製品開発なのか受託開発なのかよく分からない変なプロジェクトが何かの拍子に立ち上がる事があって、ステークホルダー間で思惑がバラバラなまま、誰がどんな風に使って何が嬉しいのか分からないモノを開発する事になっちゃったりする事がある。

今、8章あるうちの2章までやったけど、資料はなかなかよくできている。できれば BABOK 日本語版も入手したいところだが、6,000円 もするので躊躇してしまう。とりあえず、講座で提供されている資料を当てにする事にする。

せっかくだから、単に PDU を稼ぐだけじゃなくて、現場に持って帰れるノウハウというかヒントが得られたら良いと思う。

あと4、5日で終える予定だけど、まだ 20 PDU足りないのでなんとかせねばならない。できればアジャイル関連で安いものがあれば良いのだけど。