基礎理論

基礎理論

1. 離散数学

(1) 基数

基数（radix）とは、位取り記数法で数値を書き記す際に各桁の重み付けの基本となる数で、位が上がる毎に何倍になるかを表す。我々が普段使っているのは隣の桁が 10 倍あるいは 10 分の 1 となる 10 進数（10 進法）であり、基数は 10 である。

2 進数，8 進数，10 進数，16 進数の対応を次表に示す。

10 進数整数を $r$ 進数へ変換

10 進数の整数値 $x$ を $r$ 進数に変換する手順は次のとおり。

1. $x$ を $r$ で割ったときの商 $p$ と余り $q$ を求める。
2. $p$ の値が 0 ならば終了。それ以外ならば $p$ を $x$ と読み替えて 1. へ戻る。

計算の終了後，これまでに求まった $q$ の値のうち，最後に求まった $q$ の値を最上位桁として順に下位方向に並べたときの数列が変換された $r$ 進数の値である。

10 進数小数を $r$ 進数へ変換

10 進数の小数値 $x$ を $r$ 進数へ変換する手順は次のとおり。

1. $x$ を $r$ で乗算した結果を，整数部の数値 $i$ と $i$ を除いた小数値 $d$ に分ける。
2. $d$ の値が 0 ならば終了。それ以外ならば $d$ を $x$ に読み替えて，1. に戻る。

計算の終了後，これまでに求まった $i$ の値のうち，最初に求まった $i$ の値を小数第 1 位として順に下位方向に並べたときの数列が，変換された $r$ 進数の値になる。

(2) 数値の表現

コンピュータの中では，整数だけでなく負数や小数点数なども，すべて 0 と 1 の 2 進数で表される。

浮動小数点数

浮動小数点（floating point number）とは，コンピュータにおける数値の表現形式の一つで、数値を桁の並びを表す仮数部と小数点の位置を表す指数部に分割して表現する方式。小数点以下の値を含む数値の表現法として最も広く利用されている。

浮動小数点数は，小数点の位置を固定せずに小数点数を表現する方法である。数値を指数形式（± f × r^e）で表した時の，「符号（正を 0，負を 1）」，「仮数 f」，「指数 e」を下図の順に並べて表現する。これを浮動小数点形式という。ここで，r は基数を意味し，通常，基数は 2 である。また，仮数 f は「0.1xxx」となるように，指数 e と桁合わせをする。

固定小数点数

固定小数点数（fixed-point number）とは、コンピュータが実数を扱うときの表現形式の一つで、小数点が特定の位置に固定されているもの。

単精度浮動小数点数（float 型）

単精度浮動小数点数型（single precision floating point number type）とは、プログラミング言語などで用いられる数値データ型の一つで、32 ビット長の浮動小数点数を格納することができるもの。多くの言語では実数を表すことができる最も基本的な型として用意されている。

倍精度浮動小数点数（double 型）

倍精度浮動小数点数型（double precision floating point number type）とは、プログラミング言語などで用いられる数値データ型の一つで、64ビット長の浮動小数点数を格納することができるもの。多くの言語では最も幅広い範囲の実数を表すことができる型として用意されている。この形式で表すことができる値は 10 進数で概ね -1.79769 × 10³⁰⁸ ～ 1.79769 × 10³⁰⁸ の範囲で，精度は 15 桁である。

BCD

BCD（Binary-Coded Decimal，2 進化 10 進数）とは、10 進数の値を 2 進数で表現する方式の一つで、10 進数の一つの数字を 4 桁の 2 進数に対応させたもの。IBM 社がメインフレームで用いていた方式が広まったもので、これをアルファベットや記号を含む文字コードに拡張したものは EBCDIC として知られる。

パック 10 進数

2 進化 10 進数（BCD）を拡張し、末尾に数値の符号を表すコードを追加したものをパック 10 進数（packed BCD）という。1 バイトで 1 桁を表すゾーン 10 進数（アンパック 10 進数）に比べ少ないデータで数値を表すことができる。

(3) 算術演算と精度

論理シフト

全ビットを一律に移動させるものを「論理シフト」（logical shift）という。

算術シフト

最上位ビットは変化させず残りのビット列でシフトを行うものを「算術シフト」（arithmetic shift）という。

桁落ち

桁落ち（loss of significance）とは、丸め誤差を含む非常に近い大きさの小数同士で減算を行ったときに、有効数字が減る現象のこと。コンピュータでは浮動小数点数の数値計算において生じる。例えば，有効桁数 3 の浮動小数点数同士の演算「0.789 × 10⁵ - 0.788 × 10⁵」の結果は，0.1 × 10⁵ となり，有効桁数は 1 に減少する。

情報落ち

情報落ち（loss of trailing digits）とは、コンピュータで絶対値の大きさが極端に異なる数字を足したり引いたりしたときに、小さい値の情報が無視されてしまう現象。また、そのような現象によって起きる計算の誤差。例えば，有効桁数 3 桁の演算「0.111 × 10⁵ + 0.111 × 10^-1」の場合，0.111000111 × 10⁵ → 0.111 × 10⁵ となり，絶対値の小さい値が演算結果に反映されない。

オーバフロー（あふれ）

オーバーフロー（overflow）とは、あふれ（る）、あふれ出たもの、という意味の英単語。ITの分野では、数値の計算結果がその格納領域に収まる範囲を超えること（算術オーバーフロー/桁あふれ）や、与えられたデータが多すぎて指定の領域に収まりきらないこと（バッファオーバーフローなど）を指す。

