| 題名 | 3-ヘッド逆ワトソンクリック・オートマトンによる単純スティッカー言語の認識 |
| 著者 | *村上 和樹, 坂本 典子 (島根大学大学院総合理工学研究科), 青山 真之, 會澤 邦夫 (島根大学総合理工学部) |
| Page | p. 294 |
| Keyword | DNA Computing, Watson-Crick Automata, Sticker Systems, Formal Language |
| Abstract | DNA計算は, Adelmanの実験をきっかけに，極小サイズかつ高速なコンピュータを実現する為の方法の1つとして考えられた．DNA計算における計算モデルの1つであるワトソン・クリックオートマトンはG. Paunらによって導入され，これまで種々のタイプのワトソン・クリックオートマトンが研究されてきた．現在，スティッカーシステムの言語を認識する機構としてマルチヘッドオートマトンや5’→ 3’センシングワトソン・クリックオートマトン等が知られている．これらの認識機構は共にヘッド同士の距離や，その位置を互いに感知する能力を持つ．本研究ではそのような能力を持たない3-ヘッド逆ワトソン・クリック有限オートマトン（3-RWKFA）を提案し，3-RWKFAによっていくつかのスティッカーシステムの言語クラス（SSL(n)，及びASL(b)）を認識できることを示す． |
| 題名 | DNA計算を用いたk-SATの解法 |
| 著者 | *坂本 典子, 村上 和樹 (島根大学大学院総合理工学研究科), 青山 真之, 會澤 邦夫 (島根大学総合理工学部) |
| Page | p. 295 |
| Keyword | DNA計算, SAT |
| Abstract | DNA計算とは，DNA分子の構造と分子生物学的な操作を活用して計算を行うことである．現在の我々が使用している計算機では計算量的に解を求めることが困難な問題をDNA計算により解く方法が研究されている． Liptonは，論理式の充足可能性問題（satisfiability problem；SAT）の特殊形である3-SATについてDNA計算を用いて解いた．しかし，問題のサイズに対して解の候補のサイズが指数関数的に増大するというスケール問題を抱えており，これを克服するアルゴリズムとして陶山らはダイナミックプログラミング法を用いて大幅に少ない分子量で3-SAT問題をDNA計算で解いた． 本研究では，陶山らのアルゴリズムからk-SATを解くアルゴリズムに拡張した． |
| 題名 | 確率法によるゲーム木探索アルゴリズム |
| 著者 | *三原 康弘 (島根大学大学院総合理工学研究科), 小林 康幸 (島根大学総合理工学部) |
| Page | pp. 296 - 297 |
| Keyword | ゲーム理論, アルゴリズム, オセロ, 探索 |
| Abstract | 将棋，囲碁，チェス，オセロなどの二人零和完全情報ゲームでは，様々な探索手法においてミニマックス法が用いられている． 本研究では，ミニマックス法よりも効率の良い探索法として，確率法を提案した．確率法は過去の経験による確率を用い，ゲーム木全体を評価して最も勝つ確率の高い手を選択する探索法である．さらに，ゲーム木の枝刈りを行うことによって，探索時間を減少させることが可能であることも示した． 実験には過去のオセロの対戦棋譜を用い，ミニマックス法の枝刈りであるアルファベータ法と正解率，探索時間の比較をしたところ，同程度の探索時間では確率法の方が正解率が高いという結果となリ，確率法が優れた探索法であることが示された。 |
| 題名 | スペクトル拡散型電子透かしにおける確率的復号法の提案 |
| 著者 | *寺西 直緒 (山口大学理学部), 川村 正樹 (山口大学大学院理工学研究科) |
| Page | p. 298 |
| Keyword | 電子透かし, 確率, 復号アルゴリズム |
| Abstract | スペクトル拡散型電子透かしに対して，確率的復号法を提案する．メッセージをスペクトル拡散して画像に埋め込むとき，多重化が可能である．しかしながら，多重化を行うと透かし間干渉が生じる．計算可能な準最適な復号方式の1つに決定論的な復号方法であるマルチステージ復号がある．これは推定したほかのメッセージ情報を用いて透かし間干渉分を除去し，それを反復してメッセージ推定精度を上げる方法である．本研究では，メッセージの推定に確率を導入した復号方法を提案する．計算機シミュレーションによって，その性能を評価した結果，通信路ノイズが大きいときはビット誤り率が大きくなり，小さいときには，従来のマルチステージ復号とほぼ同等の性能であった。 |
| 題名 | グラフ点彩色法VNS_TOの独立点抽出に基づく改良 |
| 著者 | *小新 雄太 (広島大学大学院 工学研究科 情報工学専攻), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | p. 299 |
| Keyword | 点彩色 |
| Abstract | グラフの点彩色とは、与えられたグラフGにおいて隣接する（辺で結ばれている）頂点が異なる色となるようにすべての頂点に色を塗ることである. 点彩色問題は最小色数及びそのときの点彩色を求めることが目的であるが, 一般にNP困難であることが知られている. そこで, 多くの発見的解法が提案されている. 本研究では, 発見的解法として知られているVNS_TOの改良手法を中心に報告する. |
| 題名 | 系列探索の改良により性能強化されたペトリネットのマーキング構成問題解法 |
| 著者 | *吉岡 篤人 (広島大学工学部第二類), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科情報工学専攻) |
| Page | p. 300 |
| Keyword | アルゴリズム, ペトリネット, マーキング構成問題, 可達問題, 発見的解法 |
| Abstract | ペトリネットのマーキング構成問題(MCP: Marking Construction Problem)とは,「ペトリネットN,初期マーキングMi,目標マーキングMtが与えられた時,Miからトランジションの発火により遷移可能なマーキングのうちでMtに最も近いマーキングを求めよ」という問題である.MCPは一般にNP-困難であり,貪欲的にトランジションを発火させて複数の系列を調べてその中から最も目標マーキングに近づく系列を選択していく手法が既にいくつか提案されている。その中で最も高精度な手法がMCAである。貪欲的に目標マーキングに近づく系列を選択していく手法には,調べる系列数が少ないと解精度が低くなるという問題点があることが分かっている.既存手法のMCAに対して発火系列探索をより多く継続する改良を組み込んだ解法を提案し、計算機実験により性能評価を行う。 |