基本情報技術者(午前)のまとめノート 01 基礎理論

基本情報技術者(午前)についての実施概要、基礎理論

実施概要

  • 午前、午後試験ともに100点満点
  • 両方60点以上得点できれば合格
  • 午前試験はテクノロジ(technology)系分野を中心とした出題
  • 午前試験は過去問題が多い、80問のうち60%+が過去問題
  • 分野別
    • テクノロジ系問題:50問
    • マネジメント系:10問
    • ストラテジー(Strategy)系:20問、システム戦略、企画、経営戦略、技術戦略、ビジネスインダストリ(Industry)、法務

基礎理論

数値表現

基数変換

  • 基数:10進数の場合0~9、2進数の場合0~1
  • 進数記号:$$(abc.de)_n$$
  • 基数変換:小数を含めて、2進数と8進数と16進数の変換、10進数から2進数、8進数、16進数への変換

補数表現

  • 定義:補数とはある数に対して、足し合わせることで同じ桁数の最大値になる数、あるいは足し合わせることで、同じ桁数の最大値に1を加えた数になるような数のことを指す。(X的补码Y就是说X+Y等于相同位数数的最大值)
  • 1の補数:Xの各ビットを反転 $$(1111)_2-(1101)_2=(0010)2$$
  • 2の補数:1の補数+1
  • 負数の表現:2の補数で負数を表現
  • 負数の計算:X-Y=X+Y補
  • 固定小数点数:最上位0の場合正数を表現、最上位1の場合負数を表現
  • 固定小数点数の表示範囲:$$-2^{n-1}$$から$$+2^{n-1}-1$$まで nは桁数
  • 浮動小数点数:符号部、指数部、仮数(尾数)部で表現、即ち$$pm{(mantissa)*(radix)^{index}}$$ 基数は2または16
    • 符号部(s):1ビット;0なら正、1なら負
    • 指数部(e):7ビット;
    • 仮数部(m):24ビット;正規化を行う;小数第1位からを24ビットで表現。
  • 浮動小数点数の参考資料:01
  • 浮動小数点数の例:
    • 10進数123.125の二進数表現は1111011.001
    • 正規化:$$1.111011001*2^6$$
    • 即ち:$$1.111011001*2^{133-127}$$
    • それで仮数:$$S=111011001$$
    • 指数: $$E=(133)_{10}=1000101$$
    • 浮動小数点数表現は0 1000101 111011001

算術演算と精度

  • 参考資料:情報落ち、桁落ち、丸め誤差、打切り誤差の違い
  • 情報落ち
    • 定義:絶対値の大きい数値に絶対値の小さい数値を加減算することによって、絶対値の小さい数値が無視されてしまうこと。
    • 例:$$2.000000010^8+1.0000000=2.000000010^8$$ (有効桁数が8桁の場合)
    • 対策:小さい数から足し算を行い、可能な限り情報落ちを回避
  • 桁落ち
    • 定義:値がほぼ等しい浮動小数点数同士の減算をしたとき、有効桁数が少なくなる
    • 例:$$0.55610^7-0.55210^7=0.400*10^5$$
  • 丸め誤差
    • 定義:切捨て,切上げ,四捨五入などで有効桁数未満の桁を削除することによって発生する誤差
  • 打切り誤差(截断误差)
    • 定義:計算結果が無限小数となるような計算(無限級数など)を途中で打ち切ったことによって発生する誤差のこと

論理演算とシフト演算(转移操作)

論理演算

  • 論理演算の種類:論理積(AND)、論理和(OR)、否定(NOT)、排他的論理和(XOR)、否定論理積(NAND)、否定論理和(NOR)
  • ド・モルガン法則(德摩根定律)
  • 基本回路:AND、OR、NOT回路
