Hatena::ブログ(Diary)

cocoatomo衝動日記

2011-02-03 ネタ募集中 このエントリーを含むブックマーク

今のとこ集まってるのが

です.

2つ目以降はとある数学の変態さん大好きな follower さんから依頼が来たので, なんだか重そうなものばかりです.


自分で考えていたネタは

です.

ついでに開発の方でやりたいこととしては

  • bloggart というブログエンジンを AppEngine 上で動かしてはてダから移行.
  • Python のソース読みおよび改造

です.


結局何にするかと言うと, 最近 Twitterタイムラインでちょこちょこ上がってる圏論の具体例としての代数学について話すことにしようと思っています.


これで締め切ったわけではないので, まだまだ受け付けますよ(^-^/

それでは.

kyoro1kyoro1 2011/02/03 21:52 変態ですみませーん、てか、
ちゃんと謝ったじゃないすか〜(涙)

tmiya_tmiya_ 2011/02/04 16:40 期待しています>圏論の具体例としての代数学

cocoatomococoatomo 2011/02/05 20:36 > id:kyoro1 さん

いやぁ, すみません. 褒めてたつもりだったんですが……

> tmiya_ さん

期待に応えるよう気合い入れます.

2011-01-18 ガチな数学

[]点線で楕円を描く 02:32 点線で楕円を描く - cocoatomo衝動日記 を含むブックマーク

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。




今日は 1 つネタをもらったので, ガチな数学をやろうと思います.


お題は「点線で楕円を描く」です.

円の場合は, 等角度ごとに区切って点線を書いていけば良いので簡単です.

たいていの場合, 三角関数は標準ライブラリにあるのであまり苦労しません.

しかし楕円の場合となると, 円がつぶれた形をしているので一筋縄ではいきません.


話の流れを追いつつ, どう解決していったか見ていきましょう.

発端

募集:PIL で点線の楕円を描画するのが得意な人。つーか、arc (円弧描画)関数だけで点線が書ける人。

http://twitter.com/#!/tk0miya/status/26986376482267136

楕円の場合は角度あたりの弧の長さが均等にならないよね。つまり点線を描画するにはどうすればいいんだ? 平面幾何なんてさっぱり分からないんだから、こんなん解決できないよ!

http://twitter.com/#!/tk0miya/status/26987619082571776

@tk0miya 楕円の弧長の話ですよね? その計算は楕円積分と言って, 数学で有名な積分計算です. 円もそうですが初等関数にならないので, きっちり計算する以上に楽な方法はありません. 計算式書きましょうか?

http://twitter.com/#!/cocoatomo/status/26991426927599616

実は, この楕円の弧長を求めるという問題は数学でも大きな問題でした.

いったいこれはどんな性質を持っているのか? 三角関数のようなものなのか?

数学のはなし

これを研究していた人たちにヤコビやワイエルシュトラスがいます.

彼らは

¥begin{align*}¥begin{cases}x = a ¥cos ¥varphi ¥¥ y = b ¥sin ¥varphi¥end{cases}¥end{align*}

という楕円の周を (a, 0) から左回りにたどったときの長さを求める積分

¥begin{align*}E(k,¥quad ¥varphi) = ¥int_0^{¥varphi} ¥sqrt{1 - k^2 ¥sin^2 ¥varphi} d ¥varphi ¥¥ (k^2 = ¥frac{a^2 - b^2}{a^2}) ¥end{align*}

逆関数に着目し, その性質を調べ数学的な業績を挙げました.

その逆関数¥varphi(k,¥quad u) とするとその微分は以下のように求まります. (みなさん高校でやりましたね!?)

¥begin{align*}¥frac{d ¥varphi}{du}(k,¥quad u) &= ¥frac{1}{E’(k,¥quad ¥varphi)} ¥¥ &= ¥frac{1}{¥sqrt{1 - k^2 ¥sin^2 ¥varphi}} ¥¥ (u = E(k,¥quad ¥varphi)) ¥end{align*}

これを微分の形から差分の形に直して

¥begin{align*} ¥Delta ¥varphi &= ¥frac{¥Delta u}{¥sqrt{1 - k^2 ¥sin^2 ¥varphi}}¥end{align*}

これをさらに総和の形に直すと

¥begin{align*}¥varphi_0 &= 0 ¥¥ ¥varphi_n &= ¥varphi_{n-1} + ¥Delta ¥varphi_{n-1} ¥¥ &= ¥varphi_{n-1} + ¥frac{¥Delta u}{¥sqrt{1 - k^2 ¥sin^2 ¥varphi_{n-1}}} ¥¥ (¥varphi_n ¥approx ¥varphi(n * ¥Delta u) ¥) ¥end{align*}

となる.

なので, ¥varphi (k,¥quad u) の値を求めるときは n を十分大きく (つまり ¥Delta u = u/n 十分小さく) とれば ¥varphi の値が差分の総和を計算することで求まり,  x = a ¥cos ¥varphi,¥quad y = b ¥sin ¥varphi という計算で座標の値に戻せる.

誤差評価を行ってないので収束あたりがまだあやしいけれど, 一応目処は立った.

これからは誤差が出てしまったときの対処が残っているかな.

あとがき

こんなんでどうでしょう, tk0miya さん.

2011-01-06 大学数学の第一歩

[][][][] グラフのはなし・その2 01:46  グラフのはなし・その2 - cocoatomo衝動日記 を含むブックマーク

昨日は休講にしてしまいましたが、今日はやります。


さて、一昨日「グラフとはどんなものか?」という話をしました。

次にグラフの点の順序付けの話をするのですが、話の展開をどういったペースで書けばいいのかまだ感触が掴めないので、まずは簡単な例から話をしていくことにします。

自由な順序付け

(A)→(B)→(C)

(↑ (A) は点「○」に「A」が書いてあると思ってください。)

こんなグラフの点を順序付けるときに、何の制限も無く自由に順序を付けるとするとどんなパターンがあるでしょうか?

懐しい (苦しい?) 順列の問題ですね。答えは以下の 3! = 6 通りです。

(1)→(2)→(3)
(1)→(3)→(2)
(2)→(1)→(3)
(2)→(3)→(1)
(3)→(1)→(2)
(3)→(2)→(1)

(↑ (1) は点「○」に「1」と書いたと思ってください。)

でも1番上以外はなにか違和感がありませんか?

せっかく矢印があるのですから、それに沿った番号付けにしたいですよね?


そこで、グラフの点の順序付けです。

グラフの点の順序付け

上の例では、グラフというよりいくつかある点に自由に数字を記入して、完全に矢印のことを無視していました。

今回はそんなことはせず、矢印も考慮に入れて順序付けを考えていきましょう。

まず上の例では

(1)→(2)→(3)

が矢印を考慮した順序付けで、他は全てダメだと考えるでしょうか?

確かにそれも1つの考え方です。この考え方で順序付けすることを topological sort と言います。topology は「位相、位相幾何学」と訳されるので、位相幾何学的順序付けと言うのが直訳なのですが topological sort と言うことが多いようです。どうせ専門用語は何語で書いても難しさは変わらないので、ここではトポロジカルソートと書くことにしましょう。


ソートと探索

さて、この記事は cocoatomo が思い付くままに書いているので、突然専門用語が出てきますね(汗)

なのでここでいったん用語の整理をしておきます。


「ソート」は「並び換え」と訳されるように「(ある決まった順序に) 並び換えること」です。このときの順序はたいていあらかじめ決められたものがあります。例えばさっき出した例は自然数の小さい順で並べてますね。


そしてトポロジカルソートと関係が深いのが「深さ優先探索」です。また専門用語が出てきました。

「探索」とはグラフの全ての点や辺 (矢印) を順々に調べることです。

その調べる順序ももちろん順序と考えることもできます。

トポロジカルソートのところで、トポロジカルソート以外にも可能な順序付けがあることをほのめかしていましたが、この順序がそれです。


ところで「グラフの点や辺を全て調べる」という作業をしなくちゃいけないときはどのように考えて作業をしますか?

できるだけ作業の重複が無いようにしたいけれども、どんな複雑に入り組んだグラフでもできるだけ作業量を減らすにはどうしたらいいでしょうか?


人間だったら全体をぼやーっと見てなんとなくの順序を決めると思いますが、もしとてつもなく大きなグラフで全体を見通せない場合はどうしたらいいでしょうか?

巨大な迷路を進んでいるのと同じように、いっぺんに見えるのは全体のほんの一部でしかない状況でどうやって探索をしていきましょうか?


この状況設定が探索やソートでは非常に重要です。

なぜならコンピュータ (計算機) というのは、巨大迷路を進んでいるときのように「いっぺんに把握できる情報に限りがあり」「一歩ずつしか進めない」ような作業しかできないのです。

まとめ

だいぶ取り留めなく書きましたが、

  1. グラフの点には順序が考えられるよ、
  2. その順序付け作業に探索というものを使うよ、

という話をしたつもりです。

この言葉の関係だけ覚えておいてもらえれば大丈夫です。

反省

眠気に従ってだんだんと文章があやしくなってきてしまう……。

図や絵が少ないのはやはり読みづらいので、できる限り図を入れていきたいと思います。

あとがき

明日は「全順序、半順序、前順序をグラフで表すと?」という話をします。

たぶん明後日以降に「探索」や「ソート」について詳しくやっていきます。

やや行ったり来たりするのはご愛嬌。