Embedded Files
離散アルゴリズム研究室では離散構造に着目した効率的なアルゴリズムの設計に関するさまざまな研究を行っています．
グラフ・ネットワークアルゴリズム，グラフ描画
重要な離散構造であるグラフ上でモデル化された種々の問題に対し，その離散構造の解明や効率的なアルゴリズムの設計を行います．
テーマ例
「密なグラフにおける影響予防境界判定問題を解く高速なアルゴリズムの設計」（2024年度，修士）
「グラフ上での二人拡散競争ゲームにおけるナッシュ均衡の頂点数による存在性」（2024年度，学部）
「ネットワーク上の最小識別コード問題に対する近傍対称差を利用したアルゴリズム」（2023年度，修士）
「影響予防境界判定問題を解く固定パラメータアルゴリズムの実用性の検証 」（2022年度，学部）
「グラフ焼失数問題に対する近傍多様性を用いたカーネル化の改良と有効性の検証」（2021年度，修士）
「最短経路問題に対する双方向探索の有効性の検証」（2020年度，学部）
「固定パラメータアルゴリズムを実現する有界探索木とカーネル化の実用的有効性の検証」（2019年度，学部）
「媒介中心性のグラフ分解を用いた効率的な計算およびその実ネットワークへの適用 」（2017年度，修士）
ネットワーク科学
現実世界の複雑な構造には，ネットワークとしてモデル化されるものが多くあります．たとえば，SNS における人間関係，インターネットの通信網，物流の流通網，生物学的相互作用ネットワークなど，多様な現象がネットワークとして抽象化できます．本研究室では，こうした複雑ネットワークの構造的性質を解析し，その成り立ちや進化，機能との関係性を理論的に探究しています．
テーマ例
「社会的距離ゲームの効用関数に基づくグラフ分割手法の実用性の検証」（2024年度，学部）
「ネットワークにおける頂点変化のグラフカーネルを用いた定量化」（2023年度，学部）
「ネットワークにおける頂点変化の定量化および腸内細菌ネットワークへの適用」 （2022年度，修士）
「感染抑制を目的とした人流制限による費用対効果の検証」 （2022年度，修士）
「媒介中心性を用いた腸内細菌ネットワークの解析」（2021年度，学部）
「Louvain コミュニティ検出法の探索手順改良による効率化と安定化に基づく実用性向上」（2019年度，修士）
「実ネットワークに対する性質検査のための超有限性の検証」（2018年度，修士）
「実ネットワークに対する性質検査のための全域分割アルゴリズムの実装と超有限性の検証 」（2017年度，修士）
離散構造
離散構造とは，上記に述べたグラフの他に，集合族，順列，組合せデザイン，ブール関数など，個別に数え上げ可能な要素から成る数学的対象の総称です．これらは情報の構造や関係性を記述する上で基盤となり，理論計算機科学やアルゴリズム設計において不可欠な役割を果たします．本研究室では，とくに幾何的な離散構造に着目し，効率的に扱うための数理的・計算的手法を探究しています．
テーマ例
「ごみ圧縮問題に対する高速なアルゴリズムの設計」（2024年度，修士）
「2×n地図の平坦折り可能および不可能パターンの発見」（2024年度，学部）
「地図折り問題における平坦折り不可能な3×n地図の発見」（2023年度，学部）
「ごみ圧縮問題における圧縮不可能条件」（2022年度，学部）
「地図折り問題に対するSAT定式化とASP定式化の性能評価」（2022年度，修士）
「地図折り問題における平坦折り不可能地図の列挙および平坦折り不可能パターンの発見」（2022年度，修士）
「SAT型ソルバを用いた地図折り問題の求解」（2018年度，修士）
組合せ最適化
限られた資源の中で最善の選択を行う——このような問題は，工学，経済学，人工知能，ネットワーク設計など，あらゆる分野に現れます．組合せ最適化は、離散的な選択肢の中から最適な解を効率的に見つけることを目指す理論と技術です．
テーマ例
「コンテナ積み替え問題に対するクレーン操作時間評価の改善によるアルゴリズムの高速化」（2023年度，修士）
「解集合プログラミングを用いた非接触パッキング問題の優良解探索手法」（2022年度，学部）
組合せパズル・ゲーム
組合せパズルは，限られたルールと初期条件のもとで，特定のゴール状態（たとえば充足解や構造的配置）を見つけることを目的とした問題です．本研究室ではナンプレ（数独），ぬりかべ，スリザーリンクなど，いわゆる「ニコリ系パズル」なども含むパズルや，それらを一般化したパズルの離散構造の解明を行っています．
テーマ例
「重力を利用した物理的ゼロ知識証明：ストストーンとドッスンフワリへの適用」(2024年度，修士)
「Gourdsパズルの二段盤面における最大最短手数」（2023年度，学部）
「パズル「シャカシャカ」の正方形盤面での最少ヒント数」（2017年度，学部）
Page updated
Google Sites
Report abuse