プログラム再構成に関する特許申請について

データ構造と
アルゴリズム
知能情報学部
新田直也
講義概要

私の研究室：


講義資料について:


13号館2階(13-206)
http://silverbullet.is.konan-u.ac.jp/lectures/
教科書:
近藤嘉雪:「Cプログラマのためのアルゴリズムとデータ構
造」, ソフトバンクパブリッシング

成績評価:

主に試験(1回)，演習(2回)で評価
講義計画
第1回アルゴリズムとは
第2回アルゴリズムと計算量
第3回基本データ構造
第4回連結リストとその操作(1)
第5回連結リストとその操作(2)
第6回演習
第7回二分木とその操作（1）
第8回二分木とその操作（2）
第9回二分木とその操作（3）
第10回演習
第11回線形探索
第12回二分探索
第13回二分探索木(1)
第14回二分探索木(2)
第15回試験
アルゴリズムとは？

直感的には，与えられた問題を解くための処理手順の
こと．

プログラミング言語に依存しない．
（コンピュータができる前からアルゴリズムの概念はあった．）

同一の問題に対して複数の解法が存在しうる．
→優れた解法，劣った解法?
解法1
問題A
解法2
解法3
最大公約数を求めるアルゴリズム

問題: 与えられた2自然数ａ, b の最大公約数を求めよ．

解法1: 総当り計算
1)
2)
3)

c := min{a, b} とおく．
c が a, b を共に割り切る場合, c を出力して停止．
c := c – 1 とおき，2) へ．
解法2: ユークリッドの互除法
1)
2)
3)
4)
c := max{a, b}, d := min{a, b} とおく．
c を d で割った余りを r とおく．
r が 0 ならば，d を出力して停止．
c := d, d := r とおき，2) へ．
計算の例

12と9の最大公約数を求めよ.
[総当り計算]
1)
2)
3)
2)
3)
2)
3)
2)
3)
2)
3)
2)
3)
2)
c := 9
割り切らない
c := 8
割り切らない
c:=7
割り切らない
c:=6
割り切らない
c:=5
割り切らない
c:=4
割り切らない
c:=3
割り切るので 3 を出力
[ユークリッドの互除法]
1)
2)
3)
4)
2)
3)
c := 12, d:= 9
r := 3
r は 0 でない
c := 9, d := 3
r := 0
r が 0 なので 3 を出力
入力(a, b)の値が大きくなればなるほど，
ユークリッドの互除法の方が総当り計算より
短いステップで答えを出す傾向が強くなる．
→時間計算量の議論は次週に
アルゴリズムと数学
数学の問題を解く手続きは，アルゴリズムである．
 割り算:




与えられた2整数 a, b について, ax = b を満たす x
を求めよ．
解法: 割り算の筆算
鶴亀算:


与えられた2整数 a, b について,
2x + 4y = a, x + y = b を満たす x, y を求めよ．
解法:

x := (4b – a) / 2 を計算，y := b – x とする．
アルゴリズムの数学的定義

数学的にアルゴリズムとは?


チャーチの提唱(1936年)
「チューリング計算可能関数，一般帰納的関数，λ定義
可能関数のクラスはすべて一致する．チューリングマシ
ンで記述可能な手続きをアルゴリズムと呼ぼう．」
チューリングマシン





アラン・チューリング(1936年)
「計算」を数学的にモデル化したマシン．
現在のコンピュータも理論的にはチューリングマシン．
チューリング賞はコンピュータ科学における最高権威．
暗号機械エニグマの解読に成功
チューリングマシン

有限状態制御部，半無限長のテープ，テープヘッドからなる
機械で，その動作は遷移関数によって定義される．
テープは加算無限個のセルの列で構成され，各セルには有限種類のテープ記号
(空白記号を含む)のうちのいずれか1つが記憶される．
b
d
a
a
α
c
b
a
c
…
テープヘッドは常にテープ上の1つのセルを指し，
1回の動作でセル1つ分右または左に移動する．
各動作によってテープヘッドの先のセルの内容が
読み書きされる．
有限状態制御部には有限種類の状態記号のうちのいずれか1つが記憶され，
動作の度に読み書きされる．状態記号のうちのいくつかは終了状態を表し，
終了状態になったときマシンは yes を出力し終了．
チューリングマシンの動作

遷移関数δは各マシン毎に定義される．
δ(α, a) = (β, c, L) であった場合:
b
d
a
a
c
α
β
c
b
a
c
…
チューリングマシンの例

チューリングマシンによる引き算



テープ記号: {1, -, =}
状態記号: {q0, q1, q2, q3}
遷移関数:
1
遷移前の
状態記号
q0
1
1
遷移前のテープ記号
-
=
q0
(q0,1,R) (q1,-,R)
(q3, ,L)
(q0, ,R)
q1
(q2, ,L)
(q3, ,L)
(q1, ,R)
q2
(q0, ,R)
5
1
終了状態
(q2,-,L)
2
1
1
-
1
q0 q1 q2
1
=
…
q3
(q2, ,L)
チューリングマシンの能力

本質的に，チューリングマシンによってあらゆる算術計算を
表現することができる(計算万能)．

チューリングマシン以外にも一般帰納関数，λ計算などの計
算機構が考えられたが，いずれもチューリングマシンと表現
能力が等しいことが証明された．

今のところチューリングマシンの能力を超える計算機構は見
つかっていない．
→チューリングマシンを計算手続き(アルゴリズム)
の定義とみなそう!!(チャーチの提唱)
チューリングマシンの限界

有限時間内で解くアルゴリズム(チューリングマシン)が存在
しない問題が存在する．




言い換えれば，その問題を解こうとすると無限時間かかってしまうよ
うな問題．
決定不能命題と呼ばれる．
ゲーデルの不完全性定理の別表現．
情報科学分野には決定不能命題がたくさんある．

与えられたチューリングマシンが与えられた入力に対していずれ停止
するか否か?(停止性判定問題)



与えられたプログラムが無限ループに入らないか否か?
与えられた2つのチューリングマシンが等価であるか否か?
解けないと証明されている問題に取り組んでも意味がない．
結局アルゴリズムとは?

理論的にはチューリングマシンで定義されるが，等価な計算
機構なら何でもよい．

チューリングマシンと等価な計算機構:






λ計算
一般帰納関数
DNA計算機
量子計算機
ランダムアクセス機械
プログラミング言語(ただしメモリは無尽蔵)
:

Download Report