2005年12月

全部オンラインなのはいいのだが，LaTeX を使った場合の説明がジャーナルのページに無い．クラスファイルはなんでもいいのか，ファイルを分割して \input で読み込んでいいのか，デフォルトでないパッケージ使っていいのか，bibtex やってくれるのかなど疑問点満載．大体にしてファイルフォーマット LaTeX ってのが良く分からんし... 　とりあえず dvi 送ったらエラーになったので tex のソースを送れってことだけど．

とにかく LaTeX の Instruction ぐらいちゃんと書いておいてほしいと思う．んで，埒が明かないので他のジャーナルとかの Instruction を見てみたら LaTeX の書き方を発見．同じシステムを使うのだからこれに従っておけば良いだろうと tex を指示に従って書き換えて提出．\input が使えるか分からんし，bibtex使えず bbl を直接書き込まねばならんので，\input の展開と \bibliography コマンドを bbl の中身で置き換えるスクリプトを書いた．

んで，どのパッケージが使えるのか良く分からんのでコンパイル結果の PDF を見ながら調整．tex のコンパイル時にエラーがある場合はそのコンパイル時の出力が PDF になる仕様らしい．そんなこんなで試行錯誤の末にどうにか提出を終えることができた．

あとは Copyright Transfer Form に記入して FAX するだけだ... あとでやろ．とりあえず帰省だ．

セミコロンで複数の文章をつなげ，最後の文の手前に and を書いていたら WordPerfect に怒られた．んで，ちょっと調べてみたら ここら辺の記述 により確かによろしくない使い方であることがわかった．基本的にはセミコロンはピリオドと等価で，And で文を始めないというルールがセミコロンでも当てはまると．一番単純にはセミコロンを使わなければいいので今後気をつけよう．

とりあえず WordPerfect の英文校正機能は出来が良くかなりありがたいなと．Grammarian も試したけど設定のせいなのか判断がいまひとつだったし，設定わからんし．あと，Knuth の書いた Mathematical Writing という本（講義ノートか？）もよさげ．英語で論文書くときの書き方がのっとるし，PDFが落ちとるので．んで，自分の書いてた文の大きな間違いとしては

• 関係代名詞の which は前置詞やカンマの後ろでないなら that を使う
• to 不定詞の to と動詞の間に副詞を入れてはダメ

が一番知らなかった部分で，あとはあいまい性の低いほうに書き換えろとかこの書き方は弱いとか．さらには同じ文頭が近くに沢山あるだとか動詞と目的語が離れすぎとか文が長すぎとかもあった．これからはここら辺に気をつけながら書くことにしよう．

よくわからん．IEEE の Style に従えといわれても LaTeX のスタイルファイル見つからないし．ガイドラインに沿っていれば細かいことは気にしないということだろうか...　細かいこと気にしないでさっさと投げることにしよう．

宣言どおり来年も Grid Challenge が行われるらしい．前回の問題はスケジューリング云々よりも如何にシーケンシャル部分を速くするか，ファイルのキャッシュをうまく効かせられるかにかかっていたのだけど，来年の問題はグラフの分割の最適化問題ということでこのウェイトが変わることを期待．とはいえ，シーケンシャルがある程度速いことは前提であるけれど…　このシーケンシャルの速度差をアルゴリズムでカバーする余地がありそうな気がする．やるとすればGAで新世代の生成を farmer/worker で投げてやるってのが一番シンプルかな．どっかで聞いた気がするけど…　交叉や判定なんかを調節すれば何とかなるのかも．でも，やっぱ離散最適化の手法でどうにかできてしまうことを期待したいなぁ．

scan を機械的に build form にもっていったら型がうまくつかず...　ああ，面倒．別のルートで変形してみるか．

オートマトンの話が出たときにふと思い出したので．問題の確認をば．これは1957年頃に Myhill によって提起された問題で，内容は以下のとおり．

とりあえず兵士が一列に並んでいて，端以外の兵士は全部同じである．右端の兵士を将軍として，将軍が時刻 t = 0 に隣の兵士に射撃命令を下す．各兵士は有限の状態（記憶）を持っており，時刻 t における両隣の兵士の状態によって自身の時刻 t+1 の状態を決定する．ただし，初めは待機状態にいるものとする．これらの条件の下で，全兵士がある時刻 T において一斉にある特定の状態（射撃状態）に移行するように，兵士たちの状態遷移関数を構成せよ．

この問題の解は，兵士の人数を n とすると最小時間である 2n-2 （伝令が往復する）の解が存在し，87年に Mazoyer が 6 状態の最小時間解を与えている: Mazoyer. A six-state minimal time solution to the firing squad synchronization problem: Theoretical Computer Science, Vol. 50, Issue 2, pp. 183-238, 1987.

並列プロセッサの同期とか生物細胞の成長同期とかの応用問題があるらしい．