スキップしてメイン コンテンツに移動

投稿

6月, 2010の投稿を表示しています

小学3年生の授業参観でアルゴリズムに出会った

小学3年生の娘の日曜授業参観に行ってきた。算数の授業だ。授業の後半、以下のような問題が出された。 問題 : ゴマダラチョウとトノサマバッタがあるゲームをしている。0から9までの数字の書かれたカードがそれぞれ一枚ずつ全部で10枚あって、それを使って3桁の数を2つ作り、その差をできるだけ小さくした方が勝ちとなるゲームだ。ただし百の位は0にできない。できるだけ小さくするにはどのようにカードを選べばよいだろうか。 これを約30人の生徒に考えさせていた。解き方を先に教えるということはしない。生徒が問題を考えている間、先生は生徒たちを見回り、質問などに答える。しばらくするといろいろと答えが挙がってきた。自分の娘は以下のように考えたようだ。 百の位は差が1であればどの数字でも良いので、まず十の位を最小にする数字を考えてみると、最小の数字0から最大の数字9を引いた場合が最も小さくなる。同様に一の位では0と9以外の最小・最大の数字を選ぶ。つまり1から8を引いた場合が最小になる。百の位は残りの数字カードから差が1となるものを選ぶ。解答例は「501-498」や「701-698」となり、差は3になる。 これはまさにアルゴリズムだ。Pythonであれば以下のコードと同じだろう。 digits = range(10) ten = (digits.pop(), digits.pop(0)) one = (digits.pop(), digits.pop(0)) idx = random.randrange(len(digits) - 1) hund = (digits.pop(idx), digits.pop(idx)) a = reduce(lambda x, y: x * 10 + y, map(array, (hund, ten, one))) print "%d - %d = %d" % (a[1], a[0], a[1] - a[0]) 出力例: 601 - 598 = 3 小学3年生の算数だと思ってそれほど期待せずに観に行ったのだが、生徒たちはみな楽しそうに問題に取り組んでいたし、なかなか面白い授業をしているようで何だか安心した。因みに、今回のようなクラス全員で考える問題は普段からよく行っているとのことだった。

スーパーコンピュータとプログラミング言語

世の中には星の数ほどのプログラミング言語があるかもしれないが、スーパーコンピュータで利用するとなるとかなり限られてくる。ライフサイエンス分野のデータの処理にはPython、Ruby、Perlなどのいわゆるスクリプト言語はよく使われるし、データベース関連だとJavaなどもあるだろう。しかし科学技術計算に限れば、FortranやC/C++が多数を占めると思う。やはり実行効率と既存資産の存在は大きい。 数値計算プログラムでは、とにかく速さが求められる。どれだけの速さがあれば十分かだって? この質問はナンセンスだと思う。たとえ現在の最高速度を誇るスーパーコンピュータの1億倍の速度があったとしても十分ではない。使える資源でできる範囲の計算をするだけなのだから。 自分の携わる分野では一回の計算に半年かかることもざらなので、計算速度は死活問題だ。1分で終わる処理なら倍に高速化したとしても差は30秒でしかない。しかし、半年となるとその差は3ヶ月にもなる。だから、Fortranを使うにしても、よりモダンなFortran90/95だけではなく、 古めかしいが実行速度の速いFORTRAN77 もよく使われる。まあ、最近は速度差も縮まってきているのでそこまでFORTRAN77にこだわらなくなってきているけど。本当にクリティカルな部分にはアセンブリ言語なども使われている。 また、汎用コンピュータのコンパイラに比べてスーパーコンピュータに最適化されたコンパイラではバグの入っていることが多く、C++でもBoostなどの外部ライブラリは避けた方が無難だ。使うにしても GoogleのC++コーディング規約 のように一部に限定して使う方が良い。実際にBoost絡みのコンパイラバグによる混乱を見るに、STLなどの標準ライブラリのみをシンプルに利用していた方がまだ安全だ(それでもバグるけど)。そうは言ってもBoostは便利なのでできるだけ早くC++0xの標準化がされてほしい。標準化されていればコンパイラベンダも言い訳できないしね。 そういえば Fortress なんて言語もあるね。面白い試みではあるけれど現状で利用するのは難しいような気がするなぁ。特に冒頭でも述べた、Fortranと同程度の実行効率が出せるかという点と既存資産の代替が存在するのかという点で。因みにFortressでの&qu