目的

この記事では、応用情報技術者試験の出題分野である離散数学に関する覚書きを列挙する。

基数変換

対象となる数の基数（桁上がりする基準の数でN進数のNにあたる）を異なる基数へ変換する。

• 例 \(1\) : 整数の基数変換 \(10\) → \(2\)

  \((25)_{10}\) の基数を \(2\) に変換する。
  変換元の基数と変換先の数の剰余から導く。

  \(25 \div 2 = 12 \) 余り \( 1 \)
  \(12 \div 2 = 6 \) 余り \( 0 \)
  \(6 \div 2 = 3 \) 余り \( 0 \)
  \(3 \div 2 = 1 \) 余り \( 1 \)
  \(1 \div 2 = 0 \) 余り \( 1 \)
  → 最後の剰余から順に並べて \((11001)_{2}\)

• 例 \(2\) : 整数の基数変換 \(10\) → \(16\)

  \((555)_{10}\) の基数を\(15\)に変換する。
  変換元の基数と変換先の数 の剰余から導く。

  \(555 \div 16 =  34 \) 余り \( 11(B) \)
  \(34 \div 16 = 2 \) 余り \( 2 \)
  \(2 \div 16 = 0 \) 余り \( 2 \)
  → 最後の剰余から順に並べて \((22B)_{16}\)

• 例 \(3\) ： 小数の基数変換 \(10\) → \(2\)

  \((0.75)_{10}\) の基数を \(2\) に変換する。
  変換元の数に変換先の基数をかけた整数部から導く。

  \(0.75 \times 2 = 1.50\) → 整数部 \(1\)
  \(0.50 \times 2 = 1.00\) → 整数部 \(1\)
  \(0.00 \times 2 = 0.00\) → 整数部 \(0\)
  → 最後の整数部から順に並べて \((0.11)_{2}\)

• 例 \(4\) ： 小数の基数変換 \(2\) → \(10\)

  \((110.01)_{2}\) の基数を \(10\) に変換する。
  変換元の各桁に基数のべき乗をかけた総和から導く。

  \((110.01)_{2}\)
  \( = 1 \times 2^{2} + 1 \times 2^{1}\) \(+ 0 \times 2^{0} + 0 \times 2^{-1}\) \(+ 1 \times 2^{-2}\)
  \(= 4 + 2 + 0\) \(+ 0 + 0.25\) \(= (6.25)_{10}\)

補数表現（負の表現）

• 補数表現
  対象の数（決められた基数と桁数の条件下）に加算すると桁上がりする最小の数。

  • 例 \(1\) : \(2\) 桁の \(10\) 進数 \((55)_{10}\) の補数。

    \(10^{2} - (55)_{10}\) \(= (45)_{10}\)

  • 例 \(2\) : \(8\) 桁の \(2\) 進数 \((00001101)_{2}\) の補数。

    ※ \(2\)進数の場合、全桁（ビット）反転して1を加算する。
    → \((11110011)_{2}\)

• 補数表現するメリット
  減算を加算のみで表現できる。
  

  • 例 \(1\) : \((25)_{10} - (13)_{10}\) を加算のみで表現する。

    \((25)_{10} - (13)_{10}\) \(= (25)_{10} + ( - 13)_{10}\)
    ここで負の表現を補数表現で置き換えると、\((25)_{10} + (87)_{10}\) \(= (112)_{10}\)
    よって、\(2\) 桁の範囲で見ると \(12\) となる。

  • 例 \(2\) : \((25)_{10} - (14)_{10}\) を \(2\)進数で加算のみで表現する。

    \((25)_{10} - (14)_{10}\) \(= (00011001)_{2}\) \(- (00001110)_{2} \)
    ここで負の表現を補数表現で置き換えると、
    \((00011001)_{2}\) \(+ (11110010)_{2}\) \(= (100001011)_{2}\)
    よって、(8) 桁の範囲で見ると \((00001011)_{2}\) \(= (11)_{10} \) となる。

小数表現

• 固定小数点数表現
  制限された桁数（ビット）内で小数点の位置を固定し数値を表現する。

• 浮動小数点数表現
  数値に応じて、制限された桁数（ビット）内で仮数部と指数部に分類して数値を表現する。
  → 固定小数点表現に比べ、より広義の数値表現ができる。

