~matubara/ChangeLog / 2006-04 →移動しました

■ TIME 100 - Kurt Goedel - [math][net]

<http://www.time.com/time/time100/scientist/profile/godel.htlm>
Yet another homage to Goedel by Douglas Hofstadter

■ 公開ワークショップ　＜認知言語学の学び方３＞ [lx][net]

<http://gamp.c.u-tokyo.ac.jp/~tohori/manabi.html>
昨年のReading List
は、言語学の教養的な入門、言語学科な入門、
認知言語学の本などの解説つきガイド。

■ Intersection [math][programming][net]

<http://acm.pku.edu.cn/JudgeOnline/problem?id=1401>
線分と長方形の交わり(Intersection)を判定する。
線分や長方形を点の集合とみなしたとき、intersectionが非空かどうか。

基本的には、
線分と線分の交わりを判定するサブルーチンを作り、
長方形の四辺いずれかと線分との交わりを判定させる。

線分と線分の交わりは、一方の線分を延長して直線にし、
他方の線分と交わるかを調べ、逆も成り立つかを調べることで行う。
具体的には、一方の線分の傾きと切片を求め、
その片側だけに他方の両端点が来る場合は交わらない、と判定する。
（事実上交点を求めている）

例外：
長方形の中に線分が含まれる場合は、四辺との交わりがなくても、交わっている
片方の線分が垂直な場合は、傾きがとれないので特別扱い
片方の線分が点の場合は、やはり特別扱い

手法が泥臭すぎるのは仕様。
せめて、線分の交わりの判定は何とかならないものか。

Java はメモリ食いすぎ、時間も遅すぎ。
小さい問題だとオーバーヘッドが強く影響する。


岡本先生のプログラムは、だいたい同じ考えで作られている。
違いは、「長方形の中に線分」の扱いと、線分同士の交わり。
「中」よりも緩い条件である「長方形の中に線分の端点のいずれか」がいえれば、
交わっていることが分かる。
（線分の両端点が中、を言わなくてもいい）
線分同士の交わりは、片方が垂直な場合について細かい場合わけにより判定。
片方が水平な場合、XYを反転して↑に渡す。

■ ファイルサーバのHOMEディレクトリにSVNリポジトリを置いて使う [win][svn]

Cygwin からは、

svn ls svn+ssh://zonen/home/wijs/matubara/backup_winhome/cygwin_home/.repos

当然のように、ssh-agent が有効なのがありがたい。

サーバー上では、

svn ls file://localhost/home/wijs/matubara/backup_winhome/cygwin_home/.repos

TortoiseSVNでは、

■ Gad M. Landau [string][nlp][people][net]

<http://cs.haifa.ac.il/~landau/>
Construction of Aho Corasick Automaton in Linear Time for Integer Alphabets
など。

■ How to Use Notepad to Create a Log File [win][chalow][net]

<http://support.microsoft.com/?kbid=260563>

2. Type .LOG on the first line, and then press ENTER to move to the next line.

■ 岡野原さんによる定数時間検索の解説 [algorithm][net]

<http://hillbig.cocolog-nifty.com/do/files/2005-12-compInd.pdf>
Suffix Array を使うと、
4NのメモリとO(log N)の時間で検索ができる
…というのはもう古い。

メモリはCSAでN/2程度、
時間はwavelet tree でO(m)

■ Syllabus (11-761 Spring 2006 Course Syllabus) [nlp][net]

<http://www.cs.cmu.edu/~roni/11761-s06/syllabus.htm>
サイコロ本の講義。

■ The Personal Page of Gonzalo Navarro [string][people][algorithm][nlp][net]

<http://www.dcc.uchile.cl/~gnavarro/eindex.html>
自然言語の全文字列索引付けとか、
あいまい検索とか。

■ Templates for the Solution of Linear Systems, 2nd Edition [math][book][net]

<http://www.netlib.org/linalg/html_templates/Templates.html>
「Numerical Recipe を使ってはいけない」という須田先生のお薦め本。
行列式とか固有値とか連立一次方程式を解く、反復法の本。

■ Christopher D. Manning, Hinrich Schuetze, Foundations of Statistical Natural Language Processing [book][nlp][net]

<http://nlp.stanford.edu/fsnlp/>
2006年辻井研M1輪講で読む本のひとつ。
表紙はサイコロ。
Foundations of Statistical Natural Language Processing: Errata

■ Computer Science Special Course (進化計算) [algorithm][net]

<http://www.iba.k.u-tokyo.ac.jp/~iba/CS/>

■ Complexity Zoo - Qwiki [algorithm][net]

<http://qwiki.caltech.edu/wiki/Complexity_Zoo>
計算量クラスの一覧。
PTAS(Polynomial-Time Approximation Scheme)

■ B. Jedynak and S. Khudanpur, "Maximum Likelihood Set for Estimating a Probabilty Mass Function," 2005. [nlp][lm][net]

<http://www.clsp.jhu.edu/~sanjeev/Pubs/NC2005.pdf>
Good-Turing のスムージング法、Bayesian な確率推定に代わる方法。
難しそう。

■ An Algebra for Structured Text Search and A Framework for its Implementation - Clarke, Cormack, Burkowski (1995) [math][ir][net]

<http://citeseer.ist.psu.edu/clarke95algebra.html>
GCL(General Concordance List)問い合わせ代数。

■ NAACL ARCHIVES [nlp][net]

<http://www.cs.cornell.edu/home/llee/naacl/archives/>
Conference とか Workshop の重要な講演、
チュートリアルくらいは調べよう、
ということで、North American chapter of
the Assoc. for Computational Linguistics のアーカイブ。

■ 情報科学実験I ML演習 [programming][net]

<http://web.yl.is.s.u-tokyo.ac.jp/~kohei/lecture/caml-enshu/>

■ Jabion-日本語バイオポータルサイト- [bio][net]

<http://www.bioportal.jp/index.html>

■ xyzzy, cygwin/emacs, Meadow [emacs]

今日の時点で、
- すぐに日本語が打てて、
- changelog-mode が最初から使える
のは Meadow

■ Richard Dawkins, "The Blind Watchmaker" [bio][book]

「盲目の時計職人」
辻井研の吉田さんからいただいた本。