論理演算

この記事での学習内容 ITパスポート  基本情報  応用情報

論理式の表現,論理演算,ド・モルガンの法則などの基本法則,真理値表,カルノー図の 手法を理解する。

用語例: 否定,論理和,論理積,排他的論理和,否定論理和,否定論理積,論理関数,分 配則

論理演算

命題の真偽によって演算結果を表すことを論理演算といいます。
基本となるものに「否定(NOT)」「論理積(AND)」「論理和(OR)」があります。

演算意 味
否定1つの命題が「~ではない」と逆になる(NOT)
論理積2つの命題が「~かつ~」の関係(AND)
論理和2つの命題が「~または~」の関係(OR)

論理演算はコンピュータと縁の深いモデル化の技法です。
AND、OR、NOTで複数の命題を組み合わせれば、どんな複雑な論理回路も作ることが出来ます。
また、データ間の関係も論理式に置き換えると整理できるので、プログラミングやデータベースの構築に欠かせない理論です。

否定(NOT) 、論理積(AND)、論理和(OR)

集合の論理演算は、リレーもしくは半導体回路を使った電子回路で実現することが出来ます。
真理値表のAとBを入力に見立てて、その真、偽の状態によって論理和の真理値表と同じ結果を出力する回路をOR回路、論理積と同じ結果を出力するものをAND回路、入力の否定を出力するものをNOT回路といいます。

 MIL記号ベン図真理値表
Aの否定
AとBの論理積
AとBの論理和

それぞれの回路は回路図上で以下の図のような記号(MIL記号)を使って表します。
NAND回路とNOR回路は、それぞれAND回路、OR回路にNOT回路を繋いだものとなります。

これらの回路を組み合わせることで、非常に複雑な論理式や機能を電子回路で実現することが出来ます。実際、コンピュータ内部で足し算やシフト演算を行うALU、命令デコーダ、タイミング制御回路、レジスタやメモリ(DRAMを除く)なども全て論理回路で構成されています。

また、基本となる論理演算を組み合わせたものもよく利用されます。代表的なものは、「否定論理和(NOR)」「否定論理積(NAND)」「排他的論理和(XOR)」です。

論理演算の一般的な法則

2つの命題を使った論理演算には、幾つかの法則が成り立ちます。

交換の法則:

結合の法則:

分配の法則:

復元の法則:

ド・モルガンの法則:

ド・モルガンの法則を始めとする、論理演算の各種の法則は、複雑な論理式を簡略化したり、別の式に変換したりする時に利用できます。

これは、プログラムの開発において、判定条件が複雑になった時、評価する式を簡略化したり、デジタル回路を設計する時に、同じロジックの回路を少ない部品点数で設計し直したり、と言った場面で役立ちます。

カルノー図法

カルノー図法は真理値表でパターン数が増えて見づらいときなど、論理式を簡略化するための図法。下記のような変数が3つ以上の式で、論理積の項を論理和した形(積和形)の場合に使いやすいとされている。

上記の式をカルノー図で表した例

 

集合と命題

この記事での学習内容 ITパスポート  基本情報  応用情報

集合,命題,ベン図の手法と考え方を理解する。

用語例: 和集合,積集合,補集合,部分集合,真,偽,命題論理

集合

集合とは、同じ属性を持つ要素の集まりのことです。

集合はよく「ベン図」で表されます。要素全体の集まりを四角で表し、そのうち集合に含まれる要素を色付きの円で示します。この時、集合に含まれない円の外側のことを補集合といいます。

集合演算

集合同士を演算することを集合演算といい、「和集合」「差集合」「積集合」が代表的です。

演算意 味
和集合集合と集合を足す
差集合ある集合から、別の集合と共通する部分を引く
積集合複数の集合から、互いに共通する部分を取り出す
補集合全体から、その集合を取り除く

集合の包含関係

2つの集合の関係は、場合によっては下図のように、集合Aが集合Bに含まれる場合もある。この様な包含関係を表す演算子として「⊆」や「⊇」が用いられる。

命題

命題とは、要素を「正しい(真)」か「正しくない(偽)」かで振り分けるための条件付けを指します。ある命題について、真か偽かによって要素を振り分けると集合を作ることが出来ます。

また、「真」と「偽」を真理値といい、「真」を1、「偽」を0として表すこともあります。対象となる要素の真理値を表の形にまとめたものを、真理値表といいます。

算術演算と精度

この記事での学習内容 基本情報 応用情報

加減乗除,表現可能な数値の範囲,シフト演算,演算精度(誤差とその対策)など,コ ンピュータでの算術演算を理解する。

用語例: 論理シフト,算術シフト,桁落ち,情報落ち,丸め,打切り,オーバフロー(あ ふれ),アンダフロー,単精度,倍精度

シフト演算

引き算は2の補数を使うと足し算で同じ計算が出来ましたが、掛け算や割り算の場合はどうでしょうか。

例えば、10進数の123を10倍すると1230に、100倍すると12300になりますが、この計算は123の桁を10倍のときは1つ、100倍のときは2つ左ずらすことで簡単に求めることが出来ます。

逆に、10分の1にする場合は右に1つ、100分の1にする場合は右に2つずらすことで求めることが出来ます。

つまり、数値の桁を1つずつずらすことは、その数値の『基数倍』や『基数分の1』を計算するのと同じ効果があります。

このように桁を左や右にずらすことを『シフト』といいます。左にずらすことを「左シフト」、右にずらすことを「右シフト」といいます。

これらのシフト演算は掛け算や割り算の代わりに利用することもありますが、通常は2進数でビットバターンの特定の操作をしたり、ビットの状態を判定する際に利用します。

