さかなの思い

競技プログラミングの話が主になるかもしれません

演習Ⅲ体験記

東京大学名物授業その2の演習Ⅲを受けたので、その時の記録を残しておきます。
(備忘録的な要素が大きいです)

はじめに

東京大学の理学部情報科学科の4Sセメスターでは、情報科学演習Ⅲという授業が開講されます。この授業では、1ヶ月ずつ、3つの異なる研究室に配属され、そこで研究や演習を行います。テーマなどは自分で設定して、自分で調べた内容を紹介する・論文の追実装を行う・新規性のあるアイデアを提案するなど、様々な発表ができます。(研究室にもよりますが)

今回の授業ではコロナウイルス感染拡大の影響も受け、全ての発表はオンライン形式で行われました。Zoomを用いた発表だと、聞いている人たちの反応を直接得ることができず、なかなか大変でした。

第1期:Fine-grained complexity

第1期では、計算量理論について、特に"Fine-grained complexity"について扱い、内容を読んで発表しました。"Fine-grained complexity"とは、計算量クラスについて、P vs NP よりも精緻な分類をPの中で行うというものです。内容としては、(min, +)-convolution と色んな問題が計算量的に等価であることの証明や、数え上げ問題における最悪計算量ケースから平均計算量ケースへのReductionなどを扱いました。個人的には、LCSを解く計算量o(N^2)のアルゴリズムが存在しないと予想されている話などが、自分の日常生活と結びついていて面白かったです。

第2期:pix2pix

第2期では、pix2pixと呼ばれる、ディープラーニングを用いた画像処理について学習し、追実装を行いました。pix2pixとは、2つの画像のペアからその間の関係性を学習することで、ある画像から別の関連する画像を生成するモデルを構築するための技術です。例えば、モノクロ写真をカラー写真に変換したり、昼の風景の画像を夜の風景に変換する、などの応用例があります。学習により生成された画像は結構不気味で、深夜の作業中に生成画像をチェックするのにビビってた記憶があります。

第3期:Contraction Hierarchy

第3期では、経路探索アルゴリズムの高速化手法の一つである、"Contraction Hierarchy"について扱い、追実装を行いました。この技術は、巨大なグラフに対して、重要でなさそうな頂点を削除しながらshortcutと呼ばれる短絡辺を追加する前計算を行うことで、のちに与えられる大量のクエリに対して高速に回答できるようにする、というものです。第3期では、第1期・第2期と違って、割とテーマに関する自由度が大きかったので、面白いテーマを選択するのに苦労しました。

個人的な感想

あまり満足できない結果になりました。というのも、どのテーマについても、何か新しいアイデアを発信できたわけでもなく、かといって既存論文を超える性能を発揮できたわけでもない、というかなり微妙な結果に終わってしまったからです。反省点としては、(CPU実験の時にも感じたことですが)僕は目の前の結果に固執してしまう傾向があり、事前に設計について吟味したり、世の中ではどういう先行研究が存在するのかなどを事前にリサーチする能力が低いのだと感じました。そのため、すでに研究され尽くしているテーマを無謀にも選択し、何も結果を残せずに終わってしまう、ということが多かったように感じます。付け加えるなら、目の前のことに集中できず、すぐにTwitterYoutubeを開いてしまう癖がついてしまったのも良くない点だと思います。卒論研究ではこれらの反省点を改善し、大学生活の締めを有意義なものとしたいです。