アンダーフロー

アンダーフロー（underflow）とは、コンピュータで実数の計算をした結果、絶対値が小さすぎて正確に表現・計算できなくなってしまうこと。

単精度

数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を32ビットのデータで表現する方式のこと。多くのプログラミング言語などでは単に浮動小数点といえば単精度を意味し、“float” などの名称で表されるデータ型が用意されている。

倍精度

数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を32ビットのデータで表現する方式のこと。多くのプログラミング言語などが高精度な数値計算のために組み込みデータ型として用意しており、 “double” などの名称で表される。

(4) 集合と命題

和集合

積集合

補集合

部分集合

真

偽

命題論理

(5) 論理演算

否定（NOT）

否定の論理式は次式，真理値表は次表で表される。

論理和（OR）

論理和の論理式は次式，真理値表は次表で表される。

論理積（AND）

論理積の論理式は次式，真理値表は次表で表される。

ド・モルガンの法則

ド・モルガンの法則は，否定論理はおよび否定論理積をそれぞれ論理和と論理積に変換するものである。

否定

論理否定（NOT）とは、論理演算の一つで、与えられた命題が真のときに偽となり、偽のとき真となるもの。論理回路や2進数の数値による論理否定は、入力が 1 のとき 0 となり、0 のとき 1 となる。

論理和

論理和（OR）とは、論理演算の一つで、二つの命題のいずれか一方あるいは両方が真のときに真となり、いずれも偽のときに偽となるもの。論理回路や 2 進数の数値による論理和は、二つの入力のいずか一方あるいは両方が 1 のとき出力が 1 となり、いずれも 0 の場合に 0 となる。

論理積

論理積（AND）とは、論理演算の一つで、二つの命題のいずれも真のときに真となり、それ以外のときは偽となるもの。論理回路や 2 進数の数値による論理積は、二つの入力の両方が 1 のときのみ出力が 1 となり、いずれか一方あるいは両方が 0 の場合は 0 となる。

排他的論理和

排他的論理和（XOR）とは、論理演算の一つで、二つの命題のいずれか一方のみが真のときに真となり、両方真や両方偽のときは偽となるもの。論理回路や 2 進数の数値における XOR は、二つの入力のうち片方のみが 1 であるときのみ出力が 1 となり、両方 1 や両方 0 の場合は 0 となる。

否定論理和

否定論理和（NOR）とは、論理演算の一つで、二つの命題のいずれも偽のときに真となり、それ以外のときは偽となるもの。論理回路や 2 進数の数値による NOR は、二つの入力が 0 のときのみ出力が 1 となり、いずれか一方あるいは両方が 1 のときは 0 となる。論理和（OR）の結果を否定（NOT）したものと同値。

否定論理積

否定論理積（NAND）とは、論理演算の一つで、二つの命題のいずれも真のときに偽となり、それ以外のときは真となるもの。論理回路や 2 進数の数値による NAND は、二つの入力が 1 のときのみ出力が 0 となり、

論理関数

分配論

2. 応用数学

(1) 確率と統計

① 確率

確率とは，ある事象（結果）が発生する可能性を表す数値である。事象 A の確率 $P(A)$ は，事象 A の起こりうる場合の数（$r$）と全ての事象の数（$n$）から，次のように求める。

正規分布はガウス分布とも呼ばれ，統計学では最もよく用いられる連続型の確率分布である。自然界でも多く見られ，理論的にもとても都合の良い性質を持っている。実用面でも多くの場面で誤差関数（仮定した理論的な値と観測された値との差）として正規分布が仮定されている。

確率変数（実数）を $x$，平均を表すパラメータ（実数）を $\mu$，標準偏差を表すパラメータ（正の実数）を $\sigma$ とすれば，正規分布の確率密度関数は次式で表される。

平均が 50，標準偏差が 5，10，20 である正規分布の確率密度関数を表すグラフを下図に示す。形状は平均値 50 を中心に左右対称で，標準偏差が小さければ，データの分布は平均値付近にまとまる。

階乗

加法定理

乗法定理

同時確率

条件付き確率

ベイズの定理

正規分布

平均値を中心とする左右対称で釣鐘状の連続確率分布のこと

一様分布

すべての事象が起こる可能性が等しい現象を表す確率分布のこと

ポアソン分布

離散的に発生し，発生確率は一定である離散確率分布のこと

指数分布

② 統計

中央値（メジアン）

データを中央に並べたときに中央に位置するデータ。データの数が偶数の場合，中央付近の 2 つのデータの平均値から求める。

最頻値（モード）

データの中で出現する頻度が最も高いデータ。

平均値

標準偏差

分散

相関係数

推定

回帰分析（単回帰分析，重回帰分析，ロジスティック回帰分析）

相関分析

主成分分析

因子分析

(2) 数値計算

線形代数

スカラ

ベクトル

固有値

固有ベクトル

行列

逆行列

単位行列

転置行列

等差数列

等比数列

フィボナッチ数列

対数

三角関数

(3) 数値解析

ニュートン法

絶対誤差

相対誤差

丸め誤差

打切り誤差

(4) 数式処理

因数分解

微分

積分

(5) グラフ理論

有向グラフ

(6) 待ち行列理論

キューとは、最も基本的なデータ構造の一つで、要素を入ってきた順に一列に並べ、先に入れた要素から順に取り出すという規則で出し入れを行うもの。順番を待つ人の行列と同じ仕組みであるため「待ち行列」とも訳される。