2進数のシフト演算

2進数の場合は、1桁左シフトすると数値は2倍、1桁右シフトすると、数値は2分の1となります。

桁あふれ(オーバーフロー)

コンピュータで数値を表現する場合、8ビットや16ビットなどあらかじめ表現範囲は決まっています。
その為、シフトを行うと表現の幅を超え、ビットが飛び出してしまい、正確に数値が表現できない場合があります。これを「桁あふれ」または「オーバーフロー」といいます。

シフトの種類

シフト演算には、符号ビットを考慮しない「論理シフト」と、符号ビットを考慮してそのままにする「算術シフト」があります。

論理シフト

論理シフトでは、符号ビットを考慮しません。最上位のビットも含めてシフトを行います。

シフトすることによって飛び出したビットは捨てられ、空いたビットには0が入ります。

シフトによって飛び出したビットに1が入っていた場合、桁あふれが発生し、正しい計算結果を得ることが出来ません。
左にシフトして桁あふれが発生した場合を「オーバーフロー」、右にシフトして桁あふれが発生した場合を「アンダーフロー」といいます。

左論理シフト

左論理シフトでは、左にNビットシフトすると、左側の上位Nビットが飛び出して捨てられます。その分、右側の下位Nビットが空き、そこには0が入ります。

これによって、元の数の2N倍の数となります。

但し、シフトによって飛び出したビットに1が入っていた場合、オーバーフローが発生し、正しい計算結果を得ることが出来ません。

右論理シフト

右論理シフトでは、右にNビットシフトすると、右側の下位Nビットが飛び出して捨てられます。その分、左側の上位Nビットが空き、そこには0が入ります。

これによって、元の数の1/2N倍の数となります。

但し、シフトによって飛び出したビットに1が入っていた場合、アンダーフローが発生し、正しい計算結果を得ることが出来ません。

算術シフト

算術シフトでは符号ビットを考慮して、先頭の最上位ビットはそのまま移動しません。最上位以外のビットだけをシフトします。

負の数を2の補数で表現する、符号付きの2進数の場合は算術シフトが使われます。

左算術シフト

左算術シフトでは、先頭の符号ビットは移動せず、それ以外のビットを左にシフトします。先頭の符号ビットが移動しない以外は論理シフトと同様です。

算術シフトの場合は、シフトによって飛び出したビットに「符号ビットと異なる値」が入っていた場合、オーバーフローが発生し、正しい計算結果を得ることが出来ません。

右算術シフト

右算術シフトでは、先頭のの符号ビットは移動せず、それ以外のビットを右にシフトします。
シフトによって左側に空いたビットには、符号ビットと同じ値が入ります。

但し、シフトによって飛び出したビットに1が入っていた場合、アンダーフローが発生し、正しい計算結果を得ることが出来ません。

数値データの形式と誤差

コンピュータでは扱う情報に応じて、数値の表現方法が使用される。

使用する数値データの形式により、精度、扱える範囲、データサイズ、誤差の生じやすさが異なってくる。

形式としては、整数型、浮動小数点型等がある。

誤差の種類

誤差の種類としては以下の様なものがある。

  • オーバーフロー、アンダーフロー:扱えるデータの範囲を超えた時の誤差。
  • 丸め誤差:無限小数の桁を区切った際に発生。
  • 情報落ち:絶対値の大きい数と小さい数を加減算した時、絶対値の小さい値が無視される。
  • 桁落ち:値がほぼ等しく、丸め誤差を持った数値同士の減算を行なった場合に有効数字が減少

 

数値の表現(小数)

この記事での学習内容 ITパスポート 基本情報 応用情報

小数の表現を理解する。

用語例: 固定小数点数,単精度浮動小数点数,倍精度浮動小数点数,仮数,指数

小数の表現方法の種類

小数の表現方法には固定小数点数と浮動小数点数があります。また、浮動小数点数には、単精度浮動小数点数と倍精度浮動小数点数などがあります。

固定小数点数

コンピュータで負の数を含む整数の数値データを扱うときは、固定小数点数という方式を使うのが一般的です。

固定小数点数では、次のようにデータを記憶します。

  1. データの格納に必要なビット長の記憶領域をあらかじめ用意する。
  2. 小数点の位置を決めて、各桁の2進数値を各ビットに当てはめる。
  3. 先頭の1ビットを正負の符号ビットとして扱う。

なお、固定小数点数のビット長はコンピュータによって異なりますが、16ビットや32ビット長などが一般的です。

浮動小数点数

浮動小数点数は、文字通り小数点の位置が浮いて移動するように見えるので、浮動小数点数と呼ばれています。

この方式では、非常に大きな数や小さい数を扱うことが出来ます。
例えば、32ビットの固定小数点数の場合、正の数なら 231-1 が最大の数となりますが、32ビットの浮動小数点数の場合、3.4 × 1038 という非常に大きな値となります。

浮動小数点数の正規化

浮動小数点数では、同じ数値を仮数部、指数部の調整次第でいろいろな表現が可能になります。しかし、コンピュータにとって表現方法が一定ではないのは都合が悪いため、仮数部の小数第1位に0以外が来るようにします。このことを正規化とよんでいます。

なお、仮数部の整数部が基数1桁に収まるようにすることを正規化とする場合もあります。後述する「バイアス表現」を使う場合に、この方法を使います。

例) 1.5 という10進数の値を浮動小数点数として表現
  15 × 10-1
  1.5 × 100 ← こちらを正規化されたデータとする場合もある
  0.15 × 101 ← 正規化されたデータ
  0.015 × 102

