| 題名 | 確率フローネットワークにおける信頼性評価法の性能比較 |
| 著者 | *田原 将充 (広島大学), 坂本 達哉 (広島大学大学院工学研究科), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究院) |
| Page | pp. 295 - 296 |
| Keyword | 確率フローネットワーク, 信頼性 |
| Abstract | 本稿では, 頂点の容量が無限大で, 辺の容量が確率的に変化 する有限の整数値を取るような確率フローネットワークを取 り扱う．この確率フローネットワークに対して需要値d が与 えられた際，「最大フローが少なくともd 以上になるネット ワークが出現する生起確率」を, 確率フローネットワークの信 頼性という．信頼性評価法として, state-space, inclusionexclusion, disjoint subset, タイセット法 などがある． しかし，実行計算時間や使用メモリ量といった実処理能力の 観点から，どの解法が優れているかはほとんど知られていな い．そこで本稿では，この観点からの研究の第一歩として， state-space，inclusion-exclusion を実装し，計算機実験により 性能比較を行う. |
| 題名 | 発火抑止辺を持つマークグラフの発火系列問題 |
| 著者 | *林 佳弘 (広島大学大学院工学研究科), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究院) |
| Page | pp. 297 - 298 |
| Keyword | ペトリネット, 抑止ペトリネット, 発火系列問題, マークグラフ |
| Abstract | 発火抑止辺を有するペトリネットとは，ペトリネットに発火抑止辺（トークンの存在により接続するトランジションの発火を強制的に禁止する辺）を付加したものであり，そのモデル化能力はチューリングマシンと同等であることが既知である． 本研究では，辺重みが不均一であるマークグラフにおいてリベット数が1，2，3 である場合のINLFS（抑止辺ペトリネットの発火系列問題）について，既存の発見的解法を実験的に性能評価する．これらに関しては、現在のところINLFS が擬多項式時間(O(|X|)) で解けるかNP 困難であるかはまだ判明していない． |
| 題名 | 時間付きペトリネットの最小初期マーキング問題に対する遺伝的アルゴリズム |
| 著者 | *杉本 貴亮 (広島大学工学部), 落岩 諭 (広島大学大学院工学研究科), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究院) |
| Page | p. 299 |
| Keyword | ペトリネット, 時間付きペトリネット, 初期マーキング |
| Abstract | ペトリネットはシステムの解析などに広く利用されている強力なモデリン グツールである．時間付きペトリネットに対する最小初期マーキング問 題(TPMIM) は「(トランジションの発火に時間遅延がある) 時間付きペト リネットTPN，発火回数ベクトルX が与えられたとき，各トランジション t がX(t) 回発火し，かつ，実行終了時間が π 以下である発火系列 δ が存在する初期マーキングのうち，総トークン数が最も少ない初 期マーキングを求めよ」と定義される．これはシステムの最適初期資源配 分に関わる問題の一つである．TPMIMはNP-困難であることが知られており， TPMIM に対する発見的解法TPM，TMDLO が提案されている．本稿では，遺 伝的アルゴリズムを用いたTPMIM の解法を提案し，計算機実験によりTPM， TMDLO と性能比較する． |
| 題名 | 順序グラフパターンの多項式時間マッチングアルゴリズム |
| 著者 | *日野 隆博, 鈴木 祐介, 内田 智之 (広島市立大学), 糸川 裕子 (広島国際大学) |
| Page | pp. 300 - 301 |
| Keyword | 順序グラフ, グラフパターン, データマイニング |
| Abstract | CADや地図のような平面グラフ構造データは各頂点が順序づけられた隣接頂点を持つ平面図として表現できる．Jiangらは各頂点が順序付けられた辺を持つ順序グラフを提案した． 本論文では，順序グラフを拡張し，各頂点が順序付けられた辺と変数を持つ新しいグラフパターンである順序グラフパターンを提案する．順序グラフパターンの変数は任意の順序グラフを代入できる． 本論文では，順序グラフパターンgと順序グラフGがマッチするかどうか，つまりgの変数に順序グラフを代入することによりGが得られるかどうかを判定する問題を考える．本論文では順序グラフパターンに対する多項式時間マッチングアルゴリズムを与える． |
| 題名 | ブロックターボ復号法の効率化に関する研究 |
| 著者 | *菊元 貴大, 日下 卓也 (岡山大学大学院自然科学研究科) |
| Page | p. 302 |
| Keyword | ブロックターボ復号法, 誤り訂正符号, 軟判定復号法 |
| Abstract | 線形符号の軟値出力復号法として軟判定復号法として 有名なOrdered Statistics Decoding(OSD) を軟値出力 に対応させた軟値入力/軟値出力-OSD(Soft In Soft Out- OSD(SISO-OSD))[1] が知られている. また, SISO-OSD を対応させた積符号の復号法であるブロックターボ復号 法が知られている．既存法では水平方向, 垂直方向への 復号に常に同じ次数のSISO-OSD を用いるため復号の 計算量が大きくなる場合があることが問題である. 本研 究では積符号のブロックターボ復号法における水平方向, 垂直方向の各ステップにおいてSISO-OSD の次数を変 化させることにより, ビット誤り率を悪化させることな く復号を効率的に行える手法を提案し, (32; 21; 6) 符号 の2 次元積符号(32; 21; 6)2 を例として性能を評価する. |
| 題名 | 2方向ワトソン・クリック有限オートマトンの受理能力について |
| 著者 | *松本 慶都, 青山 真之, 會澤 邦夫 (島根大学大学院総合理工学研究科) |
| Page | p. 303 |
| Keyword | DNA計算, ワトソン・クリック有限オートマトン |
| Abstract | DNA計算は，Adlemanの実験をきっかけに，極小サイズかつ高速なコンピュータを実現する為の方法の1つとして考えられた。DNA計算における計算モデルとして，ワトソン・クリック有限オートマトン(以下，WK)やスティッカーシステムなどが考案されている。2方向有限オートマトンは1方向有限オートマトンと言語のクラスが等しいことが知られているが，本研究ではWKの上下2つのヘッドのうち，上側は1方向のみに動き，下側のヘッドが2方向に動くような(1.2)-ワトソン・クリック有限オートマトンが，ヘッドが共に1方向のみに動くWKより言語受理能力が高いことを示す。 |