「基礎理論」カテゴリーアーカイブ

離散数学とは

離散数学とは

離散数学(りさんすうがく、英語: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パスポート  基本情報  応用情報

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

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

基数

この記事での学習内容 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通りとなります。

数値の表現(整数)

この記事での学習内容 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パスポート 基本情報 応用情報

小数の表現を理解する。

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

小数の表現方法の種類

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

固定小数点数

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

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

  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ビットの倍精度浮動小数点数を利用します。

 

算術演算と精度

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

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

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

シフト演算

引き算は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パスポート  基本情報  応用情報

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

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

集合

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

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

集合演算

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

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

集合の包含関係

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

命題

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

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

論理演算

この記事での学習内容 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つ以上の式で、論理積の項を論理和した形(積和形)の場合に使いやすいとされている。

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

 

応用数学とは

応用数学とは

応用数学(おうようすうがく、英語:applied mathematics)とは、数学的知識を他分野に適用することを主眼とした数学の分野の総称である。

Wikipediaから引用

情報処理技術者試験において、『応用数学』では、確率・統計の計算や分析手法を理解し活用すること、数値解析、グラフ理論、待ち行列理論などの基本的な数学的原理を理解し活用することが求められています。

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

【基本情報・応用情報】
確率・統計の計算、分析手法を習得し、応用する。
数値解析、グラフ理論、待ち行列理論など、数学的原理を習得し、応用する。

【ITパスポート】
確率と統計の基本的な考え方を理解する。

(1)確率と統計 ITパスポート 基本情報 応用情報

1.確率

順列、組合せ、場合の数、確率とその基本定理、確率分布(離散型、連続型)と期待値、マルコフ過程を理解する。

用語例:階乗、加法定理、乗法定理、正規分布、ポアソン分布、指数分布、カイ二乗分布、確率密度

2.統計

度数分布表、ヒストグラム、代表値、ばらつき、相関関係、回帰直線、分散分析、検定など統計分析の手法を理解する。

用語例:中央値(メジアン)、最頻値(モード)、平均値、標準偏差、分散、相関係数、推定、回帰分析、帰無仮説、有意水準、カイ二乗検定

(2)数値計算 基本情報  応用情報

連立一次方程式の解法など、数値計算に関する基本的な内容を理解する。

用語例:行列、対数、掃出法、近似解法、収束、誤差

(3)数値解析 基本情報 応用情報

二分法、補間法、オイラー法など、近似解を数値的に求める考え方や計算過程で生じる誤差を理解する。

用語例: 数値積分、シンプソン法、ニュートン法、絶対誤差、相対誤差、丸め誤差、打切り誤差

(4)数式処理 基本情報  応用情報

コンピュータを用いて、数式を記号的に代数処理する数式処理システムとそのアルゴリズムを理解する。

用語例: 因数分解、微分、積分

(5)グラフ理論 基本情報  応用情報

グラフ理論の基本的な概念とその応用を理解する。

用語例: 無向グラフ、有向グラフ、完全グラフ、重み付きグラフ

(6)待ち行列理論ITパスポート 基本情報  応用情報

待ち行列理論の構成要素、考え方、M/M/1モデルにおける計算、乱数を利用したシミュレーションを理解する。

用語例: サービス時間、到着間隔、平均到着率、平均サービス率

(7)最適化問題 基本情報  応用情報

最適化問題とは何か、線形計画法、PERT、最短経路問題などの考え方を理解する。

用語例: 動的計画法

確率と統計(1)

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

順列、組合せ、場合の数、確率とその基本定理、確率分布(離散型、連続型)と期待値、マルコフ過程を理解する。

用語例:階乗、加法定理、乗法定理、正規分布、ポアソン分布、指数分布、カイ二乗分布、確率密度

場合の数

ある出来事が起きる可能性の数を「場合の数」と呼びます。場合の数で数えられる「ある出来事」は「事象」と呼びます。

例えば、サイコロを一個転がす場合を考えると、場合の数は6です。サイコロが2個になれば、場合の数は 6 × 6 で36です。

順列

箱の中に赤、青、黄の3種類の玉が1個ずつあるとします、この中から2個を選んで、順番に並べる場合、次の6通りの順番が考えられます。

1個め
2個め


この例のように、複数あるものから幾つかを選んで、順番を付けて並べる時の並べ方を「順列(Permutation、パーテーション)」といいます。n 個の中から r 個取って並べる順列を、nPr と表します。

順列の個数は計算で求めることが出来ます。
上の例では、1個めの玉の色は赤、青、黄の3通りあり、2個めは残りから取るので2通りあります。
1個めの3通りに続いて、2個めの2通りのとり方が並ぶと考えられるので、全部で 3×2=6 通りの順列となります。
同じ要領で、10個のうちから3個選ぶ順列は 10×9×8 = 720通りあります。

n 個の中から r 個取って並べる順列は、以下の公式で求められます。

nPr = n × (n-1) × ・・・× (n-r+2) × (n-r+1)

又は、階乗を使って、以下のような式でも表されます。

階乗とは、以下のように 値を n から 1まで、全て掛け算する計算のことです。

n! = n × (n-1) × ・・・× 2 × 1

公式を使って、10個の中から3つを選んで順に並べる順列を求めると、以下のようになります。

組合せ

複数あるものから幾つかを選んで、順番を付けずに一組にする時のまとめ方を「組合せ(Combination、コンビネーション)」といい、 n 個の中から r 個を取ってまとめる組合せを nCr と表します。

例えば、赤、青、黄の3種類の玉(1個ずつ)の中から2個を選んで組にする場合、「赤、青」「赤、黄」「青、黄」の3通りの組み合わせができます。
順列の場合と違い、「赤、青」と「青、赤」は同じ組み合わせとみなします。

組合せの数を求めるには、以下の公式のように、全体の順列を取った数の順列でわれば求められます。

公式を使って、10個の中から3つを選んだ組合せの数を求めると、以下のようになります。

確率

ある出来事が起きると期待できる割合を確立(Probability)といい、事象Aの起こる確率を P(A) と表します。

例えば、1個のサイコロを投げて、「1」の目が出る確率は次のように求めます。

  • 全ての目の数は1~6の6通り
  • そのうち、「1」の目は1つだけ

事象の排反

同時に起こりえない事象同士のことを、『事象排反する』という。

ベン図を書いた時に重なる部分がなかったり、論理積をとった時に解が空集合になる場合。

例えば、サイコロを振って『出目が2である』という事象と、『出目が3である』という事象は同時には発生し得ないので、事象が背反している。

が、『出目が2の倍数である』という事象と『出目が3の倍数である』という事象は、出目が6になったときに、ともに条件を満たすので、これらの事象は背反しない事になる。

事象の独立

二つの事象の発生確率を考えた場合、

  • 互いに影響しない→事象が独立している。
    例)サイコロを続けて振った場合の出目、ルーレットで特定の数字が出る確率など
  • 他方に影響を与える→事象が独立していない
    例)あたり数に限りのあるクジ引きで、1人目が当たる確率と、2人目が当たる確率。

*独立と排反の違い
独立している→互いに影響しない
背反している→同時に発生しない

確率の和事象(加法定理)

事象A又は事象Bが起こることを「和事象(A ∪ B)」といいます。
和事象の起こる確率は事象Aの起きる確率と事象Bの起きる確率を足したものから、事象AとBの積事象の確率を引いたものです。

例えば、サイコロを2回投げ、1回目に偶数の目が出る場合と、2回めに「2」が出る場合のいずれか、又は両方が起こる確率は以下のように求めます。

確率の積事象(乗法定理)

互いに独立した事象であるAとBがともに起こることを、事象AとBの積事象( A ∩ B)と言います。
積事象の起こる確率は事象Aの起きる確率と事象Bの起きる確率を掛けたものです。

例えば、サイコロを2回投げる時、1回目に偶数の目が出て、なおかつ2回目に「2」が出る確率は次のように求めます。

(参考)事象が独立していない場合に、事象Aが起きたという条件下で、事象Bが起きる確率は、以下のように求める。

マルコフ過程

時間とともに確率が変化する過程を「確率過程」と呼びます。例えば、降水確率は時間とともに確率が変化するので、確率過程とみなせます。
確率過程の中で、確率の値が過去の状態に一切関係がないものを「マルコフ過程」といいます。

例えば、サイコロを振り続ける場合にある目が出る確率過程を考えます。
現在のサイコロの目が出る確率は、過去のサイコロの目の影響を一切受けないので、マルコフ過程となります。
これに対して、降水確率は現在の降水状況に影響を受ける確率過程なのでマルコフ過程にはなりません。

  • 確率過程を取る例:株価、為替、電子回路に対するノイズの発生確率、降水確率など
  • マルコフ過程を取る例:サイコロ、ルーレット、宝くじの当選番号

確率分布

ある事象が起きる確率が変数によって決まる場合、変数と確率の関係を「確率分布」と呼びます。

例えば2個のサイコロを降る場合を考えます。

目の数の合計が2になるのは、1と1の場合だけなので、36分の1の確率です。
目の数の合計が3になるのは、1と2,2と1の2つの場合なので、18分の1です。
したがって、この場合は目の数の合計を変数とする確率分布が考えられます。

出た目の和23456789101112
確率1/362/363/364/365/366/365/364/363/362/361/36

なお、確率分布にはサイコロの目のように確率変数が離散的な値を取る場合と、連続する値を取る場合があります。

  • 離散型の確率分布:二項分布、ポアソン分布など(サイコロの目など、確率変数がとびとび)
  • 連続型の確率分布:正規分布、指数分布など(ある人の身長・体重など、確率変数の小数点以下をいくらでも細かく取れる場合)
ポアソン分布

単位時間中に平均でλ 回発生する事象が、ちょうど k 回(k は0を含む自然数)発生する確率をグラフに取ると、λ = k となる時にピークが来るようなグラフになる。

例:1時間に5人の利用者があるATMで、実際に1時間にATMを利用した人数の分布。

指数分布

単位時間中に平均でλ 回発生する事象が、「次に発生するまでの時間」の分布。

例:1時間に5人の利用者があるATMで、次にATMを利用する人が来るまでの時間の分布。

カイ二乗分布

独立に標準正規分布に従う k 個の確率変数 X1, …, Xk をとる。 このとき、統計量   の従う分布のことを自由度 k のカイ二乗分布と呼ぶ。この分布は自由度 k に応じて下図のような形をとる。

実際に様々な観測データを取得した場合、その分布には誤差が含まれるため、理論的に求められる分布と完全には一致しない。例えば、サイコロの各目の出る確率は1/6であるが、だからといってサイコロを6回振ったら各目が1回ずつ出るわけではない。フル回数を多くすればおおよそ1/6ずつに近い分布になると思われるが、均等に1/6ずつにはならない。

こういった時に「実際の観測データが理論値の分布にほぼ等しいとみなせるかどうか」を分析する際に、カイ二乗分布が用いられる。(この分析方法のことを「カイ二乗検定」とよぶ)

確率と統計(2)

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

度数分布表、ヒストグラム、代表値、ばらつき、相関関係、回帰直線、分散分析、検定など統計分析の手法を理解する。

用語例:中央値(メジアン)、最頻値(モード)、平均値、標準偏差、分散、相関係数、推定、回帰分析、帰無仮説、有意水準、カイ二乗検定

統計

ある集団に関するデータを集めてその分布を調べ、数値化して集計することを統計といいます。

