第1章

基礎理論
IT について学ぶときに知っておくと役に立つ分野，それが基礎理論です。直接目にする機会は少ないですが，基礎の理論なので，いろいろな技術の仕組みや，本質的なことを知るときには役に立ちます。
内容は「基礎理論」と「アルゴリズムとプログラミング」の二つです。
基礎理論では，離散数学や応用数学などの数学や，情報・通信・計測制御に関する理論について学びます。アルゴリズムとプログラミ
ングでは，定番のデータ構造やアルゴリズム，プログラム言語やその他の言語でのプログラミングについて学びます。

1-1

基礎理論

⿇⿇1-1-1 離散数学
⿇⿇1-1-2 応用数学
⿇⿇1-1-3 情報に関する理論
⿇⿇1-1-4 通信に関する理論
⿇⿇1-1-5 計測・制御に関する理論
1-2 アルゴリズムとプログラミング

⿇⿇1-2-1 データ構造
⿇⿇1-2-2 アルゴリズム
⿇⿇1-2-3 プログラミング
⿇⿇1-2-4 プログラム言語
⿇⿇1-2-5 その他の言語

演習問題

⿇⿇1-3
⿇⿇1-4

演習問題
演習問題の解答

22

第1章

基礎理論

1-1 基礎理論
IT 全般を理解する上で基礎となる理論です。基礎理論を理解していると，コンピュータやシステムの仕組みが分かるだけでなく，ネットワークやデータベース，セキュリティなどの応用技術の学習にも役立ちます。

勉強のコツ

基礎理論の分野は，応用情報技術者試験では応用的な内容が出題されます。理解するためには，前提として
基本情報技術者試験レベルの習得が必要です。
本書の内容が難しく感じられる場合には，次に紹介する動画などを利用して，先に基本について学んでおき
ましょう。

1-1-1

離散数学

離散数学とは，とびとびの数字を扱う数学です。コンピュー
タは，データを 0 か 1の 2 種類の値（ディジタル）でしか表現できません。その制限の中でどのようにデータを変換して表現す
るかに，離散数学は活用されています。

基数変換
基数とは，数を表現するときに，けた上がりの基準になる数です。例えば，10 進数では基数が 10なので，0，1，2，3，4，5，6，

動画

基礎理論の分野についての解説動画を以下で公開しています。
http://www.wakuwaku
academy.net/itcommon/1
本書では取り扱っていない
基本的な内容，特に基数変換などの基本情報技術者試
験レベルの内容についても詳しく解説しています。
本書の補足として，よろし
ければご利用ください。
参考

補数の考え方は，実は小学校のときに習っています。
10 進数では，1の補数は 9，
2 の 補 数 は 8，3 の 補 数 は
7……というかたちで覚えて，引き算で使ったと思います。これを 2 進数に応用したのが，2の補数です。

7，8，9ときて10になるところでけた上がりをして10になります。
同じように，2 進数では基数が 2 なので，0，1ときて 2 になるところでけた上がりをして10になります。
2 は，10 進数では次のように表現で
例えば，2 進数の（110.01）

きます。なお，下付きの数字は基数を表します。
2 ＝ 1 × 22 ＋ 1 × 21 ＋ 0 × 20 ＋ 0 × 2−1 ＋ 1 × 2−2（110.01）＝（6.25）10負の数の表現（補数表現）
コンピュータ上で負の数を表す場合は，補数という考え方を使います。補数とは，ある自然数に足したときにけたが一つ上が2の2のる最も小さい数です。例えば，8けたの 2 進数（00001101）2
補数は，足すことでけたが上がって9けたの最小値（100000000）になる値です。計算すると次のようになります。
		

00001101

元の数

10
（13）

＋ 11110011

2の補数

10
（−13）

		 100000000

けたが一つ上がる最小値1-1

この補数を用いることによって，引き算を足し算で表現できま
10 −
10 を計算するときには，次のように変す。例えば，
（25）
（13）

換します。
10 −
10 ＝
10 ＋
10
（25）
（13）
（25）
（−13）

8 けたの 2 進 数に変 換 すると，先ほどの 2 の補 数 表 現より
2＝
10 なので，次のようになります。
（11110011）（−13）

00011001

10
引かれる数（25）＋11110011

102の補数 （−13）

		100001100

/

		

10
計算結果 （12）あふれたけた（9けた目）は無視される
引き算を足し算に直すことで計算の種類を減らすことができ，計算に必要なコンピュータの回路を単純にできます。

基礎理論

過去問題をチェック負の数の表 現については，
午前問題の定番です。
応用情報技術者試験
平成21年秋 午前 問1，
平成25年春 午前 問1，
平成 25 年秋 午前 問3で出題されています。
午前の最初の問題で出題されることが多いので，この問題が解けると試験で調子が出やすくなります。

発展

コンピュータで数を表現するときは，あらかじめ「けた数」を決めておく必要があります。そして，決めたけた数からあふれたデータは，格納場所がないのでなかったものとして扱われます。

なお，2 の補数の求め方としては，各ビットを反転して，それに1を加えることによって，簡単に計算することができます。

小数の表現
小数をコンピュータ内部で表現する方法には，次の 2 種類があります。
・固定小数点数表現

関連・浮動小数点数表現
固定小数点数表現とは，あらかじめ小数点の位置を決めておき，その位置に合わせてデータを表現する方法です。例えば，22 を表現するとき，8 けた分の場所を確保し，4 け
進数の（110.01）

た目の後を小数点にすると決めると，次のようになります。
0

1

1

0

0

1

0

0

小数点を，4けた目の後に固定する
固定小数点数表現

プログラム言語では，型の宣言によって，どちらの小数点数表現が使われるかが決まります。
C 言語や C++，Java 言語で用いられるfloat 型，double
型は，浮 動 小 数 点を表 す
データ型です。
COBOL など 事務処 理系の言語では，固定小数点数表
現が使われることが多いで
す。

23

1

24

第1章

基礎理論

小数点の位置が決まっているためデータの解釈は簡単なのですが，その分，表現できる数値の範囲が限られてしまいます。例
えば，前ページの図の 8 けたで数値を表現すると，最大値でも2＝10 となり，大きな数は表現できません。
（1111.1111）（15.9375）

それに対し浮動小数点数表現では，指数部と仮数部を使って数値を表現します。例えば，10 進数の 0.000603 は，10 進数の浮動小数点数表現を使うと次のように表されます。
0.000603 ＝ 6.03 × 10 −4
仮数部

指数部

浮動小数点数表現

2進数の場合には，指数部を2のべき乗のかたちにし，符号部（数値がプラスなら0，マイナスなら1）と合わせて表現します。
具体的な方法はいろいろありますが，決められた形式のルールに従って数値を変換します。正しい形式に変換するこの作業を正規化と呼びます。
実際の問題を例に，正規化の作業を行ってみましょう。

問題

動画

この問をはじめ，問題の解説動画も多数公開しています。
http://www.wakuwaku
studyworld.co.jp/blog/
youtube_ap
問題の URLリストを上記にまとめていますので，文章で理解するより動画のほうが分かりやすいという場合
は，併せてご利用ください。

図に示す 16 ビットの浮動小数点形式において，10 進数 0.25
を正規化した表現はどれか。ここで，正規化は仮数部の最上位けたが 1 になるように指数部と仮数部を調節する操作とする。
1 ビット 4 ビットse

11 ビットf

小数点の位置s：仮数部の符号（0：正，1：負）
e：指数部（2 を基数とし，負数は 2 の補数で表現）
f ：仮数部（符号なし 2 進数）

1-1

ア

0

0001

10000000000

イ

0

1001

10000000000

ウ

0

1111

10000000000

エ

1

0001

10000000000

251（平成 22 年春 応用情報技術者試験 午前 問2）

解説
この問題の正規化では，仮数部の最上位けたが 1になるように指数部と仮数部を調節します。つまり，10 進数の 0.25を 2 進数に直すと，（0.25）（0.01）
10 ＝2 となるので，これを仮数部の最上位けたが 1になるように浮動小数点数表現にすると，次のようになります。
（0.01）（0.1）
2＝
2 ×2 −1

仮数部

基礎理論

指数部

また，指数部は（−1）の表記
10 なので，問題文中のe （指数部）に「2を基数とし，負数は 2 の補数で表現」とあり，またe は 4ビットで表されることから，（1）（0001）
10 ＝
2 を2の補数で表現します。
（−1）（10000）（0001）（1111）
10 ＝
2−
2＝
2
したがって，浮動小数点数表現で（0.25）
10 を表すと，s ：仮数部の符号… …… 正の数なので「0」e ：指数部… …………… 先ほど求めた2 進数「1111」
f ：仮数部… …………… 1だが，後ろに0を補って「10000000000」となり，合わせて「0 1111 10000000000」となります。
≪解答≫ ウ

26

第1章

基礎理論

基礎をしっかり学ぶ

勉強のコツ

基礎理論はもともと数学の1分野なので，理解するた
めには数学の知識も必要になります。
といってもそんなに難しいものではなく，累乗や確率，
統計くらいまでの高校で学
ぶ数学の基礎が分かれば十分です。数学的な考え方が分かると他の分野でもいろ
いろ生かせますし，試験問
題を解くときにもとても助
けになります。
時間があるときに一度，ひととおり数学の勉強をやり直してみることもおすすめします。特に，応用情報技術者試験で終わらせず，より高度な試験を受けようとされている方はぜひチャレ
ンジしてみてください。

応用情報技術者試験は，その名のとおり，「応用」的なことを問われる試験です。基本情報技術者試験レベルの「基礎」を基に，実務に応用できるような使えるスキルを身に付けるのが試験本来の姿です。
試験範囲はほとんど同じなので，基本情報技術者試験の内容は半分くらいはそのまま使えます。その分，応用情報技術者試
験の勉強は，基本情報技術者試験の内容を理解していないと分からない部分が多くあります。逆に，基本的な内容をきちんとマスターしていれば，積み重ねるのはそれほど難しくありません。
ですから，応用情報技術者試験の勉強をとても難しく感じる
場合には，まずは基本情報技術者試験レベルに戻り，それも難しければ IT パスポート試験レベルの内容を復習してみましょう。
特に，テクノロジ系の基礎理論などの分野は基本の内容がとても大切なので，しっかり基礎から学ぶことが必要です。本書の内容は応用情報技術者試験レベルに合わせていますが，基本情報技術者試験レベル以下の基本的な内容については公開動画でフォローを行っていますので，よろしければご利用ください。
また，第 1 章は「基礎理論」というタイトルですが，この“基礎”という言葉には，「コンピュータ，IT 全般の基礎」という意味合いが込められています。基礎理論の内容は直接仕事で役立つよ
うには感じられにくいですが，実は結構関係があるのです。基
礎理論の内容を理解しておくことで，他の分野の勉強がスムーズになったり，トラブルの本当の原因が理解できたりします。
急いで合格しようと焦らず，まずはしっかり，基礎から身に付けていきましょう。

1-1

基数変換と誤差コンピュータで数値を表現する際には，誤差に注意する必要があります。例えば小数の場合は，10 進数から2 進数へ基数変換するだけでも誤差が出ることがあります。
10 進数の 0.4を2 進数に変換する場合を考えてみましょう。0.4という数は有限のけたで表されているので，こういった数のこと
を有限小数と呼びます。0.4 を 2 進数に変換すると，割り切れず循環する，次のような数になります。
●

●

10 ＝
2＝
2
（0.4）
（0.01100110011001100110）（0.0110）

基礎理論

発展

コンピュータ内部では，10進小数から2 進小数への基
数変換が自動的に行われることがあります。例えば，C
言 語 や Java など で float 型
やdouble 型を使うと，デー
タは 2 進数で格納されるので 数 値に少し誤 差 が 出ます。そうすると予期しない
計算ミスが発生することがあるので，注意が必要です。

有限小数で表せない小数を無限小数といいますが，そのうち上記のように 0110 の部分が繰り返される小数のことを循環小数と呼びます。0.4という有限小数は，10 進数を 2 進数に変換しただけで循環小数となるのです。
逆に 2 進数から10 進数への基数変換の場合には，有限小数を変換すると必ず有限小数になります。

数値演算と誤差コンピュータでは限られたけた数でデータを表現するので，いろいろな誤差や，表現しきれないことが出てきます。具体的には，
次のようなことで誤差が発生します。

①けた落ち
値がほぼ等しい二つの数値の差を求めたとき，有効数字のけた数である有効けた数が減ることによって発生する誤差です。
		

256.432

有効けた数 6けた

− 256.431

有効けた数 6けた

		

0.001

有効けた数が 1けたになってしまう！

②情報落ち
絶対値が非常に大きな数値と小さな数値の足し算や引き算を行ったとき，小さい数値が計算結果に反映されないことによって発生する誤差です。
		

256.432＋

0.000011

		

256.432011

有効けた数 6けた
非常に小さい数
有効けた数の関係で無視される

間違えやすいけた落ちと情報落ちは混同されやすいので，正確に覚えておきましょう。有効けた数が減るのがけた落ち，
小さい数値の情報が落ちるのが情報落ちです。

27

1

28

第1章

基礎理論

③丸め誤差
指定された有効けた数で演算結果を表すために，切り捨て，切り上げ，四捨五入などで下位のけたを削除することによって発生する誤差です。

用語与えられた数をすべて加えることを総和といい，Σ（シグマ）という記号で表されます。
この総和を行う足し算の数
が 有 限 で はなく，無 限 個の演算を行うことを無限級数，または単に級数と呼びます。

④打ち切り誤差無限級数で表される数値の計算処理を有限の回数で打ち切ったことによって発生する誤差です。

⑤オーバフロー
演算結果が有限のけた内で表せる範囲を超えることによって，使用している記述方法では値が表現しきれなくなることです。

⑥アンダーフロー
浮動小数点数演算において，演算結果の指数部が小さくなりすぎ，使用している記述方法では値が表現しきれなくなることです。つまり，浮動小数点数表記では，0 や 0に近い数値は表現することができません。

集合
集合は，ある条件で集まったグループです。例えば，
集合A「コー
ヒーが好きな人」，集合 B「紅茶が好きな人」とすると，コーヒーが好き，紅茶が好き，というのが条件です。
集合を視覚的に分かりやすく表すために，ベン図という図が用いられます。二つ以上の集合を組み合わせることが多く，代表的な組合せに次の五つがあります。

①和集合（A OR B，A＋B，A∪B，A∨B）
二つの集合を足したものです。上記の例では，「コーヒーか紅茶が好きな人」になります。

A

B

和集合

1-1

②積集合（A AND B，A・B，A∩B，A∧B）

発展

二つの集合の両方に当てはまるものです。前記の例では，「コーヒーも紅A

茶も好きな人」になります。

B

積集合③補集合（NOT A，A ）ある集合の否定です。前記の例では，「コーヒーが好きではない人」にな

A

ります。

補集合

④差集合（A−B）
ある集合から，別の集合の条件にあてはまるものを引いたものです。前記の例では，「コーヒーは好きだけれどAB

紅茶は好きではない人」になります。
差集合⑤対称差集合（A XOR B，A⊕B，A △ B）
二つの集合のうち，どちらかの条件にあてはまるものから，両方の条件にあてはまるものを引いたものです。前A

B

記の例では，「コーヒーか紅茶が好き，
しかし両方は好きではない人」になり

基礎理論

対称差集合

ます。

