やかんです。
試験が近い（1週間後！）ので、ちょこちょこ復習を進めていこうっていう記事になります。
試験について
サンプル数少ないのでなんとも言えないところが大きいですが、理学部開講科目のこの授業、工学部開講科目のOS、工学部開講科目の数理手法1と見てみて、学部的に過去問が「すごい大事」とされているなあと言う印象です。
やっぱり、理学部とか工学部は、全然知りませんが、研究室配属とかで成績が大事になってくるからでしょうか。
それに対して、法学部は過去問を見たところで意味がわからないんですよね。。「試験自体の重さ」で言うたら法学部ってなかなか重い方なんだなあなど思いました。
まあ、わからないんですけども。
過去問見た。
この授業の過去問は1週間前くらいに見ました。実装は不要で、とにかくアルゴリズム周辺の概念を理解してますか？っていう試験の印象。概念わかってれば実装できるでしょっていうスタンスなんですかね。
実装はGPTとかがやってくれるしね。
あと、しっかり解析が求められるんだよな。。これ怖いな。
データ構造
ヒープ
ヒープは優先度付き待ち行列です。
- あくまで、「半順序」であって「順序」は完全にはついていない。
- 木の高さは平均してlognになる。nは要素数。底はもちろん2。
二分探索木
計算量を導出する。
- 二分探索木は、改めて実装してみてもいいかもな。delete minのところ。
間接点
「なぜそうなるのか」はわからないが、とりあえずアルゴリズムは頭に入っていると思う。まあ要復習。
ベルマンフォード
一回実装してみてもいいかもしれない。
ダイクストラ
これは大丈夫じゃないかなあ。
分割統治法で長大整数の掛け算
再現できるから、まあちゃんと定着させるだけだよね。
やることなど
- 二分探索木のdelete min実装。 → これは不要。
- 二分探索木の解析について質問。 → Done
- avl木の各メソッドを再現。
- 動的計画法の表を描く。
- Aスターとか。
- ベルマンフォード法を実装してみてもいいかもしれない。
- 間接点のアルゴリズム。
ということでday1終了。最後までお読みいただき、ありがとうございます。
