繰り返しになりますが。プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 本日、書庫より『別冊サイエンス　コンピューターレクリエーションIII　遊びの発見』、『プログラミング・セミナー』、『スマリヤンのXXの論理パズル』、その他を発掘しました。 『ソフトウェア千夜一夜物語』、『続ソフトウェア千夜一夜物語』は、未発掘です。 この記事は、medium.comのstoryを元にしています。 では本題です。 アルゴリズムということが、おそらく誰もの頭にあると思うので、その流れでは「その計算方法は自然なものに思えるか？」というようなことをいうかのようなタイトルに見えるかもしれない。 だが、そうではない。たとえば、物理の法則は自然をモデル化している。このタイトルの「自然」とは、そういう意味での自然だ。 「なにを馬鹿なことを」と思われるかもしれない。プログラムはまだ人間が書くものだし、計算の手順を決めるのも人間だ。ならば、書かれたコードは、自然そのものということはないだろう。ここで書いてみたいのは、計算という概念は自然なのかということだ。 実際のコードから離れて、アルゴリズムで考えてみよう。あるアルゴリズムが存在するとする。では問題だ。**そのアルゴリズムは、誰かが思いつく以前から存在していたのだろうか？** 計算は自然だという立場なら、“yes” と答えるだろうし、そのアルゴリズムは発見されたと言うだろう。自然ではないとするなら、“no”と答え、発明されたと言うだろう。 これは、実は単純な話ではない。アラン・チューリングが、おおざっぱに言うなら、「計算できるものは計算できる」と、数学的に証明してしまっているからだ。つまり、計算という概念は数学の一部なのだ。 ここで話がややこしくなる。数学は自然なのかという疑問も関係してくるからだ。 数学は、物理の法則を記述できるし、さらには未発見の事柄の予想の根拠にもなる。なぜ数学にそんなことができるのかは、わかっていない大きな疑問だ。 この手のことについては、数学とは人間がそのように決めたものという考えがされることもある。もちろん、数学のいろいろな分野における公理は、人間が定めたものだ。公理を最小化しようという研究もあり、それはほとんど理解を超える話になってしまう。だが、問題は、なぜ公理を設定することが可能で、しかもどういう公理からの数学であっても、対応する自然があるのかだ。 話が大仰なものになった。だが、アルゴリズム、そして具体的なコードも、児童・生徒から「なぜ動くの？」と聞かれたら、先生は「そうなるように書いたから」という答えで済ませては欲しくない。現実的には、そう答えざるをえないかとも思うが、その背後には、そう簡単ではない疑問が存在することは意識して欲しいと思う。

繰り返しになりますが。プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 この記事は、medium.comからの転載です。 先にこれを書きました:sedで足し算(超簡略版) そちらもですが、この記事も、パズルのようなものです。 では、本題に入ります。 足し算ができるなら、掛け算くらいなら手軽にできるだろうと思いますね? はいできます。 先と同じく1〜9の1桁の任意の数の掛け算です。先の記事ではいくつの数の足し算でもかまいませんでしたが、今回は2つの数の掛け算に限定します。 コードはこちら。名前は “multi.sed” とします:ps/1/I/gs/2/II/gs/3/III/gs/4/IIII/gs/5/IIIII/gs/6/IIIIII/gs/7/IIIIIII/gs/8/IIIIIIII/gs/9/IIIIIIIII/gs/ *\* */ /gs/ *$//p:loop1/I+ i*I+/ { s/(I+) (i*)I/\1 \2i/ # A bloop1}:loop2/I+ I*i+/ { s/(I+) (I*)i/\1 \2\1/ # B# p bloop2}s/^I+ +// データはこれとします。名前は “multi.dat” とします:2 * 33 * 3 “multi.sed” に “multi.dat” を食わせると、こうなります:$ sed -r -f multi.sed multi.dat2 * 3II IIIIIIIII # ここが結果3 * 3III IIIIIIIIIIII # ここが結果 ここで、「# ここが結果」は表示されません。ですが、計算はできています。 コードの肝はloop1の “# A” と:s/(I+) (i*)I/\1 \2i/ # A loop2の “# B” です:s/(I+) (I*)i/\1 \2\1/ # B Aの方は、 “I” だらけだとわけがわからなくなるので、2つめの数を “i” に置き換えています。虚数を意味してるとかではありません。 “I” と区別できればいいだけなので、なんでもかまいません。 Bの方は、その “i” を一個ずつ、1つめの数の “I” の並びで置き換えています。この過程を確認したい場合は、 “multi.sed” のloop2のとこのここ:# p この “#” を消してみてください。