リトルの法則

リトルの法則（Little's law）とは，待ち行列理論において「安定な系において長時間平均化した顧客数 $L$（与えられた負荷）は，長時間平均化した到着率 $\lambda$ と長時間平均化した顧客が形に費やす時間 $W$ に等しい」というものであり，次式が成り立つ。

サービス時間

待ち時間

到着間隔

平均到着率

平均サービス率

(7) 最適化問題

動的計画法

3. 情報に関する理論

(1) 情報理論

(2) 符号理論

コンピュータ同士の通信においては，次の点を考慮する必要がある。

• 通信路上で起きた誤りの検出・訂正を受信側で行えること
• 送信する元の情報を短くし，通信効率を高めること

上記を実現する方法はさまざまあるが，その 1 つとして符号化がある。

通信路符号化

ハフマン符号

ハフマン符号（Huffman compression）とは、1952年にデビット・ハフマン（David Albert Huffman）氏が考案した、可逆圧縮アルゴリズムの代表的な方式の一つ。現代でもファイル圧縮や画像ファイル形式など様々な場面で応用されている。

データ圧縮

データ圧縮（data compression）とは、データを一定の計算手順で加工し、実質的な内容を損なわずにより短い符号列で表すこと。原則として得られた圧縮符号は逆の計算手順により元のデータに復元することができ、データの一部を損なって容量を減らす削減や間引きとは異なる。

(3) 文字の表現

ASCII コード（アスキーコード）

ASCII（American Standard Code for Information Interchange）とは、アルファベットや数字、記号などを収録した文字コードの一つ。最も基本的な文字コードとして世界的に普及しており、他の多くの文字コードが ASCII の拡張になるよう実装されている。文字を 7 ビットの値（0～127）で表し、128 文字が収録されている。

EUC（Extended UNIX Code）

EUC-JPとは、主に UNIX 系 OS で標準的に用いられる、日本語文字に対応した文字コード規格（正確には符号化方式）の一つ。

JIS コード（ISO-2022-JP）

JIS コードとは、国際的な文字コード規格の一つである ISO/IEC 2022 の枠組みに沿って定義された日本語の文字コードの一つ。

シフト JIS コード

Shift JIS とは、JIS 規格として標準化された日本語を含む様々な文字を収録した文字コードの一つ。正確には「Shift_JIS」と間にアンダーバーを挟んで表記する。MS-DOS や Windows が標準の日本語文字コードとして採用したことから広く普及した。

Unicode

Unicode とは、文字コードの国際的な業界標準の一つで、世界中の様々な言語の文字を収録して通し番号を割り当て、同じコード体系のもとで使用できるようにしたもの。

UCS

ISO/IEC 10646 標準で規定される文字集合を UCS（Universal Coded Character Set）というが、Unicode の基本多言語面にほぼ相当する冒頭 16 ビット分の領域を UCS-2 という。

(4) 述語論理

関係データベース

(5) 形式言語

コンピュータで使用する言語は，明確な定義のもとで作成した形式（フォーマット）に従い，文字やプログラムを読み，理解する。これを形式言語と呼ぶ。形式言語の代表的な表記方法として，正規表記，BNF がある。

正規表現

正規表現とは，文字列などの記号列を表現する形式言語である。正規表現では，有限個の記号に対して，規則を表すメタ文字を組み合わせて表現する。

BNF

BNF（Backus-Naur Form）とは、コンピュータが扱う人工言語の文法を定義する際に用いられるメタ言語（言語を記述するための言語）の一つ。コンピュータ言語の多くはその仕様は BNF で記述している。構文規則には，順次，反復，選択があり，次表の記号を用いる。

逆ポーランド表記法

逆ポーランド記法（Reverse Polish Notation）とは、数式などを記述する際の表記法の一つで、演算子を被演算子（演算対象）の列の後に記す方式。後置記法とも言う。ポーランド記法を逆順にしたものであるためこのように呼ばれる。

(6) オートマトン

オートマトン（automaton）とは、計算機の構造や動作を抽象化したモデルの一つで、内部に固有の状態と、状態を変化させる規則の集合を持ち、外部からの入力に応じて状態を変化させるもの。複数形は “automata” （オートマタ）。

(7) 計算量

アルゴリズムの効率性を評価する基準として，処理を行うデータ件数を $n$ としたときの実行時間の目安を表す計算量がある。計算量は，「$O$」（英字の大文字で，オーダと読む）の記号を用いて，「$O(n)$」と表す。計算量が $O(n)$ の場合は，処理件数 $n$ に計算量が比例し，$O(1)$ は処理件数に関わらず計算量は変わらないことを示す。

時間計算量（time complexity）

時間計算量とは、コンピュータが特定の手順に従って与えられた問題を解く際に必要とする手順の回数。これが少ないほど、より短い時間で問題を解くことができる。

(8) AI（Artificial Intelligence : 人工知能）

人工知能とは、人間にしかできなかったような高度に知的な作業や判断をコンピュータを中心とする人工的なシステムにより行えるようにしたものである。

機械学習は，機械に与えるデータを AI 自身が解析してルールや法則を反復的に学習し，人間が行う知的な振る舞いを人工的に再現する技法である。機械学習における学習方法は，次表に示す 3 つがある。

エキスパートシステム（expert system）

エキスパートシステムとは、ある分野の専門家の持つ知識をデータ化し、専門家のように推論や判断ができるようにするコンピュータシステム。1970 ～ 80 年代の人工知能（AI）研究から生まれた応用分野の一つである。

