授業資料/07 の変更点

#contents

* 前回の課題について [#na54261f]

前回の課題は以下のようなものであった．

行列とベクトルの積，行列と行列の積を計算する関数をプログラミング

+ 行列は正方行列のみ扱うとしておく
+ 次元の違いのチェックはしなくてもよい(もちろんしてもよい)
+ (上級者向け)上で定義した ''inner_product'' 関数を用いて実装する

そして，4 x 4 の行列を適当に二つ，4次元ベクトルを適当に一つ用意して，それらに対して積の計算がうまくいくことを確認せよ．

&ref(/materials/warning.png); この文章を読む限り ''一般の n x n 行列を扱えないといけない'' (4 x 4 はあくまできちんと動くことの確認用) ので，それを念頭にプログラムを書いていこう．
&ref(/materials/warning.png); だから，条件を満たしていないので ''4 x 4 行列専用のプログラムは失格'' である．残念だけどね．

&br;
** 全体構造を考える [#i25568de]

いつものように全体構造を考える．
基本的な機能として行列同士の積と行列とベクトルの積の二つが必要で，例題としてそれをデモンストレーションする本文ということになるので，まずは以下のようになるだろう． ただし，最初から 4 x 4 行列を扱うのは面倒なので，まずは 2 x 2 行列などの「一番小さな問題」で試すように書いておく．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
include Math

# 行列同士の積: 行列二つが引数
def mtx_product_mtx(m_a, m_b)
  # 出力は行列．「とりあえず動くように」最初の引数を返しておく．
  return m_a
end

# 行列とベクトルの積: 行列とベクトルが引数
def mtx_product_vec(m_a, v_x)
  # 出力はベクトル．「とりあえず動くように」引数ベクトルを返しておく．
  return v_x
end

# 行列を人間用に出力する
def print_mtx(m_a)
end

# ベクトルを人間用に出力する
def print_vec(v_x)
end

# 以下，プログラム本体

# サンプルの 2 x 2 問題用データ
a = [[1,2],
     [3,4]]

b = [[5,6],
     [7,8]]

x = [10,11]

# 行列同士の積を計算
c = mtx_product_mtx(a,b)

# 行列とベクトルの積を計算
y = mtx_product_vec(a,x)

# 画面に出力
print_mtx(c)
print_vec(y)
}}

&br;
** 機能を増やしていく: 結果をすぐチェックできるように，表示機能を先に実装してみる [#s3e2c194]

今回の課題は行列の添字のズレなどのあちこちに間違いが発生しやすい．それを最小限に抑えるためにも表示機能が早めに実装されると楽が出来そうだ．そこで，''print_ '' 関数を先に実装しよう．
まずは，ベクトルの表示から手を付けるのが簡単だろう．例えば以下のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
def print_vec(v_x)
  print("[ ")
  for i in 1..v_x.size do
    print(v_x[i-1]," ")
  end
  print("]\n")
end
}}
この関数ができれば，行列の表示にはこれを利用するのが真っ当な人間の思考というものだ．以下のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
def print_mtx(m_a)
  for i in 1..m_a.size do
    print_vec(m_a[i-1])
  end
end
}}

この例では ''print_vec'' 関数を使えば ''print_mtx'' 関数ではほとんど低レベルの実装をしなくて良い．

&ref(/materials/warning.png);このように，「既にプログラムしてあることを利用してプログラムする」ことは非常に重要である． なぜなら，
+ 同じようなことを何度も書かなくて良いので，ミスが入り込む確率が下がる
+ 修正する時に，修正箇所が必要最小限で済む
+ プログラムの抽象度が上がり，よりきちんとしたものになる可能性が高まる