浮動小数点数の表現方法

浮動小数点数は、仮数部の符号、指数部、仮数部を用いて表現します。
仮数部の符号は、0か正の数の場合は0を、負の数の場合は1とします。
指数部は基数を何乗するのかという値を入れます。

 

浮動小数点数の表現形式

浮動小数点数の表現形式にはいくつかの種類があります。
ここでは、24ビットの浮動小数点数について、『バイアス表現』と使わない形式と使う形式を紹介します。

*バイアス:下駄履き、底上げ

バイアス表現を使わない形式

24ビットの内、1ビットを符号ビット、7ビットを指数部、16ビットを仮数部とします。
これを用いて、10.375(10) を表現してみます。

10.375(10) を2進数で表すと、1010.011(2) となります。この数は正の数ですので、符号ビットは「0」となります。

次に、仮数部が1未満になるように正規化を行います。
1010.011 = 0.1010011 × 24 となるので、仮数部の上位から「1010011」を入れ、残りビットは0とします。

最後に指数部は4を7桁の2進数に変換し、「0000100」を入れます。

バイアス表現を使う形式

24ビットの内、1ビットを符号ビット、8ビットを指数部、15ビットを仮数部とします。
これを用いて、-10.375(10) を表現してみます。

-10.375(10) を2進数で表すと、-1010.011(2) となります。この数は負の数ですので、符号ビットは「1」となります。

次に、仮数部が1.**になるように正規化を行います。
1010.011 = 1.010011 × 23 となるので、ここから小数点以下の部分「010011」を抜き出し、仮数部の上位から「010011」を入れ、残りビットは0とします。

最後に指数部分ですが、ここで『バイアス表現』を使います。
バイアスとは「下駄を履かせる、底上げする」という意味ですが、マイナスの数値を符号なしの2進数で表すために、所定の数(=バイアス値)を加えて表す方法です。

今回は指数部分を8ビットとし、最小値の-127を0と表すために、バイアス値を127とします。指数部の値は3ですので、これに127を加えた130を2進数に変換し「10000010」を指数部に入れます。

単精度浮動小数点数と倍精度浮動小数点数

浮動小数点数を32ビットで表現する方法を単精度浮動小数点数といいます。

ここから使用する桁数を増やし、精度を上げる場合は64ビットの倍精度浮動小数点数を利用します。

 

数値の表現(整数)

この記事での学習内容 ITパスポート 基本情報 応用情報

負の数の表現(補数表現)を理解する。

用語例: BCD (Binary Coded Decimal:2 進化 10 進),パック 10 進数

2進数における表現の問題点

整数の場合は桁数が多くなる程度ですが、小数の場合はそもそも表現できる数が少ないため、どうしても「誤差」が生じてしまいます。

例えば、10進数の 0.75 は、2進数で 0.11 と表すことが出来ますが、10進数の0.7を2進数で表そうとすると、 0.1011011… と延々と続く「無限小数」となってしまい、2進数で表すことが出来ません。

こういった数を表そうとすると、一定の桁で打ち切って表現せざるを得ません。しかし、打ち切ると10進数に戻した時にもとの値に戻すことが出来ず、「誤差」が生じてしまいます。

例えば、先述の 0.7 を2進数で表現し、小数第6位までで打ち切ったとすると、0.101101 となります。これを再度10進数に戻すと、0.64275 となり、元の 0.7 には戻せません。

打ち切る際に出来るだけ桁数を多く取れば誤差を減らすことは出来ますが、誤差を無くすことは出来ません。

10進数に近い形で数値を表現する方法

コンピュータ内部で扱われるデータは2進数が使われますが、コンピュータに入力される数値は10進数の場合が多いため、単純に2進数に変換しただけだと、誤差が発生しやすくなります。

その為、10進数の値を2進数に変換せずに表現する方法が考えられてきました。ゾーン10進数とパック10進数です。

ゾーン10進数は1桁を8ビットで表現し、パック10進数は1桁を4ビットで表現します。
いずれも、10進数書く桁の数字を4ビットの2進数で表現したBCDコードというものを使います。

BCDコード

BCD : Binary Coded Decimal の略。

BCDコードとは、10進数の各桁の数字を4ビットの2進数で表したもので、10進数を2進数に変換し、4ビット中の残りの上位ビットに0を入れたものです。

10進数BCDコード
00000
10001
20010
30011
40100
50101
60110
70111
81000
91001

なお、BCDコードで表現した2進化10進数といいます。

ゾーン10進数(アンパック10進数)

ゾーン10進数は8ビット(=1バイト)で10進数1桁を表現する方法です。8ビットを上位4ビットのゾーン部と、下位4ビットの数値部に分け、数値部は先述のBCDコードを使って表します。

なお、ゾーン部の値は、汎用コンピュータなどで使われるEBCDIC方式では「1111」、JIS方式では「0011」が用いられます。

ゾーン10進数で10進数を表現する場合、数値の桁数分のバイト数が必要となり、格納効率はよくありません。しかし、数字を表す文字コードとの相性が良く、数値と文字の変換が行いやすくなっています。

パック10進数

パック10進数は8ビット(=1バイト)で10進数2桁を表現する方法です。8ビットを4ビットずつに分けて数値部とします。
数値部はゾーン10進数と同様にBCDコードを使って表します。
さらに、最下位の4ビットを符号部とし、符号を入れます。

パック10進数はゾーン部を省略してまとめてパックしたイメージとなります。

パック10進数で10進数を表現する場合には、桁数の約半分のバイト数が必要で、ゾーン10進数と比べると格納効率にまさり、計算などに適しています。

