| 題名 | 数値ラプラス逆変換における離散作用素積分法の精度について |
| 著者 | *市川 正美, 松田 章 (岡山県立大学 情報工学部), 宮川 佳夫 (元岡山県立大学) |
| Page | p. 314 |
| Keyword | 数値ラプラス逆変換, 境界要素解析, Convolution quadrature |
| Abstract | 離散作用素積分法は合成積の近似計算法としてLubichによって提案された手法であるが，ラプラス像関数などを利用するためラプラス変換を用いた非定常境界要素解析との親和性がよく，近年，非定常境界要素解析で使用されている．しかし離散作用素積分法の精度に疑問を呈する計算例が少なからず存在する．本研究では解析解が導出できる場合を取り上げ，また高速Fourier変換を利用するKrings & Waller法との比較を通じて離散作用素積分法の精度の考察を行っている．結果として，離散作用素積分法は対象とした計算例において安定した結果を与えるが，十分な精度を得るには少なくともKringer & Waller法の4倍程度の分割数を必要とすることが明らかとなった． |
| 題名 | 候補点抽出法の改良による障害物を有する格子グラフ上のスタイナー木算出法の性能強化 |
| 著者 | *江頭 一廣, 高藤 大介, 田岡 智志, 渡邉 敏正 (広島大学 大学院工学研究科) |
| Page | pp. 315 - 316 |
| Keyword | 格子スタイナー木, VLSI設計 |
| Abstract | 格子スタイナー木問題は，VLSI基板設計などの幅広い応用を持つ問題で，次で 定義される: 格子グラフH=(V,E)，障害物を表す点集合D⊆Vと 指定点集合P⊆V-Dが与えられたとき， HからDの各点とそれの接続辺を取り除いたグラフにお いて指定点をすべて含む辺数最小の木（格子スタイナー木）を求めよ． 本問題は|P|≧4でNP-困難であることが知られており、様々な近似解法，発見 的解法が提案されいる．また、計算機実験によりAGRF+の最も解精度が良いことが知られている．本稿では，AGRF+において候補点抽出法を改良した解法を提案し、 その性能を計算機実験により評価する． |
| 題名 | 重み増加パス探索の改良によるグラフ最大重みマッチング算出法の性能強化 |
| 著者 | *西河 恭倫, 高藤 大介, 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 317 - 318 |
| Keyword | グラフ最大重みマッチング, 重み増加パス, 近似解法 |
| Abstract | グラフ最大重みマッチング問題とは，辺重みを持つグラフG=(V,E) において重み総和最大のマッチングを1つ求める問題で、応用性の広い重要問題の１つである．マッチングMとは，どの辺も互いに端点を共有しない辺集合M⊆Eである．最大重みマッチングを求める多項式時間解法がいくつか提案されているが，計算複雑度が大きく、計算機実験により点数が数千以上のグラフでは現実的な時間で解が求まらないことが知られている．そこで，実用性を考慮して高速な近似解法が提案され、計算機実験によるAvis+が最も性能が良いことが知られている．本稿ではAvis+の後処理における増加パス探索を改良したAvis_S+を提案し，計算機実験によりその性能を示す． |
| 題名 | ペトリネットの下限制約発火系列問題とその解法設計 |
| 著者 | *片山 幸喜, 田岡 智志, 渡邉 敏正 (広島大学大学院 工学研究科) |
| Page | p. 319 |
| Keyword | ペトリネット, 発火回数緩和, 発火系列問題 |
| Abstract | ペトリネットの下限制約発火系列問題(LBFS)は，スケジューリング問題などへの応用を持つ問題で，次で定義される：「ペトリネットN,初期マーキングM,発火回数ベクトルX が与えられたとき,M から順次発火可能で すべてのトランジションが X(t)回以上出現し, 超過発火回数の総和ができるだけ小さい発火系列を求めよ」． 本稿の目的は，LBFSに対する解法設計の基礎とし， 超過発火回数を1回に限定した二つの解法D-X1, N-X1を提案し， 計算機実験によりこれらの性能評価を行うことである． |
| 題名 | 抑止辺を有するペトリネットに対する発火系列求解法FEIDEQ_ODC |
| 著者 | *名嘉真 宣一 (広島大学工学部), 田岡 智志, 渡邉 敏正 (広島大学大学院 工学研究科) |
| Page | pp. 320 - 321 |
| Keyword | ペトリネット, 抑止辺 |
| Abstract | 抑止辺を有するペトリネットとは，ペトリネットに抑止辺（発火を抑止する辺） を付加したものであり，そのモデル化能力はチューリングマシンと同等である． 抑止辺ペトリネットの最大発火系列問題（MAX INLFS）はスケジューリング問 題などに応用があり，『抑止辺ペトリネットIN，初期マーキングM，発火回数 ベクトルXが与えられたとき，Mから順次発火可能で各トランジションtがX(t) 回を越えない回数出現する発火系列で，できるだけ長い系列δを求めよ．』と 定義される．INLFSの解法としてRADQ_ODC が提案されているが，本稿ではこの 解法を改良したFEIDEQ_ODCを提案する． |
| 題名 | グラフ点彩色問題に対するハイブリッド解法の終了条件の改良による高性能化 |
| 著者 | 飯田 恵大, *福岡 宏樹 (広島大学工学部), 田岡 智志, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | pp. 322 - 323 |
| Keyword | グラフ点彩色 |
| Abstract | グラフの点彩色問題とは，グラフの点彩色に必要な最小の色数，及びそのとき の点彩色を求める問題である．この問題は一般にNP困難であり，発見的解法が 提案されている．このアプローチ方法の一つとして，色数kを減少させながらk 点彩色を試み，より少ない色数の点彩色を発見的に求めるpartition approach がある．本稿では，このpartition approachにおいてk点彩色を求める際に隣 接探索法とタブ探索法を併用したハイブリッド解法に着目し，隣接探索法の終 了条件を改良することでアルゴリズムの高精度化を行い，計算機実験による有 効性を示す． |
| 題名 | 基準構造を用いた構造系統図によるプログラムの分析 |
| 著者 | *吉岡 俊一 (島根大学大学院総合理工学研究科), 賈 凡 (島根大学総合理工学部), 森田 亜希人 (島根大学大学院総合理工学研究科), 會澤 邦夫 (島根大学総合理工学部), 佐藤 匡正 (無所属) |
| Page | pp. 324 - 325 |
| Keyword | プログラム構造形式化手法, 構造系統図, プログラム分析 |
| Abstract | プログラミング演習において,仕様を学生に与え,プログラムを作成させるプログラム演習形態がある．この演習において作成されるプログラムを評価する方法として,構造系統図が提案されている．この方法は,プログラムを，プログラム構造とプログラム機構からなると考え，プログラム構造を正規表現式で表す．正規表現式から，任意の組を一致，不一致，包含のいずれかの関係によって位置づけ図式化する．図中の基準式(以下基準構造）から位置取りによってプログラムを評価する．従来基準構造を一つに定めたため，基準構造と不一致の関係を持つプログラム構造が生じた．そこで，複数の基準構造を用意し，この問題点を解決すると共に，新たな構造系統図上でのプログラムの分析を行う． |