ネタ本を新たに発掘しました。『マイコンとパズルの世界　BASICプログラミング頭の体操』〔小谷 善行, 産報出版, 1981.〕。 プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 では本題、前回の続きです。 先の符号ビット表示のみを取り出し、そのまま並べてみます:符号ビット表示１１１１１１０　１１１１１１０１１１１１１１０　１１１１１１１１００　１００　１０１１０　１１１０１１０　１１１０１１１１０　１１１１１０１１１１０　１１１１１０１１１１１１１１１０　１１１１１１１１１１０１１１１１０　１１１１０１１１０　１１０１１１０　１１０１１１０　１１０１０　０１０　０１０　０ さらに、これを8ビットずつの並びにしてみます:2進表示１１１１　１１０１　　　１１１１　１０１１　　　１１１１　１０１１１１１１　１１００　　　１００１　０１１０　　　１１１０　１１０１１１０１　１１１０　　　１１１１　１０１１　　　１１０１　１１１１０１１１　１１１１　　　１１０１　１１１１　　　１１１１　１０１１１１１０　１１１１　　　０１１１　０１１０　　　１１１０　１１０１１１０１　１０１０　　　０１００　１００１(最後に1ビット、1を付け加えています。) 16進表示ＦＤ　ＦＢ　ＦＢＦＣ　９５　ＥＤＤＥ　ＦＢ　ＤＦ７Ｆ　ＤＦ　ＦＢＥＦ　７６　ＥＤＤＡ　４９ この場合、元の32バイトが、17バイトに収まっています。もっとも、これはデータの部分だけですが。 なお、今回は、圧縮の対象のデータを8bit固定長としましたが、可変長でも構わないことに注意してください。 さて、この16進表示だけでは、元に戻せないので、戻すための辞書も作りましょう。前回の投稿分の、「ここで、これらに次のようにbit単位の符号を割り当てたとします」にこのようなデータがありました:値　　回数　　ビット列００　２　　　１１１１１１００１　１　　　１１１１１１１０８０　１　　　１１１１１１１１００２　５　　　０４０　５　　　１００４　５　　　１１０２０　５　　　１１１００８　３　　　１１１１０１０　３　　　１１１１１０１Ｆ　１　　　１１１１１１１１１０Ｆ８　１　　　１１１１１１１１１１０ ここで「回数」は必要ないので削除します。ついでに「ビット列」と「値」も入れ替えてみましょう:ビット列　　　　　　　　値　　１１１１１１０　　　　　００１１１１１１１０　　　　０１　１１１１１１１１０　　　８０　０　　　　　　　　　　　０２１０　　　　　　　　　　４０１１０　　　　　　　　　０４１１１０　　　　　　　　２０１１１１０　　　　　　　０８１１１１１０　　　　　　１０１１１１１１１１１０　　１Ｆ　１１１１１１１１１１０　Ｆ８　 これを、ビット列の長さで並べ替えます:ビット列　　　　　　　　値　　０　　　　　　　　　　　０２１０　　　　　　　　　　４０１１０　　　　　　　　　０４１１１０　　　　　　　　２０１１１１０　　　　　　　０８１１１１１０　　　　　　１０１１１１１１０　　　　　００１１１１１１１０　　　　０１　１１１１１１１１０　　　８０　１１１１１１１１１０　　１Ｆ　１１１１１１１１１１０　Ｆ８　 続いて「値」もビット列に直しましょう:ビット列　　　　　　　　値　　　値のビット列　　０　　　　　　　　　　　０２　　００００　００１０１０　　　　　　　　　　４０　　０１００　００００１１０　　　　　　　　　０４　　００００　０１００１１１０　　　　　　　　２０　　００１０　００００１１１１０　　　　　　　０８　　００００　１０００１１１１１０　　　　　　１０　　０００１　００００１１１１１１０　　　　　００　　００００　００００１１１１１１１０　　　　０１　　００００　０００１１１１１１１１１０　　　８０　　１０００　００００１１１１１１１１１０　　１Ｆ　　０００１　１１１１１１１１１１１１１１０　Ｆ８　　１１１１　１０００ さて、次にこの「ビット列」と「値のビット列」をくっつけます。この場合、「可変長 + 8ビット」という形式に決まっており、かつ「可変長」つまり「ビット列」の部分は “０” で終っていることに注意しましょう:全体のビット列０　００００　００１０１０　０１００　００００１１０　００００　０１００１１１０　００１０　００００１１１１０　００００　１０００１１１１１０　０００１　００００１１１１１１０　　００００　００００１１１１１１１０　００００　０００１１１１１１１１１０　１０００　００００１１１１１１１１１０　０００１　１１１１１１１１１１１１１１０　１１１１　１０００ では、これを8ビットずつにくっつけたり分割したりします:全体のビット列 2進表示００００　０００１　　０１００　１０００　　０００１　１００００００１　００１１　　１０００　１０００　　００１１　１１０００００１　０００１　　１１１１　００００　　１０００　０１１１１１１０　００００　　００００　１１１１　　１１１０　０００００００１　１１１１　　１１１１　０１００　　００００　０１１１１１１１　１１００　　００１１　１１１１　　１１１１　１１１１１０１１　１１１０　　００１１　１１１１(最後に１を6こ付け加えました。) これにより辞書の部分は20バイトとなります。 では、これからもとの「辞書」を再現できるかやってみましょう。まず、1ビットめは「０」ですから、符号は「０」のみで、以下の8ビットは元の値です。その8ビットは「００００　００１０」とわかります。その次のビット列は「１０」で、それに続く8ビットは「０１００　００００」だとわかります。さらにその次のビット列は「１１０」で、それに続く8ビットは「００００　０１００」だとわかります。以下略。 このようにすると、先のデータに対して辞書を加えて、17バイト + 20バイト = 37バイトとなりました。前回の投稿の「最後に8ビットごとの “□” と “■” の並びをそのままバイトに置き換えるとします」の箇所では32バイトでしたので、嬉しい結果ではありませんが、もとのバイト数が少なかったからというところでしょう。辞書は必要ですが、ここではデータ本体が32バイトに対して17バイトになったことでよしとしましょう。 これらの例は、すこしばかり不自然な面もありますが、データ表現やデータ圧縮の入口のネタには使えるのではないかと思います。もうすこし工夫が必要ですが。文字、それもアルファベットのようなシンプルなものではなく、絵や漢字にすると、面白さとしては違ってくるかと思います。 興味を持たれましたら、ぜひご支援や、コメントを頂ければと思います。

プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 では本題です。 別の課題として、データ圧縮を取り上げることも可能かと思います。白黒のドットのまとまりを対象にすれば、ラン・レングスなどの簡単なデータ圧縮方法もあるかと思います。『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』では、微妙に変形したラン・レングスを題材にしていました。あるいは、『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』で同じく扱かっていますが、例文によっては文字や単語などの頻度からデータ圧縮を課題にすることも可能でしょう。 16 x 16ドットの簡単な画像を例にしてみましょう。まず、この例では、ビット表示の1ビットを送る、あるいは記録するのに1バイトを用いるものとします (ちょっと不自然ですが):ビット・マップ　　　　　　　　　　ビット表示(実際にはバイト)□□□□□□□□□□□□□□□□　００００００００００００００００□□□□□□□■■□□□□□□□　０００００００１１０００００００□□□□□□■□□■□□□□□□　００００００１００１００００００□□□□□□■□□■□□□□□□　００００００１００１００００００□□□□□■□□□□■□□□□□　０００００１００００１０００００□□□□□■□□□□■□□□□□　０００００１００００１０００００□□□□■□□□□□□■□□□□　００００１００００００１００００□□□□■□□□□□□■□□□□　００００１００００００１００００□□□■■■■■■■■■■□□□　０００１１１１１１１１１１０００□□□■□□□□□□□□■□□□　０００１００００００００１０００□□■□□□□□□□□□□■□□　００１００００００００００１００□□■□□□□□□□□□□■□□　００１００００００００００１００□□■□□□□□□□□□□■□□　００１００００００００００１００□■□□□□□□□□□□□□■□　０１００００００００００００１０□■□□□□□□□□□□□□■□　０１００００００００００００１０□■□□□□□□□□□□□□■□　０１００００００００００００１０ この方法だと、16 x 16 = 256バイトが必要になります。 このビット・マップは、“□” と “■” で構成されています。これに注目した方法はなにかないでしょうか。横方向に “□” が何個並んでいるかを数えるというような方法はどうでしょう。ラン・レングスと呼ばれるものの一種です。 ここで、変則的かもしれませんが1バイトを4ビットずつに分け、各4ビットの一番上位のビットが “0” であれば「□」であることを示し、 “1” であれば「■」であることを現わすものとします。「□」、「■」の並びの数は、残りの3ビットを使い、 “0” から “7” までを数えられるものとします。これで試してみましょう:ビット・マップ　　　　　　　　　　　4ビット-1バイト表示□□□□□□□□□□□□□□□□　０:７-０:７　０:２-０:０□□□□□□□■■□□□□□□□　０:７-１:２　０:７-０:０□□□□□□■□□■□□□□□□　０:６-１:１　０:２-１:１　０:６-０:０□□□□□□■□□■□□□□□□　０:６-１:１　０:２-１:１　０:６-０:０□□□□□■□□□□■□□□□□　０:５-１:１　０:４-１:１　０:５-０:０□□□□□■□□□□■□□□□□　０:５-１:１　０:４-１:１　０:５-０:０□□□□■□□□□□□■□□□□　０:４-１:１　０:６-１:１　０:４-０:０□□□□■□□□□□□■□□□□　０:４-１:１　０:６-１:１　０:４-０:０□□□■■■■■■■■■■□□□　０:３-１:７　１:３-０:３□□□■□□□□□□□□■□□□　０:３-１:１　０:７-０:１　１:１-０:３□□■□□□□□□□□□□■□□　０:２-１:１　０:７-０:３　１:１-０:２□□■□□□□□□□□□□■□□　０:２-１:１　０:７-０:３　１:１-０:２□□■□□□□□□□□□□■□□　０:２-１:１　０:７-０:３　１:１-０:２□■□□□□□□□□□□□□■□　０:１-１:１　０:７-０:５　１:１-０:１□■□□□□□□□□□□□□■□　０:１-１:１　０:７-０:５　１:１-０:１□■□□□□□□□□□□□□■□　０:１-１:１　０:７-０:５　１:１-０:１ この「4ビット-1バイト表示」のバイト数を数えてみると、45バイトになります。 最後に8ビットごとの “□” と “■” の並びをそのままバイトに置き換えるとします。“□” は0に、 “■” は1とします。ビット・マップ　　　　　　　　　　バイト表示□□□□□□□□□□□□□□□□　００　００□□□□□□□■■□□□□□□□　０１　８０□□□□□□■□□■□□□□□□　０２　４０□□□□□□■□□■□□□□□□　０２　４０□□□□□■□□□□■□□□□□　０４　２０□□□□□■□□□□■□□□□□　０４　２０□□□□■□□□□□□■□□□□　０８　１０□□□□■□□□□□□■□□□□　０８　１０□□□■■■■■■■■■■□□□　１Ｆ　Ｆ８□□□■□□□□□□□□■□□□　１０　０８□□■□□□□□□□□□□■□□　２０　０４□□■□□□□□□□□□□■□□　２０　０４□□■□□□□□□□□□□■□□　２０　０４□■□□□□□□□□□□□□■□　４０　０２□■□□□□□□□□□□□□■□　４０　０２□■□□□□□□□□□□□□■□　４０　０２ このサイズの、2値のビットマップは、右にあるように 2 x 16 = 32バイトを必ず必要とします。 ここまででも課題とてしては十分なのでしょうが、企画の課題とは別に、どうせなので技術としてのデータ圧縮も眺めてみましょう。題材は３つめのものを使います。３つめのもののバイトの出現頻度は次のようになります:値　　回数００　２０１　１　８０　１０２　５４０　５０４　５　２０　５０８　３１０　３１Ｆ　１Ｆ８　１ ここで、これらに頻度に応じて次のようにbit単位の符号を割り当てたとします:値　　回数　　ビット列００　２　　　１１１１１１００１　１　　　１１１１１１１０８０　１　　　１１１１１１１１００２　５　　　０４０　５　　　１００４　５　　　１１０２０　５　　　１１１００８　３　　　１１１１０１０　３　　　１１１１１０１Ｆ　１　　　１１１１１１１１１０Ｆ８　１　　　１１１１１１１１１１０ これを上の図のバイト列に当てはめていきます:バイト表示　　符号ビット表示００　００　　１１１１１１０　１１１１１１００１　８０　　１１１１１１１０　１１１１１１１１００２　４０　　０　１００２　４０　　０　１００４　２０　　１１０　１１１００４　２０　　１１０　１１１００８　１０　　１１１１０　１１１１１００８　１０　　１１１１０　１１１１１０１Ｆ　Ｆ８　　１１１１１１１１１０　１１１１１１１１１１０１０　０８　　１１１１１０　１１１１０２０　０４　　１１１０　１１０２０　０４　　１１１０　１１０２０　０４　　１１１０　１１０４０　０２　　１０　０４０　０２　　１０　０４０　０２　　１０　０ 長くなったので、続きは次回にいたします。 興味を持たれましたら、ぜひご支援や、コメントを頂ければと思います。  

プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 では本題です。 他の課題としては、データベースというものも考えられます。たとえば、「名前」と「電話番号」の並びからなるデータベースにおいて、目的とする「名前」と「電話番号」にどのように到達するか、またどうやって平均として速く到達できるかというような課題もあるかと思います。配列や木構造、ハッシュなど、先に挙げたものの延長線上の例題にはなるものの、見た目が違うという点では、候補の一つです。 迷路というのも、題材とてしては悪くないものではないと思います。木構造を使うにせよ、グラフを使うにせよ、探索が必要になるため、講習で扱うとしても後の方になるのではないかと思いますが。あるいは、探索はどっちにしろ必要になりますが、迷路をそのまま配列で表現するという方法もあるでしょう。 また、実質的に迷路とほぼ同じなのですが、地図の上の場所Aから場所Bに到達できるのかという課題もありえるでしょう。ただ、最小距離でという条件を付けると、難易度が上がりすぎるかもしれません。これをすこし面倒にしたものとして、地図の上の点を全て結ぶにはどうしたらいいかという課題もあるでしょう。 あるいは、ハノイの塔も同じく木構造と探索の例になるでしょう。 あるいは、児童・生徒には高度な課題になるかもしれませんが、オセロの対局ソフトというのも課題になるでしょう。オセロではなくチェッカー (あるいはドラフツ) の対局ソフトも、検討ないし視野に入って来ます。これらも木構造と探索が必要になる例題です。 オセロ、あるいはチェッカーと、迷路、そしてハノイの塔のどれを採用するかはわかりませんが、これらはどれであってもおそらく児童・生徒にとっては高度なものになると思います。対戦ではない分、オセロやチェッカーよりも、ハノイの塔や迷路の方が扱いやすいかなとは思いますが。なんにせよ、なにか別のものに落し込む必要があるかもしれないと思います。 オセロやチェッカーについては、改めて紹介したいと思います。 なお、「普通のパズルではない「正規表現クロスワード」がBBCラジオに登場」というようなものを除いて、クロスワード・パズルはコンピュータにとっては難易度が高いものの一例です。これの場合、辞書があればなんとかなりますが、一般のクロスワード・パズルは意味処理が必要になる場合が多いためです。その部分は、人工知能という言葉が一般によく使われるようになった今でもコンピュータにとって苦手な部分です。 これらは、単純に思いつく題材ですが、いずれも低学年児童向けに、どのような課題に落とし込むかという問題があるでしょう。興味を持たれましたら、ぜひご支援や、コメントを頂ければと思います。 次は2回に分けて、データ圧縮の話です。