2進数での符号付きの数の表現方法

正負の数を2進数で扱うためには、プラスかマイナスかを示す符号用に1ビット分を使います。この際、先頭のビットが0ならば正の数、1ならば負の数とするのが一般的です。

具体的な方法としては、以下の3つの方法が用いられています。

 nビット使った場合の表現範囲例)5と-5を8ビットで表した場合
絶対値に符号をつける-2n-1-1 ~ 2n-1-1
8ビットの場合:-127~127
5(10) → 00000101(2)
-5(10) → 10000101(2)
1の補数を用いる
*負数の場合、絶対値のビットを全て反転させる
-2n-1-1 ~ 2n-1-1
8ビットの場合:-127~127
5(10) → 00000101(2)
-5(10) → 111111010(2)
2の補数を用いる-2n-1 ~ 2n-1-1
8ビットの場合:-128~127
5(10) → 00000101(2)
-5(10) → 111111011(2)

この内、絶対値に符号を付ける方法と1の補数を用いる方法の場合、「+0」と「ー0」という同じ値が2つの方法で表現されてしまい、僅かにですが同じビット数で表現できる数値の範囲が少なくなってしまいます。

限られたビット数でできるだけ広い範囲の値を表現したいコンピュータにとっては余り良い方法ではないため、2の補数を用いる方法が一般的となっています。

2の補数による負数の表現

補数とは、「補う数」と言う名のとおり、それを足すとちょうど桁上りの基準値になる数のことです。

10進数の場合、基数が10nなので、7にとっての10の補数は4、8にとっての10の補数は2となります。

2進数の基数は2nなので、例えば 110(2) の2の補数は、足すと桁上りして 1000(2)になる数のことなので、計算すると 10(2)と求められます。

110(2) の2の補数 = 1000(2) - 110(2)  10(2)

なお、2の補数は「元の数のビットを全て反転し、1を足す」という方法で簡単に求められます。この方法の場合、結果的に負の数の先頭ビットが常に0になるため、先頭ビットが符号ビットの役割も果たします。

補数を使った減算

負数を扱う時に「2の補数」を用いると、限られたビット数で表現できる値の範囲が広くなるメリットの他に、「引き算を足し算の仕組みのままで計算できる」というメリットがあります。

一般的な10進数の計算でも、式を変形して以下のように引き算の式を「負数による加算」とすることが出来ますが、考え方は同じです。

例)  6 – 2 = 6 + ( -2) = 4

同様に、2進数の引き算を「負数による加算」で行なってみます。解が正数になる場合、負数になる場合両方を見てみましょう。
*今回は8ビットを使って正負の整数を表すものとします。

例1)6 – 2 = 4

例2)6 – 8 = -2

負数を2の補数で扱うことで、コンピュータにとっては加算命令だけで足し算も引き算もできるようになるため、演算機能が簡略化出来ます。

人間が2の補数で計算する際には、「最上位で桁上りしたビットは無視する」という手順が必要になりますが、コンピュータの場合、「整数を8ビットで表す」としている場合、桁上りして発生した最上位の9ビット目は無視されてしまうため、わざわざ「最上位で桁上りした場合」ということを考える必要も無いのです。

基数

この記事での学習内容 ITパスポート 基本情報 応用情報

2 進数,8 進数,10 進数,16 進数,n 進数の表現,2 進数と 10 進数などの基数の変換手法 を理解する。

記数法

私たちが一般的に数値を扱うときには0~9までの数字を使う、「10進法」を用いています。
一方で通信やコンピュータの分野では「2進法」「8進法」「16進法」などが使われます。

10進法では0~9までの数字を使い、「10」を桁上りの基準としていますが、2進数では「2」、16進数では「16」が桁上りの基準としています。

この桁上りの基準をどの値にするか、0からどの数字(文字)までを使って数を表すかを決めたものを「記数法」といいます。

一般的には、桁上りの基準の値を用いて「n進法:nを基準に桁上りする」となっています。

 桁上りの基準使う数字・文字表記方法の例
(10進数の100の場合)
2進法20と1のみ0b1100100
1100100(2)
8進法80~7の数字0144
144(8)
10進法100~9の数字100
16進法160~9までの数字と英字のA, B, C, D, E, F0x64
64(16)

基数と重みーn進数の表現

10進数の「1000」という値は「1 × 103」と表すことも出来ます。

この時の1を「仮数」、10を「基数」、103「重み」といい、10進数の各桁はこの表現による値となっています。
言い換えれば、「基数」は桁上りの基準で、「仮数」は実際に表示されている数字、「重み」はどの桁かを表す値となります。
(但し、重みの桁数は0が1の位となる点に注意)

このように、nを基数として数値を表す記数法を「n進数」といいます。

なお、n進数で小数を表すときには、「n-1」「n-2といった重みを使います。

前提として、以下の法則を覚えておくこと。
・n0 = 1 (nの「0乗」は必ず1になる。)
・n-x = 1 / nx

これらを踏まえて、「1234.567」という10進数の数値を基数と重みを使った表現で表すと下の式および図のようになります。

1234.567 = 1000 + 200 + 30 + 4 + 0.5 + 0.06 + 0.007
   = 1 × 103 + 2 × 102 + 3 × 101 + 4 × 100 + 5 × 10-1 + 6 × 10-2  + 7 × 10-3 

基数と重みー2進数の場合

2進数は2を基数とする数え方です。2を基準に桁上りするので、数の表記には0と1のみを使います。

例えば2進数の「1010」という値を重みを使った表現で表すと以下のようになります。

