Presentation is loading. Please wait.

Presentation is loading. Please wait.

データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.

Similar presentations


Presentation on theme: "データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也."— Presentation transcript:

1 データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也

2 講義概要 私の研究室: 13号館2階(13-206) 講義資料について: 教科書: 近藤嘉雪:「Cプログラマのためのアルゴリズムとデータ構造」, ソフトバンクパブリッシング 成績評価: 主に試験(1回),演習(2回)で評価

3 講義計画 第1回 (4/11) アルゴリズムとは 第2回 (4/18) アルゴリズムと計算量 第3回 (4/25) 基本データ構造
第4回 (5/2) 連結リストとその操作(1) 第5回 (5/9) 連結リストとその操作(2) 第6回 (5/16) 演習 第7回 (5/23) 二分木とその操作(1) 第8回 (5/30) 二分木とその操作(2) 第9回 (6/6) 二分木とその操作(3) 第10回 (6/13) 演習 第11回 (6/20) 線形探索 第12回 (6/27) 二分探索 第13回 (7/4) 二分探索木(1) 第14回 (7/11) 二分探索木(2) 第15回 (7/18) 試験

4 アルゴリズムとは? 直感的には,与えられた問題を解くための処理手順のこと.
プログラミング言語に依存しない. (コンピュータができる前からアルゴリズムの概念はあった.) 同一の問題に対して複数の解法が存在しうる. →優れた解法,劣った解法? 解法1 問題A 解法2 解法3

5 最大公約数を求めるアルゴリズム 問題: 与えられた2自然数 a, b の最大公約数を求めよ. 解法1: 総当り計算
c := min{a, b} とおく. c が a, b を共に割り切る場合, c を出力して停止. c := c – 1 とおき,2) へ. 解法2: ユークリッドの互除法 c := max{a, b}, d := min{a, b} とおく. c を d で割った余りを r とおく. r が 0 ならば,d を出力して停止. c := d, d := r とおき,2) へ.

6 計算の例 12と9の最大公約数を求めよ. [総当り計算] [ユークリッドの互除法] c := 9 割り切らない c := 8
2) 割り切らない 3) c : = 7 3) c : = 6 3) c : = 5 3) c : = 4 3) c : = 3 2) 割り切るので 3 を出力 [ユークリッドの互除法] c := 12, d:= 9 r := 3 r は 0 でない 4) c := 9, d := 3 2) r := 0 3) r が 0 なので 3 を出力 入力(a, b)の値が大きくなればなるほど, ユークリッドの互除法の方が総当り計算より 短いステップで答えを出す傾向が強くなる. →時間計算量の議論は次週に

7 アルゴリズムと数学 数学の問題を解く手続きは,アルゴリズムである. 割り算: 鶴亀算:
与えられた2整数 a, b について, ax = b を満たす x を求めよ. 解法: 割り算の筆算 鶴亀算: 与えられた2整数 a, b について, 2x + 4y = a, x + y = b を満たす x, y を求めよ. 解法: x := (4b – a) / 2 を計算,y := b – x とする.

8 アルゴリズムの数学的定義 数学的にアルゴリズムとは? チューリングマシン
チャーチの提唱(1936年) 「チューリング計算可能関数,一般帰納的関数,λ定義可能関数のクラスはすべて一致する.チューリングマシンで記述可能な手続きをアルゴリズムと呼ぼう.」 チューリングマシン アラン・チューリング(1936年) 「計算」を数学的にモデル化したマシン. 現在のコンピュータも理論的にはチューリングマシン. チューリング賞はコンピュータ科学における最高権威. 暗号機械エニグマの解読に成功

9 チューリングマシン 有限状態制御部,半無限長のテープ,テープヘッドからなる機械で,その動作は遷移関数によって定義される.
テープは加算無限個のセルの列で構成され,各セルには有限種類のテープ記号 (空白記号を含む)のうちのいずれか1つが記憶される. b d a a c b a c テープヘッドは常にテープ上の1つのセルを指し, 1回の動作でセル1つ分右または左に移動する. 各動作によってテープヘッドの先のセルの内容が 読み書きされる. α 有限状態制御部には有限種類の状態記号のうちのいずれか1つが記憶され, 動作の度に読み書きされる.状態記号のうちのいくつかは終了状態を表し, 終了状態になったときマシンは yes を出力し終了.

10 チューリングマシンの動作 遷移関数δは各マシン毎に定義される. δ(α, a) = (β, c, L) であった場合: b d a a c
β α

11 チューリングマシンの例 チューリングマシンによる引き算 テープ記号: {1, -, =} 状態記号: {q0, q1, q2, q3}
遷移関数: 終了状態 遷移前のテープ記号 1 - = q0 (q0,1,R) (q1,-,R) (q3, ,L) (q0, ,R) q1 (q2, ,L) (q1, ,R) q2 (q2,-,L) 遷移前の状態記号 5 2 1 1 1 1 1 - 1 1 = q0 q0 q1 q2 q3

12 チューリングマシンの能力 本質的に,チューリングマシンによってあらゆる算術計算を表現することができる(計算万能).
チューリングマシン以外にも一般帰納関数,λ計算などの計算機構が考えられたが,いずれもチューリングマシンと表現能力が等しいことが証明された. 今のところチューリングマシンの能力を超える計算機構は見つかっていない. →チューリングマシンを計算手続き(アルゴリズム) の定義とみなそう!!(チャーチの提唱)

13 チューリングマシンの限界 有限時間内で解くアルゴリズム(チューリングマシン)が存在しない問題が存在する.
言い換えれば,その問題を解こうとすると無限時間かかってしまうような問題. 決定不能命題と呼ばれる. ゲーデルの不完全性定理の別表現. 情報科学分野には決定不能命題がたくさんある. 与えられたチューリングマシンが与えられた入力に対していずれ停止するか否か?(停止性判定問題) 与えられたプログラムが無限ループに入らないか否か? 与えられた2つのチューリングマシンが等価であるか否か? 解けないと証明されている問題に取り組んでも意味がない.

14 結局アルゴリズムとは? 理論的にはチューリングマシンで定義されるが,等価な計算機構なら何でもよい. チューリングマシンと等価な計算機構:
λ計算 一般帰納関数 DNA計算機 量子計算機 ランダムアクセス機械 プログラミング言語(ただしメモリは無尽蔵) :


Download ppt "データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也."

Similar presentations


Ads by Google