まるはば通信　〜京都ノートルダム女子大学 　国際日本文化学科　（旧・人間文化学科）～

こんにちは、「情報科学概論A」を担当している中村です。

第10回目の講義まではコンピュータ内部の数値、データ表現、圧縮や誤り検出・訂正と
コンピュータのデータ表現に重点を置いた内容を取り扱っていたのですが、
6月26日の講義からはコンピュータがどのように動いてるか（アルゴリズム）にシフト。

今回は「コンピュータでの問題解決 - データの探索アルゴリズム」と
コンピュータがどのようにデータを探索しているかについてを、
コンピュータサイエンス アンプラグド（以下、CSアンプラグド）で体験してもらいました。

CSアンプラグドというのはコンピュータを使わずに情報科学を教えるための学習法で、
カードなどを用いたゲームやグループ活動を通して、
コンピュータの基本的なしくみを楽しく学ぶことができるものとなっています。

・コンピュータサイエンス アンプラグド（日本語版）
　－ http://csunplugged.jp/


今日の講義では探索アルゴリズムに対応するCSアンプラグド「戦艦」を使いました。
（ http://csunplugged.jp/index.php?戦艦 ）

この教材では2人組になりそれぞれ別のシートを配布します。

それぞれのシートには26隻の戦艦と戦艦の中には数字が書かれており、
その中から好きな数字を1つ選んでもらいます。

そして相手の選んだ数字が「A～Zの戦艦」のどれに書かれているのかを予想し、
攻撃する方は「〇〇（アルファベット）の戦艦に攻撃！」と言い
攻撃された方は攻撃された戦艦の数字と当たりかハズレを相手に教えます。
それを交互に繰り返し少ない回数で当てた方が勝ちとなるゲーム仕立てになっています。
CSアンプラグドでは「線形探索」「二分探索」「ハッシュ法」の探索アルゴリズムを学べます。



●線形探索
データの先頭から順番に調べて行く手法。
データを並べ替えておくなどの準備は必要がないが、
最悪のケースの場合（調べるデータ含まれていない or 最後にある）だと
データ全てを探索することになるなど比較回数が多くなる。

例）データ1万個の場合
最短の場合：比較回数 1回
最悪の場合：比較回数 10,000回

●二分探索
データをあらかじめ昇順や降順で並べ替えておく必要があるが、
目的のデータを比較的高速に検索することができる。

例）データ1万個の場合
最短の場合：比較回数 1回
最悪の場合：比較回数 14回

●ハッシュ法


データを格納場所に対応する値を割り当てて、その値をキーにしてデータを探索する。
同じキーにデータ割り当ての数が多くなると効率が落ちる。


言葉だけだと難しく感じると思うのですがCSアンプラグド（日本語版）のWebサイトに
ワークシートや実習のやり方が公開されていますので一度試してもらうのがいいかと思います。
（ http://csunplugged.jp/index.php?戦艦 ）

■講義中の風景


机の間を少し離してもらい相手のシートを見えないように。



シートの前に筆箱などを立てておき見えないようにガードして真剣勝負！


今回の講義を受講した学生のフィードバックシートには「楽しみながら学べた」というような肯定的な感想ばかりでした。
探索アルゴリズムが普段どのような場所に使われているのかを疑問にもってもらえたり、
「このアルゴリズムはここに使っている？」と鋭い視点を書いている学生もいました。

・コンピュータの動きがどのように行われているかを楽しみながら理解することができました。また、辞書が使いやすい理由についても知ることができました。
・２人１組でゲーム形式でパソコンの問題解決をする方法を学べておもしろかったです。
・二分探索、ハッシュ法は普段ではどんなものに使われているのか疑問を持ちました。
・ハッシュ法はSNSでもタグ付けが流行っていて、すぐに検索したものにアクセスできるので便利だと思います。

次回、7/3の講義は「コンピュータでの問題解決 - データの整列アルゴリズム」と
探索アルゴリズムと並んで重要なテーマを扱う予定をしております。

報告：中村亮太