| 題名 | キャストパズルの計算複雑さ |
| 著者 | *西尾 研二 (広島大学大学院工学研究科情報工学専攻), 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学) |
| Page | pp. 83 - 84 |
| Keyword | キャストパズル, 計算複雑さ, NP困難 |
| Abstract | 知恵の輪とは，つなげられた2つ以上の部品を外したりつないだりす るパズルの一種である．知恵の輪には，部品が針金から作られた，いわゆる狭義の「知恵の輪」(ワイヤーパズル)と，金型に炉で溶かした亜鉛合金を流し込んで，鋳造して作られた「キャスト系パズル」がある．本論文では，n個の部品(ピース)からなるキャストパズルの難しさを理論的に解明する．各ピースは単純多面体とし，n個のピースが，ある空間内に(組み合わされた状態で)与えられるとする．キャストパズルは指定されたピースを外して，そのピースだけをその空間内から外に移動させることが可能か否かを問う問題とする．その結果，キャストパズルがNP困難になることを証明した． |
| 題名 | 計算万能性を有する単純な有限状相１次元可逆セルオートマトン |
| 著者 | *石井 芳 (広島大学大学院工学研究科情報専攻), 森田 憲一, 岩本 宙造, 今井 克暢 (広島大学) |
| Page | pp. 85 - 86 |
| Keyword | セル・オートマトン, 可逆 |
| Abstract | セルオートマトン(CA)の理論において計算万能性は非常に重要な 問題である． 1次元の場合，わずか2状態の計算万能CAが存在することが Cookによって証明されている． 彼はサイクリックタグシステム(CTAG) と呼ぶ計算万能な システムを2状態CAで模倣する方法を与えた． ついて述べる． 可逆CA(RCA)に関しては，Morita, Haraoにより， 任意の可逆Turing機械に対し， それを模倣する1次元RCAが構成できることが示されており， それから計算万能なRCAの存在が導かれる． その後,任意のCTAGを有限状相で模倣できる98状態の計算万能な １次元RCAがMoritaによって設計された. ここでは, 96状態で任意のCTAGを有限状相で模倣できる1次元RCAを示す． |
| 題名 | A Note on One-Way Turing Machines with Sublinear Space |
| 著者 | *義永 常宏 (徳山工業高等専門学校), 徐 建良 (Ocean University of China) |
| Page | p. 87 |
| Keyword | Turing machines, sublinear space, self-verifying nondeterminism, alternation, closure property |
| Abstract | 入力の長さの線形以下の領域量をもつ１方向チューリングマシン の基本的な性質を示している．特に，全称状態のみの交代性， 自己検証非決定性および決定性の同マシンの各受理言語のクラス は正規言語との連結や長さ保存準同型の演算に関して閉じていな いこと，また，自己検証非決定性の同クラスは補集合演算に関し て閉じていることを示している． |
| 題名 | TTSPグラフに対する簡潔表現とパス探索問題への応用 |
| 著者 | *和田 将信, 三吉 純平 (広島市立大学大学院 情報科学研究科), 糸川 裕子 (広島国際大学 心理科学部), 内田 智之 (広島市立大学大学院 情報科学研究科) |
| Page | pp. 88 - 89 |
| Keyword | 簡潔データ構造, グラフアルゴリズム, TTSPグラフ, パス探索問題 |
| Abstract | グラフデータを有効活用するには，サイズを最小限にし，かつ高速に検索する必要がある．近年，木構造データに対する簡潔データ構造に関する研究が盛んである．Ferraginaらは，辺ラベル付き木に対し，そのデータサイズを小さくする変換法としてxbwを提案するとともに，高速なパス探索アルゴリズムも与えている． 電気ネットワークなどのグラフ構造データの多くはTTSPグラフでモデル化することができる．そこで，本論文では，辺ラベル付き木に対するxbwを辺ラベル付きTTSPグラフに拡張し，変換xbwを適応されたTTSPグラフ上でパス探索を高速に行うアルゴリズムを提案し，その優位性を示す． |
| 題名 | パターン表現の計算複雑さについて |
| 著者 | *重安 芳謙, 伊藤 暁 (山口大学理工学研究科) |
| Page | pp. 90 - 91 |
| Keyword | パターン表現, 領域計算量, 多ヘッドオートマトン |
| Abstract | “パターーン表現”とは一般化された正規表現の一種であり， それらが表現する言語は線形領域限定非決定性チューリング機械で受理されることが知られている。本稿では，それらが対数領域限定非決定性チューリング機械で受理されることを示す。 |
| 題名 | スーパーパズにおける成功可能な局面の割合 |
| 著者 | *新谷 敏朗 (福山大学工学部) |
| Page | p. 92 |
| Keyword | スーパーパズ, ゲーム木, 深さ優先探索 |
| Abstract | スーパーパズはトランプの一人遊びである。このゲームでは52枚のカードをシャッフルしてすべて表向きに並べた4行13列の初期局面からルールに従ってカードを移動していき，所定の成功局面に至ることが目的である。ゲーム木の節点数が非常に多くなるため，成功可能と予想されるがまだ解が得られていない局面が存在する。ルール上列数を減らしてもプレイが可能なので，ここでは4〜6列の場合にゲーム木の節点のうち成功局面に至る可能性があるものがどの程度存在するかを調べた。その結果ゲーム木全体では成功可能な局面の割合はかなり低いが，最初の成功局面までに限ると，成功不可能な局面数の割合はそれほど高くないことが明らかになった。 |
| 題名 | High Speed Rendering Method for Complex Scenes |
| 著者 | *Matthew Johnson, 玉木 徹, 金田 和文 (広島大学 大学院工学研究科), 水上 嘉樹, 多田村 克己 (山口大学 大学院理工学研究科) |
| Page | p. 93 |
| Keyword | Raindrop, Ray tracing, Real time Rendering, Rainy weather |
| Abstract | A method which allows an application to render a large number of drops through interpolation during preprocessing. This method makes use of a unique type of ray tracing to allow for accurate interpolation. This will allow numerous accurate raindrops to be rendered at real time speeds making it useful for simulations. |