知識ベース

推論エンジン

機械学習

機械学習とは，機械に与えるデータを AI 自身が解析してルールや法則を反復的に学習し，人間が行う知的な振る舞いを人工的に再現する技法である。

汎化

厳密な解でなくてもなるべく正解に近い解を得るようにする方法であり，特定分野に特化せずに，広範囲で汎用的な問題解決ができるようにするものである。

ニューラルネットワーク

ニューロンと呼ばれる脳細胞の特性をコンピュータ上で表現したモデル

ディープラーニング（深層学習）

ディープラーニングとは，機械学習においてニューラルネットワークによるパターン認識を利用した機械学習の 1 つである。その構造は，ニューラルネットワークの中間層（隠れ層）が幾重にも重なる構造を持たせて，より効率的な学習が行われるようになっている。

(9) コンパイラ理論

中間言語

中間コードとは、人間が読み書きしやすいプログラミング言語で書かれたソースコードと、コンピュータが直に実行可能なネイティブコードの中間の特徴を持つ形式のプログラムコード。命令を表すコードを 1 バイトで表現するものは特に「バイトコード」（byte code）と呼ばれる。

目的プログラム（object code）

オブジェクトコードとは、コンピュータプログラムの形式の一つで、コンピュータによる解釈・実行に適した言語やコード体系で記述されたもの。通常は人間が直接記述することはなく、ソースコードから変換して生成する。

形式言語

コンピュータで使用できるよう，明確な定義の下で作成した形式（フォーマット）に従い，文字やプログラムを記述したもの。

オートマトン（automaton，状態機械）

オートマトンとは、計算機の構造や動作を抽象化したモデルの一つで、内部に固有の状態と、状態を変化させる規則の集合を持ち、外部からの入力に応じて状態を変化させるもの。複数形は “automata” （オートマタ）。

(10) プログラム言語論

手続型言語（procedural language）

手続き型言語とは、プログラミング言語の分類の一つで、コンピュータが実行すべき命令や手続きを順に記述していくことでプログラムを構成する言語。

関数型言語（functional language）

関数型言語とは、プログラミング言語の分類の一つで、プログラム中の処理や制御を関数の定義と適用の組み合わせとして記述していくもの。そのようなスタイルでコードを記述することを「関数型プログラミング」（functional programming）という。

論理型言語

オブジェクト指向言語（object-oriented programming language）

オブジェクト指向言語とは、プログラミング言語のうち、互いに関連するデータの集合とそれらに対する手続き群をひとまとめにした「オブジェクト」（object）をプログラムの基本的な構成単位として扱うことができるもの。

4. 通信に関する理論

(1) 伝送理論

① 伝送路

単方向

半二重

全二重

② 変復調方式

AM（Amplitude Modulation : 振幅変調）

FM（Frequency Modulation : 周波数変調）

PM（Phase Modulation : 位相変調）

PCM（Pulse Code Modulation : パルス符号変調）

② 多重化方式

FDM（Frequency Division Multiplexing : 周波数分割多重）

TDM（Time Division Multiplexing : 時分割多重）

③ 誤り検出・訂正

CRC（Cyclic Redundancy Code）

CRC とは、誤り検出方式の一つで、データを値とみなしてある定数で割った余り（余剰）を用いて誤りの検知を行なうもの。その検査用の値を CRC 値、CRC 符号、巡回冗長符号などと呼ぶが、値自体を CRC（Cyclic Redundancy Code）と呼ぶこともある。

ハミング符号（Hamming Code）

ハミング符号とは、データの伝送時に付加し、誤りを検知・訂正できる誤り訂正符号の一つ。ビット列中の 1 の数の奇偶を利用するパリティチェックを拡張したもの。

パリティチェック（parity check，寄偶検査）

パリティチェックとは、データの誤り検出方式の一つで、ビット列中に含まれる「1」の数が偶数か奇数かを表す符号を算出してデータに付加する手法。最も単純な誤り訂正符号で、1 ビットの誤り検出しかできないが算出や検証が容易で高速なため広く普及している。

ECC（Error-Correcting Code）

誤り訂正符号とは、データを記録・伝送する際に発生する誤りを受け手の側で検出し、訂正することができるように付加される符号。元のデータから一定の手順に基いて算出し、データと共に記録・伝送する。

チェックサム（checksum）

チェックサムとは、誤り検出符号の一つで、データ列を整数値の列とみなして和を求め、これをある定数で割った余り（余剰）を検査用データとするもの。最も単純な誤り検出方式の一種で、誤りの検出精度は低いが原理が簡単で容易に実装でき、計算コストも低いため、簡易な誤り検出方式として広く普及している。

④ 信号同期方式

通信の分野では、機器やソフトウェアなどの間で信号やデータの送受信のタイミングを合わせ、正しく伝送されるよう制御することを同期という。

コンピュータ内部の通信では、一定周期のクロック信号に合わせて各回路や装置が信号を送り出すクロック同期が行われることが多い。クロック同期はデータの伝送だけでなく処理や制御のタイミングを合わせるのにも用いられる。

ビット同期

キャラクタ同期

フラグ同期

調歩同期

スタートビット

ストップビット

SYN 同期

フレーム同期

5. 計測・制御に関する理論

(1) 信号処理

フィルタリング（filtering）

