12/5 データの検索(2)

前回の補足

今回は代理TAで朱捍華さんが入ります．
第7章のスライド, NoteBookで
```
def comb(i, j): # iCjを求めるプログラム
  return factorial(i) // factorial(j) // factorial(i - j)
```
となっていたのを，
```
def comb(i, j): # iCjを求めるプログラム
  return factorial(i) / factorial(j) / factorial(i - j)
```
に修正します．「//」を使うとPythonのバージョンによっては，128ビット表現の数が使われずに64ビット表現に変換されてしまうことがあったようです．
演習室内は飲食禁止です．ペットボトル等を持ち込む場合も，バッグの中にしまってください．ただし，医療目的でののど飴の使用は許可します．
10/24, 31, 11/7, 12/19, 1/9は3限に講義が入っているので，3限終了後に入室してください

前回の感想，質問より

Q.: パソコン修理に出しててvote.pyの投票できてません
A.: vote.py は教育用計算機システムのMac環境からしか実行できないので，持ち込みPCで参加している場合でも，投票は教育用計算機システムのMac環境からおこなってください．
Q.: 標準テキストの第8章の練習問題を解きました。 > 練習問題8.5は計算量O(mlogn)のプログラムを作成せよ、となっていますが、私はO(mn)程度の計算量のプログラムしか書けませんでした。
A.: 標準テキストで想定した解法はおそらく提出されたものと同じものだと思いますが，O(m log n) という記述が間違っているようですね．標準テキストの修正が必要なので問いあわせてみます．

前回の課題について

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

多くの人が calc_dice20 に取り組みました．典型的な解は以下のようになります．

def calc_dice20(n):
  s = 0
  for i in range(0, n):
    v = 0
    for j in range(0, 5):
      v = v + random.randint(1, 6)
    if v <= 20:
      s = s + 1
  return s / n

モンテカルロ法を使わずに正解を得られるプログラムを提出した人もいました．
掲示板への書き込みの際にインデント(字下げ)の大きさが変わってしまったと思われるプログラムもありました．Python言語ではインデントが重要なので気をつけてください．

講義資料

教科書の代わりになる，「標準テキスト」がITC-LMSに登録後に「教材」からダウンロード可能です．他の人への再配布は禁止します．
講義スライドはITC-LMSで「教材」を選択するとPDFファイルをダウンロードできます(講義が進むに連れて追加されます)．PDFファイルからプログラムをコピー & ペーストすると動かないことがあります。

講義フォルダの作成

講義に関連したファイルはホームフォルダ直下に置くのではなく，講義専用のフォルダをalgo18 という名前で作成してください．ターミナルでフォルダを作るには，
```
mkdir ~/algo18
```
のようにします．そして，ターミナルを開くたびに
```
cd ~/algo18
jupyter notebook
```
と入力してJupyter Notebookを動かしてください．詳しくは，はいぱーワークブック「14.4 コマンドを使ったファイル操作」を参照してください．
Finderのサイドバーに自分のホームフォルダ「共通IDの数字10桁」が表示されていないと作成したフォルダがアクセスしにくいかもしれません．このときは，Finderのメニューの「Finder」->「環境設定」->「サイドバー」を選び，よく使う項目の中で家のアイコンが描かれた「共通IDの数字10桁」のチェックボックスにチェックを入れてください．

投票システム

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

cd ~/algo18

を済ませてから，

python vote.py 選択肢番号

のように使います．

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

テキストの補足

ターミナルでは，メニューバーから，「シェル」->「新規ウィンドウ」あるいは，「コマンドキー(⌘)」+「N」で新たなターミナルウィンドウを開くことができます．

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

ターミナルを開くたびに
```
cd ~/algo18
```
と入力してください．これらの機能を使うと，Jupyter Notebookを抜けずにvoteできます．
ターミナルの基本的な使い方は，はいぱーワークブックの15.2 ターミナルの基本的な使い方を，より高度な使い方は，15.4 ターミナルの便利な使い方を参照してください．
cdというコマンドと「~」の意味は，はいぱーワークブックの14.4 コマンドを使ったファイル操作の14.4.1 ディレクトリを読むと分かります．

Notebook教材

以下のNotebook教材は，~/algo18 以下にダウンロードして，Jupyter Notebookからopenして使ったり， Google Colaboratoryを使って，クラウド実行環境でPythonプログラムを実行できます．ダウンロードする場合もGoogle Colaboratoryの使い方を参照してください．Googleアカウントへのログインを求められたときは，通常のGoogleアカウント「XXX@gmail.com」ではなく，ECCSクラウドメールのアカウント「XXX@g.ecc.u-tokyo.ac.jp」を使ってログインしてください．

今日の課題

講義中に投票を求められるので，投票システムを使って投票をする．
ITC-LMSの掲示板「12/5の課題，質問」(講義の時間中に閲覧可能になる)に以下のことを書き込む(なるべく講義時間中に，それ以降は試験当日まで受け付け)．
- スライド中の練習，あるいは標準テキストの第8章の練習問題のどれかを解いて回答する．
- あとから別の問題を解いた人は後から付け加えても良い．