トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地へと向かった。 トロピカルな世界に行くためにはまずは代数を知る必要がある。要するに群・環・体の話だ。しかしこの記事の目的は代数学入門ではないので詳しい話は他の記事3に譲るとし、さっそく半環という概念を導入する。それは 半環は以下の性質を満たす二つの二項演算、即ち加法（和）"$+$" と乗法（積）"$\cdot$" とを備えた集合$R$を言う $(R, +)$ は単位元 $0$ を持つ可換モノイドを成す: $(a + b) + c = a + (b + c)$ $0 + a = a + 0 = a$ $a + b = b + a$ $(R, \cdot)$ は単

この記事はADVANCED BEGINNERからCOMPETENTの方を対象読者として書かれています。 コインの裏表やサイコロの出目はよく確率変数によって表されます。確率変数が互いに依存しているようなモデルを記述する手法としてグラフィカルモデルと云うものがあります。例えば、ある分布に従って表が出る確率が偏ったコインが選ばれた後、そのコインを投げて表裏が決まるような実験を考えた場合、コインの確率変数を $X$, コインの表裏の確率変数を $Y$ とすると、この系を記述するグラフィカルモデルは このようになります。ところで $X$ は表が出る確率Double上の確率変数RVar Doubleで、 $Y$ は $X$ の結果に依存したコインの裏表Bool上の確率変数Double -> RVar Boolであると考えるとします。今コインがランダムに選ばれると言う構造を 忘れて コインの表裏が出る確