| 題名 | 需要供給グラフの最大供給分割法Simpleの性能強化 |
| 著者 | *柳生 拓也, 田岡 智志, 高藤 大介, 渡邉 敏正 (広島大学大学院工学研究科) |
| Page | p. 285 |
| Keyword | グラフ分割問題, 需要, 供給, 発見的解法 |
| Abstract | グラフの最大供給分割問題は，グラフが木であってもNP困難であることが知られており，発見的解法がいくつか提案されている．また，グラフが木でありかつ各点の需要量・供給量が全て整数の場合，擬多項式時間で最適解を求めるアルゴリズムが提案されている．本稿では，グラフの最大供給分割問題に対する発見的解法の中で，高速で受給率もよいクラスSIMPLE(解法Simple及びその改良手法を合わせた手法の族)に着目し，改良手法の提案と計算機実験による性能評価を行った． |
| 題名 | パターン表現を導入した文脈自由文法 |
| 著者 | *大庭 健介, 重安 芳謙, 伊藤 暁 (山口大学 理工学研究科) |
| Page | pp. 286 - 287 |
| Keyword | パターン表現 |
| Abstract | パターン表現はregex等における後方参照機能の概念を形式化するために導入された拡張正規表現である。パターン表現の表現形式では同じ変数記号についてはどれも同じ文字列を表しているとみなされる。これまで、パターン表現は多項式時間でパージング可能であることが知られている。本稿では、パターン表現の考え方を文脈自由文法に導入し、パターン文脈自由文法と呼ばれる新たな文法を定義する。また、パターン文脈自由文法を拡張し、コピー時に有限状態変換を行うgsm付きパターン文脈自由文法について定義する。最後にパターン文脈自由文法の応用例について示す。 |
| 題名 | 勝ち抜きジャンケンの平均計算量について |
| 著者 | *嶋原 浩志, 伊藤 暁 (山口大学理工学研究科) |
| Page | pp. 288 - 289 |
| Keyword | ジャンケン |
| Abstract | これまで，勝ち抜きジャンケンの平均計算量について，T(N)=Θ((3/2)N)であることが知られていた．本研究では，微分方程式や差分方程式の近似解法の一種であるドミナントバランス法を無限回適用することで，定数項を除く厳密解を導出する．数値実験によれば，この定数項はNが100以下の範囲で2以下である． |
| 題名 | 記憶付き可逆論理素子のビリヤードボールモデル上での実現 |
| 著者 | *向井 優太, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 290 - 291 |
| Keyword | 可逆計算, 記憶付き可逆論理素子, ビリヤードボールモデル, ロータリー素子 |
| Abstract | 計算機の微細化が進み微視的な物理現象を直接利用するようになると，そのような現象は可逆的であるため，計算機自体の動作も可逆的でなければならない．このような可逆計算機を構成する論理素子，すなわち可逆論理素子について多くの研究がなされ，記憶を持った素子が有用であることが分かっている．特にその1種であるロータリー素子は計算万能であり，さらに可逆的な物理現象を基にしたビリヤードボールモデル上で簡単に実現可能である．記憶付き可逆論理素子には他にも多くの種類が存在し，本講演では4以下の入出力数を持つ任意の状態数の全ての記憶付き可逆論理素子をビリヤードボールモデル上で簡単に実現する系統的な手法を示す． |
| 題名 | セル生産システムにおける新しいグルーピング法の提案 |
| 著者 | *篠田 裕介 (岡山県立大学大学院 情報系工学研究科), 山内 仁, 金川 明弘 (岡山県立大学 情報工学部) |
| Page | p. 292 |
| Keyword | セル生産システム, グルーピング, アルゴリズム |
| Abstract | 製品の多仕様化・多品種化に伴って，効率の良い多品種少量生産が求められるようになっている． これに対応するためにセル生産システムが注目されている． グルーピング問題において，部品を加工するための加工工程と，製品を組み立てるための組立工程の両方を考慮する方法があり，その際，部品，機械，サブアセンブリの適当なグルーピングをすることによって，設備の共用化が図られ，数少ないラインで多くの品種を作ることが可能となる． 本研究では部品のグルーピングに関してヒューリスティック解法を用い， 機械，サブアセンブリのグルーピングでは新たな評価基準を用いる手法を提案する． |
| 題名 | 階調値勾配とライン場との相関を考慮した結合ガウス・マルコフ確率場モデルによる画像修復 |
| 著者 | *櫛部 勇気 (岡山大学大学院自然科学研究科電子情報システム工学専攻), 相田 敏明 (岡山大学大学院 自然科学研究科) |
| Page | p. 293 |
| Keyword | ベイズ推定, 画像修復, エッジ |
| Abstract | 本研究では，ベイズ推定の枠組みにしたがって，256 階調の濃淡画像における画像修復において, 結合ガウス・マルコフ確率場モデルを統計モデルとして採用した．すなわち，原画像に対する事前確率分布に, 各画素の階調値の類似性を表現する確率場に加えて，最近接画素間に存在し得るエッジも考慮している. このモデルは，画像の持つ滑らかさと輪郭の保持を同時に達成することを意図したものである． ビリーフ・プロパゲーションを用いた近似解析による，画像修復アルゴリズムの構成と数値実験結果について報告する. |