| 題名 | 可逆性と保存性を同時に満たすセルオートマトンの探索 |
| 著者 | *齋藤 亮平 (広島大学大学院工学研究科情報工学専攻), 今井 克暢, 森田 憲一, 岩本 宙造 (広島大学) |
| Page | pp. 263 - 264 |
| Keyword | セルオートマトン, 可逆セルオートマトン, 保存的セルオートマトン |
| Abstract | セルオートマトン（ＣＡ）とは,セルと呼ばれる同一の有限オートマトンを空間に一様に配置，接続したもので，おのおののセルがその近傍のセルと情報交換をして状態を変化させることにより,空間全体の状態が時刻とともに移り変わっていくようなシステムである．可逆性と保存性を同時に満たすＣＡについては，過去の論文で設計方法が明らかにされており，おそらく計算万能ではないと推測されている．この論文では２近傍で２〜６状態のものしか探索されておらず，それ以降の状態数や近傍数での探索が行われていない．そこで，実際にそれ以降の状態数や近傍数を探索し，本当に計算万能ではないものしか存在しないのかを検証するのが，本研究の目的である． |
| 題名 | 採用募集説明会開催計画問題の計算複雑さ |
| 著者 | *高田 健太郎, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学) |
| Page | pp. 265 - 266 |
| Keyword | 計算複雑さ, NP完全, SRFP, 3-SAT, スケジュール |
| Abstract | 採用募集説明会開催計画問題（Scheduling Recruiting Fairs Problem; SRFP）とは，企業が卒業予定の学生を対象に，採用募集説明会を開催する計画を立てる問題を数学的なモデルで表したものである． 本研究では，採用担当者に学生の説明会開催希望があらかじめ与えられているという仮定のもとで，SRFPの計算複雑さを検討する． このとき，p人以上の学生がそれぞれ１回以上説明会に参加できるように，ある１つの企業の採用担当者が説明会を開催する計画が立てれるか否かを決定する問題，つまり，その企業の説明会開催スケジュールが存在するか否かを決定する問題が，NP完全であることを証明する． |
| 題名 | 多面体テラインに対する面警備問題 |
| 著者 | *岸 純一, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学) |
| Page | pp. 267 - 268 |
| Keyword | 警備問題, 美術館問題, 計算幾何学, テライン |
| Abstract | 空間内に障害物があるとき，空間内の2点が互いに見えるということは2点を結ぶ線分がどの障害物とも交わらないことである．警備員を配置し,空間を監視する問題を警備問題と呼ぶ．本研究では，警備対象を多面体テラインとした面警備問題を扱う．多面体テラインとは各面が三角形からなる多面体の表面であり, 警備員が面上を自由に移動できる. 頂点数nのテラインに対して警備するために必要な警備員数を調査した. 結果として(3n-5)/16人の面警備員で警備することができ, かつ(n+1)/8人の面警備員を必要とするn頂点の多面体テラインが存在することを示した. |
| 題名 | 可逆セルオートマトンによる可逆チューリングマシンのシミュレーション |
| 著者 | *長岡 勇介, 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学 大学院工学研究科) |
| Page | pp. 269 - 270 |
| Keyword | 可逆コンピューティング, セルオートマトン, チューリングマシン |
| Abstract | 物質の原子・分子レベルの性質を扱った可逆コンピューティングは将来の計算機の重要な研究であり，現在その基礎研究が最も必要な時期にある． 過去の研究では，可逆分割セルオートマトン(RPCA) を使った研究が進められており，任意のm 状態n 記号の可逆チューリングマシン(RTM) に対して，それをシミュレートする高々(m + n + 1)(m + 2n + 1) 状態の1 次元2 近傍RPCAが存在する，という状態数の少ない結果が示されている． 本稿ではこれを改善し、任意のm状態n記号のRTMに対して、それをシミュレートする高々(m+n+1)2状態の1次元2近傍RPCAが存在することを示す。 |
| 題名 | ２×２の議席配分問題について |
| 著者 | *佐伯 順治, 金子 数馬, 伊藤 暁 (山口大学 理工学研究科) |
| Page | pp. 271 - 272 |
| Keyword | 議, 席, 配, 分 |
| Abstract | 本研究では１次元の最大剰余比例配分法を自然に２次元に拡張した比例配分法について考察する． 本研究では，２×２の比例配分問題に関して検討し，全ての場合分けについて具体例を与える． また，２×２の比例配分問題の逆問題に対する解法を与える． |
| 題名 | シグナル伝達経路の構造情報に基づく時間ペトリネットの遅延時間決定手法の提案 |
| 著者 | *村上 祐樹 (山口大学大学院/理工学研究科), 三輪 良雅 (富士通エフ・アイ・ピー), 葛 崎偉 (山口大学/教育学部), 松野 浩嗣 (山口大学大学院/理工学研究科) |
| Page | pp. 273 - 274 |
| Keyword | シグナル伝達経路, 時間ペトリネット, 滞留なしペトリネット, 競合の解決, 遅延時間の決定 |
| Abstract | 本稿では, 時間ペトリネットに対して「滞留なし」という新たな概念を導入し, トークンが滞留しないという制約を持つサブクラス「滞留なしペトリネット」を提案する. 提案する滞留なしペトリネットは, 任意の与えられたアサイクリックなペトリネットの構造情報から, 各トランジションが満たすべき遅延時間を決定することで得られる. また, 競合を起こすトランジションの発火に関しては, 確率的な解決手法の提案を行う. |