数学・計算機科学

北原鉄朗

平成 13 年 9 月 13 日

目次

第 1 章線形代数 5 1.1 線形空間 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 線形独立と線形従属 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 基底と次元 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 正規直交系 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 線形写像 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.6 行列式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.7 逆行列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.8 連立一次方程式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.9 固有値と固有ベクトル . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.10 特別な行列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.11 行列の対角化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

第 2 章微分方程式 13 2.1 1 階常微分方程式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 2 階線形常微分方程式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

第 3 章解析学 15 3.1 級数の和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 微分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

第 4 章複素解析 17 4.1 複素微分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.2 複素積分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.3 級数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.4 留数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.5 定積分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

第 5 章信号処理 21 5.1 連続時間のフーリエ変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 離散フーリエ変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.3 z 変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

第 6 章エントロピー 23 6.1 エントロピーの定義 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 第 7 章数理論理学 25

7.1 古典命題論理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 7.2 古典述語論理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.3 直観主義命題論理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.4 様相論理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

第 8 章数理計画法 29 8.1 用語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

第 9 章データ構造とアルゴリズム 31 9.1 アルゴリズム概論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 9.2 線形リスト . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 9.3 スタック . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 9.4 待ち行列（キュー） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 9.5 木構造（概論） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 9.6 順序木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 9.7 2 分木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 9.8 2 分探索木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 9.9 AVL 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 9.10 B 木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 9.11 半順序の付いた木 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 9.12 集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 9.13 優先度付き待ち行列 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 9.14 ソート法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 9.15 探索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 9.16 文字列照合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

第 10 章形式言語 43 10.1 文法と言語 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 10.2 文脈自由文法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 10.3 有限オートマトン . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 10.4 プッシュダウン・オートマトン . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

第 11 章オペレーティングシステム 47 11.1 プロセスの相互交渉 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 11.2 排他制御（概論） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 11.3 セマフォア . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 11.4 セマフォアの応用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 11.5 モニタ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 11.6 モニタの応用 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 11.7 マルチプログラミング（概論） . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 11.8 オーバレイ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 11.9 セグメンテーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 11.10ページング . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 第 12 章数値解析 53

12.1 ニュートン法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

第 13 章パターン認識の基礎 55 13.1 パターン認識概論 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 13.2 学習 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 13.3 ノンパラメトリックな学習 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 13.4 パラメトリックな学習 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 13.5 特徴空間の変換 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

第 14 章人工知能の基礎 59 14.1 探索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 14.2 導出原理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 14.3 ホーン節 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

第1章線形代数

1.1 線形空間

定義 1.1.1 (線形空間) 空でない集合 V 上に, 和 x + y とスカラー倍 ax が定義され, 次の条件を満たすとき, V を線形空間 (lineary space) という. ここで, x, y, z ∈ V, a, b ∈ K である.

(1) (可換則) x + y = y + x;

(2) (結合則) (x + y) + z = x + (y + z);

(3) 零ベクトルが存在する, すなわち, ∃0 ∈ V : x + 0 = x;

(4) 逆ベクトルが存在する, すなわち, ∃x′ ∈ V : x + x′ = 0;

(5) a(x + y) = ax + ay;

(6) (a + b)x = ax + by;

(7) (ab)x = a(bx);

(8) 1x = x.

定義 1.1.2 (部分空間) 線形空間 V の部分集合 W が, 線形空間となるとき, W を V の部分空間という.

定理 1.1.1 線形空間 V の部分集合 W が V の部分空間であるための必要十分条件は,

∀a, b ∈ K, ∀x, y ∈ W : ax + by ∈ W

が成り立つことである.

1.2 線形独立と線形従属

定義 1.2.1 (線形独立) 線形空間 V の部分空間

{x_{1}, ⋯, x_{n}} が, ∀a_{1}, ⋯, a_{n} ∈ K に対して,

a_{1}x_{1} + ⋯ + a_{n}x_{n} = 0 ⟹ a_{1} = ⋯ = a_{n} = 0

を満たすとき, {x_{1}, ⋯, x_{n}} は線形独立 (linearly independent) という.

定義 1.2.2 (線形従属) 線形独立の否定を線形従属 (lineraly dependent) という.

例 1.2.1 x := (1, −1, 4)^{t}, y := (2, 3, −1)^{t}, z := (0, −5, 9)^{t} が線形独立かどうかを調べる.

ax + by + cz = 0 とおくと,

\{ \begin{matrix}a + 2b = 0 \\ −a + 3b − 5c = 0 \\ 4a − b + 9c = 0 \end{matrix}

a = 2, b = −1, c = −1 とすれば上の連立方程式が成立するので, x, y, z は, 線形従属である.

1.3 基底と次元

定義 1.3.1 (基底) 線形空間 V の部分空間 {b_{1}, ⋯, b_{n}} が次の 2 つの条件を満たすとき, これを V の基底という.

(1) {b_{1}, ⋯, b_{n}} は線形独立である.

(2) V の任意の元は, {b_{1}, ⋯, b_{n}} の線形結合である. すなわち,

∀x ∈ V, ∃a_{1}, ⋯, a_{n} ∈ K : x = a_{1}b_{1} + ⋯ + a_{n}b_{n}.

定義 1.3.2 (次元) 線形空間 V の基底を構成するベクトルの個数を V の次元といい, dim V で表す.

1.4 正規直交系 ; 定義 1.4.1 (直交) 内積空間のベクトル x, y に対して, ; (x, y) = 0 ; が成り立つとき, xとyは直交するといい, x ⊥ y と表す. ; 定義 1.4.2 (正規直交系) 内積空間のベクトル ; v_{1}, ⋯, v_{n} が次の条件を満たすとき, 正規直交系という: ; (1) ||v_{i}|| = 1; ; (2) v_{i} ⊥ v_{j} (i ≠ j). ; グラムシュミットの正規直交化法 ; 線形独立なベクトル v_{1}, ⋯, v_{n} から正規直交系 ; {u_{1}, ⋯, u_{n}} を以下の要領で作る: ; u′_{1} := v_{1}, u_{1} := u′_{1}/||u′_{1}||; ; u′_{2} := v_{2} − (v_{2}, u_{1})u_{1}, u_{2} := u′_{2}/||u′_{2}||; ; u′_{3} := v_{3} − (v_{3}, u_{1})u_{1} − (v_{3}, u_{2})u_{2}, ; u_{3} := u′_{3}/||u′_{3}||; ; ⋮ ; u′_{n} := v_{n} − ∑_{k=1}^{n−1}(v_{n}, u_{k})u_{k}, u_{n} := u′_{n}/||u′_{n}||. ; 例 1.4.1 R^{3} の基底 v_{1} := (1, 0, 0)^{t}, v_{2} := (1, 1, 0)^{t}, ; v_{3} := (1, 1, 1)^{t} から正規直交規定を作る. ; u_{1} = v_{1} (∵ ||v_{1}|| = 1); ; u′_{2} = v_{2} − (v_{2}, u_{1})u_{1} = (1, 1, 0)^{t} − 1 · (1, 0, 0)^{t} ; = (0, 1, 0)^{t}; ; u_{2} = (0, 1, 0)^{t}; ; u′_{3} = v_{3} − (v_{3}, u_{1})u_{1} − (v_{3}, u_{2})u_{2} ; = (1, 1, 1)^{t} − 1 · (1, 0, 0)^{t} − 1 · (0, 1, 0)^{t} ; = (0, 0, 1)^{t}; ; u_{3} = (0, 0, 1)^{t}. ; ∴ {(1, 0, 0)^{t}, (0, 1, 0)^{t}, (0, 0, 1)^{t}}. 1.5 線形写像

定義 1.5.1 (線形写像) V, V′ を線形空間とする. 写像 f : V → V′ が,

f(x + y) = f(x) + f(y), f(ax) = af(x)

を満たすとき, 写像 f を V から V′ の線形写像 (linear mapping) という. ここで, x, y ∈ V, a はスカラーである.

定理 1.5.1 写像 f : V → V′ が線形写像であることの必要十分条件は,

f(ax + by) = af(x) + bf(y)

が成り立つことである. ここで, x, y ∈ V, a, b はスカラーである.

像 Imf := {f(x) | x ∈ V }.

核 Kerf := {x ∈ V | f(x) = 0}.

定義 1.5.2 (行列表現) b_{1} := {x_{1}, ⋯, x_{n}}, b_{2} := {y_{1}, ⋯, y_{n}} をそれぞれ線形空間 V, V′ の基底とするとき,

(f(x_{1}), ⋯, f(x_{n})) = (y_{1}, ⋯, y_{n})P

を満たす行列 P を基底 b_{1}, b_{2} による f の行列表現という.

例 1.5.1 f : R^{2} → R^{3} が,

f((x_{1}, x_{2})^{t}) = (x_{1}, 2x_{1} + 3x_{2}, 2x_{1} − 3x_{2})^{t}

で定義され, R^{2}, R^{3} の基底がそれぞれ

{(1, 1)^{t}, (2, −1)^{t}}, {(1, 1, −1)^{t}, (1, 0, 1)^{t}, (1, −2, 4)^{t}}

である. これらの基底による f の行列表現 P を求める.

f((1, 1)^{t}) = (1, 5, −1)^{t}, f((2, −1)^{t}) = (2, 1, 7)^{t}

だから,

( \begin{matrix}1 & 2 \\ 5 & 1 \\ −1 & 7 \end{matrix} ) = ( \begin{matrix}1 & 1 & 1 \\ 1 & 0 & −2 \\ −1 & 1 & 4 \end{matrix} ) P.

∴ P = ( \begin{matrix}1 & 1 & 1 \\ 1 & 0 & −2 \\ −1 & 1 & 4 \end{matrix} )^{−1} ( \begin{matrix}1 & 2 \\ 5 & 1 \\ −1 & 7 \end{matrix} )

\begin{matrix}= & ( \begin{matrix}2 & −3 & −2 \\ −2 & 5 & 3 \\ 1 & −2 & −1 \end{matrix} ) ( \begin{matrix}1 & 2 \\ 5 & 1 \\ −1 & 7 \end{matrix} ) \\ = & ( \begin{matrix}11 & −13 \\ 20 & 22 \\ −8 & −7 \end{matrix} ) . \\ 定義 1.5.3 (基底変換行列)b := \{x_{1}, ⋯, x_{n}\} を線形空 \\ 間 V の基底とする. b′ := \{x′_{1}, ⋯, x′_{n}\} を線形空間 V \\ の b とは異なる基底とするとき, \\ (x′_{1}, ⋯, x′_{n}) = (x_{1}, ⋯, x_{n})T \\ を満たす行列 T を基底 b から b′ への基底変換行列という. \\ 例 1.5.2 R^{2} の基底 \{(−1, 2)^{t}, (1, 0)^{t}\} を別の R^{2} の基底 \\ \{(1, 1)^{t}, (2, −1)^{t}\} に変換する基底変換行列 T を求める. \\ ( \begin{matrix}1 & 2 \\ 1 & −1 \end{matrix} ) = ( \begin{matrix}−1 & 1 \\ 2 & 0 \end{matrix} ) T \\ ∴ T & = & ( \begin{matrix}−1 & 1 \\ 2 & 0 \end{matrix} )^{−1} ( \begin{matrix}1 & 2 \\ 1 & −1 \end{matrix} ) \\ = & ( \begin{matrix}1/2 & −1/2 \\ 3/2 & 3/2 \end{matrix} ) . \end{matrix} \begin{matrix}1.6 行列式 \\ 定義 1.6.1 (行列式) n 次正方行列: \\ A := ( \begin{matrix}a_{11} & ⋯ & a_{1n} \\ ⋮ & ... & ⋮ \\ a_{n1} & ⋯ & a_{nn} \end{matrix} ) \\ に対して, 要素を同じ列から選ばないようにして各行か \\ ら 1 つずつ抜き取り, 全体の符号を掛け合わせ, すべての \\ 組み合わせに対して和をとってできたスカラーを行列式 \\ といい, det(A) または |A| と表す. \\ 計算手順 (1 次正方行列の場合) \\ |a_{11}| = a_{11}. \\ 計算手順 (2 次正方行列の場合) \\ | \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} | = a_{11}a_{22} − a_{12}a_{21}. \\ 計算手順 (3 次正方行列の場合) \\ | \begin{matrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{matrix} | = a_{11}a_{22}a_{33} + a_{12}a_{23}a_{31} + a_{13}a_{21}a_{32} \\ −a_{13}a_{22}a_{31} − a_{12}a_{21}a_{33} − a_{11}a_{23}a_{32}. \\ 計算手順 (4 次以上の正方行列の場合) \\ 定理 1.6.1(後述) をもちいて, \\ | & \begin{aligned}a_{11} & & & & ∗ \\ & . & . & . \\ O & & & & a_{nn} \end{aligned} & | \\ の形に変形し, 定理 1.6.2(後述) を適用する. \\ 定理 1.6.1 1. 行列のある行を k(≠ 0) した行列の行列 \\ 式は, もとの行列の行列式の k に等しい. \\ 2. 行列のある行に他の行のスカラー倍を加えた行列の \\ 行列式は, もとの行列の行列式に等しい. \end{matrix}

3. 行列の隣り合う 2 行を入れ替えた行列の行列式は, もとの行列の行列式の −1 倍に等しい.

定理 1.6.2

| \begin{matrix}a_{11} & & & & ∗ \\ & . & . & . \\ O & & & & a_{nn} \end{matrix} | = a_{11} ⋯ a_{nn}.

例 1.6.1

A := ( \begin{matrix}1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 4 & 1 & 2 \\ 4 & 1 & 2 & 3 \end{matrix} )

の行列式を求める.

1 行めの −2 倍, −3 倍, −4 倍をそれぞれ 2 行め, 3 行め, 4 行めにくわえて,

det A = | \begin{matrix}1 & 2 & 3 & 4 \\ 0 & −1 & −2 & −7 \\ 0 & −2 & −8 & −10 \\ 0 & −7 & −10 & −13 \end{matrix} | .

2 行めの −2 倍, −7 倍をそれぞれ 3 行め, 4 行めにくわえて,

det A = | \begin{matrix}1 & 2 & 3 & 4 \\ 0 & −1 & −2 & −7 \\ 0 & 0 & −4 & 4 \\ 0 & 0 & 4 & 36 \end{matrix} | .

3 行めの +1 倍をそれぞれ 4 行めにくわえて,

det A = | \begin{matrix}1 & 2 & 3 & 4 \\ 0 & −1 & −2 & −7 \\ 0 & 0 & −4 & 4 \\ 0 & 0 & 0 & 40 \end{matrix} | .

よって, det A = 1 · (−1) · (−4) · 40 = 160.

1.7 逆行列

定義 1.7.1 n 次の正方行列 A に対して,

AB = BA = I

を満たす n 次の正方行列 B が存在するとき, A は正則または可逆であるという. このとき, B を A の逆行列といい, A^{−1} で表す.

計算手順 (2 次正方行列の場合)

( \begin{matrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{matrix} )^{−1} = \frac{1}{Δ} ( \begin{matrix}a_{22} & −a_{12} \\ −a_{21} & a_{11} \end{matrix} ) .

ここで, Δ := a_{11}a_{22} − a_{12}a_{21}.

計算手順 (3 次以上の正方行列の場合)

1. n 次正方行列 A に対して, 行列 (A|I) を考える. ここで, I は n 次の基本行列.

2. (A|I) に行列の基本変形 (後述) を行い, (I|X) の形に変形する.

3. 2. で得られた行列 X が求める逆行列 A^{−1} である.

行列の基本変形

行の基本変形 (elementary transformation of row) は, 以下の操作とそれらを組み合わせたものである:

1. ある行をスカラー倍 (0 以外) する.

2. ある行を他の行にくわえる.

3. 2 つの行を入れ替える.

例 1.7.1

A := ( \begin{matrix}1 & 2 & 3 \\ 2 & 2 & 0 \\ 3 & 0 & 3 \end{matrix} )

の逆行列を求める.

(A|I) = ( \begin{matrix}1 & 2 & 3 & 1 & 0 & 0 \\ 2 & 2 & 0 & 0 & 1 & 0 \\ 3 & 0 & 3 & 0 & 0 & 1 \end{matrix} ) .

1 行目の −2 倍, −3 倍をそれぞれ 2 行目, 3 行目にくわえて,

( \begin{matrix}1 & 2 & 3 & 1 & 0 & 0 \\ 0 & −2 & −6 & −2 & 1 & 0 \\ 0 & −6 & −6 & −3 & 0 & 1 \end{matrix} ) .

2 行目を −1/2 倍して,

( \begin{matrix}1 & 2 & 3 & 1 & 0 & 0 \\ 0 & 1 & 3 & 1 & −1/2 & 0 \\ 0 & −6 & −6 & −3 & 0 & 1 \end{matrix} ) .

2 行目の −2 倍, 6 倍をそれぞれ 1 行目, 3 行目にくわえて,

( \begin{matrix}1 & 0 & −3 & −1 & 1 & 0 \\ 0 & 1 & 3 & 1 & −1/2 & 0 \\ 0 & 0 & 12 & 3 & −3 & 1 \end{matrix} ) .

3 行目を 1/12 倍して,

( \begin{matrix}1 & 0 & −3 & −1 & 1 & 0 \\ 0 & 1 & 3 & 1 & −1/2 & 0 \\ 0 & 0 & 1 & 1/4 & −1/4 & 1/12 \end{matrix} ) .

3 行目の 3 倍, −3 倍をそれぞれ 1 行目, 2 行目にくわえて,

( \begin{matrix}1 & 0 & 0 & −1/4 & 1/4 & 1/4 \\ 0 & 1 & 0 & 1/4 & 1/4 & −1/4 \\ 0 & 0 & 1 & 1/4 & −1/4 & 1/12 \end{matrix} ) .

よって,

A^{−1} = ( \begin{matrix}−1/4 & 1/4 & 1/4 \\ 1/4 & 1/4 & −1/4 \\ 1/4 & −1/4 & 1/12 \end{matrix} ) .

定義 1.7.2 (階数) 任意の n 次正方行列 A が, 基本変形を繰り返すことによって

( \begin{matrix}I_{r} & O \\ O & O \end{matrix} ) (I_{r} : r 次の基本行列)

と変形されるとき, r を行列 A の階数 (rank) といい, rankA で表す.

\begin{matrix}1.8 連立一次方程式 \\ 計算手順 \\ 連立一次方程式 Ax = b の両辺に対して, 行列の基本 \\ 変形を用いて \\ ( \begin{matrix}I & ∗ \\ O & O \end{matrix} ) x = b′ \\ の形に変形する. \\ 例 1.8.1 連立方程式: \\ ( \begin{matrix}4 & −13 & −13 \\ 3 & −8 & −8 \\ 1 & −2 & −2 \end{matrix} ) ( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}−55 \\ −36 \\ −10 \end{matrix} ) \\ を解く. \\ 行列に基本変形を用いると, \\ ( \begin{matrix}1 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{matrix} ) ( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}−4 \\ 3 \\ 0 \end{matrix} ) . \\ すなわち, \\ \{ & \begin{matrix}x = −4 \\ y + z = 3 \end{matrix} \\ よって, \\ ( \begin{matrix}x \\ y \\ z \end{matrix} ) = ( \begin{matrix}−4 \\ t \\ 3 − t \end{matrix} ) = ( \begin{matrix}−4 \\ 0 \\ 3 \end{matrix} ) + t ( \begin{matrix}0 \\ 1 \\ −1 \end{matrix} ) . \\ ただし, t は任意の実数. \end{matrix}

\begin{matrix}1.9 固有値と固有ベクトル \\ 定義 1.9.1 (固有値と固有ベクトル)A を正方行列とす \\ る. \\ Ax = λx \\ を満たす0でないベクトルxとスカラー λ が存在するとき, \\ λ を A の固有値といい, xを固有値 λ に対する固有ベク \\ トルという. \\ 定義 1.9.2 (固有多項式) A を正方行列とする. z を未知 \\ 数とする. A から定まる多項式: \\ F (z) := |A − zI| \\ を A の固有多項式または特性多項式といい, 方程式: \\ F (z) = 0 \\ を A の固有方程式または特性方程式という. \\ 定理 1.9.1 A を正方行列とし, F をその固有多項式とす \\ る. このとき, \\ λが A の固有値 ⟺ F (λ) = 0 \\ が成り立つ. \\ 例 1.9.1 \\ A := ( \begin{matrix}3 & 1 & 2 \\ 1 & 3 & 1 \\ 2 & 1 & 3 \end{matrix} ) \\ の固有値と固有ベクトルを求める. \\ |A − λI| & = & | \begin{matrix}3 − λ & 1 & 2 \\ 1 & 3 − λ & 1 \\ 2 & 1 & 3 − λ \end{matrix} | \\ = & − | \begin{matrix}1 & 3 − λ & 1 \\ 3 − λ & 1 & 2 \\ 2 & 1 & 3 − λ \end{matrix} | \\ = & − | \begin{matrix}1 & 3 − λ & 1 \\ 0 & 1 − (3 − λ)^{2} & λ − 1 \\ 0 & 2λ − 5 & −λ + 1 \end{matrix} | \\ = & − | \begin{matrix}1 − (3 − λ)^{2} & λ − 1 \\ 2λ − 5 & 1 − λ \end{matrix} | \\ = & −((1 − (3 − λ)^{2})(−λ + 1) − (λ − 1)(2λ − 5)) \\ = & −(λ − 1)(λ^{2} − 8λ + 13) \\ = & −(λ − 1)(λ − (4 + \sqrt{3}))(λ − (4 − \sqrt{3})) \\ ∴ |A − λI| = 0 ⟺ λ = 1, 4 ± \sqrt{3}. \end{matrix} ^{\begin{matrix}i) & \underline{λ = 1 のとき} \\ A − λI = ( \begin{matrix}2 & 1 & 2 \\ 1 & 2 & 1 \\ 2 & 1 & 2 \end{matrix} ) \\ だから, x := (x_{1}, x_{2}, x_{3})^{t} は, \\ ( \begin{matrix}2 & 1 & 2 \\ 1 & 2 & 1 \\ 2 & 1 & 2 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) \\ を満たす. 行列の基本変形を用いて, \\ ( \begin{matrix}1 & 0 & 1 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) \\ ∴ \{ \begin{matrix}x_{1} + x_{3} = 0 \\ x_{2} = 0 \end{matrix} \\ ∴ (x_{1}, x_{2}, x_{3})^{t} = t(1, 0, −1)^{t}. \\ よって, 固有ベクトルは, (1, 0, −1)^{t}. \\ ii) & \underline{λ = 4 + \sqrt{3} のとき} \\ A − λI = ( \begin{matrix}−1 − \sqrt{3} & 1 & 2 \\ 1 & −1 − \sqrt{3} & 1 \\ 2 & 1 & −1 − \sqrt{3} \end{matrix} ) \\ だから, x := (x_{1}, x_{2}, x_{3})^{t} は, \\ ( \begin{matrix}−1 − \sqrt{3} & 1 & 2 \\ 1 & −1 − \sqrt{3} & 1 \\ 2 & 1 & −1 − \sqrt{3} \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) \\ を満たす. 行列の基本変形を用いて, \\ ( \begin{matrix}1 & 0 & −1 \\ 0 & 1 & −1 − \sqrt{3} \\ 0 & 0 & 0 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) \\ ∴ \{ \begin{matrix}x_{1} − x_{3} = 0 \\ x_{2} + (1 − \sqrt{3})x_{3} = 0 \end{matrix} \\ ∴ (x_{1}, x_{2}, x_{3})^{t} = t(1, \sqrt{3} − 1, 1)^{t}. \\ よって, 固有ベクトルは, (1, \sqrt{3} − 1, 1)^{t}. \\ iii) & \underline{λ = 4 − \sqrt{3} のとき} \\ A − λI = ( \begin{matrix}−1 − \sqrt{3} & 1 & 2 \\ 1 & −1 − \sqrt{3} & 1 \\ 2 & 1 & −1 − \sqrt{3} \end{matrix} ) \end{matrix}}