1010 = 1 × 23 + 0 × 22 + 1 × 21 + 0 × 20 

2進数の加算と減算

2進数同士の加算、減算は10進数の時と同様、筆算で解くことが出来ます。

例1) 11100(2) + 10110(2)

例2) 11100(2) - 10110(2)

基数変換

また、10進数と2進数など、n進数同士は互いに変換することが出来ますが、この変換のことを「基数変換」といいます。

10進数と2進数の変換

2進数を10進数に変換

2進数を10進数に変換するには、各桁の数に重み(2のべき乗)を掛けて合計します。

10進数を2進数に変換(整数部分)

10進数の整数を2進数に変換するには、10進数を商が0になるまで2で割り続け、余りを拾い出して順に並べると2進数になる。
*拾い出して並べる順は図を参照。

10進数を2進数に変換(小数部分)

10進数の小数を2進数に変換するには、10進数を2倍し、1の位を取り出す、という作業を小数部分がなくなるまで繰り返す。
*拾い出して並べる順は図を参照。

8進数と16進数

コンピュータ内部では情報は2進数で扱われているので、そのまま表記したいところですが、少し大きな値になると桁数が非常に多くなってしまい、ただでさえ分かりにくい2進数がさらに分かりにくくなります。

そこで桁数を少なくするためのテクニックとして、8進数や16進数を用います。
8進数の1桁は、2進数の3桁に対応し、16進数の1桁は2進数の4桁に対応するため、2進数から8進数・16進数には簡単に置き換えることが出来るためです。

2進数と8進数・16進数を変換するには、以下の表で対応を覚えてしまいましょう。

10進数2進数8進数16進数
0000
1111
21022
31133
410044
510155
611066
711177
81000108
91001119
10101012A
11101113B
12110014C
13110115D
14111016E
15111117F
16100002010
2進数と8進数の変換

2進数の3桁は、8進数の1桁に対応しています。
これを利用し、小数点を基準に3桁ずつ区切り、それぞれを8進数に変換していくと8進数の値となります。
*3桁に足りない部分は0を補います。整数部の場合は左に、小数部の場合は右に補います。

2進数と16進数の変換

2進数の4桁は、16進数の1桁に対応しています。
これを利用し、小数点を基準に4桁ずつ区切り、それぞれを16進数に変換していくと16進数の値となります。
*4桁に足りない部分は0を補います。整数部の場合は左に、小数部の場合は右に補います。

情報を表す単位

コンピュータ内部では、電流のON/OFFによって情報を表現しています。
この電流のON/OFFを数字に置き換えた場合、0と1の2つの数字のみを使う2進数のほうが都合が良いため、コンピュータ内部でデータを処理する場合には2進数が用いられています。

ビット

コンピュータはデータ処理に2進数を用いますが、この2進数1桁分の情報(ON/OFF、0 or 1)がコンピュータで扱うデータの最小単位で、「ビット(bit)」といいます。

1ビットの情報量で表せるデータの範囲は、2進数1桁分ですので、0か1の2パターンです。

ビットで表すことの出来る範囲

1ビット(=2進数1桁)で表すことの出来る情報は0か1の2通りです。
これを2桁分使うと、「00」「01」「10」「11」の4通りが表せます。

2=21、4=22ですので、nビット(2進数n桁)では、2n通りの情報を表すことが出来ます。

バイト

データの最小単位はビットですが、記憶装置の保存容量などを表す単位として「バイト(byte)」という単位もよく使われます。

「1バイト = 8ビット」として換算しますので、1バイトで表すことの出来る範囲は28で256通りとなります。

コンピュータの歴史

なぜ、コンピュータの歴史にふれるのか?
それは、基本情報処理技術者のシラバスとして提示されている、『基礎理論』の「離散数学」や「応用数学」といった科目をなぜ学ぶ必要があるのか?を理解する助けになるからである。

『離散数学』『応用数学』が試験範囲として設定されている意義は、
・コンピュータの中では、情報は「0」か「1」かになる
・コンピュータは人間が組み込んだプログラム(=アルゴリズム)を忠実に再現する
この点を理解するために、用意されているとも言える。

1:計算機以前のハナシ

そもそも、「コンピュータ」というのは、何者なのか?
日本語で直訳すれば、「電子計算機」と訳される。
要するに、何らかの計算をするための機械ということになる。

では、コンピュータというものは、ある時に誰かが突然その原理を思いついて発明したものなのか?
もちろん、答えはNOである。
先人達が、必要に迫られて計算を行うための道具をつくろうとする過程から、徐々に生まれてきたものなのである。

人類にとって、計算するための最初の道具として使われたものは、人間の指や石ころであったと言われている。今の常識から考えると、あまりにも単純なことではあるが、これでも立派な「計算道具」である。計算する、という意味の英語”calculate”の語源は、ラテン語の『小石』から来ていることからも、それはうかがい知ることができる。

また、コンピュータの中ではすべての情報は0か1で表されており、そのようなデータを『デジタル』と読んでいるが、『デジタル(digital)』の語源も、ラテン語の『指』から来ている。

2:計算道具の進化

小石や指で数を数える方法を、もう少し発展させてものが、東洋の「ソロバン」や西洋の「計算尺」である。

「ソロバン」の起源は紀元前の中東で用いられていたという説があり、中国では14世紀ごろ、日本には室町時代には伝わっており、古い歴史のある計算道具である。こちらは、コマが「上がっているか」「下がっているか」のどちらかの状態しか見ないので、指や小石の延長で「デジタル」な計算道具である。