繰り返しになりますが。プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 では本題です。 本文に紹介した『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』には、数当てゲームが課題として挙げてあります。具体的には、実際の形は違いますが、海戦ゲームの見た目というか、それに似た形を取っています。 『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』では、数を当てるのに、当てにくい方法と当てやすい方法を紹介し、採用しています。たとえば、数がソートして並べていられれば、当てる側がそれを知っていれば平均して当てやすくなります。これは、当てる際に木構造によって数の並びを想定しやすいからです。また、特定の数ではなくいくつかの数の集まりを当てるという例もあり、これはハッシュを用いた例題になっており、これも平均して当てやすくなります。どのようにハッシュを求めているのかがわかれば、一回で当てられます。これらはどちらも当てやすい方法です。 対して、数がランダムに並べられていれば、平均して当てにくなります。 これをそのまま使うのは憚られますが、課題としてはシンプルなものであり、配列、木構造、ハッシュを一纏めに扱えるという利点はあります。 というのも、この課題の一部にはソートされた並びが使われていますし、ハッシュも用いられています。これは、自分自身の数の並び (たとえばトランプのAからK) を、自分自身でソートしたりハッシュを求めて並べたりし、それを相手に宣言するという方法もありますし−−『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』ではその方法です−−、相手に自分自身の方法で並べさせ、その上で数を当てるという方法にも発展できるでしょう。 なお、ソートについて既に触れた記事としては「普通のバブルソートと普通ではないバブルソート」ではバブルソートが、「課題においてデータ構造やアルゴリズムを指定するか」では選択ソートが、「ガジェット・コンピューティング」ではスパゲッティ・アナログ・ガジェット (スパゲッティ・ソート)があります。 それはともかく、上のように言葉だけではわかりにくいかもしれないので、すこしばかり例を挙げましょう。 まず、ソートされている例です。とりあえず、トランプを使うとしての場合です。 “❺” が、児童Bが当たりと決めたカードとします。そして「小さい順にソートされている」とは宣言しますが、 “❺” を選んだことは隠されています。その上でこのようなやりとりがされるかもしれません:児童Bのカード０：　①②③④❺⑥⑦⑧⑨⑩⑪⑫⑬児童A: ７児童B: それより小さい１：　①②③④❺⑥　　　⑦⑧⑨⑩⑪⑫⑬児童A: ４児童B: それより大きい２：　①②③④　　❺⑥　　　⑦⑧⑨⑩⑪⑫⑬児童A: ５児童B: 当り!３：　①②③④　　❺　　⑥　　　⑦⑧⑨⑩⑪⑫⑬ この当り外れの部分のみを取り出して、データ構造として書いてみましょう:０：　①②③④❺⑥⑦⑧⑨⑩⑪⑫⑬　　　　　　↙　　　　　　↘１：　①②③④❺⑥　　⑦⑧⑨⑩⑪⑫⑬　　　　　↙　　↘　　　　　　 ↘２：　①②③④　　❺⑥　　⑧⑨⑩⑪⑫⑬　　　　　↓　　　↓　↘　　　　　↘３：　①②③④　　❺　　⑥　　　⑧⑨⑩⑪⑫⑬ 簡単な探索の例ですが、木構造になっていることがわかるかと思います。 児童・生徒のやりとりとして：児童A: ７児童B: それより小さい児童A: ４児童B: それより大きい児童A: ５児童B: 当り! というやりとりだけを見ると、このような木構造での探索をしているということは意識しにくいかもしれません。ですので、ここで書いたような図を児童・生徒に一回のやりとりごとに書いてもらうという方法になると思います。 また、児童Aと児童Bが交互に数字を言うことで、ゲーム性もとりあえず維持できるかもしれません。さらには、どのような並べ方をしたかを宣言する必要はあるでしょうが、ソートした場合とランダムに並べた場合、あるいはハッシュにして並べた場合なども選択できることで、当てられにくい並べ方をするというような戦術的な(?)部分も組み入れられるかと思います。このあたりは、何回かゲームを繰り返すことで、発見的・体験的に学ぶ方向に持って行きたいと考えています。 ただ、ハッシュの場合の扱いに、難点があるとは言えるでしょう。『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』でも同じですが、ハッシュだと他の場合とすこしルールが違っていたりします。例えばですが:１と倍数でないもの：　１，　７，　１１，　１３２と２の倍数：　２３と３の倍数：　３，　６，　９４と４の倍数：　４，　８，　１２５と５の倍数：　５，　１０ このようにあったとします(「Xの倍数」は、Xが大きい方に入れています。その他、あくまで例なので、細かいところは無視してください)。『コンピュータ使わない情報教育　アンプラグドコンピュータサイエンス』の場合、ハッシュ値に対応する数については、どのようにハッシュを求めるかは決まっており、その戦艦(?)に対応する数字を宣言します。その上で、ハッシュ値を当てればいいという形になっています。この方法だと、一回で当たります。 この例の場合だと、「この方法を取っている」と宣言し、かつ「６」と宣言します。すると相手は「３と３の倍数」と宣言すればいいというわけです。 これを「海戦ゲーム」風の解釈をするなら(海戦ゲームにこのようなルールはあったか不明ですが)、ハッシュ値に対応した数の集りは、いわば密集した艦隊を形成していて、その艦隊を当てればいいという解釈だとも言えるかもしれません。ですが、正直、多少思うことがないわけでもありません。このあたりをうまく扱かえる方法があればいいのですが。 いずれにせよ、このような題材のままというわけではないとしても、題材や、それをどう落とし込むかを検討したいと考えています。興味を持たれましたら、ぜひご支援や、コメントを頂ければと思います。

教材、資料に、ご支援いただいた皆さんのお名前を記載するというのを、思いつきました。 これをリターンに加えると、現在承認されているリターンの内容の変更となり、再度申請を行なう必要が出てくるような気がします。 悩ましいところではありますが、そういうことを思いついたということだけを。