1/10 レコードとオブジェクト，その他

補足

演習室内は飲食禁止です．ペットボトル等を持ち込む場合も，バッグの中にしまってください．

試験について

試験は1月25日(木) 3限 13:10-になりました．試験時間は60分の予定です．
詳細が決まり次第，アルゴリズム入門共通資料のページで公開されます．
試験採点後に採点した答案用紙を返却 (正確にはスキャンしたPDFファイルをITC-LMSで本人が参照できるようにする)する予定です(採点に異議がある場合は，期限までのクレームを受け付ける予定)．2/1-2/8の間にITC-LMSにログインして，アルゴリズム入門のコースを選択して，「お知らせ」を読んで指示に従ってください．採点に関する質問等は，ITC-LMS上で2/8まで受け付けます．
2010年度共通問題
2011年度共通問題
2012年度共通問題
2013年度共通問題
2014年度共通問題
2015年度共通問題
2016年度共通問題

前回の感想，質問より

Q.: 二つ以上の解が存在する時も機械的にただひとつの解が優先されるが、参考としてほかの解も示し得るものだとより便利だと思う。
A.: そのようなプログラムを作成するのにチャレンジしてみるのも良いと思います。ただ、解の数が問題のサイズの指数のオーダになることがあるので、そのような入力を与えるといつまでたっても答えが得られないということはあるはずです。
Q: alignの穴埋めの答えはv0,v1,v2をあらかじめ用意した後でmaxに代入していましたが、maxでそのまま入れては何か問題があるのでしょうか。
A(TA前川さん).: プログラムの見やすさのためにv0, v1, v2と置いていますが、変数に代入せずにmaxに式を直接入力しても同様の動作になります。
Q.: tracebackはどのような場面で使われるのだろうかと思いました。
A.: 扱う問題にもよりますが，近い2つの種の遺伝子配列のアラインメントを取った場合，どのような遺伝子変異があったのかを推測するためには，ギャップの情報は役にたつと思われます．
Q.: 最後の手書き文字認識の話で、あえて書き順とか線を引く向きを逆にしたらいくら綺麗に書いても判別できないのかなと思った。そうだったら面白い。
A.: はい．初期の文字認識ソフトでは「認識させるためには正しい書き順を覚える必要がある」という特性があるものもありました．ただし，最近は「多くの人がやる書き順の誤りに対応する」ように進化しているはずです．
Q.: 機械学習からディープラーニングに移ったように、人間の脳の仕組みが解明されていくにつれ新たな手法が開発されると思うと楽しみです。
A.: 前回の講義のスライドで，「活性化関数φとしては実際の神経細胞をモデル化したものが使われたが，次第に都合の良さを優先」と書いたように，現在のディープラーニングは，「人間の脳の仕組み」がどうなっているかによらず，「役に立てば何でも入れる」という形で進歩しています．この点を誤解すると，ディープラーニングに過度の期待をしてしまうおそれもあるので，一応指摘しておきます．
Q.: Sセメの授業で遺伝子やアミノ酸をアライメントすることがあったが、その時に使ったサイトでも同じように動的計画法を使っているのかなと思った。
A.: この講義で扱った，長さnの2つのシンボル列のアラインメントを O(n**2)のメモリを使用して，O(n**2)の計算時間で計算する動的計画法は，この問題に対して基本的に使われるアルゴリズムになっています．一方で，「差分がnに比べて非常に小さい」ケースなどを対象にしたよりメモリ使用量，計算時間の小さいアルゴリズムも知られているので，それらも使われていた可能性はあります．

授業アンケート

授業アンケートを実施します．
授業IDは「3613」です．

前回の課題について

ITC-LMSの掲示板12/20課題，質問への書き込みは 1/10 11:00現在で 58名が済んでいます．

関数alignと関数 traceback に取り組んだ人が多かった．典型的なalignの回答は以下のとおり

def align(s,t)
  m = s.length()
  n = t.length()
  a = make2d(m+1,n+1)
  a[0][0] = 0
  for j in 1..n
    a[0][j] = a[0][j-1] + g()
  end
  for i in 1..m
    a[i][0] = a[i-1][0] + g()
  end
  for i in 1..m 
    for j in 1..n
      v0 = a[i-1][j] + g()
      v1 = a[i-1][j-1] + q(s[i-1],t[j-1])
      v2 = a[i][j-1] + g()
      a[i][j] = max(v0,max(v1,v2))
    end
  end
  a
end

典型的なtracebackの回答は以下のとおり

def traceback(a,s,t)
  u = ""
  v = ""
  i = s.length()
  j = t.length()
  while i>0 || j>0
    if j>0 && a[i][j] == a[i][j-1] + g() # 左のマスの値からa[i][j]の値が決まっていた場合
      u = "-"           + u
      v = t[j-1 .. j-1] + v
      j = j - 1 # go left
    else
      if i>0 && j>0 &&
          a[i][j] == a[i-1][j-1] + q(s[i-1], t[j-1]) # 左上のマスの値からa[i][j]の値が決まっていた場合
        u = s[i-1 .. i-1] + u
        v = t[j-1 .. j-1] + v
        i = i - 1
        j = j - 1
      else
        if i>0 && a[i][j] == a[i-1][j] + g() # 上のマスの値からa[i][j] の値が決まっていた場合
          u = s[i-1 .. i-1] + u
          v = "-" + v
          i = i - 1
        end
      end
    end
  end
  [u,v]