だから, x := (x_{1}, x_{2}, x_{3})^{t} は, ; ( \begin{matrix}−1 + \sqrt{3} & 1 & 2 \\ 1 & −1 + \sqrt{3} & 1 \\ 2 & 1 & −1 + \sqrt{3} \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) ; を満たす. 行列の基本変形を用いて, ; ( \begin{matrix}1 & 0 & −1 \\ 0 & 1 & −1 + \sqrt{3} \\ 0 & 0 & 0 \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) ; ∴ \{ \begin{matrix}x_{1} − x_{3} = 0 \\ x_{2} + (1 + \sqrt{3})x_{3} = 0 \end{matrix} ; ∴ (x_{1}, x_{2}, x_{3})^{t} = t(1, \sqrt{3} − 1, 1)^{t}. ; よって, 固有ベクトルは, (1, \sqrt{3} − 1, 1)^{t}. 1.10 特別な行列

定義 1.10.1 行列 A := (a_{i}j) に対して,

1. A^{t} := (a_{ji}) を A の転置行列 (transposed matrix) という.

2. \overline{A} := (\overline{a_{i}j}) を共役行列 (conjugate matrix) という. ここで, \overline{a_{i}j} は, a_{i}j の共役複素数である.

3. A^{∗} := (\overline{A})^{t} = \overline{A^{t}} = (\overline{a_{ji}}) を A の随伴行列 (adjoint matrix) という.

定理 1.10.1 1. (A^{t})^{t} = A, (A^{∗})^{∗} = A; 2. (A + B)^{t} = A^{t} + B^{t};

3. (aA)^{t} = aA^{t};

4. (AB)^{t} = B^{t}A^{t}, (AB)^{∗} = B^{∗}A^{∗}.

定義 1.10.2 1. A が正規行列 (normal matrix) ⟺

AA^{∗} = A^{∗}A.

2. A がユニタリ行列 (unitary matrix) ⟺ AA^{∗} = A^{∗}A = I.

3. A が自己共役行列 (self-adjoint matrix) またはエルミート行列 ⟺ A^{∗} = A.

4. A が反エルミート行列 (anti-Hermitian matrix) ⟺ A^{∗} = −A.

特に, 成分がすべて実数のとき,

1. A が直交行列 (orthogonal matrix) ⟺ AA^{t} = A^{t}A = I.

2. A が対称行列 (symmetric matrix) ⟺ A^{t} = A.

3. A が交代行列 (alternate matrix) ⟺ A^{t} = −A.

1.11 行列の対角化 ; 定義 1.11.1 (対角行列) 正方行列 A に対して, ある正則 ; な行列 P が存在して, A が ; P^{−1}AP = ( \begin{matrix}d_{1} & & & & O \\ & . & . & . \\ O & & & & d_{n} \end{matrix} ) ; の形に変形できるとき, A は対角化可能であるといい, 右 ; 辺の形の行列を一般に対角行列という. ; 定理 1.11.1 λ_{1}, ⋯, λ_{n} を n 次正方行列 A の固有値とい ; う. このとき, あるユニタリ行列 U が存在して, A は ; U^{−1}AU = ( \begin{matrix}λ_{1} & & & & ∗ \\ & . & . & . \\ O & & & & λ_{n} \end{matrix} ) ; の形に変形できる. 右辺の形の行列を一般に三角行列と ; いう. ; 定理 1.11.2 A が正規行列のとき, ; A が三角行列 ⟹ A が対角行列 ; である. ; 対角化手順 ; A が正規行列であれば, 固有値 λ_{1}, ⋯, λ_{n}, 固有ベクト ; ル u_{1}, ⋯, u_{n} を求め, U := (u_{1}, ⋯, u_{n}) とおけば, U は ; ユニタリ行列となり, ; U^{−1}AU = ( \begin{matrix}λ_{1} & & & & O \\ & . & . & . \\ O & & & & λ_{n} \end{matrix} ) ; となる. ; 例 1.11.1 ; A := ( \begin{matrix}12 + 2i & −6 + 4i \\ −6 + 4i & 3 + 8i \end{matrix} ) ; を対角化するためのユニタリ行列 U を求める. ; A が正規行列であれば, U^{−1}AU を三角行列にすれば対 ; 角行列になる. ^{\begin{matrix}|A − λI| & = & | \begin{matrix}(12 − λ) + 2i & −6 + 4i \\ −6 + 4i & (3 − λ) + 8i \end{matrix} | \\ = & ((12 − λ) + 2i)((3 − λ) + 8i) − (−6 + 4i)^{2} \\ = & λ^{2} − (15 + 10i)λ + 150i \\ = & (λ − 15)(λ − 10i) \\ よって, A の固有値は λ = 15, 10i. \\ i) & \underline{λ = 15 のとき} \\ 固有ベクトル u_{1} := (x + yi, z + wi)^{t} は, \\ (A−λI)u_{1} = ( \begin{matrix}−3 + 2i & −6 + 4i \\ −6 + 4i & −12 + 8i \end{matrix} ) ( \begin{matrix}x + yi \\ z + wi \end{matrix} ) = 0 \\ を満たす. \\ \{ & \begin{matrix}(−3x − 6z) + (2y + 4w)i = 0 \\ (−6x − 12z) + (4y + 8w)i = 0 \end{matrix} \\ ∴ x + 2z = 0, y + 2w = 0. \\ ∴ u_{1} = (−2, 1)^{t}/\sqrt{5}. \\ ii) & \underline{λ = 10i のとき} \\ 同様に, 固有ベクトル u_{2} = (1, 2)^{t}/\sqrt{5} を得る. \\ よって, \\ U = \frac{1}{\sqrt{5}} ( \begin{matrix}−2 & 1 \\ 1 & 2 \end{matrix} ) . \\ 実際, 行列 U はユニタリ行列で \\ U^{−1}AU & = & U^{−1}(Au_{1}, Au_{2}) \\ = & U^{−1}(15u_{1}, 10iu_{2}) \\ = & U^{−1} · \frac{1}{\sqrt{5}} ( \begin{matrix}−2 · 15 & 1 · 10i \\ 1 · 15 & 2 · 10i \end{matrix} ) \\ = & U^{−1} \frac{1}{\sqrt{5}} ( \begin{matrix}−2 & 1 \\ 1 & 2 \end{matrix} ) ( \begin{matrix}15 & 0 \\ 0 & 10i \end{matrix} ) \\ = & U^{−1}U ( \begin{matrix}15 & 0 \\ 0 & 10i \end{matrix} ) \\ = & ( \begin{matrix}15 & 0 \\ 0 & 10i \end{matrix} ) . \end{matrix}}

第2章微分方程式

2.1 1 階常微分方程式

変数分離形

g(y)dy = f(x)dx の形に変形できるものは, この形に変形して積分する. 例 2.1.1 (1 + x)y + (1 − y)xy′ = 0 を解く.

移項して, (1 − y)xy′ = −(1 + x)y より,

\frac{1 − y}{y} dy = −\frac{1 + x}{x}dx.

両辺を積分して,

∫ \frac{1 − y}{y} dy = − ∫ \frac{1 + x}{x}dx,

∴ log y − y = − log x − x + C′. ∴ log xy = y − x + C′. ∴ xy = Ce^{y−x}.

同次形その 1

dy/dx = f(y/x) は, y/x = u とおく. 例 2.1.2 y^{2} + (x^{2} − xy)y′ = 0 を解く.

変形すると,

\frac{dy}{dx} = −\frac{y^{2}}{x^{2} − xy} = −\frac{y^{2}/xy}{(x^{2} − xy)/xy} = \frac{y/x}{1 − x/y} .

y/x = u とおき, この式の両辺を x で微分すると,

\frac{du}{dx} = \frac{(dy/dx)x − y}{x^{2}} = \frac{1}{x} (\frac{dy}{dx} − \frac{y}{x})
= \frac{1}{x} (\frac{u}{1 − 1/u} − u) = \frac{1}{x} \frac{u − u(1 − 1/u)}{1 − 1/u}
= \frac{1}{x} \frac{1}{1 − 1/u} = \frac{1}{x} \frac{u}{u − 1}.

変形して, ((u − 1)/u)du = (1/x)dx. 両辺積分して,

∫ \frac{u − 1}{u}du = ∫ \frac{1}{x}dx. ∴ u − log u = log x + C′.

∴ u = log ux + C′. ∴ log y = u − C′.

∴ y = Ce^{y/x}.

同次形その 2

\frac{dy}{dx} = f (\frac{a′x + b′y + c}{ax + by + c}) (a′b ≠ ab′) は, x = X +

x_{0}, y = Y + y_{0} とおく.

同次形その 3

\frac{dy}{dx} = f (\frac{k(ax + by) + c′}{ax + by + c} ) は, ax + by = u とおく.

例 2.1.3

\frac{dy}{dx} = \frac{6x − 2y − 7}{3x − y + 4}

を解く.

\frac{dy}{dx} = \frac{2(3x − y) − 7}{(3x − y) + 4} = \frac{2u − 7}{u + 4} (u := 3x − y)

より,

\frac{du}{dx} = 3 − \frac{dy}{dx} = \frac{3(u + 4) − (2u − 7)}{u + 4} = \frac{u + 19}{u + 4}.

変形して,

\frac{u + 4}{u + 19}du = dx, ∴ ∫ \frac{u + 4}{u + 19}du = ∫ dx.

u + 19 = w とおいて, ∫ \frac{w − 15}{w}dw = ∫ dx.

∴ (u + 19) − 15 log(u + 19) = x. ∴ (3x − y + 19) − 15 log(3x − y + 19) = x.

∴ 3x − y − 15 log(3x − y + 19) = C.

線形常微分方程式

dy/dx = P (x)y + Q(x) は, 両辺に exp (− ∫ P (x)dx) をかける.

例 2.1.4 t^{2}(dx/dt) − 2tx = 3 を解く.

両辺を t^{2} で割って, dx/dt − (2/t)x = 3/t^{2}. 両辺に exp (− ∫ (2/t)dt) をかけて,

e^{− ∫ (2/t)dt} \frac{dx}{dt} − e^{− ∫ (2/t)dt} \frac{2}{t}x = e^{− ∫ (2/t)dt} \frac{3}{t^{2}} .

e^{− ∫ (2/t)dt} \frac{dx}{dt} − \frac{2}{t}e^{− ∫ (2/t)dt}x = e^{− ∫ (2/t)dt} \frac{3}{t^{2}} .

e^{− ∫ (2/t)dt} \frac{dx}{dt} + \frac{d}{dt} (e^{− ∫ (2/t)dt}) x = e^{− ∫ (2/t)dt} \frac{3}{t^{2}} .

\frac{d}{dt} (e^{− ∫ (2/t)dt}x) = e^{− ∫ (2/t)dt} \frac{3}{t^{2}} .

e^{− ∫ (2/t)dt}x = ∫ e^{− ∫ (2/t)dt} \frac{3}{t^{2}} + C.

x = e^{∫ (2/t)dt} (∫ e^{− ∫ (2/t)dt} \frac{3}{t^{2}} dt + C)

ここで, exp (− ∫ (2/t)dt) = t^{−2}, exp (∫ (2/t)dt) = t^{2} だから,

x = t^{2} (∫ t^{−2} \frac{3}{t^{2}} dt + C) = t^{2} (3\frac{dt}{t^{4}} + C)
= t^{2} (3\frac{1}{−3t^{3}} + C) = −\frac{1}{t} + Ct^{2}.

2.2 2 階線形常微分方程式

定数係数の斉次線形常微分方程式

d^{2}y/dx^{2} + a(dy/dx) + by = 0 は,

(\frac{d^{2}}{dx^{2}} + a\frac{d}{dx} + b) y = 0

と変形し, d/dx = λ とおくと, (λ^{2} + aλ + b)y = 0. λ^{2} + aλ + b = 0 の解 λ = λ_{1}, λ_{2} が,

i) 異なる 2 実数のとき, y = C_{1}e^{λ_{1}x} + C_{2}e^{λ_{2}x}; ii) 重解のとき, y = (C_{1} + C_{2}x)e^{λ_{1}x}; iii) 異なる 2 虚数 (λ_{1} := α + iβ, λ_{2} := α − iβ) のとき,

y = e^{αx}(C_{1} cos βx + C_{2} sin βx).

第3章解析学

3.1 級数の和

定義 3.1.1 (収束) 無限級数 ∑_{n=1}^{∞} a_{n} = a_{1} + a_{2} + ⋯ に対

して, 部分和 S_{n} := a_{1}+a_{2}+⋯+a_{n} の極限 S := lim_{n→∞} S_{n}

が存在するとき, 級数 ∑_{n=1}^{∞} a_{n} は収束するといい, S を級

数の和という.

次の定理の対偶より, 級数の収束の吟味は, lim_{n→∞} a_{n} = 0 の場合だけ考えればよい.

定理 3.1.1 ∑_{n=1}^{∞} a_{n}が収束 ⟹ lim_{n→∞} a_{n} = 0.

注意この逆は成立しない.

正項級数

各項がすべて正の級数を正項級数という.

例 3.1.1 級数 1 + 1/2 + 1/3 + 1/4 + ⋯ は, 発散する. 証明部分和 S_{n} を考える. 2^{m} = n とおくと,

S_{n} = 1 + \frac{1}{2} + (\frac{1}{3} + \frac{1}{4}) + (\frac{1}{5} + ⋯ \frac{1}{8})

+ ⋯ + (\frac{1}{n/2 + 1} + ⋯ \frac{1}{n})

> 1 + \frac{1}{2} + (\frac{1}{4} + \frac{1}{4}) + (\frac{1}{8} + ⋯ \frac{1}{8})

+ ⋯ + (\frac{1}{2^{m}} + ⋯ \frac{1}{2^{m}} )

= 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + ⋯ + \frac{1}{2}
= 1 + \frac{m}{2} → ∞. (m → ∞)

交項級数

奇数番目の項が正, 偶数番目の項が負の級数を交項級数という. 交項級数は,

|a_{1}| > |a_{2}| > ⋯ かつ lim_{n→∞} a_{n} = 0

ならば, 収束する.

例 3.1.2 級数 1 − 1/2 + 1/3 − 1/4 + ⋯ は, 収束する. 証明部分和 S_{n} を考えると,

S_{2n} = (1 − \frac{1}{2}) + (\frac{1}{3} − \frac{1}{4}) + ⋯ + (\frac{1}{2n − 1} − \frac{1}{2n})

は n が増加するについて増大し,

S_{2n} = 1 − (\frac{1}{2} − \frac{1}{3}) − (\frac{1}{4} − \frac{1}{5}) − ⋯ − \frac{1}{2n} < 1

だから, 上に有界である. ゆえに, lim_{n→∞} S_{2n} = S が存在する. ここで,

S_{2n+1} = S_{2n} + \frac{1}{2n + 1} → S + 0 = S (n → ∞)

より, lim_{n→∞} S_{n} = S. よって, 収束.

定義 3.1.2 (絶対収束) 級数 ∑ a_{n} に対して, ∑ |a_{n}| が収束するとき, ∑ a_{n} は絶対収束するという.

定理 3.1.2 級数 ∑ a_{n}が絶対収束 ⟹ ∑ a_{n}は収束する.

定義 3.1.3 (条件収束) 級数 ∑ a_{n} に対して, ∑ |a_{n}| は発散するが ∑ a_{n} は収束するとき, ∑ a_{n} は条件収束するという.

例 3.1.3 前述の級数 1 − 1/2 + 1/3 − 1/4 + ⋯ は, 条件収束する.

3.2 微分

定理 3.2.1 (ライプニッツの公式)f(x), g(x) が x_{0} で n 回微分可能であるとき,

(fg)^{(n)}(x_{0}) = ∑_{k=0}^{n}_{n}C_{k}f^{(k)}(x_{0})g^{(n−k)}(x_{0}).

例 3.2.1

(e^{x} log(1 + x))^{(n)}
= _{n}C_{0}(e^{x})(log(1 + x))^{(n)} +_{n}C_{1}(e^{x})′(log(1 + x))^{(n−1)}
+ ⋯ +_{n}C_{n}(e^{x})^{(n)}(log(1 + x)).

