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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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