| 大会名称 |
|---|
| 2008年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2008 |
| 発行日 |
| 2008/8/20 |
| セッション番号 |
| 7 |
| セッション名 |
| データサイエンスで活躍する列挙アルゴリズム－設計技法とその応用－ |
| 講演日 |
| 2008/9/2 |
| 講演場所(会議室等) |
| 第2イベント会場 |
| 講演番号 |
| 7-4 |
| タイトル |
| 列挙，数え上げ，ランダム生成 |
| 著者名 |
| 来嶋 秀治, |
| キーワード |
| 抄録 |
| 近年の計算機パワーの増大により，様々な分野において以前には計算不可能であった大規模な問題が扱えるようになっている．列挙算法もその例に漏れず，近年のアルゴリズムの高速化と相俟って，実用データを扱う汎用手法となりつつある． 列挙算法は，対象とする要素を目的に沿って吟味し，所望の要素を取りこぼすことなく見つける．反面，計算時間は出力サイズに敏感である．この問題を回避する一つの方法に乱択近似（randomized approximation）がある．すなわち，取りこぼしを許す代わりに，欲しい数だけの要素を確率的に抽出する手法である．特に，出力の分布を能動的に実現することで，所望の要素の取りこぼしの軽減が図れる． マルコフ連鎖モンテカルロ（MCMC: Markov chain Monte Carlo）法は，数値積分，シミュレーションなどに用いられる強力な確率的計算法である．特に，所望の分布を比較的容易に実現できる利点がある．本講演ではMCMC法を中心に，列挙とランダム生成の関連，ランダム生成の難しさ，ランダム生成の技法とその応用について述べる． |