論理演算
コンピュータの内部表現では，数値のほかに論理（真か偽か）も表現できます。論理演算とは，データを論理で表現し，その組合せを演算することです。
通常，真（TRUE，YES，正しい）を1，偽（FALSE，NO，正しくない）を 0 で表します。そして，それについてビットごとにその他の集合としては，二つの集合演算をかけ合わせた NAND（NOT ＋ AND），
NOR（NOT＋OR）などもあります。
さらに，データベースなどで使用する集合演算には，直積，射影，選択，商などもあります。

29

1

30

第1章

基礎理論

論理和，論理積などを考えることによって，論理演算を行います。
それでは，実際に論理演算を行っていきましょう。

問題

発展

このような AND 演 算の 使
い方を，マスク演算とも呼びます。ビットが 1の部分のみを取り出して，ほかの部分をマスク（排除）するときに使用します。
IP アドレスに 対 す るサブ
ネットマスクは，このマスク演算を応用した例です。

0 以上 255 以下の整数n に対して，

next（n ）＝

n ＋1（0 ≦n ＜ 255）

0（n ＝ 255）と定義する。next（n ）と等しい式はどれか。ここで，x AND y
及びx OR y は，それぞれx とy を 2 進数表現にして，けたごとの論理積及び論理和をとったものとする。
ア （n ＋1）AND 255

イ （n ＋1）AND 256

ウ （n ＋1）OR 255

エ （n ＋1）OR 256（平成 22 年春 応用情報技術者試験 午前 問1）

解説next（n ）では，演算を行ったときにn の値によって二つの場合に分けて計算するので，それぞれの場合を考えてみましょう。
① 0≦n ＜255の場合
例として，n ＝100の場合を考えてみましょう。n ＝100を16ビットの2 進数で表すと次のようになります。
00000000 01100100
これに 1を加えるとn ＝101となり，最後尾のビットに 1を加えるだけなので次のようになります。
00000000 01100101
この n ＋ 1 と同じ 演 算 結 果になる選 択 肢を考えてみましょう。10 進数の 255 は 2 進数で 00000000 11111111，256 は 2 進数で00000001 00000000なので，n ＝100の場合，次のようになります。

1-1

基礎理論

ア （n ＋1）AND 255
		

＝00000000 01100101 AND 00000000 11111111

		＝00000000 01100101（←n ＋1と同じ）

1

イ （n ＋1）AND 256
		

＝00000000 01100101 AND 00000001 00000000

		＝00000000 00000000（← 0になってしまう）

ウ （n ＋1）OR 255
		＝00000000 01100101 OR 00000000 11111111

		＝00000000 11111111（← 255になってしまう）

エ （n ＋1）OR 256
		

＝00000000 01100101 OR 00000001 00000000

		＝00000001 01100101（← 357になってしまう）

したがって，アの演算のみ正しい結果となります。
② n ＝255の場合
選択肢アで，n が 255 の場合を考えてみます。n ＋1＝256，2 進
数で 00000001 00000000をアの計算式で計算します。
（n ＋1）AND 255＝00000001 00000000 AND 00000000 11111111＝00000000 00000000（← 0になる）
したがって，n ＝255 のときに 0 になるという条件も満たしています。
≪解答≫ ア

論理式の変形・簡略化
論理式では，論理演算の法則・定理を使って変形や簡略化を行うことができます。代表的なものには，ド・モルガンの法則や結合の法則，分配の法則などがあります。
すべての法則を覚えなくても，ベン図などを用いたり，実際の値を入れたりすることで，等価な式を見つけることはできます。
それでは，実際の問題を解いてみましょう。

31

用語

ド・モルガンの法則

A ∪B ＝A ∩B
A ∩B ＝A ∪B

結合の法則（A ∪B ）∪C ＝A ∪（B ∪C ）（A ∩B ）∩C ＝A ∩（B ∩C ）分配の法則
A ∩（B ∪C ）＝（A ∩B ）∪（A ∩C ）A ∪（B ∩C ）＝（A ∪B ）∩（A ∪C ）

32

第1章

基礎理論

問題

過去問題をチェック

論理演算については，定番でよく出題されます。この問題のほかに，応用情報技術者試験
平成 24 年春 午前 問1，
平成 25 年春 午前 問2，
平成 25 年秋 午前 問4などで出題されています。

全体集合 S 内に異なる部分集合 A と B があるとき，A ∩ B に等
しいものはどれか。ここで，A ∪ B は A と B の和集合，A ∩ B は

A と B の積集合，A は S における A の補集合，A − B は A から Bを除いた差集合を表す。
ア A −Bイ （A ∪B ）−（A ∩B ）ウ （S −A ）∪（S −B ）エ S −（A ∩B ）（平成 24 年秋 応用情報技術者試験 午前 問1）

解説
論理演算を行う方法
それぞれの選択肢で，すべてのパターンを考えてみます。
A

B

A ∩B

ア A −Bイ（A ∪B ） ウ（S −A ） エ S −−（A ∩B ） ∪（S −B ） （A ∩B ）

0

0

1

1

1

1

0

1

0

0

1

1

1
1

1

0

0

0

1

1

1

1

1

0

0

0

0

0

A ∩B と同じものは，アのみです。
ベン図を書いて解く方法

A ∩B をベン図で書いてみると，以下のようになります。

A

B

このベン図は，アのA −B を書いたものと同じです。

その他の選択肢は，次のように同じベン図になります。

1-1

基礎理論

イ （A ∪B ）−（A ∩B ）A

B

1ウ （S −A ）∪（S −B ）エ S −（A ∩B ）≪解答≫ ア□

けた落ちは有効けた数が減ること，情報落ちは小さい数値の方の情報が落ちること

1-1-2

応用数学

勉強のコツ

コンピュータを学ぶ上で基礎となる応用的な数学です。高校から大学レベルで学ぶ数学の一部で，押さえておくといろいろなコンピュータ技術の理解に役立ちます。

確率ある事象（出来事）が起こる確率を求めるときにはまず，場合の数を求めます。それぞれの場合が起こる確率が等しいときには，全体の場合の数のうち，ある特定の事象に対しての場合の数の割合が，その事象が起こる確率になります。
ある事象が起こる確率 ＝			

ある事象の場合の数全体の場合の数

統計
統計で一番使われる考え方に，正規分布があります。繰り返
し実行した場合，それが独立した事象であれば，その分布は正規分布に従うことが知られています。
正規分布の場合，その確率の散らばり具合によって，標準偏差シグマ（σ）が求められます。その分布が正規分布に従っていた場合に，±1σ（−1σから1σ）の間に約 68％のデータが含まれます。±2σの間には約95％，±3σの間には約99.7％のデータが含まれます。

33

確率・統計のほかに微分積
分や指数・対数など，高校レベルの数学も試験範囲です。
たまに出題されますし，基礎としてとても役に立つので，勉強をしたことがない
方，苦手な方は勉強しておいた方がいいでしょう。
ただ，労力をかけても出題
は1問程度なので，時間がない場合は飛ばしても OK
です。

34

第1章

基礎理論

-3σ

-2σ

-1σ

0

1σ

2σ

3σ

68%
95%
99.7%

正規分布

また，データの分布がどれだけ直線に近いかを示す係数に，相関係数があります。完全に右上がりの直線上にデータが分布している場合には相関係数が 1，まったく相関のない無相関な場
合には相関係数が0になります。さらに，
右下がりの直線上にデータが分布している場合には相関係数が−1になります。

相関係数＝1

相関係数＝0相関係数＝−1

それでは，相関係数に関する問題を解いてみましょう。

問題
相関係数に関する記述のうち，適切なものはどれか。
ア

すべての標本点が正の傾きをもつ直線上にあるときは，相関イ

変量間の関係が線形のときは，相関係数が 0になる。

ウ

変量間の関係が非線形のときは，相関係数が負になる。

エ

無相関のときは，相関係数が−1になる。

係数が＋1になる。

（平成 23 年特別 応用情報技術者試験 午前 問3）

1-1

基礎理論

1

解説
相関係数は−1から＋1までの値をとり，完全に正の傾きをもつ
直線上にすべての標本点があるときには＋1になります。したがって，アが正解です。
相関係数は線形の度合いを示す数字で，まったく無相関のときに 0になります。また，相関係数は「いかに直線か」を示すものなので，非線形の場合には相関係数の値は意味がありません。同じ直線でも正の傾きをもつ直線の場合は＋1，負の傾きをもつ場合には−1となります。
≪解答≫ア

グラフ理論
グラフ理論とは数学の 1 分野で，ノード（node：節点）とエッジ（edge：枝，辺）から構成されるグラフについての理論です。
ノード

ノード
エッジ

グラフ

グラフには，方向性のある有向グラフと，方向性のない無向グ
ラフの 2 種類があります。A → Bには行けるが B → Aには行けな
いことがあるという場合は有向グラフ，どちらからも行けるという場合には無向グラフを用います。

有向グラフ

35

無向グラフ

関連

グ ラ フ 理 論 は，Facebook
でのソーシャルグラフ（友達関係を表すグラフ）や，電車の乗り換え案内などでも利用されています。

36

第1章

基礎理論

そして，
グラフ理論の重要な考え方に木という概念があります。
木とは，閉路（ループ）をもたないグラフの構造で，根（root）と節点（ノード：node），葉（leaf）をもちます。
根
ノード（節点）葉木
過去問題をチェック

M/M/1 待ち行列の問題は，応用情報技術者試験
平成 21年春 午前 問1，
平成 22 年春 午後 問4，
平成 22 年秋 午後 問4，
平成 24 年春 午前 問2，
平成 25 年秋 午前 問 5，
平成 26 年秋 午前 問 3などで出題されています。
およそ 2 回に 1回は出題される頻出ポイントです。
発展

待ち行列モデルの「D」は，
確 定 分 布（Deterministic
distribution）の 意 味 で す。
これは，到着率やサービス
時間が一定であることを指します。この場合には，ゆらぎがないので待ちが発生
しにくくなります。
「M」は，到着やサービスがランダムに行われる場合のモデルで，ポアソン分布または指数分布のことを指します。この二つの分布は，着目の仕方の違いで，実は同じ現象を別の視点で見ているのです。例えば，到着の場合，来る確率である到
着率はポアソン分布に従いますが，間隔に着目すると到着間隔は指数分布に従います。
試験対策としては，「ポアソ
ン到着率，指数サービス時間」ぐらいで覚えていれば十分ですが，詳しく知りた
い方は，確率論を勉強されるのも楽しいと思います。

待ち行列理論
待ち行列理論とは，ある列に並ぶときに，平均でどれだけ待たされるかを統計学的な計算で求めるための理論です。
列に並んでいるとき，待ち行列のモデルでは次の三つの要素
が待ち時間に影響を与えると考えられています。
到着率……………… どれくらいの頻度でやって来るか
サービス時間……… 実作業にどれくらい時間がかかるか
窓口の数…………… 一つの列に対して窓口がいくつあるか
これら三つの要素について，次のようなかたちで待ち行列のモデルを表します。

到着率

サービス時間

窓口の数

待ち行列のモデル

M/M/1とは，到着率が一定（D）ではなくランダム（M）（ポア
ソン分布）で，サービス時間が一定（D）ではなくランダム（M）（指数分布）な場合の待ち行列のモデルです。

1-1

到着率

基礎理論

サービス時間平均

1

平均

ポアソン分布

指数分布

待ち時間の計算
待ち時間は，待ち行列理論を使うと計算できます。待ち行列モデルが M/M/1 以外の場合は計算方法が少し複雑なので，あらかじめ計算された表などを利用しますが，M/M/1モデルの場
合には次の式で計算できます。
仕事をしている時間 平均サービス時間
ロー
利用率 ρ＝＝
		
全体の時間
平均到着間隔ρ
平均待ち時間 ＝
×平均サービス時間
		 1−ρ
平均応答時間 ＝ 平均待ち時間＋平均サービス時間
1＝
×平均サービス時間
		 1−ρ
それでは，実際の午後問題を例に，待ち行列の計算を行っていきましょう。

問題
インターネットを介した情報提供システムに関する次の記述を読んで，設問 1，2 に答えよ。
Z 社は，利用者が希望する映画のタイトル，あらすじ，上映館，上映期間などの映画情報を表示する情報提供サービスを行っており，平均待ち時間の目標値を 40 ミリ秒以下としている。このサービスに使用する情報提供システムの現在のシステム構成を図 1 に示す。

37

過去問題をチェック表を用いて M/M/n モデ ル
（窓口が n 個の場合の待ち行列モデル）での待ち時間を計算する問題は，応用情報技術者試験
平成 22 年秋 午後 問4 や
平成 26 年春 午後 問4で出題されています。
複雑な待ち行列の問題は，午後での出題頻度が高いで
す。

38

第1章

基礎理論

PC

Web サーバ…

インターネットFW
DB サーバPC

FW：ファイアウォール

図1 現在のシステム構成

Web サーバとデータベースサーバ（以下，DB サーバという）を一体のシステムとして，現在のシステムの状況を調査したところ，
1分当たりのアクセス数は平均 600 件，1アクセス当たりの平均処
理時間 Tp は 40 ミリ秒であった。また，アクセス頻度はおおむね
a

分布に，処理時間はおおむねb分布に従っていたので，M/M/1の待ち行列モデルによって評価することにした。
設問1

現 在 の Z 社 の 情 報 提 供 シ ス テ ム に つ い て，本 文 中 の
a

設問 2

，

b

に入れる適切な字句を答えよ。

現在の Z 社の情報提供システムについて，（1）〜（4）に答えよ。ただし，（1）は，整数で答えよ。
（2）〜（4）は，
小数第 2 位を四捨五入して小数第 1 位まで求めよ。

（1） 平均到着時間間隔 Tr（ミリ秒）を求めよ。
（2） 利用率ρを求めよ。
（3） 平均待ち時間 Tw（ミリ秒）を求めよ。
（4） 平均応答時間 Ts（ミリ秒）を求めよ。
（平成 22 年春 応用情報技術者試験 午後 問 4 抜粋）

解説
設問1
アクセス頻度は，M/M/1 モデルでの最初の M，つまり到着率に該当するので，ポアソン分布に従います。処理時間は，2番目のM，
つまりサービス時間に該当するので，指数分布に従います。
設問 2（1）
平均到着時間間隔 Trを求めます。1 分当たりのアクセス数は平均 600 件なので，何ミリ秒に1回アクセスがあるかという平均到着

1-1

基礎理論

時間間隔 Trは次のようになります。
Tr＝

時間

＝
件数		

1［分］×60［秒］×1000［ミリ秒］＝ 100［ミリ秒］
600［件］（2）
利用率ρを求めます。利用率とは，サーバがどれくらいの割合
で利用されているかという確率です。平均到着時間間隔 Tr＝100［ミリ秒］で，平均サービス時間 Tp＝40［ミリ秒］なので，利用率
ρは次のようになります。
ρ＝仕事をしている時間 Tp
40
＝
＝0.4
＝
全体の時間
Tr		 100（3）
平均待ち時間 Tw（ミリ秒）を求めます。M/M/1モデルの場合の平均待ち時間の待ち行列の式を適用します。
平均待ち時間Tw＝
＝

0.4
1−0.4

ρ
1−ρ

×平均サービス時間Tp

×40＝26.66……≒26.7［ミリ秒］

小数第 2 位を四捨五入して小数第1 位まで求めます。
（4）
平均応答時間を求めます。M/M/1 モデルの平均応答時間の待ち行列の式を適用します。
平均応答時間Ts＝
＝

1
1−0.4

1
1−ρ

×平均サービス時間Tp

×40＝66.66……≒66.7［ミリ秒］

小数第 2 位を四捨五入して小数第1 位まで求めます。
≪解答≫
設 問1

a：ポアソン，b：指 数