統計を取り、様々な分析手法(表やグラフを活用する)を用いると、その集団の性質や特徴をつかむことが出来ます。

度数分布表

度数分布表は統計の基礎資料となるものです。

例えば、15人が受けた試験の得点を10点刻みで採点し、結果を次のようにまとめたとします。

上の表のように、データ全体の発生範囲をいくつかの階級に分け、それぞれの階級にデータがいくつ分布しているかを示す表のことを、度数分布表といいます。

ヒストグラム

ヒストグラムはデータ分布の状況を見るために作られる図解です。
度数分布表を棒グラフにしたもので、連続した数値を区分ごとに分けて、横軸の目盛とします。

ヒストグラムにおいて、それぞれの範囲に属するデータの件数を「度数」といいます。ある区分に集中してデータが分布する場合、その区分を中心とした山形のグラフになります。

正規分布

正規分布は、データが平均値を中心として+ーに対象に分布した状態のことです。

一般的に、ある事象について一定数以上のデータを抽出して統計と取ると正規分布になり、そのヒストグラムは左右対称の釣鐘型になると言われています。

ポアソン分布

ポアソン分布は、発生確率の低い事象で見られる確率分布です。
例えば、電話における単位時間中の着呼数、工場における不良品の発生数などがポアソン分布に従うと言われています。

単位時間中に平均でλ 回発生する事象が、ちょうど k 回(k は0を含む自然数)発生する確率をグラフに取ると、λ = k となる時にピークが来るようなグラフになる。

例:1時間に5人の利用者があるATMで、実際に1時間にATMを利用した人数の分布。

指数分布

指数分布は発生階数の低い事象で見られる確率分布です。指数分布は信頼度の計算などでよく使われます。(信頼度:機械の部品が故障しない確率)

指数分布はポアソン分布と関係していて、電話における単位時間内の着呼数がポアソン分布の時、着呼間隔は指数分布になります。

単位時間中に平均でλ 回発生する事象が、「次に発生するまでの時間」の分布。

例:1時間に5人の利用者があるATMで、次にATMを利用する人が来るまでの時間の分布。

カイ二乗分布

独立に標準正規分布に従う k 個の確率変数 X1, …, Xk をとる。 このとき、統計量   の従う分布のことを自由度 k のカイ二乗分布と呼ぶ。この分布は自由度 k に応じて下図のような形をとる。

実際に様々な観測データを取得した場合、その分布には誤差が含まれるため、理論的に求められる分布と完全には一致しない。例えば、サイコロの各目の出る確率は1/6であるが、だからといってサイコロを6回振ったら各目が1回ずつ出るわけではない。振る回数を多くすればおおよそ1/6ずつに近い分布になると思われるが、均等に1/6ずつにはならない。

こういった時に「実際の観測データが理論値の分布にほぼ等しいとみなせるかどうか」を分析する際に、カイ二乗分布が用いられる。(この分析方法のことを「カイ二乗検定」とよぶ)

統計の指標

統計の指標として、平均、メジアン、モード、レンジなどの値がよく用いられます。これらの値のことを「代表値」といいます。

代表値とは、多数あるデータの値を一つの数値で代表させた値です。

平均データの合計値をデータの個数で割った値
メジアン中央値。データを大小順に並べた時に中央の位置に来る値
モード最頻値。データ中に存在する個数が最も多い値
レンジ範囲。データの最大値と最小値の差

以下の度数分布表があった場合、各代表値は以下のようにして求めます。

平均

データの合計値:10+30+40×2+50×4+60×3+70×2+80+90 = 810
データの個数:15
平均:810 ÷ 15 = 54

メジアン

個々のデータを昇順(小さい順)に並べ、中央に来る値を見る。

中央に来る値は8番目の値なので、メジアンは50。

なお、集計データが偶数個のときはメジアンは2つの中央値の平均を使う。

例:10, 30, 40, 50, 70, 80 の6つのデータのメジアン
3番めと4番目が2つの中央値になるので、(40+50) ÷ 2 =45

モード

得点の中で出現度数が最も高い値は50 (4回) なので、モードは50

なお、最頻値が複数ある場合はそれら全てがモードとなる。

レンジ

得点の最大値:90
得点の最小値:10
レンジ: 90 – 10 = 80

散布度(ばらつきの度合い)

データの分布の特性は代表値だけでは表しきれません。
例えば、以下のようなケースで代表値として平均値を採用する場合、下記の2つのケースはどちらも平均値は10で変わりません。

  • ケースA:0,10,20
  • ケースB:5,10,15

しかし、データのばらつき度合いが異なります。このばらつきの度合いを示すのが散布度です。

代表的な散布度には分散と標準偏差があります。

分散は以下の式で求めます。

Σ( データの値ー平均値 )2

これに基づいて、先ほどの2つのケースの分散を求めます。

  • ケースA:0,10,20
    ( 0 – 10 )2 + ( 10 – 10 )2 +( 20-10 )2 =100 + 0 + 100=200
  • ケースB:5,10,15
    ( 5 – 10 )2 + ( 10 – 10 )2 +( 15-10 )2 =25 + 0 + 25=50

標準偏差

正規分布の形は、母集団の平均値と、母集団の分散から求めた標準偏差で決まります。

分散とはデータのばらつきを表す値で、標準偏差は分散のルート(√ )です。

平均をμ (ミュー)、標準偏差をσ (シグマ) と表すと、正規分布では約68%のデータが μ ± σ の範囲に収まり、約95%のデータが μ ± 2σ の範囲に収まります。
 

回帰直線

散布図(*1)のデータに、できるだけ一致する曲線を求める分析を「直線回帰分析」と呼びます。
直線回帰分析では、最小二乗法と呼ばれる方法が、一般的には使われます。
これは、実際のデータの値と、直線上の値の差の二乗が最小になる直線を求める分析方法です。直線は「傾き(*2)」と「y切片(*3)」と呼ばれる2つの値で定まります。

回帰直線は、実際のデータとは一致しません。データの分布によっては回帰直線と一致する度合いが大きかったり小さかったりします。
データの分布が回帰直線と一致する度合いを「相関」といいます。回帰直線に一致するほど「相関が強い」といいます。
相関の強さを数値で示したものが「相関係数」です。相関係数は-1~1までの値を取ります。

(*1)散布図:2つの属性値の相関関係を表したグラフ(例:身長と体重の相関など)

(*2)傾き:xが1増加した時のyの変化量を表す値。傾きがプラスの場合は右上がりの直線、マイナスのときは右下がりの直線となる。絶対値が大きいほど傾きは急。

(*3)y切片:直線とy軸の交点でのyの値。y切片が大きいほど、直線はグラフの上方に位置する。

標本調査

調査対象の件数が多い場合、対象全てを調査することが難しい場合があります。

このような場合には、調査対象の中から一部を取り出して調査を行い、全体を推定します。
このような分析を標本調査と呼びます。

例)テレビ視聴率、世論調査など

数値計算

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

連立一次方程式の解法など、数値計算に関する基本的な内容を理解する。

用語例:行列、対数、掃出法、近似解法、収束、誤差

単項式、多項式、次数

単項式は、数値や文字の「掛け算」だけで造られた式のことです。2x や 3b などは単項式です。

多項式は単項式の足し算、引き算の形式で造られた式です。3x-2b と言った式が多項式の例です。多項式の中にある単項式は多項式の「項」と呼びます。

次数は、単項式の場合掛け算されている「文字の個数」です。3xy という式の場合、掛け算されている文字はx,y なので次数は2、x3 の次数は3となります。
多項式の場合は、一番次数の高い項の次数がその式の字数です。
x2+y という式の場合、x2 の次数2が一番高いので、この式の次数は2となります。

方程式、1次方程式

方程式とは、x , y といった「未知数」を含む等式のことです。未知数は「まだ分かっていない数」のことで、xやy といった文字で表します。

一次式とは、未知数の2乗以上を含まない式のことです。一元一次式は未知数が1つの一次式、二元一次式は未知数が2つの一次式です。

1次方程式とは、未知数の2乗以上の関係を含まない等式のことです。

連立一次方程式

連立方程式とは、同時に成立する複数の方程式です。方程式を組み合わせることにより、複数の未知数の解を求めることが出来ます。

連立方程式の名称は、未知数の数と次数によって決まります。

未知数の数が2個ならば2元連立方程式、3個ならば3元連立方程式となります。

つまり、連立一次方程式とは、複数の未知数を含む複数の1次方程式です。

連立一次方程式の解法

「連立一次方程式を解く」とは、与えられた方程式を全て同時に成立させる未知数の値を求めることです。数学の問題を解く方法のことを「解法」といいます。

連立方程式の解法には、加減法、代入法、等置法などがあります。連立一次方程式はこうした解法を用いて式を1元1次方程式の形にしていき、複数ある未知数を一つ一つ順番に確定していきます。

行列

行列とは、数学用語では、数値や変数を長方形に並べたものという意味になります。行列では横の並びを行、縦の並びを列と呼びます。下図の a , b , c , d などを行列の要素、あるいは成分といいます。

行列の要素を数値などで具体的に記述せずに、一般化して文字で表す場合、要素の右側に要素の位置を示す「添え字」を付けます。
上の図の「b12」であれば、最初の1は行番号、つぎの2が列番号を表します。

なお、行列の中で行数と列数が等しいものを「正方行列」といいます。

行列の和

行列同士の和は、各行列の同じ添字の要素同士を足し算します。
*下図では数値の右下に添え字を付けていますが、計算の説明のために例外的につけています。

行列の差

行列同士の差は、各行列の同じ添字の要素同士を引き算します。

行列の積

行列の積は、行方向と列方向を掛けたものを足して要素とします。行列の要素が1以外の場合、行列A×行列Bと行列B×行列Aの計算結果は異なります。

また、行列の積を「行列A×行列B」で求める場合、下図のように行列Aの列数と行列Bの行数が一致している必要があります。

例えば、行列Aが3行2列の行列だった場合、行列Bは2行n列でないと、積を求めることは出来ません。

行列による連立方程式の表記

連立一次方程式を行列の積を用いて表すことが出来ます。

対数

対数とは、ある数x は、ある数y を何回か掛け合わせた値であるとすると、そのかけ合わせた回数のことを言います。
数式で表すと、x = ya の a を「y を底とするx の対数」といい、 a = logy(x) と表します。
例)8 = 23 なので、log28 = 3

特に底を10とした対数のことを常用対数とよんでいます。

対数グラフ

通常のグラフでは、1, 2, 3, …と言うように、横軸も縦軸も順番に数が増えていきます。このようなグラフは少しずつ変化する値を描く場合などには有効です。

これに対して、2倍、4倍、8倍…と倍々で変化する値を描く場合などはすぐに縦軸が大きな値になって描けなくなってしまいます。

そこで、縦軸だけ対数を使うと、縦の変化量を抑えることが出来ます。このような、片側を対数としたグラフのことを「片対数グラフ」といいます。(両方対数としたグラフは「両対数グラフ」)

素因数分解

素数とは、1とその数自身以外に正の約数がない、1より大きな自然数です。

100以下の素数は、2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97 の25個です。

素因数分解とは、ある正の整数を十数の掛け算の形に分解することです。

例) 78 = 2 × 3 × 13

素因数分解にまつわる法則として、「2つの異なる素数p, q の積である、ある合成数Nが与えられた時、合成数N飲みから、元の素因数p, q を求めることは非常に困難」というものがあります。
この法則を利用し、安全性の根拠としている暗号化技術として、RSAという方式があります。

 

