相田 慎（あいだ しん）
研究紹介
理論計算機科学の基礎をなすアルゴリズム理論および計算量理論は、表裏一体の関係にある。与えられた離散的問題に対し、コンピュータを用いて効率的に問題解決することが前者の目標である一方、効率的に解決できない問題を見つけることが後者の目標である。これらの研究では数学的手法が用いられているため、一見すると理学的であるである。しかしながらこれらの研究成果は、例えば、通信・物流などのネットワークフローの効率化や、暗号の安全性の保証など、コンピュータ社会のあらゆる場面に応用されている。
私の研究として、アルゴリズム理論の分野では、高速なグラフの同型性判定問題に関するアルゴリズムの構築を目指す。計算量理論の分野では、交替性チューリングマシンによって受理される言語クラスと既存のクラスとの関係性について探る。
テーマ1：交替性計算の潜在的能力
概要
「ゲーム理論」は、古くより様々な分野で幅広く研究されている理論であるが、いくつかの研究アプローチがある。特に、将棋や囲碁などのゲームの盤面を計算理論的に抽象・一般化し、ゲームの進行を「ある種の計算機」と見なした計算モデルが交替性計算である。このモデルは、計算量理論においては比較的古典的なものであるが、計算構造が他のモデルと比較すると極めて複雑であり、その本質的な計算能力について未解決問題が多い。
本研究は、この交替性計算モデルの概念をより明確にするために、既存の計算モデルである決定性・非決定性・確率的計算モデルそれぞれとを比較し、従来の計算量理論の手法や新しい技法を適用することで、各計算モデルで定義される計算量（すなわち、計算に必要な時間とメモリ領域）の各クラス間の未知なる関係性を明らかにすることである。
なお、科研費・若手研究(B)「交替性計算の潜在的能力」の研究代表者として本研究に携わっている。
キーワード
テーマ2：震災救助・復興支援
概要
東日本大震災初期，Twitter に寄せられた膨大なツィートには，緊急性の高い救助要請候補が多数含まれていたものの，他の震災関連ツィートや「善意のリツィート」によって，通報されるべき情報が埋もれてしまった．この様な状況を解消するために，2011年3月16日，Twitter 上の救助要請情報をテキストフィルタリングで抽出し，類似文を一つまとめ一覧表示するWeb サイトを開発・公開した．現在，本サイト技術のみならず，通報支援活動プロジェクト#99japan との具体的な連携・活用事例についても考察している．なお #99japan は，救助状況の進捗・完了報告を重視するTwitter を用いた活動であると共に，発災2 時間後に2ちゃんねる臨時地震板ボランティアらによって立ち上げられたスレッドに由来する．
キーワード
担当授業科目名(科目コード)
情報・知能工学実験