12/13 数値計算(3)，パターン認識(1)

補足

演習室内は飲食禁止です．ペットボトル等を持ち込む場合も，バッグの中にしまってください．
TAはこれまで前川さんと森永さんでしたが，残りの3回は森永さんに代わって学際情報学府修士課程の岩佐駿さんと，前川さんとなります．

試験について

試験は1月25日(木) 3限 13:10-になりました．試験時間は発表されていませんが，参考情報としてはここ数年は60分でした．
詳細が決まり次第，アルゴリズム入門共通資料のページで公開されます．
試験採点後に採点した答案用紙を返却 (正確にはスキャンしたPDFファイルをITC-LMSで本人が参照できるようにする)する予定です(採点に異議がある場合は，期限までのクレームを受け付ける予定)．
2010年度共通問題
2011年度共通問題
2012年度共通問題
2013年度共通問題
2014年度共通問題
2015年度共通問題
2016年度共通問題

前回の感想，質問より

Q(前々回の質問ですが，前回の講義の内容なので今回掲載します).

資料pdfでは最大、最小値のオーダーの限界は10³⁰⁸とあります。ですが、irb上で2.0**-1074を実行すると 5.0e-324という値がちゃんと出力されますが、これは有効桁数を減らして最小値を拡張しているということでいいのでしょうか。

A.

スライドや教科書では省略しているのですが，浮動小数点の規格 IEEE 754ではまさに，「有効桁数を減らして最小値を拡張」を実行しています．具体的には，スライドのbが0の時(絶対値が2**-1023以下)には，仮数部の「1.XXX」の1を省略しないでデータに入れ，2**-1023以下の小さい数を表します．

irb(main):032:0> [2.0**-1023+2.0**-1025].pack("E").unpack("Q")[0].to_s(2)
=> "1010000000000000000000000000000000000000000000000000"
irb(main):033:0> [2.0**-1024+2.0**-1026].pack("E").unpack("Q")[0].to_s(2)
=> "101000000000000000000000000000000000000000000000000"

のようにして，浮動小数点のビット表現をみてみるとこのあたりがわかると思います．

Q.

チェックは通ったが、実際に動かしてみると一列目が[[1.0, 0.0, 0.0, 1.0000000000000002]となってしまった。

A.

相対誤差は 0.0000000000000002/1.0000000000000002 = 1.9999999999999995e-16 なので，有効数字は16桁近くあるということになります．元々，浮動小数点の倍精度表現では有効桁数は53ビット，10進数で16桁に少し足りない程度なので，この程度の誤差は許容範囲内になります．

Q.

誤差難しい

Q.

浮動小数点表示まではある程度理解できたが、式変形による桁落ちの回避とかGauss消去法はさっぱりだった。

A.

第6章の練習，投票のところに，この講義独自の例を追加しました．今日の講義の最初で復習も兼ねて扱います．

前回の課題について

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

関数maxrowの典型的な解答は以下のとおりです．

def maxrow(a,k)
    max_i=k
    for i in (k+1)..(a.length()-1)
        if abs(a[max_i][k]) < abs(a[i][k])
            max_i = i
        end
    end
    max_i
end

上のプログラムでは，abs(a[max_i][k]) の計算が何度も行なわれる．これを節約するために，以下のように書いている人もいた．

def maxrow(a,k)
    max_i = k
    max_v = abs(a[k][k])
    for i in (k+1)..(a.length()-1)
        v = abs(a[i][k])
        if max_v < v
            max_i = i
            max_v = v                   
        end
    end
    max_i
end

def maxrow(a, k)
    return a.index(a[k..-1].max_by{|ai| ai[k].abs()})
end

この問題を特には abs.rb を同じディレクトリに作成しておく必要がある．教科書の練習3.1にあるが，この講義のスライドの練習問題では扱わなかったので，第6章の練習，投票の中で関数の定義も含めて書いてある．
```
  
```

今日の練習，投票

投票システム

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の掲示板12/13の課題，質問に以下の内容を書き込んでください．プログラムを除いて100文字以上は書き込みをお願いします．
講義の感想，質問を書きこんでください．講義で用いなかった教科書の練習問題に対して書きたい人は書きこんでも構いません．

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

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