ブログ移転しました

http://tink.elliptium.net/ここです!連載の続きもここでやっていきます. 今後もどうぞよろしくお願いいたします.

書いてみた

文字列を適当な長さで区切って diff を表示する【追記】end 引数を使うのを忘れてたので, ちょっと修正@atsuoishimoto さんには負けました. #!/usr/bin/env python # -*- coding: utf-8 -*- def limit_characters1(s, start, maximum, end=None): """ >>> fo…

ネタ募集中

今のとこ集まってるのが 圏論入門者のための代数学の初歩 K 理論 非可換確率論 Geometric Invariant Theory 量子コホモロジーと代数幾何の関係 Arakelov 幾何 変形理論, Torelli の定理 です. 2つ目以降はとある数学の変態さん大好きな follower さんから依…

帰ってきました.

ちょっと立て込んでた用事が済んで, また時間が作れそうなので明日あたりから連載を再開します. 順序の話はグラフの話にまで発展してますが, ある程度のところで収めて次の話題に行こうかと考えてます. そこで話題を募集しようかと思います. 次に取り扱って…

しばらくお休み

「順序のはなし」「グラフのはなし」「点線で楕円を描く」とそれぞれ続き物として書いてきましたが, 私事で2月頭まで忙しくなってしまったのでいったんお休みします.楽しみに待ってる人がいたら, 突然休んでしまってすみません.また2月の再開を楽しみにして…

点線で楕円を描く・まとめ

【追記・2011/01/22】最初に書いた内容に大幅に誤りがあったので, 再度編集しています. おっちょこちょいですみません.【追記・2011/02/03】修正完了. ソースコードを色々変えました.昨日、一昨日の記事には数式に間違いがあったので訂正したまとめ記事を書…

点線で楕円を描く・その2

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。 昨日の記事の続きです。昨日は計算式までは出したのですが、実際に計算せずにはいられなかったのでやってみました。Numpy とかあるのは知ってるのですが、標準の Python だけでどこま…

点線で楕円を描く

[追記] この記事には誤りが含まれています。訂正した記事はこちらです。 今日は 1 つネタをもらったので, ガチな数学をやろうと思います. お題は「点線で楕円を描く」です.円の場合は, 等角度ごとに区切って点線を書いていけば良いので簡単です. たいていの…

グラフのはなし・その11

さて前回 mro のトポロジカルソートを使った実装までできたのですが, mro の失敗が検知できない不十分なアルゴリズムで実装してしまいました.今回はその不十分なところを修正するために, 今まで 2 つ (「未探索」と「探索済」) しかなかったノードの状態を 3…

グラフのはなし・その10

さて今回は C3 アルゴリズムをトポロジカルソートで書けることを示してみましょう. 戦略 さて C3 アルゴリズムの肝は何だったかと言うと, それぞれの親クラスにとっての祖先クラスの順序と, 親クラスどうしの順序が食い違わないように, 祖先クラスを並べるこ…

グラフのはなし・その9

今日は Perl や Python のクラスの多重継承で使われているアルゴリズム C3 を紹介します.多重継承でメソッドを呼び出した場合, 複数の親クラスを持つので今呼び出しているメソッドがどの親に属しているのかを調べなければなりません. そしてその順序も決めて…

グラフのはなし・その8