設 問 2 （1）10 0，（ 2 ）0 . 4，
（ 3 ）2 6. 7，（ 4 ）6 6. 7□

正規分布の場合，± 1σの中に入っているデータは全体の約 68％，± 2σでは約 95％□

平均待ち時間＝

ρ
× 平均サービス時間
1−ρ

39

1

40

第1章

基礎理論

1-1-3

情報に関する理論

情報技術に応用されている理論です。情報量やオートマトンなど，コンピュータでの処理を効率良く実現するにあたって必要な理論について学びます。

情報量
情報量とは，ある事象が起きたとき，それがどれくらい起こりにくいかを表す尺度です。例えば，6月に雨が降るのと雪が降るのとでは雪が降る方が起こりにくいので，情報量としては多くなります。
ある事象が起こるときの情報量を，選択情報量（自己エントロピー）といいます。選択情報量は，次の式で表されます。
選択情報量＝−log 2P

P は，その事象が起こる確率です。例えば，明日雨が降る確率
が 50％なら，雨という事象の選択情報量は，
1
雨の選択情報量 ＝−log 2 0.5＝−log 2		2＝−log 2 2−1 ＝1となり，選択情報量は1［ビット］となります。
また，系全体，つまり，すべての場合を考えて，その全体の平均をとったときの情報量を平均情報量（エントロピー）といいます。平均情報量は，次の式で表されます。
平均情報量＝Σ ni=1（選択情報量×P i）＝Σ ni=1｛（−log2P i）×P i ｝
例えば，明日の天気が，晴れが 25％，曇りが 25％，雨が 50％の可能性だったと考えてみます。晴れと曇りの選択情報量は，−log 2 0.25＝−log 2 2−2 ＝2なので，次のようになります。
平均情報量＝2×0.25＋2×0.25＋1×0.5＝1.5
したがって，平均情報量は1.5ビットです。
それでは，次の例題を解いてみて，その後で情報量の使い方について考えていきましょう。

1-1

a，b，c，d の 4 文字からなるメッセージを符号化してビット列にする方法として表のア〜エの 4 通りを考えた。この表は a，b，c，d の各 1 文字を符号化するときのビット列を表している。メッ
セージ中での a，b，c，d の出現頻度は，それぞれ 50％，30％，
10％，10％であることが分かっている。符号化されたビット列
から元のメッセージが一意に復号可能であって，ビット列の長さが最も短くなるものはどれか。
a
0
0
0
00

b
1
01
10
01

c
00
10
110
10

41

1

問題

ア
イ
ウ
エ

基礎理論

d
11
11
111
11

（平成 22 年秋 応用情報技術者試験 午前 問2）

解説
まず，「符号化されたビット列から元のメッセージが一意に復元可能か」を考える必要があります。
アの場合には，例えばビット列が 000 のときに，元のメッセージが aaaなのか acなのか caなのか区別できません。
イも，ビット列が 010のとき，baなのかacなのか区別できません。
これらの場合には，
いくらビット列の長さが短くても採用できません。
エの場合は，すべてが 2ビットなので，2ビットごとに区切れば，0110は bcというように一意に復号可能です。しかし，ビット列の長さは 2ビット必要になります。
ウの場合，元のメッセージを一意に識別することが可能です。
さらに，出現頻度が a，b，c，d それぞれ 50％，30％，10％，10％なので，平均のビット数は，1×0.5＋2×0.3＋3×0.1＋3×0.1＝1.7［ビット］となり，エの場合（2ビット）よりも短くなります。
≪解答≫ ウ

42

第1章

基礎理論

この問題を使って，情報量について計算してみましょう。
a，b，c，dの出現頻度はそれぞれ 50％，30％，10％，10％なので，選択情報量を求めると次のようになります。
a の選択情報量 ＝−log 2 0.5＝−log 2 2 −1=1
bの選択情報量 ＝−log 2 0.3＝
		−log10 0.3
log10 2−（log10 3−1）
≒1.74
＝
		
log10 2−log10 0.1
c，dの選択情報量 ＝−log 2 0.1＝
		log10 21
≒3.32＝
		 log10 2
ここから，平均情報量（エントロピー）を求めます。
すべての選択情報量を合計して平均情報量を求めると，次のようになります。
平均情報量 ＝1×0.5＋1.74×0.3＋3.32×0.1+3.32×0.1＝1.686［ビット］
この平均情報量1.686［ビット］というのは系全体がもっている情報量で，この値が実は圧縮の限界値になります。前掲の問題で，選択肢ウのように a を 0（1ビット），bを10（2ビット），c，d をそれぞれ 110，111（3ビット）割り当てると，平均情報量は1.7と，圧縮の限界値に近い値になります。

オートマトン
オートマトンとは，次のような三つの特徴をもったシステムのモデルです。
1．外から，情報が連続して入力される
2．内部に，状態を保持する
3．外へ，情報を出力する
特定の条件が起こったときに，ある状態から別の状態に移る
ことを遷移といいます。例えばデートのとき，相手が来るのを待っている状態が待ち状態で，相手が来るという遷移条件が起こると，デートをするデート状態に移ります。
オートマトンのうち，状態や遷移の数を有限個で表すことができるものを有限オートマトンといいます。

1-1

実際の問題をもとに，オートマトンを体験してみましょう。

問題
次に示す有限オートマトンが受理する入力列はどれか。ここで，S 1 は初期状態を，S 3 は受理状態を表している。
0
S1

1

S2

1

1

0

S3

0

ア 1011

イ 1100ウ 1101

エ 1110（平成 21年春 応用情報技術者試験 午前 問3）

解説
初期状態が S1 なので，S1 を起点としてそれぞれの文字列を入力
して状態遷移を見ていきます。
ア 101110
1
1S1 → S2 → S2 → S1 → S2

イ 11001
1
0
0S1 → S2 → S1 → S3 → S2

ウ 1101
エ 11101
1
0
1
S1 → S2 → S1 → S3 → S3					受理状態
1
1
1
0
S1 → S2 → S1 → S2 → S2

ア，イ，エは S2，ウのみ S3 になります。受理状態とは，その状態で終了すると受理するという状態で，この問題の場合，受理状
態はS3 です。
≪解答≫ ウ

このように，
初期状態からスタートして順番に状態遷移を行い，

基礎理論

43

1

44

第1章

基礎理論

最後に受理状態で終われば正常終了というかたちで評価を行う
ことがオートマトンの基本です。

木の走査順と逆ポーランド表記法
グラフ理論における木で，木のそれぞれのノード（節点）を順番に読んでいくことを走査といいます。走査を行う際の順番には，先行順，中間順，後行順の3 種類があります。

2

A

先行順

中間順

後行順

1 ＋

2 ＋

3 ＋

3 B

1

3 B

A

前置表記法
（ポーランド表記法）
＋AB

中置表記法
A＋B

走査順

1

A

2 B

後置表記法
（逆ポーランド表記法）
AB＋先行順，中間順，後行順でノードの内容を表記する方法をそれぞれ，前置表記法（ポーランド表記法），中置表記法，後置表
記法（逆ポーランド表記法）といいます。
人間の頭脳が理解しやすいのは中置表記法ですが，コンピュー
タは逆ポーランド表記法の方が処理しやすいという違いがあります。そのため，演算などを行うときには，コンピュータ内で逆ポーランド表記法に置き換えていきます。
以下の問題で，実際に表記法を置き換えてみましょう。

問題

過去問題をチェック

逆ポーランド表記法については，この問題のほかにも
応用情報技術者試験
平成 23 年秋 午前 問2，
平成 24 年秋 午前 問4でも出題されています。また，プログラミング問題として，午後問題でも
平成 25 年春 午後 問2で出題されています。

後置表記法（逆ポーランド表記法）では，例えば，式Y ＝（A −B ）×C をYAB −C ×＝と表現する。
次の式を後置表記法で表現したものはどれか。

Y ＝（A ＋B ）×（C −（D ÷E ））ア YAB ＋C −DE ÷×＝

イ YAB ＋CDE ÷−×＝

ウ YAB ＋EDC ÷−×＝

エ YBA ＋CD −E ÷×＝（平成 22 年秋 応用情報技術者試験 午前 問1）

1-1

基礎理論

1

解説
問題文の式は中置表記法なので，まず次のように木構造に置き
換えます。
＝
X
B

Y
＋
A
A

−
B

÷
B

C
D

E

この木を逆ポーランド表記法にするには後行順で順に読んでいけばいいので，次のようになります。

YAB ＋CDE ÷−×＝
≪解答≫ イ

BNF（Backus-Naur Form）記法
BNFは，文法などの形式を定義するために用いられる言語で，プログラム言語などの定義に利用されています。繰返しの表現に再帰を使うのが特徴です。
実際の問題を例に，BNFについて学習していきましょう。

問題あるプログラム言語において，識別子（identifier）は，先頭が英字で始まり，それ以降に任意個の英数字が続く文字列である。これを BNF で定義したとき，a に入るものはどれか。
<digit> :: ＝ 0 ｜ 1 ｜ 2 ｜ 3 ｜ 4 ｜ 5 ｜ 6 ｜ 7 ｜ 8 ｜ 9<letter> :: ＝ A ｜ B ｜ C ｜…｜ X ｜ Y ｜ Z ｜ a ｜ b ｜ c ｜…
｜x｜y｜z<identifier> :: ＝a45

過去問題をチェック

BNF のアルゴリズムに関する問題は，この問題の他にも，応用情報技術者試験
平成 22 年秋 午後 問2や平成 26 年春 午前 問 3などで出題されています。

46

第1章

基礎理論

ア

<letter>｜<digit>｜<identifier><letter>｜イ<letter>｜<digit>｜<letter><identifier>｜<identifier><digit><identifier><digit>
ウ<letter>｜<identifier><digit>エ<letter>｜<identifier><digit>｜<identifier><letter>（平成 23 年特別 応用情報技術者試験 午前 問 4）

解説
記号の「::＝」は「定義する」，「｜」は「いずれか」を意味します。
したがって，<digit> ::＝0｜1｜2｜3｜4｜5｜6｜7｜8｜9は，<digit>が 0 から9までの数字であることを定義し，<letter> ::＝A｜B｜C｜…｜X｜Y｜Z｜a｜b｜c｜…｜x｜y｜zは，<letter>が大文字か小文字の英字であることを定義しています。
識別子 <identifier>については，問題文に「先頭が英字で始まり，それ以降に任意個の英数字が続く文字列」と記載されています。
つまり，識別子 <identifier>は，<identifier> ::＝ <letter> …最初の1文字（英字）のみか，そこに再帰を用いて，<identifier> ::＝ <identifier><digit>
または，<identifier> ::＝ <identifier><letter>というかたちで，2 番目以降には英数字（英字か数字のどちらか）が続くという状態を表現できます。したがって，次のようになります。
<identifier> ::＝<letter>｜<identifier><digit>｜<identifier><letter>≪解答≫ エ1-1

基礎理論

計算量（オーダ）
計算量とは，あるプログラム（アルゴリズム）を実行するのにどれくらいの時間がかかるかを，入力データに対する増加量で表したものです。計算量を表すときには，
O -記法という表記法で，O（オーダ）という考え方が用いられます。
例えば，入力データの数（n）が増加したとき，その計算量もnに比例して増加していくときのことを，O（n）と表します。n2 に比例して増加する場合には，O（n2）です。オーダは，n が非常に大きいときの計算量を考えるので，数値が小さい場合には無視
し，定数も無視します。例えば，入力データの数（n）が増加した
とき，3n2 ＋n＋2に比例して計算量が大きくなるときには，n が大きくなってもあまり増加しない n＋2 の部分や，比例定数 3 の部分は無視されて，O（n2）となります。
以下に，試験によく出てくる代表的なO（オーダ）とその例を示します。
代表的なO（オーダ）とその例

O（オーダ）例（アルゴリズム）O（1）ハッシュO（log n）
2 分探索
O（n）
線形探索
O（nlog n） クイックソート，シェルソート
O（n2）バブルソート，挿入ソート□

木の走査順は，先行順，中間順，後行順の 3 種類。後行順で読むと，逆ポーランド表記法が表記できる□，クイックソートの計算量はO（nlog n）
2 分探索の計算量はO（log n）

47

1

48

第1章

基礎理論

発展

メモリのエラーなど，めったに誤りが起こらず，
起こっても1ビットのみのことが多い場合には，誤り訂正も可 能なハミング 符号が 用
いられます。ハミング符号による誤り訂正ができるメ
モリのことを，ECC メモリ（Error Check and Correct
Memory）といい，サーバなど，信頼性が求められる場
面で使用されます。
逆に，通信データのように，頻繁に誤りが起こり，また一度にまとめて起こること（バースト誤り：P.51「発展」
参照）が多い場合には，複数ビットの誤りを検出できるCRCを用います。

1-1-4

通信に関する理論

情報理論の中でも，
特に通信に関する理論です。データがネッ
トワークを通じて伝送されるときには途中で誤りが発生することが多く，その誤りの検出・訂正がこの分野のカギになります。

誤り検出・訂正
二つの装置間で通信を行うとき，通信時の回線状況や機器同士のやり取りなど，様々な原因で通信データの送信誤りが起こります。誤り検出・訂正の種類とその代表的な手法を以下の表にまとめます。
誤り検出・訂正の種類と代表的な手法
誤り検出・訂正の種類
1ビット誤り検出

代表的な手法パリティ（奇数パリティ，
偶数パリティ）1ビット誤り訂正＋1ビット誤り検出

垂直パリティ＋水平パリティ

1ビット誤り訂正＋2ビット誤り検出

ハミング符号nビット誤り検出

CRC

それでは，それぞれの代表的な手法について詳しく見ていき
ましょう。

パリティ
パリティとは，ある数字の並びの合計が偶数か奇数かによって通信の誤りを検出する技術です。データの最後にパリティビッ
トを付加し，そのビットを基に誤りを検出します。
そのとき，1の数が偶数になるようにパリティビットを付加するのが偶数パリティ，奇数になるようにパリティビットを付加するのが奇数パリティです。
例えば，7ビットのデータ1100010を考えます。
偶数パリティの場合，現在のデータは1の数が奇数なので最後に1を付加して11000101とします。奇数パリティの場合は，すでに1の数が奇数なので最後に0を付加し，11000100とします。
また，パリティは，使い方によっては，誤り訂正を行うことができます。データが送られるごとに，最後に1ビットのパリティ
ビットを付けるやり方を垂直パリティといいます。7ビットデー

1-1

基礎理論

タを送り，それに1ビット垂直パリティを加える，ということを

1

何度か繰り返し，データを送信します。そして最後に，それぞれのビットのデータを横断的に見て，全体で誤りがないかどうかをチェックするのに水平パリティを用います。図に表すと以下のようになります。
データの流れ
0
0
1
1
1
0
0
1
0

0
1
1
0
0
0
0
1
1

1
0
0
1
0
0
1
1
0

0
0
0
0
1
1
0
1
1

1
0
1
1
0
1
1
0
1

0
1
0
1
0
0
1
0
1

1
0
0
1
0
1
1
0
0

1
0
1
1
0
1
0
0
0

垂直パリティ

水平パリティ

垂直パリティと水平パリティ

垂直パリティと水平パリティを組み合わせることにより，どこかに1ビットの誤りが発生した場合にその場所を特定でき，ビットを反転させることでエラーを訂正できます。