からである(Don't Repeat Yourself = ''DRY 原則''に近いか)．まあ簡単に言えば，
CENTER:&size(24){''プログラムでは同等の処理を重複して書くことは「悪」''};

だと思えば良い．

&br;
** 機能を増やしていく: 行列とベクトルの積 [#h04340c6]

次に簡単なのは，行列とベクトルの積の実装だろう．これは内積を使うようにすれば簡単だ．
ただ，決められた次元のベクトルの「ひながた」を用意する方法がわからないという場合もあるだろうから，そこを関数として「とりあえず後で考える」ようにすれば，次のようになるだろう．
&ref(/materials/warning.png); 人間の脳みそはある程度以上の複雑さに対処できないので，このように「後で考える部分を分離する能力」は非常に重要だ．急いで身につけよう．
これも強調しておこう．

CENTER:&size(24){''難しい部分は関数にして追い出して「後で考える」べし''};

如何に複雑さを分解するかがプログラミングの「キモ」である．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# ベクトルの内積．前回のコピー
def inner_product(v_a, v_b)
  sum = 0.0
  for i in 1..v_a.size do
    sum += v_a[i-1]*v_b[i-1]
  end
  return sum
end

# n 次元ベクトルを作る
def make_vec(n)
  # さあどうする?
end

# 行列とベクトルの積: 行列とベクトルが引数
def mtx_product_vec(m_a, v_x)
  v_y = make_vec(m_a.size)

  for i in 1..m_a.size do
    v_y[i-1] = inner_product(m_a[i-1], v_x)
  end

  return v_y
end
}}
そして，決められた次元のベクトルの「ひながた」を用意する関数 ''make_vec'' はこれまでの知識だけから作るならば以下のようになるだろう．
#highlighter(language=ruby,number=off,cache=on){{
# n 次元ベクトルを作る
def make_vec(n)
  # まず要素がひとつもない「空集合」を作る．
  a = []
  # 要素 0.0 を n個追加する．
  n.times { a.push(0.0) }
  # 出力
  return a
end
}}
&ref(/materials/warning.png); (上級者向け) Ruby の機能をきちんと使って書くならば
#highlighter(language=ruby,number=off,cache=on){{
# n 次元ベクトルを作る
def make_vec(n)
  return Array.new(n){0.0}
end
}}
という感じになるだろう．

さて，こうすることで行列とベクトルの積はきちんと計算できるはずであるから，実際に動かしてみると，
>  [ 1 2 ]
>  [ 3 4 ]
>  [ 32.0 74.0 ]

という出力が得られ，確かに 2 x 2 行列とベクトルの積が計算されていることが確認できる．

&br;
** 機能を増やしていく: 行列と行列の積 [#e7a15e78]

さて，最後は行列と行列の積である．これも，行列をベクトルの集まりと思えば難しくない．
あとは，行列から行ベクトル，列ベクトルを抜き出す操作をしっかり行えれば，内積が使える．
だから，例えば次のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
# 列ベクトルを抜き出す
def col_vec(m_a, k)
  v_y = make_vec(m_a.size)
  # 具体的な機能はあとで実装する
  return v_y
end

# n x m 行列を作る
def make_mtx(n,m)
  # さあどうする?
end

# 行列同士の積: 行列二つが引数
def mtx_product_mtx(m_a, m_b)
  m_c = make_mtx(m_a.size,m_a.size)

  # 内積を使えば，あとは数学の定義通り．
  for i in 1..m_a.size do
    for j in 1..m_a.size do
      m_c[i-1][j-1] = inner_product(m_a[i-1],col_vec(m_b,j))
    end
  end

  return m_c
end
}}
で，ここで必要になった二つの関数の機能を実装する．
まずは「行列から列ベクトルを抜き出す」機能だが，これは簡単で，次のようにすれば良い．
// programu source 表記
#highlighter(language=ruby,number=off,cache=on){{
def col_vec(m_a, k)
  v_y = make_vec(m_a.size)

  for i in 1..m_a.size do
    v_y[i-1] = m_a[i-1][k-1]
  end

  return v_y
end
}}
残った「行列のひながたを作る」機能は，ベクトルを作る機能を使って
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
# n x m 行列を作る
def make_mtx(n,m)
  a = []
  n.times { a.push( make_vec(m) ) }
  return a
