Extended 演習
目的
この演習は、本体教科書の情報理論・暗号・並行計算を読むための前提を確認するものです。
対象範囲:
- 第10章 確率の基礎
- 第11章 数論・代数の基礎
- 第12章 線形代数の最小限
- 第13章 並行性と形式モデルの入口
難易度ラベル
- [A] 基本: 定義を読む・単純計算をする。
- [B] 標準: 複数の定義を組み合わせる。
- [C] 発展: 証明・設計・実装の説明が必要。
- [D] 実装: 実行可能なコードまたは明確な擬似コードが必要。
- [E] 接続: 本体教科書の概念へ橋渡しする。
J. 確率の基礎
E1. [A][確率] 公平なコインを3回投げる。標本空間 Ω の要素数を求めよ。
E2. [A][確率] 公平なコインを3回投げる。表がちょうど2回出る確率を求めよ。
E3. [A][確率] サイコロを1回振る。A={偶数}, B={4以上} とする。Pr[A|B] を求めよ。
E4. [A][確率] Pr[A]=1/2, Pr[B]=1/3, Pr[A∩B]=1/6 のとき、A と B は独立か。
E5. [A][確率] Pr[A]=1/2, Pr[B]=1/3, A∩B=∅ のとき、A と B は独立か。
E6. [A][確率] 条件付き確率の定義から、ベイズの定理を導け。
E7. [A][確率] 公平なサイコロの出目を X とする。E[X] を求めよ。
E8. [B][確率] 公平なコインを n 回投げる。表の回数を X とする。指示変数を使って E[X] を求めよ。
E9. [B][確率] 確率 p で1、確率 1-p で0を取る Bernoulli 確率変数 X について、E[X] を求めよ。
E10. [B][確率] X ~ Bin(n,p) のとき、Pr[X=k] を書け。
E11. [B][確率] X ~ Bin(n,p) のとき、E[X] を求めよ。
E12. [B][確率] 非負確率変数 X について、Markov不等式の形を書け。
E13. [B][確率] E[X]=10 の非負確率変数について、Pr[X≥50] を Markov不等式で上から抑えよ。
E14. [B][確率] Var[X]=4 の確率変数について、Pr[|X-E[X]|≥10] を Chebyshev不等式で上から抑えよ。
E15. [C][確率] Las Vegas アルゴリズムと Monte Carlo アルゴリズムの違いを説明せよ。
E16. [C][確率] 非決定性と確率的選択の違いを説明せよ。
E17. [C][確率] 確率変数が数学的には関数である、とはどういう意味か。
E18. [C][確率] Pr[A|B] の定義において Pr[B]>0 が必要な理由を説明せよ。
E19. [C][確率] E[X+Y]=E[X]+E[Y] が成り立つために X と Y の独立性は必要か。
E20. [C][確率] エントロピー H(X)=-Σ_x Pr[X=x] log Pr[X=x] を読むために必要な確率の概念を3つ挙げよ。
K. 数論・代数の基礎
E21. [A][数論] a | b の定義を書け。
E22. [A][数論] 29 mod 5 を求めよ。
E23. [A][数論] gcd(84,30) を Euclidの互除法で求めよ。
E24. [A][数論] 17 ≡ 2 (mod 5) が成り立つ理由を説明せよ。
E25. [A][数論] a ≡ b (mod n) の定義を書け。
E26. [A][数論] 3 の mod 7 における逆元を求めよ。
E27. [A][数論] 2 の mod 6 における逆元は存在するか。理由も述べよ。
E28. [B][数論] mod n で a が逆元を持つための必要十分条件を書け。
E29. [B][数論] 7 = 2・3 + 1 から、3^{-1} mod 7 を Bézout 等式で求めよ。
E30. [B][数論] Fermatの小定理を述べよ。
E31. [B][数論] 3^6 mod 7 を Fermatの小定理で求めよ。
E32. [B][数論] 群の4条件を列挙せよ。
E33. [B][数論] 整数全体 Z が加算について群であることを、単位元と逆元に注目して説明せよ。
E34. [B][数論] Z_8^* の要素を列挙せよ。
E35. [C][数論] 巡回群と生成元の意味を説明せよ。
E36. [C][数論] mod 7 の乗法群で、3 のべき乗を列挙し、3 が生成元か判定せよ。
E37. [C][数論] 離散対数問題を式で説明せよ。
E38. [C][数論] 体とは何か。0で割れないことにも触れて説明せよ。
E39. [C][数論] F_2 で 1+1 は何か。
E40. [C][数論] mod n で両辺を a で割ってよい条件を述べよ。
L. 線形代数の最小限
E41. [A][線形代数] m×n 行列が、どの次元のベクトルをどの次元のベクトルへ写すか説明せよ。
E42. [A][線形代数] 次を計算せよ。
[1 2] [5]
[3 4] [6]
E43. [A][線形代数] 行列積 AB が定義できる条件を述べよ。
E44. [A][線形代数] 行列積が一般に可換でないとはどういう意味か。
E45. [A][線形代数] 単位行列の役割を説明せよ。
E46. [A][線形代数] 逆行列 A^{-1} の定義を書け。
E47. [A][線形代数] 線形結合の定義を書け。
E48. [B][線形代数] span(S) の意味を説明せよ。
E49. [B][線形代数] 線形独立の定義を書け。
E50. [B][線形代数] R^2 の標準基底を挙げよ。
E51. [B][線形代数] 線形写像の2条件を書け。
E52. [B][線形代数] 次の行列のランクを求めよ。
[1 2]
[2 4]
E53. [B][線形代数] Ax=b を連立一次方程式として読むとはどういうことか。
E54. [B][線形代数] ガウス消去法で許される行基本変形を3つ挙げよ。
E55. [C][線形代数] ker(A) の意味を説明せよ。
E56. [C][線形代数] im(A) の意味を説明せよ。
E57. [C][線形代数] F_2 上で (1,0,1)+(1,1,0) を計算せよ。
E58. [C][線形代数] 線形符号における生成行列 G の役割を説明せよ。
E59. [C][線形代数] 検査行列 H による条件 Hc^T=0 の意味を説明せよ。
E60. [C][線形代数] 10110 と 10011 の Hamming 距離を求めよ。
M. 並行性と形式モデルの入口
E61. [A][並行性] 状態遷移システム T=(S, ->, s0) の3要素を説明せよ。
E62. [A][並行性] 到達可能状態とは何か。
E63. [A][並行性] 遷移関係が関数ではなく関係として定義される理由を説明せよ。
E64. [A][並行性] 非決定性と確率の違いを説明せよ。
E65. [A][並行性] P: a; b, Q: c; d の interleaving を1つ挙げよ。
E66. [A][並行性] trace とは何か。
E67. [A][並行性] safety の例を1つ挙げよ。
E68. [B][並行性] liveness の例を1つ挙げよ。
E69. [B][並行性] safety と liveness の違いを説明せよ。
E70. [B][並行性] invariant による safety 証明の2段階を述べよ。
E71. [B][並行性] race condition とは何か。
E72. [B][並行性] 共有メモリモデルとメッセージパッシングモデルの違いを説明せよ。
E73. [B][並行性] happens-before が半順序であるとはどういう意味か。
E74. [B][並行性] 線形化可能性の直観を説明せよ。
E75. [C][並行性] 合意問題の3条件を挙げよ。
E76. [C][並行性] crash failure と Byzantine failure の違いを説明せよ。
E77. [C][並行性] synchronous model と asynchronous model の違いを説明せよ。
E78. [C][並行性] Petriネットの place、transition、token の意味を説明せよ。
E79. [C][並行性] モデル検査の基本的な流れを3段階で説明せよ。
E80. [C][並行性] state explosion とは何か。