Extended 演習 解答
J. 確率の基礎
E1. 各回で H/T の2通りがあるので 2^3=8。
E2. 表が2回の列は C(3,2)=3 個。全体は8個なので 3/8。
E3. A={2,4,6}, B={4,5,6}, A∩B={4,6}。したがって Pr[A|B]=2/3。
E4. 独立である。Pr[A]Pr[B]=(1/2)(1/3)=1/6=Pr[A∩B]。
E5. 独立ではない。Pr[A∩B]=0 だが Pr[A]Pr[B]=1/6。
E6. Pr[A|B]=Pr[A∩B]/Pr[B]、Pr[B|A]=Pr[A∩B]/Pr[A] より、Pr[A∩B]=Pr[B|A]Pr[A]。これを最初の式へ代入して、Pr[A|B]=Pr[B|A]Pr[A]/Pr[B]。
E7. E[X]=(1+2+3+4+5+6)/6=21/6=3.5。
E8. i 回目が表なら1、そうでなければ0を取る指示変数を I_i とする。X=Σ_i I_i、E[I_i]=1/2。期待値の線形性により E[X]=n/2。
E9. E[X]=1・p + 0・(1-p)=p。
E10. Pr[X=k]=C(n,k)p^k(1-p)^(n-k)。
E11. E[X]=np。Bernoulli確率変数の和として表し、期待値の線形性を使う。
E12. X≥0 について、Pr[X≥a] ≤ E[X]/a。ただし a>0。
E13. Pr[X≥50] ≤ E[X]/50 = 10/50 = 1/5。
E14. Pr[|X-E[X]|≥10] ≤ Var[X]/10^2 = 4/100 = 1/25。
E15. Las Vegas は常に正しい答えを返すが実行時間が確率的に変わる。Monte Carlo は実行時間を制御しやすいが、一定確率で誤答することがある。
E16. 非決定性は複数の選択肢が可能であるという形式化であり、確率分布を指定しない。確率的選択は、各選択肢に確率が割り当てられている。
E17. 確率変数 X は、各結果 ω∈Ω に実数などの値 X(ω) を対応させる関数 X:Ω->R である。
E18. Pr[A|B]=Pr[A∩B]/Pr[B] なので、Pr[B]=0 だと0で割ることになり定義できない。
E19. 必要ない。期待値の線形性は独立でなくても成り立つ。
E20. 例: 確率変数、確率分布 Pr[X=x]、総和、期待値、対数。3つなら、確率変数、確率分布、総和でよい。
K. 数論・代数の基礎
E21. ある整数 k が存在して b=ak と書けること。
E22. 29=5・5+4 なので 29 mod 5 = 4。
E23. gcd(84,30)=gcd(30,24)=gcd(24,6)=gcd(6,0)=6。
E24. 17-2=15 が5で割り切れるため。
E25. n | (a-b) が成り立つこと。
E26. 3・5=15≡1 (mod 7) なので逆元は 5。
E27. 存在しない。gcd(2,6)=2≠1 なので逆元を持たない。
E28. gcd(a,n)=1。
E29. 7=2・3+1 より 1=7-2・3。mod 7 で 3・(-2)≡1。-2≡5 なので逆元は 5。
E30. p が素数で p∤a なら、a^(p-1)≡1 (mod p)。
E31. p=7, a=3 で 7∤3 なので、3^6≡1 (mod 7)。
E32. 閉性、結合律、単位元の存在、逆元の存在。
E33. 加算に関して単位元は 0。任意の整数 a に対し逆元は -a。加算は整数に閉じており、結合律も成り立つ。
E34. Z_8^*={1,3,5,7}。8と互いに素な剰余類。
E35. ある要素 g のべき乗だけで群の全要素が得られる群が巡回群で、g が生成元。
E36. 3^1≡3, 3^2≡2, 3^3≡6, 3^4≡4, 3^5≡5, 3^6≡1 (mod 7)。{1,2,3,4,5,6} をすべて生成するので生成元である。
E37. 群 G=<g> で h=g^x が与えられたとき、指数 x を求める問題。
E38. 加算・減算・乗算・除算ができる代数構造。ただし、0による除算は定義しない。
E39. 0。F_2 では mod 2 で計算するため。
E40. a が mod n で逆元を持つこと、すなわち gcd(a,n)=1。
L. 線形代数の最小限
E41. m×n 行列は、n 次元ベクトルを m 次元ベクトルへ写す。
E42. [[1,2],[3,4]] [5,6]^T = [1・5+2・6, 3・5+4・6]^T = [17,39]^T。
E43. A が m×n、B が n×k のとき。つまり、左行列の列数と右行列の行数が一致すること。
E44. 一般には AB=BA が成り立たないこと。片方しか定義できない場合もある。
E45. 任意のベクトルや行列を掛けても変えない。Ix=x、適切なサイズで IA=A, AI=A。
E46. 正方行列 A に対して、AB=BA=I を満たす行列 B。この B を A^{-1} と書く。
E47. ベクトル v_i とスカラー a_i に対する a_1v_1+...+a_kv_k。
E48. 与えられたベクトル集合の線形結合全体。つまり、そのベクトルたちで作れる範囲。
E49. a_1v_1+...+a_kv_k=0 を満たす係数が、すべて a_i=0 の場合だけであること。
E50. (1,0) と (0,1)。
E51. T(u+v)=T(u)+T(v) と T(cv)=cT(v)。
E52. ランクは 1。2行目は1行目の2倍で、独立な行は1本だけ。
E53. 行列 A が係数、ベクトル x が未知数、ベクトル b が右辺を表すと読むこと。
E54. 行の入れ替え、行の非零スカラー倍、ある行に別の行のスカラー倍を加える操作。
E55. ker(A)={x | Ax=0}。行列により0へ写される入力全体。
E56. im(A)={Ax | x はベクトル}。行列により到達できる出力全体。
E57. F_2 上では 1+1=0 なので、(1,0,1)+(1,1,0)=(0,1,1)。
E58. メッセージベクトルを符号語へ写す行列。典型的には c=uG。
E59. c が符号空間に属するための線形制約を満たす、という意味。
E60. 10110 と 10011 は3番目と5番目が異なるので距離は 2。
M. 並行性と形式モデルの入口
E61. S は状態集合、-> は遷移関係、s0 は初期状態。
E62. 初期状態から0回以上の遷移で到達できる状態。
E63. 並行性や非決定性により、1つの状態から複数の次状態へ進める場合があるため。
E64. 非決定性は複数の遷移が可能であるという記述で、確率を割り当てない。確率モデルでは遷移や選択肢に確率が与えられる。
E65. 例: a c b d。各プロセス内の順序 a<b, c<d は保たれている。
E66. 実行で観測されるイベント列。
E67. 例: 2つのプロセスが同時にクリティカルセクションへ入らない。
E68. 例: 要求したプロセスがいつか応答を受け取る。
E69. safety は悪いことが起きない性質。liveness は良いことがいつか起きる性質。
E70. 初期状態で不変条件が成り立つことを示す。次に、不変条件が成り立つ任意の状態から1遷移しても不変条件が保たれることを示す。
E71. 複数の処理の実行順序によって結果が変わる問題。
E72. 共有メモリは複数プロセスが同じ変数やメモリを読む・書く。メッセージパッシングはプロセス間でメッセージを送受信して通信する。
E73. すべてのイベント対に順序が付くわけではなく、因果関係があるイベント間だけに順序が付くという意味。
E74. 並行操作が重なっていても、各操作がどこか一瞬で実行されたような逐次順序として説明できる性質。
E75. 一致性、妥当性、終了性。
E76. crash failure はプロセスが停止する故障。Byzantine failure は任意の不正・矛盾した振る舞いを許す故障。
E77. synchronous model はメッセージ遅延や処理時間に既知の上限がある。asynchronous model はそのような既知の上限がない。
E78. place は条件や資源、transition はイベントや動作、token は現在存在する資源や状態を表す。
E79. 例: システムを状態遷移モデルにする。仕様を論理式やオートマトンで表す。到達可能状態を探索して仕様違反を調べる。
E80. 状態数が組合せ的に増大し、探索や検証が困難になる現象。