The Art of Computer Programming を読む 1P - 19P

超無理ゲー。地球防衛軍をプレイして数時間で間違って難易度をHARDEST選択してしまった時の気分。

なので1節か1小節くらいに超小分けにして読んで行く。
当分は1章の基礎概念。

1.1アルゴリズム

アルゴリズムという言葉の現代の意味は、レシピ、過程、方法、手法、手続き、ルーティンワーク、煩雑な手続きという言葉に似ている。しかしアルゴリズムはこれらとは少し違い、問題を解くための重要な特徴がある。

有限性
明確性
入力
出力
実効性

有限性とは

アルゴリズムは必ず終了する必要がある。すなわち、答えを導く過程が発散してはならない。

明確性とは

アルゴリズムの各ステップは明確に定義されていなければならない。曖昧さがあってはならない。現実的な問題として、プログラミング言語でアルゴリズムを表す際は明確に記述できるが、日本語や英語でアルゴリズムの記述を行う場合は曖昧さが産まれるので注意が必要である。

入力とは

アルゴリズムは0個以上の入力を持つ。入力とは、アルゴリズムが開始する前に最初に与えられるか、アルゴリズムの実行中に動的に与えられる量のことである。

出力とは

アルゴリズムは1個以上の出力を持つ。出力とは、入力との間に指定された関係を持つ量のことである。

実効性とは

アルゴリズムの処理は十分に基本的で紙と鉛筆があれば有限時間内に正確に実行できることが期待される。

1.2 数学的な基礎

1.2.1 数学的帰納法

数学的帰納法は超重要。ハイパー重要。証明に必要な道具としてだけでなく、そもそも数学の体系には根底から帰納法が組み込まれているから。
本書でクヌースは以下のように述べている。

結局のところ,整数のあらゆる性質を証明するためには,どこかで帰納法を使わなければならない.なぜかというと、基本概念まで掘り下げていけば,整数と言うものは本質的に帰納法的に定義されているからである.

帰納法は、定義や公理レベルで数の概念と密接に結びついている。例えばペアノの公理。この第五公理は帰納法である。

自然数 0 が存在する。

任意の自然数 a にはその後者 (successor)、suc(a) が存在する（suc(a) は a + 1 の "意味"）。

0 はいかなる自然数の後者でもない（0 より前の自然数は存在しない）。

異なる自然数は異なる後者を持つ：a ≠ b のとき suc(a) ≠ suc(b) となる。

0 がある性質を満たし、a がある性質を満たせばその後者 suc(a) もその性質を満たすとき、すべての自然数はその性質を満たす。

http://ja.wikipedia.org/wiki/ペアノの公理

このように帰納法は数の概念のレベルまで分解しても現れてくるものであり、理解は必須である。

数学的帰納法を用いた証明の仕方

ある命題 $P(n)$ を解くとする。

手順1: P(1)が真であることを確かめる。
手順2: 「 P(1), P(2), P(3), ... ,P(n) がすべて真であるなら、P(n+1) も真である」ことを証明する。

P(1)の時はほぼすべての問題で簡単に成り立つのでまぁ良い。問題は P(n+1) が真であることを証明するとき。この P(n+1) を証明する際の道具として、P(n) が真であるということを利用する。

何故利用してよいか？そう仮定したから。

俺みたいな底辺にとって重要なのは、P(n) が正しいことがわかったと言う事よりも帰納法の概念と手順。成果は知ったらオシマイケルだけど道具の使い方を知ればあちこちで使えるから。

演習問題の解答 (18P)

簡単すぎず、なんとか解けたレベルの演習問題の解答を載せようと思う。問の後ろの[]の中の数字はクヌースが決めた難易度。

問7[23]

$1^2,2^2 - 1^2, 3^2 - 2^2 + 1^2, 4^2 - 3^2 + 2^2 - 1^2, 5^2 - 4^2 + 3^2 - 2^2 + 1^2$ などの値を求めるための規則を定立し、帰納法によって証明せよ。

まず規則を見つけ出す。見つけるためにそれぞれ答えを出す。
$1^2 = 1$
$2^2 - 1^1 = 3$
$3^2 - 2^2 + 1^1 = 6$
$4^2 - 3^2 + 2^2 - 1^1 = 10$
$5^2 - 4^2 + 3^2 - 2^2 + 1^1 = 15$

得られた解、1,3,6,10,15 から、これらの解は n の総和であると考えられる。一般式にするとこうなる。
$n^2 - (n-1)^2 + (n-2)^2 - (n-3)^2 + ... -( -1^n ) = \frac{n(n+1)}2$

