理学部情報科学科3A
3Aの振り返りメモです、20erの方の参考になれば幸いです。 3Sについてはこちらをご覧ください理学部情報科学科3S - okura diary
対象読者誰？みたいな内容になってますがただのメモなのでご了承ください。
3Aの概観
準必修で先取りできるものもなく、基本的には皆必修のみです。課題との向き合い方次第*1で楽もできる(他のことに時間をまわせる)し忙しくもできるのかなと感じました。CPU実験がメインでそればっかりに集中できると思ってたらそうでもなく、他の課題も結構多いのでそれを片付けているとCPU実験に回せる時間もそこまで多くはない、というのが学期が始まる前に抱いていたイメージとの一番大きなギャップでした。
各授業の詳細
月2 言語モデル論
未だに言語モデルという言葉の指すものはよくわからないですが、3Sの言語処理系論の続きとなる授業です。言語処理系論がコンパイラなどプログラミング言語のsyntaxの部分を主に扱っていたのに対してsemanticsを主に扱う授業と言っても良い気がします。意味論には大きく分けて
- 操作的意味論
- 表示的意味論
- 公理的意味論
がありますが、この授業の前半ではインストラクションと評価文脈による操作的意味論の定義、ホーア論理(公理的意味論の一つ)による(半)自動プログラム検証の2つが重点的に取扱われます。表示的意味論は1回の授業でさらっと扱われるにとどまります(これは3Sに不動点演算子で再帰関数を書き換える課題などををやっているからだと思います)。 後半ではラムダ計算や型システムなど関数型言語に関連する話題を扱います。これは3SのFL実験の内容と重複して復習となる部分も多いです。
月4 連続系アルゴリズム
講義タイトルの通り連続量の問題を機械で解くためのアルゴリズム類を扱う授業です。 sd先生とysmt先生の2人が担当されていて、sd先生は主に常微分方程式、偏微分方程式の数値解法を、ysmt先生は主に行列の分解やCG法など多変数連立一次方程式の解法をそれぞれ主に扱っていた印象です。
sd先生パート
まず浮動小数の誤差評価の話から始まって、次にNewton法や減速Newton法など零点を求める方法を扱います。ホモトピー法笑 次に常微分方程式の解法として、Euler法、Runge-Kutta法をやってそのあと移流方程式や拡散方程式を差分法で解きます。ポアソン方程式を差分法で離散化すると大規模疎行列が係数の線形方程式になってysmt先生パートで学ぶ方法が使えるというのは面白かったです。これら以外にもFFTや加速、乱数なども扱われます。(結局加速って何やったんや...？)
ほとんどの課題で「方程式の数値解を描画せよ」という要件があるのでだいたいの人はPythonでMatplotlibを使っていました。自分は初めはPython書きたくないしモジュールの使い方を調べるのが面倒だったのでC++でファイル出力してgnuplotで描画してたのですが、あまりに面倒なのでmatplotlibに変えました。後述する知能システム論でも同様に描画を要求され、1セメスター通して使い続けることになるのでsubplotとかの使い方も早い内に慣れてしまうのがいいと思います(もう忘れてしまいましたが...)
ysmt先生パート
普通に掃き出し法で連立一次方程式を解くところから始まって、LU分解などの直接法をやった後、CG法、Gauss-Seidel法、SOR法などの反復解法を扱います。 他に冪乗法、Jacobi法で固有値を求めたり、Householder変換で三重対角化したり、特異値分解したりします
火2 計算量理論
タイトルの通り計算量についての授業です。決定性、非決定性チューリングマシンの定義から始まって、SATのNP-completeness(Cook-Levinの定理)を説明して、KarpのReductionでいくつかの問題がNP-completeであることを示します。 NP-completeな問題に対する解法として近似アルゴリズムを扱い、Metric-TSPに対する定数近似アルゴリズムやKnapsack問題に対してPTAS(Polynomial-Time Approximation Scheme)、FPTASを構成したりします。(この前のHash CodeのpracticeのKnapsackは貪欲とDPを適当に組み合わせたら全部入ったのでScalingとかが活用できなくて悲しかった)
火3,4,5 CPU実験(プロセッサ実験)
これに関しては別記事にまとめたのでこちらをご覧ください。
僕の呼びかけで、進捗発表が終わった後にCodeforcesのバーチャルコンテストを集まった人でやっていました。声をかけても人集まらないかなと思ってたのですが7人くらい集まったので3Sからやっておけばよかったと後悔しています。
水2 コンピュータネットワーク
A1タームのみの授業で、TCP/IPの基礎的な内容を一通り学びます。
木2 知能システム論
大きく分けて確率と統計の基礎、教師あり学習、教師なし学習、強化学習、自然言語処理を扱います。連続系アルゴリズムと同様に何度もビジュアライズを要求される課題が出ます。数学的に細かいところまでを教えてもらえるわけではないので、ちゃんと理解できてないけど書いてあるとおりにやったらなんかうまい感じにできてしまったみたいなことがありました(主成分分析やサポートベクトルマシンの課題とか)。カーネルトリックとか未だによくわかっていないので4Sで統計的機械学習を履修するなら要復習という感じがしています。
木3,4,5 コンパイラ実験
MinCamlというOCamlのサブセットのコンパイラを題材にコンパイラの基礎的な構成や最適化について学ぶ演習です。
前半
前半では既にMinCamlで実装されているK正規化、α変換、クロージャ変換、仮想マシンコード生成、レジスタ割付、機械語生成などの流れの詳細について理解します。
課題では別の変換を実装したり、より効率的と考えられる実装法を試して比較検討を行うといったものが多いです。(構文解析、型検査に関しては3SのFL実験と同じなので触れられません)
後半
後半では型多相、グラフ彩色によるレジスタ割当、データフロー解析、ループ最適化、JIT、GCなどMinCamlに限らずにより一般的なコンパイラの技術について学びます。
課題では既存の処理系での実装の詳細を調べたり論文を読んで説明させる説明系と、上に挙げた機能をMinCaml(もしくは自身がフルスクラッチしたコンパイラ)に追加する実装系があります。実装系課題はかなり重い傾向にあり、コンパイラ係以外で実装系課題をやっている人を見かけた記憶があまりありません。自分はコンパイラ係になったんやから課題は全部やろう、と思っていましたが実装系課題は締め切りに間に合わずできなかったものが多かったです。
課題について
3SのFL実験では実装系ではだいたい実装方針のお手本のようなものがあるのですが、この授業ではそういったものがありません。なので自分で考えた方針で実装するのですが、自分の方法が本当にいかなるソースコードが入力のときもそのプログラムの意味を変えないものであるのかを証明する手段がなく、なんとなくいくつかサンプルを作ってそれが動いたからOKとするしかないモヤモヤ感のなか課題を進めていたのを覚えています。できれば課題の期限終了後にお手本実装や想定解法を教えていただきたかったなぁという思いがあります。(実際にできたと言っている人に壊れる入力を与えたりして遊んでいました、被害を受けた方達ごめんなさい)
金2 科学英語
Wright先生の授業を選んでハンバーガーを食べると2単位がもらえます(注:これは必修ではありません)
金3,4 情報科学演習II
3Sの演習Iと同様に計算量理論演習と連続系アルゴリズム演習が隔週であります。
計算量理論演習
離散数学演習同様に計算量理論の授業と進度的にリンクしているわけではないですが内容的には同様です。各問題に点数がついていて低い配点の問題がなかなか解けないとつらい気持ちになることもありますが、全体を通じていくつか典型テクみたいなの(時間を犠牲にして空間を減らす、とりあえずSATで代表させてみる等)が見えてくると結構な問題を気持ちよく解くことができるように感じました。
連続系演習
こちらは基本的に授業で扱った方法の実装、評価が主な課題です。ですが授業の方でsd先生が出す課題と被っている部分がかなりあるのでそちらを先にちゃんとやっていればとても楽に済ませることができます。また完全に連続系の授業の内容のみではなく、授業で扱わなかったがこちらで扱ったトピックとしてはMPIによる並列計算やCUDAの利用などがありました。
その他
まとめっぽい内容が思いつかないので雑多なことを書きます。僕はほとんど旅行に行ったことがないタイプ(?)の人間なんですが、学期中に同期の友人*2に誘われて温泉地でまったりする楽しみを覚えてしまいました。スマブラが操作方法すらわからないところからみんなでワイワイできる程度になりました。あとハイパーロボットが多少うまくなった気がします。
まとめ
まぁがんばったのでOKです
*1:3Sはどの課題もここまでは必須、これはオプショナルといった形のものが多いのに対して3Aはこの階層構造が更に複雑になっています。 例えばコンパイラ実験は12回の内6回以上提出が必要、12回それぞれが次のn問の内m問以上を解答せよという形式(連続系演習も同様)、連続系の授業課題は課題がそもそもオプショナルでその中にオプショナル1とオプショナル2がある、といった感じです。授業のとある回の課題の提出を丸々しない、というのがどうも違和感があって結局どの授業のどの回も少なくとも提出要件を満たす分だけはやって出すようにしていましたが、もともとシステムがこうなっている以上面倒な課題は飛ばして別のことに時間を充てるのが得策ではあると思います。
*2:彼がスイスに行ってしまって寂しい
