卒業研究 テーマ
1. 適当な組合せ問題やアルゴリズム論の問題について、いろいろな性質を考えます。パズルを解くような感覚で、問題を解いていければ、と思っています。大切なことは考えることです。扱う問題として、例えば、マージングネットワークの下界、グラフの同型問題、確率アルゴリズム などです。
2. コンピュータを使って計算を行い、組合せ問題の性質を証明することを考えます。例えば、数千数万あるいはそれ以上の場合わけを行ない、各々の場合についてひとつひとつ調べる計算をします。単なるプログラム書きだけでなく、バックトラック、データ構造の知識、メモリ管理などのソフトウェア技法を必要とします。例えば、ソーティングの比較回数の下界の計算や、マージングネットワークにおける比較器数の最小数を計算します。
3. さまざまな問題に対し、効率のよいアルゴリズムが提案されています。これらのアルゴリズムを述べている文献を購読し、別の種類の新しいアルゴリズムを考案します。効率のよいアルゴリズムは、今まで解けなかった問題が解けるようになるばかりでなく、資源全体を有効に活用します。また確率アルゴリズムや、他の計算モデルにおけるアルゴリズムについても検討します。
4. アルゴリズム理論、オートマタ理論、スイッチング理論、形式言語理論、計算量理論、などの計算機科学基礎理論から適当なテーマを選び、文献を講読します。この他、推論検証、組合せ理論、フーリエ変換、コンパイラなどに関するテーマを設ける場合もあります。
5. パズルのNP完全性に関する卒研生の結果です。
興味ある方は随時見学可能です。西9-537 (教官室)、西9-539 (コンピュータ室)、西9-538 (学生室)、西9-540 (ゼミ室)です。