end
}}
とすればよい．簡単すぎて馬鹿にされている気分も有るかもしれないけれども．
&ref(/materials/warning.png); (上級者向け) Ruby の機能をきちんと使って書くならば
#highlighter(language=ruby,number=off,cache=on){{
# n x m 行列を作る
def make_mtx(n,m)
  return Array.new(n){ Array.new(m){0.0} }
end
}}
という感じになるだろう．

さて，これでこの機能も完成した．試しに動かしてみると，
>  [ 19.0 22.0 ]
>  [ 43.0 50.0 ]
>  [ 32.0 74.0 ]

となり，確かに正しく動いていることが分かる．

&br;
** 問題を大きめに変更: 最終段階へ [#zfba35ec]

さて，きちんと動いているように見えるので，問題を指示された 4 x 4 に取り換えよう．
また，出力も少し読みやすくしたい．
ということで，例えば以下のようになるだろう．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# ベクトルの内積．前回のコピー
def inner_product(v_a, v_b)
  sum = 0.0
  for i in 1..v_a.size do
    sum += v_a[i-1]*v_b[i-1]
  end
  return sum
end

# n 次元ベクトルを作る
def make_vec(n)
  a = []
  n.times { a.push(0.0) }
  return a
end

# n x m 行列を作る
def make_mtx(n,m)
  a = []
  n.times { a.push( make_vec(m) ) }
  return a
end

# 列ベクトルを抜き出す
def col_vec(m_a, k)
  v_y = make_vec(m_a.size)

  for i in 1..m_a.size do
    v_y[i-1] = m_a[i-1][k-1]
  end

  return v_y
end

# 行列同士の積: 行列二つが引数
def mtx_product_mtx(m_a, m_b)
  m_c = make_mtx(m_a.size, m_a.size)

  for i in 1..m_a.size do
    for j in 1..m_a.size do
      m_c[i-1][j-1] = inner_product(m_a[i-1],col_vec(m_b,j))
    end
  end

  return m_c
end

# 行列とベクトルの積: 行列とベクトルが引数
def mtx_product_vec(m_a, v_x)
  v_y = make_vec(m_a.size)

  for i in 1..m_a.size do
    v_y[i-1] = inner_product(m_a[i-1], v_x)
  end

  return v_y
end

# 行列を人間用に出力する
def print_mtx(m_a)
  for i in 1..m_a.size do
    print_vec(m_a[i-1])
  end
end

# ベクトルを人間用に出力する
def print_vec(v_x)
  print("[ ")
  for i in 1..v_x.size do
    print(v_x[i-1]," ")
  end
  print("]\n")
end

# 以下，プログラム本体

a = [[1,2,3,4],
     [5,6,7,8],
     [9,10,11,12],
     [13,14,15,16]]

b = [[17,18,19,20],
     [21,22,23,24],
     [25,26,27,28],
     [29,30,31,32]]

x = [3,4,5,6]

# 行列同士の積を計算
c = mtx_product_mtx(a,b)

# 行列とベクトルの積を計算
y = mtx_product_vec(a,x)

# 以下，画面に出力
print("A = \n")
print_mtx(a)
print("\n")

print("B = \n")
print_mtx(b)
print("\n")

print("A B = \n")
print_mtx(c)
print("\n")

print("x = \n")
print_vec(x)
print("\n")

print("A x = \n")
print_vec(y)
}}
そして，これを動かすと次のようになる．
手計算などで，確かに正しい結果であることが確かめられる．
>  A =
>  [ 1 2 3 4 ]
>  [ 5 6 7 8 ]
>  [ 9 10 11 12 ]
>  [ 13 14 15 16 ]
>  &br;
>  B =
>  [ 17 18 19 20 ]
>  [ 21 22 23 24 ]
>  [ 25 26 27 28 ]
>  [ 29 30 31 32 ]
>  &br;
>  A B =
>  [ 250.0 260.0 270.0 280.0 ]
>  [ 618.0 644.0 670.0 696.0 ]
>  [ 986.0 1028.0 1070.0 1112.0 ]
>  [ 1354.0 1412.0 1470.0 1528.0 ]
>  &br;
>  x =
>  [ 3 4 5 6 ]
>   
>  A x =
>  [ 50.0 122.0 194.0 266.0 ]

