| 題名 | 隠れ警備員配置問題における上下限 |
| 著者 | *山本 裕嗣, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 71 - 72 |
| Keyword | 警備問題, 隠れ警備員配置問題, 警備員数の上下限 |
| Abstract | 警備問題とは，空間に警備員を配置して監視する問題のことであり，この問題の種々の変形版に関する研究論文は数百篇にものぼり，計算幾何学の中の重要な一角を占めている．本論文では，警備問題の一種である隠れ警備員配置問題を取り扱う．隠れ警備員配置問題とは，警備員を互いに見えない位置に配置し，多角形の内部を監視する問題である．まず，警備員数の下限の定理1を与える．次に，間仕切りを用いることで警備員数を減らせることから，間仕切りを用いた隠れ警備員配置問題の警備員数の上限の定理2と下限の定理3を与える．さらに，間仕切りの数も考慮することで定理3を改善した定理4を与える．最後に，定理1，4の証明をし，定理2の配置アルゴリズムを紹介する． |
| 題名 | 非決定性チューリング機械の厳密な領域階層定理 |
| 著者 | *立花 大輔, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 73 - 74 |
| Keyword | チューリング機械, 計算複雑さ, 領域階層定理, 非決定性 |
| Abstract | テープ記号が0と1に制限された１テープ非決定性チューリング機械の厳密な領域階層定理を導出する．s_1(n),s_2(n)を領域構成可能関数とし，s_2(n)-s_1(n+2)-nがO(1)に含まれないとき，s_1(n)領域の１テープ２記号１ヘッド非決定性チューリング機械に受理される言語のクラスは，s_2(n)領域の同機械のクラスに真に包含されることを証明する．領域関数s_1(n+2)の変数nに加えられた2は，再帰詰込み論法における万能チューリング機械のテープの「２トラック化」に由来している．また，s_2(n)とs_1(n+2)の「差」は，nより大きい必要があるが，これは，万能TM を再帰的に呼び出すときに必要となる入力列を保存するための領域である． |
| 題名 | 4記号万能可逆チューリングマシンの構築 |
| 著者 | *三上 敦志 (広島大学大学院工学研究科情報工学専攻), 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 75 - 76 |
| Keyword | チューリングマシン, 可逆性, サイクリックタグシステム, Turing Machine, TM |
| Abstract | 現在の論理素子は小型化が進んでいるが，既存の技術の延長だけでは近い将来に限界を迎えるものと推測される．その解決策の１つとして研究されているのが可逆性である。これは物質のミクロな性質を反映しており，さらなる小型化の鍵と考えられている。この可逆性を理論的な方向から研究するためのアプローチとして，基本的な計算機モデルであるチューリングマシンを題材とし，可逆性を備えた万能チューリングマシンを構築するというものがある．過去にもサイズ(状態数と記号数)の小さい複数の万能可逆チューリングマシンが発表されている．本研究ではこれらを継続し，これまでに構築されていない４記号万能可逆チューリングマシンを構築した． |
| 題名 | 非決定性チューリング機械をシミュレートする非決定性論理回路の設計 |
| 著者 | *小野 優介 (広島大学大学院工学研究科情報工学専攻), 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科) |
| Page | pp. 77 - 78 |
| Keyword | チューリングマシン, 論理回路, 非決定性, Turing Machine, TM |
| Abstract | 直列計算および並列計算の基本モデルは，チューリング機械と論理回路である． 本研究では，非決定性チューリング機械と非決定性論理回路，これら2つのモデル間のシミュレーションについて考え，以下のような結果を得た． T(n)時間S(n)領域で動作し，G(n)回の非決定的動作をする任意のTM Mに対して，MをシミュレートできるサイズO(S 2(n)T(n))，段数O(log T(n))，非決定性入力ビット数T2(n)の論理回路と,サイズO(S(n)T(n)), 段数O(T(n)log S(n))，非決定性入力ビット数G(n)の論理回路を構成した．また,サイズを増やせば段数はO(T(n))に改善できる. |
| 題名 | 4入出力2状態可逆論理素子の万能性 |
| 著者 | *谷澤 強, 藤井 洋一, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 79 - 80 |
| Keyword | 可逆, ロータリー素子, 万能性, RE, 可逆論理素子 |
| Abstract | 現在の計算機には半導体素子が用いられ，その微細化が進められているが，それはあと十数年で限界に達すると言われている．それ以降は原子，分子などミクロレベルの物質を直接論理演算に用いるような手法へ移行すると予測される．このような手法の研究の有力なアプローチとして可逆コンピューティングが挙げられる．本研究では可逆コンピューティングを構成するための可逆論理素子について，特に4入出力2状態可逆論理素子の万能性を考察する． |
| 題名 | 反応拡散セルオートマトンを用いた結線構築法 |
| 著者 | *雪田 恭兵 (広島大学大学院 工学研究科 情報工学専攻), 今井 克暢, 森田 憲一 (広島大学大学院 工学研究科), 岩本 宙造 (広島大学大学院工学研究科) |
| Page | pp. 81 - 82 |
| Keyword | セルオートマトン, 反応拡散系, 化学反応波 |
| Abstract | 反応拡散現象は生物の体模様やBZ反応(Belousov, Zhabotinsky反応)などに見られ, 特徴として時間的振動や, 動的で多様なパターン形成があげられる. この反応系では化学反応により物質の濃度が空間的に変動する現象が起こり, その現象は化学反応波と呼ばれている. 過去の研究としてセルオートマトンを用いて反応拡散現象をシミュレーションする試みは数多く示されている. 具体的なものとしては, 貝殻の模様に見られるチューリングパターンの形成手法があげられる. 本研究では反応拡散現象で見られる化学反応波を2次元のセルオートマトンを用いて表現する. それらを互いに衝突させることでセル空間内に結線構造を構築するとともに, 論理回路を構築できる可能性を示す. |