月曜日にアルゴリズムイントロダクション輪講の第1回を開催しました。http://tokyoenvious.xrea.jp/ria-kyoto/ria-01.pdf が輪講スライドです。輪講中でホワイトボードを使って説明したところもあり (Θ記法のところとか)、資料としては不親切なところもあるかもしれません。
第1巻の最初は基礎部分で、なるべく早めにアルゴリズムそのものに触れたいというのもあり初回だけ一度に 3章分やったのですが、なかなか大変でした。FOR ループの正しさを検証するためのループ不変条件や、アルゴリズムの漸近的効率を記すための漸近記号のところの理解 (特に o や ω) がなかなか難しいようです。
個人的には、漸近記号については p.48 の
- O 〜 ≦
- Ω 〜 ≧
- Θ 〜 =
- o 〜
- ω 〜 >
という対応がしっくりきましたが、なかなか上手く説明できませんでした。終わった後も id:antipop といろいろ話していましたが、o を使うのは「アルゴリズムの実行時間の増え方はこの関数以上に悪くはならないけど、この関数ほどにも悪くはならないよ」という時かなーと思いました (O は同じくらい悪い場合も含む)。なかなか直感的な説明は難しいです。
次回は4章の漸化式です。最初から結構難しいところが続きそうなのですが、ここを乗り越えれば一番楽しいところであろうアルゴリズムなので、ふんばりどころです。
メンバーも適宜追加募集をかけたいと思っています。その時はまた告知しますので、よろしくお願いします。
