転倒数と測度の話

数学

転倒数について調べてたらwikipediaに気になる記述があった。

列の転倒数 (inversion number) は、その整列性の測度として広く用いられる[3][2]。(wikipedia)

いったいどんな可測空間上で定義された測度なんだ？と気になって調べた。

最小有向全域木を求める | Chu-Liu/Edmonds' algorithm

アルゴリズム数学

最小全域木問題の有向グラフバージョン。

無向グラフに対する最小全域木は、クラスカル法とかプリム法とかで求められるけど、有向グラフの場合はどうすればいいのか気になったので調べてみた。

Chu-Liu/Edmonds' algorithmというアルゴリズムで計算量は $O(nm)$ 。頑張ったら $O(m\log n)$ や $O(m + n\log n)$ とかにできるらしい。 $O(m + n\log n)$ のやつはフィボナッチヒープを使うとのこと。

この記事では $O(nm)$ のアルゴリズムについてまとめる。

Advent Calendar

この記事はQiitaで書いた記事をはてなブログに移動させたものです→ Internet Archive

この記事はEsolang(難解プログラミング言語) Advent Calendar 2016の4日目です。 ~~深夜テンションでうっかり参加登録ボタンを押してしまった・・・~~

今流行のBrainf*ckについて「今すぐ○○を始めるべき10の理由」形式で紹介します！

Shader

この記事はQiitaで書いた記事をはてなブログに移動させたものです→ Internet Archive

手軽にシェーダで遊べる環境が欲しくて色々と調べてたら Kotlin + Processing + GLSL という環境に行き着きました。そこで、ざっくりとした使用方法を備忘録的に記事にまとめました。

（ちなみにピクセルシェーダだけとかであれば Shadertoy がおすすめです！）