ここで, (e^{x})′ = (e^{x})′′ = ⋯ = (e^{x})^{(n)} = e^{x}, (log(1 + x))′ = 1/(1 + x), (log(1 + x))′′ = (1/(1 + x))′ = −1/(1 + x)^{2}, (log(1 + x))′′′ = (−1/(1 + x)^{2})′ = 2/(1 + x)^{3},

⋮

(log(1+x))^{(k)} = (−1)^{n−1} ·(k −1)(k −2) ⋯ 3·2/(1+x)^{k} より, 0 ≤ k ≤ n − 1 に対して,

nC_{k}(e^{x})^{(k)}(log(1 + x))^{(n−k)}
= \frac{n!}{k!(n − k)!}e^{x} \frac{(−1)^{n−k−1}(n − k − 1)!}{(1 + x)^{n−k}}
= (−1)^{n−k−1} \frac{n!}{(n − k) · k!} \frac{1}{(1 + x)^{n−k}} e^{x}.

よって,

(e^{x} log(1 + x))^{(n)}
= \{log(1 + x) + \frac{n}{1 + x} − \frac{n(n − 1)}{2(1 + x)^{n}}

+ ⋯ + (−1)^{n−1} \frac{n!}{(1 + x)^{n}} \} e^{x}.

定理 3.2.2 (テイラーの公式)[x_{0}, x] で f^{(n−1)} が連続で, (x_{0}, x) で f^{(n)} が存在するならば, ξ ∈ (x_{0}, x) が存在し,

f(x) = f(x_{0}) + ∑_{k=1}^{n−1} \frac{f^{(k)}(x_{0})}{k!}(x − x_{0})^{k} + R_{n}(x).

ここで, R_{n}(x) := \frac{f^{(n)}(ξ)}{n!}(x − x_{0})^{n}.

定理 3.2.3 (マクローリンの公式)[0, x] で f^{(n−1)} が連続で, (0, x) で f^{(n)} が存在するならば, θ ∈ (0, 1) が存在し,

f(x) = f(0) + ∑_{k=1}^{n−1} \frac{f^{(k)}(0)}{k!}x^{k} + \frac{f^{(n)}(θx)}{n!}x^{n}.

証明テイラーの公式で x_{0} = 0 とおけばよい.

例 3.2.2

e^{x} = e^{0} + \frac{e^{0}}{1} x + \frac{e^{0}}{2} x^{2} + ⋯ + \frac{e^{0}}{n!} x^{n} + ⋯
= 1 + x + \frac{1}{2} x^{2} + ⋯ + \frac{1}{n!} x^{n} + · · · .
cos x = cos 0 + \frac{− sin 0}{1} x + \frac{− cos 0}{2} x^{2} + \frac{sin 0}{6} x^{3}

+ \frac{cos 0}{24} x^{4} + ⋯

= 1 − \frac{1}{2} x^{2} + \frac{1}{24} x^{4} − ⋯ + (−1)^{n} \frac{1}{(2n)!} x^{2n} + · · · .
sin x = sin 0 + \frac{cos 0}{1} x + \frac{− sin 0}{2} x^{2} + \frac{− cos 0}{6} x^{3}

+ \frac{sin 0}{24} x^{4} + ⋯

= x − \frac{1}{6} x^{3} + ⋯ + (−1)^{n} \frac{1}{(2n + 1)!} x^{2n+1} + · · · .
log(1 + x) = log 1 + \frac{1/(1 + 0)}{1} x + \frac{−1/(1 + 0)^{2}}{2} x^{2}

+ ⋯ + \frac{(−1)^{n−1}(n − 1)!/(1 + 0)^{n}}{n!} x^{n} + ⋯

= x − \frac{1}{2} x^{2} + ⋯ + (−1)^{n−1} \frac{1}{n} x^{n} + · · · .

17

第4章複素解析 ; 4.1 複素微分 ; 定義 4.1.1 (形式的複素微分)f(z) := u(z)+iv(z) (z := ; x + iy) が C^{1} 級であるとき, ; \frac{∂f}{∂z} := \frac{1}{2} (\frac{∂f}{∂x} − i\frac{∂f}{∂y} ) , \frac{∂f}{∂z̄} := \frac{1}{2} (\frac{∂f}{∂x} + i\frac{∂f}{∂y} ) . ; 定義 4.1.2 (複素微分可能性)関数 f(z) が領域 G で定義 ; されているとき, G の点 z_{0} に対して, ; \frac{df}{dz} (z_{0}) := lim_{α→0} \frac{f(z_{0} + α) − f(z_{0})}{α} ; が存在するとき, f(z) は z_{0} において複素微分可能である ; という. ; 定理 4.1.1 (コーシー・リーマンの関係式) f(z) は G で ; C^{1} 級とする. G の点 z_{0} で f(z) が複素微分であるための ; 必要十分条件は, ; \frac{∂f}{∂z̄}(z_{0}) = 0 ; である. この式は, f(z) := u(z) + iv(z) とおけば, ; u_{x}(z_{0}) = v_{y}(z_{0}), u_{y}(z_{0}) = −v_{x}(z_{0}) ; と書くこともできる. また, このとき, ; \frac{df}{dz} (z_{0}) = \frac{∂f}{∂z} (z_{0}) ; が成り立つ. ; 定義 4.1.3 (正則関数) 領域 G において C^{1} 級で, 各点で ; 複素微分可能な関数を正則関数という. ; 定理 4.1.2 f(z) が領域 G で C^{1} 級であるとき, f(z) が ; G で正則であるための必要十分条件は, G の各点でコー ; シー・リーマンの関係式が成り立つことである. ^{\begin{matrix}4.2 複素積分 \\ 定義 4.2.1 (複素積分) 路 γ : z = φ(t) (a ≤ t ≤ b) に \\ よって定まる曲線を C とする. 関数 f(z) が C 上で連続 \\ であるとき, \\ ∫_{γ} f(z)dz := ∫_{a}^{b} f(φ(t))\frac{dφ(t)}{dt}dt \\ を f(z) の γ 上の複素積分という. \\ 定理 4.2.1 γ は区分的に滑らかな路とする. \\ 1. |f(z)| ≤ M ならば, \\ |∫_{γ} f(z)dz| ≤ ∫_{a}^{b} |f(φ(t))| |\frac{dφ(t)}{dt}| dt ≤ M ∫_{a}^{b} |\frac{dφ(t)}{dt}| dt. \\ 2. γ に対して逆向きの路 −γ について, \\ ∫_{−γ} f(z)dz = − ∫_{γ} f(z)dz. \\ 定義 4.2.2 xy 平面の領域 G の境界 ∂G が有限個の区分 \\ 的に滑らかな路からなるとき, G はよい領域であるという. \\ 定理 4.2.2 (コーシーの積分定理)G がよい領域で, f(z) \\ が\overline{G} で正則ならば, \\ ∫_{∂G} f(z)dz = 0 \\ が成り立つ. \\ 例 4.2.1 \\ ∫_{0}^{∞} \frac{sin x}{x}dx = \frac{π}{2} \\ を証明する. \\ f(z) := e^{iz}/z とおくと, z ≠ 0 で正則である. 0 < ε < \\ R として \\ γ_{−} & : & z = x (−R ≤ x ≤ −ε), \\ γ_{ε} & : & z = εe^{i(π−θ)} (0 ≤ θ ≤ π), \\ γ_{+} & : & z = x (ε ≤ x ≤ R), \\ γ_{R} & : & z = Re^{iθ} (0 ≤ θ ≤ π) \\ とおく. コーシーの積分定理より \\ ∫_{γ_{−}} f(z)dz + ∫_{γ_{ε}} f(z)dz + ∫_{γ_{+}} f(z)dz + ∫_{γ_{R}} f(z)dz = 0. \end{matrix}}

18 第 4 章複素解析この式に対して ε → 0, R → ∞ とすると

2iI + (−iπ) = 0

となることを示せばよい. ここで, I := ∫_{0}^{∞} \frac{sin x}{x}dx.

(第 1 項) + (第 3 項)= ∫_{−R}^{−ε} \frac{e^{ix}}{x} · 1 · dx + ∫_{ε}^{R} \frac{e^{i}x}{x} · 1 · dx
= ∫_{R}^{ε} \frac{e^{−ix}}{−x} (−dx) + ∫_{ε}^{R} \frac{e^{ix}}{x} dx
= ∫_{ε}^{R} \frac{−e^{−ix} + e^{ix}}{x} dx
= 2i ∫_{ε}^{R} \frac{−e^{−ix} + e^{ix}}{2ix} dx
= 2i ∫_{ε}^{R} \frac{sin x}{x}dx
→ 2iI. (ε → 0, R → ∞)

(第 2 項) = ∫_{γ_{ε}} \frac{1}{z}dz + ∫_{γ_{ε}} \frac{e^{iz} − 1}{z}dz.

∫_{γ_{ε}} \frac{1}{z}dz = ∫_{0}^{π} \frac{1}{εe^{i(π−θ)}} (−iεe^{i(π−θ)})dθ = −iπ.

|∫_{γ_{ε}} \frac{e^{iz} − 1}{z}dz| ≤ ∫_{0}^{π} |\frac{e^{iz} − 1}{z}| |ε(−i)e^{i(π−θ)}|dθ
= ε ∫_{0}^{π} |\frac{e^{iz} − 1}{z}| dθ.

ここで, ε が十分に小さければ |(e^{iz} − 1)/z| ≤ 2 だから,

|∫_{γ_{ε}} \frac{e^{iz} − 1}{z}dz| ≤ 2πε → 0. (ε → 0)

さらに,

(第 4 項) = ∫_{0}^{π} \frac{e^{iRe^{iθ}}}{Re^{iθ}} (iRe^{iθ})dθ = i ∫_{0}^{π} e^{iR cos θ}e^{−R sin θ}dθ

だから,

|(第 4 項)| ≤ ∫_{0}^{π} |e^{iR cos θ}| · |e^{−R sin θ}|dθ
= ∫_{0}^{π} |e^{−R sin θ}|dθ → 0. (R → ∞)

よって, 2iI + (−iπ) = 0. ∴ I = π/2. 定理 4.2.3 (コーシーの積分公式その 1)G がよい領域で, f(z) が\overline{G} で正則ならば

f(z) = \frac{1}{2πi} ∫_{∂G} \frac{f(ζ)}{ζ − z} dζ (z ∈ G)

が成り立つ.

定理 4.2.4 (コーシーの積分公式その 2)G がよい領域 ; で, f(z) が\overline{G} で正則ならば ; f^{(k)}(z) = \frac{k!}{2πi} ∫_{∂G} \frac{f(ζ)}{(ζ − z)^{k+1}} dζ (z ∈ G) ; が成り立つ.

4.3 級数 ; 定義 4.3.1 (べき級数) 複素数列 \{a_{n}\} に対して, ; ∑_{n=0}^{∞} a_{n}(z − z_{0})^{n} = a_{0} + a_{1}(z − z_{0}) + a_{2}(z − z_{0})^{2} + ⋯; をべき級数といい, z_{0} をその中心という. ; 定理 4.3.1 (テイラー級数展開)f(z) が領域 |z−z_{0}| < R ; で正則であるとき, f(z) は次のべき級数に展開できる: ; f(z) = ∑_{n=0}^{∞} a_{n}(z − z_{0})^{n}, ; ただし, ; a_{n} := \frac{1}{2πi} ∫_{|ζ−z_{0}|=r} \frac{f(ζ)}{(ζ − z_{0})^{n+1}} dζ. (0 < r < R) ; 定理 4.3.2 (ローラン展開定理)0 ≤ R_{1} ≤ R_{2} ≤ +∞ と ; する. f(z) が円環領域 R_{1} < |z − z_{0}| < R_{2} で正則である ; とき, ; f(z) = \underbrace{∑_{m=1}^{∞} \frac{a_{−m}}{(z − z_{0})^{m}}}_{主要部}+ ∑_{n=0}^{∞} a_{n}(z − z_{0})^{n}, ; ただし, ; a_{n} := \frac{1}{2πi} ∫_{|ζ−z_{0}|=r} \frac{f(ζ)}{(ζ − z_{0})^{n+1}} dζ ; (R_{1} < r < R_{2}, n = 0, ±1, ±2, ⋯) ; が成り立ち, f(z) のローラン級数という. 簡単のため, ; f(z) = ∑_{n=−∞}^{∞} a_{n}(z − z_{0})^{n} ; と書くこともある. ; 注意負べきの項がないとき, ローラン級数はテイラー級 ; 数に一致する. ; よく知られた展開式 ; 1. 1/(1 − z) = 1 + z + z^{2} + ⋯ + z^{n} + ⋯ (|z| < 1); ; 2. 1/(1+z) = 1−z+z^{2}−⋯+(−1)^{n}z^{n}+⋯ (|z| < 1); ; 3. e^{z} = 1+z+(1/2!)z^{2}+⋯+(1/n!)z^{n}+⋯ (|z| < ∞). 4.4 留数

定義 4.4.1 (留数) f(x) が 0 < |z − z_{0}| < R で正則であるとき, 0 < r < R なる r について,

\frac{1}{2πi} ∫_{|z−z_{0}|=r} f(z)dz

を f(z) の z_{0} における留数といい, Res[f; z_{0}] で表す.

定理 4.4.1 f(z) が z_{0} で N 位の極を持つとき,

Res[f; z_{0}] = \frac{1}{(N − 1)!} lim_{z→z_{0}} \frac{d^{N−1}}{dz^{N−1}} [(z − z_{0})^{N}f(z)]

が成り立つ. 例 4.4.1

f(z) := \frac{z^{2} + z + 1}{z^{2}(z − 1)}.

f(z) は, z = 0 で 2 位の極, z = 1 で 1 位の極を持つ.

Res[f; 0] = lim_{z→0} \frac{d}{dz} [z^{2} · \frac{z^{2} + z + 1}{z^{2}(z − 1)}]
= lim_{z→0} \frac{d}{dz} [\frac{z^{2} + z + 1}{z − 1}] = lim_{z→0} \frac{z^{2} − 2z − 2}{(z − 1)^{2}}
= −2,
Res[f; 1] = lim_{z→1}(z − 1)\frac{z^{2} + z + 1}{z^{2}(z − 1)} = lim_{z→1} \frac{z^{2} + z + 1}{z^{2}}
= 3.

定理 4.4.2 f(z) := g(z)/h(z) が z_{0} で 1 位の極を持つとき,

Res[f, z_{0}] = \frac{g(z_{0})}{h′(z_{0})}

が成り立つ.

例 4.4.2 前述の f(z) := \frac{z^{2} + z + 1}{z^{2}(z − 1)} において,

Res[f; 1] = \frac{1^{2} + 1 + 1}{3 · 1^{2} − 2 · 1^{2}} = 3.

定理 4.4.3 (留数定理) G がよい領域で, f(z) が, 特異点 a_{1}, ⋯, a_{m} を除く\overline{G} で正則ならば,

∫_{∂G} f(z)dz = 2πi ∑_{k=1}^{m} Res[f; a_{k}]

が成り立つ. 例 4.4.3

I := ∫_{−∞}^{∞} \frac{1}{x^{6} + 1}dx

を求める.

γ_{x} : z = x (−R ≤ x ≤ R),
γ_{R} : z = Re^{iθ} (0 ≤ θ ≤ π)

とおく. f(z) := 1/(x^{6} + 1) の特異点のうち, γ_{x} と γ_{R} からなる閉曲線の内部に存在するのは, R を十分に大きく取れば, z = i, exp(π/6), exp(5π/6) である. これらの留数は, それぞれ, −i/6, exp(−5π/6)/6, exp(−π/6)/6 だから, 留数定理より,

∫_{−R}^{R} \frac{1}{x^{6} + 1}dx + ∫_{γ_{R}} \frac{1}{z^{6} + 1}dz

= 2πi (−\frac{i}{6} + \frac{e^{−5π/6}}{6} + \frac{e^{−π/6}}{6} ) .

(右辺) = 2π/3,

|∫_{γ_{R}} \frac{1}{z^{6} + 1}dz| ≤ ∫_{γ_{R}} \frac{1}{|z^{6}| + 1}|dz| = ∫_{0}^{π} \frac{1}{R + 1}Rdθ
= \frac{(π − 0)R}{R + 1} → 0 (R → ∞)

より, R → ∞ とすれば, I = 2π/3 を得る.

4.5 定積分

i) f(z) が,

(1) 実軸上に極を持たない,

(2) z → ∞ のとき zf(z) → 0,

(3) 上反平面で有限個の極 a_{k} を除いて正則ならば,

∫_{−∞}^{∞} f(x)dx = 2πi ∑_{k} Res[f; a_{k}].

例 4.5.1

1. ∫_{−∞}^{∞} \frac{1}{x^{6} + 1}dx = \frac{2}{3}π.

2. ∫_{−∞}^{∞} \frac{1}{x^{4} + 1}dx = \frac{π}{\sqrt{2}}.

3. ∫_{−∞}^{∞} \frac{1}{(x^{2} + 1)^{3}} dx = \frac{3}{16}π.

4. ∫_{−∞}^{∞} \frac{1}{(x^{2} + 1)^{2}} dx = \frac{π}{2} .

5. ∫_{−∞}^{∞} \frac{1}{(x^{2} + a^{2})(x^{2} + b^{2})}dx = \frac{π}{ab(a + b)}.

ii) f(z) が,

(1) 実軸上に極を持たない,

(2) z → ∞ のとき f(z) → 0,

(3) 上反平面で有限個の極 a_{k} を除いて正則ならば,

∫_{−∞}^{∞} f(x)e^{ix}dx = 2πi ∑_{k} Res[f(z)e^{iz}; a_{k}],

∫_{−∞}^{∞} f(x) cos xdx = Re [2πi ∑_{k} Res[f(z)e^{iz}; a_{k}]] ,

∫_{−∞}^{∞} f(x) sin xdx = Im [2πi ∑_{k} Res[f(z)e^{iz}; a_{k}]] .

例 4.5.2

1. ∫_{0}^{∞} \frac{x sin x}{x^{2} + 1}dx = \frac{π}{2e}.

2. ∫_{0}^{∞} \frac{x sin x}{(x^{2} + 1)^{2}} dx = \frac{π}{4e}.

3. ∫_{−∞}^{∞} \frac{x sin x}{x^{4} + 1}dx = \frac{iπ}{e^{1/\sqrt{2}}} sin \frac{1}{\sqrt{2}}.

4. ∫_{0}^{∞} \frac{x sin 2x}{x^{4} + 1}dx = \frac{iπ}{2e^{1/\sqrt{2}}} sin \sqrt{2}.