この記事は、medium.com からの転載です。 何回か、計算という概念にかかわる話題を書こうかと思います。 sedで計算するというと、どういうことかとも思うかもしれません。sedの処理自体が計算なのですから。 そこで、足し算を例に挙げて見ます。きっちり計算することもできますが、ここではわかりやすさのために超手抜き版として、1~9の任意の1桁の数字の足し算とします。 では、1つめです。コードのファイル名は “plus1.sed” とします:s/1/I/gs/2/II/gs/3/III/gs/4/IIII/gs/5/IIIII/gs/6/IIIIII/gs/7/IIIIIII/gs/8/IIIIIIII/gs/9/IIIIIIIII/gs/ *\+ *//g これに、このようなデータを与えます。ファイル名は “plus.dat” とします:1 + 43 + 39 + 91 + 2 + 37 + 8 + 9 では、実行してみましょう:$ sed -r -f plus1.sed plus.datIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII 1〜9を対応する数の “I” に置き換えて、 “+” あたりを消しているだけです。それでも、 “1 + 4” の結果が “5” に、 “3 + 3” の結果が “6” に、 “9 + 9” の結果が “18” に、 “1 + 2 + 3” の結果が “6” に、 “7 + 8 + 9” の結果が “24” になっています。 これではわかりにくい? では “plus2.sed” のコードを使ってみましょう:s/1/I/gs/2/II/gs/3/III/gs/4/IIII/gs/5/IIIII/gs/6/IIIIII/gs/7/IIIIIII/gs/8/IIIIIIII/gs/9/IIIIIIIII/gs/ *\+ *//gs/IIIIIIIIII/X/gs/IIIII/V/g これを実行するとこうなります:$ sed -r -f plus2.sed plus.datVVIXVIIIVIXXIIII まじめに計算するためには、 “a + b” とあった場合、 “a + 1” の計算と、 “b — 1” の計算をし、bの方が0になったら計算を終えるようにする必要があります。それだと、たとえば “3 + 4” の場合、“3 + 1” を行ない、 “4–1” の計算もしてやり、ループすることで結果を得られます。また、その方法を取った場合、1~9の数字のままで処理をしたり、2桁以上の数同士の足し算もそのままできるなどの利点もあります。 ですが、そのままコードも面倒になります。ですので、ここではこの例に留めます。 こっちの方が簡単であるということとともに、この例の場合で都合がいいのが、「こんなものが計算と呼べるのか」という疑問を喚起するかもしれないという点です。ですが、 “plus1.sed” の場合でも、きちんと結果は出ています。それでもこういう声も聞こえてきそうです:「結果を人間が数えなきゃならないじゃないか」 そういう文句はアラン・チューリングに言ってください。チューリング・マシンの結果というのも、こんな感じだったりします。 ですが、そういう疑問も持ってもらうのはいいことかなと思います。小中高でプログラミング教育に関わっている方にとっては特に。もしかしたらこれを計算と認めるのには抵抗があるかもしれません。ですが、きちんと計算をしています。計算というのは、おそらく普通に思われているだろうものよりも、範囲が広いものです。 なお、sedでの高機能なスクリプトはあちこちで公開されていますので、興味があれば検索して、確認してみてください。 まぁ、上の例ではあんまりだということであれば、こういうのはどうでしょうか。 1桁の数の足し算に限定するという条件は変わりませんが、 “a + b” に対して “a + 1” と “b - 1” をするという方向を見てみましょう。その変化が見えるようにしているコードの例を “plus3.sed” とします。それがこちら:ps/1/I/gs/2/II/gs/3/III/gs/4/IIII/gs/5/IIIII/gs/6/IIIIII/gs/7/IIIIIII/gs/8/IIIIIIII/gs/9/IIIIIIIII/gs/\+/ /gp:loop/^I+ +I+/ { s/I +I/II / p bloop}s/^(.)/=\1/ これを “plus.dat” にあてると、こうなります:$ sed -r -f plus3.sed plus.dat1 + 4I IIIIII IIIIII IIIIII IIIIII =IIIII 3 + 3III IIIIIII IIIIIII IIIIIII =IIIIII 9 + 9IIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII =IIIIIIIIIIIIIIIIII 1 + 2 + 3I II IIIII I IIIIII IIIIIII IIIIIII IIIIIII =IIIIII 7 + 8 + 9IIIIIII IIIIIIII IIIIIIIIIIIIIIIII IIIIIII IIIIIIIIIIIIIIIIII IIIIII IIIIIIIIIIIIIIIIIII IIIII IIIIIIIIIIIIIIIIIIII IIII IIIIIIIIIIIIIIIIIIIII III IIIIIIIIIIIIIIIIIIIIII II IIIIIIIIIIIIIIIIIIIIIII I IIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII =IIIIIIIIIIIIIIIIIIIIIIII “plus.dat” の各行を表示し、また結果には “=” をつけて表示しています。 “1 + 4” を例に見てみましょう。最初は:I IIII こうなっています。それが出力の次の行ではこうなっています:II III “I” が “II” になり、 “IIII” が “III” になっています。以下、これのループで、 “a + b” の “b” の位置に “I” が一つもなくなると:/^I+ +I+/ この、スペースの左側に “I” が1個以上ならんでおり、かつスペースの右にも “I” が1個以上並んでいるという条件が成立しなくなり、一行の処理が終わります。肝と言えるのは、この部分です:s/I +I/II / スペースの左側の “I” を “II” に書き換え、またスペースの右側の “I” を一個消しています。ここで注目しているのはスペースのすぐ左側の “I” 1個だけであり、またスペースのすぐ右側の “I” 1個だけです。ですが両方とも1個以上並んでいる条件ですから、その条件のもと、スペースの右側の “I” 1個を、スペースの左側の “I” の並びに移動したと読めます。あるいは読みます。 読みやすさのために、 “plus4.sed” も挙げておきましょう:ps/1/I/gs/2/II/gs/3/III/gs/4/IIII/gs/5/IIIII/gs/6/IIIIII/gs/7/IIIIIII/gs/8/IIIIIIII/gs/9/IIIIIIIII/gs/\+/ /gp:loop/^I+ +I+/ { s/I +I/II / p bloop}s/IIIIIIIIII/X/gs/IIIII/V/gs/^(.)/=\1/ これを “plus.dat” にあてると、こうなります:$ sed -r -f plus4.sed plus.dat1 + 4I IIIIII IIIIII IIIIII IIIIII =V 3 + 3III IIIIIII IIIIIII IIIIIII =VI 9 + 9IIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIII =XVIII 1 + 2 + 3I II IIIII I IIIIII IIIIIII IIIIIII IIIIIII =VI 7 + 8 + 9IIIIIII IIIIIIII IIIIIIIIIIIIIIIII IIIIIII IIIIIIIIIIIIIIIIII IIIIII IIIIIIIIIIIIIIIIIII IIIII IIIIIIIIIIIIIIIIIIII IIII IIIIIIIIIIIIIIIIIIIII III IIIIIIIIIIIIIIIIIIIIII II IIIIIIIIIIIIIIIIIIIIIII I IIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII IIIIIIIIIIIIIIIIIIIIIIIII =XXIIII 結果は同じですし、処理の回数は無駄と言えば無駄に増えていますが、こっちの方が計算っぽいと思えるかもしれません。 なお、数学的には、あるいは数学的な方法の一つとしては、 “a + b” というのは、このように書けます:while (b > 0) { a = succ(a) b = b - 1} ここの “succ” というのは、その引数である “a” の、整数における次の値を返す関数です。ですので、 “succ(a)” というのは “a + 1” という意味です。実際には数学だと再帰の書きかたのほうが好まれます。その場合、 “a” や “b” でもかまわないのですが、とくに “b” については具体的な数字のほうが分かりやすかったりするかと思うので、ここでは “2 + 3” ということで考えてみます:succ(succ(succ(2))) これはつまり、こういう意味です:2 + 1 + 1 + 1= 2 + 3 “succ” の回数分、 “1” を足しているので、こういう形になります。 2つめというか後半で示したスクリプトは、この形式に沿っているとも言えることがわかるかと思います。 なお、 “succ()” という関数は非常に重要で、 “1 + 1 = 2” の証明も、この関数をまず定義しています。というか、「次の値とはなにか」も含めて、 “succ()” の定義が証明のほとんどを占めています。 この “succ()” という関数は、lispなどの元にある計算モデルであるλ計算においても重要な関数です。λ計算が昔に構築されていたら、 “1 + 1 = 2” の証明も楽勝だったのにと言われたりします。  

