naoya_t@hatenablog

いわゆるチラシノウラであります

グラフ理論

2-SATと強連結成分分解

ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。(ちなみにSRM464には出場している)SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみ…

graph-tool(のMacへのインストールに挫折してvagrantと戯れるの巻)

Pythonでグラフの最小カットを計算しようと思ったのだけれど、Wikipediaから拝借してきた最大フローを求めるFord-Fulkersonコードを元に書いたものでイマイチ速度が出なかった*1ので、速いと噂の graph-tool を試してみることにした。brewで入れるとか、easy…

PRML §8.3.3 例:画像のノイズ除去

【次回復々習レーン(2013/7/21開催予定)の発表資料準備】 反復条件付きモード(ICM)での画像復元 左上から順番に走査しながら、反転するとエネルギーを減らせるピクセルを反転 走査前後のエネルギー差分がεを下回ったら(あるいは10回やったら)終了 MacB…

Graphvizで描いたグラフをGIFアニメにする - 赤黒木を例に

皆さんの脳内でも赤西仁×黒木メイサが2-3-4木でいうところの3-節として内部表現されていることと存じますが、今日は赤黒木を題材にGraphvizで描いたグラフをGIFアニメにしてみたいと思います。というか単なる Graphviz入門です。いきなりGraphvizの本家ドキ…