数値解析

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

二分法、補間法、オイラー法など、近似解を数値的に求める考え方や計算過程で生じる誤差を理解する。

用語例: 数値積分、シンプソン法、ニュートン法、絶対誤差、相対誤差、丸め誤差、打切り誤差

数値解析とは、物理学、数学、工学などの科学分野の問題を、方程式を解くのではなく、数値計算を行なって解の近似値を求める手法のことです。

数値解析は、コンピュータを使った様々なシミュレーションなどに用いられています。数値計算、実用解析などとも呼ばれます。

二分法

二分法は、方程式の一つの実数の解を求める時に、解を含む区間を二分して中間点を求め、二分したどちら側に解が入るかを判定し、再度範囲を二分して判定する作業を、何度も何度も繰り返して、解の値を求めていく方法です。

方程式 f(x) = 0 の解を求める時に使用される代表的な数値解析方法の1つで、解のおおよその値を知っていることが前提です。

ニュートン法

ニュートン法は、グラフの形がなだらかに変化している場合に有効な方法です。

下図の様にグラフの形がなだらかな場合、ある値の接線とx軸の交点を取ると、もとの値より、グラフのx軸の交点に近づきます。
これを繰り返して、 f(x) = 0 の解を求める方法です。

補間法

補間法とは、グラフ上の複数の点を通る多項式の曲線で、xの値からyの値を計算することです。

補間法には何種類かの計算方法がありますが、代表的な方法として、ラグランジュ補間法やスプライン曲線などがあります。

ラグランジュ補間法

すべての点を通過する数式を求める方法。データの点数が増えると、曲線の振れ幅が大きくなってしまうという欠点がある。

スプライン曲線

ラグランジュ補間法の欠点を補うために、データを一定の区分で区切った上で、近似する曲線を予測していく方法。

誤差

数値解析で求めた解の値は、あくまでも近似値です。本島の海の値である「真値」との差があり、この差を「誤差」と呼びます。

数値解析の誤差には、絶対誤差、相対誤差、打切り誤差があります。

絶対誤差、相対誤差

真の値(真値)と測定値や近似値との差を誤差といい、この時
絶対誤差=測定値(近似値)- 真値
相対誤差=絶対誤差 ÷ 真値
となっています。

例えば、真値が1000mmで、測定値が998mmだった場合、
絶対誤差は、998 - 1000 = -2mm、
相対誤差は、 -2mm ÷ 1000mm = -0.02 = -2%
となります。

丸め誤差、打切り誤差

計算の結果を指定した桁数で収めるために、最下位の桁を切り捨て、切り上げ、四捨五入などをすることで生じる誤差を「丸め誤差」といいます。

また、計算を途中で打ち切ってしまう場合も真の値とは誤差が出ることになります。この途中で打ち切った時に出る誤差を「打切り誤差」といいます。打切り誤差の例としては、円周率の計算などがあります。

 

 

 

数式処理

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

コンピュータを用いて、数式を記号的に代数処理する数式処理システムとそのアルゴリズムを理解する。

用語例: 因数分解、微分、積分

「数式処理」とは、数値の代わりに文字列を用いて計算式を記号的に処理することです。数値の代わりに用いる文字列を「代数」と呼びます。

具体的な例としては、計算式を分解して積の形に変換する「因数分解」、時間とともに変化する関数の増減を調べる「微分」、図形の面積や立体の体積などを微小な要素の集まりとして計算する「積分」などがあります。

コンピュータ内部でこのような処理を行うときには、数式処理を行います。

数式処理

コンピュータでは、代数を利用することで数式を記号的に処理することが出来ます。数値のみを扱う電卓とは異なり、コンピュータでは方程式をそのままコンピュータで扱うことが出来ます。

因数分解や、微分、積分の計算を行う際に、数式処理が行われっます。

因数分解

因数分解とは、下図や多項式・行列などといった計算式を分解し、因数(計算式)を積の形にすることです。

因数分解の公式
  1.  a2 ± 2ab + b2 =  ( a ± b )2
  2.  a2 – b2 = ( a + b )( a – b )
  3.  x2 + ( a + b )x + ab = ( x + a )( x + b )
  4.  acx2 + ( ad + bc )x + bd = ( ax + b )( cx + d )
  5.  a3 + b3 = ( a + b )( a2 – ab + b2 )
  6.  a3 – b3 = ( a – b )( a2 + ab + b2 )

微分

微分とは、時間の経過に伴って変化する関数の増減の度合いを求めることです。曲線のグラフでは、接線の傾きを求めることに相当します。

例えば、家から駅まで歩く場合を考えます。家から駅まで1時間かけて5キロの道のりを歩いた場合、時速5kmで歩いたことになります。
しかし、実際には常に時速5kmで歩いていたわけではなく、この時速5kmはあくまでも平均時速でしかありません。

このような場合に、実際の歩いた時間と移動距離をグラフに取り、とある時点での歩行速度を求めるような場合に、微分を用います。

なお、ニュートン法で接線の傾きを求める際にも微分が用いられています。

積分

積分とは、図形の面積や体積などを求める方法です。

長方形や三角形であれば公式を使えば面積を求めることが出来ますが、曲線のグラフの一部分のように、曲線で囲まれた部分の面積を求めるといった場合に、積分を用います。

例えば、先述の家から駅まで歩く場合をグラフにした時、横軸に時間、縦軸に速度を表したグラフの場合、積分を使うことで、一定時間に移動した距離を求めることが出来ます。

グラフ理論

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

グラフ理論の基本的な概念とその応用を理解する。

用語例: 無向グラフ、有向グラフ、完全グラフ、重み付きグラフ

グラフ理論

点と点を結ぶ集合であるグラフの性質についての理論をグラフ理論といいます。(ここでいうグラフは、一般的な「グラフ」とは別物)

グラフとは、いくつかの接点(ノード)と呼ばれる点があり、それをある規則に基づいて結んだ線(枝:ブランチ)の集合です。
1つの接点(ノード)に付いている線(枝:ブランチ)の数を次数といいます。

現実世界の様々な要素を節点に置き換えて、その関係性を分析する際に使用されます。

鉄道の路線図などのように、節点同士の距離などに重点を置かず、節点同士のつながり方に重点が置かれます。
また、つながり方の向きを考えるグラフを「有向グラフ」、向きを考えないグラフを「無向グラフ」といいます。

グラフの次数

グラフの次数は以下のような特性を持っています。

  • すべての次数の合計は必ず偶数個になる。(ループしているノードは2本として数える)
  • 次数が奇数になるノードの数も必ず偶数個になる。

グラフアルゴリズム

グラフを探索するアルゴリズムで、探索の仕方によって幅優先順探索法と深さ優先順探索法があります。

幅優先順探索法

探索の優先順位を横方向にした探索法で、根から始め、左から右へ浅い方から探索します。

探索順は、節の数値が探索順となります。

深さ優先順探索法

探索の優先順位を縦方向にした探索方法です。探索の仕方によって、さらに3種類に別れます。

先行順

親→左の子→右の子の順で探索をします。

中間順

左部分木→親→右部分木の順で探索をします。

後行順

左部分木→右部分木→親の順で探索をします。

待ち行列理論

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

待ち行列理論の構成要素、考え方、M/M/1モデルにおける計算、乱数を利用したシミュレーションを理解する。

用語例: サービス時間、到着間隔、平均到着率、平均サービス率

待ち行列モデル

我々の生活の中では、銀行のATMや行政の窓口、商店のレジなど色々なところで行列が作られています。この待たされる行列のことを待ち行列と呼びます。この顧客がサービスを受けるために行列に並ぶ時の、待っている人の人数や待ち時間などを解析するための理論を待ち行列理論といいます。

この理論の中で、特に顧客とサービス窓口、待合室からなるシステムを「待ち行列モデル」として扱っています。

待ち行列モデルには種類がありますが、この種類を表す方法として、1953年にケンドール氏によって提案されたケンドール記号があります。ケンドール記号はA/B/Cという形式で表され、
A:到着時間の分布の種類
B:窓口を利用する時間(サービス時間)の分布
C:窓口の数
となります。

到着時間の分布の種類は、殆どの事象はランダムに到着するので、記号は M を使います。(マルコフ過程のM)

サービス時間の分布は、サービス時間が短い場合が多く、サービス時間が長い場合はそれほど多くないといった事象が一般的で、指数分布のグラフを取ります。

サービス時間の分布が指数分布に従っている場合は、記号はMと表します。

窓口の数は、ネットワークやCPUを待ち行列理論で扱う場合は、窓口が1つのモデルが良く使われます。

これに従って、銀行ATMや売店のレジなどの待ち行列モデルで、窓口が一つのモデルをケンドール記号で表すと、M/M/1となり、「M/M/1モデル」と呼ばれます。

M/M/1モデルでの計算

M/M/1モデルでの、平均待ち時間などを求めるための必要な計算式は下記のとおりです。

  • 平均到着率: λ (ラムダ)
    単位時間あたりに到着する顧客の数
  • 平均到着時間: ta (time arrival)
    ta = 1 / λ
  • 平均サービス率: μ (ミュー)
    単位時間に窓口が処理できる件数
  • 平均サービス時間: ts (time service )
    窓口における一人にかかるサービス時間
    ts = 1 / μ
  • 平均利用率: ρ (ロー)
    窓口をどれだけ利用しているかの割合で0~1の値。
    ρ = λ × ts または ρ = λ / μ
    ρが1以上になってしまう場合、到着時間よりも処理時間が長いことになり、待ち行列が延々と伸び、いつまでたってもサービスが受けられない状況を表します。
  • 平均待ち時間: tw (time wait)
    待ち行列に並んでからサービスが開始されるまでの時間
    tw = ρ / (1 – ρ) ×ts
  • 平均応答時間:T
    行列に並んでから、窓口でのサービスが完了するまでの時間
    T = tw + ts

例:とある行政の窓口で、1時間あたり10人の利用者があり、その窓口では1時間で15人の利用者に対応できる場合の平均待ち時間、平均応答時間を求める。

  1. 文章から、単位時間は1時間とし、λ = 10、μ=15となる。
  2. 平均サービス時間を求める。ts=1/μ なので、
    ts=1/15 (=4分)
  3. 平均利用率を求める。ρ = λ / μ なので、
    ρ = 10 / 15 = 2/3
  4. 平均待ち時間を求める。tw = ρ / (1 – ρ) ×ts なので、
    tw = (2/3) / (1 – 2/3) ×1/15 =(2/3) / (1/3) × 1/15 = 2 × 1/15 =2/15 となり、2/15時間=8分。
  5. 平均応答時間を求める。T = tw + ts なので、
    1 / 15 + 2 / 15 =3 / 15 となり、3/15時間=12分。

 

最適化問題

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

最適化問題とは何か、線形計画法、PERT、最短経路問題などの考え方を理解する。

用語例: 動的計画法

最適化問題

制約のある中で、目的とする関数(目的関数)の解が最大(あるいは最小)となる値を求める問題を最適化問題といいます。

目的関数や制約関数によって幾つかの種類にわけられます。

線形計画法(LP法)

目的関数と制約関数が一次式(直線)で表現できる問題です。線形計画問題の中には、生産などで原材料の使用量などの制約のある中から、最大限の製品をいくつ作れるかを求める、線形計画法などがあります。