&ref(/materials/warning.png); 完成したプログラムは長いが，こうしたやり方で順序立てで作れば難しいことは何も無い．
今回の課題が難しいと思った人は，全体構造を考えずになんとなくプログラミングしようとしたのではないだろうか．そのような学生は「思いつかなかった」と発言することが多いが，それは以下の二点においてそもそも考え方が間違っている．
+ 複雑なものに対する対処をいきなり「思いつく」ほど普通の人間の脳みそは良く出来ていない．にも関わらず自分はできると思い込んでいるという意味で ''傲慢'' である.
+ プログラムは「対象を分解して機能を記述する操作を繰り返した結果」なのにその結果を「思いつく」とみなすのは，''how'' が根本から間違っているという意味で「お金が空から降ってくるのを待つというのと同じ」だ．

これはおそらく，「複雑さを分解することの本質さ，重要性を理解していない」ことが原因だろう．このことは軽視してはならない．大事なことなので標語的に大きく書いておこう．
&br;

// CENTER:&size(24){''プログラミングは思いつくものではない．''};
// CENTER:&size(24){''対象の複雑さを分解してから機能を実装する「操作」である．''};
CENTER:&size(24){''プログラミングではテクニカルな機能実装に目を奪われがちだが，''};
CENTER:&size(24){''むしろ「問題をどう分解するか」に注力すべきである．''};
&br;

&ref(/materials/warning.png); 「難しかった」「思いつかなかった」とレポートに書いた人は，自分に何が足りないのかもう一度ゆっくり考えてみよう．