フィルタリングとは、選別、濾過などの意味を持つ英単語で、IT の分野では与えられた条件に基づいて信号やデータなどを選別・加工・排除する仕組みを指す。そのような処理を行う装置やソフトウェアなどのことは「フィルタ」（filter）という。

D/A 変換

A/D 変換

(2) 制御に関する理論

① 制御の仕組み

リアルタイム OS（real-time operating system : RTOS）

リアルタイム OS とは、OS（オペレーティングシステム）の種類の一つで、時間的な制約がある処理を実行するための機能や特性を備えたもの。産業ロボットや輸送機械などの組み込みシステムの制御用としてよく用いられる。

オープンループ

応答特性

制御安定性

② センサ・アクチュエータの種類と動作特性

光学センサ

赤外線センサ

磁気センサ

加速度センサ

ジャイロセンサ

超音波センサ

温度センサ

湿度センサ

圧力センサ

ひずみゲージ

サーミスタ

ホール素子

モータ

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

1． データ構造

(1) データ構造

データ構造は，プログラムで使用するデータを扱うための枠組みのことである。

(2) データ構造の種類

① 配列

配列（array）とは、複数のデータを連続的に並べたデータ構造。各データをその配列の要素といい、自然数などの添字（インデックス）で識別される。

多次元配列（multidimensional array）

プログラミング言語などが扱うデータ構造の一つで、配列の各要素が配列に、その要素がさらに配列になっているような入れ子構造の配列データのこと。単純な配列（1 次元配列）では配列の各要素にそれぞれ値が格納されているが、多次元配列では配列の各要素が配列に、その要素がさらに配列に…という具合に配列が何段階にも入れ子構造になっている。入れ子が何段階になっているかを次元の数で表し、配列の要素が配列になっているものを 2 次元配列、その要素がさらに配列になっているものを 3 次元配列、というように呼ぶ。

静的配列

動的配列

② リスト

リストはデータの構造を連結したデータ構造で，リストの最小単位となる要素はデータ部とポイント部で構成される。データ部にはデータ自体を格納し，ポイント部には次の要素の場所に格納する。このポインタをたどることで，個々の要素にアクセスすることができる。

リストの種類には，ポインタの向きによって，単方向リスト，双方向リスト，環状リストがある。

線形リスト

先頭から末尾へ直線上に要素が連結されているもの

③ スタックとキュー

スタック（stack）とは，後に格納したデータから順に取り出す。後入先出型（LIFO : Last In First Out）のデータ構造である。スタックにデータを格納することを push（プッシュ），スタックからデータを取り出すことを pop（ポップ）と呼ぶ。

キュー（queue）とは，先に格納したデータから順に取り出す，先入先出型（FIFO : First In First Out）のデータ構造である。キューへデータを格納することを enqueue（エンキュー），キューからデータを取り出すことを dequeue（デキュー）と呼ぶ。

FIFO（First-In First-Out）

FIFO とは、複数の対象を取り扱う順序を表した用語で、最初に入れたものを最初に取り出す（先に入れたものを先に出す）方式のこと。

LIFO（Last-In First-Out）

LIFO とは、複数の対象を取り扱う順序を表した用語で、最初に入れたものを最後に取り出す（先に入れたものを後に出す）方式のこと。会計の分野では「後入先出法」と呼ぶ。

プッシュ（push）

プログラミングの分野で、スタックなどのデータ構造で新たにデータを一つ追加する操作や命令をプッシュという。

ポップ（pop）

プログラミングの分野で、スタックなどのデータ構造に保管されたデータの中から最も最近追加されたものを取り出す操作や命令をポップという。

④ 木構造

木構造（tree structure）とは、データ構造の一つで、一つの要素（ノード）が複数の子要素を持ち、一つの子要素が複数の孫要素を持ち、という形で階層が深くなるほど枝分かれしていく構造のこと。木が幹から枝、枝から葉に分岐していく様子に似ているためこのように呼ばれる。

すべての節において，「左側の子の値 < 節の値」「節の値 < 右側の子の値」という大小関係を持つ木を 2 分岐探索木と呼び，探索を効率的に行うことができる。下図は，1 ～ 9 の数字が各節に格納された 2 分岐探索木である。

2 分岐探索木からデータを探索する場合，探索データと節の値を比較し，その結果によって，次の処理を行う。

• 対象データの値 > 節の値 → 右部分木をたどり，探索を続行。
• 対象データの値 < 節の値 → 左部分木をたどり，探索を続行。
• 対象データの値 = 節の値 → 探索を終了。

葉に達した時点で一致しない場合は，探索対象データが存在しないことになるため，探索を終了する。

根

階層の最上位の節を根（ルート）という。

葉

子を持たない節を葉（リーフ）という。

枝

節同士を結ぶものを枝（ブランチ）という。

2 分木（binary tree）

二分木とは、データ構造の一つである木構造（ツリー構造）のうち、どの親ノードも二つ以下の子ノードを持つもの。子が N 個以下に制限された N 分木（N-ary tree）のうち最も単純な構造の木である。

完全 2 分木（perfect binary tree）

二分木のうち、（子のない葉ノードを除く）子を持つノードの子の数がすべて二個ずつであるようなものを「全二分木」（full binary tree）、全二分木のうちすべての葉ノードの深さが揃っているものを「完全二分木」という。

バランス木（balanced tree）

木構造のうち、根ノードから子を持たない末端の要素（葉ノード）までの高さ（深さ）がなるべく等しくなるように構築されたものを「平衡木」（へいこうぎ/balanced tree：バランス木）という。

順序木

