■

ここからようやく今日のエントリーか…。学術関係の話題でも出しますかね。

入学して最初の２年を教養学部で学んだ後各学部に振り分けられるという方式のうちの大学では、教養学部のうちに多くの選択授業をとることができる。この制度は歴史を振り返ると「未だにここだけがやってる」んだけど、あまり早いうちから専門分野を教えるより絶対こっちのほうがいいと思う。分野の細分化が激しくなっている時代だからこそマクロな視点での勉強がいるという考え方である。小宮山総長バンザイ。
まあそんなことはどうでもよく、俺が取ってる授業のひとつでアルゴリズムの基礎を学んで、その内容がなかなか感動的だったのでブログに記録している次第だ。
扱った問題はmss（最大部分列和）問題と呼ばれるもので、ある数列が与えられ、それから生成されるすべての部分列の中でその要素の総和が最大になるときの値を求める単純なもの。例えば[-6,3,2,-4,5,-2]からだったら[3,2,-4,5]から6が正答。これのアルゴリズムを組んで計算させるわけだが、最も自明で原始的なアルゴリズム（生成されうる全ての部分列を求め、それぞれの部分列の要素の総和を求め、それぞれの総和で最も大きなものを選ぶ）から自分でプログラムを書いてみて、授業で示された「良い」アルゴリズムから組まれたプログラムと計算速度を比較してみると、前者が1100秒かかったのに対し後者は6秒で計算終了した（問題として与えられた数列の要素数は30、ループ回数は30000000回）。
感心したのは、「良い」アルゴリズムを求める過程に直感が入り込んでいないことだ。「自明で原始的な」アルゴリズムにいくつかの定理を当てはめていくことで、最初と同じ働きをすることが保証された、しかも極めて計算時間の短い、「良い」アルゴリズムが求まってしまうのである。