章別例題集

各章につき、最低1問の「定義から解く」例を置く。解答は短くしているが、必ず定義に戻る。

第1章 集合と論理

問題: A ⊆ B と B ⊆ C ならば A ⊆ C を示せ。

解答: 任意の x ∈ A を取る。A ⊆ B より x ∈ B。さらに B ⊆ C より x ∈ C。したがって任意の x ∈ A について x ∈ C なので、A ⊆ C。

第2章 関数と関係

問題: 整数上の関係 a R b ⇔ a-b が偶数である、は同値関係か。

解答: 反射律は a-a=0 が偶数なので成り立つ。対称律は a-b が偶数なら b-a=-(a-b) も偶数。推移律は a-b と b-c が偶数なら和 (a-b)+(b-c)=a-c も偶数。よって同値関係である。

第3章 証明技法

問題: n^2 が偶数なら n は偶数であることを示せ。

解答: 対偶を示す。n が奇数なら n=2k+1 と書ける。このとき n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1 なので奇数。よって対偶が成り立つため、元の命題も成り立つ。

第4章 漸近記法

問題: 5n^2 + 3n + 10 = O(n^2) を定義から示せ。

解答: n >= 1 なら 3n <= 3n^2 かつ 10 <= 10n^2。したがって 5n^2+3n+10 <= 18n^2。よって c=18, n0=1 とすれば定義を満たす。

第5章 擬似コードと再帰

問題: sum_to(n) = 1 + ... + n を再帰で定義し、正しさを示せ。

解答: sum_to(0)=0, sum_to(n)=n+sum_to(n-1) とする。帰納法で示す。基底部 n=0 は正しい。sum_to(n-1)=1+...+(n-1) と仮定すると、sum_to(n)=n+sum_to(n-1)=1+...+n。

第6章 グラフと木

問題: 木に閉路がないことを使って、任意の2頂点間の単純パスが一意であることを説明せよ。

解答: 木は連結なので、任意の2頂点間に少なくとも1本のパスがある。もし異なる単純パスが2本あれば、それらを合わせると閉路ができる。これは木が閉路を持たないことに反する。よって一意。

第7章 組合せと数え上げ

問題: 長さ n の 0/1 文字列のうち、1 がちょうど k 個のものはいくつか。

解答: n 個の位置から、1 を置く k 個の位置を選べば文字列が一意に決まる。したがって C(n,k) 個。

第8章 データ構造と基本アルゴリズム

問題: ソート済み配列に対する二分探索が O(log n) である理由を説明せよ。

解答: 各反復で探索範囲が高々半分になる。t 回後の候補数は高々 n/2^t。これが1以下になるには 2^t >= n、つまり t >= log2 n が必要。したがって反復回数は O(log n)。

第9章 形式言語の入口

問題: 1 の個数が偶数である 0/1 文字列を受理する DFA の状態の意味を説明せよ。

解答: 状態を Even と Odd にする。Even は読んだ接頭辞に含まれる 1 の個数が偶数であること、Odd は奇数であることを表す。0 では状態を変えず、1 では偶奇が反転する。受理状態は Even。

第10章 確率の基礎

問題: P(A)=0.4, P(B|A)=0.5, P(B|¬A)=0.2 のとき P(B) を求めよ。

解答: 全確率の公式より、P(B)=P(A)P(B|A)+P(¬A)P(B|¬A)=0.4*0.5+0.6*0.2=0.32。

第11章 数論・代数の基礎

問題: 7 の mod 26 における逆元を求めよ。

解答: 7x ≡ 1 (mod 26) を満たす x を探す。7*15=105 で、105 ≡ 1 (mod 26)。したがって逆元は 15。

第12章 線形代数の最小限

問題: F_2 上で 1011 と 1110 の和を求めよ。

解答: F_2 では各成分を mod 2 で足す。1011 + 1110 = 0101。

第13章 並行性と形式モデルの入口

問題: safety と liveness の違いを例で説明せよ。

解答: safety は「悪いことが起きない」という性質である。例: 共有カウンタが負にならない。liveness は「良いことがいつか起きる」という性質である。例: 要求された処理がいつか完了する。前者は有限の反例で壊れたことを示しやすいが、後者は無限実行を考える必要がある。