11/1 関数から「計算」へ(2), アルゴリズムと計算量(1)

前回の補足

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

前回の感想，質問より

Q.

prime(99991)を計算しようとすると動かなかった．　これとはべつのコードでprimeを定義すれば９９９９１も処理できるようにんるのでしょうか？

A.

はい．

SystemStackError: stack level too deep
	from sod.rb:6:in `sod'
	from sod.rb:9:in `sod'
       ...

のようなエラーが出ると思いますが，関数 sod が再帰的に定義されていて，実行時に呼び出しの深さが深くなりすぎると(この場合では10万位)，このようなエラーが出てしまいます．関数sodを繰り返しで書き直したり，別の方法で素数かどうかを判定するようにすれば，もっと大きいnについても計算できるようになります．

Q.

matchで本当に調べられているのか、確かめるためにmatch(hogehoge,hoge)と入力してみたらうまくできませんでした。なんでだろうと思って出てきた注意をみてみたらhogehogeなる未定義の変数が存在していると捉えられたようです。文字列はだぶるくおーてーしょんまーくで括らないと文字列だと思ってくれないのですね。まったくコンピュータは頭が固いなあと思いました。

A.

「頭が固い」というのは別の言い方をすると，「書いた通りに動く」という点でメリットにもなりますね．プログラミング言語の文法は「状況によって別の意味で解釈される」ことがないように定められています．

前回の課題について

ITC-LMSの掲示板10/25課題，質問への書き込みは 10/31 10:00現在で 49名が済んでいます．
prime の典型的な提出プログラムは以下のようになっている．
```
def prime(n)
 1 == sod(n, n - 1)
end
```
以下のように書くのは冗長．
```
def prime(n)
  if sod(n, n - 1) == 1
    true
  else
    false
  end
end
```
「prime(1) は true でも構わない」と問題文に書いてあるが，
```
def prime(n)
 n + 1 == sod(n, n)
end
```
と書いて，prime(1) を false になるように書いている人もいた．

combinationの典型的な解答は以下のとおり

def combination(n,k)
  if k > n
    0
  else
    if k == 0
      1
    else
      combination(n - 1, k - 1) + combination(n - 1, k)
    end
  end
end

前回もあったが，elsif を使って以下のように書いた解答もあった．

def combination(n,k)
  if k>n
    0
  elsif k==0
    1
  else
    combination(n-1,k-1)+combination(n-1,k)
  end	
end

別の漸化式を使って以下のように定義した人もいた．

def combination(n,k)
  if n > k
    combination(n-1,k)*n/(n-k)
  elsif n < k
   0
  else
   1
  end
end

階乗(factorial)の関数を定義して，それを使って計算した人もいた．

def factrial(n)
  if n>=2
    factrial(n-1)*n
  else
    1
  end
end

def combination2(n,k)
  factrial(n)/(factrial(n-k)*factrial(k))
end

match_safeの典型的な解法は以下のとおり．

def match_safe(s, p)
  i = 0
  sl = s.length()
  w = p.length()
  while i <= sl - w && submatch(s, i, p, w) < w
    i = i + 1
  end
  if i <= sl - w
    i
  else
    -1
  end
end

今日の練習，投票

授業の登録方法

教材のダウンロード，課題の提出のため，ITC-LMSへのコース登録が必要になります．ITC-LMSへの登録方法に従ってコース登録してください．
Utask-Webでの履修登録は別に必要になります．

講義資料

教科書は情報科学入門 2700円(税込み) になります．正誤表が公開されているので，そちらも参照してください．また，電子版も発売されています(書籍版よりも若干安くなっているようです)．
講義スライドはITC-LMSで「アルゴリズム入門(水4)」を選んで「教材」を選択するとダウンロードできるようにする予定です．

講義フォルダの作成

講義に関連したファイルはホームフォルダ直下に置くのではなく，講義専用のフォルダをalgo17 という名前で作成してください．ターミナルでフォルダを作るには，
```
mkdir algo17
```
のようにします．そして，ターミナルを開くたびに
```
cd algo17
```
と入力してからirbを動かしてください．詳しくは，はいぱーワークブック「14.4 コマンドを使ったファイル操作」を参照してください．

配付プログラムのダウンロード

配付プログラムのページから，allcode.zipのリンクを右クリックして，「リンク先のファイルを別名でダウンロード」を選びます．
保存先のフォルダとして，さきほど作成したalgo17を選択します．
ターミナルで，
```
cd algo17
unzip allcode.zip
```
を実行してください．
Finderでallcode.zip をダブルクリックして展開した場合はallcodeというフォルダが下に作られるので、そこのファイルをすべて algo17 のフォルダに移動してください．
配付プログラムは，未完成の場合があります．mi等のテキストエディタで中身を確認した上で，必要があれば修正して使います．

投票システム

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

cd algo17

を済ませてから，

ruby vote.rb 選択肢番号

のように使います．

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

テキストの補足

第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
```
と実行すると，関数を与えた時の入力と出力があっていることが確認できます．詳しくは，補足説明 (練習問題確認プログラムの使い方)を御覧ください．

今日の課題

講義中に投票を求められるので，投票システムを使って投票をしてください．
今日(11/1)は通常の課題はありません．第1-4章まとめ課題に取り組んでください．課題とは関係なく 11/1までの講義での質問等がある人はITC-LMSの掲示板11/1の質問に書き込んでください．

第1-4章まとめ課題

自分の好きな図を描くプログラムを書いて，プログラムと実行結果の画面を第1-4章まとめ課題に投稿して下さい．第3章の最後にある図でも良いし，自分で工夫して考えた図でも良いです．
途中でiMac端末の画面を取り込んでpng形式のファイルに変換する必要があります．これには，Finderを使って，「アプリケーション」-> 「プレビュー.app」を起動して，「ファイル」->「スクリーンショットを撮る」->「選択部分」で取り込む部分を選んでから，「ファイル」->「別名で保存」でフォーマット「PNG」を選んで，適当なフォルダに保存してください．

ITC-LMSのマニュアルによると，画像ファイルの登録可能な拡張子は以下のようになっているようです．

.ai, .ani, .anim, .apng, .art, .bef, .bmf, .bmp, .bsave, .cal, .cdf, .cdr, .cgm, .cgm, .ciff, .cin, .cpc, .djvu, .dng, . dpx, .dxf, .ecw, .emf, .eps, .eva, .exr, .fits, .flic, .fpx, .gerber, .gif, .hdri, .hvif, .icer, .icns, .ico, .ics, .iges, .iges pgml, .ilbm, .jbig, .jbig2, .jng, .jpeg, .jpeg 2000, .jpeg
xr, .jpeg-hdr, .jpeg-ls, .miff, .mng, .pbm, .pcx, .pdf, .pgf, .pgm, .pict, .pict, .pictor,
.pixel, .png, .postscript, .ppm, .psd, .psp, .rad, .rgbe, .sgi, .svg, .swf, .tga, .tiff, .vml, .wbmp, .webp, .wmf, .x aml, .xar, .xar, .xbm, .xcf, .xpm

掲示板で画像を表示する方法がうまくいくかを試すには，テスト用掲示板を使ってください．こちらにだけ投稿して提出したつもりにならないようにしてください．
11/20(月)までに投稿された作品は11/22(水)の講義の際にコンテスト(相互評価)を開催します．

昨年度の作品

昨年度の作品が第1-4章まとめ課題にあります．

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

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