第5章信号処理 ; 5.1 連続時間のフーリエ変換 ; 定義 5.1.1 (たたみ込み) 2 つの信号 x(t) と h(t) に対し ; て, ; x(t) ∗ h(t) := ∫_{−∞}^{+∞} x(τ)h(t − τ)dτ ; をたたみ込みという. ; 定義 5.1.2 (デルタ関数) デルタ関数 δ(t) を次式で定義 ; する: ; δ(t) := \{ \begin{matrix}+∞ & (t = 0) \\ 0 & (t ≠ 0) \end{matrix} ; かつ任意の ϵ > 0 に対して, ; ∫_{−ϵ}^{ϵ} δ(t)dt = 1. ; このとき, ある時刻 t_{0} の連続時間信号 x(t) は, ; x(t_{0}) = x(t_{0}) ∗ δ(t_{0}) = ∫_{−∞}^{+∞} x(t)δ(t_{0} − t)dt ; と表すことが出来る. ; 定義 5.1.3 連続時間信号 x(t) のフーリエ変換 X(ω) は ; X(ω) := ∫_{−∞}^{+∞} x(t)e^{−jωt}dt ; で定義される. この式を変形して得られる式: ; x(t) = \frac{1}{2π} ∫_{−∞}^{+∞} X(ω)e^{jωt}dω ; を逆フーリエ変換と呼ぶ. ; 連続時間信号 x(n) のフーリエ変換および逆フーリエ変 ; 換を F[x(n)], F^{−1}[x(n)] で表すことがある. ; 定理 5.1.1 F[x(t) ∗ h(t)] = X(ω)H(ω).

5.2 離散フーリエ変換

単位インパルス

δ := \{ \begin{matrix}1 & (n = 0) \\ 0 & (n ≠ 0) \end{matrix}

任意の離散時間信号は, 単位インパルスを使って

x(n) = ∑_{k=−∞}^{∞} x(k)δ(n − k),

ただし,

δ(n − k) := \{ \begin{matrix}1 & (n = k) \\ 0 & (n ≠ k) \end{matrix}

と表すことができる.

標本化

連続時間信号 x_{a}(t) の標本化された信号 x(t) は, インパルス列:

δ_{s}(t) := ∑_{n=−∞}^{+∞} δ(t − nT)

を用いて

x(t) = x_{a}(t)δ_{s}(t) = ∑_{n=−∞}^{+∞} x_{a}(t)δ(t − nT)

と表すことができる. 定理 5.2.1 (シャノンの標本化定理)連続時間信号 x_{a}(t) が帯域 Ω_{c}[rad] に制限されているとき, 標本化周波数 Ω_{s}[rad/sec] が

Ω_{s} > 2Ω_{c}

を満たせば, 標本 x(n) から連続時間信号 x_{a}(t) を復元できる.

5.3 z 変換

定義 5.3.1 (z 変換) 信号 x(n) に対して,

X(z) := ∑_{n=0}^{∞} x(n)z^{−n}

を {x(n)} の z 変換 (z-transform) といい, Z{x(n)} または X(z) で表す.

定義 5.3.2 (収束領域) X(z) が収束する z の範囲を X(z) の収束領域という.

第6章エントロピー

6.1 エントロピーの定義

定義 6.1.1 (エントロピー)完全事象系:

X := ( \begin{matrix}x_{1} & ⋯ & x_{n} \\ p_{1} & ⋯ & p_{n} \end{matrix} )

に対して,

S(p) := − ∑ i = 1^{n}p_{i} log p_{i}

を系 (X, p) のエントロピーという. 定義 6.1.2 (X, p), (Y, q) を完全事象系とする. このとき, 複合事象系 (X × Y, r) のエントロピーは,

S(X × Y) := − ∑_{i,j} p(x_{i}, y_{j}) log p(x_{i}, y_{j})

で与えられる. 定義 6.1.3 (条件付きエントロピー)条件付き確率 p(x|y) に対するエントロピー:

S(X|Y) := − ∑_{x∈X,y∈Y} p(x, y) log p(x|y)

を条件付きエントロピーと呼ぶ. 定義 6.1.4 (相対エントロピー)p, q を事象の集合 X に対する確率分布とするとき,

S(p|q) := ∑_{i=1}^{n} p_{i} log p_{i}/q_{i} (ただし p_{i} ≠ 0 ⟹ q_{i} ≠ 0)

を相対エントロピーと呼ぶ. 定義 6.1.5 (相互エントロピー)完全事象系 (X, p), (Y, q) に対して,

I(X, Y) := ∑_{x∈X,y∈Y} p(x, y) log \frac{p(x, y)}{p(x)p(y)}

を相互エントロピーと呼ぶ.

第7章数理論理学 ; 7.1 古典命題論理 ; 命題 (真偽の確定していることがら) と論理記号 ; ¬, ∧, ∨, ⊃ のみを扱う論理体系. ; ヒルベルト流公理系 ; • 公理 ; (⊃_{1}) A ⊃ (B ⊃ A); ; (⊃_{2}) (A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ C)); ; (⊃_{3}) ((A ⊃ B) ⊃ A) ⊃ A; ; (∧_{1}) A ∧ B ⊃ A; ; (∧_{2}) A ∧ B ⊃ B; ; (∧_{3}) (A ⊃ B) ⊃ ((A ⊃ C) ⊃ (A ⊃ B ∧ V)); ; (∨_{1}) A ⊃ A ∨ B; ; (∨_{2}) B ⊃ A ∨ B; ; (∨_{3}) (A ⊃ C) ⊃ ((B ⊃ C) ⊃ (A ∨ B ⊃ C)); ; (¬_{1}) (A ⊃ B) ⊃ ((A ⊃ ¬B) ⊃ ¬A); ; (¬_{2}) ¬A ⊃ (A ⊃ B). ; • 推論規則（分離規則） ; A, A ⊃ B が真なら, B も真である.

LK による証明

証明する論理式を A とすると, 式 “→ A” に対して以下の推論規則を逆に適用することで, 以下の公理を導く.

定義 7.1.1 (式) 論理式 A_{1}, ⋯, A_{m}, B_{1}, ⋯, B_{n} を

A_{1}, ⋯, A_{m} → B_{1}, ⋯, B_{n}

の形に繋げたものを式といい, A_{1}∧⋯∧A_{m} ⊃ B_{1}∨⋯∨B_{n} を意味する. なお, m, n は 0 でもよい.

定義 7.1.2 (推論規則) 式 S_{1}, ⋯, S_{n}, S を

\frac{S_{1} ⋯ S_{n}}{S}

の形にならべたものを推論規則といい, S_{1}, ⋯, S_{n} が正しいときに S も正しいことを意味する.

• LK の公理： A → A.

• LK の推論規則

増左\frac{Γ → Δ}{D, Γ → Δ}  増右\frac{Γ → Δ}{Γ → Δ, D}
減左\frac{D, D, Γ → Δ}{D, Γ → Δ}  減右\frac{Γ → Δ, D, D}{Γ → Δ, D}
換左\frac{Γ, C, D, Π → Δ}{Γ, D, C, Π → Δ}  換右\frac{Γ → Δ, C, D, Π}{Γ → Δ, D, C, Π}
⊃ 左\frac{Γ → Δ, A B, Π → Σ}{A ⊃ B, Γ, Π → Δ, Σ} ⊃ 右\frac{A, Γ → Δ, B}{Γ → Γ, A ⊃ B}
∧ 左\frac{A, Γ → Δ}{A ∧ B, Γ → Δ}  ∧ 右\frac{Γ → Δ, A Γ → Δ, B}{Γ → Δ, A ∧ B}
∨ 左\frac{A, Γ → Δ B, Γ → Δ}{A ∨ B, Γ → Δ} ∨ 右\frac{Γ → Δ, A}{Γ → Δ, A ∨ B}
¬ 左\frac{Γ → Δ, A}{¬A, Γ → Δ}  ¬ 右\frac{A, Γ → Δ}{Γ → Δ, ¬A}

例 7.1.1 1. A ⊃ B ⊃ A ⊃ A.

\frac{\frac{\frac{\frac{\frac{A → A}{A → A, B}}{→ A, A ⊃ B} A → A}{A ⊃ B ⊃ A → A, A}}{A ⊃ B ⊃ A → A}}{→ A ⊃ B ⊃ A ⊃ A}

2. ¬¬A ⊃ A.

\frac{\frac{\frac{A → A}{→ A, ¬A}}{¬¬A → A}}{→ ¬¬A ⊃ A}

7.2 古典述語論理

述語 (変数の内容が確定しないと真偽が確定しないことがら) と論理記号 ¬, ∧, ∨, ⊃, ∀, ∃ を扱う論理体系.

古典述語論理の公理系

ヒルベルト流の古典命題論理の公理系に, 次の限定記号の公理と限定記号の推論を追加する:

• 限定記号の公理 (∀_{1}) ∀xA(x) ⊃ A(t); (∃_{1}) A(t) ⊃ ∃xA(x).

• 限定記号の推論 (∀_{2}) C ⊃ A(a) ⟹ C ⊃ ∀xA(x); (∃_{2}) A(a) ⊃ C ⟹ ∃xA(x) ⊃ C.

古典述語論理の LK

次の 4 つの推論を追加する:

∀ 左\frac{A(t), Γ → Δ}{∀xA(x), Γ → Δ} ∀ 右\frac{Γ → Σ, A(a)}{Γ → Σ, ∀xA(x)}
∃ 左\frac{A(a), Γ → Δ}{∃xA(x), Γ → Δ} ∃ 右\frac{Γ → Σ, A(t)}{Γ → Σ, ∃xA(x)}

∀ 右と ∃ 左の下式には, 自由変数 a は現れない.

7.3 直観主義命題論理

排中律 (A ∨ ¬A が常に真) を認めない命題論理.

直観主義命題論理の公理は, 古典命題論理の公理から (⊃_{3}) を取り除いたものである.

LJ

LJ の公理は LK と同じ. 推論規則に関しては, LK の右辺の論理式の個数を高々1 つに制限したもの. 推論規則を以下に示す (Δ は高々1 つの論理式):

増左\frac{Γ → Δ}{D, Γ → Δ}  増右\frac{Γ →}{Γ → D}
減左\frac{D, D, Γ → Δ}{D, Γ → Δ}
換左\frac{Γ, C, D, Π → Δ}{Γ, D, C, Π → Δ}
⊃ 左\frac{Γ → A B, Π → Δ}{A ⊃ B, Γ, Π → Δ}  ⊃ 右\frac{A, Γ → B}{Γ → A ⊃}
∧ 左\frac{A, Γ → Δ}{A ∧ B, Γ → Δ}  ∧ 右\frac{Γ → A Γ → B}{Γ → A ∧ B}
∨ 左\frac{A, Γ → Δ B, Γ → Δ}{A ∨ B, Γ → Δ} ∨ 右\frac{Γ → A}{Γ → A ∨ B}
¬ 左\frac{Γ → A}{¬A, Γ →}  ¬ 右\frac{A, Γ →}{Γ → ¬A}

7.4 様相論理

• ◇A ：「A は可能である」

• □A ：「A は必然である」

定義 7.4.1 次の 3 条件で定まるものを様相論理の論理式という (これらの全体を WFF^{□} で表す):

(1) PVAR ⊆ WFF^{□} ;

(2) A, B ∈ WFF^{□} ⟹ A ⊃ B, A ∧ B, A ∨ B ∈ WFF^{□} ;

(3) A ∈ WFF^{□} ⟹ □A, ¬A ∈ WFF^{□} .

ここで, PVAR は命題変数全体の集合.

定義 7.4.2 1. ¬□¬A を ◇A と表す; 2. □(A ⊃ B) を A ≺ B と表す;

3. (A ≺ B) ∧ (B ≺ A) を A = B と表す.

体系 M

• 公理： (1) □A ⊃ A, (2) □(A ⊃ B) ⊃ (□A ⊃ □B).

• 推論規則： A, A ⊃ B ∈ M ⟹ B ∈ M (分離規則); A ∈ M ⟹ □A ∈ M

体系 S_{4} 体系 M に公理 (3) □A ⊃ □□A を追加.

体系 Br 体系 M に公理 (4) A ∨ □¬□A を追加.

体系 S_{5} 体系 M に公理 (5) □A ∨ □¬□A を追加.

定理 7.4.1 S_{5} ⊃ S4, Br ⊃ M.

定理 7.4.2 S_{4} に公理 (4) を追加した体系は S_{5} に等しい.

LK 流の推論

□ 左\frac{A, Γ → Δ}{□A, Γ → Δ} □ 右_{M}  \frac{Σ → A}{□Σ → A}
□ 右_{S_{4}}  \frac{□Σ → A}{□Σ → □A}
□ 右_{S_{5}}  \frac{□Σ → □Δ, A}{□Σ → □Δ, □A}

第8章数理計画法

8.1 用語

線形計画問題 (linear programming problem)

目的関数 (objective function):

z := c_{1}x_{1} + ⋯ + c_{n}x_{n}

を制約条件:

( \begin{matrix}a_{11} & ⋯ & a_{1n} \\ ⋮ & ... & ⋮ \\ a_{m1} & ⋯ & a_{mn} \end{matrix} ) ( x_{1} ; ⋮ ; x_{n} ) = ( b_{1} ; ⋮ ; b_{m} )

とすべての変数に対する非負条件 (nonnegative condition):

x_{j} ≥ 0, j = 1, ⋯, n

の下で最小にする解 x := (x_{1}, ⋯, x_{n})^{t} を求める問題として定式化される問題.

シンプレックス法 (単体法)

線形計画問題に対する最適解を求めるための手法であり, 次の 2 段階からなる. 第 1 段階で, 1 つの実行可能基底解を得る (存在しない場合は存在しないという情報を得る). 第 2 段階では, 基底変数を入れ換えて, 別の実行可能基底解を得る. このとき, 相対費用係数 (relative cost coefficient) がすべて非負ならば, その実行可能基底解は, 最適解である.

凸集合 (nonconvex set)

n 次元ユークリッド空間 E^{n} の部分集合 S に対して, x^{1}, x^{2} を S に属する任意の 2 点として,

λx^{1} + (1 − λ)x^{2} (0 ≤ λ ≤ 1)

が S に属するとき, 集合 S を凸集合という.

幾何学的には, x^{1}, x^{2} を結ぶ (閉) 線分が S に含まれることである.

カーマーカー法 線形計画問題を解くための手法で, 内路経路法とも呼ば れる. 射影変換→内接円上で最小化→逆変換の繰り返し によって多項式オーダーで解を収束させることができる. シミュレーテッド・アニーリング 一般的な逐次近似法は, 初期の実行可能解より常に解 が改善されるアルゴリズムであり, いったん極小値の穴に 入ってしまうと, そこから出ることはできない. そこで, 逐次に近似していく過程において解の改善だけでなく改 悪も許すことで, 極小値から脱出し最適解に近づけるこ とを考える. この手法をシミュレーテッド・アニーリン グという.

第9章{データ構造と \atop アルゴリズム}

9.1 アルゴリズム概論

アルゴリズムが正しい条件

(1) どんな入力に対しても, 答えを与える場合にはその答えが正しいこと;

(2) どんな入力に対しても, 有限の時間で答えを与えること.

アルゴリズムの正しさの証明

上記 2 つの条件を別々に証明する.

(1) ループ不変条件 (くり返しのなかで, 回るたびに常に成立する変数間の関係式) の成立を示す.

(a) 繰り返しが始まる直前にこの条件が成立していること;

(b) この条件が成立しているときに繰り返しを 1 回進めると, 再び条件が成立すること

を示せばよい.

(2) 単調減少する変数の値とその下限を示せばよい.

例 9.1.1 (ユークリッドの互除法)次のプログラムが正しいことを示す:

function gcd(m, n: integer): integer;
  var r: integer;
begin
  repeat
    r := m mod n;
    m := n;
    n := r;
  until r = 0;
  gcd := m;
end.

(1) について. 繰り返し直前, 求める最大公約数を d とすると,

d = gcd(m, n)  (9.1)

\begin{matrix}が成り立つ. このとき, 整数 m′, n′(m′, n′ は互いに素) を \\ 使って, m = dm′, n = dn′ と表すことができる. \\ 1 回繰り返しが回った直後, m, n はそれぞれ元の n, r. こ \\ こで, r は m と n を割ったときの余りで, m = qn+r (q ∈ \\ Z) と表すことができる. \\ \{ & \begin{matrix}r = m − qn = dm′ − q · dn′ = d(m′ − qn′) \\ n = dn′ \end{matrix} \\ で, m′−qn′ と n′ は互いに素だから, 最大公約数は d. よっ \\ て, 式 (9.1) が成り立つ. これは, 任意の回数まわしても \\ 常に成り立つ. \\ 有限回まわして r = 0 になったとき, m = qn が成り \\ 立つ. この n が m に代入されるから, 最大公約数は m. \\ よって, 計算が有限時間で停止した場合, 与える答えは正 \\ しい. \\ (2) について. n は単調減少し, 下限は 0 である. \end{matrix}

32 第 9 章データ構造とアルゴリズム

9.2 線形リスト

要素リストの各要素は, 同じ型の値を持つ.

構造リストの要素間の関係は線形.

操作 • procedure FindRight(L: LIST);

• procedure FindLeft(L: LIST);

• procedure Findith(L: LIST; i: integer);

• function Retrieve(L: LIST): Element;

• procedure Update(L: LIST; e: Element);

• procedure InsertLeft(L: LIST; e: Element);

• procedure InsertRight(L: LIST; e: Element);

• procedure Delete(L: LIST);

• function Size(L: LIST);

• function CurPos(L: LIST);

• procedure Create(L: LIST);

実現

(i) 配列のべた詰め • InsertRight, InsertLeft, Delete—–末尾の要素に対しては一定時間. その他は後続する要素をすべて移動するため O(n).

• その他—–一定時間. (ii) 一方向連結リスト

• InsertLeft, Delete, FindLeft, Fineith, Size, CurPos—–先頭からたどる必要があるため O(n).

• その他—–一定時間 (iii) 一方向連結リスト（ポインタは対応する要素の左隣

を指す） • InsertLeft, Delete—–一定時間.

• その他—–(ii) と同じ. (iv) 双方向リスト

• FindLeft—–一定時間.

• その他—–(ii) と同じ. 連結リストは, 通常レコードとポインタで実現される

が, 配列とインデックスで実現することもできる.

9.3 スタック

要素・構造線形リストと同じ

操作先頭要素のみ操作可能.

• procedure PushDown(S: STACK; e: Element);

• procedure PopUp(S: STACK);

• function Retrieve(S: STACK): Element;

• function Empty (S: STACK): Boolean;

• procedure Create(S: STACK);

実現配列を使用.

• 配列の長さで制約を受ける.

• 配列は先頭に対する処理は一定時間なので最適.

グラフの探索深さ優先探索法 (depth-first search) で利用.

9.5. 木構造（概論） 33

9.4 待ち行列（キュー）

要素・構造線形リストと同じ.

操作削除・参照は先頭, 挿入は末尾の要素に対してのみ可能.

• procedure EnQueue(Q: QUEUE; e: Element);

• procedure DeQueue(Q: QUEUE);

• function Retrieve(Q: QUEUE);

• function Empty(S: STACK): Boolean;

• procedure Create(Q: QUEUE);

実現

(i) 配列—–配列の最初の方にたまる空きが無駄になる. (ii) 循環配列—–(i) の欠点が解消.

グラフの探索幅優先探索法 (breadth-first search) で利用.

9.5 木構造（概論）

木の帰納的定義

木 (根付き木, rooted tree) とは, 有限集合 T (各要素を節点 (node) という) のうち, 次の条件を満たすものである:

(1) 根 (root) と呼ばれる節点が, 1 つだけ指定されている;

(2) 根以外の接点は, m(≥ 0) 個の共通部分を持たない有限集合 T_{1}, ⋯, T_{m} に分割でき, T_{1}, ⋯, T_{m} は再び木である (これらを部分木 (subtree) という).

表現法

(i) 節点と辺の集合の対 (接点の集合, 辺の集合, 根) ({A, B, C, D, E}, {(A, B), (B, D), (B, E), (A, C)}, A)

(ii) 入れ子の括弧による表現 (根 (部分木) ... (部分木)) (A, (B, (D), (E)), C)

9.6 順序木

各節点の子に対して, 順序を区別する. この順序を兄弟 (siblings) と呼ぶ.

9.7 2 分木

各節点の子の個数を高々2 とし, 「左の子」と「右の子」を区別.

注意片方の子が空の 2 分木と 1 つの子しか持たない順序木は異なる.

操作 • function FindParent (n: Node): Node;

• function FindLeftChild (n: Node): Node;

• function FindRightChild (n: Node): Node;

• function FindRoot(T: BinaryTREE): Node;

• function Retrieve(n: Node): Label;

• function EmptyNode(n: Node): Boolean;

9.8 2 分探索木

2 分木において, 接点のラベルに対して次の制限を加えたものである:

(1) 節点のラベルの型が線形順序を持つ.

(2) 各節点のラベルが, 左部分木のすべての節点のラベルより大きく, 右部分木のすべての節点のラベルより小さい.

(通りがけ順にたどることで, ソートされたラベルのリストが得られる.)

関数 member(x, A)

  fun member(x, Empty) = false
    | member(x, Node(y, L, R)) =
        if x = y then true
          else if x < y then member(x, L)
          else member(x, R);

関数 insert(x, A)

根から順番にラベルと挿入すべきデータとの大小関係を比較して, それに基づいて反復的に下へたどる. 葉にたどり着いたらその子として導入.

  fun insert(x, Empty) = Node(x, Empty, Empty)
    | insert(x, Node(y, L, R)) =
        if x = y then Node(y, L, R)
          else if x < y then
            Node(y, insert(x, L), R)
          else Node(y, L, insert(x, R));

関数 delete(x, A)

i) 削除すべき節点が子を持たないとき, 削除のみ行う. ii) 削除すべき節点がただ 1 つの子を持つとき, 親と子

をくっつける. iii) 削除すべき節点が 2 つの子を持つとき, 左部分木の

