IT関連の勉強に興味を持ち始めたので、広く浅く基礎知識を得られそうな基本情報技術者試験を受けようと思いました。
不定期ではありますが、関連する記事を書こうと思っています。
#はじめに
この記事は、私が基本情報技術者試験に向けての勉強の理解を深めるために書いています。
図の挿入などはしないので、わかりにくい場所が多々あると思いますがご了承ください(本や過去問の解説見た方が良いと思います)。
#①離散数学1
##10進数から2進数への変換
10進数であらわされた数を商が0になるまで2で割り続ける。
最後の計算の余りを頭として順に並べる。
##10進小数から2進小数への変換
10進少数の小数点以下の数を2倍する。
積の1の位の数が求める2進小数の少数第一位。
求めた積の小数点以下の数を2倍する。
積の1の位の数が求める2進小数の小数点第二位。
以下同様
##整数の表現方法
符号付きの場合、最上位ビット(MSB)はプラスのとき0、マイナスのとき1。
完全補数とは、ある数と足したときに桁が上がる最小の数
<2進数の完全補数の求め方>
補数を求める数より1桁多く、MSBが1、それ以外0の数から引く。
(例 1000000 - 110100 = 001100)
不完全補数とは、ある数の桁数における最大の数
不完全補数 = 完全補数 - 1
##小数点数の表現方法
固定少数点数表示は、整数部と小数部に分け、その間に小数点があるとみなして数を扱う。
表現できる数の範囲は狭いが、高速な演算処理が可能。
(例) 0.1011(2) = (1 x 1/2) + (1 x 0/4) + (1 x 1/8) + (1 x 1/16) = 0.6875(10)
浮動小数点表示は、指数表現で表される表現方法。
固定少数点数表示よりも表現できる範囲は広いが、演算処理が比較的低速。
符号を1ビット、指数を3ビット、仮数を4ビットで表すと以下のようになる
(例) 2.5(10) = 10.1(2) = +0.101 x (2^2) = 00101010
この例では符号+(0)、指数2(010)、仮数101(1010)で表される。
限られたビット列で数値を高い精度で表現するために、仮数の最初の桁を0以外の数(2進数なら1)にすることを正規化という。
##演算
###算術演算
減算では引く数を2の補数を利用し加算に置き換える。
###シフト演算
論理シフト演算
ビット列を左右にシフトする(ずらす)演算で、MSBやLSBからあふれた値は捨て、空いたビットには0を挿入する。符号ビットの値は保持されない。
145(10)を左へ1ビットシフトすると100100010(2)となり290(10)となるが、9ビット目は無視されるため00100010(2)つまり34(10)。
逆に右へ1ビットシフトすると01001000(2)となり72(1)となる。
算術シフト演算
負数を考慮したシフト演算で、符号ビット以外のビットをシフトする。
どちらの演算も左1ビットシフトで2倍、右1ビットシフトで1/2倍。ただし小数点以下切り捨て。
##誤差
###情報落ちによる誤差
浮動小数点演算において、絶対値の大きな数と小さな数の加減算で、絶対値の小さな数の有効桁の一部(or全部)が反映されないことで生じる誤差
###桁落ちによる誤差
値がほぼ等しい浮動小数点数同士の減算において、有効桁数が大幅に減ってしまうことで生じる誤差
###打切り誤差
演算結果が無限小数となる場合に、一定の桁数で打ち切ったことが原因で発生する誤差
###丸め誤差
数表現の桁数の限度により、最下位桁より小さい部分について切り捨て切り上げ四捨五入によって生じる誤差
###オーバーフロー and アンダーフロー
用語参照
###絶対誤差と相対誤差
真の値と演算結果の差を誤差という。
絶対誤差は誤差の絶対値。
相対誤差 = 絶対誤差 / 真の値
##用語
・MSB(Most Significant Bit)...最上位ビット。左端ビットともいわれる
・LSB(Least Significant Bit)...最下位ビット。右端ビットともいわれる
・桁あふれ...表現できる数値範囲を超えてしまい、正しい数値にならないこと。このうち表現できる最大値を超えることをオーバーフロー、最小値を超えることをアンダーフローという
##その他気になったこと
・IEEE 754(IEEE Standard for Floating-Point Arithmetic)は浮動小数点数の計算で最も広く採用されている標準規格であり、多くのプロセッサなどのソフトウェア・ハードウェアで実装されている。
単精度、倍精度、拡張単精度、拡張倍精度の4つの形式を定義している。
単精度は32ビットで表現(指数部8、仮数部23ビット)
#②離散数学2
##集合
OR(論理和)...いずれか一方が1であれば1
AND(論理積)...両方が1のとき1
NOT(否定)...1のとき0、0のとき1
NOR(否定論理和)...論理和の結果の否定
NAND(否定論理積)...論理積の結果の否定
XOR/EOR(排他的論理和)...2つの両方が1、または0のとき0
直積集合...複数の集合から1つずつ要素を取り出し、組を作って得られる集合
べき集合...集合の部分集合の集合
##ビット演算
マスク演算...データをビット単位で保持・消去する演算。データを保持したいビットには1、消去したいビットには0を対応させたビット列(ビットマスクやマスクという)との論理積を実施する
ビットの値を反転するには、各ビットごとに1との排他的論理和(XOR)を実施。
ビットの値を0にするには、そのビットと同じ値で排他的論理和(XOR)を実施。
半加算回路...2つの値を加算し、その桁の加算結果と上位桁への桁上がりを得る回路
全加算回路...最下位桁以外の加算を行う回路。2つの半加算回路と論理和(OR)からなる
##情報・通信に関する理論
###情報理論
マルコフ情報源...ある時点で発生した事象の生起確率がそれ以前に発生した事象の生起確率に依存する情報源
遷移確率行列を二乗することにより二段階で移る確率を求めることができる。
過去1個の記号系列のみに依存してある時点の記号の出現する確率が決まるプロセスを単純マルコフ過程という。
###符号理論
通信路符号化...信頼性の向上のため、元の情報に冗長ビットを加える
①CRC方式(巡回冗長検査)...連続する誤り(バースト誤り)を検出するのに適した誤り検査方式。ビット列を多項式とみなし、ある生成多項式で割った余りをそのビット列に付加する。受信したビット列が同じ生成多項式で割り切れるかどうかで誤りを判断。ビットの誤り訂正はできない
②パリティチェック(奇偶検査)...送信するビット列にパリティビットを付加し、データ列全体の1の数が偶数か奇数化で判断
③ハミング符号方式...情報ビットに冗長ビットを付加し、誤り検出とその自己訂正を受け取り側でできる方式。
情報源符号化...情報源から発生した情報をその確率的性質を利用して、より効率的に圧縮
①ハフマン符号化...出現が多い符号には短いビット列、出現が少ない記号には長いビット列を割り当てる
②ランレングス符号化...同じ文字が連続して出現する部分を、「反復回数と文字」の組に置き換える
有限オートマン...状態と入力信号の2つが決まれば次の状態が一意的に決まる数学的振る舞いモデル。状態遷移表や状態遷移図を用いて表される
正規表現...記号列すべての集合の中で、どのような規則を持ったものを取り扱うのか、特別なメタ文字(演算子)を用いて表現したもの
【代表的なメタ文字】
[m-n] : m~nまでの連続した文字の中の1文字
＊ : 直前の正規表現の0回以上の繰り返し
+ : 直前の正規表現の1回以上の繰り返し
? : 直前の正規表現が0個か1個ある
r1 | r2 : 正規表現r1またはr2である
形式言語...特定の目的のために作られた言語。正規言語や文脈自由言語など
BNF...文脈自由言語の文法を定義する表記法。
【BNFでの構文の記述に用いる記号】
::= : 定義する
| : または
[ ] : []で囲まれた構文要素は省略可能
逆ポーランド記法(後置記法)...スタックを用いて左から右へ演算を進める。演算子は直前の二つの値にかかると覚える！
(例)ABCD÷+-
①AB(C÷D)+-
②A(B+(C÷D))-
③A-(B+(C÷D))