非線形計画法

目的関数あるいは制約関数が一次式でない場合の問題です。ニュートン法などの開放があります。

動的計画法

動的計画法は、問題全体を細かい部分問題に分割し、分割された問題の最適解を解いていくことによって、これらの結果を集めて全体の解を導く方法です。

例:最短経路問題。PERTのクリティカルパスを求めるのは動的計画法の一種。

情報に関する理論

 

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

【基本情報・応用情報】
情報理論、符号理論の考え方、仕組みを習得し、応用する。
コードによる文字の表現を習得し、応用する。
述語論理、形式言語、オートマトンなど、情報に関する理論の考え方、仕組みを習得し、応用する。
正当性理論の考え方、仕組みを習得し、応用する。【応用情報】
AI(人工知能)の考え方、仕組みを習得し、応用する。
コンパイラ理論、プログラム言語論や意味論の考え方、仕組みを習得し、応用する。

【ITパスポート】
情報量の単位を理解する。
情報のデジタル化の基本的な考え方を理解する。

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

情報量の概念、事象の生起確率と情報量との関係を理解する。

(2)符号理論 ITパスポート 基本情報  応用情報

アナログとデジタルの特徴、量子化、標本化、A/D変換などの符号化、符号化の目的、情報伝送における信頼性、効率性、安全性の向上などの効果を理解する。

用語例:通信路符号化、ハフマン符号、データ圧縮

(3)文字の表現 ITパスポート 基本情報 応用情報

代表的な文字コードを理解する。

用語例: ASCIIコード、EUC(Extended UNIX Code)、JISコード、シフトJISコード、Unicode、UCS

(4)述語論理 基本情報  応用情報

述語論理の考え方、演繹推論と帰納推論の違いを理解する。

用語例: 関係データベース

(5)形式言語 基本情報  応用情報

形式言語とは何か、言語の定義、演算、種類、文法を理解する。また、BNF、構文図式などの表記法、正規表現、文脈自由文法を理解する。

用語例: 逆ポーランド表記法

(6)オートマトン 基本情報  応用情報

有限オートマトンの概念、形式言語との関係、チューリング機械との関係、状態遷移表、状態遷移図を理解する。

用語例:プッシュダウンオートマトン

(7)正当性理論 応用情報

プログラムの正当性理論とは何か、部分正当性、全正当性の基本的な考え方、仕組みを理解する。

用語例: 停止問題

(8)計算量 基本情報  応用情報

計算量の理論の考え方を理解する。

用語例:時間計算量、領域計算量、オーダ記号、P(Polynomial)問題、NP(Non-deterministic Polynomial)問題、NP完全問題

(9)AI(Artificial Intelligence:人工知能) 基本情報  応用情報

人工知能の基本的な考え方、仕組みを理解する。

用語例:知識工学、学習理論、機械学習、ニューラルネットワーク、ディープラーニング(深層学習)、エキスパートシステム、解析型問題、合成型問題、知識ベース、推論エンジン

(10)コンパイラ理論 基本情報  応用情報

コンパイラの役割、コンパイルの過程、字句解析、構文解析、最適化の基本的な考え方、仕組みを理解する。

用語例:文脈自由文法、意味解析、コード生成、中間言語、目的プログラム、形式言語、オートマトン

(11)プログラム言語論・意味論 基本情報  応用情報

プログラム言語は、処理対象を表現するために構文と意味があること、各言語で構文と意味がどのように定義されるか、データ構造とアルゴリズムがどのように表現されるか、構造化と抽象化がどのように定義されるかなど、基本的な考え方、仕組みを理解する。

用語例:手続型言語、関数型言語、論理型言語、オブジェクト指向言語

 

情報理論

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

情報量の概念、事象の生起確率と情報量との関係を理解する。

情報理論

情報理論とは、ある事象における確率や統計を元に、情報の量を数学的に定義する理論です。

  • 生起確率: ある事象 E が起こる確率。 P(E)
  • 情報量:  事象が起こる確率を P(E) とする時、事象が起こったことを知らされた時に得られる(選択できる)情報の量。

情報量は以下の式で求める。

例)英数字8文字からなるパスワードを1パターン知らされた時に得られる情報量

まずは、生起確率から考える。
英数字は英小文字26文字+英大文字26文字+英数字10文字からなるので、62文字。
パスワード1文字の場合、とある1パターンの確率は 1 / 62 なので、今回の8文字の場合、P= 1 / 628 となる。

よって、公式に当てはめて情報量を求める。

データの単位

コンピュータで扱えるデータ量の最小単位は、2進数の1桁分に当たる、1ビットです。また、8ビットをまとめて1バイトと換算します。通常、データ量はバイトを単位として表します。

更に大きい単位や小さい単位をわかりやすく表記するために、「メガ」や「ミリ」などの補助単位を組み合わせることがあります。

アナログとデジタル

アナログとは、時間の変化に伴って連続的に変化するデータのことです。「連続的」というのは、ある時点の値と別の時点の値の間に異なる値が無限に連続しているような状態です。

対して、デジタルとは、連続して変化する値を離散数(飛び飛びの値)として扱うデータです。離散数として扱うというのは、特定の時点の値を一定の有効桁数の値に当てはめて扱うということです。結果、値は飛び飛びになり、「ある時点とある時点の間」と言うのは存在しなくなります。また、有効桁数で表現できる範囲外の値も存在しません。例えば、有効桁数を小数第一位とした場合、1.5 や -9.9 という値は存在しますが、0.05 と言った値は存在しません。

アナログデータの特徴として、図(グラフ)で表すと波状となります。気温の変化や音の波、光の波などもアナログデータです。
対して、デジタルデータを図(グラフ)で表すと棒グラフ状になります。

A/D変換

コンピュータ内部ではデータは0か1の2進数で表すため、アナログデータをそのまま扱うことは出来ません。そのため、アナログデータは2進数で表すことの出来るデジタルデータに変換して扱います。

このアナログ→デジタルの変換のことを「A/D変換」と言います。A/D変換は以下のような流れで進められます。

  1.  標本化(サンプリング)
    アナログデータから、ある一定間隔ごとに区切って値を抜き出します。このプロセスを「標本化」といいます。
    この段階で、できるだけ細かく区切ることで元のアナログデータに近くなります。
  2.  量子化
    標本化で抜き出した値は、元がアナログデータなので、小数点以下の細かい数値があるため、これをもっとも近い整数値にします。このプロセスを「量子化」といいます。
  3.  符号化(数値を抜き出す)
    区切って量子化した数値を抜き出して、2進数の値とします。このプロセスを「符号化」といいます。

D/A変換

デジタル化したデータは必要に応じて、再度アナログデータに戻す必要があります。(音声データをスピーカーなどで流すなど)

その際の手順をD/A変換といいます。

デジタル→アナログへの変換手順は、A/D変換のサイト逆の手順で行います。

符号理論

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

アナログとデジタルの特徴、量子化、標本化、A/D変換などの符号化、符号化の目的、情報伝送における信頼性、効率性、安全性の向上などの効果を理解する。

用語例:通信路符号化、ハフマン符号、データ圧縮

符号化理論

符号化とは、データを数値に変換し、情報量として表現することで、コード化ともいいます。

符号化理論とは、情報を符号化し、伝送を行う場合の正確性や高速性に関する理論です。

符号化理論には大きく分けて下記の2つがあります。

  • 情報源符号化
  • 通信路符号化

情報源符号化

元のデータに適した形で符号化を行う方法です。

特性として、圧縮率を高めるほど、データサイズは小さくなりますが、負荷が大きくなります。逆に、圧縮率を低くすれば、データサイズは大きくなりますが、負荷は小さくなります。

通信路符号化

符号化されたデータを伝送する際に、伝送路の帯域や雑音、妨害などによって、正しく届かない可能性もあります。
そこで、既に符号化されたデータに冗長なデータを付け加えて再度符号化します。これを通信路符号化と言います。

例えば、データの信頼性を高めるための誤り検出や誤り訂正機能を付け加えます。

ハフマン符号化

データを圧縮する方法の1つで、出現頻度の高いデータには短いビット列を、頻度の低いデータには長いビット列を割り当てて、全体としてデータの圧縮を行う方法です。

例えば、元データが以下の34バイト(1文字1バイト)からなる文字列だったとします。これをハフマン符号化を用いて圧縮してみます。

元データ:AAJABBDBDBFAAAABAABABAFADAAJLAFBAD

・出現する文字は、A, B, D, F, J, L の6文字なので、この6文字に出現頻度に合わせて各文字にハフマン符号を割り当てます。

各文字の登場頻度ハフマン符号データ長
A:16回01ビット
B:8回102ビット
D:4回1103ビット
F:3回11104ビット
J:2回111105ビット
L:1回1111106ビット

表のように出現頻度の高い文字に少ないビットを割り当てるため、ビット列の容量を減らすことが出来ます。
表のハフマン記号に基づいて元データを変換すると、以下のようなビットの並びになります。(便宜上、元の文字の区切りにスペースを入れていますが、実際には空白はありません)

0 0 11110 0 10 10 110 10 110 10 1110 0 0 0 0 10 0 0 10 0 10 0 1110 0 110 0 0 11110 111110 0 1110 10 0 110 

上記のビットの並びで、72ビットになります。元データの34バイトは272ビットになりますので、おおよそ4分の1のデータ量に圧縮できたことになります。

このように元のデータ量を縮小することを「データ圧縮」と呼びます。
その手法には大きく分けると2種類あり、圧縮後のデータから元データが復元できる「可逆圧縮」と、復元不可能な「不可逆圧縮」があります。

 

文字の表現

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

代表的な文字コードを理解する。

用語例: ASCIIコード、EUC(Extended UNIX Code)、JISコード、シフトJISコード、Unicode、UCS

文字コード

アルファベットやかな、漢字といった文字データを扱うために、コンピュータ内部ではそれぞれの文字に、0と1からなるコード番号を割り当てています。これを文字コードといいます。

文字コードには多くの体系があり、体系によって扱える文字種やコードの長さ(ビット数)が異なります。

ASCIIANSI(アメリカ規格協会)が定めた7ビットコード。
英字と数字、記号のみに対応し漢字やかなの規定はない。
Unicode全世界の文字に統一的に対応するための国際規格の標準コード。2~4バイトコード。
文字コードセットとしてUCSが、エンコード方式としてUTFがそれぞれ定められている。
EUCExtended Unix Code(拡張UNIXコード)の略。UNIX上で2バイト文字の漢字・かなを表現できる。
JISコードJIS(日本工業規格)が定めたコード。英数字と半角カナに対応する7又は8ビットのコード体系と、漢字などに対応する2バイト体系がある。
シフトJISJISコードをシフトさせて、ASCIIコードと混在できるようにしたもの。さらに機種ごとの特殊記号などの拡張コードが加えられている。
EBCDICIBMなどの汎用機で用いられているコード。英数字用の文字コード。

日本語の文字コード

ASCIIなどの文字コードでは、基本的に1バイトで1文字を表しますが、1バイトでは最大でも256文字までしか規定することが出来ません。日本語の場合、ひらがな、カタカナ、漢字と種類が多く、特に漢字は「常用漢字」だけでも2,000字近くあり、1バイトで規定することが出来ません。

そこで、1文字2バイトとすることで、表現できる文字数を増やして対応しているのが日本語用の文字コードです。

