計算情報学Ｉ
名古屋大学 情報文化学部
自然情報学科３年
第４回

鈴木泰博
情報文化学部・大学院情報科学研究科
複雑系科学専攻

Science ofinteractions

Agenda

計算情報学 Ｉ 第４回
1.
2.
3.
4.
5.

前回の復習
連立方程式
ガウスの消去法
ガウスの消去法のアルゴリズム
アルゴリズムの計算量による評価

Science ofinteractions

アルゴリズムの数学的定義
チューリングマシン(A.Turing,1912‑54)“計算 の数学的定義を与える
ＲＡＭモデル、λ計算、帰納関数、whileプログラミング, e.t.c#ちなみにARMS, P systemsもすべて計算能力はチューリングマシンと等価。
チューリングマシンは実行可能な手続きという概念に対応し得る十分に汎用性のある形式的な計算モデルである(チャーチの提唱）：
つまり、チューリングマシンで表現される手続きをアルゴリズムの数学的な定義としよう。
Science ofinteractions

アルゴリズムの評価
入力のサイズが大きくなるに従って、アルゴリズムの時間効率がどのように変化するか？
評価のための単位時間には、CPU, ALUの性能
コンパイラの特性
２次記憶、入出力処理のオーバーヘッド
プログラミング言語の特性…
はすべて 無視 する。そして、プログラムの １命令 ＝１単位時間とみなす。

Science ofinteractions

計算量の計算演習
次のアルゴリズムの計算量を見積もれ
for i = 1 to n{a:=(1+2)x4}

for i = 1 to n{b:=a+bfor j=1 to n{a:=(1+2)x4}}
Science ofinteractions

計算量の計算解答
次のアルゴリズムの計算量を見積もれ
for i = 1 to n{a:=(1+2)x4}
Ans. O(n)for i = 1 to n{b:=a+bfor j=1 to n{a:=(1+2)x4}}
Ans. O(n2)Science ofinteractions

計算ができないということ
演習
1.

クレタ人は嘘つきだとクレタ人が言った。クレタ人は果たして嘘つきであるか、そうでないかを判定せよ。

2.

このスクリーンに書いてあることは、すべて嘘です
ではこの講義の内容はすべて嘘であるのか判定せよ。

自己言及のパラドクス
Science ofinteractions

計算量
計算の複雑さの理論
前提：アルゴリズムが ある 問題
において、そのアルゴリズムがどの程度複雑かを評価する理論•時間計算量•解くのに必要な時間•領域計算量•解くのに必要な記憶領域
Ｐ（多項式時間で答えが出る）、ＮＰ（Ｐではない場合）
ＮＰ困難：ＮＰのクラスの問題だが、Ｐのクラスに多項式時間で帰着可能
ＮＰ完全：ＮＰのクラスの問題で、Ｐに帰着できない場合（最も難しい問題）（ＮＰ完全問題の例 → ＳＡＴ問題）

Science ofinteractions

連立方程式の直接解法〰ガウス法

Science ofinteractions

なぜ、連立1次方程式？
結構、計算機にとってはハードな問題なのです。

• 数値計算の 得意技 は補間と近似計算であるが、連立一次方程式はそれらのどの局面にも現れる不可避な存在である。曲線補間、微分方程式、偏微分方程式のなどなど）。
• 実際の問題ではＮが100万近い大規模な問題が多い。
• あらゆる連立１次方程式に対して計算量的にも効率が良い、オールマイティな解法は存在しない。

Science ofinteractions連立1次方程式〜線形代数の復習
つるかめ算
問題：つるとかめが合計5匹いる。足の数は合計16本である。
つるとかめはそれぞれ何匹いるか。
つるとかめの数をそれぞれx,yとすると。

x2xy4y516①②② ① ２xy2y5
6y=3, x=2
Science ofinteractionsガウスの消去法〜線形代数の復習
素直に順番にただ未知数を消去し、与えられた問題を簡単な形に書き換えて解く

□

□

□□

□

□

□

□□

□

□

□□

□

□

□

□

□

□

□

□

□

① 下の式 から 上の式 の何倍かを引き、左から順に未知数を消してゆく。
（前進消去）

□□

□

□

□

□

□

□

□

②求まった未知数を下の式から代入し順番に未知数を求めていく。
（後退代入）
Science ofinteractionsガウスの消去法〜線形代数の復習
ガウスの消去法：

下の式から上の式

2x4xy6yz3z

15 L ①
41 L ②8x8y9z

83 L ③2xy4yzz

15 L ①
11 L ②4y5z

23 L ③の何倍かを引く。

②−①ｘ2
③−①ｘ4

Science ofinteractionsガウスの消去法〜線形代数の復習
ガウスの消去法：

下の式

から上の式の何倍かを引く。

2xy4yzz

15 L ①
11 L ②4y5z

23 L ③y4yzz

15 L ①
11 L ②4z

12 L ③③−②ｘ１

2x+2+3=15よりx=52x4y+3=11よりy=2後退代入

Z=3以上より、x=5, y=2, z=3

Science ofinteractions

演習問題〜ガウスの消去法

以下の連立一次方程式を解きなさい。

2x4xy6yz
3z

15 L ①
41 L ②8x8y9z

83 L ③

Science ofinteractions

2x4xy6yz3z

15 L ①
41 L ②8x8y9z

83 L ③

演習問題
解答

②−①ｘ２
③−①ｘ４2xy4yzz

15 L ①
11 L ②4y5z

23 L ③③−②ｘ１2xz = 3, y = 2, x=5y4yzz

15 L ①
11 L ②4z

12 L ③

Science ofinteractions

演習問題〜ガウスの消去法

以下の連立一次方程式を解きなさい。

x2xy2yzz

6 L ①
3 L ②x3yz

8 L ③

Science ofinteractions

演習問題
x2xy2yzz

6 L ①
3 L ②x3yz8 L ③

解答

②−①ｘ２
③−①ｘ１

xxyz3z

6 L ①
9 L ②4y2z14

L ③y4yz2z

614

L ①
L ③3z

9 L ②z = 3, y = 2, x=10が現れたら入れ替える

部分ピポット選択
Science ofinteractions

部分ピボット選択〰桁落ち
x1 x2 1 r
x1 x2 1
しかし、実際は x2x2

1 r
1

1 r , x1r

x2

1 r , x10ε<<なので1/ε>>となり桁落ちが発生
そこで、部分ビボッド交換をすると、

x1x2

1x1x2

1 r(1) x2

1 rx2

1 r , x1r

Science ofinteractions連立1次方程式〜線形代数の復習
x2xy4y516

1 12 4xy516Axy

係数行列Ａ べクトル x べクトル y連立方程式は一般にN変数、N方程式だからAはN次の正方行列

Science ofinteractions

答えは一つとは限らない
ないかもしれないし。。
1 2 3x64 5 6y157 8 9z24

x=1, y=1, z=1 でもいいし、x=3, y= -3, z=3でも、x=0,y=3, z=0でもＯＫ
ガウスの消去法で計算してみてください。
z = tとおくと、y = 3 – 2t, x = t より、z = x, y = 3 – 2t

連立一次方程式の解が一意である＝係数行列が正則だが、正則の判定には計算量がかかるので、予め正則か否かの判定を行なわず、計算の過程でアルゴリズム的に判断するのが普通。
Science ofinteractionsガウスの消去法のアルゴリズム

前進消去
下の式

a 212xa11 4÷2=2倍 4 x8x2xa 31a11 8÷2=4倍 4 x8x

第１行の

a i1,ia11から上の式のyz

15 L ①

6y8y3z9z

41 L ②83 L ③yz

15 L ①

6y8y3z9z

41 L ②83 L ③

何倍かをひく

2,3,...n を第 i 行から引く。
Science ofinteractionsガウスの消去法のアルゴリズム

前進消去
a ik
第 k 行 (k=1,2,…n)の,ia kk
2xyz

15 L ①

4y4yz5z

11 L ②23 L ③

2,3,...n を第 i 行から引く

a 32
第2行のを第3行から引く
a 22→第1列からk列までは既に0a ik
またk列も、a ik( ) a kka kk0アルゴリズム
for k=k+1 to N
引き算を繰り返すayi ( ik ) yk
a kk

yi

Science ofinteractionsガウスの消去法のアルゴリズム

前進消去
k =1,2,…,N の順に
i = k+1,k+2, … N の順に

a ik
p:
a kk

j = k+1, k+2, … N の順に

a ij : a ij
を繰り返す

yi

a ik
a kj
a kk

a ik
( ) yka kkyi

を繰り返すを繰り返す
Science ofinteractionsガウスの消去法のアルゴリズム

後退代入
前進消去完了後

a 11 x1xN 1

a12 x2L

a1N xNy1

a 22 x2LL

a 2 N xNy2

a N 1N 1 xN 1a N 1N xN

yN 1a NN xN

yN( yN 1 a N 1N xN ) / a N 1N 1xNyNa NN

Nxi( yia ik xk ) / a ii
k i 1

Science ofinteractionsガウスの消去法のアルゴリズム

後退代入
アルゴリズムxN :yNa NNi = N-1, N-2, …, 1の順に
Nxi

( yia ik xk ) / a ii
k i 1

を繰り返す

Science ofinteractionsガウスの消去法のアルゴリズム

計算量
k =1,2,…,N の順に
i = k+1,k+2, … N の順に

a ik
p:
a kk

（割り算１回）

j = k+1, k+2, … N の順に

a ij : a ij

p a kj（掛け算(N-k)回）

を繰り返す

yip ykyi（掛け算１回）

を繰り返す
n 1

を繰り返す

(n k 2)(n k )
k 1

n23

Science ofinteractions