折り紙、パズル、ゲームを学んで
柔らかな知力を身につけよう！

上原研究室　UEHARA Laboratory
教授：上原 隆平（UEHARA Ryuhei）

E-mail：
［研究分野］
理論計算機科学・計算量理論・アルゴリズム論・計算幾何学
［キーワード］
計算折り紙、組合せ最適化、グラフアルゴリズム、ゲームやパズルの計算量

研究を始めるのに必要な知識・能力

数学に関しては、基礎的な離散数学やグラフ理論が必要となる。授業科目の「アルゴリズムとデータ構造」程度の知識は必須となる。パズルやパズル的なもの、折り紙やアルゴリズムに興味があり、何かをずっと考え続けることが好きなこと。

この研究で身につく能力

研究活動は、まず研究対象となる問題を把握すること、把握した問題を解決すること、結果を発表することという三つの段階からなる。修士研究においては、自分で独自の問題をゼロから見つけてくることは簡単ではない。そこで、グラフアルゴリズムなどの基礎分野の学習を通して、現在解かれていない問題や解くべきテーマを見つけることを目指す。この際に、日本語だけではなく、英語の文献を読む能力を身につける。問題解決に関しては、基礎理論をきっちりと身につけて、それを使いこなして解決する能力の獲得を目指す。また研究活動においては、十分なプレゼンテーション能力を身につけることも重要である。一連の研究活動を通じて、知的な基礎体力が身につき、長期的な問題解決能力が向上する。

【就職先企業・職種】 情報通信・情報処理産業、技術コンサルタント会社など

研究内容

　折り紙やパズルといった、一見、情報科学とは関係がなさそうなテーマの中にも、実はコンピュータサイエンスが隠れている。例えば「折り」を基本的な演算であるととらえると、「折り紙を折る」という行為は、コンピュータでいうところのアルゴリズムに対応する。つまり同じ折り紙でも、効率のよい手順を考えたり、ある種の問題の困難性を数学的に示せることもある。こうした「問題の抽象化」は、実はあらゆる分野に応用がある。そして抽象化した問題の「解法を理論的に考える」ことこそ、まさに理論計算機科学の醍醐味なのだ。
　時には、ある問題が「どうしようもなく難しい」ということが理論的に示されてしまう場合もある。難しいからといってあきらめられればよいが、そうも言っていられない。こうした「計算が困難な問題」に対して、何らかの妥当性をもつ解を、現実的な時間で与えることが上原研究室のメインテーマの一つである。
　その一方で、ある問題に対して、有効な解決方法が見つかることもある。そこにはそれまで誰も知らなかった解法があるはずで、その解法の記述こそが「アルゴリズム」である。良いアルゴリズムには、単なる思い付き以上の理論的な保証がある。こうした効率のよいアルゴリズムの理論保証も、上原研究室のメインテーマの一つである。
　もう少し具体的に上原研究室の研究テーマを詳しく説明しよう。以下の三つのテーマが最近の中心的な研究テーマである。

①計算折り紙

　計算折り紙は計算幾何学の中でも新しいテーマであり、特に折りのアルゴリズムや計算量については、日本では本研究室が最先端である。例えば単純なジャバラ折りを例として取り上げてみよう。端から順に折り目をつけていけば、簡単に折り目をつけることができる。しかし、紙を重ねて一度に折れば、もっと早く折り目をつけることができるのではなかろうか。こうした折りを定式化して、効率のよい折り手順を考えることこそ、アルゴリズムの開発に他ならない。そして実際、非常に高速にジャバラを折るアルゴリズムが存在する。こうした効率を理論的に評価して、アルゴリズムのよさを示すことができる。
　また一方で、紙の重なりが多くなると、誤差が出たり、折りにくくなったりしてしまう。こうした紙の厚みを評価基準にすれば、まったく別の評価基準に基づいたアルゴリズムの問題を考えることができる。こうした問題のモデル化や理論的な解析が計算折り紙の重要なトピックである。

②ゲームやパズルの計算量

　パズルやゲームの理論的な困難さや、具体的な解法のアルゴリズムの効率の研究も、理論計算機科学の世界では昔から活発に行われている。それはパズルやゲームが、ある種の計算メカニズムとみなせるからだ。ある種のゲームやパズルは、計算の本質を抽出し、アルゴリズムや計算量の研究対象として非常に有用である。

③グラフアルゴリズム

　世の中の「つながり」は、抽象的なグラフ構造で表現することができる。こうした抽象化モデル上でのアルゴリズムの研究や開発は、現実的なアルゴリズムにもつながり、その一方で、グラフ上での困難性の証明は、その問題の本質的な難しさを浮き彫りにしてくれる。
　以上の他にも、理論計算機科学や離散数学に関する研究テーマを全般的に手がけており、そうした研究テーマをやりたい学生は、幅広く受け入れている。

主な研究業績

1. Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka, and Toshiki Saitoh. Sorting Balls and Water: Equivalence and Computational Complexity, Theoretical Computer Science, Vol. 978, 114158(15 pages), August, 2023. DOI:10.1016/j.tcs.2023.114158
2. Ryuhei Uehara. Computational Complexity of Puzzles and Related Topics, Interdisciplinary Information Sciences, Vol. 29, No. 2, pp. 119-140, December, 2023. DOI:10.4036/iis.2022.R.06
3. Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara. Developing a tetramonohedron with minimum cut length, Computational Geometry: Theory and Applications, Vol. 108, 101903(11 pages), 2022. DOI:10.1016/ j.comgeo.2022.101903