日本語用の文字コードとしてはUnicode、JISコード、シフトJIS、EUCの4種類が広く用いられています。

文字化け

データを表示した時に、本来の文字列とは異なるでたらめな文字や記号が表示されてしまう現象を「文字化け」といいます。

これは、間違った文字コードが使用された時に起こる現象で、他のシステムからデータを移行・転送した場合にしばしば起こります。また、本来の文字コード体系に含まれていない、ユーザー登録した外字や機種依存文字を含む場合にも発生することがあります。

文字化けを防ぐには、事前に双方で使用している文字コードを確認する必要があります。

述語論理

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

述語論理の考え方、演繹推論と帰納推論の違いを理解する。

用語例: 関係データベース

述語論理

述語論理とは、命題の内部の構造を主語と述語の二つの構成要素に分解し、その中の術後部分を扱う理論です。

命題

文章や式で表された事象について、それが真であるか偽であるかが明確に決まるもの。

命題論理

審議の解っている既存の命題をつなげて新しい命題を作ったり、命題を否定したりすること。

推論

ある命題から別の命題を導くこと。
元の命題を「前提」または「過程」といい、導かれた命題のことを結論といいます。
述語論理における推論には、「演繹推論」と「帰納推論」の二種類があります。

演繹推論

複数の前提条件から結論を導く推論方法。代表的なものに、一般的な大前提と個別の小前提から結論を導く三段論法があります。

三段論法の例
大前提:「塩水は塩辛い」
小前提:「海の水は塩水である」
結論 :「海の水は塩辛い」

帰納推論

与えられた事例から一般的法則を導き出す推論方法で、予測や仮説を導くのにも使う推論方法です。

例「海の水は塩辛い」
事例:沖縄の海の水は塩辛い
   三陸沖の海の水は塩辛い
   ハワイの海の水は塩辛い
推論:海の水は塩辛い

 

述語論理や命題、推論といったキーワードは『論理学』の中で用いられる用語です。論理学とは、論理を成り立たせる論証の後世やその体型を研究する学問です。
ここでいう論理とは、思考の法則、思考のつながり、推理の仕方や論証のつながり方のことを言います。

よく言われる『論理的に話す、書く』ということの意味は、つながりを明確に、論証を的確に話し、書く、ということです。

形式言語

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

形式言語とは何か、言語の定義、演算、種類、文法を理解する。また、BNF、構文図式などの表記法、正規表現、文脈自由文法を理解する。

用語例: 逆ポーランド表記法

自然言語と形式言語

日本語や英語などの言語は人間が暮らしていく中で自然に発生したため、必ずしも厳密な文法に従っているとは限りません。こういった言語を自然言語といいます。

それに対し、特定の目的のために作られ、厳格な文法に則った言語を形式言語といいます。
コンピュータに指示を与えるためには、プログラミング言語と呼ばれる言語を用いたプログラムを作成します。
このプログラミング言語も形式言語の一つです。

文脈自由文法

言語に関するルールを定めたものが『文法』で、制限の強さの異なる4つの分類があります。ここでいう文法は文の形式を定めるだけで意味についての解釈は行いません。

  • 句構造文法
  • 文脈依存文法
  • 文脈自由文法
  • 正規文法

句構造文法が制限が最も弱く、正規文法が最も制限が強い文法です。形式言語では、文脈自由文法が用いられます。

文脈自由文法は、プログラミング言語を正確に記述するための厳密な形式を定めることが出来る文法です。

例えば、文脈自由文法で『直角とは90度である』と定義する場合、定義が必要なもの(この場合は「直角」)を「非終端記号」といい、それ以上他のものに置き換えることが出来ずに定義が必要でないもの(この場合は「90度」)を「終端記号」といいます。

BNF記法(バッカス・ナウア記法)

BNF(Backus-Naur Form)は、文脈自由文法の文法自体を定義するための記法で、一般的には、バッカス・ナウア記法と呼びます。
プログラミング言語 algol60の文法定義に初めて用いられた記法です。

記号意味
<変数名><非終端記号>(=メタ変数名)
::=左辺が右辺に分解できることを表す。(○○とは▲▲であるの部分を表す)
「または」を表す

メタ変数名

非終端記号のことを「メタ変数名」と呼ぶこともあります。「メタ」というキーワードは情報処理の分野ではよくつかわれるキーワードで、「メタ情報」「メタデータ」という使われ方をします。意味としては、「情報のための情報」「そのデータが持つ、データ自身についての抽象度の高い付加的データ」という意味でつかわれます。

現在では、ヴィルド博士がBNFを拡張して作成したEBNF(拡張バッカス・ナウア記法)も一般的です。
BNFとEBNFの相違は、EBNFでは繰り返し部分を中かっこで囲んだり、終端記号をダブルクォーテーションやシングルクォーテーションで囲んだり、といった違いがあります。

例:

  • <a> ::= <b>  aはbである。
  • <a> ::= 1|2  aは1または2である。

例2(数値の表現をBNF記法で表した例)

  • <数値>::= <数字列>|<符号><数字列>|<数字列>.<数字列>
  • <数字列>::=<数字>|<数字列><数字>
  • <数字>::=0|1|2|3|4|5|6|7|8|9
  • <符号>::= +|-

この例の<数字列>の定義のように、自身の定義の中で自らを定義するような書き方が、情報処理の分野ではよく用いられます。このような定義の仕方を「再帰(的)」と呼びます。

構文図式

構文図式は、BNFで定義した文法の構造、「構文」を視覚的に表現する方法の一つです。

以下に、BNFのと構文図式の例を示します。

<算術式>のBNF表記

  • <算術式>::=<項>|<加減演算子><項>
  • <加減演算子>::= +|-

なお、点線で囲っている部分は0回以上の繰り返しを表します。

正規表現

正規表現とは、いくつかの文字をパターン化して一つの形式で表現する表記法です。BNFを記述するときにも使われます。

正規表現を用いることで、個別の文字列を指定しなくても、また表記にゆれがあっても検索することが可能です。

例えば、以下のようなケースで正規表現を用いて、文字列を検索します。

  • 数値のみで構成されている任意の文字列を検索したい
  • 「ユーザ」と「ユーザー」といった、調音の有無を無視して検索したい

例)メールアドレスの表記ルールを正規表現で表す

正規表現: [\w\d_-]+@[\w\d_-]+\.[\w\d\._-]+

正規表現で用いられる記号の例

  • \w 半角英字(a~z、A~Z)
  • \d 半角数字(0~9)
  • \. 半角ピリオド
  • _ 半角アンダースコア
  • - 半角ハイフン
  • [\w\d_-] []内のいずれか1文字
  • + 直前の正規表現の1回以上の繰り返し
  • . 任意の1文字
  • * 直前の正規表現の0回以上の繰り返し

逆ポーランド記法

演算方法の表記法の一つに「逆ポーランド記法(Reverse Polish Notation : RPN)」があります。
数式を記述する際、演算子を演算対象の後ろに置く方法です。

逆ポーランド記法はコンピュータと相性の良い数式の書き方です。なぜなら、コンピュータは人間と違って与えられた情報を俯瞰的に眺めることは苦手であり、基本的には「右から来た情報を左に受け流す」というのがコンピュータの情報の扱い方なので、逆ポーランド記法のように、情報を流れてきた順序に沿って処理できる方法と相性が良いからです。
また、コンピュータが持つ「スタック」というデータの管理機構で数式を処理しやすい、という面もあります。

スタックは「積み重ねる」という意味で、最後に入れたものを最初に取り出すデータ構造です。

実際に、逆ポーランド記法で書かれた、「135×82÷++」という計算式を、スタックを用いて計算してみましょう。
基本的な動作は、以下の2つです。

  • 数値が来たら、スタックに投入する。
  • + や – などの演算子が来たら、スタックから数値を2個取り出して計算し、その結果をスタックに投入する。

 

正当性理論

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

プログラムの正当性理論とは何か、部分正当性、全正当性の基本的な考え方、仕組みを理解する。

用語例: 停止問題

 

プログラムの正当性

プログラム開発においては、不具合(=バグ)の発生はなかなか避けられないものです。このバグの除去のために作成するプログラムに対して、テストや検証を行いますが、「検証」を行うことで、プログラムの正当性を証明することができます。

ここでいう「プログラムの正当性」とは、「入力条件を満たしたプログラムを実行すると、そのプログラムは確実に停止するとともに出力条件を満たした結果が得られる」ということを指します。完全正当性とも言います。

部分正当性

正当性のうち、「入力条件を満たしたプログラムを実行すると、そのプログラムは出力条件を満たした結果が得られる」ことを部分正当性といいます。

停止性

正当性のうち、「そのプログラムは確実に停止する」ことを停止性といいます。

プログラムの検証において、停止性を証明するためには、特にプログラム内の繰り返し(ループ)部分に着目します。繰り返しの条件が不適切な場合、プログラムが永久に終了しない(=無限ループ)状態となってしまい、停止性を満たすことができません。

停止性問題

計算可能性理論において停止(性)問題(ていしせいもんだい・ていしもんだい、halting problem)は、あるチューリング機械(≒コンピュータプログラムアルゴリズム)が、そのテープのある初期状態(≒入力)に対し、有限時間で停止するか、という問題。アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。すなわち、そのようなチューリング機械の存在を仮定すると「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」ような別のチューリング機械が構成でき、矛盾となる。

Wikipediaから引用

 

オートマトン

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

有限オートマトンの概念、形式言語との関係、チューリング機械との関係、状態遷移表、状態遷移図を理解する。

用語例:プッシュダウンオートマトン

オートマトン

プログラミング言語などの形式言語で記述された分を解釈するための仮想的な機械概念をオートマトンといいます。
コンピュータそのものを数学的な観点からモデル化し、アルゴリズム(=問題解決のための処理手順)を定型化したものです。

元々は「自動人形」を意味している言葉で、現代のコンピュータ技術の基礎原理の一つとして、様々な場面で応用されています。

オートマトンのモデルでは、コンピュータを外部からの入力に応じて内部の状態が変化し外部に出力を行うものとして扱います。

なお、オートマトンとコラム「コンピュータの歴史」で紹介した「チューリング機械」というのは非常に似たものとなっていて、オートマトンの定義を拡張したものがチューリング機械となっています。

チューリング機械は無限の記憶領域を持つとされているが、0と1という記号の並びを入力として、順次処理を行い、後戻りしない、という共通点があります。

有限オートマトン

オートマトンの中で有限個の状態を扱うものを、特に「有限オートマトン」と呼びます。有限オートマトンでは、開始時点の状態(=初期状態)が決まっています。そして、入力によって他の状態へ変化(=遷移)します。最後に成功して終了する状態(=受容状態)のどれかに遷移すれば終了とします。

以下に有限オートマトンの特徴をまとめました。

  • 一つの初期状態を取る。
  • 有限な記憶領域を持つ。
  • 記号列を入力とし、一度に1つずつ読み込む。
  • 後戻りしない。
  • 入力に応じて、他の状態の遷移する。
  • 特定の状態のどれかで終わっていれば成功。受容状態となる。

例えば、「ノートパソコンの電源投入状態」を有限オートマトンで考えてみましょう。
このノートパソコンは、閉じると休止状態となり、開くと休止状態から復帰するものとします。

  • 初期状態は、電源が入っていない「停止」状態です。
  • 「電源スイッチON」という入力によって、状態は「動作」に遷移します。
  • 「動作」状態でパソコンを閉じると「休止」に遷移します。
  • 「休止」状態でパソコンを開くと「動作」に遷移します。
  • 「シャットダウン」という入力によって、「停止」に遷移し、終了します。