ハミング符号
ハミング符号とは，データにいくつかの冗長ビットを付加することによって，1ビットの誤りを検出し，それを訂正できる仕組みです。実際の問題を例に誤り箇所を検出し，それの訂正を行ってみましょう。
過去問題をチェック問題
符号長 7 ビット，情報ビット数 4 ビットのハミング符号による誤り訂正の方法を，次のとおりとする。
受信した 7 ビットの符号語 x 1 x 2 x 3 x 4 x 5 x 6 x 7（x k ＝ 0 又は 1）に対して

c 0 ＝x 1
c1 ＝
c2 ＝

＋x 3

x 2 ＋x 3

＋x 5

＋x 7
＋x 6 ＋x 7

x 4 ＋x 5 ＋x 6 ＋x 7

（いずれも mod2 での計算）

49

ハミング符号については，
この問題のほかにも応用情報技術者試験
平成 24 年秋 午前 問 3，
平成 25 年春 午前 問4でも出題されています。パ
リティビットについても，
平成 24 年春 午前 問 5で出題されています。
毎回少しずつ数値を変えて出題されていますので，答えを覚えるのではなく，やり方をしっかり理解しておきましょう。

50

第1章

基礎理論

を計算し，c 0 ，c 1 ，c 2 の中に少なくとも一つは 0 でないものがある場合には，

i ＝c 0 ＋c 1 × 2 ＋c 2 × 4を求めて，左からi ビット目を反転することによって誤りを訂正する。
受信した符号語が 1000101 であった場合，誤り訂正後の符号語はどれか。
ア 1000001

イ 1000101

ウ 1001101

エ 1010101（平成 23 年秋 応用情報技術者試験 午前 問3）

解説
この問題のハミング符号は，4ビットから成るデータに 3ビットの冗長ビットを加えて 7ビットにしたものです。このハミング符号
では，正しくデータが送られた場合には，c 0 ，c 1 ，c 2 の演算結果
はすべて0になるはずです。
ここで，受信した符号語 1000101について，c 0 ，c 1 ，c 2 の演算を行ってみると，

c 0 ＝x 1 ＋x 3 ＋x 5 ＋x 7 ＝1＋0＋1＋1＝3 → 3 mod 2＝1
c 1 ＝x 2 ＋x 3 ＋x 6 ＋x 7 ＝0＋0＋0＋1＝1 → 1 mod 2＝1
c 2 ＝x 4 ＋x 5 ＋x 6 ＋x 7 ＝0＋1＋0＋1＝2 → 2 mod 2＝0となり，誤りがあることが分かります。どこのビットが誤りかは，

i を求める式より次のように導き出すことができます。
i ＝c 0 ＋c 1 ×2＋c 2 ×4＝1＋1×2＋0×4＝3
3ビット目が誤っていることが分かるので，これを修正します。
したがって，訂正後のハミング符号は，1010101となります。
《 解 答 》エCRC（Cyclic Redundancy Check）
CRC は，連続する誤りを検出するための誤り制御の仕組みです。送信する基となるデータを，あらかじめ決められた多項式
で除算し，その余りをCRCとします。CRCのエラーチェックは，次の図のように示すことができます。

1-1

送信側

受信側

データ

データ

％多項式
CRC

％多項式
CRC

（余り）

二つが一致すれば OK
注 ％は，余りを求める演算子

CRC のエラーチェック

なお，
CRCのエラーチェックは，改ざん防止などのセキュリティ
チェックには使えません。これは，データは暗号化されていない
テキストであり，多項式は公開されているため，改ざんして再計算することが可能だからです。

発展

通信データの場合，ケーブルの不良や混線などによって誤りが一度にまとめて起こることがあります。こういった誤りをバースト誤りと呼びます。
バースト誤りに対しては，
複数ビットの誤りを検出できるCRCを用います。
家庭や社内のLANで一般的に使われているイーサネッ
トのパケットでは，誤り検出にCRCを用いています。
過去問題をチェック

CRCについては，応用情報技術者試験
平成 21年秋 午前 問4で出題されています。

□

1の数を足すと奇数になるのが奇数パリティ，偶数になるのが偶数パリティ□

ハミング符号では，1ビットの誤り訂正ができる□

CRC では，バースト誤りが検出できる

1-1-5

計測・制御に関する理論

計測・制御に関する理論は，主に組込系のシステムにおいて使われます。

A/D 変換，D/A 変換
人間世界にあるアナログの情報（音，画像など）をコンピュータ
で扱うためには，ディジタルのデータに変換する必要があります。
この変換をA/D 変換（Analog/Digital 変換）といいます。また，そのディジタルのデータを実際に用いる場合（録音したディジタル音
声を聞く場合など）は，逆にアナログの情報に変換する必要があります。この逆の変換をD/A変換（Digital/Analog変換）といいます。
A/D 変換を行うためには，標本化と符号化という二つの作業が必要です。標本化とは，連続のデータを一定の間隔をおいて
サンプリングすることで，符号化は，そのサンプリングしたデー
タをディジタルに置き換えることです。

基礎理論

過去問題をチェックA/D 変 換 や D/A 変 換 は，
応用情報技術者試験
平成 22 年春 午前 問23，
平成 22 年秋 午前 問13，
平成 23 年秋 午前 問4で出題されています。また，
PCM やサンプリングについても，応用情報技術者試験
平成 22 年春 午前 問27，
平成 22 年秋 午前 問 3，
平成 25 年春 午前 問26に出題されています。
アナログ／ディジタルの相互変換は，隠れた出題ポイ
ントです。

51

1

52

第1章

基礎理論

発展

音を標本化し，符号化したデータを格納する方式で代
表 的 な も の に PCM（Pulse
Code Modulation）があります。音楽CDやISDNなどでは，
PCMが用いられています。

例えば，下図のような音の波があったときに，一定間隔でデータを取得することを標本化，それをディジタルのデータに置き換えることを符号化といいます。
符号化
255
220

0
標本化（サンプリング）

標本化と符号化

それでは，次の問題を解いてみましょう。

問題
サンプリング周波数 40kHz，量子化ビット数 16 ビットで A/D変換したモノラル音声の1秒間のデータ量は，何kバイトとなるか。
ここで，1k バイトは 1,000 バイトとする。
ア 20

イ 40

ウ 80

エ 640

（平成 23 年秋 応用情報技術者試験 午前 問 4）

解説
サンプリング周波数 40kHzということは，1 秒間に 40×103 回サンプリングするということです。そのため，1サンプリング当たりの量子化ビット数を16ビットで A/D 変換した場合の1 秒間のデー
タ量は，以下のようになります。
16［ビット］×40×103［回／秒］÷8［ビット／バイト］＝80×103［バイト］＝80［k バイト］
≪解答≫ウ

1-1

標本化定理
標本化定理とは，ある周波数のアナログ信号をディジタルデー
タに変換するとき，それをアナログ信号に復元するためには，その周波数の 2 倍のサンプリング周波数が必要だという定理です。
例えば，4kHzまでの音声データを復元させるためには，その倍の8kHzのサンプリング周波数が必要です。
実際の問題で考えてみましょう。

問題
0 〜 20kHz の帯域幅のオーディオ信号をディジタル信号に変換するのに必要な最大のサンプリング周期を標本化定理によって求めると，何マイクロ秒か。
ア 2.5

イ 5

ウ 25

エ 50

（平成 21年秋 応用情報技術者試験 午前 問3）

解説
最大で 20kHz のオーディオ信号なので，必要なサンプリング周
波数を標本化定理によって求めると，次のようになります。
20kHz×2＝40kHz
ここからサンプリング周期を求めます。
1		
1＝
サンプリング周期 ＝
		 サンプリング周波数
40000
		

＝0.000025［秒］＝25［マイクロ秒］《 解 答 》ウ

基礎理論

53

1

54

第1章

基礎理論

制御システム
制御システムとは，ロボットや機械など，他の機器を制御するシステムです。制御システムを構成する要素には以下のようなものがあります。

①センサ
動きや温度などを計測するための機構です。センサには，ロボットや機械自身の状態を知るための内界センサと，周りの状況を知るための外界センサがあります。

過去問題をチェック

アクチュエ ータについて
は，応用情報技術者試験
平成 22 年秋 午前 問4で出題されています。

② アクチュエータ
機械・機構を物理的に動かすための機構です。制御棒などを実際に動かしたり，ロボットの腕を動かしたりします。

□

標本化定理では，2 倍のサンプリング周波数が必要□

アクチュエータは，実際の機械を物理的に動かす

1-2

アルゴリズムとプログラミング

1-2 アルゴリズムとプログラミング
アルゴリズムとプログラミングは，午前でも午後でも出題される，テクノロジ系では最重要分野です。
『データ構造＋アルゴリズム＝プログラム』という有名な古典があるほど，データ構造とアルゴリズムはプログラミングのカギになります。データ構造とアルゴリズムの定番を押さえて，様々なプログラム言語を学習していきましょう。

1-2-1

データ構造

データ構造とは，データをコンピュータ上でどのように保持するかを決めた形式です。基本的なデータ構造のほかに，配列，スタックなど，様々なデータ構造があります。

配列
データ構造を複数個連続させたものです。複数のデータを一度に管理することができます。例えば，文字型を連続させて文字配列とすることで，文字列を表現することができます。同じデー
タ型のデータをあらかじめ決めた数しか収納できない静的配列が基本ですが，最近のプログラム言語では，異なった型のデー
タを収納することや，データの数に応じて可変長の配列とすることが可能な動的配列を扱えるものもあります。

スタック
スタックとは，後入れ先出し（LIFO：Last In First Out）のデー
タ構造です。データを取り出すときには，最後に入れたデータが取り出されます。スタックにデータを入れる操作をpush 操作，
データを取り出す操作をpop 操作と呼びます。スタックは，CPUのレジスタやプログラムでの関数呼出しなど，現在のコンピュー
タシステムで非常に広範囲で使われています。

勉強のコツ

プログラミングは，“ 慣れ ”
が一番大切なので，基本を押さえたあとは演習を行いましょう。午後のアルゴリ
ズム問題を数多く演習する
か，または実際にプログラ
ミングしてみるなどして，実践力をつけると効果的です。
発展

データ構造は，プログラムの様々な部分で使われるため，いったん決めると変更が大変です。
そして，データ構造の選び方によって，処理速度が変わってきたり，変更のしやすさが変わったりと，影響が大きい部分でもあります。
そのため，「データ構造の選び方」が，プログラマの腕の見せ所になります。
発展

C++，Java な ど は 基 本 的には静的配列ですが，ライ
ブラリを使用することで動的配列にすることができます。Perl などでは，言語に組み込まれており，意識せず可変長の動的配列を使うことが可能です。

55

1

56

第1章

基礎理論

1，2，3

push

pop

3，2，1

3
2
1

スタック

次の問題で，スタックについて確認しましょう。

問題

過去問題をチェック

スタックについてはよく出題されるので，しっかり理解しておくことが 大 切です。この問題のほかにも応用情報技術者試験
平成 23 年特別 午前 問 7，
平成 24 年春 午前 問6で出題されています。また，
平成 25 年春 午後 問2の逆ポーランド表記法のア
ルゴリズムでは，スタックが利用されています。

配列を用いてスタックを実現する場合の構成要素として，最低限必要なものはどれか。
ア

スタックに最後に入った要素を示す添字の変数

イ

スタックに最初に入った要素と最後に入った要素を示す添字の変数

ウ

スタックに一つ前に入った要素を示す添字の変数を格納する
配列

エ

スタックの途中に入っている要素を示す添字の変数（平成 24 年秋 応用情報技術者試験 午前 問5）

解説
スタックを配列で表現するためには，スタック用の配列を用意します。配列に次の要素を入れるために，最後に入った要素の添
字（下の図の場合は1）を示しています。
添字

0

1

配列

○

○

2

3

最後に入った要素

4

5

6

7

添字 1

push 操作を行うと，次の添字 2 の配列要素に値が入ります。このとき，最後に入った要素の添字は，一つずれて2になります。

1-2

添字

0

1

2

配列

○

○

○

3

4

5

最後に入った要素

6

アルゴリズムとプログラミング

7

添字 2

ここで pop 操作を行うときには，最後に入った要素の添字，添
字 2 の配列要素を取り出します。その後，次にデータを入れる場
所を一つずらして，添字 1とします。
データ取出し
添字

0

1

配列

○

○

2

3

4

5

最後に入った要素

添字 1

6

7

スタックではpush操作とpop操作しか行わないので，必要なデー
タ構造としては，配列以外では，スタックに最後に入った要素を示す添字の変数のみとなります。したがって，アが正解です。
≪解答≫アキュー（待ち行列）
キュー（待ち行列）とは，先入れ先出し（FIFO：First In First
Out）のデータ構造です。データを取り出すときには，最初に入れたデータが取り出されます。キューにデータを入れる操作をエ ン キ ュ ーデ キ ュ ー

enqueue 操作，データを取り出す操作をdequeue 操作と呼びます。キューは，プリンタの出力やタスク管理など，順番どおりに処理する必要がある場合に用いられます。データに優先度を付
け，優先度を考慮して順番を決定する優先度付きキューもよく用いられます。

enqueue
1，2，3

3
1 2 3

キュー

dequeue

1，2，3

57

1

58

第1章

基礎理論

過去問題をチェック

リストについての問題は，応用情報技術者試験
平成 21年秋 午前 問 5，
平成 22 年秋 午前 問 5で問われています。
午後問題でも，
平成 21年春 午後 問2で単方向リストが，平成 22 年春 午後 問2で双方向リストが出題されています。
データ構造の中では，リストが応用情報技術者試験の最頻出項目です。

リスト
リストは，線形リストともいい，順序づけられたデータの並びです。データ構造としては，データそのものを格納するデータ部と，データの並び（次のデータへのポインタ，前のデータへのポインタなど）を格納するポインタ部を合わせて管理します。デー
タの先頭を指し示すために，先頭ポインタを使用し，管理します。
また，先頭ポインタだけでなく，末尾ポインタを用いて，最後方のデータに簡単にたどりつけるようにすることもあります。

先頭ポインタ末尾ポインタ（オプション）

ポインタ
データ

ポインタ
データ

ポインタ
データ

データ部とポインタ部

リストには，次のデータへのポインタのみをもつ単方向リストと，前へのポインタと次へのポインタをもつ双方向リストがあります。また，最後尾のデータから先頭に戻って環状につなげる
環状リストなどもあります。
単方向リスト

双方向リスト

環状リスト

リストの種類実際の問題を例に，リストの動きを確認してみましょう。

1-2

アルゴリズムとプログラミング

1

問題
先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，
末尾ポインタ又は各データのポインタをたどる回数が最も多いものはどれか。ここで，単方向のリストは先頭ポインタからつながっているものとし，追加するデータはポインタをたどらなくても参照できるものとする。
ア 先頭にデータを追加する処理
イ 先頭のデータを削除する処理
ウ 末尾にデータを追加する処理
エ 末尾のデータを削除する処理（平成 22 年秋 応用情報技術者試験 午前 問5）

解説
先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストを図で表すと，以下のようになります。
先頭ポインタデータ

末尾ポインタ

データ

59

データ

この線形リストに，ア，イ，ウ，エそれぞれの処理を行う場合を考えてみます。
ア 先頭にデータを追加する処理は，現在の先頭ポインタの値を追加するデータの次へのポインタにし，先頭ポインタが追加するデータを指し示すようにすれば OKです。
イ 先頭のデータを削除する処理は，先頭ポインタを2 番目のデー
タ（＝1 番目のデータの次へのポインタ）を指すようにすればOKです。
ウ 末尾にデータを追加する処理は，末尾ポインタをたどり，末

60

第1章

基礎理論

