2009年12月29日火曜日

ファインマンに学ぶ科学的良心

年末は,ファインマンに学ぶ科学的良心.

リチャード P. ファインマンの自伝「ご冗談でしょう、ファインマンさん」の「カーゴ・カルト・サイエンス」.これは彼のカリフォルニア工科大学1974年卒業式式辞を文書化したものですが,非常に素晴らしいことが書かれています.ということで一部抜粋.


 今あげたこういう教育上の、または心理学上の研究は、実は私が「カーゴ・カルト・サイエンス(積み荷信仰式科学)」と呼びたいと思っているえせ科学の例なのです。南洋の島の住民の中には積み荷信仰ともいえるものがある。戦争中軍用機が、たくさんのすばらしい物資を運んできては次々に着陸するのを見てきたこの連中は、今でもまだこれが続いてほしいものだと考えて、妙なことをやっているのです。つまり滑走路らしきものを造り、ヘッドホンみたいな恰好のものを頭につけた男(フライトコントローラーのつもり)をその中に座らせたりして、一心に飛行機が来るのを待っている。形の上では何もかもがちゃんと整い、いかにも昔通りの姿が再現されたかのように見えます。
 ところが全然その効果はなく、期待する飛行機はいつまで待ってもやってきません。このようなことを私は「カーゴ・カルト・サイエンス」と呼ぶのです。つまりこのえせ科学は研究の一応の法則と形式に完全に従ってはいるが、南洋の孤島に肝心の飛行機がやってこないように、何か一番大切な本質がぽかっとぬけているのです。



 諸君に第一に気をつけてほしいのは、決して自分で自分を欺かぬということです。己れというものは一番だましやすいものですから、くれぐれも気をつけていただきたい。自分さえだまされなければ、他の科学者たちをだまさずにいることは割にやさしいことす。その後はただ普通に正直にしていればいいのです。
 もう一つ、これは科学にとってはさほど重大なことではないが、私が信じていることを申し上げたい。それは諸君が科学者として話をしているとき、たとえ相手が素人であっても決してでたらめを言ってはならないということです。(中略)私が言わんとしていることは、嘘を言う言わないではなく、科学者として行動しているときは、あくまでも誠実に、何ものもいとわず誠意を尽して、諸君の説に誤りがあるかもしれないことを示すべきだということです。これこそ科学者同士の間ではもちろんのこと、普通の人たちに対するわれわれ科学者の責任であると私は考えます。



 あるとき私はラジオに出演する友人と話をしていて、少なからずびっくりしたことがあります。彼は宇宙論と天文学をやっている男でしたが、この研究がどのようにして実際に応用できるかを、いかに説明すればいいかというので、頭を悩ませていました。私がつい「そうさなあ。応用できることなんか何もないんじゃないか」と言いますと、彼は「うん、実はその通りなんだ。しかしそんなことではこの種の研究に研究費が出してもらえなくなるからな」と言いました。私はこれを一種の不正直さだと考えるのです。もし科学者として立つなら、素人に自分の研究していることをよく説明し、それでも支持してくれないのなら、それは向こうの決めることなのだからしかたがないのではないか。


最近(というかちょっと前)話題になっている「事業仕分け」.それで上の話を思い出しました.
内なる世界にいれば,どうしても盲目的になりがちな気がしますが,そういう人も他の人に対し自分が何をやっているか懇切丁寧に説明しなければならないのではないかと感じました.

2009年12月26日土曜日

カオス#30 リアプノフ指数

リアプノフ指数(Lyapunov exponent)

リアプノフ指数とは,力学系において接近した軌道が離れていく度合いを表す量を表します.
1次元写像に関して,この値は非常に簡単に求めることが出来ます.
具体的な式は以下の通り.



例:

テント写像

テント写像T(x)は以下で定義されます.



パラメータaを0から2まで変化させたときのリアプノフ指数を計算してみます.



Fig.1

0≦a<1 ⇒ λ>0
1≦a≦2 ⇒ λ<0
となっている所がポイントです.

ここで,テント写像の分岐図を見てみましょう.


Fig.2

分岐図からは,a>1のとき,カオスになっていることが分かります.
これより,(強引だけど)λ>0の時,写像はカオス性を持つと予想出来ます.