繰り返しになりますが。プロジェクトの本文や、活動報告についての感想、ご意見、ご質問を、ぜひコメントでお寄せいただければと思います。現在は支援募集期間中であり、本企画の実施期間ではないため、お寄せいただいた感想などについてはリターンとしてではなく、お返事や回答をさせていただきます。 また、私個人についてはこちらをご覧ください。 本企画において、「スマホや、AI、IoT、ロボットに関係するプログラミングはどうなるんだ」という疑問もあるかもしれません。ですが、それらの話題を採用するかとなると、「う〜ん」というところです。 というのも、たとえばロボットを使うとなれば、「ロボットを動かすこと」が、すくなくともその課題においては目的になるでしょう。その際、「ロボットがきちんと動く」ことはどうやって確認すればいいのでしょうか？ 「課題においてデータ構造やアルゴリズムを指定するか」に書いたように:| 「動いたことで確認とする」というのは、実は極めて甘い基準 であり、あまり採用したい基準ではありません。あるいは、仮に「動いたことで確認とする」ことでよしとするなら、それでよしとできるような制約のきつい、あるいは発展性に乏しいトイ・プログラムでなければならないでしょう。 本企画では、同じく「課題においてデータ構造やアルゴリズムを指定するか」に書いたように:|「なぜきちんと動くと言えるのか」を説明できること、| あるいは強く言うなら証明できること を基本に据えたいと考えています。ですので、上記のようなものは、すくなくとも積極的に採用したいと思える範疇からは外れることになると考えています。 もっとも、本企画、つまり第一版では、スマホという媒体を使用することは、そもそも的に企画の範疇外です。ですが、AI、IoT、ロボットは、できないこともありません。統計に基づくAIは、統計をきちんと勉強してからということになるでしょうが、そうでないAIや、IoT、ロボットは、たとえば「探索」(データ構造としては、おおむね木構造かグラフ) からの発展の話題として扱えないこともないでしょう。というのも、「探索」はAIでよく使われる技術の一つですから。たとえば、LOGOという言語におけるタートルやタートル・グラフィックのようなものも含めてかまわなければ、そして「ロボットに迷路を抜けさせよう」という感じでよければ、やりようはいくつもあるかと思います。 すこし統計的なAIに触れるとしたら、グラフからオートマトンに発展し、それから小規模な確率付きオートマトンやマルコフ・モデル (マルコフ過程)、隠れマルコフ・モデル、さらにはn-gramをこちらで用意して、それを使って体験してみるということもできるかもしれません。 ですが、本企画では、積極的に表に「スマホや、AI、IoT、ロボット」という文言を出すことはないと思います。それらを表に出すと、「それらで何をしたいのか」と、「それらを動かすこと」という目的と手段が混乱するように思うからです。ただし、これはあくまで本企画の主旨から考えてということであることには注意してください。むしろ、このような態度としての企画であることから、それらを主眼としたプロジェクトとの住み分けができるでしょうし、場合によってはお手伝い、あるいは相互に協力できるかもしれません。