さて今日は目標の1つであったトポロジカルソートのプログラムを見てみましょう. 基本的な構造は昨日の深さ優先探索 (DFS) と同じです. 今日トポロジカルソートを行う DAG (輪っか無しの矢印グラフ) はこれです. 0 -> 1 -> 3 | `-> 4 | V `-> 2 -> 5 `-> 6昨…

グラフのはなし・その7

ちょっと今日は趣向を変えて, プログラムで語ってみます.昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます. ソースコード こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG にな…

グラフのはなし・その6

さて, 今日からは探索やソートの話をしていきます.探索やソートについては以前も触れましたが, ここで簡単におさらいをしておきます. ソート (sort) とは ソートは日本語に訳すと「並びかえ」になります. 文字通りなんらかの順序でものを並べかえる作業のこ…

グラフのはなし・その5

さて今日は「順序をグラフで書こう」の話の 3 回目.今まで全順序, 半順序と扱ってきましたが, それぞれ順序のルールがかなり縛りのきついものだったので, グラフの形も分かりやすいものでした. 覚えていますか? 全順序は一直線のグラフになりましたし, 半順…

高木貞治プロジェクト・代数的整数論

高木貞治プロジェクトとは 2011年1月1日をもって高木貞治先生の著作権が切れ, 著作物の内容を様々な形で利用できるようになりました. そこで著作物の内容を Web 上で公開していくプロジェクトが開始されました.ここがプロジェクト・ホームになると思います. …

グラフのはなし・その4

だんだん連載記事を書く時刻が遅くなっている cocoatomo です。はてダの日付変更線が3:00くらいらしいので助かってます。追記: 今日は書かずに寝てしまったので、次の日の朝に更新してます。さて今日は昨日持ち越した、半順序をグラフで表現してみようという…

グラフのはなし・その3

これまで順序の話として全順序, 半順序, 前順序について書いてきました.今日はその順序をグラフで書くとどうなるか? という話をします. 全順序をグラフで では簡単な全順序を用意してそのグラフを見てみましょう.3つの点に A, B, C と名前を付けて, A ≦ B C …

グラフのはなし・その2

昨日は休講にしてしまいましたが、今日はやります。 さて、一昨日「グラフとはどんなものか?」という話をしました。次にグラフの点の順序付けの話をするのですが、話の展開をどういったペースで書けばいいのかまだ感触が掴めないので、まずは簡単な例から話…

休講

ごめんなさい. 今日は記事を書く時間が作れなかったので, 休講とさせてくださいm(_ _)m

グラフのはなし

今日は昨日までと話題を変えてグラフの話をします. でも順序の話とつながっている話なのです. どうつながっているかは追々. グラフとは? グラフと聞くと y = f(x) を xy 平面に書いたものを思い浮かべる人がいるかもしれませんが, ここで言うグラフはそのグ…

順序のはなし・その3

今日扱うのは「前順序」(preorder) です. (しつこいようですが「全順序」の typo ではないです.) 私の事情で今日は短めにします. 細かいところは端折りますが内容は漏らさずに書くので, 質問などあればコメントや Twitter ( http://twitter.com/cocoatomo ) …

順序のはなし・その2

さて今日は「半順序」の話をします. 昨日の全順序 (total order) に比べやや足りないところがあるので,「半順序」(partial order) と言います. どこが足りないかをこれから見ていきましょう. 半順序の定義 さて, まずは定義から行きましょう. 全順序のときと…

順序のはなし

古来より日本のプログラマの間には、「正月はフラクタル」という風習があります。 http://d.hatena.ne.jp/ku-ma-me/20110101/p1 ほぉ〜寡聞にして知らなんだ。じゃあ、俺は「正月は数学」という風習を始めてみようと思います。よしっ、今年のテーマは「順序 …

読書会#2に行ってきました。

まぁ色々あったりして16:00くらい開始でした。 今日やった範囲 P.66 5.2.9 から P.71 5.3.5 まで。 P.72, P.73 は各自復習(何!?)するということで、めでたく Chap5 が終わった。 分からないとこなどは Google Group に書き込みをしましょう。 内容 5.2.9 fac…

とあるブログにコメント

なぜか http://www.goodpic.com/mt/archives2/2008/01/openid_oauth.html にコメントが書けなかったので、ブログからトラックバックでコメントの代わり。以下コメント - 「エンタープライズでは、信頼性の担保されたシステム、ユーザーが前提」の項にある、…

[algorithm] その他の SSSP アルゴリズムは並列処理に向くのか?

(見ての通りの書きかけです.)

Dijkstra 法がなぜ並列処理に向かないか?

※[2010/09/21 9:00] 用語を「並列」(parallel) に統一しました. まだ「並行」「並列」「分散」の使い分けがいまいち飲み込めてないので, 変だったらツッコミをいただけると幸いです.さてここでは前のエントリで書いた Dijkstra アルゴリズム がなぜ Hadoop …

Half Adder 作ったよ

プログラミンで論理回路 - 西尾泰和のはてなダイアリー http://d.hatena.ne.jp/nishiohirokazu/20100919/1284860321西尾さんのところに面白い記事が出ていて, 何か心に火が点いたので半加算器 (Half Adder) 作ってみました.http://www.mext.go.jp/programin/…

[algorithm] その他の SSSP アルゴリズムは並列処理に向くのか?

(見ての通りの書きかけです.)