春休み折り返し
春休みもそろそろ半分くらい経ったので、勉強の進行具合をまとめてみる。
3冊借りたけど、『Introduction to Algorithms』しか読んでいない。というか、この本が面白すぎて復習などやっている場合ではない！全35章ある本で、休み中に17章まで行きたいと思っている。ちょうど今日、9章まで読み終わった。やった内容は、
- 挿入ソート
- マージソート
- 計算量解析の基本的手法（マスターメソッドなど）
- 乱択アルゴリズムと確率的アルゴリズム解析
- ヒープソート
- クイックソート
- 比較ソートの下限と分布数え上げソート・基数ソート・バケットソート*1
- メディアンと順序統計量を求めるアルゴリズム
色んなソートを勉強した感じ。データ構造の話をやれば、学部でやるレベルのデータ構造とアルゴリズムについては一通りやったことになるだろう。
やっぱりこの本は厳密さがあっていい。計算量の評価もしっかりと漸化式で評価して、証明しているのがいい。そこらの本だと「ループがn回回って、1回のループでO(n)だから全部でO(n^2)でしょ？」みたいな書き方がしてあったり、証明が載ってないこともしばしば。
それよりも、けっこう微積の知識を使うことに驚いた。計算量解析なので、よく考えれば当たり前なんだけど。
ノートを書き書き勉強していたら、今1冊半消費した。全部英語で書いているのでしんどいけど、だんだん数学で使う英語表現がわかってきた。
もう微積と線形の復習は諦めて、春休みまでに目標の17章まで行くことを目指そう。
