2010年度　情報数学期末試験略解

単位がヤバいと思う人はこれを参考に須田先生にお願いするといいことがあるかもしれませんが、正しさは保証しません。

• 問題1A
  1. 1,2,3,2,1の形になった
  2. 辞書順一直線
• 問題1B
  • kに関する帰納法。 x ≦ (y_1∨……∨y_(i-1)∨y_(i+1)+∨……∨y_k) ∨ y_i に対してxが既約であることを用いる。 x=y ⇒ x≦y を用いて帰納法の仮定を適用。
• 問題2A
  • 加法+と乗法*が定義された集合Xが体であるとき、以下に示す条件を満たす。
  • Xは+について可換群をなす。すなわち、
    1. 演算+について閉じている
    2. 結合律が成り立つ
    3. 単位元0が存在
    4. 任意の元に対して逆元（-1倍）が存在
  • X-{0}は*について可換群をなす。すなわち、
    1. 演算*について閉じている
       • (a+b√2)*(c+d√2)を具体的に計算。
    2. 結合律が成り立つ
    3. 単位元1が存在
    4. 任意の元に対して逆元（逆数）が存在
       • 1/(a*b√2)がQ(√2)の元であることを示す。分母を有理化。
  • 分配律が成り立つ
    • 詳しく書いていないものはほぼ自明か有理数体の性質から従う。
• 問題2B
• 問題3A
  • 解けませんでした……
• 問題3B
  1. • Xからd-1個以下のベクトルを組み合わせて生成できるのはi個の中からd-1個以下を組み合わせるので不等式の左辺となる。 GF(2)上のm次列ベクトルは零ベクトル以外全部で2^m -1個（不等式の右辺）ある。 よって、不等式が成り立つならばxからd-1個以下のベクトルを組み合わせて生成できないベクトルが存在するのでこれをx_i+1とすればよい。 あとはx_i+1とd-1個のベクトルの一次独立性を示せば終わり。
  2. • 左辺の1を移項して(1)の結果を利用する。i=n-1。 検査行列Hとして、(1)の条件を満たすように作られた列ベクトルx_iを並べたものを考える。符号語p = (p_1, ……, p_n)を検査すると、 p*H^T = p_1*x_1 + p_2*x_2 + …… + p_n*x_n = 0 （符号語ならば検査結果は0） これと任意のd個のベクトルが一次独立であることを用いるとp_iのうちd+1個以上は0でないことがわかる。したがって最小重みd+1の線形符号なので命題は成り立つ。