他に身近な例では、有限オートマトンの考え方で表現できるものとしては、「自動販売機」があります。

状態遷移表と状態遷移図

オートマトンの状態を表すものには、「状態遷移表」と「状態遷移図」があります。

どの状態の時に、どの入力があると、どの状態に変化(遷移)するのかを示す規則を、表にしたものが状態遷移表、図にしたものが状態遷移図です。

先述のノートパソコンの例を元に、状態遷移表と状態遷移図を確認してみましょう。

まずは、状態遷移表を示します。

縦が遷移前の状態、横が入力、表の中は遷移後の状態を表しています。なお、標柱の横棒は遷移がないことを示します。

次に状態遷移図を見てみましょう。

状態を楕円形で、入力を矢印によって、状態の遷移を視覚的に分かりやすいように表現しています。

プッシュダウンオートマトン

有限オートマトンの「状態」と「入力」に加えて、無限の容量の「スタック」を持っているのが、プッシュダウンオートマトンと呼ばれるものです。

スタックを持つことに加え、以下の点で有限オートマトンとは異なっています。

  • スタックのトップ(=最上位の要素)でなすべき状態遷移を判断する。
  • 遷移実行の一部として、スタック操作を行うことが出来る。

 

計算量

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

計算量の理論の考え方を理解する。

用語例:時間計算量、領域計算量、オーダ記号、P(Polynomial)問題、NP(Non-deterministic Polynomial)問題、NP完全問題

計算量

ある問題を解く場合に、問題を解く手順(=アルゴリズム)は複数存在します。例えば、以下のような単純な掛け算を取ってみても、複数の計算方法があります。
例)3×1977

  • 3を1977回足す
  • 1977を3回足す

この例の場合、明らかに1977を3回足すほうが計算の回数が少なく、優れた解法といえます。

この例のように、問題を解くためのアルゴリズムは一つとは限らず、いくつかあるアルゴリズムから最良のものを選ぶためには、アルゴリズムを定量的に評価する指標が必要となります。この指標が「計算量」と言われるものです。
アルゴリズムに基づいて処理するデータ量によって、プログラムの実行時間がどのように変化するかを表し、アルゴリズムの複雑さをはかることが出来ます。
時間計算量はあるアルゴリズム手順(=処理手順)の数と繰り返し回数の最大数で表すことが出来ます。

解く問題の種類によっては、計算量が一定でない場合があります。例えば検索処理です。

検索処理では場合によっては、処理開始直後に見つけられることもあれば、最後の最後で見つかることもあります。このような一定でない計算量を表現するために、最大計算量と平均計算量という考え方もあります。それぞれ、計算量の最大値と平均値を示すものです。
計算量の代表値としては、平均計算量のほうが適切ですが、平均計算量は算出が難しい場合があり、最大計算量で評価することも多くあります。

時間計算量の他に、「領域計算量」も評価指標として使うことがあります。この場合は使用するメモリの容量を指標とし、より使用メモリの少ないアルゴリズムを良いアルゴリズムとしてみなすものです。
但し、現在はメモリが大容量化、かつ低価格化しているので、時間計算量がより優先される傾向にあります。

オーダ記法

良いアルゴリズムを考える場合に、「実行速度が早い」という点は大変重要ですが、実際の速度というのはコンピュータの性能によって異なってきます。
そこで、実行にかかる時間の目安を「時間計算量」として計算して評価します。その際に時間計算量は「O(オーダ)」という記号を使って表します。この表記法を「オーダ記法」といいます。

AI(Artificial Intelligence:人工知能)

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

人工知能の基本的な考え方、仕組みを理解する。

用語例:知識工学、学習理論、機械学習、ニューラルネットワーク、ディープラーニング(深層学習)、エキスパートシステム、解析型問題、合成型問題、知識ベース、推論エンジン

人工知能

人間の知的活動をコンピュータに行わせるための技術を「人工知能」と呼びます。英語表記の「Artificial Intelligence」を略してAI(エーアイ)とも呼ばれます。

人工知能は基盤となる技術によって、三種類に分類されます。

知識ベース型

「知識ベース」とは、専門家の知識や経験をデータベース化したものです。知識ベース型人工知能は、この知識ベースを活用して問題の解決方法を見つけ出すものです。

代表的な知識ベース型人工知能には、エキスパートシステムがあります。

エキスパートシステムとは、知識ベースとあわせて、推論エンジンを使います。推論エンジンは状況に合わせて推論を行なっていく機能を持つもので、知識ベースと推論エンジンを組み合わせることでエキスパート(=人間の専門家)と同じような応答をするものです。

ファジィ型

「ファジィ」とは「ぼやけた」という意味です。ファジィ型人口では、真と偽の教会が「ぼやけた」もの、つまり曖昧な値を扱います。
例えば「安全」か「危険」かという二者択一だけではなく、「やや危険」といった中間的な状況も扱い、最適な答えを導き出していきます。

「安全」や「危険」であれば、安全度もしくは危険度と言うかたちで数値化することができれば、人工知能を用いなくても答えを導くことが出来ますが、ファジィ型人工知能を使うことで負荷の大きな数値計算をすることなく、効率的に判断を行うことが出来ます。

学習型

学習型人工知能とは、入力されたデータに応じて、答えを導く論理構造を変化させていくものです。

代表的な学習型人工知能にはニューロコンピュータシステムがあります。
ニューロコンピュータコンピュータシステムは、人間の脳の構造をモデル化した、ニューロネットワークモデルに基づくものです。

身近な例としては、迷惑メールフィルタなどに用いられている「機械学習」や、囲碁や将棋のソフトなどで注目を浴びた「ディープラーニング」などが上げられる。

 

コンパイラ理論

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

コンパイラの役割、コンパイルの過程、字句解析、構文解析、最適化の基本的な考え方、仕組みを理解する。

用語例:文脈自由文法、意味解析、コード生成、中間言語、目的プログラム、形式言語、オートマトン

言語プロセッサ

コンピュータが直接実行できるプログラムは「機械語」のプログラムです。
機械語のプログラムは、人間がみると単なる数値(2進数)の並びで、人間が作成したり呼んだりするのには不向きです。

そのため、人間がプログラムを扱いやすくするために、プログラミング言語が存在します。プログラミング言語で書かれたプログラムのことを「ソースコード」あるいは「原始プログラム」と呼びます。

「ソースコード」はそのままではコンピュータ上で実行することは出来ません。実行可能な機械語のプログラムに変換することが必要になります。この変換処理を行うのが「言語プロセッサ」と呼ばれるものです。

言語プロセッサにはいくつかの種類があります。

  • アセンブラ: 機械語と1対1に対応したアセンブラ言語を機械語に変換するプログラム
  • コンパイラ: ソースコードを一括して機械語に変換するプログラム
  • インタプリタ: ソースコードを機械語に変換しながら実行するプログラム
  • ジェネレータ: 必要な条件をパラメータで支持することで、目的に応じたプログラムを自動生成するプログラム

コンパイラ理論

コンパイラで実行可能なプログラムを生成する場合、直接実行可能なプログラムを生成するわけではありません。これは、大規模なプログラムになると、一つのプログラムのソースコードを複数に分けて扱う必要が出てくるからです。

実行可能なプログラムを生成する第一段階は、ソースコードを変換して「オブジェクトコード」または「目的プログラム」を生成することです。
この「オブジェクトコード」はソースコード単位で作られます。

第二段階として、オブジェクトコードをつなげて実行可能なプログラムを生成します。
この段階では、ライブラリと呼ばれるオブジェクトコードの集合体が使われることもあります。
ライブラリは多くのプログラムで使われるであろう、ファイル入出力などの機能をあらかじめオブジェクトコードとして用意しておいたものです。

なお、第二段階で使われるプログラムのことを「リンカ」または「リンケージエディタ」とも呼びます。

コンパイラの処理手順

コンパイラがソースコードからオブジェクトコードを生成する時、いくつかの段階を経て処理が行われます。

典型的な流れは、字句解析→構文解析→意味解析→最適化→コード生成、となっています。

  1. 字句解析: ソースコードを最小の単位の語句(トークン)に分解
  2. 構文解析: トークンの並びを、定められた文法に従って解析
  3. 意味解析: トークンの意味を考慮した解析
  4. 最適化&コード生成: プログラムの高速化、サイズの縮小

 

プログラム言語論・意味論

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

プログラム言語は、処理対象を表現するために構文と意味があること、各言語で構文と意味がどのように定義されるか、データ構造とアルゴリズムがどのように表現されるか、構造化と抽象化がどのように定義されるかなど、基本的な考え方、仕組みを理解する。

用語例:手続型言語、関数型言語、論理型言語、オブジェクト指向言語

プログラミング言語の種類

プログラミング言語には多くの種類があり、処理の手順などによって分類することが出来ます。

代表的なプログラミング言語の分類

言語の種類概要代表的な言語
低水準言語機械語コンピュータが直接実行できる言語
アセンブラ言語機械語と1対1に対応した命令語からなる言語CASLⅡ
高水準言語手続型言語処理内容を記述した命令を、順を追って実行する言語FORTRAN
COBOL
C言語
BASIC
非手続型言語関数型言語関数と呼ばれる式を組合せた後世の言語LISP
論理型言語論理式で記述していく言語Prolog
オブジェクト指向言語すべての事象をオブジェクト(モノ)として扱う言語Java
C++
Objective-C

 

通信に関する理論

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

【基本情報・応用情報】
情報を伝送するための技術について、代表的な方式の考え方、仕組みを習得し、応用する。

(1)伝送路 基本情報 応用情報

伝送路上でデータがどのように伝送されるか、伝送路の考え方、仕組みを理解する。

用語例:単方向、半二重、全二重、2線、4線、直列、並列

(2)変復調方式 基本情報  応用情報

デジタルデータをアナログ伝送路を介して送るために必要な仕組みである変調、それを受信側で元に戻す処理である復調の代表的な方式の考え方、仕組みを理解する。

用語例:AM(Amplitude Modulation:振幅変調)、FM(Frequency Modulation:周波数変調)、PM(Phase Modulation:位相変調)、PCM(Pulse Code Modulation:パルス符号変調)、QAM(Quadrature Amplitude Modulation:直交振幅変調)PWM(Pulse Width Modulation:パルス幅変調)、モデム

(3)多重化方式 基本情報 応用情報

一つの伝送路を複数の通信で同時に使用する多重化について、代表的な方式の考え方、仕組みを理解する。

用語例: FDM(Frequency Division Multiplexing:周波数分割多重)、TDM(Time Division Multiplexing:時分割多重)、CDM(Code Division Multiplexing:符号分割多重)、WDM(Wavelength Division Multiplexing:波長分割多重)

(4)誤り検出・訂正 基本情報  応用情報

偶数パリティ、奇数パリティなど、信頼性を高める技術の考え方、仕組みを理解する。

用語例: CRC、ハミング符号、パリティチェック、ECC、チェックサム

(5)信号同期方式 基本情報  応用情報

送信側と受信側で送受信のタイミングを合わせる信号同期制御について、代表的な方式の考え方、仕組みを理解する。

用語例: ビット同期、キャラクタ同期、フラグ同期、調歩同期、スタートビット、ストップビット、SYN同期、フレーム同期

