データ構造と アルゴリズム 知能情報学部 新田直也.

Presentation on theme: "データ構造と アルゴリズム 知能情報学部 新田直也."— Presentation transcript:

1 データ構造と アルゴリズム 知能情報学部 新田直也

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

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

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