第６章のねらい モデルの記述（第4章） モデル上の操作による計算とプログラム（第5章） 本章 アルゴリズム：計算手順 計算のモデル化 よいアルゴリズムとよくないアルゴリズムがある 計算のモデル化 有限状態機械，チューリング機械 計算量と計算可能性 ○玉井先生スライド

ハノイの塔問題 円盤の山を左から中央に移すのにかかる時間は? n: 円盤の枚数 1枚動かすのに10-9秒かかるとする (cf. 1GHz) A: 約5ミリ秒 B: 約50秒 C: 約50億年 D: 約50兆年 ヒント: n=20のとき約1ミリ秒 ○増原先生スライド

コンピュータによる問題解決: 実際 問題解決の手順 アルゴリズム 現実世界の 問題 プログラム モデル化 された 問題 答 プログラミング 人間が コンピュータが 実行 人間が考察 モデル化 人間が

アルゴリズムの重要性 性能に大きな違いが出る 類型化されている 同じ問題を解く複数のアルゴリズムがある アルゴリズムによって計算時間が桁違いに変わることがある 類型化されている 全く違う問題を解くアルゴリズムが同じものになることがある 性能に関する考察・プログラミングを共通化できる

問題: 平方根の計算 を求める 注意: 問題: 小数の計算は有限の精度で行われる →近似値しか求められない ある正の実数 x が与えられたときに、2乗すると x に近くなる正の実数 y を精度 d で求める． つまり， となるような y を 1 つ求める

平方根のアルゴリズム: 反復法 x = 90, d = 1 の場合を考える 「y = 0, 1, 2, 3, ... を順に検討してゆき (y+d)2 が 90 より大きくなったら、 その1つ前が解」 実際の動作 x =2, d =0.0001 の場合、 アルゴリズム1 (反復による 平方根の計算)

平方根のアルゴリズム: 二分法 アルゴリズム2 (二分法による平方根の計算) x の平方根を精度 d で求める (ただし x > 1): >

平方根のアルゴリズム: 二分法の実際 「区間の幅」が1/2ずつ減ってゆく

アルゴリズムの速度 反復法: 約 回 二分法: 比較: x=2, d=0.0000000001 のとき 反復法: 約 回 二分法: 1回繰り返すごとに区間の幅が1/2になる n回繰り返し後の区間の幅は これが 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 計算量: 反復法アルゴリズム: 二分法アルゴリズム

計算量の違いによる実行時間の差 1回の計算に1ナノ秒かかる場合の計算時間 差が大きい → 定数倍の差は無視しても構わない 数倍速くするよりも、計算量の違うアルゴリズムを使う方が良い場合も多い (1 n = 10^ -9)

現実的な計算可能性: その問題に対する計算モデルのアルゴリズムがあり，それを実行すればいずれは答えが出る 例: 平方根の計算、フィボナッチ数の計算、・・・ →計算量によってさらに分類 問題の大きさ n に対して O(log n) ― かなり速い (平方根) O(nk) ― 現実的な時間で解ける O(kn) ― nが大きいと膨大な時間がかかる

6.1 アルゴリズム（p.131最短路問題)

ネットワークが有向閉路を持たないとき そのときは、前の式が逐次代入ですぐ解ける。 ネットワークが有向閉路をもたないとき、点の添え字を適当につけ替えれば、有向辺 が存在すれば必ず となるようにできる このとき で、順に求まる。

6.2 計算のモデル色々 有限状態機械 チューリング機械・ランダムアクセス機械 帰納的関数・ラムダ計算 単純→現実のコンピュータよりも計算能力が低い (記憶装置がない) チューリング機械・ランダムアクセス機械 有限状態機械 + 記憶装置 現実のコンピュータと「同じ」計算能力 帰納的関数・ラムダ計算 数学的な関数を単純化したもの

有限オートマトン

語：(word)とは、有限の長さの記号列。 言語とは、語の集合のこと。 　　：非空有限集合でその元を記号と呼ぶ。 語：(word)とは、有限の長さの記号列。 言語とは、語の集合のこと。 語(記号列)に従ってオートマトンが内部状態の遷移を行い、最後の状態が受理状態であれば、このオートマトンは、この語を受理するという。 受理される語の全体のなす言語がオートマトンによって定まる。

オートマトンの状態遷移図 初期状態: a : 記号集合 1 b a 1 1 d c 1 受理状態：

F={c,d} のとき、受理される語(word)は、0 が奇数個含まれるもの F={d} のとき、受理される語wordは、0,1 をそれぞれ奇数個含むもの

開始 1 F

1 F 開始

演習問題　　以下を受理するオートマトンを作れ。 00 で終わる列の全体 3 個連続した 0 を含む列の全体 1 で始まる列で、2 進数としてみたとき 、5 で割り切れるものの全体。 オートマトンで識別できない言語の例 例　L を 1 で始まる 0,1 の列で 2 進数とみたとき素数になるものの全体の集合。

6.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 は不完全である。 ゲーデルの第一不完全定理 体系が無矛盾で初等的な自然数論を含むとすると、その体系内で証明も反証もできない命題が存在する。

問題をモデル化することができず，そもそも解けたかどうかを決められない 例: 「コンピュータは人間の知能を模倣できるか?」 →何をもって人間の知能とするか? (ある種のモデル化) チューリングテスト: 端末 人 会話 人 端末 話し相手は人か コンピュータか? コンピュータ

プレイヤー B は質問者を正解のほうに援助することを目的とし、プレイヤー A はその逆を目的とする。 イミテーション・ゲーム(アラン・チューリング) 男性（Ａ）、女性（Ｂ）、と質問者（男性でも女性でもよい）の３人で行われる。質問者は他の２人と別の部屋にいる。このゲームでの質問者の目的は、この二人のうち、どちらが男性であり、どちらが女性であるかを確定することである。 彼はこのふたりを 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 かもしれない。こころを物理量として計測すると、その単位はエントロピーあるいは同じことだが情報量の単位で計測されることになるだろうか？

「ゲーデルの哲学」高橋昌一郎、講談社現代新書