アルゴリズマーのそだてかた
日本発の「Topcoderトレーニング講座」は最強最速アルゴリズマーへの最短経路
こんな記事も出して貰えたところですし、凄く簡単に、自分の中での教育論みたいな部分を少し話してみようかと思います。
ある物事を習得するのに必要なのは何か？という話をした時に、僕が絶対に必要だと思っているのは、「すげぇ！！」ってなることだと思っています。当然だとは思いますが、せっかくなので具体例を見ていきましょう。
Wikipediaにおける、動的計画法の記事を見ると、このようになっています。
動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP）は、コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法である。分割統治法がトップダウン的な手法であるのに対し、動的計画法はボトムアップ的な手法といえる。
「動的計画法(dynamic programming)」という言葉は1940年代にリチャード・E・ベルマンによって最初に使われた。 動的計画法の応用としては、最短経路の問題やナップサック問題、行列の積の計算に対する応用が挙げられる。多項式時間での解法が存在しないと思われる一部の問題に対して、この方法を適用することで、擬似多項式時間では最適解を得ることができる。ネットワーク、近似アルゴリズムの分野で研究されている。
さて、このブログの読者さんで、この説明を読んで、良く判った人はいるでしょうか？当時の僕は判りませんでした。確かに正確に書かれていますし、情報科学をきちんと学んでいる人にとっては、わかりやすい説明なのかもしれません。しかし、あまりがっちりとした数学に触れていないような人には、具体例で教えてほしいところでしょう。
ということで、用意されている例題がこちらです。
動的計画法の適用例を示す。
フィボナッチ数列
フィボナッチ数列とは第n項の値が第 n-1 項と第 n-2 項の和となる数列のことである。
動的計画法を利用したプログラム
int fib(n) {
int num1 = 1, num2 = 1, tmp = 1;
for(int i = 1; i < n; i++) {
tmp = num1 + num2;
num1 = num2;
num2 = tmp;
}
return tmp;
}
さて、このプログラムは、確かに動的計画法の例として、もっともシンプルなものです。一見、例として適切といえるかもしれません。Wikipediaに載せる例としては、極めて妥当なものではないかと思います。が、教育的な場面において、この例を使うのはどうでしょう？
このプログラムは、簡単に言ってしまえば、
さて、ここで皆さんに問いたいです。このプログラムを見て、「おー！すげえ！」ってなった人、一人でもいるでしょうか？僕は確信をもって、一人もいないであろうと断言します。フィボナッチ数列を考える際に、１個前の数字を覚える、以外の実装を考える人なんて、どこにいるんですか？当たり前のことを言われても、何にも嬉しくないじゃないですか。このプログラムを見て、じゃあこの知識を使って、別の問題も解ける！みたいな連想ができる人は殆どいないでしょう。
さて、ここで、宣伝になってしまいますが、僕の過去の連載をご覧ください。
アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5)
この内容は、僕が小学生の時に日能研で学び、凄く感心した記憶があるものなので、あえて採用しました。知ってる人も多いと思いますし、知らない人には新鮮な内容じゃないかと思います。表現しきれているか判りませんが、この記事で言いたかったのは結局のところ、「動的計画法っていうのは、そこまでの結果とかをまとめて覚えておいて、まとめて計算するもんだよ」ということだけです。もちろん、これで動的計画法の全ての意味を説明できているわけではありません。ですが、大体の使い方を覚えてもらえれば、最初の定義からちょっと外れてしまうものを追加で覚えてしまうことは、そう難しいことではありません。
この２つの例を見て、一番大きな違いはなんでしょう？僕は、「具体例のシンプルさの違い」だと思っています。例はシンプルなほうが良い、と考えるのは当然ですが、教育という場において、僕はそれを否定します。その解法を、頭の中で一般化出来ていなくても、最小のケースにおいては、経験的にそうした解法で解けてしまうことが多いからです。それでは驚きはありません。新しい知識を身に着けて、その一般化された考え方を使わないと解けない問題を見つけることで、初めて驚きが生まれるわけです。よって、ある程度のシンプルさを保ちつつ、ある程度の大きさを持った問題を扱うべきだと、僕は考えています。アルゴリズム教育の場において、それに最も適しているのが、TopCoderのようなコンテストの場でしょう。
納得できない人は、高校数学のlogを思い出してください。logってものを習って、「logすげえ！！！」ってなったこと、貴方にはありますか？おそらく多くのアルゴリズマーにはあるでしょうし、多くの一般の方にはないと思います。貴方はlog、得意ですか？きちんと扱える自信はありますか？凄いと思ったことがないものは、やっぱり良く判んない、という感覚が判ってもらえるんじゃないかなと思います。
さて、今回の講座においては、そうした「驚き」を大切にしつつ、可能な限り簡単な問題に触れていくことで、自分の能力が徐々に上がっていく楽しみ、というのを最大限感じてもらおうと思っています。簡単な講座となりますし、初回ですのでそこまでうまくいくかはわかりませんが、皆様のご参加をお待ちしています！
講座申込みはこちらから！ http://www.appliplanet.co.jp/training/topcoder/