A B A AND B A OR B A XOR B A NAND B A NOR B
0 0 0 0 0 1 1
0 1 0 1 1 1 0
1 0 0 1 1 1 0
1 1 1 1 0 0 0
  • 否定論理積は論理積の否定;否定論理和は論理和の否定;
  • ビット演算:二つの2進数の対応する各桁それぞれに論理演算を行う

    シフト演算

  • 算術シフト
    • 定義:先頭ビットを符号とみなして、符号ビットを除いてシフトを行う
    • 左シフト:空いた位置に0を入れ
    • 左シフトの例:00000011 -左2ビットシフト-> 00001100
    • 右シフト:空いた位置に符号ビットを入れ
    • 右シフトの例:10100000 -右2ビットシフト-> 11101000
  • 論理シフト:
    • 定義:単純にビットを左右にシフトし、空いた位置に0を入れる

情報量・符号化

情報量

情報量は、対象となる情報ごとのデータの取り得るのバリエーション(variation)によって変わる。

  • ビットとバイト:1バイト=8ビット
  • 生起確率(产状概率):発生すると考えられるデータの予測確率。サイコロの結果は最低3ビットのデータ量が必要。
  • 期待値:ある試行を行ったときに得られる数値の平均値。サイコロの期待値は3.5。

    符号化(编码)

  • ランレングス符号(游程编码):同じビットパターンが連続するデータをできるだけ短いビット列として表現するための符号化方式。
  • ハフマン符号(霍夫曼编码):出現頻度が高いものほど短いビット列で表現する。例えば:出現頻度が高い単語を1に、次に10、11…順次に符号化。

BNFと逆ポーランド表記法

BNF(Backus Naur Form, 巴科斯-诺尔范式)

  • ::= 左辺を右辺のように定義する
  • | 又は(OR)
  • 例:<数字>::=0|1|2|3|4|5|6|7|8|9
  • 例:<英字>::=A|B|C

    ボーランド表記法(波兰表达式)

表記法 演算子の配置 特徴
ポーランド表記法 前置記法 演算子を演算対象の前に置く +ab
通常の表記法 中置記法 演算子を演算対象の間に置く a+b
逆ポーランド表記法 後置記法 演算子を演算対象の後ろに置く ab+

データ構造

リスト(List)

  • 定義:いくつかの要素をデータの場所を示すポインタ(指针)でつないで構成し、物理的な位置とは関係はく、ポインタによって論理的に決められる。
  • 種類:単方向リスト(線形リスト)、双方向リスト(双リスト)、環状リスト

    スタック(stack)

  • 特徴:LIFO(Last-In First-Out;後入れ先出し)
  • 操作:プッシュ(PUSH;要素を格納)、ポップ(POP;要素の参照・取り出し)

    キュー(queue)

  • 特徴:FIFO(First-In First-Out;先入れ先出し)
  • 操作:エンキュー(enqueue;要素を挿入)、デキュー(dequeue;要素の参照・削除)

    木(tree)

  • 二分木(binary tree)
    • 完全二分木:どの節も子の数が2以下であるような木。
    • 探索法
      • 幅優先探索:同じ深さの節を左から右に探索
      • 深さ優先順:
        • 先行順(前順):親→左部分木→右部分木の順
        • 中間順(間順):左部分木→親→右部分木の順
        • 後行順(後順):左部分木→右部分木→親の順
  • 二分探索木(binary search tree)
    • 定義:左の子の要素の値 < ある節の要素の値 < 右の子の要素の値
    • 操作:追加・削除
  • ヒープ(heap)
    • 定義:どの親子を見ても、必ずその節の値が「親<子」(又は「親>子」)という関係を保っている完全二分木である。
    • 特徴:根の節の値は最小値(又は最大値)となる。

アルゴリズム

### 整列(Sort)

  • 交換法(バブルソート)
    • 計算法:互いに隣り合うデータを比較し、大小関係が逆なら変換すると、左側に最小データが来る。次に、左側データを除くデータ列に対して同じ操作を繰り返し、データが残り一つになったら処理を終了する。
    • 計算量:$$O(n^2)$$
  • 選択法
    • 計算法:最小データを左端データと交換する。左端を除くデータを繰り返し操作。
    • 計算量:$$O(n^2)$$
  • 挿入法
    • 計算法:2番目のデータを取り出し、左端に適切な位置に挿入する。
  • クイックソート(交換法の改良)
    • 計算法:中央データを取り出し、以下のデータを左、以上のデータを右、分けて繰り返す。

– end p.82