最大の節点で置き換える.

                                                   fun delete(x, Empty) = Empty
                                                     | delete(x, Node(y, L, R)) =
                                                         if x < y then Node(y, delete(x, L), R)
                                                           else if x > y then
                                                             Node(y, L, delete(x, R))
                                                           else if L = Empty then R
                                                           else if R = Empty then L
                                                           else let val (z, R1) = deletemin(R)
                                                                in  Node(z, L, R1)
                                                                end;

関数 deletemin(A)

                                                   fun deletemin(Node(y, Empty, R)) = (y, R)
                                                     | deletemin(Node(y, L, R) =
                                                         let val (x, L1) = deletemin(L)
                                                         in  (z, Node(y, L1, R)
                                                         end;

9.9 AVL 木

2 分木において, 次の制限を加えたものである:

1. すべての節点において, 左部分木と右部分木の高さの差が高々1.

探索が最悪でも O(log n).

挿入

まず, 通常の 2 分探索木と同様に挿入し, 上の条件を満たさなくなったら, 木を再構成する:

i) 根 A の左の子 B の\underline{左部分木}の高さが h, 右部分木の高さが h − 1, A の右部分木の高さが h − 1 の場合.

(a) B を根とし, A を B の右の子にする.

(b) 元々の B の右部分木を A の左部分木にする. (1 重回転 (single rotation) という.)

ii) 根 A の左の子 B の\underline{右部分木}の高さが h, 左部分木の高さが h − 1, A の右部分木の高さが h − 1 の場合.

(a) B の右の子 C を根にする.

(b) B を C の左の子, A を C の右の子にする.

(c) 元々の C の左部分木を B の右部分木, C の右部分木を A の左部分木にする.

(2 重回転 (double rotation) という.)

右が高くなる場合も, 同様に考える.

O(log n).

削除

まず, 通常の 2 分探索木と同様に削除し, 条件を満たさなくなったら, 1 重回転・ 2 重回転によって木を再構成する.

定理 9.9.1 n 個の節点をもつ AVL 木の高さは O(log n) である.

証明高さ h の AVL 木の節点の個数が, 最小の場合でも h の指数関数のオーダーになることを示せばよい.

高さ h の AVL 木のうちで, 節点の個数が最小のものの 1 つは, 葉以外のすべての節点において, 左部分木の高さが右部分木の高さより 1 大きいものである (Fibonacci 木). 高さ h の AVL 木の最小の節点の個数を N_{h} とすると,

N_{h} = N_{h−1} + N_{h−2} + 1 (h ≥ 2),

ここで, N_{0} = 1, N_{1} = 2 である. この漸化式を解くと,

N_{h} = \frac{1}{\sqrt{5}} \{(\frac{1 + \sqrt{5}}{2})^{h−3} − (\frac{1 − \sqrt{5}}{2})^{h+3}\} − 1.

|\frac{1 − \sqrt{5}}{2}| < 1 より, h を十分に大にとれば,

(\frac{1 − \sqrt{5}}{2})^{h+3} ∼ 0. また, −1 も無視できるので,

N_{h} ∼ \frac{1}{\sqrt{5}} (\frac{1 + \sqrt{5}}{2})^{h+3} .

よって, 節点の個数 N_{h} は, 高さ h の指数関数のオーダーで増加する. これは, 逆に AVL 木の高さは, 節点の個数に対して, 高々対数のオーダーでしか増えないことを示している.

9.10 B 木

m(≥ 3) 木において, 次の制限を加えたものである^{1} :

1. 各節点 (葉以外) のこの個数は ⌈m/2⌉ 以上, m 以下 (ただし, 根の子は 2 個以上);

2. 根から葉までの深さは, どの葉についても等しい.

データはすべて葉に昇順に格納され, 葉以外の節は, (( 子の個数) − 1) 個の要素からなる配列を持ち, k 番目の要素には k 番目の子より大きく, (k + 1) 番目の子より小さい値を持つ.

挿入

1. 挿入すべき葉の位置を求める.

2. 求めた位置の親の子の個数が m 以上の場合, 親を 2 つに分割した上で挿入する.

3. 分割によって新しくできた親に対して, 2. を繰り返す.

O(log n).

削除

1. 削除すべき葉を削除する.

2. 削除した葉の親の子の個数が ⌈m/2⌉ を下回った場合, 隣 (左右どちらでもよい) と同数の子を持つように, 隣から子をもらってくる.

3. それによってとなりの子の個数が ⌈m/2⌉ を下回った場合, 両者を合体する.

4. 合体した場合, その親に対して 2.〜3. を繰り返す.

O(log n).

9.11 半順序の付いた木

定義

2 分木において, 節点のラベルに対して次の制限を加えたものである:

1. 節点のラベルの型が線形順序を持つ.

2. 各節点のラベルが, 左右の子のラベルより小さいか等しい.

関数 Deletemin(Q)

1. 根節点を削除.

2. 最下段で最も右の葉を根に移す.

3. この節点 (新しい根) とその左右の子を比べ, 子より小さければ入れ換える.

4. 入れ換えた子に対して, 3. を繰り返す.

(sift down 操作)

手続き Insert(x, Q)

1. x を最下段のできるだけ左に挿入.

2. 挿入した節点とその親を比べ, 親より大きければ入れ換える.

3. 入れ換えた親に対して, 3. を繰り返す.

(sift up 操作)

配列による実現

1. h[1] には根を入れる.

2. h[i] の左の子を h[2i], 右の子を h[2i + 1] に入れる.

このとき, h[i] ≤ h[2i], h[i] ≤ h[2i + 1] (i = L, L + 1, ⋯, R/2) を満たし, ヒープと呼ぶ.

1 m = 3(各節点の子の個数が 2〜3) の B 木を 2-3 木, m = 4(各節点の子の個数が 2〜4) の B 木を 2-3-4 木という.

9.12 集合

要素各要素は, 同じ型の値を持つ.

構造重複はなく, 順序を区別しない. 要素数は有限.

操作 • function Union(A, B: SET): SET;

• function Intersection(A, B: SET): SET;

• function Difference(A, B: SET): SET;

• procedure Insert(x: Element; A: SET);

• procedure Delete(x: Element; A: SET);

• procedure Create(A: SET);

• function Member(x: Element; A: SET): Boolean;

• function Min(A: SET): Element;

実現

(i) ビットベクトル • 集合演算を論理演算命令を使って容易に実現できる.

• Min の実現は難しい.

• Member, Insert, Delete—–一定時間.

• Union, Intersection, Difference—–O(n), 一語に収まる場合は一定時間.

(ii) 連結リスト • Union, Intersection, Difference—–ソートされていれば 2 つのリストの長さの和, ソートされていなければ積.

• Insert—–ソートされていれば O(n), ソートされていなければ一定時間.

9.13 優先度付き待ち行列

要素の削除参照は, 一番優先度の高い要素に対して行われる. 操作は, Insert と Deletemin がある.

実現

ハッシュ法 (Deletemin が難しい) 以外であれば, どれでも可能.

(i) 連結リスト • リストをソートする／しないに関わらず, Insert ／ Deletemin のどちらかが O(n).

(ii) 半順序木 • Insert ／ Deletemin ともに O(log n).

9.14 ソート法

単純交換法 (バブルソート)

begin
  for i := 1 to n-1 do
    for j := n downto i+1 do
      if A[j-1] > A[j] then
        exchange(j-1, j)
end
   { 48  (65) (10)  36   83   5   21   72 }
-> { 48  [10]([65])(36)  83   5   21   72 }
-> { 48   10  [36] [65] (83) (5)  21   72 }
-> { 48   10   36   65  [5]([83])(21)  72 }
-> { 48   10   36   65   5  [21]([83])(72)}
-> {(48) (10)  36   65   5   21  [72] [83]}
-> {[10]([48])(36)  65   5   21   72 | 83 }
-> { 10  [36] [48] (65) (5)  21   72 | 83 }
-> { 10   36   48  [5]([65])(21)  72 | 83 }
-> { 10   36  (48) (5) [21] [65]  72 | 83 }
->                ......
-> {  5   10   21  36   48   65   72   83 }

O(n^{2}).

単純選択法

begin
  for i := 1 to n-1 do
    begin
      min := i;
      for j := i+1 to n do
        if A[j] < a[min]
          exchange(j, min)
    end
end
   {(48)  65    10   36   83    (5)   21    72 }
-> {[5]  (65)  (10)  36   83   [48]   21    72 }
-> { 5 | [10] ([65]) 36   83    48   (21)   72 }
-> { 5    10 | [21]  36  (83)  (48)  [65]   72 }
-> { 5    10    21 | 36  [48] ([83]) (65)   72 }
-> { 5    10    21   36   48 | [65] ([83]) (72)}
-> { 5    10    21   36   48    65 | [72]  [83]}
-> { 5    10    21   36   48    65    72    83 }

O(n^{2}). 比較に比べて交換の手間が大きい場合に有用.

単純挿入法

                                                 begin
                                                   for i := 2 to n do
                                                     begin
                                                       temp := A[i];
                                                       A[0] := A[i];
                                                       j := i - 1;
                                                       while A[i]  < A[j]
                                                         begin
                                                           A[j+1] := A[j];
                                                           j := j - 1
                                                         end;
                                                       A[j+1] := temp
                                                     end
                                                 end
                                                    { 48 |(65)  10   36   83    5   21   72 }
                                                 -> { 48  [65]|(10)  36   83    5   21   72 }
                                                 -> {[10]  48   65 |(36)  83    5   21   72 }
                                                 -> { 10  [36]  48   65 |(83)   5   21   72 }
                                                 -> { 10   36   48   65  [83]| (5)  21   72 }
                                                 -> { [5]  10   36   48   65   83 |(21)  72 }
                                                 -> {  5   10  [21]  36   48   65   83 |(72)}
                                                 -> {  5   10   21   36   48   65  [72]  83 }

O_{ave}(n^{2}), O_{max}(n^{2}), O_{min}(n). データがほとんど整列済みの場合に有用 (線形時間).

シェルソート

h(> 1) おきにとったデータに対して, 挿入法と同様の方法である程度整列された状態にする (場合によってはこれを繰り返す). その上で, 挿入法を適用.

h の取り方で計算量変化. O(n^{1.25}) も実現可能.

クイックソート

procedure qsort(L, R: integer);
var i: integer;
begin
  if L < R then
    begin
      i := partition(L, R);
      qsort(L, i-1);
      qsort(i+1, R)
    end
end
function partition(L, R: integer): integer;
var i, j: integer;
var center: item;
begin
  i := L;
  j := R;
  center := A[(L+R) div 2];
  repeat
    while A[i] < x do i := i + 1;
    while A[j] > x do j := j - 1;
    if i <= j then
      begin
        exchange(i, j);
        i := i + 1;
        j := j - 1
      end
  until i > j;
  partition := j + 1;
end
   {(48)  65   10  /36/   83    5   (21)  72 }
-> {[21] (65)  10  /36/   83   (5)  [48]  72 }
-> { 21   [5]  10  /36/   83  [65]   48   72 }
-> {(21)  /5/  10 | 36 | (83) /65/  (48)  72 }
-> {/5/  [21]  10 | 36 | [48] /65/  [83]  72 }
-> { 5 | /21/ (10)| 36 |  48 | 65 | /83/ (72)}
-> { 5 | [10] /21/| 36 |  48 | 65 | [72] /83/}
-> { 5 |  10 | 21 | 36 |  48 | 65 |  72 | 83 }

O_{ave}(n log n), O_{max}(n^{2}).

ヒープソート

まず, ヒープ列を構成する. A[n/2+1], ⋯, A[n] はすべて葉なので, A[n/2] から A[n/2 − 1], A[n/2 − 2], ⋯, A[1] と順番にふるい落とし (sift)^{2} を行う.

次に, このヒープ列からソート列を構成する. ヒープ列の根 A[1] は最小なので A[n] と交換する (A[n] は決定). すると, 配列 A[1], ⋯, A[n−1] がヒープ列でなくなる^{3} ので, ふるい落としによってヒープ列を構成する. このとき, 根 A[1] はヒープ列 A[1], ⋯, A[n − 1] のなかで最小なので, A[n − 1] と交換する. これを繰り返す.

                                                 begin
                                                   L := n div 2;
                                                   R := n;
                                                   repeat                   (* ヒープ列の構成 *)
                                                     sift;
                                                     L := L - 1
                                                   until L <= 1;
                                                   repeat                   (* ソート列の構成 *)
                                                     exchange(A[1], A[R]);
                                                     R := R - 1;
                                                     sift
                                                   until R <= 1
                                                 end
                                                 begin                      (* ふるい落とし *)
                                                   i := L;
                                                   x := A[i];
                                                   while 2 * i <= R do
                                                     begin
                                                       j = 2 * i;
                                                       if (j < R) and (A[j] < A[j + 1]) then
                                                         j := 2 * i + 1;
                                                       if x <= A[j] then goto 13;
                                                       A[i] := A[j];
                                                       i := j;
                                                       j := 2 * i;
                                                     end;
                                                 13: A[i] := x
                                                 end

2 ヒープ A[L + 1], ⋯, A[R] が与えられたとき, A[L], A[L + 1], ⋯, A[R] をヒープにすること. いま, ふるい落としの対象要素を A[i] とすると, min(A[2i], A[2i + 1]) と A[i] とを比較して, A[i] > min(A[2i], A[2i + 1]) なら交換し, 交換した相手を A[i] とおいて, A[i] が葉になるまで繰り返す.

3 A[2], ⋯, A[n − 1] はヒープ列のままである.

9.15 探索

線形探索

配列やリストに格納されたデータを前から順番に探索する. 挿入：一定時間探索： O(n)

2 分探索

1. データを配列に小さい順にならべる.

2. 与えられたデータと配列の中央のデータを比較し, 与えられたデータの方が小さければ左半分を, 大きければ右半分を探索対象とする.

3. 新しい探索対象に対して, 再帰的に 2. を繰り返す.

挿入： O(n) 探索： O(log n)

2 分探索木を用いる方法

挿入： O(log n) 探索：平均 O(log n). 最悪で O(n).

AVL 木

探索は最悪でも O(log n).

• ほとんどの場合, 完全 2 分木より 1 高い程度におさえられる.

• 挿入で約 47%, 削除で約 21%の確率で, 回転が必要.

→探索が挿入・削除に比べて多い場合に最適.

B 木

2 次記憶上で実現するのに最適. 2-3 分木を 2 分木で表現した場合, AVL 木の制約がゆ

るいものに相当. → AVL 木に比べて再構成が少なくて済む.

ハッシュ法

• サイズ B の配列 T (ハッシュ表という) を用意し, ハッシュ関数 h : Element → {0, ⋯, B −1} を使って, 挿入・削除・探索を行う. Element 型の要素 x をキー, h(x) をキー x のハッシュ値という.

• いくつかのキーが同じハッシュ値を持つ場合, 衝突 (collision) するといい, 同じハッシュ値を持つキーのクラスをバケット, そのハッシュ値をバケット番号という.

• 平均時間計算量: 一定.

(i) オープンハッシュ法, チェイン法, 連鎖法 • 同じバケット中の要素を連結リストにし, そのヘッダをハッシュ表に格納する.

• 挿入： T [h(x)] をヘッダとする連結リストに x があれば何もしない, なければ挿入.

• 削除： T [(h(x)] をヘッダとする連結リストに x があれば削除, なければ何もしない.

• 探索： T [h(x)] をヘッダとする連結リストに x があるかを調べる.

• 代表的なハッシュ関数 : h(n) := (n^{2} div C) mod B. ここで, BC^{2} ∼ K^{2} となるように C を定める.

• 平均時間計算量 : O(1 + N/B). (登録要素数) ≥ 2B となったら倍のサイズのハッシュ表を作ることにすれば, 平均時間計算量は常に 3 以下.

• Min の時間計算量のよいアルゴリズムはない. (ii) クローズドハッシュ法, 開番地法, オープン法

• ハッシュ関数 h のほかに再ハッシュ関数 h_{1}, h_{2}, ⋯ を用意する. 要素 x を格納するときに T [h(x)] がふさがっていれば再ハッシュ関数を用いて別の場所へ格納する.

• 挿入： x が辞書に含まれているかを調べ, 含まれていれば何もしない, 含まれていなければ ‘削除状態’ または ‘空状態’ が見つかるまで再ハッシュし登録.

• 削除： T [h(x)] が ‘空状態’ なら何もしない, x なら ‘削除状態’ に書き換える, 別の要素または ‘削除状態’ なら再ハッシュ.

• 探索：T [h(x)] が ‘空状態’ なら false, x なら true, 別の要素または ‘削除状態’ なら再ハッシュ.

• 代表的なハッシュ関数

(1) 線形検査法 h_{i}(x) := (h(x) + i) mod B. (h(x) に集中しやすい)

(2) h_{i}(x) := (h(x) + ci) mod B, c と B は互いに素. (c 個めごとに団子状態)

(3) 2 次関数検査法 h_{i}(x) := (h(x)+i^{2}) mod B.

(4) h_{i}(x) := (h(x) + d_{i}) mod B, d_{i} : ランダムな順列.

• 登録要素数がバケット数 B の 90%以上になったとき, 表中にある要素を探す平均時間計算量は 2.56 以上, 表中にない要素を探す平均時間計算量は 10 以上.

• Min の時間計算量のよいアルゴリズムはない.

トライ

データの値自身によって木の分岐を決める方法.

例えばデータが文字列なら, 各節点は文字の種類の分だけ子を持ち, それぞれの子が各文字に対応する. 根の子がデータの 1 文字目を表し, さらにその子が次の文字を表す. 以下同様. 長所：探索・挿入の計算量がデータの個数によらない (データ長に比例). 短所：記憶域の無駄が大きい. (解決策： 3 段目までトライ, それ以降 2 分探索木など.)

9.16 文字列照合

テキスト文字列 text := u_{1} ⋯ u_{m} の中に含まれる照合文字列 pattern := v_{1} ⋯ v_{n} の開始位置を求める.

単純法

                                                 begin
                                                   k := 0;
                                                   found = false;
                                                   while (k < m) and (found = false)
                                                     begin
                                                       k := k + 1;
                                                       j := 1;
                                                       while (text[k+j-1] = pattern[j])
                                                                and (found = false)
                                                         begin
                                                           j := j + 1;
                                                           if j > n then found = true
                                                         end
                                                     end;
                                                   if found = false then k := -1
                                                 end

O(mn).

KMP 法

照合文字列の繰り返しに着目し, 以下の配列に基づいて照合の一部を省略.

next[j] = k ⟺ v_{1} ⋯ v_{k} と v_{j−(k−1)} ⋯ v_{j} が一致 ⟹ u_{i−(k−1)} ⋯ u_{i} と v_{j−(k−1)} ⋯ v_{j} が一致すれば, u_{i−(k−1)} ⋯ u_{i} と v_{1} ⋯ v_{k} が一致する ⟹ u_{i+1} と v_{j+1} が不一致なら, u_{i+1} と v_{k+1} を調べればよい.

照合文字列の各文字について何文字一致しているかをあらかじめ表にしておく.

例 9.16.1 text := “ABCABCABA”, pattern := “ABCABA”. next[1] = 0, next[2] = 0, next[3] = 0, next[4] = 1, next[5] = 2, next[6] = 1 より, text[4..5] と pattern[4..5] が一致 ⟹ text[4..5] と pattern[1..2] が一致.

AABABABBABAAB   (BABAA)
B.
 B.
  BABAA
    ..BA
       BABAA

O(m + n).

Boyer-Moore のアルゴリズム

照合文字列を\underline{末尾から}照合. 次の方針に従い, 不一致時にできるだけ照合を省略.

(1) 不一致時の\underline{テキスト側の}文字が, 照合文字列にあるか, あるならどこにあるかで, 何文字ずらすかを変える.

1. あらかじめすべての文字に対して, その文字列が照合文字列に含まれているか, 含まれているなら末尾から数えて何番目にあるかを表す表を作成する. 例 never

n e v r その他
4 1 2 5  5

2. 不一致時, テキスト側の文字に対する 1. の表の値

の分だけずらす.

(2) 不一致時, \underline{すでに一致した部分の繰り返しが}照合文字列にあるか, あるならどこにあるかで何文字ずらすかを変える. v_{j} で不一致になったとする.

i) v_{j+1} ⋯ v_{m} が v_{(j+1)−s} ⋯ v_{m−s} と一致し, v_{j} ≠ v_{j−s} ならば, s 文字ずらす.

