応用情報勉強まとめ(離散数学)

前置き

過去に勉強していた応用情報技術者試験の内容がOneNoteに残っていて、腐らすのももったいないと思ったので、ここで公開します。

参考書からまとめた内容だと思うので、ジャンル分けはその参考書に沿ってます。
なんの参考書だったかは思い出せません・・・職場の先輩に借りたものだったので(笑)

離散数学

基数

桁上がりの基準となる数。10進数なら10だし、2進数なら2となる。

下付きの数字は基数を表す。　(110.01)2 = (6.25)10

2進数と10進数の変換

10進数を桁に分けた計算式で表すと [423 = 4 * 10^2 + 2 * 10^1 + 3 * 10^0] となる

基数が乗数がかけられる値で、指数は1桁目が0の連番(小数点以下は^-1,^-2となる)である。

↓

2進数→10進数変換はこの式を2進数で表してから計算すればよい。

[(1101)2 → 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 → (13)10] となる。

10進数→2進数変換は違う方法となる。

10進数をどんどん2で割って余りを右から並べていくと2進数となる。

例) (13)10 ↓

13 / 2 = 6 % 1

06 / 2 = 3 % 0

03 / 2 = 1 % 1

01 / 2 = 0 % 1

→ (1101)2

※ 右から並べる　の覚え方は2進数は最後1を2で割るから、最後の余りは1になるのは確定　という覚え方か。

2進数の負の数を表現

負の数には補数という考え方を用いる。補数とは、正の2進数に対し1桁繰り上げる為に必要な最小限の数となる。

(00001101)2 【(13)10】

(11110011)2 【(-13)10】← 11110011が補数となる(2進数的には243だけど、これは補数なので違います)

（100000000)2

2進数の補数(2の補数)の簡単な計算は、ビットを反転して1を足す　と覚えればよい。

補数を使うことで、足し算のみで引き算の表現が表せれる。

引かれる数と引く数の補数を足して、計算結果のあふれた数を無視すれば引き算の完成である。

例) 25-13=12

00011001　引かれる数　(25)10

11110011　２の補数　  (-13)10

↓（足す）

100001100　計算結果　　(12)10

あふれた9桁目は無視で → 1100

2進数の少数表現

〇 固定小数点　→　あらかじめ小数点の位置を決めて、その位置に合わせてデータを表現

〇 浮動小数点　→　指数部と仮数部で少数点を表現する（0.000603　→　6.03*10^-4）

浮動小数点を決められた形式で正しい形にすることを正規化と言う。

基数変換と誤差

0.4みたいなのを有限小数という。

0.4を2進数にすると、割り切れない循環したかたちとなる。これを無限小数というが、特に同じ表現が繰り返されるのを循環小数という。

数値演算と誤差

コンピュータで起こりうる表現しきれない事象

・桁落ち

値がほぼ等しい二つの数値の差を求めたとき有効桁数が減ることによって発生する誤差

・情報落ち

絶対値が非常に大きい数値と小さな数値の足し引きを行ったとき小さい数値が計算結果に反映されない誤差

・その他

[丸め誤差][打ち切り誤差][オーバフロー][アンダーフロー]がある。重要性は低い。

集合

ある条件で集まったグループ

・和集合・・・2つの集合を足したもの

・積融合・・・2つの集合、両方に当てはまるもの

・補集合・・・ある集合の否定型

・差集合・・・ある集合から別の集合に当てはまるものを引いたもの

・対称差集合・2つの集合のうち、どちらかのみに当てはまるもの

論理演算

集合を使ったand or の計算。

AND演算の中には、マスク演算というものがあり、

ビットが1の部分のみを取り出して他の部分を排除(マスク)するときに使用する。

IPアドレスに対するサブネットマスクはこのマスク演算を応用した例。

最後に

懐かしいですね。

IPアドレス周りやメモリ周りは2進数が頻出する世界なので、覚えておきたいところです。

また、集合はプログラミングやSQLで必須の知識なので、おさえておきましょう。