この章のねらい

第６章のねらい
• モデルの記述（第4章）
• モデル上の操作による計算とプログラム（第5
章）
• 本章
– アルゴリズム：計算手順
• よいアルゴリズムとよくないアルゴリズムがある
– 計算のモデル化
• 有限状態機械，チューリング機械
– 計算量と計算可能性
ハノイの塔問題
• 円盤の山を左から中央に移すのにかかる時
間は?
– n: 円盤の枚数
– 1枚動かすのに10-9秒かかるとする (cf. 1GHz)
– n=100のときにかかる時間は?
A: 約5ミリ秒
B: 約50秒
C: 約50億年
D: 約50兆年
– ヒント: n=20のとき約1ミリ秒
コンピュータによる問題解決: 実際
• 問題解決の手順
現
問実
題世
界
の
モ
さ
問デ
題れル
た化
モ人
デ間
ル
化が
人
間
が
考
察
ア
ル
ゴ
リ
ズ
ムプ
ロ
グ人
ラ間
ミが
ン
グ
プ
ロ
グ
ラ
ム
答
コ
ン
実ピ
行ュ
ー
タ
が
アルゴリズムの重要性
• 性能に大きな違いが出る
– 同じ問題を解く複数のアルゴリズムがある
– アルゴリズムによって計算時間が桁違いに変わ
ることがある
• 類型化されている
– 全く違う問題を解くアルゴリズムが同じものになる
ことがある
– 性能に関する考察・プログラミングを共通化でき
る
問題: 平方根の計算
• x を求める
• 注意:
– 小数の計算は有限の精度で行われる
– →近似値しか求められない
• 問題:
– ある正の実数 x が与えられたときに、2乗すると
x に近くなる正の実数 y を精度 d で求める．
– つまり， | x  y | d となるような y を 1 つ求め
る
平方根のアルゴリズム: 反復法
• x = 90, d = 1 の場合を考える
• 「y = 0, 1, 2, 3, ... を順に検討してゆき
(y+d)2 が 90 より大きくなったら、
アルゴリズム1
その1つ前が解」
(反復による
平方根の計算)
• 実際の動作 x =2, d =0.0001 の場合、
平方根のアルゴリズム: 二分法
• アルゴリズム2 (二分法による平方根の計算)
x の平方根を精度 d で求める (ただし x > 1):
>
平方根のアルゴリズム: 二分法の
実際
• 「区間の幅」が1/2ずつ減ってゆく
アルゴリズムの速度
• 反復法: 約
• 二分法:
x
d 回
– 1回繰り返すごとに区間の幅が1/2になる
x n
– n回繰り返し後の区間の幅は 2
– これが d 以下になるのに要する回数
x
→ 約 log 2 d 回
• 比較: x=2, d=0.0000000001 のとき
– 反復法: 約141億回
– 二分法: 35回
小数点以下
10桁まで求める
計算量の考え方
• 重要: 計算時間の見積り
– 「天気予報」の計算に3日かかっては困る
– 「百年後に答が出る」は解けないのと同じこと
– アルゴリズムによって計算時間が大きく違う
• 計算量とは
– 対象: アルゴリズムの計算時間
• コンピュータ性能の違いやプログラムの作り方を無視
– 「問題の大きさ」に対する関係のおおまかな見積
り
計算量の見積り方
• 問題の大きさを変数で表わし、
– 例: n個のデータを処理する
• 計算の回数を式で表わす
– 例: 3n+8回, 5 log2(n+1)回
• 詳細な式ではなく「オーダー」を使う
– 例: O(n)回, O(log n)回
– ポイント:
• 定数を無視する
• 各変数について一番変化の大きい項だけを残す
– 理由: 定数倍の差はコンピュータの性能の違いやプログ
ラムの作り方ですぐに変わる
計算量の例: 平方根の計算
• 問題: 精度 d で x の平方根を求める
• 問題の大きさ: x と d
• 計算量:
x
– 反復法アルゴリズム:
– 二分法アルゴリズム
O(
δ
)
x
O(log( ))
d
計算量の違いによる実行時間の
差
• 1回の計算に1ナノ秒かかる場合の計算時間
(1 n = 10^ -9)
• 差が大きい
→ 定数倍の差は無視しても構わない
– 数倍速くするよりも、計算量の違うアルゴリズムを
使う方が良い場合も多い
現実的な計算可能性:
• その問題に対する計算モデルのアルゴリズ
ムがあり，それを実行すればいずれは答えが
出る
• 例: 平方根の計算、フィボナッチ数の計
算、・・・
• →計算量によってさらに分類
• 問題の大きさ n に対して
– O(log n) ― かなり速い (平方根)
– O(nk) ― 現実的な時間で解ける
– O(kn) ― nが大きいと膨大な時間がかかる
6.1 アルゴリズム（p.131最短路問題)
点集合V  {v1 ,...,vn }, v1が始点
v1から各点 viへの最短距離をri
とすると動的計画法の最適律から
r1  0,
rj  min{r k l (v k , v j ) | k  j}( j  1)
一般にこのままでは解けない
ネットワークが有向閉路を持たないとき
• そのときは、前の式が逐次代入ですぐ解ける。
• ネットワークが有向閉路をもたないとき、点の添
え字を適当につけ替えれば、有向辺 (v , v )
が存在すれば必ず
kq
k
q
となるようにできる
このとき
rj  min{rk  l (vk , v j ) | 1  k  j}
for　j  2,...,n.
で、順に求まる。
6.2 計算のモデル色々
• 有限状態機械
– 単純→現実のコンピュータよりも計算能力が低い
(記憶装置がない)
• チューリング機械・ランダムアクセス機械
– 有限状態機械 + 記憶装置
– 現実のコンピュータと「同じ」計算能力
• 帰納的関数・ラムダ計算
– 数学的な関数を単純化したもの
– 現実のコンピュータと「同じ」計算能力
有限オートマトン
 : 記号の非空有限集合
