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
  1. 半群は演算について閉じていることと結合律を示せばよい。
     • 演算が閉じているか
       • w,x∈Bとy,z∈Aを考える。 w*(x*y) = w*(x*z) ⇒ x*y = x*z ⇒ y = z とy,zが先頭にきている場合を考えることによりw*x∈Bが示せる。x*wも同様。
     • 結合律
       • Aが半群であることから従う。
  2. 反射律，対称律，推移律を示せばよい。可換であることに注意。
     • 反射律
       • 自明。
     • 対称律
       • これも自明。
     • 推移律

       • x,x',x~ ∈A,y,y',y~ ∈Cに対して(x,y)R(x',y'),(x',y')R(x~,y~)とする。
         x*y' = x'*y
         x'*y~ = x~*y'
         右からそれぞれy~,yを掛けて、
         x*y'*y~ = x'*y*y~
         x'*y~*y = x~*y'*y
         x'*y~*yに注目すると
         x*y'*y~ = x~*y'*y
         y'の正則性よりx*y~ = x~*y なので(x,y)R(x~,y~)

• 問題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の線形符号なので命題は成り立つ。
  3. GF(2)上の線形符号において最小重みd ⇒ 最小距離d の略証
     • 線形符号は群符号なので符号語は群をなす。したがって各符号語ごとの差は別の符号語で表される。式で書くと任意のx,yを符号語としてある符号語zがあり x-y = z. 従ってxとyの距離はzの重みとなるが、最小重みdなのでx-yの距離は最小d。