多分木（multi-branch tree/multi-way tree）

木構造のうち、親要素（親ノード）が3個以上の子要素（子ノード）を持つことができるもの多分木（たぶんぎ）という。

探索木

2 分探索木（binary search tree）

二分探索木はデータの探索に適したデータ構造の一つである。値を探索するには、根ノードから出発して、各ノードの値が探索している値より大きければ左の子に、小さければ右の子に移っていき、末端のノード（葉ノード）まで辿れば探索が終了する。根から葉までの深さ（高さ）の数だけ値を調べればよく、値を単純に端から順番に調べるより効率的に探索できる。

深さ優先探索

幅優先探索

先行順

後行順

中間順

2. アルゴリズム

アルゴリズム（algorithm）とは、ある特定の問題を解く手順を、単純な計算や操作の組み合わせとして明確に定義したもの。数学の解法や計算手順なども含まれるが、IT の分野ではコンピュータにプログラムの形で与えて実行させることができるよう定式化された、処理手順の集合のことを指すことが多い。

(1) 流れ図

アルゴリズムを表記するための方法として，手続きの種類を表す記号を組み合わせて処理の流れを視覚化する流れ図（フローチャート）がある。流れ図の表記方法は JIS 規格（JIS X 0121-1986）で定義されている。

端子

処理の開始と終了を示す

処理

変数の代入や計算などの処理を記述する

定義済み処理

サブルーチンを示す

判断

処理を分岐するための条件を記述する

ループ端

繰返しの処理の開始と終了，および，繰返しの終了条件を記述する

データ

データの入出力を記述する

線

流れ図記号を結び処理の流れを示す

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

① 整列・併合・探索のアルゴリズム

整列（sort : ソート）は，ある基準に従ってデータを並び替える操作のことである。探索は，データの集合に目的のデータが存在するかを調べる処理である。

選択ソート（selection sort，基本選択法）

選択ソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、未整列の要素の中から最大あるいは最小のものを選択し、整列済みの列の末尾に追加していくもの。

バブルソート（bubble sort，単純交換法 / 隣接交換法 / 基本交換法）

バブルソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、端から順番に隣接する要素同士を比較・交換していくもの。

マージソート（merge sorting，併合ソート / 併合整列法）

マージソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの一つで、データ列を細かく分割し、整列しながら次第に併合（merge）していくもの。

挿入ソート（insertion sort，基本挿入法 / インサーションソート / 単純挿入法）

挿入ソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、未整列の要素を一つずつ、整列済みの列の適切な位置に挿入していくもの。

シェルソート（Shell sort）

シェルソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの最も基本的な手法の一つで、挿入ソートを改良したもの。1959 年にアメリカのコンピュータ科学者ドナルド・シェル（Donald Shell）が考案した。

クイックソート（quick sort）

クイックソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムで、最も高速な手法の一つ。1960 年に英コンピュータ科学者アントニー・ホーア（Charles Antony Richard Hoare）氏が考案した。

ヒープソート（heap sort）

ヒープソートとは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート（整列）アルゴリズムの一つで、ヒープ構造と呼ばれる二分木の一種を構築して並べ替えを行うもの。

線形探索法（linear search）

線形探索とは、データ探索アルゴリズムの一つで、配列などに格納されたデータ列の先頭から末尾まで順番に、探しているデータと一致するか比較していく手法。

2 分探索法（binary search，バイナリサーチ）

二分探索とは、データ検索アルゴリズムの一つで、ソート（整列）済みのデータ群の探索範囲を半分に絞り込むを操作を繰り返すことで高速に探索を行う手法。

ハッシュ表探索法（hashing method）

ハッシュ法とは、データ探索アルゴリズムの一つで、対象となるデータから一定の手順で算出したハッシュ値を用いてデータ本体の代わりに比較に用いる方式。対象とするデータが長い場合に処理を高速化することができる。

② 再帰のアルゴリズム

プログラミングの分野で、関数やメソッドなどの処理内容の記述の中に、自身の呼び出しを行なうコードが含まれることを「再帰呼び出し」（recursive call：リカーシブコール）、そのような関数を「再帰関数」（recursive function）という。また、そのような構造を用いて記述されるアルゴリズムを「再帰的アルゴリズム」（recursive algorithm）という。

③ グラフのアルゴリズム

深さ優先探索

幅優先探索

最短経路探索

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

文字列照会

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

(2) アルゴリズム設計

再帰

再帰（リカーシブ）は，手続きや関数の中で，自分自身を呼び出すことをいう。

分割統治法

3. プログラミング

(1) プログラミング

プログラミング（programming）とは、コンピュータに意図した動作を行わせるために、まとまった処理手順を作成し、与えること。作成された手順のことをコンピュータプログラム（computer program）あるいは単にプログラムという。プログラミングを行う人や職種のことをプログラマ（programmer）という。

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

字下げ（インデンテーション）

インデントとは、文章の行頭に空白を挿入して先頭の文字を右に押しやること。また、そのために左端に挿入された空白や、テキストエディタやワープロソフトの持つ字下げ機能のこと。

ネストの深さ

命名規則

使用禁止命令

プログラムの機能適合性・性能効率性・使用性・保守性の向上

② プログラム構造

モジュール分割

モジュール分割とは、コンピュータプログラムを設計する際に、全体を何らかの基準に則って複数の部品（モジュール）に分割すること。モジュールは特定の機能や構造を表す適切な大きさのプログラムのまとまりであり、これを組み合わせてプログラム全体を構成していく。

