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

離散数学とは

離散数学とは

離散数学(りさんすうがく、英語: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とは、リアルタイム処理(=処理に対する応答時間が一定の範囲内であること)が保証されているオペレーティングシステムです。

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

 

データ構造(概要)

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

【基本情報・応用情報】
・データ構造の考え方、仕組みを習得し、応用する。
・代表的なデータ構造の種類、特徴、操作を習得し応用する。

【ITパスポート】
・データ構造の基本的な考え方を理解する。

(1)データ構造 ITパスポート 基本情報 応用情報

データ構造の考え方、仕組みや、BNFを使用したデータ構造の定義方法を理解する。

(2)データ構造の種類

1.配列 ITパスポート 基本情報  応用情報

配列の考え方を理解し、データの格納方法、取り出し方法などの操作を理解する。

用語例:多次元配列、静的配列、動的配列

2.リスト ITパスポート 基本情報  応用情報

リストの考え方、その操作を理解する。

用語例:線形リスト、単方向リスト、双方向リスト、環状リスト、リンク付きリスト

3.スタックとキュー 基本情報 応用情報

スタックとキューの考え方、その操作を理解する。

用語例:FIFO、LIFO、プッシュ、ポップ

4.木構造 ITパスポート 基本情報 応用情報

木構造の種類と考え方、木の巡回法、節の追加や削除、ヒープの再構成などを理解する。

用語例:根、葉、枝、二分木、完全二分木、バランス木、順序木、多分木、探索木、深さ優先探索、幅優先探索、先行順、後行順、中間順

 

 

データ構造

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

データ構造の考え方、仕組みや、BNFを使用したデータ構造の定義方法を理解する。

データ構造

「データ構造」とは、コンピュータでデータを系統立てて扱う仕組みをいいます。

プログラミングに際して、データ構造の設計はすべての基礎・土台となるものです。目的とする処理が確実に、迅速に実行できるようなデータ構造となるよう、あらかじめ十分検討し設計しておく必要があります。

変数

プログラムはコンピュータへの操作を指示するもので、コンピュータになにがしかの処理をさせるときに、支持を効率的に与えます。

そのプログラムの内部で、情報を一時的に格納するための「器」として「変数」を用います。変数を定義する際には「変数名」を付与し、他のデータと区別できるようにします。

また、変数では、数値のみならず、文字や文字列、真偽を表す真理値など様々な情報を扱うことが出来ます。その際、変数が扱う情報の種類を「型」と呼びます。

データの型

コンピュータで扱う様々なデータは、用途によって以下のような種類に分けることが出来ます。これをデータの型(属性)といいます。

プログラム内部で扱われる変数には、それぞれ「型」が定義されていて、「型」が異なる変数に情報を入れることは、基本的には出来ません。

数値型整数型小数点がつかない整数値のみ扱える。
実数型小数点以下の数値も扱える。
文字型英字や記号、漢字やひらがな・カタカナなどが扱える。
文字コードによって文字を区別する。
論理型真(True) か偽(False)かの2つの値のみ扱える。

データ構造の種類

コンピュータでたくさんのデータを管理するには、そのデータ構造をなるべく用途に適した形で、コンパクトに収納でき、かつ簡単に探し出せるものにしておくと便利です。

代表的なデータ構造には、レコード、配列、リストがあります。

レコード

プログラムがデータを処理する時の基本単位になるまとまりを、レコードといいます。

1件のレコードには型の異なる幾つかの項目(=フィールド)があるのが一般的です。

例えば「住所録」のデータであれば、一人分のデータを1件のレコードとし、その中に「氏名」「住所」「生年月日」といったフィールドが含まれます。

また、同じフィールドを持つレコードの集まりのことを「ファイル」といいます。

 

配列

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

配列の考え方を理解し、データの格納方法、取り出し方法などの操作を理解する。

用語例:多次元配列、静的配列、動的配列

配列

コンピュータで大量のデータを高速に処理する場合に、同じ型の変数を、先頭から順番を付けて並べたものを配列といいます。

配列におけるそれぞれの変数は「配列要素」または「要素」と呼ばれます。要素にはそれぞれを区別するために順番に番号が振られています。この番号のことを添字(インデックス)といい、添字を指定すると、配列の中から特定のデータを任意の順番で探し出すことが出来ます。

添字は先頭のデータを1から数える場合と、0から数える場合とがあります。

配列の特徴

配列は構造が単純で、先頭から順に読み込んでいくには便利ですが、データの論理的な順序どおりに物理的にも並んでいるように作られていないといけないので、後からデータを追加したり、削除したりする場合に、そこから後ろのデータを全てずらして書き直さなければならないというデメリットがあります。

あらかじめ配列内の要素の数が決まっているものを「静的配列」といいます。
対して、データの数によって配列の要素の数が変化するものを「動的配列」といいます。

二次元配列

配列には、行が2行以上の多次元配列もあります。2行の場合は二次元配列といいます。

例えば、5名の数学のテスト結果を1行目に、英語のテスト結果を2行目に格納する、といった具合に利用することが出来ます。

二次元配列を使う場合には添字が二つ必要となり、添字の1つ目が行番号、2つ目が列番号となります。

リスト

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

リストの考え方、その操作を理解する。

用語例:線形リスト、単方向リスト、双方向リスト、環状リスト、リンク付きリスト

配列のデメリットとリスト

配列では、要素の追加・挿入をする場合に、挿入する位置以降のすべての要素を1つずつずらす処理が必要になるため、要素の数が大量の場合は処理に時間がかかります。
つまり、要素の追加や削除が非効率という欠点があります。

この欠点を踏まえ、追加や削除を効率良く行うことが出来るように工夫されたデータ構造が「リスト」です。

リスト(線形リスト)

リストは同じ型のデータを集めて、それぞれに「自分の次のデータがどれか」という情報(=ポインタ)を持たせて連結したものです。データは物理的に順番に並んでいる必要はありません。

リストの中のデータは、データ部とポインタ部からなります。
データ部には実際のデータが、ポインタ部には次のデータの格納場所が入っています。ポインタ部に入っているメモリ城の格納場所のことをアドレス(番地)といいます。

なお、リスト構造には配列のような添字という概念はありません。そのため、配列のように添え字を使って任意の要素にアクセスする、ということが出来ません。

単方向リストと双方向リスト

リストには、次へのポインタのみを持つ単方向リストと、前後へのポインタを両方持つ双方向リストがあります。

単方向リストは先頭からデータを探すことしか出来ないので、後ろの方のデータを見つけるには時間がかかります。

双方向リストは両方向のポインタを持つため、単方向リストよりもサイズは大きくなりますが、各データの前後、およびリストの先頭、末尾を示すポインタを持っているので、データを後ろから探索することも出来ます。

リスト構造への追加と削除

リスト構造のデータはポインタを保つ必要があるため、配列よりも大きくなりますが、データの挿入や削除をする際、その前後のポインタを書き換えるだけで済むので、データを頻繁に更新する場合に適しています。

環状リスト

単方向リストでは、末尾のデータの「次へのポインタ」は空になります。また、双方向リストでは、先頭のデータの「前へのポインタ」と、末尾のデータの「次へのポインタ」は空になります。
これらを空にせずに、データが環状につながっているようにしたものが環状リストです。

環状リストにはポインタを1つ持つ単方向リストを基にするものと、ポインタを2つ持つ双方向リストを基にするものとがあります。

 

スタックとキュー

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

スタックとキューの考え方、その操作を理解する。

用語例:FIFO、LIFO、プッシュ、ポップ

スタック(LIFO)

スタックは、最後に入れたものを最初に取り出すデータ構造で、LIFO(Last In, First Out:後入れ先出し)ともいいます。

スタックにデータを追加する動作をプッシュ(push)、データを取り出す動作を(pop)といいます。

スタック構造は、逆ポーランド記法の計算やプログラムにおける提携処理の呼び出しと戻りなどに応用されています。

逆ポーランド記法の説明で「コンピュータと相性が良い」と述べていますが、その特徴とスタックというデータ構造は密接に関連しています。

逆ポーランド記法で記述された式を処理する場合、以下のルールでスタックを使った処理を行っています。

  • 数値が来たら、その数値をスタックにPUSHする。
  • 演算子が来たら・・・
    • スタックからデータをPOPする。(データ1)
    • スタックからデータをPOPする。(データ2)
    • データ1とデータ2を演算し、その結果をスタックにPUSHする。

この処理を行うと、最終的にスタックの一番上に一連の式の結果が保存されています。

キュー(FIFO)

キュートは、最初に入れたデータを最初に取り出すデータ構造で、FIFO(First In, First Out:先入れ先出し)ともいいます。

キューにデータを追加する動作をエンキュー(ENQ)、データを取り出す動作をデキュー(DEQ)といいます。

キューは通信において、タイミング調整に使われることがあります。代表的な例として、送信バッファや受信バッファがあります。バッファとは、一時的にデータを入れる場所のことです。

例えば、コンピュータでのデータ受信の際に、インターネット等伝送路からのデータ量が一定していない場合、そのまま受信してしまうとデータ受信ペースの遅れや、瞬間的に大量のデータを受信した場合などで不都合が生じます。このような場合に受信バッファが用いられ、受信したデータを一時的に格納しておき、できるだけコンピュータが受信するデータ量を一定にするようにします。

スタックやキューをプログラムで実現する場合の違い

スタックやキューをプログラムで実装する場合、データ量や用途に応じて配列構造とリスト構造を使い分けます。

 配列で実現リストで実現
キュー先頭を指すポインタと最後尾を指すポインタが必要
処理が単純で速い
単方向リストで可能
データあふれの心配がない
スタック最新のデータを示すポインタが必要
処理が単純で速い
単方向リストで可能
データあふれの心配がない

木構造

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

木構造の種類と考え方、木の巡回法、節の追加や削除、ヒープの再構成などを理解する。

用語例:根、葉、枝、二分木、完全二分木、バランス木、順序木、多分木、探索木、深さ優先探索、幅優先探索、先行順、後行順、中間順

木構造

 

木構造はデータ間の階層的な関係、つまり親と子のような関係を表現するのに用いられるデータ構造です。大量の情報を系統的に管理する際に有効です。

木構造は、「節(ノード)」と「枝(ブランチ)」から構成されています。最上位の節は「根(ルート)」といいます。また、最下位の節を「葉(リーフ)」といいます。複数に枝分かれしている場合には、「葉(リーフ)」は複数になります。「枝(ブランチ)」は節と節をつなぐ経路のことです。

また、ある節の上の枝につながる節を親、下の枝につながる節を子といいます。

木構造では、親の節から子の節をたどっていくことでデータを取り出すことができます。

木構造の深さ

木構造では、節や葉の階層を示すため「深さ」という数値が使われます。深さは根の階層を0として、下に行くと1ずつ増えていきます。

部分木

木構造の部分を示す時に「部分木」という言葉が使われます。

ある節に注目した時、その節の左の枝から下の木構造を「左部分木」、節の右の枝から下の木構造を「右部分木」といいます。

二分木と多分木

節から出る枝が2本以下である木を二分木といいます。対して、節から出る枝が2本より多い気を多分木といいます。

二分木では、節の左側に繋がる部分を左の子(左部分木)、右側に繋がる部分を右の子(右部分木)といいます。

二分木の中で、根から葉までの深さが全て同じものを「完全二分木」と呼びます。一般的な二分木は「葉の深さの差が1以内である」、「葉を除く全ての節が左部分木を持っている」という二つの条件を満たすものです。

同じ階層の節に順位があるものを順序木といいます。順序木では一つの節の下の節や葉は左側のほうが高い順位と見なされます。順序木ではデータの格納方法を工夫することにより、データの検索や大小関係での並び替えを効率的に行うことが出来ます。

木の巡回法

木構造からデータを探して読み出すことを「木の巡回」といいます。二分木の巡回法には幅優先探索と深さ優先探索があります。

木の幅優先探索

幅優先探索は、階層が浅いデータを優先して検索する方法です。

幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、1階層目の節や葉のデータを左から右へと順番に読み出していきます。1階層目のデータが検索したデータでない場合は、次は2階層目と進んでいく、という方法です。

木の深さ優先探索

深さ優先探索は、左部分木を優先して、階層が下のデータを先に読み出す方法です。

葉以外の節のデータと、葉のデータを読み出す順番の違いにより、先行順探索、中間順探索、後行順探索の3種類があります。

先行順探索

先行順は、節、左部分木、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると、最初の節である根のデータ1を読み出し、次に左部分木の節のデータ2を読み出します。
その次は2階層目の左部分木のデータ3を読み出します。
3階層目はないので、2階層目の右部分木のデータ4を読み出します。

中間順探索

中間順は、左部分木、節、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると。根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次に、上の階層に戻ってデータ2を読み出します。
その次に2階層目の右部分木のデータ3を読み出します。
2階層目の読み出しが終わると、次は根のデータ4を読み出します。

後行順探索

後行順は、左部分木、右部分木、節の順番で読み出す方法です。

右の図を例にとって説明すると、根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次は2階層目の右部分木のデータ2を読み出します。
その次は、上の階層に戻ってデータ3を読み出します。
その次は、1階層目の右部分木ですが、そこからは左部分木が出ているので、左部分木のデータ4を読み出します。

二分探索木の応用

二分木に対して、データを格納するルールを定めることにより、木構造をデータの検索や大小順での並び替えに活用できます。

データの検索に活用する例が「2分探索木」、整列に活用する例が「ヒープ」です。

2分探索木

二分木の中でも、左の木の全てのデータが親よりも小さく、右の木の全てのデータが親よりも大きいという声質を持つ木を「2分探索木」といいます。
なお、2分探索木は完全二分木である必要はありません。

データの探索

2分探索木を用いると、節毎に大小関係を比較することにより、データの探索を効率的に行うことが出来ます。

例えば、9階層の木構造の場合、深さ優先探索や幅優先探索を行うと、最大で1000回を越える比較が行われますが、2分探索木ならば、比較回数は10回未満で済みます。

データの追加

2分探索木にデータを追加する場合は、検索と同じような手順で、追加する場所を探していきます。

データを追加した後も2分探索木になるようにします。

データの削除

2分探索木でデータを削除する場合、削除する節の持つ枝の数により処理が異なります。

  • 枝のない葉の場合: そのまま葉を削除します。
  • 枝が1本の場合: 節を削除して、下の節をつなぎ直します。
  • 枝が2本の場合: 削除する節の左部分木の中で、最も大きな値のデータを削除する節に移動します。

削除をこの手順で行うことにより、削除を行った後も2分探索木になるようにします。

バランス木

木構造は、追加や削除を繰り返していくうちに、葉の深さにばらつきが出て、部分木のバランスが悪くなることがあります。

部分木のバランスが悪くなると、探索の効率が低下してしまうので、一定のルールを定めて、部分木のバランスを取る木構造があります。そのような木構造を「バランス木」といいます。
完全二分木はバランス木の一種です。他のバランス木には「AVL木」や「B木」があります。

AVL木

葉の深さの差が常に1以下の木構造です。完全二分木と異なり、葉でない節が左部分木を持つ必要はありません。

AVL木では、要素の追加や削除が発生する時に、バランスが崩れていないかをチェックしつつ、崩れていればそれを回復する処理(=再構築)を行う必要があります。そのため、追加や削除が発生する場合には、通常の2分探索木より手間がかかるのですが、バランスを取りながら木の深さを浅く保つことで、探索時のコストを抑えることが可能になります。

B木

B木は多分木のバランス木の一つです。一つの節に入れられるデータの個数や分岐の数は、「次数」と呼ばれる数値で決まります。

次数をNとするB木を「N次のB木」といいます。N次のB木は以下の4つの条件を満たす必要があります。

  • 一つの節のデータ数は2×N個以下であること。
  • 根以外の節はN個以上のデータを持つこと。
  • 葉以外の節はデータ数+1個の枝を持つこと。
  • すべての葉は同じ階層であること。

バランス木の実用例

バランス木の実用例としては、データベースの「インデックス(索引)機能」にB木が多く利用されています。(AVL木を使う場合もあります。)

検索の処理を高速に行うことを優先したい場合には、単純な2分探索木よりも、バランス木が用いられます。
単純な2分探索木で最初の木構造の作り方が悪いと、偏った木構造となり、検索のコストがリスト構造と変わらなくなることがあるためです。

アルゴリズム(概要)

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

【基本情報・応用情報】
・アルゴリズム、流れ図の考え方、表現方法を習得し、応用する。
・代表的なアルゴリズムを習得し、応用する。
・アルゴリズムの設計方法を習得し、応用する。

【ITパスポート】
・アルゴリズムと流れ図の基本的な考え方と表現方法を理解する。

(1)アルゴリズムと流れ図 ITパスポート 基本情報 応用情報

アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。

用語例:端子、処理、定義済み処理、判断、ループ端、データ、線

(2)代表的なアルゴリズム

1.整列、併合、探索のアルゴリズム ITパスポート 基本情報  応用情報

整列のアルゴリズム、併合のアルゴリズム、探索のアルゴリズムを理解する。

用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート、線形探索法、二分探索法、ハッシュ表探索法、シノニム対策

2.再帰のアルゴリズム 基本情報  応用情報

再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。

3.グラフのアルゴリズム 基本情報 応用情報

グラフのアルゴリズムを理解する。

用語例:深さ優先探索、幅優先探索、最短経路探索

4.文字列処理のアルゴリズム 基本情報 応用情報

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

5.ファイル処理のアルゴリズム 基本情報 応用情報

バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。

6.近似アルゴリズム 応用情報

近似アルゴリズムを理解する。

用語例:近似計算

7.確率アルゴリズム 応用情報

モンテカルロ法を例として、確率アルゴリズムを理解する。

8.遺伝的アルゴリズム 応用情報

最適化問題への進化論の適用例であることを理解する。

9.自然言語処理のアルゴリズム 応用情報

情報検索、機械翻訳などを例に、自然言語処理のアルゴリズムを理解する。

10.データ圧縮のアルゴリズム 応用情報

データ圧縮のアルゴリズムを理解する。

用語例:ランレングス法。ハフマン法

11.図形に関するアルゴリズム 応用情報

3次元図形処理アルゴリズムを理解する。

用語例:Zバッファ法、スキャンライン法、レイトレーシング法

12.記憶域管理アルゴリズム 応用情報

OSのメモリ管理の方法について、空きメモリ管理のためのデータ構造、メモリの割当、開放などのアルゴリズムを理解する。

(3)アルゴリズム設計 基本情報 応用情報

アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。また。アルゴリズムの設計方法を理解する。

用語例:再帰、分割統治法

 

アルゴリズムと流れ図

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

アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。

用語例:端子、処理、定義済み処理、判断、ループ端、データ、線

アルゴリズム

アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。

同じ結果を出すための処理であっても、より整理されたアルゴリズムで行うほうが、効率よく結果を得ることが出来ます。プログラムを作るときは、特にどんなアルゴリズムを使うかが重要になります。

流れ図

流れ図は「フローチャート」ともいい、処理のアルゴリズムを視覚的に表現できる図解法です。プログラムの設計によく用いられます。

流れ図は以下の記号類を使って、上から下に流れていくように描きます。

アルゴリズムの基本構造

アルゴリズムの基本構造には、順次型、分岐型、反復型があります。

  • 順次型: 順番に処理を実行していく。

    流れ図では、上から順に、四角系の中に処理を描いていきます。

  • 分岐型: 条件によって異なる処理を実行する。

    流れ図では、ひし形の中に分岐の条件を書き、矢印を分岐させます。

  • 反復型: 繰り返しを終える条件が満たされるまで、同じ処理を繰り返す。

    繰り返しを終える条件を、角を切り取った四角形(=ループ端)の中に描き、繰り返す処理を2つのループ端の間に描いていきます。


    繰り返しの図形を使わずに、右記のように分岐のひし形を使って描く方法もあります。

前判定型と後判定型の繰り返し

反復型には、先に繰り返しを行うかどうかの条件判定をしてから、一通りの処理を行う「前判定型」と、処理を一通り実行した後で、終了するかどうかの条件判定を行う「後判定型」の2種類があります。

反復処理の「1回め」をどのように扱うかで、前判定型と後判定型を使い分けます。

前判定型では、1回目の条件判定で終了条件を満たすと、繰り返しの処理は1回も実行されません。
対して後判定型では繰り返し処理の後で終了条件を判定するので、少なくとも1回は処理が実行されます。

流れ図を使った例

二人で行うゲームを例に、流れ図を見てみましょう。

互いにじゃんけんをし、勝ったほうがピコピコハンマーで相手の頭を叩きます。同時に、負けた方はヘルメットで防御します。
ハンマーが頭にヒットすれば叩いた方の勝ちとなる、というゲームです。(いわゆる「たたいてかぶってジャンケンポン」)

 

整列-代表的なアルゴリズム1

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

整列のアルゴリズムを理解する。

用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート

整列(ソート)

整列とは、データを大きい順(降順)または小さい順(昇順)になるように並び替えることです。

 昇順降順
数値「32514」1234554321
英字「BDAEC」ABCDEEDCBA
かな「いあえおう」あいうえおおえういあ

数値データは値の大小順に整列され、文字データは文字コードの値の大小順で整列されます。
英字はアルファベット順に、ひらがな、カタカナは50音順に文字コードが割り振られているため、英字同士はアルファベット順、ひらがな同士、カタカナ同士は50音順で並び替えが可能になります。

代表的なソートアルゴリズムと計算量・速度の比較
名称オーダー(計算量)処理速度備考
バブルソートO(n2)遅い処理が単純で実装が容易。
選択ソートO(n2)遅い処理が単純で実装が容易。
挿入ソートO(n2)遅い処理が単純で実装が容易。
O(n2) のアルゴリズムの中では高速。
シェルソートO(n1.2)~O(n2)程度やや遅い挿入ソートの改良版だが、場合によっては挿入ソートと速度が変わらない。
マージソートO(n log2n)高速「再帰」の概念の理解が必要。
クイックソートO(n log2n)高速「再帰」の概念の理解が必要。
ヒープソートO(n log2n)やや高速「ヒープ木」の概念の理解が必要。

バブルソート

代表的な整列のアルゴリズムに、バブルソートがあります。バブルソートは一つとなりと比べては入れ替える、という処理を繰り返していく方法です。
隣同士のうち、大きい方が前に並ぶように入れ替えていくと、結果的に全体が降順で並びます。逆に小さいほうが前に並ぶようにすると昇順となります。

例:「1・5・7・3・9」の5枚のカードをバブルソートで降順に並び替える。

  1. 要素[1]と[2]を比較して、大きい方が前になるように入れ替える。
  2. 続いて[2]と[3]、[3]と[4]、[4]と[5]の順に比較と入れ替えを行う。
    この時点で、要素[5]が最小値になるので、要素[5]の位置が確定する。
  3. 要素[1]~[4]について、同様に比較と入れ替えを繰り返し、各要素の位置を確定する。
バブルソートの計算量

n個の要素をバブルソートで整列する時の比較の回数は、 ( n ( n - 1 ) ) ÷ 2 であり、n の2乗に比例します。。
オーダ記号で表すと、O(n2) となります。

選択ソート

選択ソートは、最小値の要素を選択して、先頭の要素と置き換える整列アルゴリズムで、基本選択法ともいいます。
処理効率は、バブルソートと変わらず、計算量はO(n2) となります。

例:「1・5・7・3・9」の5枚のカードを選択ソートで昇順に並び替える。

  1. 要素[1]~[5]の値を調べて、最小値を求める。
  2. 1.で求めた最小値を先頭の要素と交換する。
  3. 残りの要素について、1と2を繰り返す。

挿入ソート

挿入ソートは、前の方の整列済みの並びの途中へ、直後の要素を挿入する整列アルゴリズムで、基本挿入法ともいいます。
計算量はO(n2) となります。

例:「1・5・7・3・9」の5枚のカードを挿入ソートで昇順に並び替える。

  1. 先頭の要素を1要素だけの整列済みの並びと見立てる。
  2. 整列済みの並びの要素と、その直後の要素を比較して、バブルソートと同じ要領で並び替えを行う。
  3. 最後の要素を処理するまで、2を繰り返す。

マージソート

マージソートは、並びを2等分しながら、分割された部分同士を併合(マージ)することによって、全体を整列させるアルゴリズムです。

例:「2・7・5・3・8・1・4・6」の8枚のカードをマージソートで昇順に並び替える。

  1. 並びを2等分することを、整列済みの部分並びが見つかるまで反復する。(要素が1つになれば整列済みとみなすので、反復は必ず終了する。)
  2. 整列済みの部分並び同士を、整列状態を保つように併合して、1つの部分並びにする。
  3. 全体が1つの部分並びになるまで、2を反復する。

シェルソート

シェルソートは、シェル氏によって考案された挿入ソートの改良版の整列アルゴリズムです。

  1. 適当な間隔を決めて、等間隔の飛び飛びの要素で作った部分的な並びに対して挿入ソートを適用する。
  2. 間隔を狭めながら、間隔が1になるまで1を繰り返す。

例:「2・7・5・3・8・1・4・6」の8枚のカードをシェルソートで昇順に並び替える。

挿入ソートは、元々の並びが整列状態に近いほど高速になる性質があるため、間隔を空けて部分的な並びを作って徐々に整列させることで速度の向上を図っています。

クイックソート

クイックソートはその名の通り、特に高速な整列アルゴリズムです。

  1. 適当な基準値を定めて、その値より小さい要素を前の方に移し、その値以上の要素を後の方へ移す。
  2. 分割したそれぞれのグループへ、1の処理を反復して、全てのグループに属する要素数が1になるまで繰り返す。

例:「9・2・7・5・3・8・1・4・6」の9枚のカードをクイックソートで昇順に並び替える。

反復する毎に、分割されたグループの数は2倍、4倍、8倍というペースで増えていくので、各グループに含まれる要素の数は急激に減っていきます。
基準値と要素の値を比較する回数が急速に減っていくことが、クイックソートが特に高速である理由です。

ヒープソート

ヒープソートは、ヒープを経由する整列アルゴリズムです。

ヒープは「小さい山」という意味の言葉であり、親の値が必ず子の値以上であることを保つ二分木です。

  1. 要素の並びを元にして、ヒープを構築します。子の処理には、木構造アルゴリズムの一種である、ヒープ構築アルゴリズムを用います。
  2. 根に当たる要素を取り出して、並びの端へ移します。
  3. ヒープに残った要素に対して、ヒープ再構築アルゴリズムを適用します。
  4. 2と3をヒープの要素がなくなるまで繰り返します。

例:「2・7・5・3・1・4・6」の7枚のカードをヒープソートで降順に並び替える。

二分木は木の階層ごとに、部分木の数が2倍、4倍、8倍と増えていきます。値の大小比較の回数は2つの部分木の根を比較するだけなので、ヒープソートは特に高速とされています。

 

探索、併合、再帰-代表的なアルゴリズム2

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

探索、併合のアルゴリズムを理解する。
再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。

用語例:線形探索法、二分探索法、ハッシュ表探索法、シノニム対策

探索

「探索」とは配列などに格納されたデータの集まりから、特定のデータを探すことです。その値が見つかる場合と、見つからない場合があり、複数ある場合には最初の一つを見つければ良い場合と、全てを見つける必要がある場合があります。

つまり、探索の結果も見つかったかどうかだけではなく、何番目に見つかったか、いくつあったか、という情報を帰す場合があります。

線形探索法(リニアサーチ)

線形探索法とは、配列の先頭から1つずつ調べてゆき、求めるデータが見つかるか、又は配列の最後まで探し終わったとき探索を終了する方法です。

以下に、線形探索法の場合の流れ図を示します。ここでは、4つの数が入った配列の中から、「5」を探すものとします。

探索する数「5」を変数 x とし、探索対象の数を n [ i ] と表します。
先頭の n [ i ] から順に x と比較していき、同じものが見つかったら、その添字 i を表示して探索を終了、最後まで探して見つからなかった場合は、「無し」と表示して終了します。

なお、線形探索法を行なった場合の探索回数は以下の通りとなり、オーダ記号で表すと O(n) となります。(データは n 個とする)

  • 最小探索回数: 1回
  • 最大探索回数: n回
  • 平均探索回数: (n+1)÷2回

番兵を使った線形探索法

線形探索をより簡単にするために、配列の最後に「番兵」と呼ばれるデータを追加する方法があります。

探すデータと同じ値を、配列の最後尾の次に追加しておくことで、反復の終了条件として、添字の範囲を毎回チェックする必要がなくなります。

但し、配列を拡張できないケースではこの方法は使用できません。

二分探索法

二分探索法は、整列済みのデータの並びを二等分しながら、目的のデータを探す探索アルゴリズムです。

例えば、昇順に整列済みの配列であれば、以下のような流れとなります。

  1. 並び全体の中央のデータと目的のデータを比較する。一致すれば終了。
  2. 目的のデータが中央のデータより小さければ、前半の部分並びにを対象にして、大きければ後半の部分並びを対象にして、1を繰り返す。
  3. 最終的に部分並びの要素が1つになったら、見つからなかったことになる。

なお、二分探索法を行なった場合の探索回数は以下の通りとなり、オーダ記号で表すと O(log2n) となります。(データは n 個とする)

  • 最小探索回数: 1回
  • 最大探索回数: ( log2n)+1回
  • 平均探索回数:  log2n 回

例えば、要素の数が65,536個(216)であった場合、線形探索法なら、最大で65,536回、平均でも32,768回かかります。
対して、二分探索法の場合、比較を行うたびに、部分並びの数が、216、215、214、・・・22、21、20 と減っていき、最大でも17回で済みますので、二分探索法の方がはるかに高速なアルゴリズムです。

ハッシュ表探索

ハッシュ表探索法は、データの格納位置をデータの値から決めることで、目的のデータを直接得られる方法です。
ハッシュ表という配列の複数の要素に、探索対象の部分並びを所属させておき、目的のデータの値に対してある種の計算を行い、一つの部分並びだけを探索対象として選択する探索アルゴリズムです。

例えば、目的のデータを100で割った余りは、必ず0~99の数になります。この値を100個の要素の配列の索引として、一つの部分並びを選択することが出来ます。
この例の「目的のデータを100で割った余り」といったような、目的のデータを範囲内の値に換算する関数のことを「ハッシュ関数」といいます。

ハッシュ表探索では、最初の1回目の検索で多くの部分並びの中から1つを選択することで、初めの時期の検索回数を減らしています。

ハッシュ関数と衝突

ハッシュ関数を適用した結果、値が重複してしまうことを衝突(シノニム)といいます。

ハッシュ表を使う場合、ハッシュ関数を検討する際に極力シノニムが発生しないようにすることも重要ですが、余りハッシュ表を大きくすると無駄も多いので、シノニム発生時の対処法もあわせて検討しておく必要があります。
例えば、データの件数が1万件だからといって、1万件のハッシュ表を作るのでは、メモリをムダに消費してしまいます。

シノニム対策としては、以下のようなパターンが主流です。

  • ハッシュ表の隣接する要素を使う。
  • シノニム用の領域を別途用意する。

併合のアルゴリズム

併合のアルゴリズムは、二つの整列済みのデータの並びを一つの整列されたデータの並びにするアルゴリズムです。

  1. 二つの配列のそれぞれ先頭の要素を比較して、値の小さい要素を併合先の配列の先頭に移す。
  2. 残りの配列について、それぞれの配列の最後の要素を移し終わるまで1の処理を繰り返す。

再帰のアルゴリズム(リカーシブ)

再帰とは、定義自身の一部にその定義が含まれるという性質です。

再帰のアルゴリズムは、反復を含むアルゴリズムと似ていますが、それよりも簡潔になります。

例えば、1からnまでの自然数の和を表す関数を f( n ) とします。
・n=1のときは、f(1) は値として「1」を返す。
・n>1のときは、f( n )は値として「n+f( n-1 )」を返す。

この関数を使って、1から4までの和を計算する場合、以下のように再帰が進行していきます。

f(4) = 4+f(3)
 =4+3+f(2)
 =4+3+2+f(1)
 =4+3+2+1
 =10

再帰のアルゴリズムは、これまでに紹介した整列や探索のアルゴリズム(マージソート、クイックソート、二分探索法)でも活用されているアルゴリズムです。

グラフのアルゴリズム-代表的なアルゴリズム3

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

グラフのアルゴリズムを理解する。

用語例:深さ優先探索、幅優先探索、最短経路探索

グラフのアルゴリズム

グラフは節(ノード)とそれらを連結する結線(リンク)で結ばれた一つの図です。通信網、木構造、あるいは流れ図がその例です。(木構造の場合は、結線のことを枝とも呼ぶ)

これらのグラフを扱うアルゴリズムをグラフのアルゴリズムといいます。

木の巡回法(再掲)

木構造からデータを探して読み出すことを「木の巡回」といいます。二分木の巡回法には幅優先探索と深さ優先探索があります。

木の幅優先探索

幅優先探索は、階層が浅いデータを優先して検索する方法です。

幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、1階層目の節や葉のデータを左から右へと順番に読み出していきます。1階層目のデータが検索したデータでない場合は、次は2階層目と進んでいく、という方法です。

木の深さ優先探索

深さ優先探索は、左部分木を優先して、階層が下のデータを先に読み出す方法です。

葉以外の節のデータと、葉のデータを読み出す順番の違いにより、先行順探索、中間順探索、後行順探索の3種類があります。

先行順探索

先行順は、節、左部分木、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると、最初の節である根のデータ1を読み出し、次に左部分木の節のデータ2を読み出します。
その次は2階層目の左部分木のデータ3を読み出します。
3階層目はないので、2階層目の右部分木のデータ4を読み出します。

中間順探索

中間順は、左部分木、節、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると。根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次に、上の階層に戻ってデータ2を読み出します。
その次に2階層目の右部分木のデータ3を読み出します。
2階層目の読み出しが終わると、次は根のデータ4を読み出します。

後行順探索

後行順は、左部分木、右部分木、節の順番で読み出す方法です。

右の図を例にとって説明すると、根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次は2階層目の右部分木のデータ2を読み出します。
その次は、上の階層に戻ってデータ3を読み出します。
その次は、1階層目の右部分木ですが、そこからは左部分木が出ているので、左部分木のデータ4を読み出します。

最短経路探索

最短経路とは、グラフのある出発点の節から終着点の節へ到達するのに、結線ごとに要する時間や距離の合計が最短である結線の並びです。この最短経路をたどることを「最短経路探索」といいます。
結線ごとに要する時間や距離を総称して「コスト」といいます。

例:ダイクストラのアルゴリズム

  1. 出発点から各説へのコストの表は、出発点の節だけゼロとし、それ以外の節へのコストは初期値として無限大とする。
  2. 出発点の節から、結線の一つをたどって、節のデータを調べる。
    1. その節へのコストの記録が、今回の経路のコストより大きいなら、今回の経路のほうが短いので、今回の経路のコストを記録し、直前の節の記号をその節に関するデータとして記録する。(その節へのコストが初期値の無限大だったのなら必ずこちらの処理)
    2. その節へのコストの記録が、今回の経路のコスト以下なら、今回の結線は最短経路に含まれないので、それ以降の処理対象から除外する印を記録する。
  3. 以上の処理を、処理していない結線について反復する。
  4. すべての処理が終わったら、終着点の節から最短のコストを回答する。また、直前の節を次々と逆行して、出発点から終着点までの節の順序を経路として回答する。

 

文字列処理のアルゴリズム-代表的なアルゴリズム4

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

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

文字列処理のアルゴリズム

文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。

  • 連結: 一つの文字列の後へ別の文字列を追加して、一つの文字列にします。
  • 挿入: 文字列の途中に別の文字列を挿入して、一つの文字列にします。
  • 削除: 文字列の一部の文字を取り除いて、残りを一連の文字列にします。
  • 照合: 文字列が別の文字列の中に含まれるか、有無を調べて位置を特定します。

順次探索法

  1. 対象の文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。
    すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。
  2. 対象の文字列の1文字後ろから1の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。

ボイヤ・ムーア法(BM法)

ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。

  1. 特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の2表を作成する。
  2. 対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。
    一致したら全体の処理を終了して、対象の文字列の位置を返す。
  3. 一致しなかったら、比較時に得られた情報と1で作った表を元にして、文字をスキップし、2の処理に戻る。

 

ファイル処理のアルゴリズム-代表的なアルゴリズム5

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

バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。

ファイル処理のアルゴリズム

ファイル処理とは、入力装置や外部記憶装置から読み取ったファイルを処理することです。処理対象のデータが主記憶装置の中にないため、以下のような手順が基本となります。

  1. 前処理: ファイルを開き、内容を主記憶装置の中に展開します。
  2. 主処理: 開いたファイルに対して、1レコードずつ所定の処理を行います。
  3. 後処理: ファイルを閉じます。

なお、ここでいうファイルは以下の定義となります。

  • レコード: 型の異なる幾つかの項目(=フィールド)を持つ
  • ファイル: 同じフィールドを持つレコードの集まり

ファイルの性質として、データ件数が膨大になることがあるため、ハードディスクなどの外部記憶装置に作業ファイルを作成し、中間結果を一時退避しながら処理をすすめることもある。その場合、外部記憶装置に十分な空き容量が必要となる。

ファイルの併合処理

ファイルの併合処理は、二つの整列済みのレコードの並びで構成されるファイルを、一つの整列されたレコードのファイルにする処理です。

例:ファイルAとBから、ファイルCを作成する

  1. 前処理: ファイルA、B、Cをそれぞれ開く。
  2. 主処理: ファイルA、Bを1レコードずつ読み込み、値の小さい方のレコードをファイルCに出力し、出力した方のファイルの次のレコードを読み込む。
    これを両ファイルの終端まで繰り返す。
  3. 後処理: ファイルA、B、Cをそれぞれ閉じる。

コントロールブレイク処理

コントロールブレイクとは、同じキー値を持つレコード軍の切れ目のことです。

コントロールブレイク処理とは、コントロールブレイクに出会ったらそのレコード群の処理を終了し、複数のレコード群の処理を反復することです。レコード群の中のレコードごとの処理の反復とあわせて、二重の反復になります。

例:社員の給与の部署ごとの合計

  1. 社員の給与一覧ファイルをあらかじめ部署で整列
  2. 部署が同じである間、社員毎の給与を計算用変数に加算していく。
  3. 違い部署コードが出現したら「コントロールブレイク」
    部署名と計算用変数の値を中間ファイルに出力し、計算用変数0で初期化。
  4. 2と3をファイルの終端まで繰り返す。
  5. ファイル終端まで来たら、部署名と計算用変数の値を中間ファイルに出力。中間ファイルの内容を処理の最終結果として書き出す。

ファイルの編集処理

ファイルの編集処理は、既存のファイルのデータを修正する処理です。

  1. 前処理: マスターファイルM、トランザクションファイルT、新マスターファイルNを開く。
  2. 主処理: ファイルMとファイルTからから1レコードずつ読み込み、キー値を比較して以下の処理を行う。これをファイル終端まで繰り返す。
    1. Tのキー値=Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルMとファイルTの次のレコードを読み込む。(データの更新)
    2. Tのキー値>Mのキー値なら、ファイルMのレコードをファイルNに出力し、ファイルMの次のレコードを読み込む。
    3. Tのキー値<Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルTの次のレコードを読み込む。(レコードの追加)
  3. 後処理: ファイルM、ファイルT、ファイルNを閉じる。

アルゴリズム設計

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

アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。また。アルゴリズムの設計方法を理解する。

用語例:再帰、分割統治法

アルゴリズム設計

アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。アルゴリズムを考える、設計する目的は、単に問題を解く方法を見つけるだけではなく、より効率的に、より速く、より簡単に問題を解くアルゴリズムを探す事が重要です。

同じ結果を出すための処理であっても、そのアルゴリズムが異なると、処理にかかる時間や、必要となるメモリの容量などが異なってきます。効率の良いアルゴリズムほど、処理時間が短くなり、メモリの消費量が少なく済むものなのです。

アルゴリズムの表現

プログラムを設計するときには、アルゴリズムを何らかの形式で表現します。

アルゴリズムの表現には、流れ図(フローチャート)、擬似言語、決定表(デシジョンテーブル)などの表現があります。

擬似言語

擬似言語は、人間が用いる自然言語とプログラム言語を混合した言語です。

アルゴリズムをできるだけ人間向きに自然言語で表現しつつ、反復や選択のように微妙な部分にプログラム言語を混用したりします。

プログラム言語と同様にテキストエディタで描くことが出来、図形を用いた表現に比べて修正が容易なのが特徴です。

テキストのみで表現した例

if a[mi] が a[i] より小なら then
   a[mi] と a[i] の値を交換する

図形処理の発達に伴い、情報処理技術者試験の分野では、以下のような簡易な図記号を混用したものを擬似言語と称しています。
(実際に情報処理技術者試験で使われたものを紹介します。)

擬似言語の仕様の例
実際に出題された擬似言語の記述例

決定表(デシジョンテーブル)

決定表(デシジョンテーブル)は、条件とその条件に対する処理の関係を4つの部分からなる表にして表現する技法です。

  1. 条件表題欄: 問題を処理するための条件を表します。
  2. 行動表題欄: 条件によって取りうる行動を表します。
  3. 条件記入欄: 条件表題欄の各条件について、当てはまる場合は[Y]、当てはまらない場合は[N]と記載します。条件判断を必要としない場合は[-]と記載します。
  4. 行動記入欄: 行動表題欄の各行動について、当てはまる場合に[X]と記載します。当てはまらない場合は空欄か[-]と記載します。

大きなプログラムの場合、「行動」の単位で「サブルーチン」化することがよく行われています。(=後述:分割統治法)

また、決定表を作成するときは、取りうる条件の組み合わせを網羅し、なおかつ全てのパターンに対して、必要な処理が行われるように設計することが重要です。

分割統治法

分割統治法とは、大きな問題を小さな問題に分割して、それぞれの問題ごとに解決に集中する方法です。

再帰のアルゴリズム、モジュール分割、オブジェクト指向設計などが分割統治法の具体的な例です。

また、ソートのアルゴリズムの中でも、マージソートやクイックソートは分割統治法に基づいて設計がなされています。

例えば、1からnまでの自然数の和を求めるアルゴリズムの場合、分割統治法を使わない場合と使った場合とでは、以下のように違った流れ図となります。

プログラミング(概要)

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

【基本情報・応用情報】
・プログラミング作法、コーディング基準を習得し、応用する。
・プログラム言語の文法の表記法を習得し、応用する。

【ITパスポート】
・プログラム言語とプログラミングの役割を理解する。

(1)プログラミング

1.プログラミング作法とコーディング基準 ITパスポート 基本情報 応用情報

プログラミング作法とコーディング基準の目的、効果、種類を理解する。また、プログラミング作法とコーディング基準を守らない場合に起こる弊害を理解する。

用語例:字下げ(インデンテーション)、ネストの深さ、命名基準、仕様禁止命令、プログラムの機能性・効率性・使用性・保守性の向上

2.プログラム構造 基本情報 応用情報

プログラムの信頼性、保守性の観点からプログラム構造を理解する。

用語例:モジュール分割、独立性、メインルーチン、サブルーチン、DLL

3.データ型 基本情報 応用情報

プログラム言語で使用される代表的なデータ型を理解する。

用語例:整数型、実数型、論理型、文字型、抽象データ型、構造型

4.Webプログラミング 基本情報 応用情報

WebサーバとWebクライアントの仕組みを理解し、Webサーバ、Webクライアントにおけるプログラムの役割と作成方法、Webアプリケーションプログラムを開発する環境を理解する。

用語例:サーバサイドプログラミング、リッチクライアント、Ajax、Apache、JSP(Java Server Pages)、HTML5技術(canvas、WebSocket、Geolocation APIほか)

(2)文法の表記法 基本情報 応用情報

プログラム言語の構文を定義するために、BNF等のメタ言語を使用することを理解する。

用語例:EBNF(拡張バッカス記法:Extended Backus Naur Form)

 

プログラミング作法とコーディング基準

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

プログラミング作法とコーディング基準の目的、効果、種類を理解する。また、プログラミング作法とコーディング基準を守らない場合に起こる弊害を理解する。

用語例:字下げ(インデンテーション)、ネストの深さ、命名基準、仕様禁止命令、プログラムの機能性・効率性・使用性・保守性の向上

プログラミング

プログラミングは、コンピュータを使って実行する作業手順を、前もって作っておく作業です。プログラムとは、コンピュータ用の作業手順書を、コンピュータに分かることが出書き出したもの、といえます。

人間が何かの仕事をこなすときは、まず段取りを考えて計画を立て、それに従って実際に仕事を進めます。これと同じように、コンピュータに仕事をさせるための段取りを書いたものがプログラムであり、プログラムを作成する作業がプログラミングです。コンピュータはプログラムに従って運用を行います。

プログラミング作法とコーディング基準の目的・効果

プログラミング作法は、プログラムを読む人にとって適切であろうと、一般的に指示された流儀のことです。対して、コーディング基準とは、チームや組織が定めたプログラムの書き方の基準です。いずれもプログラムの保守性を改善することが目的であり、読む人の労力や読み間違いを減らす効果があります。

同じ処理をするプログラムであっても、書き方の流儀や個人差が発生してしまいます。例えば、C言語で「変数aに1を加算する」という処理でも、以下のように異なる書き方が可能です。

  •  a++
  •  a = a + 1

専門家の間では、前者のほうが簡潔で、読み間違いが少ないとして支持されている、というのがプログラミング作法の例です。

また、コーディング基準は以下のような事項に関して定められることが多いです。

インデンテーション文の書き出し位置のインデンテーション(字下げ)の指針。
ネスト(入れ子)データ構造や制御構造の階層状態。ネストの深さを規制。
命名基準変数やモジュールの名前の付け方の指針。
使用禁止命令使用を推奨しない命令。(Goto文の禁止など)

インデンテーション

インデンテーション(字下げ)とは、プログラムの文の書き出し位置を、何文字分か右の方へ下げることです。これは、一般的なビジネス文書でも当てはまる事柄で、文章を読む時の人間の視線が左から右、上から下と流れることを踏まえたものです。

プログラムのインデンテーションは、例えば次のようにします。

  1. データ構造のネストを字下げで表す。
  2. 反復や選択などの制御構造のネストを字下げで表す。
  3. ラベルよりそれ以外の部分を字下げする。
  4. 字下げは半角文字4文字分ずつとする。
インデンテーションの例

label1:
    i=0;
    repeat
        a=b+c;
        ~~

このような字下げは、処理には関係ない表現なので、人間にとっての読みやすさを目的として、コーディング基準で規定するのが一般的です。

ネスト

データ構造や制御構造の階層状態をネスト(入れ子)といいます。ネストが深すぎると人間は把握することが難しくなります。

例えば、コーディング基準でネストの深さを4までに規制します。それを越えようとする場合は、一部を他のモジュール呼び出しや関数参照にしてネストが深くなるのを回避します。

命名基準

命名基準とは、変数、モジュール、関数、ラベルなどの名前の付け方の指針です。以下に、命名基準の例を示します。

  1. 元になっている業務や学術の用語と一致する名前を用いる。
  2. 配列の索引には、i,j,kを用いる。
  3. カウンタにはn,mを用いる。
  4. 長さを表す変数には、l,mを用いる。
  5. ポインタ変数には、p,qを用いる。
  6. 合計には、sを用いる。
  7. 一時的な変数には、t,wを用いる。

使用禁止命令

使用禁止命令とは、仕様が推奨されていない命令や文のことです。

例えば、goto文を禁止して、代わりに反復や選択の文で代替するほうが、読み手には読みやすくなります。

プログラム構造

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

プログラムの信頼性、保守性の観点からプログラム構造を理解する。

用語例:モジュール分割、独立性、メインルーチン、サブルーチン、DLL

プログラム構造

一つのプログラムは、いくつかの要素で構成されます。複数の要素で構成されるプログラムの形を、プログラム構造といいます。

モジュール

一つのプログラムを構成する要素を「モジュール」といいます。モジュールは、メインルーチン、サブルーチン、コンパイル単位などを総称する一般的な用語です。

モジュール構成にすることで、次のような効果が生まれます。

  • 人間の行っている作業の分解単位にモジュールを対応させることによって、わかりやすくなります。例えば、ATMを例に取ると、預入モジュール、引出しモジュール、残高照会モジュールといった対応をさせます。
  • 共通部分を「共通モジュール」とすることによって、プログラム全体の規模を減らすことが出来ます。
  • 分割統治法といって、モジュール単位に分割することで、モジュールごとの設計や試験、保守に集中することが出来ます。

メインルーチン

いくつかのモジュールで構成されるプログラムにおいて、最初に起動されるモジュールをメインルーチンといいます。「ルーチン」とは、「決められた仕事」という意味の言葉です。

メインルーチンの内容は、全体の処理の流れの概要を表す役割をはたすことが多いです。

サブルーチン

サブルーチンは、メインルーチンや他のサブルーチンから呼び出されるモジュールです。サブルーチンは2ヶ所以上から利用する共通ルーチンにすることが出来ます。また、別のプログラムで再利用することも出来ます。

Webプログラミング

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

WebサーバとWebクライアントの仕組みを理解し、Webサーバ、Webクライアントにおけるプログラムの役割と作成方法、Webアプリケーションプログラムを開発する環境を理解する。

用語例:サーバサイドプログラミング、リッチクライアント、Ajax、Apache、JSP(Java Server Pages)、HTML5技術(canvas、WebSocket、Geolocation APIほか)

Webプログラミング

Webプログラミングは、WWW(ワールドワイドウェブ)を閲覧する一環として利用するプログラムのプログラミング作業です。HTMLなどのマークアップ言語の機能や部品を用いたり、プログラム言語で書かれたモジュールを呼び出したりする形でプログラミングします。

初期のWWWは、資料を世界的に共用するという、静的な表現の役割をはたすものでしたが、次第に旅行業やインターネット通販などの動的な処理をすることが出来て、現在に至っています。

Webプログラミングには、閲覧者側のクライアントコンピュータ側で動作するプログラムを作ることと、提供者側のWebサーバ側で動作するプログラムを作ることがあります。

具体的な例としては、各種の会員制Webサイトや通販サイト、インターネットバンキングなどがあります。また、スマートフォンのアプリもある種のWebプログラムと言えるでしょう。

Webプログラミングにおけるサーバの役割

Webプログラミングにおける、サーバの役割は次のようなものがあります。

  • クライアントコンピュータへ送信するコンテンツの量を減らすために、大規模な処理はサーバ側で担当する。
  • プログラム言語で書かれたモジュールをアクセスする部分をサーバ側に置く。
  • サーバ側にあるファイルやデータベースにアクセスする部分をサーバ側に置く。

その他、サーバ側のプログラムは、アクセスが集中した場合の負荷や、セキュリティなどを意識して設計・プログラミングします。

Webプログラミングにおけるクライアントの役割

Webプログラミングにおける、クライアントの役割は次のとおりです。

  • HTMLなどのマークアップ言語や、小さな部品を用いてプログラミングします。
  • 閲覧者との対話の部分を担当します。

クライアント側のプログラムは、閲覧用に提供する文章や画像のを用いて、閲覧者にとって分かりやすくて手間の掛からない操作性になるように設計・プログラミングします。

 

プログラム言語(概要)

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

【応用情報】
・プログラム言語の種類、特徴、記述方法を修得し、応用する。
・プログラム言語の制御構造を修得し、応用する。
・プログラムの実行に必要な記憶域の考え方、利用法を修得し、応用する。
・プログラム言語が持つ構文規則、意味規則を修得し、応用する。

【基本情報】
・プログラム言語の種類、特徴、基本的な記述方法を修得し、適用する。
・C、COBOL、Java、アセンブラ言語のプログラム作成方法を修得し、適用する。
・表計算ソフトの活用方法を修得し、適用する。

【ITパスポート】
・プログラム言語とプログラミングの役割を理解する。

(1)プログラム言語の種類と特徴

1.プログラム言語の変遷と分類 ITパスポート 基本情報 応用情報

プログラム言語は、機械語、アセンブラ言語、高水準言語と発展してきたこと、プログラム言語の分類を理解する。

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

2.手続型言語 基本情報 応用情報

代表的な手続き型言語の特徴、記述方法を理解する。

用語例:Fortran、COBOL、PL/Ⅰ、Pascal、BASIC、C

3.オブジェクト指向言語 基本情報 応用情報

代表的なオブジェクト言語指向言語の特徴、記述方法を理解する。

用語例:Java、C++

4.スクリプト言語 基本情報 応用情報

代表的なスクリプト言語の特徴、記述方法を理解する。

用語例:ECMAScript、Perl、PHP、Python、Ruby

5.共通言語基盤(CLI:Common Language Infrastructure) 基本情報 応用情報

JIS X 3016(ISO/IEC 23271)で標準化されている、共通言語基盤の特徴、利用法を理解する。

用語例:共通言語基盤(CLI)

(2)プログラム言語の制御構造 応用情報

プログラム言語の基本的な制御構造、手続きと関数、逐次制御と並列制御を理解する。

用語例:連接、選択、繰り返し、手続き呼び出し、パラメータ、仮引数、実引数、値呼び出し、参照呼び出し、制御の流れ、再帰呼び出し、プロセス、疑似並列制御

(3)プログラム言語の記憶域 応用情報

プログラムの実行に必要な記憶域の考え方、利用法を理解する。

用語例:目的プログラムテキスト、定数、静的変数、自動変数、ヒープ、ガベージコレクション、ブロック、スコープ

(4)プログラム言語の記述 応用情報

プログラム言語が持つ構文規則、形式的意味論を中心とした意味規則を理解する。

用語例:プログラムの構成単位、文脈自由文法、BNF

(5)Cの知識と技術 基本情報

  • Cのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理などを行うプログラムの作成方法を修得し、適用する。
  • ライブラリ関数の利用方法を収録し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

(6)COBOLの知識と技術 基本情報

  • COBOLのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理、表操作を行うプログラムの作成方法を修得し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

(7)Javaの知識と技術 基本情報

  • Javaのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理などを行うプログラムの作成方法を修得し、適用する。
  • クラスの宣言方法、クラスをインスタンス化して利用する方法を修得し、適用する。
  • 継承、インタフェースを利用し、効率よくプログラミングを行う方法を修得し、適用する。
  • 例外処理、並列処理などの作成方法を修得し、適用する。

(8)アセンブラ言語(CASLⅡ)の知識と技術 基本情報

  • コンピュータシステムCOMETⅡの仕様を理解する。
  • CASLⅡのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理を行うプログラムの作成方法を修得し、適用する。
  • 表を使った処理、入出力処理を行うプログラムの作成方法を修得し、適用する。
  • スタック、およびスタックを用いたサブルーチンコールの仕組みと用法を修得し、適用する。

(9)表計算ソフト 基本情報

  • 表計算ソフトが持つ計算、集計などの機能を修得し、適用する。
  • 関数の種類、使い方を修得し、適用する。
  • マクロの作成方法を修得し、適用する。
  • 業務処理における表計算ソフトの活用方法を修得し、適用する。

 

プログラム言語の分類と概要

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

プログラム言語は、機械語、アセンブラ言語、高水準言語と発展してきたこと、プログラム言語の分類を理解する。

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

プログラム言語

コンピュータに処理をさせるには、処理の手順を司令として与える必要があります。この指示書をプログラムといい、プログラム言語によって書かれています。

以下に、代表的なプログラミング言語をいくつか紹介します。なお、「基本情報」アイコンがついているものは、基本情報技術者試験の午後の問題で出題されるプログラム言語です。

C  基本情報
パソコンやワークステーションのアプリケーションソフト、デジタル家電やIoT機器など、いわゆる「組み込み系」の開発で用い要られています。
C++
C言語をベースとして、オブジェクト指向の概念を取り入れた言語です。UNIXやLinuxのサーバ内部のプログラムや、Windowsアプリケーションで用いられています。
COBOL  基本情報
10進数の扱いを得意とするプログラミング言語で、金融分野などの汎用コンピュータで利用されている、事務処理用のプログラム言語です。
Java 基本情報
C++をベースとして開発され、インターネット環境などで利用される言語です。「Java仮想マシン」という仕組みを使い、OSや機種といったプラットフォームの違いにかかわらず動作できるという特徴があります。
Visual Basic
GUI環境でのWindowsアプリケーションソフト開発に用いられる言語です。
C#
主にWindowsアプリケーションソフト開発に用いられる言語です。.Net Frameworkという、共通言語基盤(CLI)上で動作するプログラム言語です。
Fortran
主に科学技術系の計算処理で用いられるプログラム言語です。

機械語と言語プロセッサ

コンピュータが直接理解できる命令は、2進数で表現された機械語です。しかし、機械語は機種によって異なり、かつ機械語は人の手で記述するのは難しいので、より人間の言葉に近いプログラム言語で記述したもの(ソースコード)を機械語に翻訳してから動作させます。

このソースコードを機械語に翻訳する機能を「言語プロセッサ」といいます。翻訳の方法には、機械語と1対1に対応する疑似命令を機械語に変更する「アセンブラ」、ソースコード全文を一括で機械語に翻訳する「コンパイラ」、1行ずつ逐次翻訳しながらプログラムを実行する「インタプリタ」があります。

コンパイラ

コンパイラは、プログラム言語で書かれたソースコードを、一括して機械語のオブジェクトやプログラムに作り変えるソフトウェアです。

CやCOBOL等の高水準言語はコンパイラで変換されます。

インタプリタ

ソースコードを1行ずつ解析しては機械語に変換し、実行するという動作を繰り返すもので、逐次変換ともいいます。

以前のVisual Basicはインタプリタで実行されていました。

スクリプト言語

コードを記述するだけで、コンパイルの必要なく動作させることが出来る、スクリプトと呼ばれるプログラムがあります。これを記述するプログラム言語を、スクリプト言語と言います。

代表的なものには、PerlやPHP、JavaScriptなどがあります。これらはWebページに動きを加えたり、Webサーバ上でデータを計算してWebブラウザに送るなどの機能を作る時に用いられています。

以下に、いくつかスクリプト言語の特徴を紹介します。

Perl(パール)
Perlは、テキスト処理から機能を拡大してきた、スクリプト言語です。実用性を重視していて、C言語などの各種の言語を参考にして、多様な機能を持ちます。
Perlを処理するためのソフトウェア、”perl”はフリーソフトウェアとして提供されています。 
記述されたスクリプトの提供形態は、Webページに動的な性質を持たせる、CGI(Common Gateway Interface)という機能の形をとることが多いです。
PHP(Hypertext Preprocessor)
Webページに動的な機能を持たせるためのスクリプト言語および言語処理ソフトウェアの名称です。
PHPで書かれたスクリプトはWebサーバ側でHTML形式のマークアップ言語表現に変換されるので、閲覧するクライアントコンピュータ側には、PHPのソフトウェアは必要ありません。
Python(パイソン)
オブジェクト指向型のスクリプト言語です。Perlとは対象的に、言語そのものの機能は少なめに限定されています。そのかわり、多様な標準ライブラリを提供してカバーしています。
見た目のブロック構造と、実際の制御が同じで、視覚に訴えるソースコードが強制されている言語です。
Ruby(ルビー)
日本人が発案したオブジェクト指向型のスクリプト言語です。テキスト処理や機能の多様性という性質はPerlに近く、オブジェクト指向型という点でPythonと比較されます。

 

その他の言語(概要)

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

【応用情報・基本情報】
・代表的なマークアップ言語の種類、特徴、記述方法を修得し、応用する。
・コンピュータで使用されるその他の言語を修得し、応用する。

【ITパスポート】
・代表的なマークアップ言語の種類とその基本的な使い方を理解する。

(1)マークアップ言語 ITパスポート 基本情報 応用情報

1.HTML

Webページの作成に利用されるHTMLの特徴、基本的な記述方法を理解する。

用語例:開始タグ、終了タグ、DTD(文書型定義:Document Type Definition)、SGML

2.XML

HTMLの機能に加えて、独自にタグを定義できる機能を備え、主にインターネットを介したデータ交換に利用されているXMLの特徴、基本的な記述方法を理解する。

用語例:DOM(Document Object Model)、SOAP(Simple Object Access Protocol)、SVG(Scalable Vector Graphics)、SAX(Simple API for XML)、XML Schema

3.XHTML

HTMLをXMLで再定義したマークアップ言語であるXHTMLの特徴、基本的な記述方法を理解する。

用語例:XHTML Basic、XHTML Modulation

4.スタイルシート

HTMLやXMLなどマークアップ言語の構造と表示形式を分離するための仕様である、スタイルシートを理解する。

用語例:CSS(Cascading Style Sheets:段階スタイルシート)、XSL(Extensible Stylesheet Language:拡張可能なスタイルシート言語)

(2)その他の言語 基本情報 応用情報

オブジェクト指向設計のための表記法である、UMLやその他の言語を理解する。

用語例:クラス図、シーケンス図、オブジェクト図、コラボレーション図、ステートチャート図、操作、属性、ロール名、ユースケース図、SDL(Specification and Description Language)、ADL(Architecture Description Language:アーキテクチャ記述言語)、データ定義言語(DDL:Data Definition Language)

 

その他の言語

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

・代表的なマークアップ言語の種類、特徴、記述方法を修得し、応用する。
・コンピュータで使用されるその他の言語を修得し、応用する。

 

 HTML

HTML(HyperText Markup Language)はインターネットのWebページの記述に使われる言語です。言語といっても、プログラムを組むものではなく、文章の中に編集用の指定を織り交ぜて記述できる、マークアップ言語の一種です。

HTMLでテキスト文書を描くときには、ページの構造や書式、レイアウトに関する指定を、タグという形式で挿入することが出来ます。

HTMLで記述したテキストは、HTMLファイルとして保存します。ファイル名の末尾には、”.html”などの拡張子をつけます。

HTMLのタグ

HTML文書の基本構造は、ヘッダ部とボディ部からなります。ヘッダ部には文書のタイトルなどを、ボディ部には文書の内容を記述します。

HTMLでは、編集したいテキストの前後に”<>”で囲んだタグを挿入します。開始タグ(<タグ名>)から終了タグ(</タグ名>)までが、そのタグの有効範囲です。

タグ名概要
<html>~<html>HTML文書であることを宣言するタグ
<head>~<head>文書のヘッダ部を示す。ヘッダ部はタイトルなどを記述する場所で、本文には含まれない。
<body>~<body>文書のボディ部を示す。ボディ部は、ブラウザ上で実際にWebページとして表示される本文を記述するところ。
<img>画像を表示する。<img src="~~">のように、src属性を使って表示する画像ファイルのURLを指定する。
<a>~<a>他の文書ファイルへのリンクを示す。href属性に参照先ファイルのURLを指定する。
Webページ上で、このタグに囲まれた部分をクリックすることで、参照先に移動することが出来る。
<br>文章の改行を指定する。

タグのネスト

タグを入れ子にすると、階層的に書式を指定することが出来ます。内側のタグほど指定が優先されます。

以下に<font>というタグを使って3段階の入れ子の形で指定した例を示します。

ハイパーリンク

<a>タグや<img>タグのような、他のHTML文書や画像ファイルを参照して表示するタグを挿入すると、文書の中から関連のある別のファイルを直接開いてみることが出来るようになります。これをハイパーリンクといいます。

こういったハイパーリンクを含むテキストをハイパーテキストといいます。

ブラウザ

HTML文書を閲覧するためのソフトウェアとブラウザ(Webブラウザ)といいます。HTMLのタグが指定するレイアウトにしたがい、画像などを含む文書として表示します。

Google ChromeやInternet Explorer、Firefoxなどの製品が代表的です。

なお、HTMLの仕様は、WWWコンソーシアム(W3C)で標準化されていますが、タグの中にはブラウザ側が独自に拡張したものもあり、それらのタグをHTML文書内で使うと、表示結果がブラウザの種類によって違ってしまう場合があります。

SGML

SGML(Standard Generalized Markup Language)は論理構造を持つ文書を記述するために、ISOで制定されたマークアップ言語です。SGML文書同士の参照関係と階層構造を、文書中に定義する機能があります。

このSGMLを元にして、HTMLやXMLが作られました。

XML

XML(Extensible Markup Language)は、HTMLのような使い勝手の良さだけでなく、SGMLのような拡張性も備えたマークアップ言語です。汎用性が高く、ユーザが独自にタグを定義して使用することが出来るのが特徴です。

複雑なデータをインターネット経由で交換することが出来るため、企業間の電子商取引などに欠かせない技術となっています。

XHTML

HTMLをXMLの仕様に準拠した形で再定義したマークアップ言語です。HTMLの言語仕様が拡張によってXMLと整合しきれない部分があるのを修正したものです。

言語としてはHTMLとほぼ同じですが、改めて書式を幻覚に規定し、各ブラウザによる表示の差などを減らしました。

スタイルシート

スタイルシートは、スタイル言語で記述された文書の内容以外の様式の定義です。HTMLなどのマークアップ言語や組版系のソフトウェアとともに利用されます。

マークアップ言語や組版系のソフトウェアは、文書の内容も様式も指定できますが、スタイルシートを用いて文書の内容・構造と様式・デザインを分離することによって、作業を分業したり、保守性を向上させたり、様式・デザインを再利用したりするのに役立ちます。

CSS

CSS(Cascading Style Sheets)は、スタイルシートを記述するための代表的なスタイル言語です。

以前は、文字の色や大きさ、フォントといった見栄えに関する記述も全てHTMLで行っていました。しかし、文書構造と見栄えを分離することにより、保守性が向上し、開発も分担しやすくなります。

現在では、文書の内容はHTML、見栄えに関してはCSSで定義するのが一般的です。

XSL

XSL(Extensible Stylesheet Language)はマークアップ言語XMLに準拠したスタイル言語です。

UML(Unified Modeling Language)

その他の言語としては、UMLがあります。「言語」と名前はついていますが、他の言語とは大きく異なり、UMLはモデリング技法・表記法と考えるべきものです。

UMLはオブジェクト指向のソフトウェアを設計・開発するための統一表記法です。オブジェクト指向に基づいてシステムを図解したり、モデル化したりする際の表記法が定められています。

UMLで定義されている図解法は、大きく次の3種類にわけられます。

構造図システムの静的な構造を表すクラス図など
振る舞い図システムの動的な変化や相互作用を表すユースケース図など
実装図ソフトウェア実装時の構成や配置を表す配置図など

C言語の知識と技術(概要)

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

【基本情報】

  • Cのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理などを行うプログラムの作成方法を修得し、適用する。
  • ライブラリ関数の利用方法を収録し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

1. C の基本的なプログラム

C の基本的なプログラムを作成する。

修得項目: main 関数,printf 関数,標準出力,注釈,ヘッダ など

2.数値の計算

四則演算を使ったプログラムを作成する。

修得項目:四則演算子,変数,式,整数の計算,型変換(キャスト),実数の計算,データ型のビット幅,増分演算子,減分演算子,比較演算子 など

3.選択型のプログラム

条件式を使って条件分岐するプログラムを作成する。

修得項目:等価演算子,関係演算子,論理演算子,代入演算子,if 文,switch 文 など

4.反復型のプログラム

繰返し文を使ったプログラムを作成する。

修得項目: while 文,do 文,for 文 など

5.ビット演算

ビット単位の演算子を使ったプログラムを作成する。

修得項目: 符号なし整数型,ビットシフト など

6.入力処理

標準入力を使ったプログラムを作成する。

修得項目:scanf 関数,空白類文字,アドレス演算子 など

7.配列

配列を使ったプログラムを作成する。

修得項目: 1 次元配列,2 次元配列 など

8.文字処理

文字列を処理するプログラムを作成する。

修得項目: putchar 関数,puts 関数,getchar 関数,gets 関数,文字の入出力,文字列の入出力,文字列リテラル,ナル文字 など

9.ポインタ

ポインタを使ったプログラムを作成する。

修得項目: ポインタの配列,アドレスの加減算 など

10.関数

関数を作成し,関数を使ったプログラムを作成する。

修得項目: 関数原型,void 型,再帰呼出し など

11.ライブラリ関数

ライブラリ関数を使ったプログラムを作成する。

修得項目:プリプロセッサ,#include,#define,前処理指令 など

12.記憶域クラス指定

記憶域クラス指定子を使ったプログラムを作成する。

修得項目:自動記憶域期間をもつ変数,静的記憶域期間をもつ変数,register,typedef,記憶域期間,外部定義 など

13.構造体

構造体を使ったプログラムを作成する。

修得項目:構造体の配列,自己参照する構造体,共用体 など

14.ファイル処理

ファイル処理を行うプログラムを作成する。

修得項目:シーケンシャルなファイル処理,ランダムなファイル処理,ストリーム,バッファリング など

 

 

COBOLの知識と技術(概要)

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

【基本情報】

  • COBOLのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理、文字処理、表操作を行うプログラムの作成方法を修得し、適用する。
  • ファイル処理を行うプログラムの作成方法を修得し、適用する。

1. COBOL の基本的なプログラム

COBOL の基本的なプログラムを作成する。

修得項目: 部(DIVISION),節(SECTION),見出し部,環境部,データ部,手続部,ACCEPT文,DISPLAY 文,データの構造,データ項目,データの転記,データの編集,正規法,注釈 など

2.数値の計算

四則演算を使ったプログラムを作成する。

修得項目:計算文,算術式,作業場所節 など

3.選択型のプログラム

条件式を使って条件分岐するプログラムを作成する。

修得項目:IF 文,比較演算子,正負条件,字類条件,論理演算子,入れ子になった分岐,多分岐,GO TO 文,STOP 文 など

4.反復型のプログラム

反復型の制御文を使ったプログラムを作成する。

修得項目: 回数を指定する反復実行,条件を指定する反復実行,入れ子になった反復実行,PERFORM 文 など

5.文字処理

文字処理を行うプログラムを作成する。

修得項目:文字列の部分参照,文字列の検査,文字列の置換,文字列の連結,文字列の分解 など

6.表操作

表操作を行うプログラムを作成する。

修得項目:表の概念,1 次元の表,多次元の表,指標,初期値の設定,逐次探索,非逐次探索,OCCURS 句,SEARCH 文 など

7.ファイル処理の基本

順ファイルの入出力操作を行うプログラムを作成する。

修得項目: ファイルの入出力,帳票の出力,データの集計,コントロールブレーク,マッチング など

8.ファイル処理の応用

相対ファイル,索引ファイルを使ったプログラムを作成する。

修得項目: レコードの書換え,レコードの削除,レコードの位置づけ,整列,併合 など

 

 

Javaの知識と技術(概要)

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

【基本情報】

  • Javaのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理などを行うプログラムの作成方法を修得し、適用する。
  • クラスの宣言方法、クラスをインスタンス化して利用する方法を修得し、適用する。
  • 継承、インタフェースを利用し、効率よくプログラミングを行う方法を修得し、適用する。
  • 例外処理、並列処理などの作成方法を修得し、適用する。

1. Java の基本的なプログラム

Java の基本的なプログラムを作成する。

修得項目: クラス,メソッド,main メソッド,標準出力,注釈,javadoc コメント など

2.数値の計算

四則演算を使ったプログラムを作成する。

修得項目:データ型,型変換(キャスト),変数,配列,四則演算子,式,代入演算子,比較演算子,増分演算子,減分演算子,シフト演算子 など

3.選択型のプログラム

条件式を使って条件分岐するプログラムを作成する。

修得項目:if 文,switch 文 など

4.反復型のプログラム

反復型の制御文を使ったプログラムを作成する。

修得項目: while 文,do 文,for 文,拡張for 文 など

5.クラスとインスタンス

クラスを定義し,インスタンス化して使用するプログラムを作成する。

修得項目: インスタンス変数,インスタンスメソッド,アクセス修飾子,参照型変数,隠蔽(いんぺい),コンストラクタ,オーバロード,this,クラス変数,クラスメソッド,文字列クラス,パッケージ,完全限定名,super,単純名,import 宣言,クラス修飾子 など

6.差分プログラミング

既存のクラスの機能を拡張するプログラム,インタフェースを利用して機能を追加するプログラムを作成する。

修得項目:継承,final,extends,スーパクラス,サブクラス,Object,implements,キャスト,アップキャスト,ダウンキャスト,instanceof,オーバライド,ダイナミックバインド,クラスライブラリ,抽象クラス,抽象メソッド,基底クラス,派生クラス など

7.例外処理

例外処理を行うプログラムを作成する。

修得項目:try 文,throw 文 など

8.並列処理

並列処理を行うプログラムを作成する。

修得項目: スレッド,synchronized 修飾子,wait( ),notify( ) など

9.コレクションと総称

コレクションを使ったプログラムを作成する。

修得項目: add( ),remove( ),List,Set,Map,Stack,型引数 など

10.入れ子クラス

入れ子クラスを使ったプログラムを作成する。

修得項目: メンバクラス,メンバインタフェース,局所クラス,匿名クラス など

11.列挙

列挙型を使ったプログラムを作成する。

修得項目:列挙定数,final 変数 など

 

 

アセンブラ言語(CASLⅡ)の知識と技術(概要)

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

【基本情報】

  • コンピュータシステムCOMETⅡの仕様を理解する。
  • CASLⅡのプログラムの作成方法の基本を修得し、適用する。
  • 演算処理、制御処理を行うプログラムの作成方法を修得し、適用する。
  • 表を使った処理、入出力処理を行うプログラムの作成方法を修得し、適用する。
  • スタック、およびスタックを用いたサブルーチンコールの仕組みと用法を修得し、適用する。

1. COMETⅡ

COMETⅡを構成するレジスタ,命令形式を理解する。

修得項目: GR0~GR7,SP,PR,FR,OF,SF,ZF,注釈

2.CASLⅡの基本的なプログラム

CASLⅡの基本的なプログラムを作成する。

修得項目:START,END,DS,DC,LD,ST,LAD,実効アドレス

3.算術演算,論理演算

算術演算命令,論理演算命令を使ったプログラムを作成する。

修得項目:ADDA,ADDL,SUBA,SUBL,AND,OR,XOR

4.選択と反復処理

比較演算命令,分岐命令を使って選択型,反復型のプログラムを作成する。

修得項目: CPA,CPL,JPL,JMI,JNZ,JZE,JOV,JUMP

5.シフト演算

シフト演算命令を使ったプログラムを作成する。

修得項目: SLA,SRA,SLL,SRL

6.表を使った処理

表(配列)を使ったプログラムを作成する。

修得項目:GR1~GR7,指標レジスタ

7.入出力処理

マクロ命令IN,OUT を使って入出力処理を行うプログラムを作成する。

修得項目: IN,OUT

8.スタック

スタック操作を行うプログラムを作成する。

修得項目: PUSH,POP,RPUSH,RPOP,CALL,RET

 

表計算ソフト(概要)

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

【基本情報】

  • 表計算ソフトが持つ計算、集計などの機能を修得し、適用する。
  • 関数の種類、使い方を修得し、適用する。
  • マクロの作成方法を修得し、適用する。
  • 業務処理における表計算ソフトの活用方法を修得し、適用する。

1. ワークシート

基本的なワークシートを作成する。複数のワークシート間での参照,集計を行う。

修得項目: セル,空白セル,セル番地,セル範囲,ワークシート参照,相対参照,絶対参照 など

2.式

定数,セル,演算子,関数などを組み合わせて式を作成する。

修得項目:算術式,文字式,論理式,単項演算子(+,-),算術演算子(+,-,*,/,^),比較演算子(=,≠,>,<,≧,≦) など

3.関数

関数と数値,関数とセル,関数と関数などを組み合わせて式を作成する。

修得項目:引数,関数の入れ子,合計,平均,標本標準偏差,母標準偏差,最大,最小,IF,個数,条件付個数,整数部,剰余,平方根,論理積,論理和,否定,切上げ,四捨五入,切捨て,結合,順位,乱数,表引き,垂直照合,水平照合,照合検索,照合一致,条件付合計 など

4.マクロ

変数,セル変数,配列,演算子,関数を使ってマクロを作成する。

修得項目: 変数,セル変数,絶対表現,相対表現,配列,宣言,注釈,代入,選択処理,繰返し処理 など

5.表計算ソフトの応用

会計処理,成績処理などの業務処理に表計算ソフトを適用する。具体的には,対象業務を把握し,業務処理のアルゴリズムを表計算ソフトで実装する。