二分探索は，値の探索に使うという認識が一般的だと思いますが，実際にはもっと守備範囲が広いです。ということでなるべく一般的な形で書くとどうなるのかを整理した話を書いてみることにしました。why3 で書いて正しいことを検証してみたらけっこうすっきり…

距離空間は豊穣圏であるという Lawvere の論文(http://www.tac.mta.ca/tac/reprints/articles/1/tr1abs.html)がありますが，それに似た感じで重みつきグラフから自由に生成された豊穣圏を考えると hom-object が最短経路になるらしいことに気付いて面白いと…

と書いたとき中国剰余定理として知られる同型 の具体的な与え方が毎回思い出せないのでどこかに書いておきたいと思ってメモ。ついでに単数群の生成元も。 同型 は単純にそれぞれの成分に射影すればよい。逆が少しややこしくて， となる。mod q_i での逆元は…

Graphillion で遊んでみた。 やったこと 有限集合上の半順序の個数を数えてみた(cf. OEIS A001035)。これを効率的に求めるのは未解決問題らしい。ちなみに有限集合上の位相の個数を数える問題とだいたい同じ。要素数 n を固定して，Graphillion を使って [1.…