独立性

ルーチン（routine）

ルーチンとは、型通りの（動作）、日課、定形業務などの意味を持つ英単語で、コンピュータプログラムのうち特定の機能や処理を実装したひとまとまりのコードの集合のことをこのように呼ぶ。

メインルーチン（main routine）

プログラムの本体となる最初に起動される部分のこと。

サブルーチン（sub routine）

メインルーチンや他のルーチンから呼び出されて利用されるルーチン。

③ データ型

データ型（data type）とは、プログラミング言語などが扱うデータをいくつかの種類に分類し、それぞれについて名称や特性、範囲、扱い方、表記法、メモリ上での記録方式などの規約を定めたものである。

整数型（integer type，int 型）

整数型とは、プログラミング言語などで用いられるデータ型の一つで、整数の値を格納できるもの。多くの言語に実装されている最も基本的なデータ型で、ビット長や符号の有無などにより複数の種類に分かれている場合もある。

実数型

論理型（boolean type，ブーリアン型）

ブーリアン型とは、プログラミング言語などに用意されているデータ型の一つで、「真」（true）と「偽」（false）の二種類の値だけを取りうるもの。

文字型（character type）

文字型とは、C 言語などに用意されている基本的なデータ型の一つで、一文字分の文字コードを格納するためのもの。

抽象データ型

構造型（structure）

構造体とは、C 言語などのプログラミング言語が持つデータ型の一つで、複数の異なるデータ型の変数を一つにまとめたもの。言語によっては似た機能が「ユーザー定義型」「レコード型」などの名称で提供されている場合もある。

④ Web プログラミング

サーバーサイドプログラミング

リッチクライアント（rich client）

リッチクライアントとは、Web アプリケーションのクライアントとして、Web ブラウザで単純な Web ページを表示する方式を超える表現力や操作性を備えたシステムを用いること。専用のアプリケーションソフトを利用する場合と Web ブラウザで高度な機能や拡張技術を用いる場合がある。

Ajax（Asynchronous JavaScript + XML）

Ajax とは、ある Web ページを表示した状態のまま、別のページや再読込などを伴わずに Web サーバ側と通信を行い、動的に表示内容を変更する手法。ページ上でプログラムを実行できるプログラミング言語 JavaScript の拡張機能を用いる。JavaScript の非同期通信の機能を使うことによって，動的なユーザインタフェースを画面全体の遷移を伴わずに実現する技術。

Apache

Apache とは、世界的に最も普及している Web サーバ（HTTP サーバ）ソフトウェアの一つ。Apache Software Foundation（Apacheソフトウェア財団）が開発しており、オープンソースソフトウェアとして公開している。

HTML5 技術（convas ほか）

HTML5 とは、Web ページの記述などに用いるマークアップ言語である HTML（Hypertext Markup Language）の第 5 版。HTML4 から仕様が大幅に刷新された。

(2) 文法の表記法

4. プログラミング言語

(1) プログラミング言語

① プログラミング言語の変遷と分類

② 手続型言語

手続型言語（procedural language）とは、プログラミング言語の分類の一つで、コンピュータが実行すべき命令や手続きを順に記述していくことでプログラムを構成する言語。

③ オブジェクト指向言語

オブジェクト指向言語（object-oriented programming language）とは、プログラミング言語のうち、互いに関連するデータの集合とそれらに対する手続き群をひとまとめにした「オブジェクト」（object）をプログラムの基本的な構成単位として扱うことができるもの。

④ スクリプト言語

スクリプト言語（scripting language）とは、プログラミング言語の一種で、オペレーティングシステム（OS）やアプリケーションソフトの動作や機能などをプログラムの形で記述できるもの。転じて、実行可能形式への変換作業などを省略・自動化したり、少ない記述量でも実行できるなど、仕様や開発手順が簡略化された言語の総称を表すこともある。

⑤ 共通言語基盤（CLI : Common Language Infrastructure）

米マイクロソフト（Microsoft）社が推進する .NET の実行環境（CLR）および対応プログラムの記述言語（CIL）の標準仕様を定めた規格。同社による実装を .NET Framework という。

機種や OS に依存しないプログラムの開発・実行環境を実装するために必要な諸技術の仕様を定めている。.NET プログラムの配布形式である CIL（Common Intermediate Language/共通中間言語/MSIL/IL）の仕様と、開発に用いるプログラミング言語に求められる共通仕様、実行環境（CLR）が実装すべき仕様を定めている。

(2) C の知識と技術

C 言語（C language）とは、広く普及している手続き型の高水準プログラミング言語の一つ。汎用的な言語で様々な分野で広く利用されているが、特にハードウェアを直接制御するプログラムの開発で利用される機会が多い。

C 言語の最初の仕様は 1972 年に AT&T 社のベル研究所でデニス・リッチー（Dennis M. Ritchie）氏とブライアン・カーニハン（Brian W. Kernighan）氏によって発表され、1989 年に ANSI（米国国家規格協会）標準に、1990 年に ISO（国際標準化機構）標準となった。日本でも 1993 年に ISO 標準を和訳したものを JIS（日本工業規格）の一部として標準化している。

#include<stdio.h>
int main(void){
	printf("Hello World !");
	return 0;
}

C 言語は UNIX の移植性を高めるために作られたプログラミング言語である。UNIX では，main 関数から返される値が「0」であれば正常終了，「0 以外」であれば異常終了と判断される。上記のリストにおいて，5 行目の「return 0;」は，main 関数が正常に終了したことを示している。

