No Such Blog or Diary

論文出来が悪すぎ．第一著者の書いた部分はほとんど時間の無駄と化した．まあ，修論の焼き直し見たいにして書いてたから当然なのかも．実験データもかなり変な結果が出てるし…　とりあえず提出してしまえ．大会で発表するのは問題なかろう．論文としては採録されなさげ～．

論文のために実験データを取ろうと必死こいて作業しているが…　大体，うまくいくわけねーんですよ．既存のプログラム間違ってるし，だれもちゃんと実行させてないし．ぽこぽこ出てくる問題は回避不能だったり，「運」で良し悪しが決まるとか言われたり…　こーなったらもうスクリプトでデータ生成しまくって走らせてやる！

教訓：論文書くときは大分前から実験しとけ．実験してないのに締め切り前に蒸発するな．

とあるDFAを使うプログラムに「最小のオートマトンを求める」というコメントの付いた関数があった．んで，全ての入力に対して同じ状態へ遷移する状態集合だけをまとめて最小だと叫んでいる．これだけじゃ明らかに最小にはならないのに…　このプログラムの作者は何も考えてないんだなぁと思わざるを得ない．最小化できない例としてもっとも単純に考えられるのは，あらゆる入力に対して自分自身に帰ってくるような状態が二つ以上ある場合で，このとき遷移先の状態は各々異なっているので状態がまとめられない．ということで，正しく最小化するには逆の考えをとらねばならない．すなわち，明らかに異なることをチェックしていき，異なると示せないものを等価とする．

輪講発表の２４時間前くらいには作り始めましょう…

Parallel Dynamic Programming の論文を読んでいるのだが…　ローカル計算後の縮約作業が複雑すぎ．他への応用というか一般化はほとんどできなさそう．

格子点上に頂点を持つ多角形の面積と内部の格子点数と辺の上に載っている格子点数の間には関係式がある．

「Ｐｉｃｋの定理」 平面上の格子多角形 P に対して，辺上にある格子点の個数を b, P の内部格子点数を c とすると, その面積 S(P) は次式となる: S(M) = (c-1) + b/2 .

基本的なアイデアは多角形を面積が 1/2 の三角形に分解していくイメージのはず．とりあえず，この定理を知っていると格子点上の図形問題が格段に簡単に解けるに違いない．