尾のデータの次へのポインタが，追加するデータを指し示す
ようにすれば OKです。
エ 末尾のデータを削除する処理は少し複雑です。末尾のデータを削除すると，末尾ポインタは末尾の一つ前のデータを指し示す必要があるのですが，それを見つけるためには，先頭から末尾の直前までたどっていく必要があります。図にすると，
次のようなかたちです。
先頭ポインタ末尾ポインタ

データ

データ
一つ前のデータを調べるため，先頭からたどる必要がある

データ削除

先頭から順に末尾の一つ前までたどるには，（データの個数−1）回，データのポインタをたどる必要があります。したがって，選択肢エが，ポインタをたどる回数が最も多くなります。
≪解答≫エ

関連

ハッシュは，セキュリティの改ざん検出や，探索のア
ルゴリズム（ハッシュ探索）など，様々な場面で利用されます。
具 体 的 な 活 用 例 は「3-5-1
情報セキュリティ」で取り上げますので，そちらを参照してください。

ハッシュ
ハッシュ関数とは，あるデータが与えられたときに，そのデー
タを代表する値に変換する関数です。ハッシュ関数y＝h（x）があった場合，x → yに変換できますが，y → xには変換できない一方向性の関数になります。ハッシュ関数で求められた値のことをハッシュ値または単にハッシュといいます。
ハッシュ関数の典型例としては，割り算の余りを求める関数h（x）＝x mod nなどがあります（modは余りを求める演算子）。
それでは，次の問題を確認してみましょう。

問題
自然数をキーとするデータを，ハッシュ表を用いて管理する。
キー x のハッシュ関数 h（x）を
h（x）＝ x mod n

1-2

アルゴリズムとプログラミング

nはハッシュ
とすると，
キー aとbが衝突する条件はどれか。ここで，1

表の大きさであり，x mod n は x を n で割った余りを表す。
ア a＋b が n の倍数

イ a−b が n の倍数

ウ n が a＋b の倍数

エ n が a−b の倍数（平成 25 年秋 応用情報技術者試験 午前 問7）

解説
キー aとbの余りが同じ数 mだとすると，a，bは次のように表すことができます。
a＝a’×n＋m， b＝b’×n＋m （a’，b’は任意の整数）
そのため，aとbの差 a−bを計算すると，
a−b＝（a’−b’）×nとなり，a’，b’ は整数なので，a−b は n の整数倍，つまり倍数となります。したがって，イが正解です。
≪解答≫イ

木
木（木構造）とは，グラフ理論（「1-1-2 応用数学」P.35 参照）の木の構造をしたデータ構造です。ノード間の関連は親子関係で表され，根ノード以外の子ノードでは，親ノードは必ず一つです。
親ノードに対する子ノードの数が二つまでに限定されるものを2
分木，三つ以上もてるものを多分木と呼びます。また，2 分木のうち形が完全に決まっているもの，つまり，一つの段が完全にいっぱいになるまでは次の段に行かないものを完全 2 分木といいます。
完全2分木（普通の）2分木

この段が終わるまでは
次の段には行かない

2 分木

61

過去問題をチェック木についての問題は，ソフトウェア開発 技 術 者 試 験（平成 20 年以前）ではよく出題されていて，平 成 20 年 秋 午 前 問 9（B木）と問10（葉の数），
平 成 20 年 春 午 前 問 9（2分木）など，ほぼ毎回問われていました。ただ，応用情報技術者試験になってから（平成 21 年 以 降 ）は，難 易 度が高いせいか出題頻度が下がっています。応用情報技術者試験
平成 23 年特別 午前 問6，
平成 25 年秋 午前 問6では出題されていますし，
いちおう押さえておいた方がいい分野ですが，難しけ
れば飛ばしてもOK です。

62

第1章

基礎理論

2 分木の実用例としては，データの大小関係を，木を使ってたどっていく2 分探索木や，構文や文法を表現する構文木などがあります。完全 2 分木の実用例としては，2 分探索木を完全 2 分
木に変換した AVL 木や，根から葉に向けてだけデータを整列させたヒープなどがあります。多分木の例としては，完全多分木
で 2 分探索木の多分木バージョンであるB 木などがあります。まとめると，以下のようなかたちになります。
2分木

2分探索木
構文木

完全2分木

AVL木
ヒープ

完全多分木

B木

2分木
木
多分木

木構造の分類

それでは，実際の問題を例に，木について確認してみましょう。

問題
葉以外の節点は全て二つの子をもち，根から葉までの深さが全て等しい木を考える。この木に関する記述のうち，適切なものはどれか。ここで，深さとは根から葉に至るまでの枝の個数を表す。
また，節点には根及び葉も含まれる。
ア

枝の個数が n ならば，節点の個数も n である。

イ

木の深さが n ならば，葉の個数は 2n − 1 である。

ウ

節点の個数が n ならば，深さは log2n である。

エ

葉の個数が n ならば，葉以外の節点の個数は n − 1 である。
（平成 25 年秋 応用情報技術者試験 午前 問6）

解説
葉以外の節点はすべて二つの子をもち，根から葉までの深さがすべて等しい木の例を図にすると，次のようになります。

1-2

根
枝

アルゴリズムとプログラミング

63

1

木の深さ
節点
1
2

葉

この木は完全 2 分木で，木の深さ（根から葉までの段数）は 2 です。○はすべて節点で，頂点が根，一番下の子がない節点が葉です。
節点と節点を結ぶ線が枝になります。
この図から，葉の個数が 4，それ以外の値も含む節点の個数が3 であることが分かります。つまり，葉の数が nならば，葉以外の節点の個数が n−1 個になっているということです。これは木の深さを増やしても成り立つので，エが正解です。
ア 枝の個数（6）は，葉を含むすべての節点（7）より少なくなります。一般的には，枝の個数が nならば，節点の個数はn＋1です。
イ 木の深さが nならば，葉の個数は 2n になります。
ウ 節点の個数が nならば，深さは log（−1となります。
2 n＋1）≪解答≫エヒープ
ヒープとは，完全 2 分木の一種で，最大値または最小値を求めるのに適したデータ構造です。
「子要素は親要素より常に大きいか等しい」か，または逆に「子要素は親要素より常に小さいか等しい」のどちらかになります。子要素が親要素より常に大きいか等
しい場合，根の値は全体の最小値，逆の場合は最大値になります。

□

リストには単方向リストと双方向リストがあり，単方向だと後ろからたどれないので削除
時の探索量が多くなる□

ヒープは完全 2 分木の一種で，子要素は親要素より「常に大きいか等しい」または，「常に小
さいか等しい」

64

第1章

基礎理論

勉強のコツ

アルゴリズム分野のポイン
トは，定番アルゴリズムについてしっかり知っておく
ことと，プログラムを読み解くスキルを身に付けることの二つです。
午前問題では，定番アルゴ
リズムについての知識問題と，簡単な流れ図を読み解く問題が中心になります。
発展

アルゴリズムは，業務でプ
ログラムを作成するときにも使えます。自分のやりたいことを実現してくれるア
ルゴリズムを「アルゴリズ
ム辞典」などから探し，それを適用することで，自分で一から考えなくても効率的なプログラムを組むことができます。

1-2-2

アルゴリズムアルゴリズムとは，処理の流れ，手順を記述したものです。
定番アルゴリズムを知ることで，プログラミングに必要な基礎力を身に付けることができます。

流れ図（フローチャート）
流れ図（フローチャート）では，順次・選択・繰返し（ループ）という基本 3 構造（ダイクストラが提言したので，ダイクストラの基本 3 構造とも呼ばれます）を用いて，プログラムの骨組みを記述します。
開始
朝起きる
顔を洗う

開始

朝は和食

開始
No

45kg超の間

Yes

ダイエット

ご飯を用意

パンを用意

歯を磨く
終了

終了

終了

順次

選択

繰返し

流れ図を基本 3 構造で記述

応用情報技術者試験の午後では，疑似言語を用いて基本 3 構
造を表現することが多いのですが，このとき，選択をif，繰返し
をwhileまたは forとしてアルゴリズムを表現します。
また，アルゴリズムでは，プログラミングを1 行 1 行追って確認していくことをトレースといいます。変数の値を1 行ごとに確認していくことが大切です。
それでは，流れ図の例として，次の問題を解いてみましょう。

問題
正の整数 M に対して，次の二つの流れ図に示すアルゴリズムを実行したとき，結果x の値が等しくなるようにしたい。a に入れる条件として，適切なものはどれか。

1-2

開始

アルゴリズムとプログラミング

開始
1 →x

1 →x
演算
n：M ,−1,1

1 →n

ループ端の繰返し指定は，
変数名：初期値，増分，終値を示す。

x ×n → xx ×n → x

n ＋1→ n
No

演算

a
Yes

終了

終了

M

イ n ＞M −1

ウ n ＞Mエ n ＞M ＋1＞

ア n

過去問題をチェック

流れ図を読み解く問題は，
応用情報技術者試験
平成 22 年春 午前 問 5，
平成 22 年秋 午前 問 7，
平 成 23 年 特 別 午 前 問 9，
平成 23 年秋 午前 問8，
平成 25 年春 午前 問8，
平成 25 年秋 午前 問9と，かなりの頻度で出題されています。
午後問題では，疑似言語になりますが，午後問 2 で毎回，プログラムの流れを読み解く問題が出されます。

（平成 22 年秋 応用情報技術者試験 午前 問7）

解説
二つの流れ図では，左が繰返し，右が選択を用いています。このように，選択を用いることで，繰返しと同じような内容を表現することができます。
まず左の流れ図（繰返し）では，ループの繰返し指定で，n の初期値がM ，増分が−1，終値が 1となっています。このループの間，

x ×n →x という計算を繰り返します。x の初期値は 1なので，ここでの計算結果は以下のかたちになります。

x ＝ 1×M ×（M −1）×（M −2）×（M −3）×……×3×2×1
右の流れ図（選択）で表現されるループは，n の初期値が 1でス
タートし，n ＋1 →n でn を1 ずつ増やしながら，x ×n →x という計算を繰り返します。x の初期値は1なので，ここでの計算結果は次のようになります。

x ＝ 1×1×2×3×……
ここで，左図のループとx の値が等しくなるためには，最後をMで終わらせて以下のようにする必要があります。

x ＝ 1×1×2×3×……×（M −3）×（M −2）×（M −1）×M
つまり，n がM までの間は計算して，M を超えたら終了となれ

勉強のコツ

流れ図やプログラムを読み解く問題では，面倒がらずに一つ一つをトレースすることが大切です。慣れない
うちは大変かもしれません
が，変数の値の変化を1行
1行確かめながら追ってい
くと，確実に答えを導き出せるようになります。

65

1

66

第1章

基礎理論

ば OKです。したがって，空欄 aに入れる条件はn ＞M としてn がM を超えたら終了というかたちにすれば，左の流れ図と同じ結果になります。
≪解答≫ウ

勉強のコツ

定番のアルゴリズムでは，同じ結果を出すために複数の方法が存在します。それ
ぞ れの手法には特徴があり，得意な条件とそうでない条件があります。そのアルゴリズムにかかる計算量などを中心に，やり方だけ
でなくそれぞれの特徴を押さえておきましょう。

探索アルゴリズム
探索のアルゴリズムは，データの並びの中から目的のものを見つけ出すという最も基本的な定番アルゴリズムです。探索アル
ゴリズムの代表的なものには，以下の三つがあります。

①線形探索
データを先頭から順番に探索していく単純なアルゴリズムです。データがランダムに並んでいる場合，探索するデータは先頭にあることも最後尾にあることもありますが，平均すると大体
真ん中くらいで見つかると考えられます。そのため，n 個のデー
タで探索を行うと，平均探索回数は n ／ 2回，計算量はO（n）となります（計算量については，P.47を参照）。

② 2 分探索
データをあらかじめ整列させておき，最初に真ん中のデータと探索するデータを比較します。二つのデータの関係から前後どちらのグループに目的のデータがあるかを予測し，そのグループの真ん中のデータと比較します。例えば，次のようなデータがある場合を考えます。
探索されるデータ

1

2

3

4

5

6

7

8

9

探索するデータ

3
最初に，真ん中のデータ「5」と探索するデータ「3」を比較します。5＞3なので，探索するデータは「5」より前のグループ

1-2

1

2

3

アルゴリズムとプログラミング

4

67

1

の中にあることが分かります。したがって，このグループについて再度，真ん中の値を求めます。このとき，「2」と「3」はどちらも真ん中なのでどちらでもいいのですが，通常は前の値「2」をとります。このとき，2 ＜3なので，探索するデータは「2」より後ろにあることが分かります。その後ろのグループ「3」「4」の真ん中のデータ「3」と比較し，3＝3でデータが見つかります。
このように，半分にデータを絞って探索を行うため，n回の探索で 2n までのデータ数に対応できます。したがって，計算量はO（log n）となります。

③ハッシュ表探索
ハッシュ関数を利用し，データからハッシュ値を求めることによって探索します。例えば，ハッシュ関数として，
h（x）＝ x % 5（%は余りを計算する演算子）というものを設定し，データの格納場所を五つ用意します。

発展

O - 記法での対数関数では，log2nやlog10nなどといったかたちの底は記入せず，O（log n）と表現します。
O - 記法は，「だいたいこれくらいの割合で増加する」ということを示 す 記 法 です。対数関数の場合，底がいくつでも増加の割合は同じなので，底を記入する必要がないのです。

ハッシュ表の例
ハッシュ値

データ

0

25

1

11

2

7

3

13

4

4

ここで，探索するデータが「7」のとき，h（7）＝7 % 5＝2となり，ハッシュ値が「2」の場所を見るとデータ「7」が見つかります。
この方法は演算ですぐに格納場所が見つかるので，データ量に関係なく計算量はO（1）となります。
ただし，違うデータでハッシュ値が重なるシノニムという問題が発生することがあり，その場合には工夫が必要です。
それでは，次の問題を解いてみましょう。

発展

シノニムの解決方法としては，そのシノニムデータを線形リストによって管理するチェイン法や，次の空き
位 置にデ ータを格 納する
オープンアドレス法などがあります。チェイン法については，応用情報技術者試験
平成 21年春 午後 問2で詳しく出題されています。

68

第1章

基礎理論

問題

過去問題をチェック

ハッシュ表探索に関するプ
ログラミング問題が，応用情報技術者試験
平成 21年春 午後 問2，
平成 23 年秋 午後 問2で出題されています。また
午前でも，ハッシュ法について，応用情報技術者試験
平成 23 年特別 午前 問8，
平成 23 年秋 午前 問 5でも出題されています。午前でも午後でも周期的に出題されていますので，探索方法をしっかり押さえておきましょう。

探索表の構成法を例とともに a 〜 c に示す。最も適した探索手法の組合せはどれか。ここで，探索表のコードの空欄は表の空きを示す。
a コード順に格納した b コードの使用頻度順に探索表格納した探索表
コード120380120381120520140140

データ
……
……
……
……

コード
120381140140120520120380ac コードから一意に決まる
場所に格納した探索表

データ
……
……
……
……

コード

データ

120381……

120520140140……
……

120380……

b

ア 2 分探索

線形探索c
ハッシュ表探索

イ 2 分探索

ハッシュ表探索線形探索

ウ 線形探索2 分探索

ハッシュ表探索エ 線形探索ハッシュ表探索2 分探索（平成 25 年春 応用情報技術者試験 午前 問5）

