情報科学概論Ⅰ「計算とアルゴリズム」担当：亀山幸義 2015・07・14 1

情報科学概論Ⅰ「計算とアルゴリズム」
２０１５・０７・１４
担当：亀山幸義
プログラムＨとＧ
プログラムの実行の停止・非停止


1引数のＪａｖａプログラムPと、
入力の文字列s に対して、


プログラムＨ


P(s)↓ …この計算が停止して答えを出す
プログラムＧ


P(s)↑ … この計算が停止しない

H（p,s）＝１ … p(s) ↓ のとき
H（p,s）＝０ … それ以外
Ｇ（p）＝無限ループ …Ｈ（p,p)＝１のとき
Ｇ（p）＝１
…それ以外
なんと、既に矛盾している


G(G)↓ → H(G,G)=1 → G(G) = 無限ループ
G(G)↑ → H(G,G)=0 → G(G) = 1
1
コンピュータ科学の基本中の基本
１．Turing Machine
(チューリング機械）

コンピュータ科学の基本中の基本
２．Church-Turing’s thesis
(チャーチとチューリングの提唱）
Alan Turingが提唱した計算モデル




2

計算モデル＝計算を表現するための抽象的な（しか
し、厳密な）仕組み
機械(machine)＝抽象的なコンピュータ
計算可能な部分関数とは、


これは、他のたくさんの計算モデルと同等

1本の無限長テープと、有限個の命令（プログラム）か
ら構成される。
プログラム内蔵方式（フォン・ノイマン機械）を表す。
Turing機械で表現できるもののことである。


ラムダ計算で表現できるもの
帰納的部分関数として表現できるもの
Javaなどのプログラム言語を理想化したもの(無限メモ
リなど）
3
課題１
コンピュータ科学の基本中の基本
３．決定可能問題




文字列ｓの中に、tsukubaという文字列が含まれるか
文字列ｓは、1引数Javaプログラムを表しているか




与えられたプログラムが停止するかどうか

5
Turing機械（学籍番号が３で割り切れる人）
ラムダ計算（３で割って1余る人）
帰納的関数（あるいは帰納的部分関数、あるいは、再帰的
関数）（３で割って2余る人）
オプション課題：余力がある人向け

決定可能でない問題を決定不能という。

以下の計算モデルについて調査し、その内容をレポ
ートに書きなさい。

決定問題：入力ｓに対して、yes/noを返す問題
決定問題の解が、計算可能な関数で表現できる場
合、その問題を決定可能という。


4
ゲーデルの不完全性定理について調べなさい。
エッシャーの絵は無限ループを表しているようにも見える。
止まらない計算で有意義なものはあるか？
バッハはコンピュータ科学とどう関係するか。
6
1
情報科学概論Ⅰ「計算とアルゴリズム」
２０１５・０７・１４
担当：亀山幸義
アルゴリズム
Fibonacci数(1)

Fib (n)
1
if n = 1, 2
=
Fib(n-2) + Fib(n-1) if n > 2
アルゴリズム



アルゴリズムとプログラムの違い

Fib(1) = Fib(2) = 1
Fib(3) = Fib(1) + Fib(2) = 1 + 1 = 2
Fib(4) = Fib(2) + Fib(3) = 1 + 2 = 3
「問題」に対する「解き方」
与えられた基本命令をどう組み合わせて、解を求め
るかを記述したもの。

プログラムは、特定のプログラム言語で記述。その言
語の処理系を用いて実行可能。
アルゴリズムは、特定のプログラム言語や実装方式
に関する記述を取り除いた記述。抽象的な（しかし、
手順が明確になった）記述。
7
Fib(n)に対する、より高速な方法（２）
8
Fib(n)に対する、より高速な方法（3）
メモ化法：
x = Fib(n-1) ⇒ x２ = y = Fib(n)
y = Fib(n)
y２ = x+y = Fib(n-1)+Fib(n)
= Fib(n+1)
0
1
0
1
x
x2
=
y
y2
1 n-1 1 = Fib(n)
Fib(n+1)
1
1
A=
0
1
10
課題２
整数の
加算
Fib(n)-1
n-2
< 8 log n
1 n-1 1 = Fib(n)
Fib(n+1)
1
1
9

「より高速な方法」は本当に高速か？
整数の
乗算
素朴法０
メモ化法０
より高速 < 16 log n
な方法
1
1
A → A^2 → A^4 → …. → A^1024
1
1
問題

0
1
合計
自分の学籍番号の下７けたをＮとするとき、Fib(N)の
下５けたを計算せよ。



Fib(n)-1
n-2
<24 log n

20151234567 の人は、N=1234567とせよ。
プログラムを書いてもよいし、他の手段を使ってもよい。
高速なアルゴリズムを使った場合は加点する。
オプション課題(余力がある人向け）「Ｐ＝ＮＰ問題」
が、コンピュータ科学における最大の難問として、今
も解かれていない。これがどういう問題かレポートに
まとめよう。以下のキーワードを参考にしても良い。

11
これらを下２けたに修正します

ＳＡＴ問題、ナップザック問題、巡回セールスマン問題
非決定性、ＮＰ完全
12
2

Download Report