end

なお，現在の Ruby では文字列sのi-1番目の1文字からなる文字列を生成するには，s[i-1 .. i-1]と書かずに s[i-1] と書くことも可能なので，そのように書いていた人もいた．

今日の練習，投票

第8章の練習，投票

投票システム

vote.rbをダウンロードして(「リンク先のファイルを別名で保存」で，ホームフォルダの下のalgo17を選択(なければ作る)．".txt"を「追加しない」を選ぶ)，ホームディレクトリに保存します．ドックからターミナルを起動して，

cd algo17

を済ませてから，

ruby vote.rb 選択肢番号

のように使います．

irbを使いながら(一旦終了せずに)，投票システムも使うには，ターミナルのメニューバーの「シェル」->「新規タブ」を選ぶか，[Command]+[T]で別のタブを開いて(あるいは[Command]+[N]で別のウィンドウを開いて)，投票システムを使うことをお勧めします．このあたりのことは，「はいぱーワークブック」の15.4 ターミナルの便利な使い方に書いてあるので参考にしてください．

テキストの補足

誤差の回避法について第6章の練習，投票のところに，この講義独自の例を追加しました．

実際のRuby処理系での実数の倍精度表現は，以下のようにすれば見ることができます．以下は0.5 の倍精度表現を見ています．


irb(main):034:0> a = 0.5
=> 0.5
irb(main):035:0> s = ("0"*64 + [a].pack("E").unpack("Q")[0].to_s(2))[-64..-1]
=> "0011111111100000000000000000000000000000000000000000000000000000"
irb(main):036:0> [s[0], s[1..11], s[12..-1]]
=> ["0", "01111111110", "0000000000000000000000000000000000000000000000000000"]

第4章のチェックは配布プログラム中のcheck.rb では prime のチェックがうまくいかないようです．とりあえずは修正版のcheck.rbを ~/algo17 にダウンロードすると直るはずです．
ターミナルでは，メニューバーから，「シェル」->「新規ウィンドウ」あるいは，「コマンドキー(⌘)」+「N」で新たなターミナルウィンドウを開くことができます．

ウィンドウが多くなるのが面倒な人は，「シェル」->「新規タブ」あるいは「コマンドキー(⌘)」+「T」で同じウィンドウ内に新しいタブでターミナルを開くことができます．

ターミナルを開くたびに
```
cd ~/algo17
```
と入力してください．これらの機能を使うと，irbを抜けずにvoteできます．
ターミナルの基本的な使い方は，はいぱーワークブックの15.2 ターミナルの基本的な使い方を，より高度な使い方は，15.4 ターミナルの便利な使い方を参照してください．
cdというコマンドと「~」の意味は，はいぱーワークブックの14.4 コマンドを使ったファイル操作の14.4.1 ディレクトリを読むと分かります．
Webブラウザ上で，ターミナルの実行，Ruby関数の実行，ファイルの編集ができる iruby が利用可能になっています．ターミナル上で，
```
iruby notebook
```
を実行すると，Webブラウザ上で対応するタブが開きます．
第1章で，irbを起動直後に，
```
include(Math)
```
を入力するように書いています．毎回入力するのが面倒な場合は，ホームディレクトリの下に「.irbrc」というテキストファイルを作り，その中に
```
include(Math)
```
と書いておくと，irb起動時にこのファイルの中身を実行してくれるので，毎回指定しなくても大丈夫です．ただし，このファイルの実行中にエラーが出ないように正しく記述剃る必要があります．また，
```
Math.sqrt(2)
```
のような形で指定すれば，
```
include(Math)
```
は不要です．
ある程度大きなプログラムを作る場合は，テキストエディタを使って入力してファイルに保存しておくと，後から修正したり再利用が容易におこなえます．テキストエディタの説明は，はいぱーワークブック「8. テキストエディタ」を参照してください．
miを使う場合に改行コードがCR(Mac)になっている場合は，LF(UNIX)にしてから保存してください．
この講義で作成したプログラムのファイルは自分のホームディレクトリ(ホームフォルダ)の下に「algo17」という名前のディレクトリ（フォルダ）を作って，その下に置くようにしています．スライドや教科書でファイル名が指定されている場合もあるので，その場合は指定されたファイル名を使うようにしてください．
情報科学入門: Rubyを使って学ぶ / 配付プログラムの中には練習問題のチェックプログラムが含まれています．たとえば，第1章の練習問題をテストする時には，同じディレクトリに，練習問題で作成したプログラムを教科書で指定されたファイル名で置いて，
```
ruby check.rb ex01.rb
```
と実行すると，関数を与えた時の入力と出力があっていることが確認できます．詳しくは，補足説明 (練習問題確認プログラムの使い方)を御覧ください．

今日の課題

講義中に投票を求められるので，投票システムを使って投票をしてください．
ITC-LMSの掲示板1/10の課題，質問に以下の内容を書き込んでください．プログラムを除いて100文字以上は書き込みをお願いします．
講義の感想，質問を書きこんでください．講義で用いなかった教科書の練習問題に対して書きたい人は書きこんでも構いません．

自宅で自習をする人のために

アルゴリズム入門共通資料の中に講義で使うRuby言語の処理系のインストール法があります．