解説
a 〜 cの探索表をそれぞれ見ていきます。
a：コード順に格納した探索表の場合
線形探索では上から順に単純に見ていくため，計算量はO （n）になります。これに対し，2 分探索を用いると，真ん中のデータと比較して半分にしていくので計算量がO（log n）となり，線形探索
より効率的です。なお，ハッシュ値で格納されているわけではな
いので，ハッシュ表探索は使用できません。
b：コードの使用頻度順に格納した探索表の場合
線形探索で上から順番に見ていく場合，一番上に最も使用頻度の高いデータがあるので，通常の並びに比べて早く見つかる可能性が高くなります。なお，2 分探索は整列されていないデータには

1-2

アルゴリズムとプログラミング

使用できず，ハッシュ表探索はハッシュ値を使用していないデー

1

タには使用できません。
c：コードから一意に決まる場所に格納した探索表の場合コードから一意に決まる場所はハッシュ値によって求められる
ので，ハッシュ表探索が計算量O（1）で使用できます。線形探索
でも探索はできますが，データが格納されていない領域などもあるので効率は悪くなります。また，整列されていないデータなので 2 分探索は使用できません。
≪解答≫ア

整列アルゴリズム
整列のアルゴリズムは，昇順（小さい順）または降順（大きい順）にデータを並び替えるアルゴリズムです。代表的な整列アルゴリ
ズムには以下の七つがあります。

①バブルソート
隣り合う要素を比較して，大小の順が逆であれば，その要素を入れ替える操作を繰り返すアルゴリズムです。隣同士を繰り発展

整列アルゴリズムは，①〜③が基本 3 ソート，④〜⑦が応用 4 ソートというかた
ちで 分 類されます。 基 本
ソートの三つは，単純です
が時間がかかります。応用
ソートは，それぞれアルゴ
リズムは複雑ですが，速度が改善されて効率良く整列を行うことができます。

返しすべて比較するので，計算量はO（n2）となります。

②挿入ソート
整列された列に，新たに要素を一つずつ適切な位置に挿入する操作を繰り返すアルゴリズムです。挿入位置を決めるのに線
形探索を行うため，計算量はO（n2）となります。

③選択ソート
未整列の部分列から最大値（または最小値）を検索し，それを繰り返すことで整列させていくアルゴリズムです。最小値の探索を毎回行うため，計算量はO（n2）となります。

④クイックソート
最初に中間的な基準値を決めて，それよりも大きな値を集めた部分列と小さな値を集めた部分列に要素を振り分けます。そ69

発展

クイックソートでは，ランダムなデータなどでうまく基準値を選べると非常に効率的な計算が行えるため，
クイックソートの名のとおり，ランダムに並んだデー
タを整列させるときの速度は最も速くなります。しかし，最初から整列してある
データなどではかえって非効率になり，最悪の場合，計算量がO（n2）となってしまうことがあるため，使う場面には注意が必要です。

70

第1章

基礎理論

の後，それぞれの部分列の中で基準値を決めて，同様の操作を繰り返すアルゴリズムです。ランダムなデータの場合には，計算量はO（nlog n）となります。

⑤シェルソート
ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列させ，さらに間隔を狭めて同様の操作を繰り返し，最後に間隔を1にして完全に整列させるというアルゴリズムです。挿入ソートの発展形で，ざっくり整列させてから細かくしていくので効率が良くなります。間隔は，15，7，3，1……と，2n −1で nを一つずつ減らして狭めていくので，計算量はO（nlog n）となります。

関連

ヒープについては，「1-2-1
データ構造」（P.63）を参照
してください。

⑥ヒープソート
未整列部分でヒープを構成し，その根から最大値（または最小値）を取り出して整列済の列に移すという操作を繰り返して，未整列部分をなくしていくアルゴリズムです。選択ソートの発展形であり，ヒープを使うことで，最大値（または最小値）を検索する作業を効率化しています。そのため，計算量はO（nlog n）となります。

⑦マージソート
未整列のデータ列を前半と後半に分ける分割操作を，これ以上分割できない，大きさが 1の列になるところまで繰り返します。
その後，分割した前半と後半をマージ（併合）して，整列済のデー
タ列を作成することを繰り返し，最終的に全体をマージするアルゴリズムです。計算量はO（nlog n）と効率的ですが，マージするための領域が必要となるので，作業領域（メモリ量）を多く消費することが欠点です。
それでは，次の問題を解いてみましょう。

1-2

アルゴリズムとプログラミング問題

過去問題をチェック

次の手順はシェルソートによる整列を示している。データ列 7，
2，8，3，1，9，4，5，6 を手順（1）〜（4）に従って整列す
るとき，手順（3）を何回繰り返して完了するか。ここで，［］は小数点以下を切り捨てた結果を表す。
〔手順〕（1）［データ数÷ 3］→ H とする。
（2） データ列を，互いにH 要素分だけ離れた要素の集まりからな
る部分列とし，それぞれの部分列を，挿入法を用いて整列する。
（3）［H ÷ 3］→ H とする。
（4） H が 0 であればデータ列の整列は完了し，0 でなければ（2）
に戻る。
ア 2

イ 3

ウ 4

エ 5

（平成 24 年春 応用情報技術者試験 午前 問7）

解説
データ列 7，2，8，3，1，9，4，5，6を手順（1）〜（4）に従って，
シェルソートにより順に整列していきます。データ列より，データ
数は 9です。
〔手順1回目〕（1）［データ数（9）］÷3 → 3で，H ＝3（2） データ列を3ごとの部分列とし，それぞれの部分列を，挿入法を用いて整列します。次のようなかたちになります。

7，2，8，3，1，9，4，5，6

それぞれの部分列ごとに整列すると，次のようになります。

整列のアルゴリズムは，以前のソフトウェア開発技術者試験ではよく出題されていましたが，最近はあまり出題されていません。
アルゴリズム問題は知識よ
りも実際に流れを追う問題が出題される傾向があります。それぞれのアルゴリズ
ムの特徴を実際の流れで確認しておきましょう。

71

1

72

第1章

基礎理論

3，1，6，4，2，8，7，5，9（3）［3÷3］→ 1で，H ＝1（4） Hは1で，0 ではないので（2）に戻ります。
〔手順 2回目〕（2） データ列を1ごとの部分列にします。1ごとなので，すべて一つにまとまります。1回目でできた列が3，1，6，4，2，8，7，5，9
なので，これを挿入法で整列すると，
1，2，3，4，5，6，7，8，9となります。
（3）［1÷3］→ 0で，H ＝0（4） H ＝0なので，データ列の整列は完了です。
したがって，（3）は 2回実行されるので，アの2 が正解になります。
≪解答≫ア

発展

クイックソート，
マージソー
トなどは，再帰を用いてプ
ログラムを記述することもできます。

再帰のアルゴリズム
再帰とは，再び帰る，つまり，自分自身をもう一度呼び出すよ
うなアルゴリズムです。関数などで，呼び出した関数自身を呼び出す場合が再帰に当たります。
言葉だけではイメージしづらいので，問題を見ながら再帰を感じてみましょう。

問題
次の数式は，ある細菌の第 n 世代の個数（f n ）が 1 世代後にどのように変化するかを表現したものである。この漸化式の解釈として，1 世代後の細菌の個数が，第n 世代と比較してどのようになるかを説明しているものはどれか。

f （n ＋ 1）＋ 0.2 ×f （n ）＝ 2 ×f （n ）

1-2

アルゴリズムとプログラミング

ア

1世代後の個数は，第n 世代の個数の1.8 倍に増える。

イ

1世代後の個数は，第n 世代の個数の2.2 倍に増える。

ウ

1世代後の個数は，第n 世代の個数の 2 倍になり，更に増殖
後の20％が増える。

エ

1世代後の個数は，第n 世代の個数の 2 倍になるが，増殖後の20％が死ぬ。
（平成 21年春 応用情報技術者試験 午前 問5）

解説
この問題でいう，ある細菌の第n 世代の個数を示す関数f （n ）では，この値を計算するのに，同じ関数f （n ）を，n の値を変えて再利用します。これが再帰です。
問題の式だと分かりにくいので，変形すると次のようになります。

f （n ＋1）＝1.8×f （n ）ここで，f （n ＋1）はf （n ）の1.8 倍になることが分かります。
そしてこの式からf （n ）を求めるためには次の式を計算する必要があることが分かります。

f （n ）＝1.8×f （n −1）
さらに，f （n −1）＝1.8×f （n −2），f （n −2）＝1.8×f （n −3）……と，どんどんさかのぼっていく必要が出てきます。この計算自体が，再帰計算です。
ちなみに，問題自体はf （n ＋1）＝1.8×f （n ）なので，単純に，1世代後の個数は第n 世代の個数の1.8 倍に増えます。
≪解答≫ア

文字列処理のアルゴリズム
文字列処理のアルゴリズムには，文字列の探索，置換などがあります。文字列の探索には，単純に前から探索する方法のほ
かに，BM 法（ボイヤ・ムーア法）などの効率的な探索方法があります。置換は探索の後に行われるので，基本的に文字列探索と同じアルゴリズムです。
それでは，実際の午後問題を例に，文字列探索のアルゴリズ
ムを学習していきましょう。

73

1

74

第1章

基礎理論

問題

勉強のコツ

アルゴリズム問題は，実際のプログラムも大 事ですが，その前の説明文をしっ
かり理解してプログラムと対 応 付けることが 大 切です。文章の部分もしっかり読みましょう。そして，その文章を理解することが，アルゴリズムの学習にもつながります。

文字列照合処理に関する次の記述を読んで，設問 1，2 に答えよ。
ある文字列（テキスト）中で特定の文字列（パターン）が最初に一致する位置を求めることを文字列照合という。そのための方法として，次の二つを考える。ここで，テキストとパターンの長さは，どちらも 1 文字以上とする。
〔方法 1

単純な照合方法〕

テキストを先頭から 1 文字ずつパターンと比較して，不一致の文字が現れたら，比較するテキストの位置（比較位置）を 1 文字分進める。この方法による処理例を図 1 に示す。
位置 1 2 3 4 5 6 7 8 9 10
テキスト A B C D E F G H I Jパターン C D E 不一致なので，1文字分進める。
C D E 不一致なので，1文字分進める。
C D E 一致

図1 単純な照合方法

この手順を基に，テキストとパターンを与えると，最初に一致した文字位置を返すアルゴリズムを作成した。このアルゴリズムを図 2 に示す。
なお，テキストは配列 T，パターンは配列 P に格納されており，T［n］及び P［n］はそれぞれの n 番目の文字を，T.length 及びP.length はそれぞれの長さを示す。

1-2

アルゴリズムとプログラミング

1function search1(T,P)
まで1ずつ増やすfor iを1からまで1ずつ増やすfor jを1から

if T[i＋j−1]とP[j]が等しい

←α

が等しい

if jと
return i
endif
else
break
endif
endfor
endforreturn −1// パターンが見つからない場合は−1を返す

endfunction
図2 単純な照合方法のアルゴリズム〔方法 2

効率的な照合方法〕

方法 1 では，パターンとテキストの文字が不一致となった場合，比較位置を 1 文字分進めている。ここでは，比較位置をなるべく多くの文字数分進めることで，照合における比較回数を減らすことを考える。
パターンの末尾に対応する位置にあるテキストの文字（判定文字）に着目すると，次のように比較位置を進める文字数（スキップ数）が決定できる。
（1） 判定文字がパターンに含まれていない場合は，判定文字とパターン内の文字の比較は常に不一致となるので，パターンの文字数分だけ比較位置を進める。また，判定文字がパターンの末尾だけに含まれている場合も，同様にパターンの文字数分だけ比較位置を進める。
（2） 判定文字がパターンの末尾以外に含まれている場合は，判定文字と一致するパターン内の文字が，テキストの判定文字に対応する位置に来るように比較位置を進める。ただし，パターン内に判定文字と一致する文字が複数ある場合は，パターンの末尾から最も近く（ただし，末尾を除く）にある判定文字と一致するパターン内の文字が，判定文字に対応する位置に来るように比較位置を進める。

75

76

第1章

基礎理論

この方法による処理例を図 3 に示す。
位置 1 2 3 4 5 6 7 8 9 10 11
テキスト A B C D E J F G H I J
発展

さらに効率的な照 合 方 法として，テキストとパターンを比較するとき，先頭からではなく最後の文字から順に比較する方法があります。この 方 法 は BM 法（ ボイヤ・ムーア法）と呼ばれるもので，文字列探索では一般的に使われているアルゴリズムです。

パターン HI

J

C はパターンに含まれないので，3文字進める。
HIJ

J はパターンの末尾だけに含まれるので，3文字進める。
H

注

I

は判定文字を表す。

J

H はパターンの1文字目と一致するので，2文字進める。

H

I

J

一致

図3 効率的な照合方法

パターンが与えられると，判定文字に対応するスキップ数を一意に決定することができる。例えば，パターン HIJ に対して判定
文字とスキップ数の対応表を作成すると表 1 のようになる。
表 1 パターンHIJに対するスキップ数
判定文字

H

I

J

その他の文字

スキップ数

2

1

3

3

この考え方を基に作成したアルゴリズムを図 4 に示す。
なお，テキストは配列 T，パターンは配列 P，スキップ数を決める表の判定文字は配列 C，スキップ数は配列 D に格納されており，
T[n]，P[n]，C[n]，D[n] はそれぞれの n 番目の文字又は数値を，T.length 及び P.length はテキストとパターンの長さを示す。
このアルゴリズムは，三つの主要部分から成っている。一つ目は，与えられたパターンについて判定文字とスキップ数の対応表を作成する処理である。ここでは，配列 C に格納される空白文字は表1 の“その他の文字”及びパターンの末尾の文字“J”を表現するために使用している。テキストとパターンは空白文字を含まないものとする。二つ目は，文字を比較する処理である。ここでは，現在の比較位置に対応したテキストとパターンを方法 1 と同様に 1
文字ずつ比較して，パターンに含まれる文字と対応するテキストの文字がすべて一致するか，不一致となる文字が見つかるまで繰り返す。三つ目は，判定文字とスキップ数の対応表を引いてスキッ
プ数を決定する処理である。

1-2function search2(T,P)
for xを1からP.lengthまで1ずつ増やす
C[x] ← " "// " "は空白文字を表す
D[x] ← P.length
endfor// （1）：表の作成
for jを1からP.length−1まで1ずつ増やす
for kを1からjまで1ずつ増やす
if C[k]とP[j]が等しい or C[k]と" "が等しい
C[k] ← P[j]D[k] ←
break
endif
endfor
endfor// 文字列を照合する
i ← 1
while iが// （2）：文字の比較

以下である

まで1ずつ増やすfor jを1から
if T[i＋j−1]とP[j]が等しい

←β

if jと
が等しい
return i
endif
else
break
endif
endfor// （3）：スキップ数の決定
for kを1からP.lengthまで1ずつ増やす
if C[k]とT[i＋P.length−1]が等しい or C[k]と" "が等しいd ← D[k]
break
endif
endfori ← i＋d
endwhile
return −1
endfunction
図 4 効率的な照合方法のアルゴリズム

アルゴリズムとプログラミング

77

1

78

第1章

基礎理論

設問 1

図 2 及び図 4 中の〜アに入れる適切ウ

な字句を答えよ。
設問 2パターン HIPOPOTAMUS に対するスキップ数を表 2 に
示す。

，

エ

に入れる適切な数値を答えオよ。
表 2 パターンHIPOPOTAMUSに対するスキップ数
H

I

P

O

T

A

M

U

S

その他
の文字

スキップ数 エ

9

オ

5

4

3

2

1

11

11

判定文字

（平成 21年秋 応用情報技術者試験 午後 問2 抜粋）

