情報の基礎理論

コンピュータを学習するうえで必要となる基礎事項・知識について解説します。

数値変換とデータ表現

r進法

10進法に代表されるr進法。
2進法とか3進法などなど。この2とか3とかを基数といいます。
たとえば、16進法であらわされたcht=tx&chl=2A.4({_1_6})

cht=tx&chl=2\times16^{1}+10\times16^0+4\times16^{-1}=32+10+0.25=42.25

となります。

正の整数の表現

2進数nけたで表現できる数

2進数は各桁を0か1で表現します。2進数で表現できる正の数は
cht=tx&chl=0\sim2^n-1
です。

負数の表現

2の補数

一般的に負の数を表現する場合、補数というものが用いられます。
補数を利用する理由は、コンピュータではそもそもマイナスは使えません。 そこで、最上位ビットの上にけたに1があると仮定し計算した結果を-1とします。

100000000
-       1 → N
----------
011111111 → M

N(1) + M(−1) = 0   

このような考え方で2の負数を補数であらわします。
補数であらわせる負数の範囲は nビットの場合、 cht=tx&chl=-1\sim-2^{n-1} です。

負数を表現する方法

負数を表現する方法は3つあります。

  1. 2の補数
  2. 符号と絶対値 → 0と-0がある。
  3. 1の補数 → 0と-0がある。 正負の別を表現するために先頭の1ビットを使用します。
    この中で2の補数がもっとも一般的です。

小数点数の表現

小数の表現

一般的に小数だけで構成された数値を表現する場合は、最上位ビットの右側を小数点位置とします。これを固定小数点表現といいます。

01010000 = 0.625
 |_小数点位置

11010000 = 0.625 - 1 = -0.375
 |_小数点位置

小数点数の表現

上記の固定小数点表現では整数部分を表現できません。そのため小数点を右に移動させ整数部分を拡張します。

01011010 = 5.625
    |_小数点位置

11011010 = -2.375
    |_小数点位置

浮動小数点数表現

実数の表現

7.25を有効桁数を表す仮数部と桁数を表す指数部に分けられる。
cht=tx&chl=7.25=10^1*0.725

10:底
1:指数部
0.725:仮数部 → 1未満で表現する。

この表現方法を浮動小数点表現といいます。

正規化

浮動小数点表現で仮数部の最上位桁が0以外になるように桁を合わせることを正規化といいます。

cht=tx&chl=7.25=111.01(_2)

= cht=tx&chl=2^0\times111.01(_2)
= cht=tx&chl=2^3\times0.11101(_2)

0 00000011 1110 1000 0000 0000 0000 000(浮動小数点4バイト)
| |        |_仮数部。ここが小数第1位
| |_指数部
|_正で0   


有効けた数

正規化した2進浮動小数点の有効桁数は仮数部の桁数で決まります。

アンダフローとオーバフロー

演算結果の絶対値が表現できる範囲を超えてしまった場合 → オーバーフロー
下回ってしまった場合 → アンダーフロー

誤差

誤差の種類説明サンプル
丸め誤差四捨五入で切り捨てられたことにより発生する誤差3.653を小数第二位で四捨五入
情報落ち絶対値の大きな数と小さな数の足し算、引き算で小さい数が計算結果に反映されないために発生する誤差
けた落ち有効桁数減少に伴う誤差
打ち切り誤差浮動小数点の計算処理の打ち切りにより発生する誤差

集合と論理

集合論理

部分集合とべき集合

集合とは、ある条件を満たし、ほかものとは明確に区別できるものの集まりをいいます。

集合名説明
要素集合に属するもの
空集合要素数が0の集合
有限集合要素数が有限である集合
無限集合要素数が無限である集合
部分集合1つの集合の中で選択できる集合

/Top/応用情報tips/


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2010-07-10 (土) 23:11:33 (4530d)