統合到達確認テスト 解答

A. Core

A1. ∀x (x∈A → x∈B)。

A2. ∃x∈S, P(x) ∧ ¬Q(x)。

A3. ¬Q→¬P と ¬P∨Q。

A4. ∀x,y∈A, f(x)=f(y) → x=y。

A5. 反射律、対称律、推移律。

A6. 半順序は任意の2要素が比較可能とは限らない。全順序は任意の2要素が比較可能である。

A7. n が奇数なので n=2k+1 と書ける。すると n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1 なので奇数。

A8. n が奇数ならば n^2 は奇数である。

A9. 基底ステップでは最初の値で命題が成り立つことを示す。帰納ステップでは、k で成り立つと仮定して k+1 で成り立つことを示す。

A10. n≥1 で 4n^3+2n+9 ≤ 4n^3+2n^3+9n^3 = 15n^3。よって c=15, n0=1 とすれば O(n^3)。

A11. log n < sqrt(n) < n < n log n < n^2。

A12. 内側の実行回数は 1+2+...+n = n(n+1)/2 なので Θ(n^2)。

A13. 各反復で j が半分になるため Θ(log n)。

A14. 基底条件があること、再帰呼び出しごとに基底条件へ近づく測度が減少すること。

A15. 例:

for i = 0 to n-1:
    if A[i] == x:
        return i
return NOT_FOUND

A16. 配列が探索キーでソート済みであること。

A17. ループの各反復の前後で保たれる性質。初期化・保存・終了時の利用で正しさを示す。

A18. ε は長さ0の文字列。∅ は要素を持たない集合。

A19. 文字列、式、木、リスト、構文木など。

A20. 仕様は何を満たすべきかを述べるもの。実装はそれをどの手順やデータ構造で実現するかを述べるもの。

B. Standard

A21. G=(V,E)。V は頂点集合、E は頂点対または2要素部分集合からなる辺集合。

A22. パスは辺に沿って頂点をたどる列。閉路は始点と終点が同じパス。連結性は任意の2頂点間にパスがあること。

A23. n-1。木は連結で閉路を持たないため、頂点を1つ増やすごとに辺が1本増えると考えられる。

A24. BFS は始点からの距離が近い順に層状に探索する。DFS は進める限り深く進んでから戻る。

A25. 隣接行列は O(|V|^2)。隣接リストは O(|V|+|E|)。

A26. C(n,k)。

A27. 3の倍数は33個、5の倍数は20個、15の倍数は6個。よって 33+20-6=47。

A28. 例: 13人いれば、少なくとも同じ月に生まれた人が2人いる。12か月を箱、13人を物と見る。

A29. ADT は操作と意味の仕様。実装は配列、リスト、木などでその仕様を実現する方法。

A30. ハッシュが分散すれば各バケットが小さく平均定数時間。多数の衝突が起これば同じバケット内を線形に探索するため最悪線形時間。

A31. 根を削除後、最後の要素を根に置き、ヒープ条件を回復するために木の高さ分だけ下げる。完全二分木の高さは O(log n)。

A32. 集合の併合と、2要素が同じ集合に属するかの判定。連結成分管理など。

A33. Σ は記号の集合。Σ* は Σ 上のすべての有限文字列の集合。

A34. M=(Q,Σ,δ,q0,F)。状態集合、アルファベット、遷移関数、初期状態、受理状態集合。

A35. NFA は確率で遷移を選ぶのではなく、受理経路が少なくとも1つ存在するかで受理を定義するため。

C. Extended

A36. Pr[A|B]=Pr[A∩B]/Pr[B]。ただし Pr[B]>0。

A37. Pr[A∩B]=Pr[A]Pr[B]。

A38. 排反は同時に起きないこと。独立は片方が起きてももう片方の確率が変わらないこと。正の確率を持つ排反事象は独立ではない。

A39. E[I_A]=Pr[A]。

A40. 252=2*105+42, 105=2*42+21, 42=2*21+0。よって gcd(252,105)=21。

A41. n | (a-b) が成り立つこと。

A42. gcd(a,n)=1。

A43. 閉性、結合律、単位元の存在、逆元の存在。

A44. n 次元ベクトルを m 次元ベクトルへ写す。

A45. 1。F_2 では mod 2 で計算するため 1+1+1 = 3 ≡ 1。

A46. 同じ長さの2つの文字列またはベクトルが異なる位置の数。

A47. S は状態集合、→ は遷移関係、s0 は初期状態。

A48. 非決定性は複数の遷移が可能であることだけを表し、確率は割り当てない。確率では各選択肢に確率分布が与えられる。

A49. safety は悪いことが起きない性質で、有限の悪いprefixで反例を示せる。liveness は良いことがいつか起きる性質で、任意の有限prefixからまだ満たされる可能性が残る。

A50. 一致性、妥当性、終了性。

判定補足

• Q7, Q8, Q10, Q23, Q49 は、説明不足なら0.5点減点。
• Q2 は ∃x∈S を落としている場合は部分点。
• Q30 は平均と最悪の区別がなければ部分点。
• Q35 は「どれか1つをランダムに選ぶ」と書いた場合は不正解。
• Q49 は safety/liveness の反例の違いまで書ければ満点。