(6)暗号化 応用情報

暗号化に関連する技術の考え方、仕組みを理解する。

用語例:符号理論、公開鍵、秘密鍵、PKI(Public Key Infrastructure:公開鍵基盤)

(7)データ圧縮 応用情報

データ圧縮に関連する技術の考え方、仕組みを理解する。

用語例: 符号理論、ランレングス、ハフマン符号

 

伝送路と通信方式

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

伝送路上でデータがどのように伝送されるか、伝送路の考え方、仕組みを理解する。

用語例:単方向、半二重、全二重、2線、4線、直列、並列

伝送と伝送路

  • 伝送:機器の間でデータをやり取りすること
  • 伝送路:データをやり取りするための経路

搬送波

何らかの情報を載せて、有線・無線・波動(光や音波)で送るための信号のこと。キャリア、キャリア波ともいいます。

直流方式と交流方式

デジタルデータを伝送する方式には、直流方式と交流伝送方式があります。  

  • 直流方式:デジタル信号に対応した直流信号をそのまま伝送する方式。ベースバンド方式。
  • 交流方式:アナログ伝送路にデジタルデータをアナログ信号に変換して伝送する方式。帯域伝送方式。

シリアル伝送とパラレル伝送

シリアルの場合は、1本の線で1ビットずつ順番に信号を送ります。

パラレルの場合は、複数の線で複数のビットを同時に送ります。

デジタル信号の送り方

伝送は信号の方向による分類の他に、信号の数による分類もあります。(前述のシリアル伝送とパラレル伝送)

伝送性能は、一般的には同時に複数の信号を送れる並列方式が優れているとされてきましたが、伝送路が長かったり信号の周波数が高くなったりすると、複数の信号のタイミングを合わせることが難しくなります。そのため、長距離の通信や高周波数での伝送には、シリアル伝送方式が使われることが多くなっています。

とくに、近年はシリアル伝送方式の性能向上が著しいため、制御の容易なシリアル伝送方式が用いられることが多くなっています。(USBが代表的)

単方向通信と双方向通信

伝送における信号が流れる方向は、単方向通信と双方向通信に分けられます。

単方向通信は、一方向にしか信号が流れない通信で、例えばGPSを使った自動車とGPS衛星の間は単方向の通信となっており、この場合、自動車から衛星へは、電波は送られません。

このため、単方向通信では、送信元は、データが相手に届いたことを確認したり、データの破損を検出することが出来ません。その為、コンピュータ間の通信では、ほとんど使われていません。

これに対して双方向通信は、相互に信号をやり取りできる通信であり、単方向通信とは異なり送信元は、送信先からデータが届いたり、データの破損があった場合などに、送信先からの通知を受け取ることが可能になっています。

双方向通信の際の通信の方法

双方向通信には、伝送路の使い方の違いから、半二重通信と全二重通信に分けられます。

半二重通信は一本の伝送路で、単方向のみへの通信が可能な方式です。データを二者間でやり取りする場合、データの送信・受信を同時に行うことは出来ません。

全二重通信は同時に双方向の通信が可能な方式で、データの送信・受信を同時に行うことが出来ます。半二重・全二重の違いがわかり易い例として、鉄道の単線と複線の違いがあります。

鉄道の単線では、駅などで対向列車を待ち、双方向で線路を使う時間帯を分けることで双方向の行き来を可能にしています。

但し、伝送路の場合は、鉄道の線路とは異なり、時間をずらす以外にも1本の伝送路を使い分ける方法があります。

時間で分ける方式を『時分割複信(TDD:Time Division Duplex)』と呼び、これは鉄道と同様に、双方向で伝送路を使う時間を分けて、通信を行う方法で半二重通信で用いられます。

別の方式として『周波数複信(FDD:Frequency Division Duplex)』という方法があり、これは1本の伝送路を、周波数帯を使い分けることで、あたかも複数の伝送路があるかのように使う方式で、全二重通信に用いられます。

伝送速度と信号速度

  • 伝送速度(転送速度)・・・伝送路を通ってデータが送られる速度
  • 信号速度(変調速度)・・・変調が行われる速度(単位:baud[ボー])
  • 伝送速度[bps]・・・一回の変調のビット数×信号速度。

 

変復調方式

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

デジタルデータをアナログ伝送路を介して送るために必要な仕組みである変調、それを受信側で元に戻す処理である復調の代表的な方式の考え方、仕組みを理解する。

用語例:AM(Amplitude Modulation:振幅変調)、FM(Frequency Modulation:周波数変調)、PM(Phase Modulation:位相変調)、PCM(Pulse Code Modulation:パルス符号変調)、QAM(Quadrature Amplitude Modulation:直交振幅変調)PWM(Pulse Width Modulation:パルス幅変調)、モデム

変調と復調

コンピュータ内部の信号は、そのままでは伝送路に流せない場合があります。

そのような場合には、伝送路に適した信号に変換する必要があるが、この際の変換を『変調』と呼びます。(この変調された信号を乗せる信号を搬送波という)

信号を変調した場合には、伝送路の信号をコンピュータ内部の信号に戻す変換も行う必要があり、この場合の変換を『復調』と呼びます。

コンピュータ内部の信号はデジタル方式のため、アナログ伝送路を使用する場合は、必ず変調と復調の作業が必要になります。

変復調方式

変調・復調の方式には、下記のものがある。

名称特徴
振幅変調方式
(AM:Amplitude Modulation)
ビットが0の時は振幅なし、1の時は振幅ありに対応させる方式
周波数変調方式
(FM:Frequency Modulation)
ビットの0と1に対応させて、周波数を変化させる方式。
位相変調方式
(PM:Phase Modulation)
位相(電波の進み具合)を変化させる方式
パルス符号変調方式
(PCM:Pulse Code Modulation)
アナログ信号を一定間隔でサンプリングして整数値化し、その整数を二進数に置き換える方式
直角位相振幅変調方式
(QAM:Quadrature Amplitude Modulation)
振幅と位相の両方の要素を変化させることで複数の情報を一度に伝達できる変調方式。
パルス幅変調
(PWM:Pulse Width Modulation)
パルス波のデューティ比を変化させて変調すること。
(デューティー比:パルス幅をパルス期間(周期)で割ったもの)

多重化方式

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

一つの伝送路を複数の通信で同時に使用する多重化について、代表的な方式の考え方、仕組みを理解する。

用語例: FDM(Frequency Division Multiplexing:周波数分割多重)、TDM(Time Division Multiplexing:時分割多重)、CDM(Code Division Multiplexing:符号分割多重)、WDM(Wavelength Division Multiplexing:波長分割多重)

多重化方式

大容量の伝送路がある場合、これを特定の通信が占有することは、効率が良い使い方とはいえません。
そこで、大容量の伝送路を複数の通信で共同利用できれば、効率的に伝送路を使うことが出来ます。

このように、一本の伝送路を複数の通信が共同で利用することを「多重化」といいます。
多重化には仕組みの違いにより、いくつかの方式があります。

周波数分割多重方式(FDM:Frequency Division Multiplexing)

アナログ伝送路で多く採用されている方式で、信号が正弦波の場合、周波数が異なる複数の信号を混合しても分離できる性質があるので、この性質を利用して、上りと下りの信号で異なる周波数を使います。

また、周波数を等間隔に分割し、複数の回線を回線ごとに違う周波数を利用するという方法も取られます。(ADSLはこの方式)

時分割多重方式(TDM:Time Division Multiplexing)

デジタル伝送路で多く採用されている方式で、複数のデジタル信号にそれぞれ時間を順番に割り当てて、一本の伝送路で送る方式です。

伝送路は短い時間でみると、上り専用、下り専用になっています。

符号分割多重方式(CDM:Code Division Multiplexing)

デジタル伝送路で採用されている方式で、デジタル信号を符号によって「色分け」し、区別するようにする方式です。

波長分割多重方式(WDM:Wavelength Division Multiplexing)

光通信技術の一つで、複数の回線ごとに異なる光の波長を割り当てて、一本の伝送路にまとめて伝送する方式。

 

信号同期方式

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

送信側と受信側で送受信のタイミングを合わせる信号同期制御について、代表的な方式の考え方、仕組みを理解する。

用語例: ビット同期、キャラクタ同期、フラグ同期、調歩同期、スタートビット、ストップビット、SYN同期、フレーム同期

信号同期方式

通信においては、送信側と受信側でタイミングを合わせることが必要になります。
タイミングを合わせなければ、受信側はデータの始まりと終わりを知ることも出来ません。この、通信においてタイミングを合わせることを「同期」といいます。

一般的な伝送路の同期方式は、ブロック同期方式とビット同期方式に分類されます。

ビット同期方式は電話網などで使われる同期方式です。

通常の通信では、ブロック同期方式が使われます。

ブロック同期方式の代表的なものに、調歩同期方式、キャラクタ同期方式、フレーム同期方式があります。

調歩同期方式

調歩同期方式は、文字符号の前後に同期のためのビットを付加する方式です。

1つの文字は8ビットですが、この8ビットの前に開始と終了を示す特別なビットを付加します。
開始を示すビットを「スタートビット」、終了を示すビットを「ストップビット」と呼びます。通常、スタートビットは0、ストップビットは1、データが無い場合は1を取ります。

受信側は、スタートビットとストップビットによって、文字の始まりと終わりの位置を知ることが出来ます。

文字毎にスタートビットとストップビットが付き、伝送効率が悪いため、低速な通信で利用されます。

キャラクタ同期方式(SYN同期方式)

キャラクタ同期方式は、同期用の制御文字を使い、キャラクタ(メッセージ)単位で同期をとる方式です。同期用の制御文字は「SYN」と呼ばれるので、SYN同期方式とも呼ばれます。

キャラクタ同期方式には、制御文字の使い方が異なる複数の方式があります。

一つは、データ部分を識別するために、データの先頭と終端にそれぞれ別の制御文字を付加する方式です。

もう一つは、データ部分を識別する制御文字を使わずに、代わりに先頭に「SYN」を2個入れる方式です。

キャラクタ同期方式が利用できるのは、8ビット単位の文字情報を伝送する場合に限られます。これは不定長や8ビットではない長さのデータの場合、「SYN」と同じビットの並びが出現する可能性があるためです。

メッセージのブロックごとにビット列を付加するため、中速な通信で利用されます。

フレーム同期方式(フラグ同期方式)

フレーム同期方式は、データのブロックの区切りに特定のビットの並びを使う方式です。例えば、フレーム同期を行うある通信方式では、2進数の「01111110」という並びを使っています。
この特定のビットの並びを「フラグパターン」と呼びます。そのため、フラグ同期方式とも呼ばれます。

キャラクタ同期方式が8ビット単位の文字情報を前提としているのに対し、フラグ同期方式は任意の長さのビットデータを扱えるので、文字情報以外の画像や音声などのデータ伝送でも利用できます。

フラグ同期方式は、送信するデータが無い場合でも常にフラグを送り続けており、データが発生した際にフラグの間にデータを挿入します。
受信側はフラグ以外のビット列が現れたときに、次のフラグまでのビット列をひとまとまりのデータとしてみなします。

データのまとまり毎にフラグと呼ばれるビット列を付け加えるため、キャラクタ同期方式よりも高速な通信で利用されます。

誤り検出・訂正

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

偶数パリティ、奇数パリティなど、信頼性を高める技術の考え方、仕組みを理解する。