「計算尺」は、目盛をつけた2本の定規を使って簡単に計算を行う道具で、1622年にイングランドの数学者・オートレッドが発明した。
スコットランドの数学者・ネイピアが1617年に考案した「ネイピアの棒」を起源としており、数学の「対数」という考え方を使って、掛け算や割り算を簡単な足し算や引き算で置き換えようとしたモノ。
定規のカーソルの位置で計算結果を求める「アナログ」の計算機であった点が特徴である。「関数電卓」が登場した1970年代頃までは理工学系の設計計算や測量の分野で使用されていた。
cf)ネイピアの棒:http://www.geocities.jp/kyo_oomiya/napier.html など

*対数とは・・・

16世紀末にジョン・ネイピアやヨスト・ビュルギらによって、考案され、便利な計算方法として広まったモノ。

定義:
正の実数 a ≠ 1 をとると、 任意の正の実数 xに対し、x = ap を満たす 実数 p が唯一つ定まる。
この p を p = logX と書き、p のことを 「a を底(てい、base)とする x の対数」という。

ソロバンも計算尺も「手動」で計算を行う道具だが、機械式の計算機も17世紀に登場している。以下、登場順に

  • シッカートの計算機:6桁の加減算と、オーバーフローの検出、複数の「ネイピアの棒」を使った乗算が可能
  • パスカルの計算機:歯車を使って、加減算を計算。自動で桁上りする機能を持つ
  • ライプニッツの計算機:パスカルの計算機を改良し、乗除算が出来る

ライプニッツは、計算機を単純に数値の計算だけに使うのではなく、「論理的な仮説を検証することにも使える」という考え方を打ち出している。これは、現在のコンピュータにも通じるもので、その後の計算機の理論的な発展に重要な影響を及ぼしたとされている。

ただし、ここまでの機械は歯車などの比較的単純な機構を用いた装置であった。

3:コンピュータ誕生前夜

(1)プログラムの誕生

現在のコンピュータにもつながる基本的な仕組みは、産業革命期のイギリスにおいて発明された。航海に必要な天文学の計算や、機械設計などの科学技術分野で、膨大な計算作業が必要になったことを受けてのことである。

それは、イギリスの数学者・バベッジによる「階差機関」と「解析機関」として、開発が着手され、とりわけ「解析機関」は現在のコンピュータにも通じる、重要なアイディアが盛り込まれていた。
「演算機能」と「記憶機能」が分離されていて、「プログラム」によって色々なパターンの計算をさせよう、という考え方を採用していた点である。そのため、バベッジは「コンピュータの父」とも言われている。
*ただし「階差機関」も「解析機関」も、バベッジが生きているうちには完成しなかった。

「解析機関」では外部から「プログラム」を与えるとされているが、その「プログラム」の入力には、織り機のために発明されていた「パンチカード」を使うことが考えられていた。「パンチカード」は紙で出来たカードに穴をあけたもので、開けられた穴の位置によって計算の指示を与えるものである。

ちなみに、「解析機関」の開発に深く携わった人物として、エイダという女性がいる。彼女はバベッジに対して、「解析機関」の開発費用の援助を行っただけでなく、解析機関の解説書の作成や、解析機関で利用されるプログラムの作成にも携わっている。そのプログラムの考え方は、現在のコンピュータのプログラムにも通じるほど高度なものであり、『人類初のプログラマ』とも言われている。

(2)0と1の世界の確立

ライプニッツによって『計算機械が論理的な仮説の検証にも使える』という考え方が提唱されたが、19世紀になって、イギリスの数学者・ブールがこの考え方をさらに発展させて、コンピュータで使われる理論の基礎を築いた。

1854年にブールは『真』と『偽』の二つの値を使う『論理学』という学問を、『1』と『0』という2つの数字だけを使って扱うことが出来るという考え方を示した。これを『ブール代数』と読んでいる。

ブールは『事象1』が『真』であり、かつ、『事象2』が『真』であれば、『結果』も『真』であるということを、『論理積』として、単純に1×1=1という演算で表現した。この『論理積』以外の他に、『論理和』や『否定』といった『論理演算』を使って、論理の世界を1と0の演算で表現できることを証明した。

つまり、1と0の演算を行える機械を作りさえすれば、その機械でどんな論理的な計算もできることを示したのである。

その後、20世紀に入り、イギリスの数学者・チューリングによって、論理的な計算を仮想的な機械で行うことが出来ることが示された。

チューリングは、無限に長いテープと、それに0か1かの情報を読み書きするヘッドを持った、テープレコーダーのような機械を想定し、その機械を何回か動作させれば、加減乗除をはじめとして、数学的な様々な問題が解けることを証明したのである。この仮想的な機械は『チューリング機械』と呼ばれている。

また、チューリング機械の可能性を示すと同時に、限界も示されており、「プログラムに書けない問題は解決することは出来ない」ということである。プログラムに書ける=アルゴリズムが分かっている、という言い方もできるが、アルゴリズムがわからない問題は、チューリング機械では解決できないということである。

(3)コンピュータの誕生

バベッジの『解析機関』で構想された、『プログラムによって動作する計算機』というものが実現するのは、第二次世界大戦前後まで待つこととなる。

まずは、ドイツで1938年に『Z1』という計算機械が開発される。初期型の『Z1』は機械式だったが、改良版の『Z2』では、電気のオン・オフを切り替える『リレー』という電子部品が使われており、航空機の設計計算に用いられた。

一方、アメリカでは1939年にアタナソフにより『ABC』という名の電子計算機が試作された。『ABC』では、リレー回路だけではなく、『真空管』という電子部品も使われた。さらに1944年に『MarkⅠ』というリレーを使った大型計算機も開発されている。

