情報

Size: px

Start display at page:

Download "情報"

ちえここしの
4 years ago
Views:

1 アルゴリズム入門第 1 回 ~ ガイダンス数の計算 ~ 情報理工学系研究科創造情報学専攻中山英樹 1

2 教員について中山英樹大学院情報理工学系研究科創造情報学専攻専門 : コンピュータビジョン自然言語処理人工知能機械学習講義情報 ( スケジュール資料など ) 中山英樹東京大学で google ITC-LMS からもリンク張ってます 2

3 教科書情報科学入門増原英彦他著 Ruby を使って学ぶ正誤表 3

4 Lawrence Livermore National Laboratory 情報科学とは何か (C) Honda Motor Co., Ltd. 計算と情報の科学的基礎様々な分野に現われる情報を扱うための科学 cf. 数学は様々な分野の数理を物理は物質を扱うための科学生物の理解 : 個体細胞化学反応情報の流れロボット工学 : 機械制御ソフトウェア科目情報の土台部分情報系の学科で学ぶことの入り口 Christian Blouin 2006 (c National Research Council of Canada

5 情報教育の重点化イギリス 2014 年 9 月からプログラミング初等教育に正式科目として導入フィンランド 2016 年より小学校の科目として導入米国オバマ大統領 : 全ての米国人にプログラミングを学んで欲しい日本 (2014/6/24) 成長戦略 : 義務教育段階からの IT 教育 5

6 講義の目的前半 : プログラミングコンピュータに計算 (= 情報処理 ) をさせる手段後半 : 情報科学の基礎概念特にアルゴリズムと呼ばれる領域を中心にプログラミングそのものは主目的でない前提知識夏学期情報 6

7 プログラミング言語 Ruby 比較的新しい言語で初学者のしきいが低い選択に深い意味はない米国の大学だったら Python だったかも日本発で世界的に使われている言語 ( これ大事 ) 開発者の多くが日本人である ( これ大事 ) 7

8 アルゴリズム問題の解き方有限時間で答が出ることが保証されているもの一つの問題に複数のアルゴリズムアルゴリズムによって計算時間が劇的に違う異なる問題に同じアルゴリズム本質的に同じ構造の問題なら使いまわしができる? 8

9 異なる問題同じアルゴリズム日米間には沢山のネットワーク経路がある各経路には帯域幅がある日米間全体の最大帯域幅は? 注 : 単純な和でない

10 異なる問題同じアルゴリズム生産割当問題車種別の必要台数工場別の生産台数の上限どの工場でどの車種を作れるか? X 40 X 30 X X 10

11 成績評価共通試験 50%: 平常点 50% 平常点毎週出題の課題 ( 毎回講義時間の後半は課題の時間 ) 半分終わったところで多めの課題 (11/10の予定) ちゃんと授業に出ていれば単位はとれます優は 3 割相対評価 11

12 毎週の課題自分で手を動かして考えることが大事 ( テストではない ) 友達と相談したり TA に質問してもよいただしコピペはダメ ( 全員 0 点にします ) 出席は別途講義時間中に毎回とります課題がどうしてもできなかった場合の救済ただし出席のみで課題を提出しないのはダメ考えてみたところまでを書いて出してください自信のある人向けに +α の課題を出すことがあります提出は任意ですが提出があった場合は加点します難しいけど授業で扱った範囲の知識で解ける ( はず ) 12

13 ITC-LMS ITC-LMS の利用登録ウェブブラウザ (Safariなど) からアルゴリズム入門( 金 1) 中山英樹を選択する出席課題の提出アンケート ( 無記名 ): 質問感想

14 もう 1 つターミナルのウインドウを開くコンピュータとの対話ターミナルの起動 irb の起動数式の入力ターミナルのプロンプト irb のプロンプト irb の返答 cm12345$ irb 改行 irb(main):001:0> 1+1 改行 => 2 irb(main):002:0> コントロール D cm12345$ 入力は赤で示す改行は Return, Enter とも今回は指示されるまで irb を使いながら

15 数式の計算電卓がわり以下改行は省略 irb(main):003:0> 7 2 => 5 irb(main):004:0> 7 * 2 => 14 irb(main):005:0> 7 / 2 => 3 irb(main):006:0> 7 % 2 => 1 irb(main):007:0> 7 ** 2 => 49 7 の 2 乗 irb(main):009:0> 7-2 * 3 => 1 irb(main):010:0> (7-2) * 3 => 15 irb(main):012:0> 7.0 / 2 => 3.5 irb(main):013:0> 7 / 2.0 => を 2 で割った余り

16 整数と浮動小数点数 Ruby ( 他の言語も ) は区別する整数と整数の演算は答も整数整数と小数の演算は答も小数 3 は整数 3.0 は小数 16

17 さまざまなエラー irb(main):001:0> 3/0 ZeroDivisionError: divided by 0 from (irb):1:in `/' from (irb):1 irb(main):002:0> SyntaxError: compile error (irb):2: syntax error, unexpected tinteger, expecting $end from (irb):2 irb(main):003:0> (7 - irb(main):004:1* 2) * 3) SyntaxError: compile error 式の途中で改行するとプロンプトが異なる (irb):4: syntax error, unexpected ')', expecting $end from (irb):4 irb(main):005:0>

18 わけがわからなくなったらともかくコントロール C を押す irb はトップレベルに戻る

19 クイズ : 17-17/3*3 の値は? 1: 0.0 2: 0 3: 2 4: : 16 irb を使わずに答えよう!

20 数学関数数学関数を使う準備 irb を起動し直すたびに必要 irb(main):003:0> include(math) => Object irb(main):004:0> sqrt(2) => irb(main):005:0> cos( /3) =>

21 変数値に名前を付ける変数への値の代入 irb(main):003:0> h=188.0 => irb(main):004:0> w=104.0 => irb(main):006:0> w / (h / 100.0) ** 2 =>

22 変数を使うわけ式の意味が理解しやすくなる w weight body_weight_in_pound 小文字で始まることアンダースコアは小文字と考える違う値で計算のやり直しができる irb(main):008:0> w= => 94.0 キーで入力が復活! irb(main):009:0> w / (h/100.0) ** 2 =>

23 関数の定義 BMI を求める関数 irb(main):003:0> def bmi(height, weight) irb(main):004:1> weight / (height/100.0) ** 2 irb(main):005:1> => nil end irb(main):007:0> bmi(188.0, 104.0) => irb(main):008:0> 1.1*bmi(174.0, * 0.454) => スペースキーを押してインデントを入れるとよい ( 見やすくする )

24 書き方になれる数学なら BMI 関数 f(h, w) = w / (h / 100) 2 Ruby なら def f(h, w) w / (h / 100.0) ** 2 end こっちがベター def bmi(height, weight) weight / (height / 100.0) ** 2 end 24

25 練習 1. 平面上の 2 点 (x, y) と (u, v) の距離を求める distance(x,y,u,v). 2. f フィート i インチをセンチメートルに変換する feet_to_cm(f,i). ただし 1 フィート = 12 インチ = cm である

26 解答 def distance(x, y, u, v) sqrt((x-u)*(x-u) + (y-v)*(y-v)) end # sqrt((x-u)**2+(y-v)**2) def feet_to_cm(f, i) end 30.48*f /12*I # (f + i/12.0)*30.48

27 # 以下行末までコメントファイルに保存した関数定義ファイルからの読み込み # BMI of a person with height (cm) and weight (kg) def bmi(height, weight ) end weight / ( height / 100.0) ** 2 Emacs を使おうホームディレクトリへ保存せよ! 一度 irb を終了し再起動してから bmi.rb irb(main):003:0> load("./bmi.rb") => true irb(main):005:0> bmi(188.0, 104.0) =>

28 速修 Emacs 新しくファイルを作る E アイコンをクリックメニュー File Visit New File 出てきたウィンドウに bmi.rb ( 場所 : ホームディレクトリ ) 関数定義を入力メニュー File Save 前に作ったファイルの編集ファイルを E アイコンへドラッグ & ドロップ # BMI of a person with height (cm) and weight (kg) def bmi(height, weight ) end weight / ( height /100.0) ** 2

29 課題の提出 ITC-LMS で提出すること提出様式問題ごとに ( 学籍番号 )q.txt ( 例 q1.txt) Ruby プログラムファイルの場合は.rb のように名前を付ける一つの問題で複数のファイルの提出が必要な場合 ( 学籍番号 )q.zip のように一つの zip ファイルにまとめて提出〆切は次回の講義開始まで (10 月 6 日 8:29) 29

30 本日の課題 ( 問題 1) 東京大学と米 Stanford University の学部学生 (undergraduate student) の年間授業料 (tuition) を調べ irb を使って金額の大小を比較せよ ( 電卓として使えばよい ) 解答にあたってはそれぞれの金額 ( 東大は日本円 Stanford 大は米ドル ) を示しまた換算に用いた円ドル為替レートも示せさらに換算のために irb に入力したコマンドも示せプログラム ( 関数 ) になっている必要はない 30

31 本日の課題 ( 問題 2) 2 次方程式 ax^2 + bx + c = 0 の解をひとつ計算する関数 quadratic(a,b,c) を定義するプログラムを書けただし a がゼロの場合や解が存在しない場合は考えなくてよい (x^2 は x の二乗を意味する ) 31

32 注意かけ算記号は省略できない a*c は ac とは書けない ac という別の変数の意味になる 2a という変数は定義できない (Ruby のルール ) include(math) を忘れずにプログラムを実行する前に読み込んでおくことが必要 (irb を再起動すると忘れてしまう ) あるいはファイルの先頭に書いておく 32

数の計算と関数

数の計算と関数はじめに情報科学とは何か情報に関する科学的な基礎様々な分野に現われる情報を扱うための科学 cf. 数学は様々な分野の数理を物理は物を扱うための科学生物の理解 : 個体分子情報ロボット工学 : 機械制御ソフトウェア科目情報の土台部分情報系の学科で学ぶことの入り口授業形式評価クラス指定講義 (2/3) + 演習 (1/3) 講義はスライド板書を用いる