アドバンスドトピック 計算できるものと計算できないもの 2008年4月9日 神林　靖.

Presentation on theme: "アドバンスドトピック 計算できるものと計算できないもの 2008年4月9日 神林　靖."— Presentation transcript:

1 アドバンスドトピック 計算できるものと計算できないもの 2008年4月9日 神林　靖

2 コンピュータサイエンスの誕生 世界初のコンピュータが完成したのは1946年 コンピュータサイエンスが誕生したのは1936年

3 ENIAC (1)

4 ENIAC (2)

5 ENIAC (3)

6 John Atanasoff

7 Atanasoff-Berry-Computer

8 「コンピュータサイエンス」とは？ コンピュータに何ができて、何ができないか？ 計算とはなにか？ 計算できる関数とはなにか？
計算できない関数とはなにか？ コンピュータに何ができて、何ができないか？

9 「計算する」とは何か？ 記号を処理すること（ホッブス） コンピュータが行えることすべて

10 「計算を定義するもの」 帰納的関数 ラムダ計算 チューリングマシン

11 二進法 (1) 1 2 10 3 11 4 100 5 101 6 110 7 111 8 1000 9 1001 1010

12 二進法 (2) 100 101 +) 1001

13 子ザル・モデル（１） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

14 子ザル・モデル（２） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

15 子ザル・モデル（３） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

16 子ザル・モデル（４） 西野哲郎著「中国人郵便配達問題＝コンピュータサイエンス最大の難関」講談社選書メチエ　より

17 子ザルモデル（番外編）

18 子ザル・モデルが達成したこと N 2N+1

19 アラン・チューリング

20 チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態
チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

21 チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態
チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

22 チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態
チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

23 チューリングマシン Ｍ １ ０ １ B B B S 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態
チューリングマシン 　Ｍ 無限長のテープ １ ０ １ B B B ヘッド S 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

24 チューリングマシン Ｍ １ ０ １ １ B B T 無限長のテープ ヘッド 有限制御部 状態遷移関数 S R 1 B T N 現在状態
チューリングマシン 　Ｍ 無限長のテープ １ ０ １ １ B B ヘッド T 有限制御部 状態遷移関数 現在状態 現在記号 次の状態 新記号 移動方向 S R 1 B T N

25 チューリングマシンの例 チューリングマシンで何ができるか、見てみよう 別のパワーポイントへ

26 チューリングマシンの符号化 チューリングマシンのテープと状態遷移関数を０と１の列で符号化する。
2019/4/14 チューリングマシンの符号化 チューリングマシンのテープと状態遷移関数を０と１の列で符号化する。 符号化したチューリングマシンをテープ上に書き込む。 そうしたテープを読み込んで、元のチューリングマシンの動作を模倣するチューリングマシンを作成できる。 それって、コンピュータのことですかい？

27 2019/4/14 万能チューリングマシン　Ｕ 元のチューリングマシンの符号 元のチューリングマシンへの入力 作業領域 S 有限制御部 A B C 無限長のテープ 万能チューリングマシンＵは、元のチューリングマシンＭへの入力（Ｂ）と、Ｍの状態遷移関数（Ａ）を見ながら、Ｍの動作を模倣する。

28 チューリングマシンの停止性判定問題 チューリングマシンＭとそれへの入力ｘが与えられたときに、Ｍがｘに対して停止するか否かを判定せよ。

29 計算不可能であることの証明（１） x1 x2 x3 … xj … M1 M2 M3 … Mi a11 a12 a13 … a1j …
すべてのチューリングマシンを書き出してみる。 x1 x2 x3 … xj … M1 M2 M3 … Mi a11 a12 a13 … a1j … a21 a22 a23 … a2j … a31 a32 a33 … a3j … … … … ai1 ai2 ai3 … aij … チューリングマシンMiが入力xjに対して、 停止するならば aij =1、さもなければ、 aij =0。

30 計算不可能であることの証明（２） Mが入力xiに対して停止するのは、表中のチューリングマシンMiがxiに対して停止しないとき、かつその時に限る。 というチューリングマシンがどこかにあるはずだから、探しなさい。

31 計算不可能であることの証明（３） MはMiではありえない。なぜなら、 Miがxi対して停止しないとき Mは停止し、 Miがxi対して停止するときにはMは停止しないからである。 え～！矛盾じゃ～ん！ すべてのチューリングマシンを網羅する表は構成できない。 チューリングマシンの停止性判定問題は計算不可能である。

32 ENIGMA (1)

33 ENIGMA (2)

34 ENIGMA (3)

35 アラン・チューリングと仲間

36 理論的に可能でも、 現実には不可能な問題 P = NP？ アルゴリズムの例 クリーク問題
グラフと3以上の整数ｋが与えられたとき、ｋ個の頂点からなる完全グラフがあるか？

37 公開鍵暗号 （１） ２つの素数 (p, q) を求める N = p×q L = lcm(p-1, q-1)
gcd(E, L) = 1 となる E を求める E×D mod L = 1となる D を求める

38 公開鍵暗号 （２） 暗号文 = 平文E mod N 平文　= 暗号文D mod N 暗号解読には、素因数分解が決め手 （でも、たいへん！）

39 P = NP？問題 P=[ｎｃの計算時間で解ける判定問題の集合] NP=[与えられた解答をｎｃの計算時間で確認できる判定問題の集合]

40 帰着可能性 (NP完全問題) 判定問題A 判定問題B Algorithm Y Algorithm X Yes/No Yes/No

41 NP完全問題 NPに属するすべての問題Aに対して、AはBに多項式時間で帰着可能である。 問題Bは、クラスNPに属する。
NP完全問題を解く多項式時間で解くアルゴリズムXが存在すれば、NP ⊆ Pとなる。

42 思い出話 １９８０年当時のコンピュータメーカー IBM Burroughs UNIVAC NCR CDC Honeywell
富士通+日立+NEC+東芝+三菱電機+沖電気

43 ソフトウェア会社の栄華盛衰 (1) 1984年 1 MicroPro $60,000 2 Microsoft $55,000 3 Lotus
$53,000 4 Digital Research $45,000 5 VisiCorp $43,000 6 Ashton-Tate $35,000 7 Peachtree $21,700 8 MicroFocus $15,000 9 Software Publishing $14,000 10 Borderbund $13,000

44 ソフトウェア会社の栄華盛衰 (2) 2001年 1 Microsoft $23,845,000 2 Adobe $1,266,387 3
Novell $1,103,592 4 Intuit $1,076,000 5 Autodesk $926,324 6 Symantec $790,153 7 Network Associates $745,692 8 Citrix $479,446 9 Macromedia $295,997 10 Great Plains $250,231

45 第五世代コンピュータ (1) 並列論理型コンピュータ 人間はいつか死ぬ p→q 彼は仙人である r→s 仙人は死なない s→￢q
彼は人間ではない r→￢p

46 第五世代コンピュータ (2)

47 私の研究室でやっていること 移動エージェントを使ったロボットの制御

48 課題 感想文 注 意：用紙はＡ４版２枚。ワープロ打ち とする。 1枚目に概要、2枚目に感想。 提出期限：4月16日 午前13時まで（厳守）
注　　意：用紙はＡ４版２枚。ワープロ打ち 　　とする。 　　　　　1枚目に概要、2枚目に感想。 提出期限：4月16日　午前13時まで（厳守） 提出場所：情報工学科事務室前 　　　　　レポート提出用ポスト