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

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自然数 ａ, 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計算機 量子計算機 ランダムアクセス機械 プログラミング言語(ただしメモリは無尽蔵) :