ロジスティック写像

ロジスティック写像L(x)=ax(1-x)において,aを変化させた時のリアプノフ指数を求めてみます.


Fig.3 0≦a≦4
3.5≦a≦4が特にゴチャゴチャしているので,拡大してみます.



Fig.4 3.5≦a≦4

所々λ<0となっています.

さて,ロジスティック写像の分岐図はFig.5です.


Fig.5

これらを比較してみると,λ<0の時,分岐図はカオスではありません,ある周期の周期軌道に落ち込んでいます.

そんなわけで,リアプノフ指数は写像がカオス性を持つかどうかを判断するのに非常に役立つといえるでしょう.

2009年12月21日月曜日

カオス #29 クリスマスツリーの製作

----------------

クリスマスが今年もやって来る
悲しかった出来事を 消し去るように
さあ パジャマを脱いだら 出かけよう
少しずつ白くなる 街路樹を駆け抜けて

クリスマスがもうじきやって来る
うれしさをかくせない 犬や猫まで
もみの木に灯る明かりをうけて
いつもよりやさしそうな パパの目が笑ってる

クリスマスは誰にもやって来る
もしひとりぼっちでも 淋しがらずに
心に住むサンタに呼びかけて
幼い頃の夢を 思い出してごらんよ

----------------

すてきなホリデイ/竹内まりや

やってきましたクリスマス.
今年は「カオスで作るクリスマスツリー」です.

■木
ツリーは以前作ったシダのパラメータを変えることで表現してみます.

初期座標を(x0=0, y0=0)とし,以下に示す4つの座標変換の内一つを選択し,反復適用していきます.Pは選択される確率です.

xn+1=-0.08xn
yn+1=0.72yn-1
P1=1%
xn+1=-0.16xn-0.32yn
yn+1=0.4xn-0.18yn+1.6
P2=7%
xn+1=0.16xn+0.32yn
yn+1=0.4xn-0.18yn+1.6
P3=7%
xn+1=0.86xn
yn+1=0.91yn+0.65
P4=85%


Fig.1

■星,雪
これらはStar juliaというフラクタルを用いてみます(詳細は後日).

・星
m=2, n=2

Fig.2

・雪
m=1, n=1

Fig.3
このパラメータだと三角形が出来あがるので,60°ずらしたものを重ねています.

