全 学 共 通 科 目 工 学 部 専 門 科 目 計 算 機 科 学 概 論 アルゴリズムとプログラミング その3 五 十 嵐 淳 igarashi@kuis.kyoto-u.ac.jp 大 学 院 情 報 学 研 究 科 通 信 情 報 システム 専 攻
担 当 分 のメニュー 6/21, 6/28: アルゴリズムについて 7/5: 出 張 につき 休 講 7/12, 7/19: プログラミングについて ( 補 講 の 予 定 内 容 は 未 定 です) 講 義 情 報 http://www.fos.kuis.kyotou.ac.jp/~igarashi/class/cs-intro/
今 日 のメニュー 前 回 の 積 み 残 し アルゴリズムの 正 しさ プログラムとプログラミング 言 語 JavaScript プログラミング 入 門 とにかく 動 かしてみよう
アルゴリズムの 正 しさ アルゴリズムが 任 意 の 入 力 に 対 し 停 止 するか? アルゴリズムがその 目 的 を 任 意 の 入 力 に 対 して 果 たすか? マージソート クイックソートは 本 当 に 整 列 するの か? 互 除 法 はいつでも 止 まるのか? 本 当 に 求 まったの は 最 大 公 約 数 なのか?
ユークリッドの 互 除 法 入 力 : 自 然 数 n, m (ただし n m) 1. k を n m の 余 りとする 2. k について 場 合 分 け k = 0 m を 出 力 として 終 了 k 0 m, k を 入 力 として 互 除 法 を 行 いその 出 力 をそのまま 出 力 とする 再 帰 (recursion)
互 除 法 の 正 しさの 証 明 (1/2) 以 下 のふたつは 同 値 相 異 なる 自 然 数 m, n の GCD が g である 互 いに 素 な 自 然 数 a, b が 存 在 し m = ga かつ n = gb
互 除 法 の 正 しさの 証 明 (2/2) m n の 余 りは a b の 余 り c の g 倍 しかも b と c は 互 いに 素 つまり GCD は g 入 力 の GCD が 再 帰 を 越 えて 保 存 される プラス 入 力 の 和 は 再 帰 の 度 に 減 っていく より 厳 密 な 証 明 には 数 学 的 帰 納 法 を 使 う
数 学 的 帰 納 法 任 意 の 自 然 数 n について P(n) を 示 したければ 以 下 のふたつを 示 せばよい P(0) P(k) ならば P(k+1) ( 任 意 の k について) P(k) を 帰 納 法 の 仮 定 と 呼 ぶ ひとつ 小 さい 数 については 今 示 そうとしている P が 成 立 することを 使 ってよい
任 意 の n に 対 し 1からnまでの 和 = n(n-1)/2 の 証 明 P(0): 1から0までの 和 = 0(0-1)/2 P(k) を 仮 定 して P(k+1) を 示 す 1 から k+1 までの 和 = 1 から k までの 和 + (k+1) (P(k) より) = k(k-1)/2 + (k+1) = (k+1)k/2
数 学 的 帰 納 法 のバリエーション ( 累 積 帰 納 法 ) 任 意 の 自 然 数 n について P(n) を 示 したければ 以 下 を 示 せばよい P(0) かつ P(1) かつ... かつP(k) ならば P(k+1) ( 任 意 の k について) k 以 下 については P が 成 立 しているとしてよい
累 積 帰 納 法 を 使 った 互 除 法 の 正 しさの 証 明 任 意 の n, m, k について n = m + k ならば m, k を 入 力 とした 互 除 法 の 出 力 は m, k の GCD ( 証 明 ) 累 積 帰 納 法 による m k の 場 合 を 示 す m k の 余 り j について 場 合 わけ: (1) j=0の 場 合 出 力 k は 確 かに m, k のGCD (2) j>0の 場 合 帰 納 法 の 仮 定 P(k+j) より k, j を 入 力 とした 互 除 法 の 出 力 は k, j の GCD 先 般 の 議 論 より k, j のGCD = m, k のGCD m < k の 場 合 も 同 様 ( 証 明 了 )
今 日 のメニュー 前 回 の 積 み 残 し アルゴリズムの 正 しさ プログラムとプログラミング 言 語 JavaScript プログラミング 入 門 とにかく 動 かしてみよう
プログラム コンピュータへの 命 令 書 機 械 語 プログラム バイナリ(binary)プログラム ビット 列 としてメモリに 格 納 され ハードウェアの 動 作 を 制 御 する ふつうはプログラミング 言 語 (プログラムを 書 くための 人 工 言 語 )で 書 かれる アセンブリ 言 語 高 水 準 言 語 言 語 なので 文 法 意 味 がある!
アセンブリ 言 語 機 械 語 命 令 に 人 間 が 理 解 しやすい 名 前 をつけたもの 01001000 を ADD X, Y と 呼 ぶ などなど ADD X, Y から 01001000 に 戻 す( 簡 単 な) 翻 訳 が 必 要 アセンブラ
高 水 準 プログラミング 言 語 より 人 間 よりの 表 記 でコンピュータへの 指 示 を 記 述 X + Y - Z など 演 算 が 入 れ 子 になった 式 が 使 える 整 数 文 字 などのデータの 種 類 の 区 別 処 理 のまとまりに 名 前 をつけて まとまりとして 使 うこ とができる など 機 械 語 への 翻 訳 が 大 変 ソースプログラムとターゲットプログラム ハードウェアの 差 異 を 吸 収 できる(プログラム 再 利 用 )
歴 史 に 名 を 残 した 高 水 準 言 語 (ごく 一 部 ) FORTRAN (1954) 数 値 計 算 への 応 用 Lisp (1958) 記 号 処 理 への 応 用 COBOL (1959) 事 務 処 理 への 応 用 ALGOL (1958) アルゴリズム 記 述 用 Simula (1954) シミュレーション 記 述 オブジェクト 指 向 Prolog (1970) 人 工 知 能 への 応 用 論 理 プログラミング C (1971) オペレーティングシステム 記 述 Smalltalk (1971) オブジェクト 指 向 ML (1973) 証 明 戦 略 記 述 関 数 プログラミング
高 水 準 プログラムの 実 行 方 式 インタプリタ( 解 釈 実 行 系 )による 実 行 高 水 準 プログラムを 読 み 込 みながらその 意 味 通 り 実 行 す るプログラム 同 時 通 訳 のようなもの? コンパイラによる 実 行 高 水 準 プログラムを 予 め 機 械 語 プログラムに 翻 訳 翻 訳 書 のようなもの? ふたつの 方 式 のハイブリッド: 中 間 水 準 言 語 に 翻 訳 して 解 釈 実 行 解 釈 実 行 しつつ 何 度 も 実 行 する 重 要 箇 所 はコンパイル
本 講 義 でふれるプログラミング 言 語 JavaScript OCaml ( 予 定 ) Prolog ( 予 定 )
今 日 のメニュー 前 回 の 積 み 残 し アルゴリズムの 正 しさ プログラムとプログラミング 言 語 JavaScript プログラミング 入 門 とにかく 動 かしてみよう
JavaScript ウェブページで たのしいこと をする 用 途 で 発 明 当 初 は 誰 も 大 規 模 なプログラムを 書 かない おも ちゃ 言 語 と 認 識 されていた Google が GMail を 発 表 して 皆 腰 をぬかした 多 くのウェブブラウザで 動 く ただしブラウザ 毎 に 少 しずつ 動 作 が 違 う ;-( (Java 言 語 とはほとんど 関 係 ない)
講 義 中 に 見 せるプログラムについて 講 義 ホームページで 該 当 するリンクをクリックすると プログラムが 動 く ブラウザの ページのソースを 見 る で 閲 覧 ページを 保 存 すれば 保 存 編 集 も 可 能 編 集 したファイルは 開 く で 読 み 込 める
プログラムその1 機 能 : ペ ー ジ を 読 み 込 む と メ ッ セ ー ジ Hello, world を 確 認 ダイアログボックスに 表 示 (web ページ 自 体 は 空 っぽ)
ページのソース <html> <body> <script> alert("hello, world"); </script> </body> </html> JavaScript プログラムはHTML 中 の <script> </script> に 埋 め 込 まれている
ウェブブラウザの 動 作 HTML 部 分 を 表 示 <script> </script> 部 ( 複 数 あってもよい)を 前 か ら 順 に JavaScript プログラムとして 実 行
プログラム 大 解 剖 alert( Hello, world ); JS プログラム = 文 (statement)の 列 文 は(たいてい)セミコロンで 終 わる これは ひとつの 文 からなるプログラム 文 の 種 類 もいろいろある これは 手 続 き 呼 出 文 : 手 続 名 ( 式 ); 手 続 alertの 機 能 括 弧 内 に 書 かれた 式 の 値 を 確 認 ダイアログボックスに 表 示 し OK が 押 されるの を 待 つ
文 と 式 文 : コンピュータへの 命 令 となる 構 文 単 位 式 (expression): 計 算 をして 値 (value)を 得 るため の 構 文 単 位 整 数 定 数 (..., -1, 0, 1, 2,...)や 文 字 列 定 数 Hello, world は 式 ( 複 数 の) 式 を 演 算 子 で 組 み 合 わせたもの 1 + 4
プログラムその2 機 能 : キーボードから 名 前 の 入 力 を 促 し 入 力 され た 名 前 の 人 に 挨 拶 をする var username = prompt("what's your name?"); alert("hello, " + username);
変 数 宣 言 初 期 化 文 var 変 数 の 名 前 = 式 ; 変 数 値 をしまっておくための 箱 言 語 によっては 値 につける 名 前 という 考 え 方 も 変 数 宣 言 文 新 しい 変 数 を 用 意 する 初 期 化 式 の 値 を 箱 に 入 れる JS では 初 期 化 ( 等 号 以 下 の 部 分 )は 省 略 可 変 数 参 照 変 数 の 中 身 の 値 の 取 り 出 し ( 多 くの 言 語 では) 宣 言 せずに 参 照 してはいけない
関 数 呼 出 式 関 数 名 ( 式 ) 関 数 prompt の 機 能 式 の 値 をダイアログボッ クスに 表 示 し 入 力 を 待 つ 入 力 された 文 字 列 を 式 全 体 の 値 とする 入 力 された 文 字 列 を 返 す(return) ともいう
演 算 子 + 加 算 式 1+1 の 値 は 2 文 字 列 の 連 結 式 Hello, + Igarashi の 値 は Hello, Igarashi 整 数 と 文 字 列 を 足 し たら? ( Hello, + 2) JSでは: Hello,2 言 語 によってはエラーになる 実 行 時 エラー or 実 行 前 エラー
プログラムのフォーマットについて 空 白 文 字 と 改 行 は 区 別 されない ただし 全 角 空 白 は 使 ってはいけない 英 文 字 の 並 びの 間 ときには 記 号 間 の 空 白 の 有 無 は 重 要 var と username の 間 の 空 白 は 重 要 個 数 はどうでもよい 行 頭 の 空 白 ( 字 下 げ インデント)は 読 みやすさのため // から 行 末 まではコメントと 呼 ばれプログラムの 実 行 には 影 響 しない
プログラム その3 機 能 : キーボードからふたつの 数 を 入 力 させ その 平 均 を 表 示 する function average(x, y) { return (x + y) / 2; } var a = Number(prompt(...)); var b = Number(prompt(...)); var c = average(a, b); alert("the average is " + c);
関 数 手 続 き 定 義 文 の 並 び 式 に 名 前 をつける function 名 前 ( 変 数 列 ) { 文 の 並 び } 呼 び 出 し 側 から 渡 される 情 報 ( 引 数 (ひきすう))を 格 納 する 変 数 の 宣 言 alert などと 同 様 に 呼 び 出 せる return 文 (return 式 ;)で 式 の 値 を 呼 び 出 し 元 に 返 す ( 訂 正 : プログラム = 文 と 関 数 定 義 の 列 )
その 他 除 算 演 算 子 / 文 字 列 を 数 値 に 変 換 する Number 関 数
プログラムその4 機 能 : キーボードからふたつの 数 を 入 力 させ その 最 大 公 約 数 を 表 示 する 最 大 公 約 数 を 計 算 する 関 数 の 定 義 % は 余 りを 計 算 する 演 算 子 function gcd(x, y) { var z = x % y; return (z==0)? y : gcd(y, z); }
条 件 分 岐 式 と 比 較 演 算 子 条 件 分 岐 式 式 1? 式 2 : 式 3 式 1 (の 値 )の 真 偽 で 場 合 分 け 真 なら 式 2 の 値 偽 であれば 式 3 の 値 が 式 全 体 の 値 比 較 演 算 子 ( 値 が 真 偽 になるような 式 を 構 成 する) == 両 辺 が 等 しい!= 両 辺 が 等 しくない < より 小 さい > より 大 きい <= 以 下 >= 以 上
ちょっと 脱 線 : 条 件 文 が 真 なら をする 偽 なら をする という 文 レベ ルでの 条 件 分 岐 もできる if ( 式 ) { 文 の 並 び } else { 文 の 並 び } セミコロンで 終 わらない 文 なので 注 意 return (z==0)? y : gcd(y,z); は if (z==0) { return y; } else { return gcd(y,z); } でもOK
ユークリッドの 互 除 法 入 力 : 自 然 数 n, m (ただし n m) 1. k を n m の 余 りとする 2. k について 場 合 分 け k = 0 m を 出 力 として 終 了 k 0 m, k を 入 力 として 互 除 法 を 行 いその 出 力 をそのまま 出 力 とする 再 帰 (recursion)
プログラムその5 機 能 : キーボードからふたつの 数 を 入 力 させ その 最 大 公 約 数 を 表 示 する var x = Math.max(m, n); var y = Math.min(m, n); var z = x % y; while (z!= 0) { x = y; y = z; z = x % y; }
繰 り 返 し 構 文 while while ( 式 ) { 文 の 並 び } 式 が 真 である 限 り 文 の 並 び を 繰 り 返 し 実 行 する 式 が 偽 なら 何 もしない
代 入 文 : 名 前 = 式 ; 変 数 の( 箱 の) 中 身 を 更 新 する ( 初 期 化 を 伴 う) 変 数 宣 言 文 との 違 いに 注 意 while (z!= 0) { } // この 時 点 での y, z を // それぞれ 新 たな x, y とする x = y; y = z; z = x % y;
ここまでのまとめ JS プログラム = 関 数 手 続 き 定 義 と 文 の 列 文 命 令 の 単 位 式 値 を 計 算 するひとまとまり いろいろな 値 の 種 類 ( 数 値 文 字 列 真 偽 値 ) 変 数 ( 式 の) 値 を 格 納 する 箱 宣 言 初 期 化 参 照 代 入 関 数 手 続 定 義 ひとまとめの 処 理 に 名 前 をつける 条 件 判 断 と 繰 り 返 し