ii) v_{j+1} ⋯ v_{m} の後半 (m − s) 文字 v_{s+1} ⋯ v_{m} が, v_{1} ⋯ v_{m} の前半 (m − s) 文字 v_{1} ⋯ v_{m−s} と一致するとき, s 文字ずらす. iii) 上記以外のとき, m 文字ずらす.

あらかじめ照合文字列の各文字に対して, 不一致になったら何文字ずらすかを表にする.

O(n + m). うまくいくと, O(n/m).

第10章形式言語

10.1 文法と言語

定義 10.1.1 (文法) 文法 G は, 次の 4 組 G := (N, Σ, P, S) からなる:

(1) N : 非終端記号 (nonterminal symbol) の有限集合;

(2) Σ : 終端記号 (terminal symbol) の有限集合;

(3) P : 生成規則 (production rule) の有限集合;

(4) S : 開始記号 (start symbol), S ∈ N.

定義 10.1.2 (文脈依存文法)文法 G := (N, Σ, P, S) が 1 型文法または文脈依存文法 (context-sensitive grammar; CSG) であるとは, 任意の生成規則 α → β ∈ P に対して, |α| ≤ |β| が成り立つことである.

定義 10.1.3 (文脈自由文法)文法 G := (N, Σ, P, S) が 2 型文法または文脈自由文法 (context-free grammar; CFG) であるとは, 任意の生成規則 α → β ∈ P に対して, α がただ 1 つの非終端記号であることである.

定義 10.1.4 (正規文法) 文法 G := (N, Σ, P, S) が 3 型文法または正規文法 (regular grammar) であるとは, 任意の生成規則が A → aB または A → a (A, B ∈ N, a ∈ Σ) からなっていることである.

定義 10.1.5 (言語) 文法 G := (N, Σ, P, S) によって生成される言語を

{w | w ∈ Σ^{∗} かつ S ⟹^{∗} w}

と定義し, L(G) で表す.

例 10.1.1 G := ({S}, {0, 1}, {S → 0S1, S → 01}, S).

S ⟹ 0S1 ⟹ 00S11 ⟹ ⋯ ⟹ 0^{n−1}S1^{n−1} ⟹ 0^{n}1^{n}. 逆に, L(G) はこの列しか含まない. よって, L(G) = {0^{n}1^{n} | n ≥ 1}.

例 10.1.2 G := ({S, B, C}, {a, b, c}, P, S). ここで, P は以下の生成規則の集合である:

(1) S → aSBC;

(2) S → aBC;

(3) CB → BC;

(4) aB → ab;

(5) bB → bb;

(6) bC → bc;

(7) cC → cc.

S ⟹^{∗}  a^{n−1}S(BC)^{n−1} (∵ (1))
⟹ a^{n}(BC)^{n} (∵ (2))
⟹^{∗}  a^{n}B^{n}C^{n} (∵ (3))
⟹ a^{n}bB^{n−1}C^{n} (∵ (4))
⟹^{∗}  a^{n}b^{n}C^{n} (∵ (5))
⟹ a^{n}b^{n}cC^{n−1} (∵ (6))
⟹ a^{n}b^{n}c^{n} (∵ (7)).

ゆえに, L(G) は a^{n}b^{n}c^{n} (n ≥ 1) を含む. また, 逆に L(G) はこの列しか含まない (証明省略). よって, L(G) = {a^{n}b^{n}c^{n} | n ≥ 1}.

定義 10.1.6 (帰納性) 文法 G が帰納的 (recursive) であるとは, 任意の語 w について, w が G によって生成されるか否かを決定するアルゴリズムが存在することをいう.

定理 10.1.1 文脈依存文法は, 帰納的である.

例 10.1.3 例 10.1.2 で取り上げた文法 G において, w := abac が L(G) に属するかどうかを考える.

生成規則を高々n 回適用して得られる列の集合を T_{n} とする. ただし, 長さが 4 より長いものは考えない.

T_{0} = {S},
T_{1} = {S, aSBC, aBC},
T_{2} = {S, aSBC, aBC, abC},
T_{3} = {S, aSBC, aBC, abC, abc},
T_{4} = {S, aSBC, aBC, abC, abc},
⋮

T_{4} = T_{3} で, abac ∉ T_{3}. よって, abac ∉ L(G).

10.2 文脈自由文法

定理 10.2.1 (Chomsky 標準形定理) 任意の文脈自由言語は, 生成規則が A → BC または A → a だけからなる文法によって生成できる.

例 10.2.1 G := ({S, A, B}, {a, b}, P, S). ここで, P := {S → bA, A → a, A → aS, A → bAA, S → aB, B → b, B → bS, B → aBB}.

A → a と B → b はすでに標準形になっている. まず, S → bA を S → C_{1}A と C_{1} → b に,

A → aS を A → C_{2}S と C_{2} → a に, A → bAA を A → C_{3}AA と C_{3} → b に, S → aB を S → C_{4}B と C_{4} → a に, B → bS を B → C_{5}S と C_{5} → b に, B → aBB を B → C_{6}BB と C_{6} → a に, それぞれ置き換える.

次に, A → C_{3}AA を A → C_{3}D_{1} と D_{1} → AA に, B → C_{6}BB を B → C_{6}D_{2} と D_{2} → BB にそれぞれ置き換える.

よって, 最終的に得られる生成規則は, 次の通り:

S → C_{1}A A → C_{2}S A → C_{3}D_{1}

S → C_{4}B B → C_{5}S B → C_{6}D_{2}

C_{1} → b C_{2} → a C_{3} → b

C_{4} → a C_{5} → b C_{6} → a

D_{1} → AA D_{2} → BB A → a B → b

定理 10.2.2 (Greibash 標準形) すべての文脈自由言語は, 生成規則が A → aα の形だけからなる文法によって生成できる. ここで, A は非終端記号, a は終端記号, α は非終端記号の列 (空でもよい) である.

定義 10.2.1 1. CFG G := (N, Σ, P, S) において, L(G) のなかに 2 つ以上の異なった最左導出を有する語が存在するとき, G は曖昧 (ambiguous) であるという.

2. CFL を生成するどの文法も曖昧なら, その言語を本質的に曖昧 (inherently ambiguous) という.

例 10.2.2 1. 例 10.2.1 の文法を考える. 語 aabbab は次の 2 つの最左導出がある: S ⟹ aB ⟹ aaBB ⟹ aabB ⟹ aabbS ⟹ aabbaB ⟹ aabbab; S ⟹ aB ⟹ aaBB ⟹ aabSB ⟹ aabbAB ⟹ aabbaB ⟹ aabbab. よって, 曖昧である.

2. 言語 L(G) := {w | w の a と b の個数は同じ } は本質的に曖昧ではない. たとえば, L(G) は, 曖昧でない文法 G_{1} := ({S, A, B}, {a, b}, P, S), P := {S → aBS, S → aB, S → bAS, S → bA, A → bAA, A → a, B → aBB, B → b} によって生成される.

10.3 有限オートマトン

定義 10.3.1 (有限オートマトン)(決定性) 有限オートマトン ((deterministic) finite automaton, automata とも書く) とは, 次の 5 組からなるシステム M := (K, Σ, δ, q_{0}, F) である:

(1) K : 状態 (state) の有限集合;

(2) Σ : 入力アルファベット (input alphabet) の有限集合;

(3) δ : 遷移関数 (transition function), K × Σ から K への写像^{1} ;

(4) q_{0} : 初期状態 (starting state), q_{0} ∈ K;

(5) F : 終了状態 (final state), F ⊂ K.

定義 10.3.2 有限オートマトン M := (K, Σ, δ, q_{0}, F) において, ある入力系列 x ∈ Σ^{∗} に対して δ(q_{0}, x) ∈ F が存在するとき, x は M によって受理 (accept) されるという.

定義 10.3.3 (非決定性有限オートマトン)有限オートマトンにおいて, 遷移関数の値域を K から「K の部分集合」に置き換えたものを非決定性有限オートマトン (nondeterministic finite automaton) という. すなわち, 決定性有限オートマトンの遷移関数の値が, 1 個の状態であるのに対し, 非決定性有限オートマトンでは, 0 個以上の状態の集合となる.

定理 10.3.1 L を非決定性有限オートマトンによって受理される集合とするとき, L を受理する決定性オートマトンが存在する.

定理 10.3.2 正規文法 G := (N, Σ, P, S) に対して, 有限オートマトン M := (K, Σ, δ, S, F) が存在して, T (M) = L(G).

定理 10.3.3 有限オートマトン M に対して, 正規文法 G が存在し, L(G) = T (M).

1 δ(q_{i}, a) = q_{j} は, 現在の状態が q_{i} のときにアルファベット a が入力されると, 状態が q_{j} に遷移することを表している.

例 10.3.1 G := ({S, B}, {0, 1}, P, S), P := {S → 0B, B → 0B, B → 1S, B → 0}.

G から T (M) = L(G) を満たす非決定性有限オートマトン M := ({S, B, A}, {0, 1}, δ, X, {A}) を構成する.

1. δ(S, 0) = {B} (∵ S を左辺に, 0 を右辺に持つ規則は S → 0B のみ);

2. δ(S, 1) = ∅ (∵ S を左辺に, 1 を右辺に持つ規則は存在せず);

3. δ(B, 0) = {B, A} (∵ B → 0B, B → 0);

4. δ(B, 1) = {S} (∵ B → 1S);

5. δ(A, 0) = δ(A, 1) = ∅.

次に, これと同等な決定性オートマトン M_{1} := (K, {0, 1}, δ′, [S], F) を構成する.

K := {∅, [S], [A], [B], [A, S], [A, B], [B, S], [A, B, S]}, F := {[A], [A, S], [A, B], [A, B, S]},

δ′([S], 0) = [B],  δ′([S], 1) = ∅,
δ′([B], 0) = [A, B],  δ′([B], 1) = [S],
δ′([A, B], 0) = [A, B], δ′([A, B], 1) = [S],

δ′(∅, 0) = δ′(∅, 1) = ∅.

最後に, いま構成した有限オートマトン M_{1} から文法 G_{1} := (K, {0, 1}, P_{1}, [S]) を構成する.

[S] → 0[B],  [S] → 1∅,
[B] → 0[A, B], [B] → 1[S], [B] → 0,
[A, B] → 0[A, B], [A, B] → 1[S], [A, B] → 0,
∅ → 0∅,  ∅ → 1∅.

10.4 プッシュダウン・オートマトン

定義 10.4.1 (pd-オートマトン)プッシュダウン・オートマトン (pushdown automaton; pd-オートマトンと略す) とは, 次の 7 組からなるシステム M := (K, Σ, Γ, δ, q_{0}, Z_{0}, F) である:

(1) K : 状態 (state) の有限集合;

(2) Σ : 入力アルファベット (input alphabet) の有限集合;

(3) Γ : pd-アルファベット (pushdown alphabet) の有限集合;

(4) δ : 遷移関数 (transition function), K ×(Σ∪{ε})×Γ から K × Γ^{∗} の有限部分集合の写像^{2} ; (5) q_{0} : 初期状態 (initial state), q_{0} ∈ K;

(6) Z_{0} : pd-初期記号 (start symbol), Z_{0} ∈ Γ, Z_{0} がはじめに pd-記憶部に置かれている;

(7) F : 最終状態 (final state) の集合, F ⊂ K.

定義 10.4.2 pd-オートマトン M := (K, Σ, Γ, δ, q_{0}, Z_{0}, F) が決定性 (deterministic) であるとは, 次の条件を満たすことをいう:

(1) q ∈ K, Z ∈ Γ において, δ(q, ε, Z) ≠ ∅ ならば, ∀a ∈ Γ : δ(q, a, Z) = ∅;

(2) すべての q ∈ K, Z ∈ Γ, a ∈ Σ ∪ {ε} に対して, δ(q, a, Z) は 2 個以上の要素を含まない.

例 10.4.1 {ww^{R} | w ∈ {0, 1}^{∗}} を受理する非決定性 pd-オートマトン

M = ({q_{1}, q_{2}}, {0, 1}, {R, B, G}, δ, q_{1}, R, ∅)

(1) δ(q_{1}, 0, R) = {(q_{1}, BR)};

(2) δ(q_{1}, 1, R) = {(q_{1}, GR)};

(3) δ(q_{1}, 0, B) = {(q_{1}, BB), (q_{2}, ε)};

(4) δ(d_{1}, 0, G) = {(q_{1}, BG)};

(5) δ(q_{1}, 1, B) = {(q_{1}, GB)};

(6) δ(q_{1}, 1, G) = {(q_{1}, GG), (q_{2}, ε)};

(7) δ(q_{2}, 0, B) = {(q_{2}, ε)};

(8) δ(q_{2}, 1, G) = {(q_{2}, ε)};

(9) δ(q_{1}, ε, B) = {(q_{2}, ε)};

(10) δ(q_{2}, ε, B) = {(q_{2}, ε)}.

このオートマトンに列 001100 を入力させたときの計算状況を以下に示す:

入力計算状況
ε (q_{1}, R) → (q_{2}, ε)
0 (q_{1}, BR)
00 (q_{1}, BBR) (q_{2}, R) → (q_{2}ε)
001 (q_{1}, GBBR)
0011 (q_{1}, GGBBR) (q_{2}, BBR)
00110 (q_{1}, BBGGBR) (q_{2}, BR)
001100 (q_{1}, BBGGBBR) (q_{2}, BBGGR)
(q_{2}, R) → (q_{2}, ε)

2 δ(q_{i}, a, X) = {(q_{j}, Y)} は, 現在の状態が q_{i} で pd-記憶部の先頭のアルファベットが X のときに, アルファベット a が入力されると, pd-記憶部の X が Y に書き換えられ, 状態が q_{j} に遷移することを表

している. 非決定性 (後述) の場合, 入力列を受理できるように自由に選択してよい.

定理 10.4.1 次の 3 つは同値である^{3} :

1. L が文脈自由言語である;

2. ある pd-オートマトン M_{1} が存在し, L = N(M_{1});

3. ある pd-オートマトン M_{2} が存在し, L = T (M_{2}).

例 10.4.2 M := ({q_{0}, q_{1}}, {0, 1}, {X, Z_{0}}, δ, q_{0}, Z_{0}, ∅);

\begin{matrix}δ(q_{0}, 0, Z_{0}) = \{(q_{0}, XZ_{0})\}, & δ(q_{1}, 1, X) = \{(q_{1}, ε)\}, \\ δ(q_{0}, 0, X) = \{(q_{0}, XX)\}, & δ(q_{1}, ε, X) = \{(q_{1}, ε)\}, \\ δ(q_{0}, 1, X) = \{(q_{1}, ε)\}, & δ(q_{1}, ε, Z_{0}) = \{(q_{1}, ε)\} \end{matrix}

に対して, N(M) を生成する文脈自由文法 G := (N, Σ, P, S) を作る.

N := {S, [q_{0}, X, q_{0}], [q_{0}, X, q_{1}], [q_{1}, X, q_{0}], [q_{1}, X, q_{1}],

[q_{0}, Z_{0}, q_{0}], [q_{0}, Z_{0}, q_{1}], [q_{1}, Z_{0}, q_{0}], [q_{1}, Z_{0}, q_{1}]},

Σ := {0, 1} とする^{4} .

M は初期状態が (q_{0}, Z_{0}) で, (q_{1}, ε) で終了するから, 最初の生成規則 S → [q_{0}, Z_{0}, q_{1}] を得る.

(q_{0}, Z_{0}) では, 入力記号 0 を受け付けて (q_{0}, XZ_{0}) となり (∵ δ(q_{0}, 0, Z_{0}) = {(q_{0}, XZ_{0})}), 非終端記号 [q_{0}, X, q_{i}] から導出される記号列によって (q_{i}, Z_{0}) となる (i = 0, 1). そして, [q_{i}, Z_{0}, q_{1}] で (q_{1}, ε) となり受理される. よって, ここから得られる生成規則は,

[q_{0}, Z_{0}, q_{1}] → 0[q_{0}, X, q_{0}][q_{0}, Z_{0}, q_{1}],
[q_{0}, Z_{0}, q_{1}] → 0[q_{0}, X, q_{1}][q_{1}, Z_{0}, q_{1}].

同様に考えて, δ(q_{0}, 0, X) = {(q_{0}, XX)} から,

[q_{0}, X, q_{0}] → 0[q_{0}, X, q_{0}][q_{0}, X, q_{0}],
[q_{0}, X, q_{0}] → 0[q_{0}, X, q_{1}][q_{1}, X, q_{0}],
[q_{0}, X, q_{1}] → 0[q_{0}, X, q_{0}][q_{0}, X, q_{1}],
[q_{0}, X, q_{1}] → 0[q_{0}, X, q_{1}][q_{1}, X, q_{1}]

を得る.

また, δ(q_{0}, 1, X) = {(q_{1}, ε)} より, M は (q_{0}, X) において 1 を受け付けて終了するので, [q_{0}, X, q_{1}] → 1. 同様に,

[q_{1}, Z_{0}, q_{1}] → ε (∵ δ(q_{1}, ε, Z_{0}) = {(q_{1}, ε)}),

[q_{1}, X, q_{1}] → ε (∵ δ(q_{1}, ε, X) = {(q_{1}, ε)}),
[q_{1}, X, q_{1}] → 1 (∵ δ(q_{1}, 1, X) = {(q_{1}, ε)})

を得る. ただし, [q_{1}, X, q_{0}], [q_{0}, X, q_{0}] から終端記号列を生成しないので, これらを含む生成規則を除外する. 結局, 生成規則は以下の通り:

S → [q_{0}, Z_{0}, q_{1}]  [q_{0}, X, q_{1}] → 1
[q_{0}, Z_{0}, q_{1}] → 0[q_{0}, X, q_{1}][q_{1}, Z_{0}, q_{1}] [q_{1}, X, q_{1}] → ε
[q_{0}, X, q_{1}] → 0[q_{0}, X, q_{0}][q_{0}, X, q_{1}] [q_{1}, X, q_{1}] → 1

[q_{1}, Z_{0}, q_{1}] → ε

例 10.4.3 言語 L(G) := {0^{n}1^{n} | n ≥ 1} を受理する pd-オートマトンを構成する. この言語の文法は,

G = ({S}, {0, 1}, {S → 0S1, S → 01}, S)

と表すことができる. これを Greibach 標準形に直すと,

G = ({S, B}, {0, 1}, {S → 0SB, S → 0B, B → 1}, S)

となる. 求める pd-オートマトンを

M := ({q_{0}, q}, {0, 1}, {Z_{0}, S, B}, δ, q_{0}, Z_{0}, ∅)

とおくと, 遷移関数 δ を以下の要領で求める:

G において S が開始記号だから,

δ(q_{0}, 0, Z_{0}) = δ(q, 0, S), δ(q_{0}, 1, Z_{0}) = δ(q, 1, S).

以下, X → aα, X → aβ, ⋯ という生成規則があれば, 遷移関数を δ(q, a, X) = {(q, α), (q, β), ⋯} と定義する. S → 0SB, S → 0B より, δ(q, 0, S) = {(q, SB), (q, B)}. B → 1 より, δ(q, 1, B) = {(q, ε)}. ここで, 定義されていない遷移関数は空集合をとる.

3 T (M) は, 最終状態で受理される言語を, N(M) は, 記憶内容を空にすることで受理される言語を表す.

4 非終端記号 [q_{i}, X, q_{j}] は, この非終端記号から導出される終端記号列 w が, pd-オートマトン M が (q_{i}, Xα) の状態で読み取りが開始され, 読み取りが終了したときの M の状態が q_{j}, 記憶部が α(先頭の X が消去された状態) であることを表す.

第11章{オペレーティング \atop システム}