&br;
** プログラム中に同じことを繰り返さない [#adc95422]

先に書いたが，同様の処理をなんども書かずに「既にプログラムしてあることを利用してプログラムする」ことは重要である．
&ref(/materials/warning.png); 実際に，上のサンプルでは「要素を掛けて足していく操作」が一箇所にしか無いことに着目しよう．そして，自分の書いたプログラムではそうした操作が何箇所に書かれているか，チェックしてみよう．

&br;
* 条件が満たされている間はループする : while 命令 [#d2fc21da]

条件が満たされている間はループするという制御を学ぼう．
まずは文法を書いておこう．
&br;

&size(24){''while (&color(blue){条件};) do''};
        &size(16){''&color(blue){上の条件が満たされたら実行される};''};
        &size(16){''&color(blue){…};''};
        &size(16){''&color(blue){# ここまで来たら，もう一度上に戻って条件がチェックされる};''};
&size(24){''end''};
&br;

&ref(/materials/warning.png); ''for'' と ''if'' を組み合わせて擬似的に実現することもできる.

&ref(/materials/notes.png); この ''while'' 命令を使って，1 + 2 + 3 + ... という計算がいつ指定された数字を超えるか調べるプログラムを書いてみよう．途中経過も出力するようにしよう．
&br;
この場合は，例えば次のようなプログラムになるだろう．
// programu source 表記
#highlighter(language=ruby,number=on,cache=on){{
include Math

# 超えるかどうか調べる数は起動時にもらう
n = ARGV[0].to_i

# 合計の初期値はもちろんゼロ．
sum = 0

# 足していく数． 最初は 1 からだが，この段階での sum に対してはまだ 0 しか足されていないので，
# ゼロにしておくのが合理的．
i = 0

# n を超えてないと while の中身が実行され，再び n を超えていないかチェック…を繰り返す．
while (sum <= n) do
  print("i = ", i, ", sum = ", sum, " <= ", n, "\n") 
  # 先に出力. この段階なら確実に sum <= n.
  # while では，結果に対する判断や出力は条件チェックのすぐあとに行うのが筋．

  i += 1     # i を 1増やす．
  sum += i   # i だけ合計する．
end

# i を増やしてから i を sum に足すこと! 
# sum に足してから i を増やすと，最後につじつまが合わなくなるよ．
# よく分からない人は，sum に足してから i を増やすようにしてプログラムを動かしてみよう.

# 最後に結果を出力．
print("i = ", i, ", sum = ", sum, " > ", n, "\n")
}}
これを
  ruby -w ./over.rb 100

などとして起動すると，
>  i = 0, sum = 0 <= 100
>  i = 1, sum = 1 <= 100
>  i = 2, sum = 3 <= 100
>  i = 3, sum = 6 <= 100
>  i = 4, sum = 10 <= 100
>  i = 5, sum = 15 <= 100
>  i = 6, sum = 21 <= 100
>  i = 7, sum = 28 <= 100
>  i = 8, sum = 36 <= 100
>  i = 9, sum = 45 <= 100
>  i = 10, sum = 55 <= 100
>  i = 11, sum = 66 <= 100
>  i = 12, sum = 78 <= 100
>  i = 13, sum = 91 <= 100
>  i = 14, sum = 105 > 100

というように結果が得られる．どうだろうか．自分でできただろうか．

&br;
&ref(/materials/warning.png); 勘の良い人はもう気づいているだろうが，while 命令の本質を書いておくと，
CENTER:&size(24){''while = 脱出判定つき無限ループの一種''};

である．

&br;
** Fizz Buzz に挑戦 [#w6428d88]

Fizz Buzz とは言葉遊びの一種で，1, 2,... と順に数字を述べていく時に，
- 3 で割り切れるときはその数字の代わりに ''Fizz'' と言う
- 5 で割り切れるときはその数字の代わりに ''Buzz'' と言う
- ただし，3 でも 5 でも割り切れるときは特別にその数字の代わりに ''Fizz Buzz'' と言う

というものである．そこで，これを以下のようにプログラムしよう．

- プログラム起動時にある程度大きな数 ''n'' (100 ぐらい?) が与えられる．
- 1,2,... と数を上のルールで出力していって，''Fizz'', ''Buzz'', ''Fizz Buzz'' の出現回数の合計が ''n'' になったら停止する．

具体的には，例えば
  ruby -w fb.rb 10

として 10個の「代わり」が出てくるまでを出力させると，
>  1
>  2
>  Fizz
>  4
>  Buzz
>  Fizz
>  7
>  8
>  Fizz
>  Buzz
>  11
>  Fizz
>  13
>  14
>  Fizz Buzz
>  16
>  17
>  Fizz
>  19
>  Buzz
>  Fizz

となる．さて，みなさんはうまくできるだろうか．
&ref(/materials/warning.png); それっぽい動作が得られても安心してはいけない．きちんと私のサンプルと同じ出力になっているか，変なところで間違えて 15 の代わりに ''Buzz'' などとなっていないか，注意深く確かめよう．

&br;
** (上級者向け) 3の倍数と3のつく数のときだけアホ [#y02db8ad]

「3の倍数と3のつく数のときだけアホになる」として上と同じことに挑戦してみよう．
ただし，「3のつく」という条件に文字列処理が必要で，これは教えた範囲に入ってない知識が必要なので自分で調べる必要がある．

&br;
** Collatz の予想を調べてみよう [#a4adf91b]

''Collatz の予想'' という予想がある．これを ''while'' を使って少し確かめてみよう．
まずこの予想について記述しよう．この予想とは，正整数 ''n'' に対する関数 ''f'' を
- n が偶数の場合: f(n) = n / 2
- n が奇数の場合: f(n) = (3 * n) + 1

とすると，「いかなる正整数に対してもこの ''f'' を繰り返して適用するといずれ必ず 1 になる」というものである．

&ref(/materials/notes.png); この予想が与えられた数について成り立つかどうかを確かめるために，入力した数に ''f'' を適用して 1 になるまでの経緯を出力するプログラムを書こう．
具体的には，例えば
  ruby -w collatz.rb 100

として最初に "100" からスタートした場合をチェックさせると
>  100 -> 50 -> 25 -> 76 -> 38 -> 19 -> 58 -> 29 -> 88 -> 
>  44 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 
>  -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1.

というような出力を出すようにしよう．
&ref(/materials/warning.png); 「''f'' の結果が 1 でない間は ''while'' の中身が実行される」というストーリーになるはずだ．

&br;
* 今日の総仕上げ [#be9b628a]

上の Collatz の予想を以下のように調べるプログラムを書いて，結果をファイルにとっておいてから適当にグラフにしよう．
条件は以下の通りである．

- 正整数 ''k'' に対して，Collatz の関数 ''f'' を何回適用すると 1 になるかを出力する関数 ''num_col(k)'' が ''def'' を使って定義されている．
- プログラム起動時にある程度大きな数 ''n'' (100ぐらい) が与えられる．
- 1 から始めて，''n'' まで ''num_col'' の結果を出力する．
- 注: ''num_col(1)'' はまあ 3 と解釈してもよいだろう( 0 としてくれるとより良いが)

&ref(/materials/warning.png); ''num_col(1)'' が 3 になったりしないように注意しよう．

具体的には，例えば
  ruby -w col_num.rb 30

として 30 までを調べさせると
>  1, 0
>  2, 1
>  3, 7
>  4, 2
>  5, 5
>  6, 8
>  7, 16
>  8, 3
>  9, 19
>  10, 6
>  11, 14
>  12, 9
>  13, 9
>  14, 17
>  15, 17
>  16, 4
>  17, 12
>  18, 20
>  19, 20
>  20, 7
>  21, 7
>  22, 15
>  23, 15
>  24, 10
>  25, 23
>  26, 10
>  27, 111
>  28, 18
>  29, 18
>  30, 18

というような出力を出すようにということである．
そして，この出力データをファイルに保存しておいて適当なツールでグラフにして(ただし，エクセル等の表ツールは禁止)，
&ref(./collatz.png,80%);

というようなものを作ろうということになる．

この例では 30までだが，これを 100 ぐらいの値で実行して，データとグラフを得られたら完成，ということになる．

&br;
* レポート [#z0c9dd1e]

本日受けた講義および行った実習について，簡単にまとめた報告をせよ.
また，総仕上げの部分で自分で書いたプログラムを報告せよ.

もちろん各自の

+ 所属(学部，学科)
+ 学籍番号
+ 学年
+ 氏名
+ 日時
+ 肝心のレポート内容(得た知見，作業について気づいたこと等も)

を書くのを忘れないように. 

* about Icons, ClipArts [#ubfbbb67]
Some icons in this page are downloadable at [[ICONFINDER:http://www.iconfinder.net/]].

The "note" icon &ref(/materials/notes.png); designed by [[Marco Martin:http://www.notmart.org/]] is distributed with the LGPL licence,
the "warning" icon &ref(/materials/warning.png); designed by [[Alexandre Moore:http://nuovext.pwsp.net/]] with the GPL licence
and the "triangle" icon &ref(/materials/JNorth_arrow-right-sm.png); designed by [[Joseph North:http://sweetie.sublink.ca/]] is distributed with the [[Creative Commons (Attribution-Noncommercial-Share Alike 3.0 Unported):http://creativecommons.org/licenses/by-nc-sa/3.0/]] licence.

Some clip arts used in this page are downloadable at [[Open Clip Art Library:http://www.openclipart.org/]].
We deeply appreciate their superb works. With licence, they describe that "the actual clipart content on open clipart library is Public domain" in the web.

// ━┃┏┓┛┗┣┳┫┻╋


// コマンドライン入力は「行頭をブランクで始める」.
// コマンドライン出力は「行頭を > で始める」.

// 実習アイコン
// &ref(/materials/notes.png);

// 注意アイコン
// &ref(/materials/warning.png);

// Link アイコン
// &ref(/materials/JNorth_arrow-right-sm.png);

// 大文字での強調 
// CENTER:&size(24){''ほげほげ''};

// programu source 表記
// #highlighter(language=ruby,number=on,cache=on){{}}