それ以外にも、1943年にイギリスで『COLOSSUS』という真空管を使った電子計算機が開発されている。

しかし、当時は世界大戦中ということもあり、情報の交換は行われず、各国内で独自に開発が行われ、現在の形のコンピュータが開発されるのは、第二次世界大戦終了後のことである。

3:コンピュータ誕生と発展

(1)最初のコンピュータ・ENIACの誕生

一般的に、「世界初のコンピュータ」と言うと、1946年に誕生した『ENIAC』を指す。

『ENIAC』はアメリカ・ペンシルバニア大学のエッカートとモークリーによって開発された計算機で、『ABC』の技術も取り入れているが、最大の違いは真空管だけを使ってすべての計算をさせるという点である。

真空管はリレーと同様に電気のスイッチの役割を果たすが、動作がリレーよりも格段に速いという特徴を持っていた。反面、リレーよりも信頼性に劣り、価格も高かったのだが、『ミサイル弾道のシミュレーション』に使いたいというアメリカ陸軍の思惑もあり、開発が進められた。

但し、『ENIAC』のプログラムは実際に人間が配線を変更することで行われ、現在のコンピュータの仕組みとは異なっている部分もあり、コンピュータの定義によっては必ずしも世界最初のものではない。 しかし、いずれにせよ『ENIAC』が、コンピュータの黎明期において歴史的に重要な役割を果たしたものの1つであることに変わりはない。

(2)フォン・ノイマン型コンピュータの確立

『ENIAC』の計算速度は、それまでの計算機械と比べて、圧倒的な性能を誇った。しかし、プログラムの変更が、人手による配線の変更を要し、手間がかかるという欠点があった。

そこで、後継機の『EDVAC』では、プログラムをあらかじめ記憶装置に内蔵しておく方式が採用されることになった。この方式を、『プログラム内蔵方式』といい、この方式を取るコンピュータのことを『フォン・ノイマン型コンピュータ』と呼ぶ。

当時すでに有名な科学者であったフォン・ノイマンは『ENIAC』の開発に途中から参画し、『ENIAC』・『EDVAC』開発プロジェクトにも深く関わっていたのだが、そのなかで出てきたアイディアをフォン・ノイマンが纏め上げたことから、彼の名が残っているわけである。

その『EDVAC』は1950年に完成したが、実は、世界初の『フォン・ノイマン型コンピュータ』とはならなかった。フォン・ノイマンらのアイディアを知った、イギリス・ケンブリッジ大学のウィルクスらが『EDSAC』というコンピュータを1949年、つまり『EDVAC』より先にに完成させたのである。

しかしながら、現在のコンピュータが『EDVAC』の延長線上にあること。すなわち『フォン・ノイマン型コンピュータ』であることには変わらない。

(3)その後のコンピュータの進化

『EDVAC』以降のコンピュータの発展は、「計算スピードの向上」「記憶容量の増大」「小型化・低価格化」といった変化を日進月歩で繰り返し、さらにそのサイクルも短くなる形で急速な発展を遂げできたわけだが、「プログラム内蔵方式」であり、「スイッチの集合体」であるという点で、『EDVAC』の延長線上にあると言える。

この数十年でのコンピュータの進化は、コンピュータの5大要素『演算』『制御』『記憶』『入力』『出力』の各機能の小型化・高速化・大容量化という点に尽きる。

具体的には『スイッチ』の機能を果たす電気部品である『真空管』が『半導体素子』に変わり、『半導体素子』自体も、初期のトランジスタから小型化・高速化が進んでIC、LSIと進化してきた。

コンピュータの形態としても、初期の大型汎用コンピュータから、オフコン・ミニコン、サーバ・ワークステーション、パソコン、といった形でダウンサイジングが進みつつ、現在のパソコンは初期の汎用大型コンピュータよりも高性能を誇るほどの高性能化も進んでいる。

しかしながら、コンピュータがどれだけ小型化・高性能化しても、スイッチの集合体であり、0と1の論理演算の組合せで、処理を実行している点や、アルゴリズム化できない問題は解決できないという、チューリング機械の限界といった、基本的な考え方については変わっていない。

コンピュータの進化という話題では、とりわけパーソナルコンピュータ(パソコン)の進化のスピードは凄まじいものがある。その大きな要因となっているキーワードが、『デファクト・スタンダード』『オープン・アーキテクチャ』『水平分業』である。

オープン・アーキテクチャとは、内部仕様の公開ということで、元々の狙いとしては、ソフトや周辺機器の開発を容易にし、多数のソフト・周辺機器を競わせることで、本体の魅力をより向上させようというものであった。

現在のパソコンの多くは『PC/AT互換機』と言われ、元はIBMの1商品で、その商品力アップのために仕様が公開されたわけだが、仕様を公開することで、ソフトや周辺機器のみならず、パソコン本体の仕様を真似た物(=互換機)も登場することとなり、パソコン市場を独占しようというIBMの目論見は失敗に終わる。

しかし、世に多数の『PC/AT互換機』が出回り、シェアを拡大することで、『PC/AT互換機』が事実上のパソコンの標準規格となってしまったわけである。(=デファクトスタンダード)
*水平分業が技術革新を進めるというのは、パソコンに限定される話ではない。殆どの産業に言えることである。

4:離散数学や応用数学との関連

結局のところ、基本情報処理技術者やITパスポートという国家試験のカリキュラム(シラバス)で、なぜ離散数学や応用数学といったテーマが出てくるのか、という事だが、
『コンピュータは色々なパターンの計算をさせるための機械である』
『様々な計算は、0と1を使った論理演算の組合せで実現できる』
という基本的な事項は、コンピュータが進化しても変わりない部分である。