■クッキー
Gingerbread man(カオス #7 GingerbreadMan参照)が正に其のものです.


Fig.4

■飾り
いいネタが無いので,良く分からない飾りを幾つか.
グモウスキー・ミラ写像というものを使いました(詳細は後日).


Fig.5
a=0
m=0.302


Fig.6
a=0
m=-0.36


Fig.7
a=0
m=-0.237

■仕上げ
これらをいい感じに組み合わせます.


Fig.8

完成.カオスとともにクリスマス・イブ…それは予測不可能の中にある秩序を見出す喜び…

2009年12月20日日曜日

数学 #13 数値計算 #6 Lotka-Volterra方程式

Lotka-Volterra(ロトカ=ヴォルテラ)方程式

Lotka-Volterra方程式とは,捕食者と被食者の増減関係をモデル化した非線形微分方程式です.

dx/dt=x(α-βy)
dy/dt=-y(γ-δx)

x:被食者
y:捕食者
t:時間の個体数
α, β, γ, δ:正の実数パラメータ

被食者の増殖速度
dx/dt=αx-βxy
αxは,被食者が多ければ多いほど,その増加速度は大きいことを意味します,つまりαは増加に関するパラメータ.
-βxyは,被食者,捕食者が多い程,被食者の個体数が減少することを意味します(被食者が食べられる量,捕食者が食べる量はそれぞれの個体数に比例),つまりβは減少に関するパラメータ.

捕食者の増殖速度
dy/dt=δxy-γy
δxyは,被食者,捕食者が多い程,捕食者の個体数が増加することを意味します(↑の-βxyと対になっている),つまりδは増加に関するパラメータ.
-γyは,捕食者の自然現象の速度を表します,つまりγは減少に関するパラメータ.

今回はルンゲ=クッタ法で数値的に解いてみましょう.
被食者-赤
捕食者-青


Fig.1
初期値:
x0=1
y0=1
パラメータ:
α=0.9
β=0.5
γ=0.75
δ=0.25


Fig.2
初期値:
x0=1
y0=1
パラメータ:
α=1.5
β=1.5
γ=0.1
δ=0.5


Fig.3
初期値:3
x0=γ/δ=3
y0=α/β=1.8
パラメータ:
α=0.9
β=0.5
γ=0.75
δ=0.25

Fig.1を見ると,周期解になっていることが分かります.また,被食者,捕食者の位相が若干ずれていることが分かります.これは,

魚が増える→サメが食べることの出来る量が増えるので,サメは増え,魚は急激に減る→サメが食べることの出来る魚の量が減ったので,サメは自然減少する他無い→サメが減ったので,魚は増える→…

というサイクルを表しているのです.
※ここで,
魚=被食者
サメ=捕食者

Fig.2では,周期がFig.1のおよそ2倍になっています.また,個体数のピーク時は,被食者よりも捕食者の方が多いことが分かります.

Fig.3では,未来永劫 個体数が変わりません.これは,初期値がx0=γ/δ,y0=α/βでは,

dx/dt=0, dy/dt=0

となるためです.

現実におこる現象は人智を超えた複雑怪奇なものですが,こんな簡単な式によって決まっているのかもしれません,しかしそこには無秩序と秩序の狭間にあるカオスが渦巻いているのでしょう.

2009年12月19日土曜日

TopCoder Member SRM 455

Member SRM455(12/18 1:00~3:00)の報告.

・MinimalDifference(DIV2 Easy)
ある大きさの長方形の各セルに蜘蛛を設置,各蜘蛛には1ターンで東西南北の4方向の内,どの方向に進めるかが与えられる.1ターン過ぎた後,蜘蛛がいないセルはいくつあるか.

Result:Passed System Test(221.87p)

・WordsGame(DIV2 Medium)
寝落ち….
Result:Opened(0p)

・NumbersAndMatches(DIV2 Hard)
寝落ち….
Result:Opened(0p)

・Challenges
寝落ち….

Rating
1153->1155

2pしか上がりませんでした.

次回は12/23…

2009年12月15日火曜日

カオス #28 Clifford Attractor

再びClifford Attractor.少しサイケな世界をお楽しみください.


Fig.1 a=1.3, b=1.7, c=0.5, d=1.4


Fig.2 a=-1.5, b=-3.0, c=1.5, d=1.5


Fig.3 a=1.4, b=-1.4, c=0.5, d=0.8

2009年12月13日日曜日

ファインマン伝説

・学生時代,ガリ勉野郎の部屋のドアを外して地下室に隠す
・マンハッタン計画中に機密の入った金庫を開けまくる
・余りに腕が良かったので,番号を忘れた仲間から依頼されることも
・検問にむかついたので抜け穴から出る→入るを繰り返してお説教を食らう
・と思ったら今度は検閲にむかついて手紙をジグソーパズル化する.当然怒られる
・当時から物理学の大家であったボーアに「何とち狂ったこと言ってるんだ」と発言
・打楽器ボンゴの名人
・ブラジルにいた頃「明日は名物のパレードが見られますよ」と言われたがそのパレードに参加していた
・精神科医が嫌いなのでいたずらしたら兵役を免れた
・絵も得意.個展を開いたこともある
・たまたま喧嘩を目撃し,皿が飛んでるのをみて皿の運動を計算する
・その理論を元にしてノーベル物理学賞を受賞
・受賞の知らせに「何て無礼な奴なんだ,今深夜じゃないか」
・「辞退する方法はないのか?」「辞退したらもっとややこしいことになりますよ」→諦めて受け取る
・初来日の時,日本に来たんだし日本の旅館に泊まりたい!というので無理を言って宿泊場所を変更
・作法が分からないのでとりあえずヒャホゥ!と風呂に入ったら先客の湯川博士に怒られた
・別の来日時は「不敗魔」と自己紹介した

ノーベル物理学賞受賞者ファインマン伝説より,一部修正.

2009年12月7日月曜日

TopCoder SRM 454

SRM454(12/6 2:00~4:00)の報告.

・MinimalDifference(DIV2 Easy)

正整数A,B,Cが与えられる.
A~Bの数の中で,Cとの「差」の絶対値が一番小さく,その中でも最も小さい値を返しなされ.
xとyとの「差」の絶対値は,例えばこんな感じ.
x=1234, y=3443
1+2+3+4=10
3+4+4+3=14
|14-10|=4

簡単な四則演算で実装可能.計算オーダーも少ないのでちゃっちゃっと提出.
Result:Passed System Test(229.46p)

・WordsGame(DIV2 Medium)
あるNxN文字行列(String[]),N文字からなる単語(String)がそれぞれ与えられる.
文字行列には,「ある2つの行or列を入れ替える」という操作が出来る.
縦or横方向に単語が並ぶように文字行列を操作した場合,最小の操作回数を求めよ.

「文字行列への操作」を読み間違えていたので,無駄な時間を掛けてしまったです.
提出したソースは本質的には問題無かったはずですが,System Testで落とされました.

Result:Failed System Test(0p)

・NumbersAndMatches(DIV2 Hard)

ある整数(long N)をマッチ棒で表す.この際最大K本のマッチ棒を動かせたとすると,何種類の整数を表すことが出来るか.但し,動かした後の整数の桁数は動かす前と同じであるとする.

WordsGameで時間(と気合)を取られてしまったので手付かず.

Result:Opened(0p)

・Challenges

WordsGameにてサンプルすら通らないと思われるソースがあったので,サンプルを落とし込んで撃墜.
Result:Challenge Successed(50p)

Rating
1163->1153

3回連続でレーティングが下がっています.500点問題も解かないと,レーティング上昇は厳しいです.

2009年12月6日日曜日

専門書を読む #16

プログラミングのための線形代数
~p147

TopCoder 練習

12/6
ToolsBox(SRM453.5 DIV2 Easy)
MazeMaker(SRM453.5 DIV2 Medium)

MazeMakerはProblem Archiveを見ながら.

カオス #27 畑政義写像

以前,大量のアトラクタを紹介した畑政義写像でしたが,今回は,それらをアニメーション化した物を.
数々のアトラクタのパラメータを連続的に変化させることで,非常に面白い動きを見ることが出来ます.

2009年12月3日木曜日

数学 #12 数値解析 #5 van der Pol方程式

van der Pol方程式

van der Pol方程式とは,次の微分方程式です.

y''+ε(y2-1)y'+y=0

Wikipediaより,
「ファン・デル・ポール振動子とは、非線形の減衰を受けた非保存系の振動子である。」
だそうです.

今回はこれを解いてみましょう.

数値計算で求める場合,色々な手法がありますが,ここでは,
v=y'
とおき,

y'=v
v'=ε(1-y2)v-y

とすることで,2変数にしてみましょう.
さらに数値計算手法として,3次のテイラー級数を用いてみます.
即ち,

yn+1=yn+hy'n+(h2/2)y''n+(h3/6)y'''n
vn+1=vn+hv'n+(h2/2)v''n+(h3/6)v'''n

y'=vやy''=v'は上にありますし,v''=y'''やv'''は気合で求められます(少しのdと公式 そして私はあなたと微分を覚えた).

初期条件の設定
基本的に,数値計算で微分方程式を解くときは初期条件が必要です.
具体的には最初に
y0と,v0=y'0
を決めれば良いのです.

実際の計算例

以下のグラフでは,横軸にy,縦軸にv=y'をとっています.
Fig.1にベクトル場((y, v)での傾き),Fig.2に数値計算で求めた解を示します.


Fig.1


Fig.2

パラメータ:
ε=0.3
h(刻み幅)=0.01
初期値
赤(y0, v0)=(2.00092238555422, 0)
青(y0, v0)=(0.5, 0)
緑(y0, v0)=(2.5, -2.5)

さて,計算結果から以下の事が分かります.
赤の軌道…周期解になっている(以後ずっと回り続ける).
青の軌道…閉曲線(赤軌道)の“内側”を初期値としているが,赤軌道に落ち込んでいる.
緑の軌道…閉曲線(赤軌道)の“外側”を初期値としているが,赤軌道に落ち込んでいる.

このようにvan der Pol方程式の解は,十分な時間が経つとこの閉曲線上(赤軌道)を回っている点の運動とすることが出来ます.このようなattractorを“limit cycle”というようです.

今回で使った3次のテーラー級数では,刻み幅hを大きくし過ぎると,発散してしまうようなので注意.

2009年12月2日水曜日

専門書を読む #15

最近溜めていたので更新.

プログラミングのための線形代数
~p57

2009年11月27日金曜日

カオス #26 馬蹄写像

楽しい写像の御提供.

馬蹄写像

馬蹄写像は下のような2変数写像です.固定された数式では無いので,定義域,値域をそれぞれ図示しています.


Fig.1 馬蹄写像
2つの半円D1,D2と正方形Sが定義域です.図では赤のチェックの領域です(一部隠れています).
馬蹄写像を定義域全体に対して適用すると,定義域を折り曲げたような形になります.図では青のチェックの領域分です.この値域の形が馬蹄に似ているから馬蹄写像と呼ぶのです.

この写像を2回適用するとFig.2のようになります.


Fig.2

3回適用.


Fig.3

繰り返すと倍々に折り重なっていくのが分かります.また,D1,D2内に入った点は以後そこから出られなくなります(D1内の点はD1内へ,D2内の点はD2内へ写像するから).そして最終的にD1,D2内に入る点は到る所無数にあるので,初期値の極僅かな差によって最終的な挙動が全く変わります.ロジスティック写像の2次元版みたいな感じです.

疑似コードはこんな感じ.上にも書いた通り,固定された数式ではないので,別にこのような定義でなくともかまいません.


horseshoe(x, y)
if(-1/2≦x≦1/2 && -1/2≦y≦1/2) # Sに含まれる
if(-1/2≦x≦-1/8)
u=map(x, -1/2, -1/8, -5/8, 1/2)
v=map(y, -1/2, 1/2, 1/8, 3/8)
else if(1/8≦x≦1/2)
u=map(x, 1/8, 1/2, 1/2, -5/8)
v=map(y, -1/2, 1/2, -1/8, -3/8)
else # -1/8≦x≦1/8 Uの字に曲がる所
r=map(y, -1/2, 1/2, 1/8, 3/8)
d=map(x, -1/8, 1/8, π/2, -π/2)
u=r・cos(d)+1/2
v=r・sin(d)
return (u, v)
else if(dist(-1/2, 0, x, y)≦1/2) # D1に含まれる
u=map(x, -1, -1/2, -3/4, -5/8)
v=map(y, -1/2, 1/2, 1/8, 3/8)
return (u, v)
else if(dist(1/2, 0, x, y)≦1/2) # D2に含まれる
u=map(x, 1/2, 1, -5/8, -3/4)
v=map(y, -1/2, 1/2, -1/8, -3/8)
return (u, v)
else # 定義域外
return null

map(value, low1, high1, low2, high2)
return (value-low1)(high2-low2)/(high1-low1)+low2;

dist(x1, y1, x2, y2)
return sqrt(sq(x2-x1)+sq(y2-y1))



写像する様子を映像化するとこんな感じ(イメージです).

2009年11月18日水曜日

TopCoder イントロダクション

TopCoderの紹介.

■TopCoderって何ですか?
定期的にネット上で開催されるプログラミングコンテスト.世界中の人が集まりコーディングで競います.

TopCoder
http://www.topcoder.com/

沢山の大会がありますが,その中でも特に盛り上がるのがSRM(Single Round Match)です.以下,その詳細をご紹介.

■参加資格
特に無し.ただし,事前にメンバ登録しておく必要があります.詳細は略.

■使用可能言語
Java,C++,C#,VBの4つ.

■競技概要
・参加登録
大会開始3時間前から参加登録が始まります.開始5分前になると,参加者達は,ある程度レベルにばらつきが出るように20人程度のRoomに振り分けられます.
そしてコンテスト開始,以下のような流れで行われます.
・Coding Phase
制限時間75分間で3つの問題を解きます.この75分間でコードを書き,提出しなければなりません.速く提出した方が高得点となります.
・Intermission
5分間休憩.
・Challenge Phase
ここでは,Room内の相手のソースを読み,誤った出力が得られそうな(バグが出そうな)入力を与えてやります(Challenge).ここで見事撃墜(Challenge成功)すると,自分の得点が+50p,相手の得点は0p.逆にChallengeに失敗すると,自分の得点が-25p.
・System Test
提出されたプログラムが「本当に」正しいかを検証するために,主催者側が用意した入出力を用いた「テスト」を行います.このシステムテストに合格すると得点獲得,不合格(正しい出力が得られなかった)になると得点は0p.

大体このような感じです.ちなみに,これら一連の内容はArenaというJavaアプリケーション上で行われます.競技終了後,計算式に従って,各レーティングが更新されます(1p以上だったとしても,現在のレーティングから落ちる可能性がある).

また,現在の得点によって以下のように色が振り分けられます.
2200p以上の「RedCoder」になると崇められます.更に,3000p以上になると「Target」となり,赤丸の中に白丸が入ります.

レーティング
初参加
0~899
900~1199
1200~1499
1500~2199
2200~
3000~Target


是非,挑戦してみて下さい.

2009年11月17日火曜日

セルオートマトン #7 ルール5

ルール5
クラス2

時刻tでの状態■■■■■□■□■■□□□■■□■□□□■□□□
時刻t+1での状態


時刻0で白:両脇が白なら次は黒,両脇のどちらかが黒ならずっと白.
時刻0で黒:両脇が白ならずっと黒,両脇のどちらかが黒なら白-黒-白-黒-…


Fig.1 rule5

こんな感じ.時刻1以降は周期2.

2009年11月15日日曜日

TopCoder 練習

11/15
WidgetRepairs(SRM150 DIV2 Easy)
InterestingDigits(SRM150 DIV2 Medium)

8/2
TheEncryptionDivTwo(SRM445 DIV2 Easy)
TheNewHouseDivTwo(SRM445 DIV2 Easy)

8/3
FourBlocksEasy(SRM444 DIV2 Easy)
SoccerLeagues(SRM443 DIV2 Easy)
CirclesCountry(SRM443 DIV2 Medium)

2009年11月14日土曜日

TopCoder 練習

11/14
BinaryCode(SRM144 DIV1 Easy)
PrefixCode(SRM151 DIV2 Easy)

BinaryCodeは分からなかったのでProblem Archiveを見ながら.

TopCoderの詳細については後日.

2009年11月11日水曜日

ねこぢる草

たまにはアニメーションについてでも.

『ねこぢる草』

発売:2001年2月21日
原作:ねこぢる
監督:佐藤竜雄
脚本・演出:佐藤竜雄,湯浅政明
絵コンテ・作画監督:湯浅政明
時間:33分

あらすじ:
(ある日)にゃーこは,死神に魂を半分奪われてしまい元気が無くなってしまう.そんな姉(にゃーこ)を気遣い,にゃっ太はにゃーこを連れてサーカスへ.だが,2人はそこから不思議な世界に迷い込んでしまう.果たして2人は無事に帰って来れるのか…

原作者のねこぢるは,1990年に『ガロ』にて『ねこぢるうどん』でデビュー.作品の多くは猫を主人公とする形式でした.特に「にゃーこ」・「にゃっ太」の姉弟を主人公とする連作は人気が高く,一見可愛いキャラクターが繰り広げる不条理・残酷なストーリーは,一部でカルト的な人気を得ていました.彼女は1998年,自殺により31歳の若さで亡くなっています.
その後,作られたOVAが『ねこぢる草』です.

この作品ではオリジナルストーリー(あらすじ参照)を軸に『ねこぢるうどん』の各シチュエーションを織り込んであります.
夢を見ている,極端に言うと臨死体験にも似た展開は何度見ても飽きが来ません.また,短編ですので非常に密度が濃く,映像作品として完成度の高いものとなっています.ラストシーンは是非自分の目でご覧になって下さい.

ちなみにこの作品では湯浅政明の存在が大きく,彼の作品の特徴が強く表れていると思います.
詰まる所,劇場版『クレヨンしんちゃん』の作画のような,具体的には強烈なパースや特徴のある気持ちの良い動きです.







時間があれば,一度見てみることをお勧めします.

2009年11月8日日曜日

数学 #11 数値解析 #4 台形則

数値計算ネタ.

積分の近似計算です.今回も対象として,フレネル積分を用います.
しかし,計算方法が違います.今回は台形則という方法を使います.


参考までにフレネル積分(sin版).


台形則

式はこんな感じです.



式だけだと意味不明なので,図をFig.1に示します.


Fig.1 trapezoid

赤線:y=sin(x2)
青い台形一つの面積:h/2(f(xi)+f(xi+1)

台形のパラメタは以下の様に対応.Fig.1ではh=0.25です.
上底:f(xi)
下底:f(xi+1
高さ:h=x軸の刻み幅
ですので,青い台形の面積の総和をとる式を構成すると,始めに示した式が出来上がります.

また,h(刻み幅)が小さければ小さいほど,計算の精度が上がる事も分かると思います(台形がどんどん細くなり誤差が減っていく).例えば,h=1/16の時はFig.2のようになります.青の面積を全て足し合わせたものが近似値なので,精度が高くなる事が納得できると思います.


Fig.2

実際にFig.1のパラメタで計算したのがFig.3.


Fig.3
0≦x≦8
h=1/4
刻み幅が大きいので,かなりがたついています(ただ,前回の様に発散してはいません).

hを小さくすると(Fig.2と同じ)Fig.4のような感じ.


Fig.4
0≦x≦8
h=1/16

非常に滑らかになり,精度が大幅に向上しています.

2009年10月25日日曜日

カオス #25 パイこね変換

今日はパイこね変換です,変な意味はありません.

パイこね変換は以下のような2変数写像です.

φ(x, y)
=(2x, 1/2y) (0≦x≦1/2)
=(2x-1, 1/2(y+1)) (1/2<x≦1)

パイを作る時の材料をこねる操作と同じなので,こんな名前が付いています.
実際に「こね」てみましょう.

Fig.1が生贄サンプル画像です.ファックス!!ファックス!!


Fig.1

ではφ(x, y)を一回適用してみましょう.


Fig.2

伸ばして重ねます.これを繰り返し適用すると,以下の様になっていきます.


Fig.3


Fig.4


Fig.5


Fig.6

もはや原型を留めていません.ついでに計算精度の限界も来ています.

この写像の特徴は,初期値鋭敏性(初期値が極僅か違うだけでも,写像を繰り返し適用すると,その差は広がり全く違う道程となる)を持つという点です.

2009年10月20日火曜日

第20回 全国高等専門学校プログラミングコンテスト After

10/17~18にかけて第20回 全国高等専門学校プログラミングコンテストが行われました.

今回,競技部門は問題なく進行されました.また,環境に関しても,無線LANが飛んでいたので控室でストリーミング放送を見ることが出来,非常に過ごしやすかったです.プロコン関係者の方々お疲れ様でした.

さて,結果の方はというと,敗者復活戦で1位を取り復帰はしたものの,準決勝では揮わず敗退.大阪府立に実力を見せつけられました(準決勝において,マップAで34ステップを出したものの,大阪はたったの22ステップでした).

そんなわけで,Itmediaの記事です.
高専プロコンリポート:「最強最速」を見せつけた浪速の高専生 - ITmedia エンタープライズ

ちなみに,主な手法はSA(焼きなまし法)を用いたものでした.ある程度の長さのステップの系列を用意し,系列中のステップを変更させながら焼きなます,といった方法です.個人的には幅優先探索を主体とした場合,ノード数が爆発的に増えるため活用は不可,と考えていました.ところが大阪府立は上手いこと(マップのサイズ毎に)評価関数を作ったのでしょうか,短い時間でステップ数の短い解を叩き出していました.すごいです.

このような大会は非常に刺激があり,今後の開発もモチベーションアップにも繋がりました.睡眠不足にはなりましたが,非常に実のある2日間であったと思います.

2009年10月13日火曜日

ノイマン伝説

・6歳で8桁の割り算は当たり前,8歳で微積分マスターも
・ノイマンの正式名称は悪魔の頭脳
・推定IQは300,仮に東大の医学部を目指せば1週間で入れるレベル
・趣味はスカートのぞき
・同僚が一晩徹夜して解いた難問を数分で解いたため,同僚は青ざめた
・ノイマン先生の車が近付くだけで,学生たちは逃げだした,心臓発作を起こす学生も
・ENIACとの計算勝負に勝ち「俺の次に頭のいい奴が出来た.」
・水爆の効率概算は天井を向いて暗算
・ハンガリー人と思われがちだが,実は火星人
・口癖は「なかよしイケメン」
・1日4時間の睡眠時間以外は常に思考
・世界史,ゲーテの小説は一字一句間違えず暗唱できた
・割り算で答えられる問題を無限級数の和で解答するというファンサービス
・紙とペンだけでセルオートマトンの分野を開拓
・ノイマンは実はまだ数学分かってないもんな.本気で覚えたらスゲエ事になるぞ
・原子力委員会の会合には救急車で出席
・葬式にて知人曰く「ノイマンは人間ではなかった.長い間人間と一緒にいたので,真似がうまくなっただけだ.」

2009年10月11日日曜日

第20回 全国高等専門学校プログラミングコンテスト Before

今年もやってまいりました,全国高等専門学校プログラミングコンテスト.
前回は不本意な終わり方をしましたが.今年は記念すべき20回目,主管校の木更津高専その他頑張っておられると思います.

さて,競技の内容は,パズルゲームです.下記公式サイトに詳細があるのでどうぞ.

http://www.procon.gr.jp/modules/procon20/item.php?itemid=18

前回に比べて圧倒的に難しいです.人力で解くことも勿論できますが,ステップ数を短くするとなると,コンピュータに頼らざるをえませんし,最適解となると時間がかなり掛かります.そして,時間が掛かっていては他のチームに負けてしまいます.また,運の要素が無い(互いに干渉しあう要素が無い)ので,実力勝負になると思われます.

高専プロコン2009競技練習場にて,練習ができます.コルンさん(久留米高専OB)に感謝.人力モードもありますので皆さん解いてみてはいかが?

2009年10月6日火曜日

カオス #24 Clifford Attractor

数学的美.

Clifford Attractor

Clifford Attractorは以下の式で表されます.

xn+1 = sin(ayn) + c cos(axn)
yn+1 = sin(bxn) + d cos(byn)
パラメータ:a, b, c, d

初期値(x0, y0)を決め,上式を反復,プロットしていきます.

以下,一例(容量がMB単位ですので注意).


Fig.1 a=-1.4, b=1.6, c=1.0, d=0.7


Fig.2 a=-1.4, b=1.6, c=1.0, d=0.7
オーロラを思い出します.


Fig.3 a=1.6, b=-0.6, c=-1.2, d=1.6
ネオンサインを思い出します.上手くトリミングすればカッチョイイ壁紙になります.


Fig.4 a=1.7, b=1.7, c=-1.2, d=1.2
円形の内部に広がる柔らかい空間.

Fig.2~4の画素値は,(xn+1, yn+1)の色は(xn-c, yn-c)(cは適当な非負整数)の値から算出しています.これにより上のような綺麗な画像を作ることが出来ます.

今回もサイズが大きく,計算に時間がかかりました.サイズは縮小していないので2048x2048のままですが,1枚当たりの製作時間が5時間位になってしまいました.困ったものです.

2009年10月3日土曜日

GOMOKU NARABE

○×ゲーム作成後,それを基盤として作りました.

GOMOKU NARABE



Fig.1
タイトル画面.稚拙ながらも狙って作っている事が窺えます.


Fig.2
ゲーム画面.プレイイヤーはマリオとルイージを交互に配置していきます.


Fig.3
プレイヤー2(ルイージ)が勝ちました.

これを製作した後3人で合作を作り,更にその数か月後,「TETRIS for GBA」を作りました.

2009年10月2日金曜日

○×ゲーム

約3年前,事実上初めて製作したゲームです.
「TETRIS for GBA」と同じくGBAのソフトであり,言語はC,開発環境はDevKit Advanceです.

○×ゲーム

そのまんま○×ゲームです.


Fig.1
タイトル画面.「ゲーム」の文字は手書きっぽくしたようです.


Fig.2
ゲーム画面.非常にシンプルな構成です.プレイヤー1,2は交互に○×を書いていき,縦横斜めの何れか3つ揃えば勝ちです.


Fig.3
一応5本先取という形です.

スプライトの使い方等をまだ知らない状態で作ったので,1ドット単位で描画を行っています.