解説
設問1・空欄ア，イ
単純な照合方法のアルゴリズムについての穴埋め問題です。基
本 3 構造，特にループ（繰返し）を中心に図 2 の構造を考えると，
次のようになります。

function search1(T,P)
まで1ずつ増やすfor iを1からまで1ずつ増やすfor jを1から

if T[i＋j−1]とP[j]が等しい
が等しい

if jと
return i
endif
else
break
endif
endfor
endforreturn −1
endfunction

ループ②
ループ①
// パターンが見つからない場合は−1を返す

1-2

アルゴリズムとプログラミング

方法の説明と，アルゴリズムを対応させていきます。
外側のループ①が，〔方法1 単純な照合方法〕の「テキストを先頭から1文字ずつパターンと比較して，不一致の文字が現れたら，比較するテキストの位置（比較位置）を1 文字分進める」部分に該当します。つまり，先頭から1文字ずつ，最後まで比較していくルー
プです。
この ル ープ が 終 わ るの は，最 後 まで 探 索し 終 わ ったとき——といっても，テキストT が一致する可能性があるのは，パター
ンP の最後がパターンT の最後と重なるときまでです。そのため，
以下のようなかたちになったときが最後になります。
位置
テキストT

1 2 3 4 5 6 7 8 9 10
最後尾が一致するのが最後
1 2 3

パターンP

最後尾が一致するときの位置は，「テキストTの長さ−パターン
P の長さ」からは一つ進んだところになります。そのため，iは1から最後尾が一致するとき，つまり，T.length−P.length＋1までとなります。そしてこれが，空欄アの答えです。
内側のループ 2は，テキストTとパターンPを比較するループです。こちらは，パターンPを1文字ずつ最後まで比較していくので，ループの終わりはP.lengthになります。
・空欄ウ
効率的な照合方法のアルゴリズムについての穴埋め問題です。
図 4 の効率的な照合方法のアルゴリズムでは，（1）：表の作成，（2）：
文字の比較，（3）：スキップ数の決定，の三つの部分に分かれています。空欄ウは，（1）：表の作成の部分なので，その部分の構造を考えると次のようになります。

79

1

80

第1章

基礎理論

// （1）：表の作成
for jを1からP.length−1まで1ずつ増やす
for kを1からjまで1ずつ増やす

ループ③
ループ④

if C[k]とP[j]が等しい or C[k]と”“が等しいC[k] ← P[j]D[k] ←
break

ウ

選択①

endif
endfor
endfor

このとき，ループ③とループ④で，パターン Pと判定文字の配列 Cを比較し，その結果，スキップ数の配列 Dを求めます。このとき，判定文字がパターンの末尾以外に含まれている場合には，〔方法2 効率的な照合方法〕（2）に「判定文字と一致するパターン内の文字が，テキストの判定文字に対応する位置に来るように比較位置を進める」とあります。この位置がスキップ数になります。スキッ
プ数は，最後尾の一つ前なら1，二つ前なら2……，先頭なら（パターンの文字数−1）となるので，空欄ウにはP.length−jが入ります。
設問 2
先ほどの図4「（1）：表の作成」
を使って，パターンHIPOPOTAMUS
を例にトレースしてみます。このとき，P.length＝11です。j＝1，
k＝1から順に考えていくと，最初の H では，配列 Cはまだ空白しか入っていないので，C［1］と" " が等しくなり，C［1］← H，D［1］← 11−1＝10 が入ります。同様に，HIPOまで終わらせると，配列CとDは次のようになります。
判定文字 CH
スキップ数 D 10

I
9

P

8

O
7

他
11

このとき，
次のPは3 番目のPと一致します。その場合には，
C［3］とP［5］が等しいことになるので，配列 Dは上書きされて，D［3］←11−5＝6となります。同様に繰り返していくと，最終的な表は次のようになります。

1-2

判定文字 CH
スキップ数 D 10

I
9

P

6

O
5

T

4

…
…

アルゴリズムとプログラミング他
11

したがって，Hのスキップ数は10，Pのスキップ数は6です。
≪ 解 答≫
設 問1 ア：T .l e n g t h −P .l e n g t h ＋1
イ：P.length，ウ：P.length−j
設問 2

エ：10，オ：6

その他のアルゴリズム
その他のアルゴリズムとして定番のものには，グラフのアルゴ
リズム，近似・確率統計などの数学的なアルゴリズム，データ圧
縮のアルゴリズム，図形描画のアルゴリズム，メモリ管理のアルゴリズムなどがあります。
出題頻度は低いですが様々なものがありますので，見かけたらその仕組みを理解しておきましょう。

□

基本 3ソートの計算量はO（n2），応用 4 ソートの計算量はO（nlog n）□

プログラムの構造を追っていくときには，ループ（繰返し）がポイント

81

1

82

第1章

基礎理論

アルゴリズム問題のポイント
アルゴリズム問題，特に午後問題で出される流れ図や疑似言語の問題を解くポイントとしては，次の三つが挙げられます。
1．プログラムの構造を明らかにする
2．実際に値を入れて，トレースする
3．最後の値を意識する
1の「プログラムの構造」とは，基本3構造のことです。特にループ（繰返し）を意識すると，プログラムの流れがよく見えてきます。そしてその構造を，実際の問題文でのアルゴリズムの説明と対比させることにより，プログラムの全体像が見えてきます。
2 の「トレース」は，面倒がらずやることが大切です。実際に手を動かして，i の値を 1，2……と増やしていきましょう。最後までやらなくても流れは見えてくると思いますが，最初からやらな
いとイメージが湧きません。
3 の「最後の値」というのは，最後の値が n で終わるのか n −1
で終わるのかといった，微妙な±1の範囲の話です。実は，プログラムのミスはこの±1の差で起こることが多いので，アルゴリ
ズム問題ではここを聞いていることが多いのです。実際に問題を解くときには，ぜひ，この「最後の値」はていねいに導き出していきましょう。
最後に，アルゴリズム問題は「慣れ」が肝心です。実際にプログラムしたりアルゴリズム問題を解いたりして，解く感覚を磨いていきましょう。

1-2

1-2-3

アルゴリズムとプログラミング

プログラミング

1

プログラミングにおいては，いろいろなプログラムの構造やその動きを知ることが大切です。

プログラム構造プログラムは，再使用できるか，同じものを呼び出すことができるかなどの観点で，次の四つの構造に分類されます。

①再使用可能（リユーザブル）プログラム
一度使用したプログラムを再度使用できるプログラムです。
つまり，プログラムを一度終了させた後に再度起動させることが可能です。再使用が不可能なプログラムとは，一度終了させた
ら電源を切って再起動しないと動かないものなので，現在のプロ
グラムはほとんどが再使用可能です。

②再入可能（リエントラント）プログラム
プログラムが使用中でも，再度入ってもう一つ起動させることができるプログラムです。一つのプログラムを複数立ち上げることができ，その複数のプログラムを管理するために，共通の領域のほかにそれぞれのプログラムを独立で管理する領域が必要になります。そして，再入可能プログラムは複数起動が可能なので，必ず再使用可能プログラムでもあります。

③再帰（リカーシブ）プログラム
自分自身を呼び出すことができるプログラムのことを，再帰プ
ログラムと呼びます。再帰のアルゴリズムを使うようなプログラ
ムで使用されます。そして，再帰プログラムは，自分自身に再入するので，必ず再入可能プログラムでもあります。
①〜③の関係を図にすると，右のようになります。

83

再使用可能プログラム
再入可能プログラム
再帰プログラム

各プログラムの関係

関連

逐次再使用可能プログラム（Serially Reusable Program）
は，再使用可能プログラムの一種です。再使用可能プ
ログラムのうち，複数の要求が来たときに一度に一つずつしか処理を行わないプ
ログラムを指します。そのため，逐次再使用可能プロ
グラムは再入可能プログラ
ムとはなりません。
発展

再入可能プログラムの代表例としては，I E（インターネットエクスプローラ）な
ど の Web ブラウザ があります。 一 つ のプ ログ ラ ム
に対していくつも同じものを立ち上げることができます。 そし て，そ れ ぞ れ のWeb ブラウザは別の Web
ページを見に行くので，見に行った Web ページの情報を別々に格納しておく必要があります。

84

第1章

基礎理論

④再配置可能（リロケータブル）プログラム
プログラムをメモリ上で再配置することが可能なプログラムです。メモリのアドレスを指定する際，相対アドレスですべて指定しているプログラムは再配置可能になります。メモリの位置を指定する必要があるOSなどのプログラムのほかは，ほとんどの場
合，再配置可能にすることができます。
それでは，実際の問題を解いてみましょう。

問題
再入可能（リエントラント）プログラムに関する記述のうち，適切なものはどれか。
ア

再入可能プログラムは，逐次再使用可能プログラムから呼び出すことはできない。

イ

再入可能プログラムは，呼出し元ごとに確保された記憶領域に局所変数が割り当てられる。

ウ

実行途中で待ち状態が発生するプログラムは，再入可能プロ
グラムではない。

エ

逐次再使用可能なプログラムは，再入可能プログラムでもある。
（平成 22 年秋 応用情報技術者試験 午前 問8）

解説
再入可能プログラムは，呼出し元ごとに確保された記憶領域に局所変数が割り当てられるので，選択肢イが正解です。再入可能
プログラムの場合，複数のプログラムを区別して管理するために，呼出し元ごとに独自変数を管理する必要があります。
ア 再入可能プログラムは，ほかのプログラムから呼出し可能です。逐次再使用可能プログラムからでも呼び出すことができます。
ウ 待ち状態は，入出力の待ちなどで発生するので，プログラムの構造とは関係ありません。

1-2

アルゴリズムとプログラミング

エ 逐次再使用可能は再入可能プログラムではありません。また，

1

再入可能プログラムは再使用可能です。
≪解答≫イ

□

再帰プログラムは再入可能プログラム□

再入可能プログラムは再使用可能プログラム

1-2-4

プログラム言語

プログラム言語については，それぞれの特徴だけでなく，「なぜその言語ができたのか」という背景を知っておくと，より深く理解できます。

プログラム言語の変遷
プログラム言語は，人間と機械を結び付けるためにできたものです。コンピュータは機械語（マシン語）しか理解できないのですが，人間が機械語でプログラムを組もうとするととても大変です。そこで，機械語との橋渡しを行うために，いろいろなプログ
ラム言語が登場してきました。
プログラム言語は，人間の役に立つために，そして，時代の需要に合わせるために徐々に進化してきました。進化の流れを次表にまとめます。
進化の流れ
アセンブリ
言語

高級言語

発展

構造化言語

オブジェク
ト指向言語

if(a==b)while(1)class Aprivate b

種類

機械語

特徴

0101011110101MOV AXADD AY

Z＝X＋Y

言語例

−

CASLII，
Z80

FORTRAN，C，Pascal
COBOL

Smalltalk,
C++, Java

言語の種類

流れを追いつつ，それぞれの言語の特徴を見ていきましょう。

85

基本情報技術者試験で出題されるアセンブリ言 語（CASLII）は，仮想機械をイメージしたアセンブリ言語です。一度勉強してみると，機械がプログラムをどう処理していくのかイメージしやすくなると思います。

86

第1章

基礎理論

①機械語（マシン語）
コンピュータが解釈できるのは，2 進数の機械語のみです。2進数の羅列なので人間にはとても分かりにくく，実際には 16 進
数で表記させてプログラムしていました。

②アセンブリ言語
機械語と1 対 1 で対応させることで書きやすくした言語です。
加算演算をADD，データの移動をMOVなどで表現します。ただし，機械語を置き換えただけなので，人間の考え方とはだいぶ異なります。例えば，C＝A＋Bを計算する場合は次のようになります。
MOV PA，A
MOV PB，B
ADD PA，PB
MOV Z，PA
このように，一つ一つプログラムを考えるのが大変でした。

発展

一般にコンピュータの世界
では，人間に近いものを高級（または高レベル），コン
ピュータに近いものを低級（または低レベル）と呼びます。高級言語とは，人間に近い言語という意味です。

③高級言語（高水準言語）
人間にとってわかりやすい形式というコンセプトで書かれた言語です。高水準言語とも呼びます。前述の C＝A＋Bなどは，そのままC＝A＋Bと書けるようになりました。
人間にとって分かりやすくといっても，いろいろな手法があります。英語で文章を書くように事務処理を記述できる言語がCOBOL です。また，数式で科学技術計算を行うための言語がFORTRANです。

④構造化言語
高級言語でプログラムするとき，適当に行をジャンプすることを繰り返していると，混沌として分かりづらいプログラム（これをスパゲティプログラムと呼びます）になりがちでした。それを解消しようと，ダイクストラという人が基本 3 構造（「1-2-2 アルゴ
リズム」P.64 参照）を提案しました。プログラムを書くときには，順次，選択，繰返しの基本 3 構造だけで書き，適当にジャンプするための GOTO 命令は極力使わない「構造化プログラミング」という考え方です。

1-2

アルゴリズムとプログラミング

その結果登場したのが，構造化言語です。C やPascalなどがこれに該当します。選択を表す if 文，繰返しを表す while や for
文が加わりました。さらに，関数やサブルーチンという，同じ処理をする単位にまとめるという考え方も，構造化言語あたりから進化してきました。

⑤オブジェクト指向言語
関数（及びサブルーチン）などによるプログラムでは，グロー
バル変数と呼ばれる，複数の関数で共通使用する変数の内容が，意図しない場所で書き換えられたりして不具合を起こすことが多くなりました。そこで，グローバル変数をなくし，共通で同じ変数を使用する関数をまとめるクラスという考え方が必要になりました。
また，クラス以外にも，オブジェクト指向というオブジェクト
やクラスを中心とする考え方が提唱されました。それらはプロ
グラミングに様々なメリットをもたらすため，新しい言語がいろ
いろ開発されています。最初にできたオブジェクト指向言語はSmalltalk で，その後，C 言語の発展形であるC++ や Java 言語などが登場しました。
Java 言語では，C や C++ で問題となっていた，使用が終わったメモリを解放しないメモリリークという問題に対応するため，自動でメモリを解放するガーベジコレクションという機能があります。

その他の言語分類
プログラム言語は，時代の流れ以外にも様々に分類できます。
代表的なものを紹介します。

①手続型言語処理手順を，1 行 1 行順を追って記述する言語です。COBOL，
FORTRAN，C，C++，Java など，通常のプログラム言語はほとんどがこれに該当します。

②関数型言語関数の定義とその呼出しでプログラムを記述する言語です。

87

1

88

第1章

基礎理論

再帰処理向きで，代表的なものに Lisp があります。C 言語の関数とは意味が異なる数学的な形式なので，注意が必要です。

③論理型言語述語論理を基礎とした論理式でプログラムを記述する言語です。人工知能の研究開発で使用されるPrologなどが代表例です。

発展

簡易的といっても，最近はそのスクリプト言語で本格的な Web システムを作る
例も多くなってきました。
PHP や Perl，Ruby な ど は
大規模な用途にも使われています。
用語

シェルとは，UNIX 上でユー
ザからの指示を解釈し，プ
ログラムの 起 動や制御を行うプログラムです。シェ
ルスクリプトには，Bourne
Shell（sh），C Shell（csh），
TENEX C Shell（tcsh）な ど
様々な種類があり，ユーザの好みによって置き換え可能です。

