我々の研究室では、アルゴリズムを研究対象としています。
現代社会では、コンピュータの利用は欠かせません。実際、スマートフォンや家電、自動車など、身近にある多くのものにコンピュータが搭載されています。コンピュータの内部では様々な計算が行われているのですが、この計算を行う手続き(プログラムのようなもの)をアルゴリズムと言います。下手なアルゴリズムを使うと、いつまでたっても計算が終わらず、例えばwebを検索して1時間以上待っても結果が返ってこないという事態に陥ります。したがって、高速に計算を終わらせるアルゴリズムを使うことが重要です。
我々の研究室では、アルゴリズムを設計し、そのアルゴリズムの効率(計算の速さやメモリの使用量、計算の正確さなど)を評価するという研究を行っています。評価には、大きく分けて実験的アプローチと理論的アプローチがあります。実験的アプローチでは、設計したアルゴリズムをプログラム化し、様々な入力を与えてみて効率を測定します。理論的アプローチでは、アルゴリズムの動作を解析して効率を数学的に保証したり、問題が効率よいアルゴリズムを持たないことを証明したりします。私自身は後者の理論的アプローチ(「アルゴリズム理論」、「理論計算機科学」などとも言います)を取っていますが、卒論や修論のテーマは学生さんの興味を尊重しますので、実験的なアプローチを取っても良いです。なお、卒論の場合は希望する研究室に配属されない場合もありますので、自分の興味に応じてアルゴリズム以外のテーマを選定しても構いません。(ただし、私の守備範囲を超えるテーマは、かなりの部分を自力でやって頂かなければなりません。)修士・博士の場合は私の研究室を希望して受験するはずなので、私の専門に近いテーマで研究して頂くことを前提としています。
最近の研究テーマ例としては、グラフ探索、グラフ分割、安定マッチング、スケジューリング、オンラインマッチングなどがあります。
アルゴリズム開発はパズル的な要素が多く含まれており、パズル好きの学生は楽しみながら研究を行うことができるでしょう。また、アルゴリズムの性能評価には、数学的・理論的な評価や、プログラムを作ることによる実験的な評価など、いろいろなアプローチがありますので、自分の得意な方法で進めることができます。
アルゴリズムの開発には柔軟な発想やアイデアが重要ですので、若い学生が活躍できるという魅力もあります。実際、重要な未解決問題を学生が解き、世界的に有名な賞を受賞した例もあります。
教員
宮崎修一(教授)
大学院生
Zhang Yinhao (チョウ インコウ)(M2)
学部生
猪崎 俊成(B4)
河野 良太(B4)
佐々木 伊吹(B4)
竹蒔 宏基(B4)
仲村 礼央(B4)
本間 史(B4)
卒業生・修了生
2023年度学部卒
穴瀬 龍汰:アルバイトのシフト作成問題に対する数理計画を用いた解法
北野 浩至:学生とアパートの部屋割り問題に対するアルゴリズム設計
小西 雅己:麻雀における13枚の手牌からシャンテン数を導出するアルゴリズム
柳瀬 広大:個人に適合したウエイトトレーニングメニュー提案システムの構築
山口 祐司:グラフ畳み込みネットワークを利用した楽曲推薦に関する研究
2024年度学部卒
川瀬 颯太:Computational Complexity of Envy-free and Exchange-stable Seat Arrangement Problems on Grid Graphs
鬼海 侑吏:過密日程を緩和しつつチーム間の公平性を最大化するサッカーの対戦表作成アルゴリズム
小山 樹人:AKQJゲームの均衡解析
2024年度卒研修了
木原 滉一:最大葉全域木問題に対する2-近似アルゴリズムの最悪例の考察
川瀬 颯太, 宮崎 修一, "グリッドグラフ上における無羨望座席配置問題及び安定座席配置問題のNP完全性", 冬のLAシンポジウム, 発表番号 S17, 2025年1月.