コンピュータの中での情報の表現方法や、論理演算といった、コンピュータの根幹に関わる理論を扱っているのが『離散数学』という分野であり、「どんなパターンの計算をさせるのか?」といった具体的な事例について触れているのが、『応用数学』(特に確率統計や、数値解析)という分野ということになる。

あくまでも、情報処理技術者として、『離散数学』や『応用数学』の分野から、役に立ちそうなエッセンスを吸収してくださいね、という事であり、情報処理技術者に学問としての『離散数学』や『応用数学』をマスターすることが求められているわけではない。(無論、マスター出来れば、大きな武器にはなるし、ハード/ソフトの根幹に近い部分では、高度な離散数学や確率統計・数値解析手法について熟知していることが求められる)

また、『数学』という学問が、『論理的思考能力』を鍛えるための学問である点も見逃せない。
『論理的思考』とは『物事を数理的に捕え、筋道を立てて考え、処理する』という事になる。

実際の仕事では『習うより慣れろ』『理論より実践』ということは、よく言われるが、慣れることで処理能力は向上しても、『なぜそうなるのか?』ということが分かっていなければ、これまでの経験を応用して異なる仕事をしたり、何がしかの問題が発生したときに原因を究明することが難しくなる。

例えば、何がしかのプログラム言語で「1÷3×3」という計算をさせたところ、1になるはずの解が1にならない。いくら算数のドリルを解いたところで、コンピュータ上で、数字がどう表現されているのか、四則演算がどう行った仕組みで行われているのか、を理解しておかないと、何が悪くて期待通りの結果が出ないのかが分からないのである。

人間の脳は直感的に、この数式の解が1であると分かるが、それはあくまでも四則演算というアルゴリズムを刷り込まれているから『直感的』に解が出せるが、コンピュータにもそのアルゴリズムを教えてあげないと、正しく計算はしてれないし、コンピュータの内部では『分数』という便利なものは表現できない点、割り算では誤差が出る可能性がある、という原理が分かっていないと、対処法が導き出せないのである。

参考文献

  • 「誰がどうやってコンピュータを創ったのか?」 星野 力 著(共立出版 1995年 )
  • 「エニアック 世界最初のコンピュータ開発秘話」 スコット・マッカートニー 著 日暮 雅通 訳(パーソナルメディア 2001年)

離散数学とは

離散数学とは

離散数学(りさんすうがく、英語:discrete mathematics)とは、原則として離散的な(言い換えると連続でない、とびとびの)対象をあつかう数学のことである。有限数学あるいは離散数理と呼ばれることもある。
グラフ理論、組み合わせ理論、最適化問題、計算幾何学、プログラミング、アルゴリズム論が絡む[1]応用分野で、その領域を包括的・抽象的に表現する際に用いられることが多い。またもちろん離散数学には整数論が含まれるが、初等整数論を超えると解析学などとも関係し(解析的整数論)、離散数学の範疇を超える。

Wikipediaから引用

『離散数学』という言葉自体は義務教育の数学ではまず聞かないだろうし、高校レベルでもキーワードとしては出てこなかったと記憶している。
とは言え、離散数学の範疇とされている要素には義務教育で習ったものや、情報処理技術者試験で問われる要素は多い。

特に、コンピュータ内部での情報の扱いを考えた場合、情報は電気信号の[ON]と[OFF]の2値の組み合わせで管理されているので、一般的には『2進数』の[0]と[1]に対応させて表現している。
ただ、2進数そのままでは人間にとっては至極扱いにくいため、必要に応じて10進数に戻して理解する。
この時の2進数や10進数という数の表し方や、相互に変換する方法などが『離散数学』の範疇にあるため、情報処理技術者試験のシラバスには『離散数学』という分野が登場している。

情報処理技術者試験での学習内容

【基本情報・応用情報】
基数,基数の変換,数値の表現,算術演算と精度など,コンピュータで扱う数値表現を修得し,応用する。
集合,論理演算の基本法則,手法を修得し,応用する。

【ITパスポート】
基数の基本的な考え方を理解する。
集合の基本的な考え方を理解する。

(1)基数 ITパスポート 基本情報 応用情報

2 進数,8 進数,10 進数,16 進数,n 進数の表現,2 進数と 10 進数などの基数の変換手法 を理解する。

(2)数値の表現 ITパスポート  基本情報  応用情報

負の数の表現(補数表現),小数の表現を理解する。

用語例: 固定小数点数,単精度浮動小数点数,倍精度浮動小数点数,仮数,指数,BCD (Binary Coded Decimal:2 進化 10 進),パック 10 進数

(3)算術演算と精度 基本情報 応用情報

加減乗除,表現可能な数値の範囲,シフト演算,演算精度(誤差とその対策)など,コ ンピュータでの算術演算を理解する。

用語例: 論理シフト,算術シフト,桁落ち,情報落ち,丸め,打切り,オーバフロー(あ ふれ),アンダフロー,単精度,倍精度

(4)集合と命題 ITパスポート  基本情報  応用情報

集合,命題,ベン図の手法と考え方を理解する。

用語例: 和集合,積集合,補集合,部分集合,真,偽,命題論理

(5)論理演算 ITパスポート  基本情報  応用情報

論理式の表現,論理演算,ド・モルガンの法則などの基本法則,真理値表,カルノー図の 手法を理解する。

用語例: 否定,論理和,論理積,排他的論理和,否定論理和,否定論理積,論理関数,分 配則