この式を帰納法で証明する。

まず手順1. n = 1の場合。
$1^2 = 1$
よって成り立つ。

次に、手順2. n = kの場合で成り立つと仮定する。
$k^2 - (k-1)^2 + (k-2)^2 - (k-3)^2 + ... -( -1^k ) = \frac{k(k+1)}2$

上の式が成り立つと仮定して以下の式が正しいことを証明する。( P(n+1)が真であることを確かめる手順 )
これは、n = k + 1 と置いた時の式である。
$(k+1)^2 - k^2 + (k-1)^2 - (k-2)^2 + (k-3)^2 + ... -( -1^{k+1} ) = \frac{(k+1)(k+2)}2$

左辺に注目する。左辺を L と置くとする。この式を変形して右辺に近づけたい。
$L = (k+1)^2 - k^2 + (k-1)^2 - (k-2)^2 + (k-3)^2 + ... -( -1^{k+1} )$

よーく注目すると、以下のように変形できる。二項目以降の符号を反転し、最後のk+1をkにすることでさらに符号を反転させ、元に戻す。
$L = (k+1)^2 - (k^2 - (k-1)^2 + (k-2)^2 - (k-3)^2 + ... -( -1^k ))$
この式はの括弧でくくった部分は n = k としたときの左辺に等しい。このことから、括弧の中の数式を n = k のときの右辺に置き換えることができる。だって n = k のときは成り立つと仮定したから。
$L = (k+1)^2 - \frac{k(k+1)}2$

あとはこいつを展開してごにょごにょやると、あら不思議！以下のようになる。
$L=\frac{(k+1)(k+2)}2$

これはつまり、n = k + 1 とした時の右辺だ！ということで無事右辺 = 左辺となり、命題は証明された。

問9[20]

以下の命題を証明せよ。
条件： $0 < a < 1$
$(1-a)^n \geq 1-an$

まず n = 1の場合。
$1-a \geq 1-a$
となり、真である。

次に n = k と置き、これが成り立つと仮定する。
$(1-a)^k \geq 1-ak$

ここから、 n = k + 1 が真であることを確かめる。
$(1-a)^{k+1} \geq 1-a(k+1)$

上の式の左辺をLと置き、以下のように変形する。
$L = (1-a)(1-a)^k$

$(1-a)^k$ は $1-ak$ より大きいので、式はこうなる。
$L = (1-a)(1-a)^k$
$\geq (1-a)(1-ak)$
$= 1-a(k+1) + a^{2}k$

$1-a(k+1)$ は n = k +1 と置いたときの命題の右辺である。
$a^{2}k$ はaが0以上であることとkが正の整数であることから、常に正である。
つまり $1-a(k+1) + a^{2}k$ は右辺より常に $a^{2}k$ 分大きい。

よって命題は証明された。

問8[25]は(a), (b)共に解けたのだけど著者の意図してる解き方とはおそらく違うので割愛。一応メモだけ。
(a)は一般式を以下のように仮定して帰納法で解く。
$n^3 = \sum_{i=1}^n n^2-n+1+2(i-1)$

(b)は命題を変形して解く。つまりこう。
$\sum_{i=1}^n i^3 = (\sum_{i=1}^n i)^2$

でも(a)は綺麗な解き方ではないような気がするし、(b)は(a)を利用できていないのでもっと綺麗な解法があるのだろう。

感想

Web上に数式書くのってなんでこんなに進歩してないんだ？いい加減Web上でも数式のWYSIWYGエディタが使える頃になっても良いと思うのだけど。フォントも汚いし。あとhatenaってtex記法使っても式番号はつけられないのかね。不便。

帰納法でいくつか問題解いてみて思ったけど、数学の問題解くプロセスってプログラム書くのに似てるよ。Σがfor文に見えてくる。式を別の文字に置き換えるのは関数化。汚い数式はリファクタ。定理は便利ツール。それから命題を証明するために色々細かい補題を証明するプロセスは、プログラムの世界で頻繁に聞く困難の分割ってやつだ。似てる。短い方が美しいけど、ショートコーディングほど短くしてしまうと理解が困難になり、やりすぎは美しさを損ねるところも似てる。

しかしそれにしてもとんでもないモンスター本に手を出してしまったものだ。20P読むのに1時間、演習問題解くのに数時間かかった。とにかく濃厚だ。

こんな濃厚な本をもし真面目に読んだら、他の本がただの紙っペラに見えちゃうよ。