まず、え〜と、私についてですが、こちらをご覧ください。 本題に入りましょう。 1次元配列で、木構造を表わす方法を考えて見ましょう。 その前に、木構造とはどういうものだったかを確認しましょう:   この木構造では、1つの要素を、1つの要素だけとして描いていますが、配列で木構造を表わそうとする場合、そうはいきません。というのも、その要素が持つ値を保持する部分が必要ですし、その要素の子となる要素を示すための部分も必要です。 先の「配列、リスト、木構造」では、一番上の要素から、そのすぐ下の要素へはいくつもの親子関係がありました。ですが、ここでは、1つの親は、2つ以下の子しか持てないとします。すると、1つの要素として描かれていたものが実際にはどういうものである必要があるかがわかり、それは次のようになります:   もっとも、ここでは1次元の配列を考えていますから、実際には1次元の配列の中に、次のように3つ組で並んでいるとしましょう:   さて、これでどうやって木構造を表わすかというと、次のようになります (読み易いように、適宜スペースを開けたり、改行しています): [ ROOT, 3,6,　　"あ", 9, 12,　　"い", 15, 18,　　　　"う", φ, φ,　　"え", φ, φ,　　　　"お", φ, φ,　　"か", φ, φ] ここでの“ROOT”は木の起点であることを示す記号であり、“φ”はそこにはどんな値も入っていないことを示す記号とします。 “ROOT” は、他のなにかであっても−−たとえば “ん” というデータでも−−かまいません。また、基本的に配列では、一つの型の要素しか取れず、この例のように “あ” というような文字、あるいは文字列と、9というような数値が混在することはありません。ですが、ここではそれを無視することとします。もっとも、レコードを要素にした配列　(レコードの配列)という方法もあります。 このように1次元配列の形として書いただけではわかりにくいかもしれないので、これを図示しましょう:   この図は、たとえば「0: ROOT」というような書き方がされていますが、この「0:」にあたる部分は、上の配列での要素の番号です。 このように、一次元配列でも木構造は描けることがわかります。 取り得る木構造の形が決まっているなら−−つまり子は常に2個以下など−−、これでも案外不便はありません。慣れは必要かもしれませんが。 なお、この木構造の場合、親から子へは記録されている値から辿れますが、子から親へは辿れません。子から親へも直接辿れるようにするには、現在3つ組であるところにもう一つ要素を付け加え、そこに親の要素の番号を記録すれば、それも可能になります。このあたりは再帰やバックトラックなどの方法の方がいいということもあるので、必ずしも4つ組にする必要はありません。 このような木構造を、本企画で行なう講習に参加していただく児童・生徒に要求するかというと、別段要求はしません。児童・生徒がこのようなものを組み上げられるならそれでかまいませんし、別の方法があるならそれでもかまいません。たとえば、1次元配列を3つ使い、同様の木構造を表わすこともできるでしょう。あるいは、課題を解くのに用いるデータ構造が、そもそも木構造でなくてもかまいません。   追記 (Aug 07, 2017, 15:45JST):Gigazineにですが、「6歳の子ども向け「プログラミング教室」を実際にやってわかった成功させる方法」という記事がアップされています。 6歳児ですから、本企画の対象とする児童よりも低学年ではあります。ですが、この知見も参考にしていきたいと思います。