■第3回研究会(2003年6月21日(土)14:00--18:00 東京大学 工学部6号館)の講演概要
 
14:00--15:50『誤り訂正符号の復号問題への統計力学的アプローチ』東京工業大学 樺島祥介 氏
誤り訂正符号の復号問題は,一般に計算論的に困難な問題である.ところが,最近,低密度パリティ検査符号(LDPCC)と呼ばれる符号に関しては,近似アルゴリズムにより,ほぼ線形オーダーの計算量で実質的に復号が可能となることが分かってきた.さて,誤り訂正符号の復号は大自由度分布からの推定問題であり,同じく大自由度分布で記述される磁性体など統計力学の問題と形式的な類似性を持つ.本講演では,この類似性を利用し,なぜ,LDPCCでは近似アルゴリズムによる復号がうまくいくのか,統計力学の概念,手法に基づき考察する.
 
16:10--18:00『2行分割表の多項式時間Perfect Samplingアルゴリズム』東京大学 来嶋秀治 氏
本発表では2行分割表を厳密に一様生成する多項式時間アルゴリズムについて述べる。このアルゴリズムはマルコフ連鎖を用いた標本生成法で、monotone CFTP (monotone Coupling From The Past)に基づくアルゴリズムである。
分割表は、医療統計の分野などで統計データを扱うために広く用いられる。分割表データに対して行われる検定法の一つに正確検定があげられるが、検定に現れるp値の計算に、MCMC(Markov chain Monte Carlo)法がよく利用される。MCMC法とはマルコフ連鎖を用いて標本生成を行うモンテカルロ法である。一方、組合せ論的立場において、分割表の数え上げは2行の時でさえ#P-完全であり、分割表に対する近似数え上げ、近似一様生成に関する多くの研究が存在する。
 
Seminars on Algorithms in Operations Research
ホーム - SAORについて - 会場案内 - 全日程 - リンク
(c) 2003-2004 SAOR All rights reserved.