用語例: CRC、ハミング符号、パリティチェック、ECC、チェックサム

誤り検出・訂正

伝送路城の信号は、ノイズやタイミングのズレなどの影響で、データを正しく伝送できないことがあります。これを「伝送誤り」や「伝送エラー」といいます。伝送誤りがあると、送られたデータは破損してしまいます。正しくデータを送るためには、伝送誤りを検出したり、訂正する必要があります。これらの伝送誤りを検出したり、訂正したりすることを「誤り制御」と呼びます。

誤り制御は「誤り検出」と「誤り訂正」に大別されます。

誤り検出

誤り検出は伝送誤りの検出を行うことです。送信側は誤り検出のための情報を付加して送信し、受信側は誤り検出のための情報を使って、受信したデータをチェックします。

誤りが検出されると、受信したデータを破棄したり、送信側に再送信を要求したりします。

代表的な誤り検出の方式は「パリティチェック」「チェックサム」「CRC」などがあります。
方式により、付加される誤り検出のための情報のサイズや誤り検出の精度が異なってきます。

誤り訂正

誤り訂正は伝送誤りの訂正を行うことです。送信側は誤り訂正のための情報を付加して送信し、受信側は誤り訂正のための情報を使って誤りを検出、必要があれば正しいデータを復元します。

そのため、誤り検出と異なり、送信側に再送信を要求する必要はありません。但し、誤り訂正のための情報は、誤り検出のための情報より大きくなるため、その分通信の効率は低下します。

パリティチェック

パリティとは、値が1のビットの個数が偶数か奇数かをチェックする方式です。送信するビット列に誤り検出用のビット(パリティビット、冗長ビット)を付け加える検出方式です。

偶数パリティと奇数パリティの2つの方式に分かれており、偶数パリティの場合、付加すると値が1のビットが偶数個になり、奇数パリティの場合は値が1のビットが奇数個になります。

ただし、パリティチェックでは誤り検出は出来ても、どのビットに誤りがあるか判断できないため、誤り訂正は出来ません。

パリティチェックはどの方向にパリティビットを付け加えるかによって、垂直パリティと水平パリティの2種に分けられ、さらに両者を組合せた垂直水平パリティという方式もあります。

垂直パリティ

垂直パリティは送信するデータのビット列のまとまり毎(文字単位など)に、1ビットのパリティビットを付け加える方法です。

この方式の場合、どのビット列のまとまり(文字)に誤りがあったかが検出できます。

水平パリティ

水平パリティでは、送信するデータのビット列の同じ位置毎にパリティビットを付け加える方式です。

この方式の場合、どの位置のビットに誤りがあったかが検出できます。

また、データの量(文字数)が増えてもひとまとまりにするビット数が変わらない限りはパリティビットの数が変わりません。

垂直水平パリティ

垂直パリティと水平パリティを組み合わせることによって、1ビットの誤りを検出し、訂正することが出来ます。

チェックサム

データを分割し、文字などのブロック単位のデータを数値とみなして、合計を取った値を検査用の符号としてデータに付け加え、誤りを検出する方法です。

合計を取るブロックの大きさは8ビットや16ビットがあります。合計を計算する時、ブロックサイズの上限値より大きくなった場合、繰り上がりの分は無視されます。

CRC方式(Cyclic Redundancy Check:巡回冗長検査)

送信するビット列をある定数(例えば生成多項式で求められる値)で割って、余りを検査用の符号としてデータに付け加える方式です。

パリティチェックの場合、複数ビットが誤っている時に誤りを検出できない場合がありますが、CRC方式では連続したビットの誤り(=バースト誤り)を検出することが出来ます。但し、訂正はできません。

ハミング符号方式

送信するビット列の中に、誤りを訂正するための符号を付け加える方式です。誤っているビットを検出し、受信側で訂正することが出来ます。この符号、又は仕組みをECC(Error Correcting Code:誤り訂正符号)といいます。

ハミング符号方式では、4ビットの情報に3ビットの誤り検査用符号を加え、2ビットの誤り検出機能と1ビットの誤り訂正機能をもたせたものがあります。よって、ブロック内に2ビットの誤りが発生した場合、誤りの訂正はできませんが検出は可能です。

ハミング符号は伝送時に使うと冗長ビットが多くなり伝送効率が落ちます。しかし、誤り訂正が可能であり、信頼性が高いため、最近のコンピュータのメインメモリにはハミング符号方式の誤り訂正機能を搭載したものが一般化しています。(ECCメモリ)

 

計測・制御に関する理論

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

【基本情報・応用情報】
・信号処理に関する考え方、仕組みを習得し、応用する。
・制御の必要性、考え方、仕組みを習得し、応用する。

(1)信号処理 基本情報 応用情報

アナログ波形を分析して、雑音を除去し、特徴を抽出する信号処理の考え方、仕組みを理解する。

用語例:DFT(Discrete Fourier Transform:離散フーリエ変換)、FFT(Fast Fourier Transform:高速フーリエ変換)、インパルス応答、フィルタ(ローパスフィルタ、ハイパスフィルタ、バンドパスフィルタ、デジタルフィルタ)、サンプリング定理、D/A変換、A/D変換

(2)制御に関する理論

1.制御の考え方、仕組み 基本情報  応用情報

制御の考え方、仕組みを理解する。また、フィードバック制御、フィードフォワード制御など、各種制御の考え方、仕組みを理解する。

用語例:リアルタイムOS、MPUアーキテクチャ、オープンループ、応答特性、制御安定性、PWM(Pulse Width Modulation:パルス幅変調)制御

2.センサ・アクチュエータの種類と動作特性 基本情報  応用情報

コンピュータ制御では、制御対象の光、温度、圧力などの状態をセンサで検出し、コンピュータが判断して、アクチュエータを通じて電動、油圧、水圧、空気圧などの機械的な動作に変換し、制御対象を一定の状態に保つなどの制御を行うことを理解する。

用語例:光学センサ、イメージセンサ、レーザセンサ、赤外線センサ、X線センサ、磁気センサ、加速度センサ、ジャイロセンサ、超音波センサ

3.計測システムの種類と動作特性 応用情報

測位システムなど、コンピュータを利用した高度な計測システムの考え方、仕組みを理解する。

用語例:GPS、基地局即位、無線LANアクセスポイント測位

 

 

信号処理

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

アナログ波形を分析して、雑音を除去し、特徴を抽出する信号処理の考え方、仕組みを理解する。

用語例:DFT(Discrete Fourier Transform:離散フーリエ変換)、FFT(Fast Fourier Transform:高速フーリエ変換)、インパルス応答、フィルタ(ローパスフィルタ、ハイパスフィルタ、バンドパスフィルタ、デジタルフィルタ)、サンプリング定理、D/A変換、A/D変換

信号処理

信号処理とは、音声信号や電気信号などに対して、いろいろな処理をして変換する技術です。処理形式は、アナログ信号処理とデジタル信号処理、相互の変換処理の3種類あります。

コンピュータの入力や出力に使われるものは、温度、音声、画像などアナログ信号が使われます。これに対して、入力された値をコンピュータ処理する際には、デジタル信号で扱われます。このアナログ信号からデジタル信号に変換する処理をA/D変換といい、逆にデジタル信号からアナログ信号に変換するのを、D/A変換とよんでいます。

フィルタリング

アナログデータのうち、デジタル化の対象にする必要がない部分を予め削ることをフィルタリングといいます。

例えば、音声の場合には、人間に聞こえない周波数の部分を予めカットする、といった処理が当てはまります。フィルタリングは「標本化」の際に行い、それ以降の手順で扱うデータの量を削減します。

また、A/D変換する際に、アナログ信号にノイズなどが混入していると、そのまま間違った値が入力されてしまうため、ノイズを取り除く必要があり、そのための装置をフィルタとよんでいます。

制御に関する理論

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

制御の考え方、仕組みを理解する。また、フィードバック制御、フィードフォワード制御など、各種制御の考え方、仕組みを理解する。

用語例:リアルタイムOS、MPUアーキテクチャ、オープンループ、応答特性、制御安定性、PWM(Pulse Width Modulation:パルス幅変調)制御

制御

制御とは、計測によって得られた入力値を元に、出力値を調整することです。

入力や出力に使われるものは、電圧、電流、圧力、温度、音量、音程などアナログ信号が使われます。

これに対して、入力された値をコンピュータ処理する際には、デジタル信号で扱われますので、必要に応じてA/D変換、D/A変換が行われます。

制御システム

制御システムとは、「制御」機能により、他の機器やシステムを管理し、制御するシステムです。

例えば、「バケツに水を汲む」という行動を例に取ってみます。

私たちがバケツに水を汲み場合、当然ながらバケツに入って水の量を見ていて、ちょうどよいところで水を止めます。「制御」とはまさしくこのような機能です。制御をせずに水をくんだ場合、単純に一定時間水を出して止めるという処理になってしまうので、出て来る水の量が外的要因で変わってしまった場合、「ちょうどよい量」の水を組めなくなってしまいます。

つまり、制御システムは外的要因にどう対処するか、がポイントになります。

制御システムにはフィードバック制御、フィードフォワード制御、オープンループ制御などがあります。

センサとアクチュエータ

センサは検知・監視装置であり、外的要因を信号に変換する機能を持ちます。電子的な温度計や、湿度計、回転計などが当てはまります。

アクチュエータは信号を動作に変換する機能を持つ機器です。制御可能なモータ、油圧装置、ヒータ、エンジンのガゾリン噴射装置などが当てはまります。

フィードバック制御

フィードバック制御とは、制御した出力の結果を入力側に戻し、目標値と比較して次の制御に反映させる制御方法です。

例えばエアコンの場合、室温と設定温度の差を計測してエアコンから出る風の温度と風量に反映していきます。

フィードバック制御では、常にセンサを用いて対象(エアコンの場合室温)を監視しています。

そのため、エアコンの場合は窓を開けるなどして室温が急に高くなった場合でもその変化を計測し、エアコンの風量などに反映することが出来ます。

フィードバック制御は変化が起きてから制御量の修正をするため、影響が現れてから修正するという後追いの修正となります。

フィードフォワード制御

フィードフォワード制御は、制御を乱す外的要因が発生する場合に、その影響が出る前に必要な修正を行う制御方法です。

例えばエアコンの場合、室内温度に変化はないけれど、外の気温が下がってきたので、冷房を弱める、といった制御を行うことが出来ます。しかし、室内温度と設定温度が等しくなるとは限りません。

通常は、フィードバック制御と組合せて用いられます。

オープンループ制御

制御量の入力値のみを計算する制御方式です。したがって、出力に対してのフィードバックや外乱などのデータは一切考慮しません。

単純に負荷のかかっていないモータの回転数などを入力電圧だけで制御する場合などに適しています。

クローズドループ制御

モータに対する負荷が変化するような場合、負荷により回転数が変化するので、回転数を一定に保つためには、オープンループ制御ではなく、フィードバック制御が必要になります。

このようなフィードバックや外乱を考慮して入力値を制御する方式をクローズドループ制御といいます。

リアルタイムOS

このような制御システムのコンピュータの制御では、リアルタイムOSが利用されることがあります。

リアルタイムOSとは、リアルタイム処理(=処理に対する応答時間が一定の範囲内であること)が保証されているオペレーティングシステムです。

利用者にとっての利便性よりもデータの処理速度を優先しているのが特徴です。