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

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

• 問題1A
  1. 1,2,3,2,1の形になった
  2. 辞書順一直線
• 問題1B

  • k に関する帰納法。 x ≦ (y₁∨……∨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 とXの d -1個のベクトルの一次独立性を示せば終わり。

  2. • 左辺の1を移項して(1)の結果を利用する。i = n -1。
       検査行列Hとして、(1)の条件を満たすように作られた列ベクトル x_i を並べたものを考える。符号語 p = ( p₁ , ……, p_n ) を検査すると、
       p * H^T = p₁ * x₁ + p₂ * x₂ + …… + p_n * x_n = 0 （符号語ならば検査結果は0）
       これと任意の d 個のベクトルが一次独立であることを用いると p_i のうち d +1個以上は0でないことがわかる。したがって最小重み d +1の線形符号なので命題は成り立つ。

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