2014/09/09

初心者向け「アルゴリズム」の教え方

1号(♂14才)が参加しているロボット教室で、思いつきで「アルゴリズム」について教えてみよう、と思った。
アルゴリズムを工夫することによって、
  • 計算の精度を高める (有効数字など)
  • 計算量を削減できる (計算時間の短縮)
を知ってもらえればいいと思った。
対象は小3〜中3である。
こんなかんじで始めた。
アルゴリズムとはコンピューティングにおける計算の順序のことで、これを工夫することによっていろいろなメリットがあります。

「計算の精度を高める」の説明
計算の精度を高める例として、次の算数を解いてもらう。
1 ÷ 3 × 3 = ?

算数で解くと、答えは「1」。
しかし、安い電卓を各自に回して解いてもらうと答えは「1」にはならず、「0.999...」となる。はてな?
これは、電卓が最初の「1 ÷ 3」の結果を2進数で表せず、「0.333...」の結果のみを保持してしまい、続く 「× 3」で「0.999...」となってしまうためである。
では、計算の順番を入れ替えるとどうなるか?
1 × 3 ÷ 3 = ?

この場合は、算数上も電卓上でも「1」である。ひゃっほー!
この説明での注意点は(安い)電卓を使うことである。
PCや、スマホのような高級なOSを持つ計算機や関数電卓では、そのあたりは配慮されていて、ちゃんと答えが「1」となるように仕組まれている。
この例題で、計算の順序によって「計算の精度」に影響が出ることを知ってもらうことができた。


さて、次に「計算量の削減」だが、ネットでネタ探しをすると、ソート(並べ替え)の話がメインなので、「バブルソート」や「バケツソート」「クイックソート」の実例を出してみても、いまいち食いつきが悪い。
というか、勝手講師の私が2度も「クイックソート」の説明でつまづいたので、とても下手な説明になってしまったのも失敗の要因として大きい(個人的にはショックが大きい…)
もっとも、講師の下手さを差し引いても、まだ、小中学生の実生活でソーティングのお世話になるようなこともないので、興味を引かなかったようでもある。

「計算量を削減する」の説明
そこで、ソートではなく「絞り込みの順番」で考えてみるとした(バケツソートになっているけど)。
次の例題を考えた。
(目的) 男女同数24人づつ合計48人のクラスの中で、9月生まれの女子の人数を知りたい。
(前提条件) 質問は1人づつ1回に1種類しかできない。質問の結果によって次の質問の対象者を減らすことが出来る(絞込)。また、回答の際の声色で男女の区別は出来ないものとする(現実ではできちゃうので)。
(導きたい結果) 9月生まれは4人おり、そのうち女子は2人である。
必然的に以下の2種類の質問をすることになる。
A. あなたの性別は何ですか? (男子ですか? 女子ですか?)
B. あなたは何月生まれですか?
この「質問の順序次第で質問の回数が大幅に変わること」を知ってもらうことが狙いである。

(A先B後の場合)
Aを最初に質問し、Bを続いて質問する場合は次の質問回数が期待値となる。
  1. あなたの性別は何ですか?  → 48回の質問
  2. 女子24人に絞られる
  3. (女子24人に対し) あなたは何月生まれですか? → 24回の質問
  4. 女子で9月生まれの2人に絞り込まれた!
この場合、48回+24回=72回の質問が必要になる。

(B先A後の場合)
Bを先に質問し、Aを後にした場合は次のとおりとなる。
  1. あなたは何月生まれですか?  → 48回の質問
  2. 9月生まれ4人に絞られる
  3. (9月生まれ4人に対し) あなたの性別は何ですか?  → 4回の質問
  4. 女子で9月生まれの2人に絞り込まれた!
この場合、48回+4回=52回の質問で済む。

質問の順序を工夫することで(=アルゴリズムを工夫することで)、20回も削減できた(28%OFF)。
最初の48回の質問回数は必須とすると、2番目の質問では24回から4回に減ったので、部分的に83%OFFと考えることもできる。ひゃっほー!
もっとも、期待値が推定出来る場合でないと有効ではないので、その点は注意が必要ではある。


次回のロボット教室でのチャンスに「計算量…」の説明で、子どもたちの合点が行くかどうか試してみる所存である。
その流れで、ロボット教室なのでセンサーの効率的なチェックの仕方や、合理的なif文の構造にまで踏み込めればいいかなと思う。

====

画像はiPhone5で撮影。
雨上がり、水たまりのアスファルトに溶け込んでいる朝の空。
そいういえば、今日、iPhone6が発表だな。NFC搭載だと嬉しいかも(買い換えないけど)。

0 件のコメント:

コメントを投稿

zenback