④スクリプト言語
プログラムを機械語にコンパイルするのではなく，スクリプ
ト（台本）のように記述して1 行 1 行処理する簡易的な言語です。
UNIX 上でシェルを動かすためのシェルスクリプトや，Excel の
マクロ言語などがあります。
Web ブラウザ上で動くスクリプト言語として，Java 言語と似た言語で記述する JavaScript と JScript があります。これら
二つは互換性が低いので，共通する部分をまとめて標準化した
ECMAScript が作られました。Web サーバ上で動くJava のスク
リプト言語にはJSP（Java Server Pages）があります。なお，
サー
バ上では，スクリプト言語ではない Javaアプリケーションやサー
ブレットも動きます。その他，Web サーバ上で動くJava 以外のスクリプト言語としては，Perl，Ruby，PHPなどがあります。
それでは，次の問題を解いてみましょう。

問題
HTML だけでは実現できず，JavaScript を使うことによってブラウザ側で実現可能になることはどれか。
ア アプレットの使用

イ 画像の表示ウ サーバへのデータの送信

エ 入力データの検査（平成 22 年春 応用情報技術者試験 午前 問7）

1-2

アルゴリズムとプログラミング

1

解説
JavaScript は，ブラウザ側にプログラムを送り，ブラウザ上で実行します。そのため，HTML 文では実行できない動的な処理，例えば，入力されたデータが適正かどうか検査するなどの処理を実行できます。したがって，選択肢エの入力データの検査が正解です。
ア アプレットは，HTML 文の<applet>タグで使用できます。ア
プレットは，ブラウザにダウンロードして実行します。
イ 画像の表示は，HTML 文の<img>タグで実現できます。
ウ サーバへのデータ転送は，HTML 文の <form>タグで囲った
領域で <input>タグに入れられたデータを転送することで実現できます。
≪解答≫エ

共通言語基盤
共通言語基盤（CLI：Common Language Infrastructure）は，プログラム言語やコンピュータアーキテクチャに依存しない環
境を定義したものです。様々な高級言語で書いたプログラムを，書き直すことなく他のプラットフォームでも使うことができます。マイクロソフトが策定した.NET Frameworkの基幹を構成す
る実行コードや実行環境などについての仕様です。

Ajax
Ajax（Asynchronous JavaScript + XML）は，Web ブラウザ
上で非同期通信を実施し，通信結果によってページの一部を書き換える手法です。JavaScript の通信機能を利用し，新技術で用語.NET Framework と は， マ
イクロソフトが開発したアプ
リケーションの開発・実行環境です。.NET Framework
でコンパイルしたプログラ
ムは，Linux やMac OSなど，
Windows 以 外の OS でも動かすことができます。

過去問題をチェック

Ajax については，応用情報技術者試験
平成 24 年秋 午前 問 32で出題されています。

はなく従来の技術を組み合わせて非同期通信を実現します。

□

89

サーバで動くJSP，サーブレット，クライアントで動くJavaScript，アプレット

90

第1章

基礎理論

1-2-5

その他の言語コンピュータ上でやりたいことを実現するために，プログラ
ム言語以外の言語を用いることもあります。その代表的なものにマークアップ言語があります。

データ定義言語デ ー タ 定 義 言 語（DDL：Data Definition Language）は，コンピュータのデータを定義するための言語や言語の要素です。
XML のデータを定義するDTD（Document Type Definition）や，関連

SQL-DDL に つ い て は，
「33-3 デ ー タ 操 作 」（P.216）
で詳しく取り上げます。

データベース言語 SQL の一部であるSQL-DDL は，データ定義
言語の一例です。

Web ページを記述するためのマークアップ言語
Web ページを記述するためのマークアップ言語には，次のよ
うなものがあります。

発展

HTML，XMLはともに，SGML（St andar d Gener alized
Markup Language）か ら 派
生した言語です。XMLはより厳密に進化したのに対し，HTMLはあいまいさを残していましたが，XML が一般化するにつれ，HTMLをXMLに適合させたいという需要がでてきたため，XHTML ができました。
過去問題をチェック

CSS についての問題が，応用情報技術者
平成 22 年秋 午後 問8に出題されています。また，
HTMLについては
平成 22 年春 午前 問 7で，XMLについては
平成 21年秋 午前 問8で出題されています。
地味に少しずつ出題されていますし，実務でもよく使われているものなので，知識は押さえておきましょう。

① HTML（HyperText Markup Language）
Web ページを作成するために開発された言語です。ハイパー
テキストと呼ばれる，通常のテキストのほかに他のページへのリンク（ハイパーリンク）を埋め込むことができるテキストを使用します。画像，音声，映像などのデータファイルもリンクで埋め込
むことができます。

② XHTML（Extensible HTML）
HTML を XML の文法で定義し直したものです。より厳密に記述のチェックを行います。例えば，XML 文書であるため，次のようなXML 宣言を行う必要があります。
<?xml version="1.0" encoding="Shift_JIS"?>その他，要素名や属性名はすべて小文字でなければならない，
必ず開始タグと終了タグで囲まれていなければならないなど，様々な制約があります。

③ CSS（Cascading Style Sheet）
文章のスタイルを記述するためにできた言語で，HTML や1-2

アルゴリズムとプログラミング

XHTML の要素をどのように表示するか定義します。文章の構

1造と体裁を分離させるという理念の下，文章の構造はHTMLで，
体裁はCSSで記述します。

XML（Extensible Markup Language）
特定の用途に限らず，汎用的に使うことができる拡張可能なマークアップ言語です。文書構造の定義は，DTDで行います。
XML 文書の正当性の水準には，次の二つがあります。

①整形式 XML 文書（well-formed XML Document）
XML データを記述するための文法に従った XML 文書です。
DTD での定義は存在しない，または定義に適合していなくても支障はありません。

②妥当な XML 文書（valid XML Document）
DTD の定義に適合した XML 文書です。整形式 XML 文書でもあります。
XML では，厳密に妥当な XML 文書のみを許可することも，整形式の文書で手軽にXMLを利用することも可能です。
その他，XML 文書を変換するために使われる XSLT（XSL
Transformation），XML 文書同士のリンクを設定するための
XLink（XML Linking Language）など，XML 文書を扱うための言語にも様々なものがあります。
また，XML 形式を利用した応用例として，円や直線などの図
形オブジェクトをXML 形式で記述する画像フォーマットである
SVG（Scalable Vector Graphics）や，ユーザの認証情報をXML形式で表現する仕様であるSAML（Security Assertion Markup
Language）など，様々なものがあります。
それでは，問題を解いていきましょう。

91

過去問題をチェックSVGについて，応用情報技術者試験
平成 24 年秋 午前 問 34で出題されています。

92

第1章

基礎理論

問題
整形式（well-formed）の XML 文書が妥当（valid）な XML 文書
である条件はどれか。
ア DTDに適合している。
イ XML 宣言が完全に記述されている。
ウ XML データを記述するための文法に従っている。
エ エンティティ参照ができる。
（平成 22 年春 応用情報技術者試験 午前 問8）

解説
妥当（valid）な XML 文書とは，DTD の定義に適合した XML 文
書です。したがって，選択肢アが正解です。
イ XML 宣言は，文法に従うための必要条件の一つです。
ウ XML データを記述するための文法に従っているのは整形式のXML 文書です。
エ エンティティ参照とは，そのまま表記すると制御文字と間違われる文字をエスケープ文字に変換することです。例えば，＜は &lt;，＞は &gt，＆は &amp; などに変換します。これは定義済なので，XML 文書ならいずれでも使用できます。
≪解答≫ア

□

XML 文書には，整形式 XML 文書と妥当な XML 文書がある

1-3

演習問題

1-3 演習問題
問1

1

排他的論理和の相補演算

CHECK ▶ □□□任意のオペランドに対するブール演算A の結果とブール演算B の結果が互いに否定の関係にあるとき，A はB の（又は，B はA の）相補演算であるという。排他的論理和の相補演算はどれか。
ア 等価演算（）

イ 否定論理和

（

）

（

）

エ 論理和

（

）

ウ 論理積

問2

逆ポーランド表記法

CHECK ▶ □□□式 A＋B×Cの逆ポーランド表記法による表現はどうなるか。

問3

オートマトンCHECK ▶ □□□

図は，偶数個の1を含むビット列を受理するオートマトンの状態遷移図であり，二重丸が受理状態を表す。a，bに入る数値は何か。
1

偶

0

問4

93

奇

a

サンプリングb

CHECK ▶ □□□PCM 伝送方式によって音声をサンプリング（標本化）して 8ビットのディジタルデー
タに変換し，
圧縮処理しないで転送したところ，転送速度は 64,000ビット／秒であった。
このときサンプリング間隔は何マイクロ秒か。

94

第1章

基礎理論

問5

関数の戻り値CHECK ▶ □□□

文字列を引数とする関数len，first，
butfirstを用いて，
関数compを再帰的に定義した。
comp（ " 11 " , " 101 " ）を呼び出したとき，返される値は何か。
〔関数の定義〕
len（S）： 文字列 Sの長さを返す。S が空文字列のときは 0を返す。

first
（S）

： 文字列 S の先頭の1 文字の ASCIIコードを返す。S が空文字列のときはエラーを返す。

butfirst（S）： 文字列 S の先頭の1文字を除いた残りの文字列を返す。S が空文字列のときはエラーを返す。
comp
（A，B）
begin
if len（A）＝0 and len（B）＝0 then return 0;
if len（A）＝0 and len（B）≠0 then return 1;
if len（A）≠0 and len（B）＝0 then return −1;
if first（A）＜first（B）then return 1;
if first（A）＞ first（B）then return −1;
return comp（butfirst（A）,butfirst
（B）
）
;
end

問6

ブロックに分けた線形探索

CHECK ▶ □□□相異なるn 個のデータが昇順に整列された表がある。この表を m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索することによって，目的のデータの存在するブロックを探し出す。次に，当該ブロック内を線形探索して目的のデータを探し出す。このときの平均比較回数を表す式はどれか。ここで，mは十分に大きく，nは mの倍数とし，目的のデータは必ず表の中に存在するものとする。
n
ア m＋
イ
m		
			

m
2

＋

n

ウ
2m		

n

エ
m		

n
2m

1-3

問7

ハッシュ関数の衝突

演習問題

CHECK ▶ □□□キーが小文字のアルファベット1 文字（a，b，. . . ，z のいずれか）であるデータを，
大きさが10のハッシュ表に格納する。
ハッシュ関数として，
アルファベットのASCIIコー
ドを10 進表記法で表したときの1の位の数を用いることにする。衝突が起こるキーの組合せはどれか。ASCIIコードでは，昇順に連続した2進数が，アルファベット順にコードとして割り当てられている。
ア aとi

問8

イ bとr

XML 文書の変換

ウ cとl

エ dとx

CHECK ▶ □□□XML 文書を，別の文書形式をもつ XML 文書や HTML 文書などに変換するための仕様は何か。

95

1

96

第1章

基礎理論

1-4 演習問題の解答
問1（平成 24 年春 応用情報技術者試験 午前 問1）《 解 答 》ア
排他的論理和は，二つの集合のうち，どちらかの条件に当てはまるものから両方の条件に当てはまるものを引いたものです。図示すると，下図左のようになります。

相補演算

互いに否定ということは白黒反転させればいいので，相補演算は上図右のようになります。
したがって，アの等価演算が正解です。
問2（平成 23 年秋 応用情報技術者試験 午前 問2 改）《 解 答 》ABC×＋＋

式 A＋B×Cは中置表記法で表した式なので，木構造に置き換えると右図のようになります。
この木を逆ポーランド表記法（後置表記法）で，左部分木，右
部分木，根の順に読んでいくと，ABC×＋となります。

問3

×
B

A

B

C

（平成 25 年春 応用情報技術者試験 午前 問3 改）《 解 答 》a：1，b：0
偶数個の1を含むビット列を受理するオートマトンの状態遷移図に， 偶 と 奇 という二つの状態があります。 偶 が受理状態なので，これが偶数個の1を含む状態を示していると推測でき， 奇 が奇数個の1を含む状態を示すことが分かります。ここで，ビット列なので 0 か 1かのどちらかが来ますが，0 が来たら1の数はそのまま奇数，1が来たら偶数になります。したがって，奇数から偶数への状態遷移である空欄 aは1が来たとき，奇数のままでいる状態遷移である空欄 bは 0 が来たときになります。

1-4

演習問題の解答（平成 22 年秋 応用情報技術者試験 午前 問3 改）問4《 解 答 》125
8ビットのディジタルデータに変換したものを64,000ビット／秒の速度で転送したということは，64,000［ビット／秒］÷8［ビット］＝8,000［回／秒］のサンプリングを行ったことになります。そのため，サンプリング間隔をマイクロ秒（＝10−6 秒）の単位で考えると，以下のようになります。
1,000,000［マイクロ秒／秒］÷8,000［回／秒］＝125［マイクロ秒］（平成 21年春 応用情報技術者試験 午前 問7 改）問5《 解 答 》−1
実際に，再帰的に値をトレースして値を求めます。
① 1度目のcomp（ " 11 " , " 101 " ）呼出し
A＝ " 11 " , B＝ " 101 " なので，次のようになります。
len（A）＝2 , len（B）＝3 , first（A）＝ " 1 " , first（B）＝ " 1 "五つの if 文の条件には当てはまらないので，
butfirst（A）＝ " 1 " , butfirst（B）＝ " 01 " で，
関数 compを再帰呼出しします。
② 2 度目のcomp（ " 1 " , " 01 " ）呼出し
A＝ " 1 " , B= " 01 " なので，次のようになります。
len（A）＝1 , len（B）＝2 , first（A）＝ " 1 " , first（B）＝ " 0 "五つ目の if 文の条件，first（A）＞ first（B）に当てはまるので，return −1 で−1を返し，①の関数 compに戻ります。
return comp（butfirst（A）,butfirst（B））なので，戻ってきた値をそのまま返します。したがって，最終的な戻り値は−1となります。

問6（平成 24 年春 応用情報技術者試験 午前 問9）《 解 答 》イ
相異なるn 個のデータが昇順に整列された表を，m 個のデータごとのブロックに分割し，各ブロックの最後尾のデータだけを線形探索するというのは，次のようなイメージになります。

97

1

98

第1章

基礎理論

n個
m

m

m

m

m

m

m

m

最後尾を順に探索m
該当ブロックが見つかったら，そのブロックを線 形 探 索

n 個のブロックをm 個のデータごとに分けると，ブロック数は n ／ m 個になります。線形探索なので，平均探索回数はその半分で n ／ 2m回です。さらに，見つかったブロック内でm 個のデータ中を探索します。このときも線形探索なので，平均探索回数は半分の m ／ 2
回になります。これらを合計すると，m ／ 2＋n ／ 2m回となるので，イが正解です。
問7（平成 23 年特別 応用情報技術者試験 午前 問8）《 解 答 》エASCIIコードは，アルファベット順に連続して並んでいます。10 進数で表すと，最初の a（小文字）は 97，次の b が 98……と順に連続しています。そのため，アルファベット全文
字を，10 進表記法で表したときの1の位でハッシュ値をとると，右の表のようになります。
選択肢の組合せでは，エの d（100）とx（120）がともに 1の位が 0なので，衝突が起こります。

問8

1の位の数

アルファベット

0

d

n

x

1

e

o

y

2

f

p

z

3

g

q

4

h

r

5

i

s

6

j

t

k

u

7

a

8

b

l

v

9

c

m

w

（平成 21年秋 応用情報技術者試験 午前 問8 改）《 解 答 》XSLTXML 文書を，別の文書形式をもつXML 文書やHTML 文書などに変換するための仕様を
XSLT（XML Styleseet Language Transformation），XSL 変換といいます。XML 文書全体または一部分について変換を行い，別の XML 文書，または HTMLなどの別の表現形式，
TeXなどの印刷用形式の文書を生成することができます。