：記号の有限列の全体
＊
1)Q : 内部状態の集合
2)q0  Q : 初期状態
3)遷移関数：Ｑ    Q
4) F  Q : 受理状態
 ：非空有限集合でその元を記号と呼ぶ。
語：(word)とは、有限の長さの記号列。
言語とは、語の集合のこと。
語(記号列)に従ってオートマトンが内部状態の
遷移を行い、最後の状態が受理状態であれば、
このオートマトンは、この語を受理するという。
受理される語の全体のなす言語がオートマトン
によって定まる。
オートマトンの状態遷移図
  {0,1} : 記号集合
初期状態: a
1
a
0
b
1
0
0
0
1
d
c
1
受理状態：
F  {c, d}, F  {d}など
F={c,d} のとき、受理される語(word)は、0 が
奇数個含まれるもの
F={d} のとき、受理される語wordは、0,1 をそ
れぞれ奇数個含むもの
0
1
1
1
0
開始
1
F
0
0
開始
F
1
1
0
0
0
0
1
F
1
演習問題
以下を受理するオートマトンを作れ。
1) 00 で終わる列の全体
2) 3 個連続した 0 を含む列の全体
3) 1 で始まる列で、2 進数としてみたとき、5 で割り切れ
るものの全体。
オートマトンで識別できない言語の例
例 L を 1 で始まる 0,1 の列で 2 進数とみたとき
素数になるものの全体の集合。
6.2 計算のモデル化(時間があれば説明する）
1. 有限状態機械の例として以下のようなもの
がある：
有限オートマトン、ペトリネット、
順序機械(出力を持つ有限オートマトン
（ミーリー型、ムーア型）)
2. 無限の状態をもつ計算の数学的モデル
Turing 機械、ランダムアクセス機械
計算可能性: 解けない問題
• その計算モデルでは答えを出すアルゴリズム
がない計算可能性の定義はＴｕｒｉｎｇ機械に
よる
• 例: 停止性問題
– 「プログラムを実行したとき、計算が止まるか?」
– 任意のプログラムについて答える
– 注: プログラムを実行させてなかなか終わらない
場合、「いつか止まる」と「永遠に止まらない」の
区別はできない
Turing 機械の停止問題
• 「Turing機械とその入力データが与えられたとき、その
Turing機械が有限時間内に停止するか」という問題。
• その問題を解けるTuring機械がMが存在したとする。そこか
ら、あるTuring機械とそれへの入力が与えられたとき、Mを
利用して、それが有限時間内で止まると分かれば永遠に動
き続け、それが有限時間内に止まらないと分かれば停止す
る、そのようなTuring機械 M* が構成できる。
• M* に入力として M*自身を与えたとする。それが有限時間内
に停止すれば、それは M* が有限時間内に止まらないことを
意味するので、矛盾。それが永遠に動き続ければ、定義から
M* は有限時間で停止しなければならないはずで、矛盾。
• ゆえに、そのようなTuring機械 M は存在しない。
ゲーデル文とゲーデルの第一不完全性定理
ゲーデル文矛盾を含まない論理体系Tで次のような述語論理式Gが論理体
系T内に存在する時、
(G)
「この命題 (G) の証明は存在しない。」
(G) が証明できれば、矛盾。ゆえに、体系 T が無矛盾であれば、(G) は証明
不能である。つまり、体系T は不完全である。
ゲーデルの第一不完全定理
体系が無矛盾で初等的な自然数論を含むとすると、その体系内で証明も
反証もできない命題が存在する。
• 問題をモデル化することができず，そもそも解
けたかどうかを決められない
• 例: 「コンピュータは人間の知能を模倣できる
か?」
– →何をもって人間の知能とするか?
– (ある種のモデル化) チューリングテスト:
端末
話し相手は人か
コンピュータか?
人
端末
人
会話
コンピュータ
イミテーション・ゲーム(アラン・チューリング)
男性（Ａ）、女性（Ｂ）、と質問者（男性でも女性でも
よい）の３人で行われる。質問者は他の２人と別の
部屋にいる。このゲームでの質問者の目的は、こ
の二人のうち、どちらが男性であり、どちらが女性
であるかを確定することである。
彼はこのふたりを X 及びY という呼び名で知って
おり、ゲームの終わりに、彼は「 X が A であり、Y
が B である」もしくは「 X が B であり、Y が A であ
る」と述べることになる。
プレイヤー B は質問者を正解のほうに援助するこ
とを目的とし、プレイヤー A はその逆を目的とする。
「このゲームにおける男性の役割を機械が演じるとしたらど
ういうことになるだろうか」質問者は相手が人間相手のときと
同じくらいの頻度で誤った決定を下すだろうか。
これが「機械が考えることができるか」に取って代わる問題
である。
原文：
・Turing, “Computing Machinery and Intelligence,” Mind,
Vol. LIX, No.236, 1950.
翻訳：
・”計算機械と知能” 「マインズ・アイ(上)」ホフタッター、ベ
ネット著、NTT コミュニケーションズ, 1992, pp.70—93.
[ コメント ] チューリングテストは、結局は、人が相手に心があると思えば心が
あるし、相手に心がないと思えば持っていないという人間の主観に頼っている。
客観的実証主義的ではない。
言葉にはふたつの異なるカテゴリーがある。ひとつ目のカテゴリーはもの自体
の集まりで、もうひとつのカテゴリーは現象の総体である。「機械に心が存在
するか」という問いを発するとき、「心」はそのどちらに属するのかをまず考えな
ければいけない。
机や椅子はもの自体として存在しているように見える。一方、「風が吹く」と言っ
たとき、風はたしかに存在しているがもの自体ではない。これは、現象である。
ろうそくの炎も現象であり、生き物の命も現象である。人間自体それもひとつの
現象である。あるいは、無数の現象の集まりである。とすれば、心も現象のひと
つである。あるいは現象の集まりである。だから、風が秒速 10 m であったり、3
m であったり、1 cm であったりするように、心も計測すれば 2300 であったり、
156 であったり 10 であったりするだろう。気絶している人や全身麻酔で手術を
受けている人の心は、かぎりなく 0 に近いだろう。あるいは 0 かもしれない。こ
ころを物理量として計測すると、その単位はエントロピーあるいは同じことだが
情報量の単位で計測されることになるだろうか？
「
ゲ
ー
デ
ル
の
哲
学
」
高
橋
昌
一
郎
、
講
談
社
現
代
新
書

Download Report