• 小数表現の正規化
  仮数部と指数部に分けて表現を標準化すること。
  ※ 仮数部と指数部を分ける基準（仮数部整数の大きさ）は、与えられた条件次第であることに注意。

  • 例 \(1\) : \((0.00052)_{10}\) を正規化する。

    \((0.00052)_{10}\) \(= (5.2)_{10} \times 10^{-4}\)
    → \(5.2\) が仮数部、\(10^{-4}\) が指数部
    \((0.00052)_{10}\) \(= (0.52)_{10} \times 10^{-3}\)
    → \(5.2\) が仮数部、\(10^{-3}\) が指数部など。

  • 例 \(2\) : \((0.011)_{2}\) を正規化する。

    \((0.011)_{2}\) \(= (1.1)_{2} \times 2^{-2}\)
    → \(1.1\) が仮数部、\(2^{-2}\) が指数部
    \((0.011)_{2}\) \(= (0.11)_{2} \times 2^{-1}\)
    → \(0.11\) が仮数部、\(2^{-1}\) が指数部など。
    

基数変換の誤差

• 小数の基数変換による誤差
  \(10\) 進数から \(2\) 進数へ基数変換した場合などに起きる有限小数から循環小数へ変化したことによる誤差。
  ※ 様々なプログラム言語で多く見かけるfloat型やdouble型は、\(2\) 進数で処理するため、基数変換の誤差を考慮してコーディングする必要がある。

  • 例 : \((0.4)_{10}\) の基数を \(2\) に変換する。

    \((0.4)_{10}\) \(= (0.011001100\)\(11001100110…)_{2}\)
    \(= (0.\dot011\dot0)_{2} \)
    → 循環小数になり、有限小数 \((0.4)_{10}\) と誤差が発生する。

数値演算の誤差

• 丸め誤差
  指定桁内での演算を行うために、四捨五入や切捨てなどで、下位の桁を削除することによって生じる誤差。

• 桁落ち
  浮動小数点数の演算過程によって生じる有効桁数の減少と正規化することによって生じる誤差。

  • 例 : 有効桁数が小数点以下7桁となる条件下で \(\sqrt{999} - \sqrt{997}\) を計算する。
    （浮動小数点数だが説明のため、\(10\) 進数であることに注意。）
    

    \(\sqrt{999}\) \(\fallingdotseq (31.606\)\(96125)_{10}\) \(\fallingdotseq (0.31606\)\(96)_{10} \times 10^{2} \)（小数点以下 \(8\) 桁で四捨五入）
    \(\sqrt{997}\) \(\fallingdotseq (31.575\)\(30680)_{10}\) \(\fallingdotseq (0.31575\)\(31)_{10} \times 10^{2} \)（小数点以下 \(8\) 桁で四捨五入）
    → この時点で丸め誤差が発生。

    上記より

    \(\sqrt{999} - \sqrt{997}\)
    \( \fallingdotseq (0.31606\)\(96)_{10} \times 10^{2}\) \(- (0.31575\)\(31)_{10} \times 10^{2}\)
    \( = (0.00031\)\(65)_{10} \times 10^{2}\)
    → この時点で互いの値がほぼ等しいため、有効桁数が \(4\) 桁に減り、桁落ちが発生。

    \( = (0.31650\)\(00)_{10} \times 10^{-1}\)
    → さらに、有効桁数が小数点以下 \(7\) 桁で正規化されるため、末尾が \(000\) 埋まり、あたかも小数点以下 \(4\) 桁の有限小数だったかのような表現になるが、上記の丸め誤差と桁落ちにより、誤差が発生している。

• 情報落ち
  指定された有効桁数に収まらない極端に大きい数値と小さい数値の加算、減算を行ったときに生じる小さい数値の無効化による誤差。

  • 例 : 有効桁数の \(6\) 桁 で \((256.789)_{10}\) \(+ (0.00011)_{10}\) の演算を実施。

    \((256.789)_{10}\) \(+ (0.00011)_{10}\) \(= (256.789)_{10}\)
    → 有効桁数が \(6\) 桁なので小さい数値 \((0.00011)_{10}\) の加算値が \((0.000)_{10}\) となり、反映されない。

  • 打切り誤差 無限級数で表現される数値を有限の回数で打切ることによって発生する誤差。

  • オーバーフロー 演算結果後の値があらかじめ準備された領域（有限の範囲）を超えて表現できない状態になること。

  • アンダーフロー 浮動小数点数の演算結果後、指数部が小さいくなり過ぎて表現できない状態になること。

集合

以下、集合演算の種類とそれぞれの記号。

• 和集合
  OR（和）条件の集合。
  表現記号：\(OR\)、\(+\)、\(\cup\)、\(∨\)

• 積集合
  AND（積）条件の集合。
  表現記号：\(AND\)、\(・\)、\(\cap\)、\(∧\)

• 補集合
  NOT（否定）条件の集合。
  表現記号：\(NOT\)、\(￣\)

• 差集合
  差分条件の集合。
  表現記号： \(-\)

• 対象差集合
  差分条件の集合。
  表現記号：\(XOR\)、\(⊕\)、\(△\)

参考文献

• 瀬戸 美月 (2020) 『徹底攻略 応用情報技術者教科書』株式会社インプレス