(3) Java の知識と技術

Java とは、様々な分野で人気の高いオブジェクト指向プログラミング言語の一つ。旧サン・マイクロシステムズ（Sun Microsystems）社が開発したもので、同社を買収した米オラクル（Oracle）社が開発を引き継いでいる。

C言語に似た表記法を採用しているが、過去の言語の仕様を受け継がず新たに設計されており、特にオブジェクト指向プログラミングを前提として言語仕様が整理されている点が大きな特徴となっている。強力なセキュリティ機構や豊富なネットワーク関連の機能が標準で用意されており、ネットワーク環境で利用されることを強く意識した仕様になっている。

Java に関連する技術は数多く存在し，その代表的な技術を下表に示す。

(4) Python の知識と技術

Python とは、簡潔で読みやすい文法が特徴的な汎用の高水準プログラミング言語の一つ。いわゆるスクリプト言語あるいは軽量言語（LL：Lightweight Language）の草分けの一つで、UNIX 系 OS を中心に広く普及している。

基本的な特徴としては、豊富なデータ型とコンテナ型、ガベージコレクション、Unicode による多言語対応、プログラムのモジュール（部品）化による他のプログラムへの容易な組み込み、プログラムの仕様の文書化（ドキュメンテーション）を支援する機能などがある。ユニークな特徴としては、多くの言語では人間にとってプログラムを読みやすくするために便宜的に行われるインデント（字下げ）を言語仕様上の構文の一つとして採用しており、ブロックの範囲を示すのに用いられる。

言語自体の文法や語彙、記法な最小限のシンプルなものに抑えられているが、対照的に、極めて広範囲の分野に渡り豊富な機能を提供する標準ライブラリが用意されている。当初は手続き型言語とオブジェクト指向言語の特徴を備えた言語として設計されたが、関数型言語の要素の多くを取り入れ、様々なスタイルのプログラミングが可能なマルチパラダイム言語として知られている。

(5) アセンブラ言語（CASL Ⅱ）の知識と技術

アセンブリ言語とは、プログラミング言語の類型の一つで、コンピュータの CPU（MPU/マイクロプロセッサ）が直接解釈・実行できる機械語（マシン語）と正確に対応する命令語で構成された言語。

(6) 表計算ソフト

表計算ソフト（spreadsheet software）とは、主に大量の数値データの集計や分析などに用いられるアプリケーションソフト。

パソコン向けの表計算ソフトとしては、Microsoft社のMicrosoft Officeの一部として提供される「Microsoft Excel」（マイクロソフト・エクセル）が最も有名でシェアが高いが、他にもApple社の「Numbers」、OpenOffice.orgやLibreOfficeの「Calc」などがある。Google社の「Google Sheets」（日本名はGoogleスプレッドシート）のようにWebブラウザなどからインターネットを通じて利用するネットサービスなどもある。

• ソフトウェア開発（表計算）

5. その他の言語

(1) マークアップ言語

マークアップ言語（markup language）とは、コンピュータによって処理される人工言語の種類の一つで、データ中に特定の記法を用いて何らかの情報を埋め込むためのもの。テキスト（文字）データ中に特定の記号で囲まれたタグ（tag）と呼ばれる表記を用いて構造や見栄えなどを記述するものがよく知られるが、バイナリデータ中に埋め込むものなど、様々な種類がある。

① HTML

HTML（Hyper Text Markup Language）とは，Web ページを記述するためのマークアップ言語。文書の論理構造や表示の仕方などを記述することができる。W3C によって標準化が行われており、大半の Web ブラウザは標準で HTML 文書の解釈・表示が行える。

② XML

XML（Extensible Markup Language）とは、文書やデータの意味や構造を記述するためのマークアップ言語の一つ。マークアップ言語とは、「タグ」と呼ばれる特定の文字列で地の文に情報の意味や構造、装飾などを埋め込んでいく言語のことで、XML はユーザが独自のタグを指定できることから、マークアップ言語を作成するためのメタ言語とも言われる。

XML では，利用者独自のタグを使って，文書の属性情報や論理構造を定義することができる。

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<root>
	<child attr="value">TEXT</child>
</root>

③ XHTML

XHTML（Extensible HyperText Markup Language）とは、Webページの記述などに用いられるマークアップ言語であるHTML（HyperText Markup Language）をXMLの仕様に従って定義しなおした言語。Web関連技術の標準化を推進するW3C（World Wide Web Consortium）によって規格の策定が行われた。

④ スタイルシート

スタイルシート（style sheet）とは、文書データの見栄えに関する情報のみを記録・定義したデータやファイルなどのこと。スタイルシートの入れ替えや編集により、文書自体の内容はそのままに見栄えだけを変更することができる。

Web ページの記述に用いられるHTMLなどにもスタイルシートの概念があり、一般的にはCSS（Cascading Style Sheets）と呼ばれる専用の言語によりスタイルシートを記述する。単にスタイルシートといった場合は CSS 形式のデータやファイルなどを指すことが多い（XSL など他の方式も存在する）。

HTML 文書にスタイルシートを適用すると、文書本体から表示形式やレイアウトなどに関する情報を分離し、文書の構造だけを HTML ファイル本体に記述することが可能になる。

これによって、HTML 文書の論理的な構造が把握しやすくなるほか、サイト内の複数のページで同じスタイルを共有でき、変更を一括して適用するなどの効率的な管理ができるようになる。

(2) その他の言語