アルゴリズムの復習
ちょっとしたことから、アルゴリズムの復習をしようと思い立ち、O’Reillyから出ている『入門データ構造とアルゴリズム』を読み始めました。しかし、この本はしょっぱなから誤植やミスが目立つため、豊富なドリルは役に立ちそうですが、心もとない雰囲気があります。
それでも我慢して冒頭を読み進めていたのですが、突然 分割統治法のマスター定理 なるものが出てきて、特に式の説明もなく、こんなもの覚えられるか！とさじを投げました。
尚、マスター定理というのは、再帰処理によって問題を解くアルゴリズム(たとえばマージソート)の計算量を(場合によって)求めることができる定理で、計算が容易です。
日本語で検索をしてもなかなか解説している資料に出会わないのですが、英Wikipediaに簡単な説明があります。
Master theorem - Wikipedia, the free encyclopedia
この説明を読むと、CLRS本として知られるMITプレス発行の『Introduction to Algorithms』によって知られるようになった定理だと書いてあります。
この本自体は以前手に入れたまま放置していたのですが、せっかくなので該当箇所を読んでみることにしました。が、該当箇所を読むだけではいまいち理解できません。
もしかして、ここは本当に覚えるべきところなのか。
気になってきたので、この本を教科書として採用しているMITの講義録を視聴してみることにしました。
MITの講義を視聴する
2005年に行われた講義がオンライン学習用に公開されています。
第1回の講義では、概要説明がしばらく続いたあとで、アルゴリズムとは何かという説明があって、その後挿入ソートとマージソートを具体例として計算量の概念を紹介しています。プログラマならこのあたりは余裕ですね。
(余談ですが、演習課題はまず自力で考え、30分以上悩んでも解答がわからなければ、時間の無駄だから友達に聞こうっていうアドバイスが、さすが合理的だなと思いました。あとは、何をしたら単位がもらえないとか、そういう話をきちんとするのも良いですね。)
マスター定理は第2回の講義で扱われています。この先生は天才肌っぽい感じがします(1981年生まれで教授!)が、本人も言及している通りハイスピードで説明が進みます。でも、ついてこれなかったらすぐ聞いてね！ペース落とすから！っていうのが優しい配慮ですね。
この2回の講義を通しで聴いて、ようやくマスター定理の言わんとするところが見えてきました。これは暗記するような性質のものではなく、意味を理解することが大切でした。
資料も充実
授業の英語についていけなくても、きちんとレジュメが配信されています。下の資料は第2回の分ですが、ずいぶんきちんと書かれていて、復習用(フォローアップ)に最適です。
Asymptotic Notation and Recurrences - lec2.pdf
自分が通っていた大学もノートは取らなくて済むようにレジュメが配られることが多かったですが、こんなにわかりやすくなかったですね。。これだけ用意してもらえるなら、授業は先生の一挙手一投足に集中することができますね。
MITは厳しい
これだけ見ると、さすが世界屈指の大学だけあって充実してるなという印象です。が、その分求められるものも結構シビアです。この講義は1週間に2回ずつ、各1.5時間で行われ、だいたい1週間に1回、以下のような宿題が課せられます。
この中でProblemというのが提出課題でExerciseは自主課題ですが、Problemを提出しないと、期末成績がどんどん減点されていきます。課題自体も結構多いのに、問題自体もなかなか味のある内容です。
Exercice 1-3. はその前の課題に証明が書いてあるのに気づかず、個人的にかなり苦戦しました。。
ふと、第1回の講義でlogが絡んだ総和の計算が出てきて、数学はPrerequisitesだからね！と先生が冗談めかして言っているのを思い出しました。確かにシラバスにもはっきり書いてあります。要求がはっきりしているのも、アメリカらしいと感じます。
まとめ
ふとアルゴリズムの復習をしようと思い立った結果、気がついたらMITの講義を2回聞き、課題を解いていました。
世間ではCLRS本を輪読したり、独学している方もいるようですが、もしかすると講義録に沿って学習を進めていくことで、割合短期間に終わらせることができるかもしれません。
個人的には冒頭に言及していたO’Reillyのアルゴリズムの本がコンパクトなので、あくまでそちらをメインに据えたいなと考えていますが、もしかしたらMIT講義録に移行するかもしれません。
飽きっぽくなかなか大きなことは続かない性格ですが、2016年は継続力も磨ければなぁと思います。