11.1 プロセスの相互交渉

• 協調 (cooperation) 複数のプロセスが互いに協調して情報交換を行いながら, 共通の目的のために処理を進めるもので, 互いに他のプロセスを必要とする場合.

• 競合 (competition) 資源を取り合うなど, 互いに他のプロセスの存在を意識しなければならないが, 自分自身の処理の進行には不要な場合.

• 干渉 (interference) 相手のプロセスの中断など, 他のプロセスに影響を与える場合.

11.2 排他制御（概論）

排他制御が満たすべき条件

(1) クリティカルセクション^{1} を実行しているプロセスが 1 つもないとき, クリティカルセクションには射る洋弓をしたプロセスは\underline{ただちに許可}されなければならない.

(2) 2 つ以上のプロセスがクリティカルセクションに入ろうと争っているとき, その選択は無期限に延長されてはならない (デッドロック防止条件).

(3) いかなるプロセスも, あるプロセスがそのクリティカルセクションに入るのを無期限に妨げることはできない (公平条件).

フラグ（実現の基本的な考え方）

誰か (いずれかのプロセス) がクリティカルセクションに入っているというフラグ (旗) を設けること. いずれかのプロセスがクリティカルセクションに入るとフラグが上げられ, 出ると降ろされる. 他のプロセスは, フラグが上がっているときにはクリティカルセクションに入らないようにする.

問題点フラグの上げ下げ自身が, 排他制御と同じ問題である.

ユニプロセッサシステムでの実現

クリティカルセクションを割込み禁止にすればよい.

マルチプロセッサシステムでの実現

次のハードウェア命令を用いる:

• TS 命令 (Test and Set) ： M 番地のメモリ内容をレジスタ R に移し, M 番地のメモリに 1 を入れる (フラグとして使われる);

• SW 命令 (Swap) ： M 番地のメモリ内容とレジスタ R の値を入れ換える.

TS 命令, SW 命令ともに, 分割不可能で, 同時には 1 個の CPU でしか実行されないことを\underline{ハードウェアが}保証する.

1 分割してはならないプログラムの部分 (実行の途中で他のプロセスが実行されると矛盾が起こる可能性がある部分).

11.3 セマフォア

排他制御の一方法で, イベント変数 (event variable) の一種.

イベント変数

イベントの発生やその履歴を伝えるためにアクセスされる, プロセス間の共通変数. 次の 2 つの要素からなる.

(1) イベントの履歴を記録するデータ構造部分 (セマフォアでは整数 S);

(2) プロセスの待ち行列.

セマフォアの命令

• P 命令

条件 S ≥ 1 が満たされるまでプロセスを一時停止 (wait 命令).

P(S) (* S : セマフォア *)
begin
  if S >= 1 then
    begin
      S := S - 1;

P 命令を実行したプロセスはそのまま続行

    end
  else

P 命令を実行したプロセスを待ち行列に

入れて待ち状態に移す

end

• V 命令

一時停止させられたプロセスを起動 (signal 命令).

V(S)
begin
  if |L(S)| >= 1 then
             (* |L(S)| : S の待ち行列に

入っているプロセスの個数 *)

    begin

待ち行列をプロセスを 1 つ取り出す; 取り出したプロセスを実行可能状態に; V 命令を実行したプロセスも実行可能状態に

    end

                                                   else
                                                     begin
                                                       S := S + 1;

V 命令を実行したプロセスは続行

                                                     end
                                                 end

AND 命令

デッドロック^{2} を避けるため, P 命令と V 命令を次のように拡張する:

• P 命令

                                                 P_and(S1, S2, ..., Sn)
                                                 begin
                                                   if S1 >= 1 and ... and Sn >= 1 then
                                                     for i := 1 to n do
                                                       Si := Si - 1;
                                                   else
                                                     begin

現在のプロセスを Si < 1 を満たす最初の

Si の待ち行列に入れる; 再起動アドレスを P 命令の先頭に設定する

                                                     end
                                                 end

• V 命令

                                                 V(S1, S2, ..., Sn)
                                                 begin
                                                   for i := 1 to n do
                                                     begin
                                                       Si := Si + 1;

Si の待ち行列のすべてのプロセスを

実行可能状態にする

                                                     end

V 命令を要求したプロセスを実行可能列に入れる

                                                 end

2 プロセス 1, 2, ⋯, N がリソース R_{1}, R_{2}, ⋯, R_{N} をそれぞれ保持しながら, R_{2}, R_{3}, ⋯, R_{1} を要求する (要求の環) ができたときに, すべてのプロセスが互いに他のプロセスのリソース開放を待ち, そのプロセスも先に進めなくなる現象.

11.4 セマフォアの応用

プロデューサ／コンシューマ問題

プロデューサがメッセージをバッファに入れ, コンシューマがバッファからメッセージを取り出す (取り出されたメッセージはバッファからなくなる). プロデューサは, バッファがいっぱいのときはメッセージを入れるのを停止し, バッファが空くのを待ち, コンシューマは, 空のバッファからメッセージを取り出してはならない.

解法 2 つのセマフォア S, M を用意する. S はバッファの空きスロットの個数を数えるのに用い, M はメッセージの個数を数えるのに用いる.

var S, M: SEMAPHORE;
BUFFER: array[0..N-1] of MESSAGE;
S := N;
M := 0;

(* プロデューサ *)

var I: integer;
I := 0;
while true do
begin
P(S);
BUFFER[I] := メッセージ;
V(M);
I := (I + 1) mod N;
end

(* コンシューマ *)

var J: integer;
J := 0;
while true do
begin
P(M);
メッセージ := BUFFER[J];
V(S);
J := (J + 1) mod N;
end

この解を複数プロデューサ／複数コンシューマ問題に拡張するには, プロデューサの共通変数 I とコンシューマの共通変数 J を排他制御しなければならない.

リーダ／ライタ問題

ライタはレコードにデータを書き込み, リーダはそれを読み出す. 不用意にレコードの書き込み／読み出しを行うと項目間に矛盾が生じる.

座席予約システムなどで現れる. 解法現在レコードをアクセスしているリーダの個数

を数え, もし 0 でなければライタの書き込みを禁止する. リーダは, ライタが書き込み中であればアクセスを延期する.

var W: SEMAPHORE;
W := 1;
(* ライタ *)
while true do
  begin
    P(W);

書き込み;

    V(W)
  end
(* リーダ *)
var M: SEMAPHORE;
var R: integer;
M := 1;
R := 0;
while true do
begin
  P(M);
  if R = 0 then P(W);
  R := R + 1;
  V(M);

読み出し;

  P(M);
  R := R - 1;
  if R = 0 then V(W);
  V(M);
end

ダイニング・フィロソファ問題

5 人のフィロソファが食卓についている. 各フィロソファは, 考えることと食べることを繰り返す. テーブルの中央にはスパゲッティがあり, 自分の前に両脇に置かれたフォークを 2 本とって食べる. 食卓にはフォークが 5 本しか置かれていないため, 自分の両隣が食べていないときのみ食べることができる.

(オペレーティングシステムのリソース競合^{3} の抽象化)

var FORK: array [0..4] of SEMAPHORE;
FORK := {1, 1, 1, 1, 1};

(* プロセス i のプログラム *)

while true do
begin
think;
P_and(FORK[(i+1) mod 5], FORK[i]);
eat;
V(FORK[(i+1) mod 5], FORK[i])
end

11.5 モニタ

目的

リソースの管理と割り当てを円滑に記述するための寄稿を提供すること.

構造

• リソース自身;

• ローカルデータ (リソースの状態を保持している変数);

• スケジューラ;

• 待ち行列 (条件変数);

• プロシージャ(プロセスがリソースを確保・開放・初期化などをするためのもの);

• 初期化コード (モニタが定義されたときに実行され, ローカルデータを初期化).

モニタのプロシージャは, どのプロセスからでも呼ぶことができるが, 同時には 1 個のプロセスしかモニタのプロシージャを実行できない.

命令

• wait 命令

(1) 待ち行列にプロセス (プロセス制御ブロック; PCB) を登録する;

(2) モニタの排他制御をはずす;

(3) 制御をディスパッチャへ渡す.

• signal 命令

(1) 待ち行列に入っているプロセスの 1 つが \underline{ただちに}起動される;

(2) 起動されたプロセスのモニタ内手続きの実行が終了する.

多くの場合, 待ち状態の理由は 1 つ以上あるので, どの理由で俟っているかを区別するため, 条件 (condition) という型の変数を導入する:

        condvariable.wait
        condvariable.signal

3 たとえば, プロセス A が磁気テープユニットとディスクを, プロセス B がディスクとプリンタを, プロセス C がプリンタとカードリーダ, プロセス D がカードリーダとプロッタ, プロセス E がプロッタと磁気テープユニットを要求した場合など.

11.6 モニタの応用

プロデューサ／コンシューマ問題

• 資源大きさ N のバッファ.

• ローカル変数 firstcounter

メッセージが入っているスロットの位置.

• ローカル変数 lastpointer

バッファ内の空きスロットの位置.

• ローカル変数 count バッファに含まれているメッセージの個数

• 待ち行列 nonempty

メッセージが入るまで俟つための待ち行列

• 待ち行列 nonfull

スロットがあくまで俟つための待ち行列

• プロシージャappend プロデューサがバッファにメッセージを入れるときに呼ぶ. count = N ならば, メッセージを入れて

count を 1 増やし, nonempty.signal を起動する.

• プロシージャremove 待っているコンシューマがあれば, その中の 1 つが呼び, メッセージを取り出す.

リーダ／ライタ問題

ダイニング・フィロソファ問題

モニタは AND 条件を容易に記述できるので, 簡単に解くことができる.

11.7 マルチプログラミング（概論）

マルチプログラミングとは

主記憶に複数個のプログラムを格納し, 入出力待ちが生じたときにプログラムを切り替えることによってコンピュータの利用効率を向上させる方式.

マルチタスキングともいう.

記憶保護

(i) ロック／キー機構主記憶を同一の長さのブロックに分割し, それぞれに鍵をかける方式. ユーザプログラムにはキーが与えられ, 各ブロックのロックの値と一致した場合のみアクセスが許される. 一致しない場合には記憶保護違反割り込みが生じる.

(ii) 下限レジスタ機構下限レジスタ (lower limit register) という特別なハードウェアレジスタが, ユーザ領域の下限を示す. ユーザプログラムから主記憶へのアクセスは, すべて下限レジスタの値と比較され, 下限レジスタよりも小さければ, 記憶保護違反割り込みが発生する.

リエントラントプログラム（再入可能プログラム）

複数のプロセスで同時に共用可能なプログラム. 以下の条件を満たさなければならない:

(1) プログラムがピュア (実行中はそのプログラムに書き込み／修正をしない).

(2) リエントラントプログラムとそれを呼ぶプログラムは互いにアクセス可能 (パラメータを渡すことも可能).

(3) 個々のプロセスは, 記憶保護される.

マルチプログラミングの形式

次の条件の組み合わせで, 4 つの形式が生じる:

(1) 分割を固定するか否か.

(2) プログラムのスワップイン／スワップアウトを許すか否か.

11.8 オーバレイ ; プログラムを ; (1) ルートセグメント：常に主記憶に存在する部分 (オー ; バレイを制御する); ; (2) オーバレイセグメント：セグメントの呼び出し要求 ; にしたがってスワップイン／スワップアウトされる ; 部分 ; に分割する. ; • オーバレイ構造：セグメント間の呼び出し関係に基 ; づいて作られる木構造. ; • リンケージエディタ：オーバレイ構造を作る. ; 11.9 セグメンテーション ; プログラムをセグメントと呼ばれる主記憶領域にロー ; ドされる論理的な単位で, 論理アドレスを割り振ってお ; き, それを実行時に, 複数のセグメントレジスタで修飾し ; て物理アドレスを生成する方式. ; セグメンテーションの長所 ; 1. プロシージャの共用が容易. ; 2. 仮想記憶を実現可能. ; 3. セグメントの大きさを動的に増減可能. ; セグメンテーションの短所 ; 1. フラグメンテーションが生じる (メモリコンパクショ ; ンが必要). ; 2. セグメントの管理が困難.

11.10 ページング

ロック／キー機構を動的再配置機能を備えるように拡張したもので,

ページ：仮想アドレス空間を分割した各領域から

ページフレーム：物理アドレス空間を分割した各領域への変換 (mapping) 機構.

ページとページフレームはすべて同じ大きさで, ページは任意のページフレームに割り当ててよい.

ページングの機能

1. 動的再配置機能 (∵ページのページフレームへの割り当てを実行時に任意に変更可能)

2. (外部) フラグメンテーションの解決 (∵固定の大きさのページを用い, ページはいかなるページフレームにも割り当て可能) ただし, 内部フラグメンテーション^{4} は解決されず. (ページを小さくすれば解決できるが, 主記憶／二次記憶間のページの転送量・ページテーブルの大きさが増加.)

3. 仮想記憶の実現

ページングの長所

1. メモリフラグメンテーション問題を解決 (メモリコンパクションが不要).

2. ジョブのアドレス空間が, 主記憶の大きさに制限されない.

3. 主記憶をより有効に使える (結果として, CPU の利用効率向上).

ページングの短所

1. ハードウェアによるサポートが必要.

2. 実行時のオーバーヘッドが少なくない.

3. ページテーブルがかなりの主記憶領域をしめる.

4. ページ管理のアルゴリズムが複雑.

4 プログラムの大きさが, ページの大きさの正数倍でないために, ページ内に空き領域ができること.

53

