| 題名 | 条件付ラッシュアワー問題の計算複雑さ |
| 著者 | *西尾 研二, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 189 - 190 |
| Keyword | ラッシュアワー, 計算複雑さ, NP, P |
| Abstract | ラッシュアワーとは，6×6マスの盤上に車が配置されていて，指定された1つの車(ターゲットカー)を，EXITと書いてある場所へ誘導して行き，そこから盤外へ出すゲームである．kei本研究では，ラッシュアワーをN×Mマスに拡張した，一般化ラッシュアワー問題を考える．また，問題には難しさの階級がつけられており，その階級に属するNP，P完全性について取り上げる．一般化ラッシュアワー問題に，条件を付けたラッシュアワー問題のことを，条件付ラッシュアワー問題と呼ぶ．本論文では，一般化ラッシュアワー問題に条件を付けたラッシュアワー問題は，NP困難またはP困難であるということを証明する．また，条件付ラッシュアワー問題はクラスNP，Pに所属するということを証明する． |
| 題名 | セルオートマトンとチューリング機械の交代性時間量の階層 |
| 著者 | *立花 大輔, 岩本 宙造, 森田 憲一, 今井 克暢 (広島大学大学院工学研究科情報工学専攻) |
| Page | pp. 191 - 192 |
| Keyword | 交代性, セルオートマトン, チューリング機械, 階層 |
| Abstract | セルオートマトン(CA)は，セルと呼ばれる同一の有限オートマトンを空間に一様に配置，接続したシステムである．また，チューリング機械(TM)は，有限制御部，左右に無限に長いテープ，読み書きを行うヘッドから成るシステムである．本論文では，それら2つのモデルの計算を並列化した交代性CA(ACA)と交代性TM(ATM)に着目する．本モデルに対して再帰的詰め込み論法を用いることによって，ACA(ATM)の時間階層定理を証明する．$t_1(n)$，$t_2(n)$を時間構成可能という性質を満たす関数とする．$t_2(n)$が$t_1(n+1)$よりも真に成長が早いとき，$t_1(n+1)$時間のいかなるACA(ATM)でも受理できないが，$t_2(n)$時間のACA(ATM)で受理できる言語が存在するということを示す． |
| 題名 | 計算量漸化式の微分方程式化について |
| 著者 | 泉 裕介, *伊藤 暁 (山口大学理工学研究科) |
| Page | p. 193 |
| Keyword | 微積分, 漸化式, オーダー |
| Abstract | 計算量を表わす漸化式の解法としては従来から，展開法，母関数，数学的帰納法などが知られている． これらに対し，漸化式を一旦微分方程式化してその連続解を代数的に求める手法は直観的かつ容易であり， しかも元の方程式の厳密解を精度良く近似している場合が多い． 本稿では，このような微分方程式化解法の理論的根拠を初等的に示すとともに，様々な具体例について解の妥当性を検証する． |
| 題名 | A Relationship between Turing Machines and Finite Automata on Four-Dimensional Input Tapes |
| 著者 | *坂本 眞人, 伊藤 孝夫, 岡谷 哲志, 福田 正嗣, 古谷 博史 (宮崎大学), 井上 克司 (山口大学) |
| Page | p. 194 |
| Keyword | automaton, computation, complexity |
| 題名 | LDPC符号による2値画像の為の符号化と復号 |
| 著者 | 岩竹 勝平, 筒井 雄一郎, 中本 弘一, *保田 大樹, 相田 敏明 (岡山大学大学院 自然科学研究科) |
| Page | p. 195 |
| Keyword | LDPCC, 通信路符号化, 統計力学 |
| Abstract | 本研究のテーマは2値画像の通信路符号化で，復号の際に画素間の相関の強さを取り入れることにより誤り訂正能力の向上を図る． 現在は通信時間の短縮の為に，データを圧縮後，通信路符号化を行うのが一般的である．これはデータ圧縮により情報源のエントロピーを大きくしてしまった為に，より多くの冗長ビット（強い冗長化）を必要とする．我々の研究では，情報源のエントロピーに応じて，符号化率を調節した符号化を行う．この符号化はランダム疎行列との積により実行される，情報源符号化と通信路符号化を統合したものであり，符号化・復号において2段階のプロセスを経由しない効率的なものである． |
| 題名 | 非線形システムのLyapunov 指数の評価法 |
| 著者 | 畑井 宏太 (岡山情報処理センター), 徳山 貢 (倉敷工業高校), *太田垣 博一 (岡山理科大学) |
| Page | p. 196 |
| Keyword | 非線形システム, Lyapunov 指数, Lorenzモデル |
| Abstract | 非線形システムの振動の態様を解明するためには Lyapunov 指数の評価をすることが有効である. しかしながら，実験の条件によっては正確なLyapunov 指数が得られないことがある． 本研究では，カオス振動の発生を確認するために有効なLyapunov 指数の評価法を提案する. |