スタンフォードのアルゴリズム講座その１を受けてみた
3行まとめ
- スタンフォードのアルゴリズム講座受けてみた
- 課金して自分を追い込み
- アカデミックさと理論的な解説は面白い
アルゴリズムのオンライン講座を受けることにした
昨年の年末に色々今年やりたいこと、目標を考えていたのですが、兼ねてからコンピューターサイエンスをアカデミックな環境で学びたいなと思っていました。
それで何かしようということで色々調べていました。
いくつか選択肢がありました。
- 夜間の定時制の講座
- 社会人向けの大学院
- オンラインの大学課程
どれも魅力的に思えましたし、例えばコンピューターサイエンスの学位があったらかっこいいなあとか思っていましたが、今回はcouseraというサービスでスタンフォード大学のアルゴリズム専門講座というコースを受けることにしました。
https://jp.coursera.org/specializations/algorithms
理由は - 大学院に進学するにしても、特に現時点で研究したいテーマがあるわけではなく、色々知りたいなあ程度の解像度→研究ではなく学部レベルの勉強をする
- なんでも知りたいというより、自分が知りたいことを考えてみると、とりあえずアルゴリズムとデータ構造をアカデミックな文脈で知りたいなと思った→いきなり入学するのではなく、一旦講座レベルで受講する
でした。
こちらのアルゴリズム専門講座は４つの講座から成り立っているのですが、この記事はその中の最初 この講座を受けてみたよー、という記事です。
講座の内容
まずアルゴリズム専門講座の全体の流れを以下に示します。
- Divide and Conquer, Sorting and Searching, and Randomized Algorithms
- Graph Search, Shortest Paths, and Data Structures
- Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
- Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
パッと私でもわかりそうな単語を拾っていくと、最初に分割統治をやって、そっからグラフに関するアルゴリズム、そして三番目で貪欲法とDPみたいなことをやって、最後にNP完全とかの話をやるみたいです。
私が競プロとかでよく見る記事だと全探索やってBFS, DFSやって二分探索やって・・・みたいな感じが多い？気もするのでなんかちょっと順番に新鮮味を覚えました。どういう意図でこの順番にしているのかは気になります。
そして、今回受講した講座のシラバスを以下に示します。
- Introduction; "big-oh" notation and asymptotic analysis.
- Divide-and-conquer basics; the master method for analyzing divide and conquer algorithms.
- The QuickSort algorithm and its analysis; probability review.
- Linear-time selection; graphs, cuts, and the contraction algorithm.
最初にアルゴリズムの解析法の基礎としてオーダーの記法を導入した後に、分割統治の考え方を導入します。そしてその応用として、クイックソートを扱い、ここで乱択アルゴリズムの考え方も導入しています。最終週ではもう少し解析を深めた後に、グラフについて簡単な導入をしています。
講座の流れ
一つの講座は一週間単位で区切られています。
一週間の中でまず講義のビデオを視聴します。講義スライドや参考資料も見ることができます。この講座は日本語字幕はなく（いつか作れたらいいなとも思いつつ）、英語字幕はあります。でも、スライドの文字を見ながら色々ググればなんとなく言っていることの大まかなところは分かります。数式とコードがありますので。とはいえ、やはり注意深く聞いているとスライドには載っていないいいことを言っていたりもするので、きちんと聞くに越したことはないでしょう。講義の途中にクイズがあって、それで理解を確かめることもできます。skipもできます。
その週の講義を受け終わると、テストを受けます。テストは二種類あり、一つは選択式の講義の理解を問うクイズです。結構計算したり手元で学んだアルゴリズムを再現してみたりする必要があります。もう一つは、コーディングクイズで、自分で学んだアルゴリズムを実装してみようというものです。問題としては手元で実装したコードを動かさないとわからないような問題が出ていて、その答えを貼るというものです（コードそのものが評価されるわけではないということです）。
あとは、時々講義の中に発展的な内容の講座もあり、より理論的な講義や、考えさせるクイズが載っていたりもします。時間的にあまりできませんでしたが、きちんと考えると面白いだろうなあと思いました。
HPには大体4~5時間一週間あたりかかると書いていましたが、自分の実力だと結構復習と課題に時間がかかっていたりして、倍ぐらいかかったなあという週もありました。
講座を受けてみてよかったこと・その他感想
基本的なアルゴリズムでもちゃんと話を聞いてみると色々知らないことがあって面白い
最初の二分探索とか、それは知っているよ〜みたいな感じでしたが、改めてきっちり話を聞いてみると理解が深まります。また、分割統治のアルゴリズムについてより一般的な理論についても知ることができたので、こういうのはやはり大学の講義ならではだよなあと思っていたりもしました。あとマージアルゴリズムのことあんまりよくわかっていなかったりもしたので、そういうのも基礎知識の補完になってよかったです。
アルゴリズムを知っていることと実装することは大きく違う
これもまあそれはそう、って感じの感想です。競プロを前にやっていてそれは痛感していましたが、なんとなくこんなことをやるアルゴリズムだなあと知識で知っているのと、それを実際に実装に起こしてコーナーケースまで考える、というのは結構な違いがあります。
今回のコーディングの課題でも変なミスをして何時間もバグを見つけられず溶かした・・・ということがありました。
自分で実装してみるというのは大事だなあ、という当たり前のことですが再実感できました。
乱択アルゴリズム面白くない・・・？
乱択アルゴリズムの存在は知っていたのと、昔競プロでこれもう乱数で適当に決めたらいい感じに解けるんじゃないか？とか思ったこともあって発想は知っていたのですが、やはり改めて勉強してみるとなんか発想として面白いなというか、アルゴリズムに乱数を導入してスマートに解くっていう発想がすごいお気に入りでした。もうちょっと深く知りたい。
課金で自分を追い込むのは良い
この講座は一応無料でも受けられる？ようなのですが、自分はあくまでモチベ的にも証明が欲しかったのと、自分を律したかったので、課金しました。
まあ実際自分を律することはできたかなと思っています。ただ、仕事とかプライベートも忙しい時期だったので、正直しんどかったですが・・・
今後
実は他の資格試験の勉強をすることにしたため、続きの二個目の講義は一旦今はお休みしていて（ただプレッシャーのため課金は続けている）、そのうち再開したいなと思っています。ただ、二個目の講義からまた難易度がグッと上がっている感じがして、不穏な感じです・・・
とはいえ、やはり基礎的なことを勉強するのは私自身の趣味に合っているので好奇心が満たされて良いです。
自分のスタンスとしては、プログラマーの仕事に役立つかどうかは一切気にしない、これはあくまで趣味だという立て付けなのですが、とはいえいつか仕事にも役立ってくれると良いなあと思っています。
Discussion