\begin{matrix}第12章数値解析 \\ 12.1 ニュートン法 \\ ニュートン法とは \\ 非線形方程式 f(x) = 0 の解 α を以下の手順で求める: \\ 1. 解 α の近くの値を出発値 x^{(0)} とする; \\ 2. x^{(k+1)} := x^{(k)} − f(x^{(k)})/f′(x^{(k)}) f′(x^{(k)}) ≠ 0; \\ 3. 停止条件が満たされれば終了し, そうでなければ k := \\ k + 1 として, 2. に戻る. \\ 例 12.1.1 f(x) := 1/x − a = 0 (a > 0) をニュートン法 \\ で解く. \\ f′(x) = −1/x^{2} より反復式は, \\ x^{(k+1)} = x^{(k)} − \frac{1/x − a}{−1/x^{2}} = x^{(k)} + x(1 − ax) \\ 収束性 \\ ニュートン法の反復は, f(x) が解 α の近傍で滑らかな \\ 関数で, かつ f′(α) ≠ 0 のとき, 出発値 x^{(0)} が α に十分 \\ 近ければ \\ k^{(k)} → α (k → ∞) \\ となる. また, ある数以上の k に対しては \\ |x^{(k+1)} − α| ≤ C|x^{(k)} − α|^{2} (C : 定数); & (12.1) \\ |x^{(k+1)} − x^{(k)}| ∼ |x^{(k)} − α| \\ が成り立つ. 式 (12.1) が成り立つとき, x^{(k)} は 2 次収束 \\ するという. \\ 停止条件 \\ 次の式を用いる場合が多い: \\ i) |x^{(k+1)} − x^{(k)}| < ε; \\ ii) |f(x^{(k+1)} − f(x^{(k)})| < ε. \end{matrix} ^{減速法 ; ニュートン法の 2. の式のかわりに ; x^{(k+1)} := x^{(k)} − μ^{(k)} \frac{f(x^{(k)})}{f′(x^{(k)})} ; を用いる. μ^{(k)} は次の方法で定める: ; まず, μ^{(k)} := 1 として x^{(k+1)} を計算し, ; |f(x^{(k+1)})| < (1 − \frac{μ^{(k)}}{2} ) |f(x^{(k)})| ; を満たすまで μ^{(k)} を繰り返し 1/2 倍する.}

第13章{パターン認識の \atop 基礎}

13.1 パターン認識概論

認識系の構成

入力

|

[前処理部]

|

[特徴抽出部]

|

[識別演算部] ← [識別辞書] (←あわせて識別部と呼ぶ)

|

対応するクラスを出力

特徴空間

• 特徴ベクトル (feature vector) ：抽出した特徴を組にしたベクトル.

• 特徴空間 (feature space) ：特徴ベクトルによって張られる空間.

• クラスタ (cluster) ：特徴空間上におけるクラスごとにまとまった塊.

識別系

(i) 最も単純な識別系：特徴空間上の各点のクラス名をすべて識別辞書として格納する. →識別辞書の作成は人手によるしかないため, 現実的でない.

(ii) 最近傍決定則 (nearest neighbor rule), NN 法 (NN rule) ：各クラスの代表的なパターン (プロトタイプと呼ぶ) を用意する. 入力パターンは, 特徴空間上でこれらのプロトタイプと比較され, 最も距離の近いプロトタイプ (最近傍 (nearest neighbor) と呼ぶ) の属するクラスを識別結果として出力する.

(iii) k-NN 法 (k-nearest neighbor rule) ：入力パターンに最も近い k 個のプロトタイプをとり, その中で最も多数を占めたクラスを識別結果として出力する.

13.2 学習

クラスを正しく分離するための決定境界を自動的に求めること.

特徴ベクトルをクラスに対応させるのに用いられる関数を識別関数 (discriminant function) といい, 線形な識別関数を線形識別関数 (linear discriminant function) と呼ぶ. いま, クラス ω_{i} の線形識別関数を g_{i}(x) := w_{i0} + w_{i1}x_{1} + ⋯ + w_{id}x_{d} とすると, 学習とは, 重みベクトル w_{i} := (w_{i0}, w_{i1}, ⋯, w_{id})^{t} を適切に求めることである (非線形の場合でも同様に定義する).

パラメトリックな学習とノンパラメトリックな学習

• パラメトリックな学習 (parametric learning) ：学習パターンを用いて確率密度関数のパラメータ推定を行い, 識別部を構成する方法.

• ノンパラメトリックな学習 (nonparametric learning) ：学習パターンから直接識別関数を求める方法.

現実のパターン認識の問題において, 確率密度関数が既知ということはまずない. 実際のパターン認識は複雑な分布をし, 正規分布などの単純な確率密度関数はまず当てはまらない. パラメータの個数を増やせば複雑な確率密度関数を任意の精度で近似できるが, あまり現実的でない. よって, ノンパラメトリックな学習の方が実用性は高い.

教師付き学習と教師なし学習

• 教師付き学習 (supervised learning) ：学習パターンがその所属クラス名とともに与えられる学習法.

• 教師なし学習 (unsupervised learning)：クラスのラベルが付いていないパターンを用いて学習を行う方法.

線形識別関数と非線形識別関数

• 線形識別関数 (linear discriminant function)

g(x) := w^{t}x. 長所：頑健.

• 2 次識別関数 (quadric discriminant function)

g(x) := w^{t}x + x^{t}W x. 線形識別関数の問題に帰着可能. 長所：線形に比べ, 自由度が高い.

• 区分的線形識別関数線形分離不可能な分布において, 識別関数を複数の線形識別関数の組で表す. クラス ω_{i} の識別関数 g_{i}(x) は, L_{i} 個の副次識別関数 g_{i}^{(l)}(x) (l := 1, ⋯, L_{i}) で表される:

g_{i}(x) := max_{l}{g_{i}^{(l)}(x)};
g_{i}^{(l)}(x) := w_{i0}^{(l)} + ∑_{j=1}^{d} w_{ij}^{(d)}x_{j}.

長所：どのような複雑な決定境界も任意の精度で近似可能. (→有限個の学習パターンを完全に分離できる) 短所：パーセプトロンの学習規則を適用できない^{1} .

• ニューラルネットワーク：入力層と出力層の間に中間層を設け, 非線形名処理を導入することで, 非線形識別関数を実現. 区分的線形識別関数と極限において等価.

頑健性 (robustness)

• 2 次識別関数は, 線形識別関数よりも多くのパラメータを持つため, 最適な識別関数へ漸近するには, より多くのパターンを必要とする.

• 自由度の高い非線形モデルを使用する際, 学習パターンでうまく識別できたからといって, その性能がそのまま未知パターンにも当てはまるとはいえない.

学習未知の
パターンパターン
非線形モデル自由度高○△
線形モデル{推定値の \atop ばらつき小}△○

13.3 ノンパラメトリックな学習

パーセプトロンの学習規則

識別関数, 教師信号^{2} ともに 2 値で, 全学習パターンに対して出力と教師信号が一致するまで重みの修正を繰り返す. 長所：線形分離可能であれば, 必ず誤認識 0 に到達. 短所：線形分離不可能な場合には収束しない.

(1) 重みベクトル w の初期値を適当に設定する.

(2) 学習パターンを 1 つ選ぶ.

(3) 識別を行い, ω_{i} を ω_{j} と間違ったとき, 次式により重みベクトルを修正する (ρ : 正の定数):

\{ \begin{matrix}w′_{i} := w_{i} + ρx \\ w′_{j} := w_{j} − ρx \end{matrix}

(4) (2), (3) をすべての学習パターンに対して繰り返す.

(5) すべての学習パターンを正しく識別できたら終了, 間違えたら (2) に戻る.

中間層を持たないニューラルネットワークに相当.

Widrow-Hoff の学習規則

識別関数の出力を連続値とし, 教師信号との二乗誤差の総和を最小化する. 長所：線形分離不可能な場合でも収束を保証. 短所：線形分離可能な場合に得られる重みは, 必ずしも誤認識 0 の重みではない.

重みベクトルの修正法として,

w′_{i} := w_{i} − ρ(w_{i}^{t}x_{p} − b_{ip})x_{p}

を用いる.

教師信号 b_{ip} を

b_{ip} := \{ \begin{matrix}1 & (x_{p} ∈ ω_{i}) \\ 0 & (x_{p} ∈ ω_{i}) \end{matrix}

とすると, パーセプトロンの学習規則と同じ式を得る. よって, パーセプトロンの学習規則は, Widrow-Hoff の学習規則の特別な場合である.

1 パーセプトロンの学習規則は, xの任意の関数 φ_{1}(x), ⋯, φ_{d}(x)

の線形結合で表される関数 (Φ 関数 (Φ function) と呼ぶ) に対して適用可能である.

2 教師信号：各学習パターン x_{p} に対する, 各クラス ω_{i} の識別関数の望ましい出力値. b_{ip} で表す.

教師ベクトル：各クラス ω_{i} の教師信号 b_{ip} からなるベクトル.

(b_{1p}, ⋯, b_{cp})^{t}.

誤差逆伝播法 ; ニューラルネットワークに適用. ; ユニット i からの出力を g_{ip}, ユニット j への入力を h_{jp} ; とすると, ; h_{ip} = ∑_{i} w_{ij}g_{ip}. ; また, g_{ip} は非線形関数 f_{j} を使って g_{jp} = f_{j}(h_{jp}) と表せ ; る. 出力層の l 番目のユニットに対する教師信号 b_{lp} と実 ; 際の出力との二乗誤差 J_{p} は, ; J_{p} = \frac{1}{2} ∑_{l}(g_{lp} − b_{lp})^{2}. ; 最急降下法 (w′_{ij} := w_{ij} − ρ(∂J_{p}/∂w_{ij})) を用いる. ; \frac{∂J_{p}}{∂w_{ij}} = \frac{∂J_{p}}{∂h_{ip}} · \frac{∂h_{ip}}{∂w_{ij}} . ; ここで, ∂J_{p}/∂h_{jp} = ε_{jp} とおくと, ∂J_{p}/∂w_{ij} = ε_{jp}g_{ip}. ; ∴ w′_{ij} = w_{ij} − ρε_{jp}g_{ip}. ; 次に ε_{jp} を求める. ; ε_{jp} = \frac{∂J_{p}}{∂h_{jp}} = \frac{∂J_{p}}{∂g_{ip}} · \frac{∂g_{ip}}{∂h_{jp}} = \frac{∂J_{p}}{∂g_{jp}} · f′_{j}(h_{jp}). ; ∂J_{p}/∂g_{jp} は, ユニット j が出力層にあるときは ; ∂J_{p}/∂g_{jp} = g_{jp} − b_{jp}, 中間層にあるときは ∂J_{p}/∂g_{jp} = ; ∑_{k} ε_{kp}w_{jk}. ; 非線形関数 f_{j} としてシグモイド関数: ; S(u) := \frac{1}{1 + exp(−u)} ; を用いるとすると, S′(u) = S(u)(1 − S(u)) より, ; f′_{j}(h_{jp}) = g_{jp}(1 − g_{jp}). ; よって, ; ε_{jp} = \{ \begin{matrix}(g_{jp} − b_{jp})g_{jp}(1 − g_{jp}) & {(ユニット j が出 \atop 力層にある時)} \\ (∑_{k} ε_{kp}w_{jk}) g_{jp}(1 − g_{jp}) & {(ユニット j が中 \atop 間層にある時)} \end{matrix} ; この手法は, ある重みで計算された出力と教師信号と ; の差に基づいて ε_{jp} を計算し, 出力層から順に重みを修正 ; する. 13.4 パラメトリックな学習

ベイズ決定則

認識対象とするパターンが, 既知の確率密度関数 p(x|ω_{i}) に基づいて生起すると考える.

• P (ω_{i}) ：クラス ω_{i} の生起確率 (事前確率),

∑_{i} P (ω_{i}) = 1;

• p(x) ： x の生起確率, p(x) = ∑_{i} P (ω_{i})p(x|ω_{i});

• P (ω_{i}|x) ： xが生起されたとき, そのクラスが ω_{i} であ

る確率 (事後確率), ∑_{i} P (ω_{i}|x) = 1

とおき, P (ω_{i}|x) を最大にするクラス ω_{i} がxの属するクラスだと考える.

ここで,

P (ω_{i}|x) = \frac{p(x|ω_{i})}{p(x)}P (ω_{i})

が成り立ち, x を固定して考えると, p(x) は定数だから, 識別関数 g_{i}(x) は,

g_{i}(x) := p(x|ω_{i})P (ω_{i})

と定義できる.

確率密度関数の形はわかるが, パラメータが未知の場合, パラメータを推定する (この意味でパラメトリックと呼ばれる).

13.5 特徴空間の変換

正規化 (normalization)

各特徴量のスケールの取り方でその特徴量の重み付けが変化するという恣意性を回避するために行われる. 1 つの方法：パターン相互の距離を最小化する. これは, 各軸の分散を等しくすることに等しい.

KL 展開 (KL expansion)

特徴ベクトルの分布を最も良く近似する部分空間 (subspace) を求める (次元を圧縮する) 方法. 主成分分析と数学的にほぼ等価.

(i) 分散最大基準または (ii) 平均二乗誤差最小基準による.

一般に, 分散最大基準による変換と平均二乗誤差最小基準による変換は一致しないが, 平均二乗誤差最小基準による変換を求める際に, 原点を分布の重心に移動することで, 2 つの変換は一致する.

• 固有次元数 (intrinsic dimensionality) ：累積寄与率 (cumulative proportion) が, 最初の m 個の特徴量でほぼ 100%に達するとき, m を固有次元数という.

線形判別法 (linear discriminant method)^{3}

各クラスのパターン分布の分離度を最大にする部分空間を求める方法.

• フィッシャーの線形判別法 (Fisher’s linear discriminant method) ： 2 クラスに対する線形判別. 特徴空間上の 2 クラスのパターンの分布から, この 2 クラスを識別するのに最適な 1 次元軸を求める.

(i) クラス内変動・クラス間変動比最大基準 (ii) クラス内分散・クラス間分散比最大基準 (iii) マハラノビス汎距離^{4} .

KL 展開と線形判別法

KL 展開は, \underline{表現または圧縮のための次元圧縮}であり, 線形判別法は, 判別のための次元圧縮である.

KL 展開は, 識別は全く考慮されていないが, 以下の理由で広く用いられる:

1. 文字認識と音声認識などは, 通常高次元の特徴ベクトルを必要とし, \underline{次元の呪い}から逃れる手段として次元削減が不可欠である.

2. はじめに選ばれた特徴には, \underline{相関の高い}特徴の組が含まれている可能性がある. 相関の高い特徴は, 冗長な情報を含み, 逆行列の計算誤差が大きくなる場合がある.

3 統計の分野では, 判別分析 (discriminant analysis) と呼ばれる.

4 マハラノビスの汎距離 (Mahalanobis generalized distance) ：共分散行列の等しい 2 つの分布の平均間距離を表す量. 2 つの分布の平均間のユークリッド距離 (Euclidean distance) が等しくても, 分散が小さければ小さいほど, マハラノビス汎距離は大きくなる.

第14章人工知能の基礎

14.1 探索

探索とは

探索とは, 多くの可能性の中から特定の解を見つけ出すための戦略. 問題の状態空間を有向グラフで表したとき, 問題の解決は, その有向グラフの出発節点 (初期状態を表す) から目標節点へ至る順路を見つけ出すことである.

横形探索，幅優先探索 (breadth-first search)

1. 出発節点を OPEN に置く.

2. OPEN が空 ⟹ 失敗.

3. OPEN の最初に位置する節点 (n とする) を取り除き, これを CLOSED に置く.

4. n が目標節点 ⟹ 終了.

5. n の, OPEN または CLOSED にない子節点を, \underline{OPEN の後ろに}付け加える. (子節点から n へポインタをつける)

6. 2. に戻る.

複数の経路が存在するとき, 横形探索を使えば最短の経路を得られる.

縦形探索，深さ優先探索 (depth-first search)

1. 出発節点を OPEN に置く.

2. OPEN が空 ⟹ 失敗.

3. OPEN の最初に位置する節点 (n とする) を取り除き, これを CLOSED に置く.

4. n が目標節点 ⟹ 終了.

5. n の子節点を\underline{OPEN の先頭に}付け加える. (子節点から n へポインタをつける)

6. 2. に戻る.

コストを考慮する探索

1. 出発節点を OPEN に置く.

2. OPEN が空 ⟹ 失敗.

3. OPEN の最初に位置する節点 (n とする) を取り除き, これを CLOSED に置く.

4. n が目標節点 ⟹ 終了.

5. n のすべての子節点 m について, 出発節点からのコスト ĝ(m) を求め, OPEN に置く.

6. OPEN をコストの小さい順に並べ換える.

7. 2. に戻る.

ここで, ĝ(m) は出発節点から節点 m までのコストの推定値で, 探索対象が木であれば, これはコストの真値 g(m) と一致する. 有向グラフのとき, 一般に g(n) ≤ ĝ(m) である.

分岐限定法 (branch and bound)

有向グラフの探索において, 循環路を作らないように, n の子節点 m が OPEN あるいは CLOSE に含まれているかに応じて ĝ(m) を評価する方法.

以下, 節点 n からその子節点 m へのコストを c_{n,m}, 出発節点から n 経由での m までのコストを ĝ(m|n) とする.

i) m が OPEN にも CLOSED にも含まれていない場合 ĝ(m) := ĝ(m|n) とする.

ii) \underline{m が OPEN に含まれている場合}

すでに得られている ĝ(m) と ĝ(m|n) を比較し, ĝ(m|n) < ĝ(m) なら, m からのポインタを n に付け替え, ĝ(m|n) を新たな ĝ(m) とする.

iii) \underline{m が CLOSED に含まれている場合}

常に ĝ(m|n) ≥ g(m) なので, n の子節点としての m は無視する.

• 経路の存在が保証されれば, かならず最適経路を見つけることができる.

• 枝のコストが均一ならば, 分岐限定法は横形探索と一致する.

山登り法 (hill-climbing)

n の子節点 m に対してヒューリスティック関数 ĥ(m) を求め, ĥ(m) が最も小さい節点を選ぶ^{1} .

• 最適順路の発見を保証しない.

• ĥ(m) の与え方によっては, 目標節点を見つけられない (収束しない) こともある.

最良優先探索 (best-first search)

1. 出発節点を OPEN に置く.

2. OPEN が空 ⟹ 失敗.

3. OPEN の最初に位置する節点 (n とする) を取り除き, これを CLOSED に置く.

4. n が目標節点 ⟹ 終了.

5. n のすべての子節点 m が OPEN にも CLOSE にも含まれていなければ, m を OPEN に入れる (子節点から n へポインタをつける).

6. OPEN を ĥ(n) の小さい順に並べ換える.

7. 2. に戻る.

• 最適順路の発見を保証しない.

• グラフが有限であれば, 探索は必ず成功する.

A アルゴリズム (algorithm A)

f̂(m) = ĝ(n) + ĥ(n) を分岐限定法と同様の考え方で評価する.

まず, n の子節点 m について, f̂(m|n) = ĝ(n) + c_{n,m} + ĥ(m) を計算する.

i) m が OPEN にも CLOSED にも含まれていない場合 ĝ(m) := ĝ(m|n) とする.

ii) \underline{m が OPEN に含まれている場合}

f̂(m|n) < f̂(m) なら, m からのポインタを n は付け替え, f̂(m|n) を新たな f̂(m) とする.

iii) \underline{m が CLOSED に含まれている場合}

f̂(m|n) < f̂(m) なら, m からのポインタを n は付け替え, f̂(m|n) を新たな f̂(m) とし, m を OPEN に戻す.

探索は必ず成功するが, 最適順路を発見できる保証はない.

A*アルゴリズム (algorithm A*)

A アルゴリズムにおいて, すべての節点 n に対して hath(n) ≤ h(n) を満たすヒューリスティック関数を用いる. このとき, 必ず最適順路を見つけることができる. ĥ(n) ≡ 0 ならば, A*アルゴリズムは分岐限定法と一致.

1 ヒューリスティック関数 ĥ(m) ：節点 m から目標節点までの最適順路のコストの予測値.

14.2 導出原理

述語論理式 P (x) の恒真性, すなわち ∀xP (x) を証明するには, ¬P (x) が恒偽式であること (充足不能性) を示せばよい.

スコーレム標準形 (Skolem standard form)

∀x_{1} ⋯ ∀x_{m}[C_{1} ∧ ⋯ ∧ C_{n}].

ここで, C_{i} は節 (C_{i} := p_{i1} ∨ ⋯ ∨ p_{ij}; p_{ij} はリテラル).

以下の要領で, 任意の述語論理式をスコーレム標準形に変換する:

1. 含意記号 “→” を除去する.

2. 否定記号を素式の直前にもってくる.

3. 束縛変数を標準化する (各限量記号について, その束縛変数の名前が他の限量記号のものと重複しないように名前を付け替える).

4. スコーレム関数を導入して存在記号を除去する (∀x_{1} ⋯ ∀x_{n}∃y∀z_{1} ⋯ ∀z_{m}P (·) において, y は x_{1}, ⋯ x_{n} に応じて決まり, z_{1}, ⋯, z_{m} には依存しないので, y = f(x_{1}, ⋯, x_{n}) とおける).

5. 冠頭形に変換する (減量記号を前に移す).

6. 母式を連言標準形に変換する. 例 14.2.1

∀x∃y[P (x, y) → Q(x)]

∧¬(∀x∃y[(P (x, y) → ¬R(y)) ∧ ∀zR(z)])

= ∀x∃y[¬P (x, y) ∨ Q(x)]

∧¬(∀x∃y[(¬P (x, y) ∨ ¬R(y)) ∧ ∀zR(z)])

= ∀x∃y[¬P (x, y) ∨ Q(x)]

∧∃x∀y[¬(¬P (x, y) ∨ ¬R(y)) ∨ ¬(∀zR(z))]

= ∀x∃y[¬P (x, y) ∨ Q(x)]

∧∃x∀y[(P (x, y) ∧ R(y)) ∨ ∃z(¬R(z))]

= ∀x_{1}∃y_{1}[¬P (x, y) ∨ Q(x_{1})]

∧∃x_{2}∀y_{2}[(P (x_{2}, y_{2}) ∧ R(y_{2})) ∨ ∃z(¬R(z))]

= ∀x_{1}[¬P (x_{1}, f(x_{1})) ∨ Q(x_{1})]

∧∀y_{2}[(P (a, y_{2}) ∧ R(y_{2})) ∨ ¬R(g(y_{2}))]

= ∀x_{1}∀y_{2}[(¬P (x_{1}, f(x_{1})) ∨ Q(x_{1}))

∧((P (a, y_{2}) ∧ R(y_{2})) ∨ ¬R(g(y_{2})))]

= ∀x_{1}∀y_{2}[(¬P (x_{1}, f(x_{1})) ∨ Q(x_{1}))

∧(P (a, y_{2}) ∨ ¬R(g(y_{2}))) ∧ (R(y_{2}) ∨ R(g(y_{2})))] 節集合

述語論理式をスコーレム標準形:

∀x_{1} ⋯ ∀x_{m}[C_{1} ∧ ⋯ ∧ C_{n}]

で表したとき, 各節からなる集合 C := {C_{1}, ⋯, C_{n}} を節集合 (clause set) という.

導出

素式 p を含む節 C_{i} とその否定形 ¬p を含む節 C_{j} から, 新しい節 C_{ij} を作り出す操作を導出という.

C_{i} = p ∨ q_{1} ∨ ⋯ q_{m} C_{j} = ¬p ∨ r_{1} ∨ ⋯ ∨ r_{n}
↓  ↙
C_{ij} = q_{1} ∨ ⋯ ∨ q_{m} ∨ r_{1} ∨ ⋯ ∨ r_{n}

このとき, C_{i} と C_{j} を親節 (parent clause), C_{ij} を導出節 (resolvent clause) という.

導出原理

節集合 C より適当な節 C_{i} と C_{j} を選び, これらを親節とする導出節 C_{ij} を求め, C に加える (C := C ⊃ {C_{ij}}). この操作を繰り返して空節が得られれば, C は充足不能である. 逆も成立する.

導出の制御戦略

• 横形優先戦略

• 線形導出

導出グラフ (resolution graph)

導出によって充足不能性を証明する様子を表すグラフ. 特に, 空節を根に持つ木であるとき, 導出反駁木 (refutation tree) という.

14.3 ホーン節 ; ホーン節とホーン集合 ; • ホーン節： ; “B ← A_{1}, ⋯, A_{n}” または “← A_{1}, ⋯, A_{n}” ; の形で表される節で, それぞれ, ¬A_{1} ∨⋯∨¬A_{n} ∨B, ; ¬A_{1} ∨ ⋯ ∨ ¬A_{n} を意味する. n = 0 でもよい. ; • ホーン集合：ホーン節からなる集合. ; ホーン集合に対する導出戦略： SNL, SLD ; 1. 最初の導出の一方の親節として, ゴール節を選ぶ. ; 2. 次の導出を行う: ; \begin{matrix}← B, C_{1}, ⋯, C_{m} & B ← A_{1}, ⋯, A_{n} \\ ↓ & ↙ \\ ← A_{1}, ⋯, A_{n}, C_{1}, ⋯, C_{m} \end{matrix} ; 3. 得られた節を一方の親節として, 導出を繰り返す. ; 例 14.3.1 動物を治療できるのは獣医である. 獣医にな ; るには資格が必要である. 太郎は獣医の資格を持ってい ; る. 犬は動物である. ジョンは犬である. 太郎はジョンを ; 治療できることを証明したい. ; 次の述語を用意する: ; T (x, y) : x は y を治療できる; ; V (x) : x は獣医である; ; Q(x) : x は獣医の資格を持っている; ; A(x) : x は動物である; ; D(x) : x は犬である. ; \begin{matrix}← T (T aro, John) & T (x_{1}, y_{1}) ← V (x_{1}), A(y_{1}) \\ ↓ & ↙ \\ ← V (T aro), A(John) & V (x_{2}) ← Q(x_{2}) \\ ↓ & ↙ \\ ← Q(T aro), A(John) & Q(T aro) ← \\ ↓ & ↙ \\ ← A(John) & A(x_{3}) ← D(x_{3}) \\ ↓ & ↙ \\ ← D(John) & D(John) ← \\ ↓ & ↙ \\ □ \end{matrix} 前向き推論と後向き推論

• 前向き推論 (forward reasoning) ：事実 P と推論規則 P → Q から結論 Q を得る.

• 後向き推論 (backward reasoning)：結論 Q の否定 ¬Q を仮定し, ¬Q と P → Q から ¬P を得る. 事実 P が存在すれば矛盾が生じるので ¬Q が棄却され, Q が成り立つ.

SNL は, 後向き推論と等価である.