11/1 データと計算(2)

前回までの補足

• 講義のスライド(PDF形式)は，cfiveの「情報科学(水4)」のコースの「教材」のところからダウンロード可能にしてある．講義受講者以外への再配布は許可されないので注意すること．

スライドの補足

• オートマトンの動作を理解するには，シミュレータで実行してみるのが早道だろう．前期の「情報」で使ったオートマトンのシミュレータの使用法を書いたページオートマトンシミュレータの使い方にしたがって，スライドのプログラムを試してみると良い．

スライドに使われたプログラム

再帰的な計算をメソッドにする

def f(n)
  if n == 0 
    1
  else
    f(n-1)*n
  end
end

def c(n)
  if n == 1 
    0
  elsif is_even(n) 
    c(n/2) + 1
  else
    c(3*n+1) + 1
  end
end

再帰的データ構造に対する再帰的な計算

Expr = Struct.new(:left, :operator, :right)

def sum(t)
  if t.kind_of?(Expr) 
    sum(t.left) + sum(t.right)
  elsif t.kind_of?(Integer)
    t
  else
    0
  end
end

再帰的なデータ構造を扱う関数

def mirror(t)
  if t.kind_of?(Expr)
    Expr.new(mirror(t.right), 
             t.operator, 
             mirror(t.left))
  else
    t
  end
end

計算 = 状態の変更

def f(n)
  if n == 0 
    1
  else
    f(n-1)*n
  end
end

状態遷移を使ったプログラム

def f_state(n)
  k=n
  g=n
  while k>1
    g = g * (k-1)
    k = k-1
  end
  g
end

状態遷移を使ったプログラム

def f_state(n)
  k,g=n,n
  while k>1
    k,g=k-1,g*(k-1)
  end
  g
end

状態遷移による計算の定義例

def c_state(n)
  k=n
  c=1
  while k>1
    if is_even(k) 
      k=k/2
    else
      k=k*3+1
    end
    c=c+1
  end
  c
end

状態遷移による計算の定義例

def c_state(n)
  k,c=n,1
  while k>1
    if is_even(k) 
      k,c=k/2,c+1
    else
      k,c=k*3+1,c+1
    end
  end
  c
end

不変量

def f_state(n)
  k=n
  g=n
  while k>1
    g = g * (k-1)
    k = k-1
  end
  g
end

繰り返しの例: ベクトル演算

def vector_scale(s, v)
  w=Array.new()
  for i in 0..(v.size-1)
    w[i] = s * v[i]
  end
  w
end


def vector_add(v1, v2)
  w=Array.new()
  for i in 0..(v1.size-1)
    w[i] = v1[i] + v2[i]
  end
  w
end
$x = [ 1.0, 0.0, 0.0 ]
$y = [ 0.0, 1.0, 0.0 ]
$z = [ 0.0, 0.0, 1.0 ]

vector_add(
	$x,
	vector_scale(
		2.0,
		vector_add($y, $z)))

繰り返しの例: 文字列の検索

def match_at(s, p, i)
  j = 0
  while j < p.size 
        && s[i+j] == p[j]
    j = j + 1
  end
  j == p.size
end

def find(s, p) 
  i = 0
  while !match_at(s, p, i)
    i = i + 1
  end
  i
end

オートマトンの実装

$automaton = [[0,1], [2,0], [1,2]]
def make_transitions(input)
  s = 0
  for i in 0..(input.size - 1)
    c = input[i] - ?0
    s = $automaton[s][c]
  end
  s
end

オートマトンの実装

$final = 0
def accept(input)
  s = make_transitions(input)
  s == $final
end