誰かネタが尽きた人は読んでリスト。
Brzozowski Minimization 周りの論文色々
「マイナーなのでお前らは知らんかもしれないが格好いい手法があるので使ってやるぜ」という前振りで最近よく参照される技法に、Brzozowski という人の考えた正規表現を微分してマッチング処理、という話があります。
- Regular-expression derivatives reexamined (JFP 2009)
- An algorithm for RELAX NG validation (2002)
- Yacc is dead (2010)
が、マイナーなので形式言語理論屋さん以外は知らんかもしれないが「『マイナーなのでお前らは知らんかもしれないが格好いい手法があるので使ってやるぜ」的文脈でよく参照される、Brzozowskiの考えた技法』」と言っただけでは一意に定まらないのである。
- A Taxonomy of Finite Automata Minimization Algorithms
などなど参照。「オートマトンの最小化」の技法。微分の方が流行るんならこっちも来年辺りから流行りますよきっと。
Smoothed Analysis 周りの論文色々
『最悪計算量の理論値は指数時間だけど、なぜか実装してみると実用上のパフォーマンスは速い』という現象をなんとかして説明したいなー的動機で導入された計算量解析の手法。
行列乗算と群論 周りの論文色々
行列乗算が O(N^2) でできるかどうか？という未解決予想を怪しげな群の存在予想に帰着する。
Cerny's Conjecture 周りの論文色々
『n頂点の有向グラフがあります。どの頂点からも k 本の辺が出ていて、1 から k までの異なる番号が振ってあります。
今、全ての頂点の上に一人ずつ小人さんが立っています。
ある番号の列 [1..k]* に従って全小人さんがグラフの上を歩いたら１つの頂点に集合するとき、
その列を "同期語" といいます。こういう同期語はないこともあるけど、
あるなら、長さ (n-1)^2 以下のものが必ずある！』
という未解決予想。
P-versus-NP page
「P=?NP問題を解決した」と主張している論文リンク集。読んで得られる物はほとんどないと思いますが、昏倒度合いとかこの会に相応しい。あと真面目に、どういう間違い方に類別されるのかとか注釈集あったら読みたい。
けど絶対自分でやりたくない。
こっち方向で真面目な方に振ると、
のような、「「このアプローチではP≠NPは絶対証明できない」という証明」の話は面白いと思うけど、多分難しいと思います。
最終更新：2011年03月06日 15:24
