基礎理論
目次
応用情報技術者試験（レベル３）シラバス－情報処理技術者試験における知識・技能の細目－ Ver.7.0 に基づき，「基礎理論」の対策ノートを作成した。
離散数学
- 基数，基数の変換，数値の表現，算術演算と精度など，コンピュータで扱う数値表現を修得し，応用する。
- 集合，論理演算の基本法則，手法を修得し，応用する。
(1) 基数
基数（radix）とは、位取り記数法で数値を書き記す際に各桁の重み付けの基本となる数で、位が上がる毎に何倍になるかを表す。我々が普段使っているのは隣の桁が 10 倍あるいは 10 分の 1 となる 10 進数（10 進法）であり、基数は 10 である。
2 進数，8 進数，10 進数，16 進数の対応を次表に示す。
| 10 進数 | 2 進数 | 8 進数 | 16 進数 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 2 |
| 3 | 11 | 3 | 3 |
| 4 | 100 | 4 | 4 |
| 5 | 101 | 5 | 5 |
| 6 | 110 | 6 | 6 |
| 7 | 111 | 7 | 7 |
| 8 | 1000 | 10 | 8 |
| 9 | 1001 | 11 | 9 |
| 10 | 1010 | 12 | A |
| 11 | 1011 | 13 | B |
| 12 | 1100 | 14 | C |
| 13 | 1101 | 15 | D |
| 14 | 1110 | 16 | E |
| 15 | 1111 | 17 | F |
10 進数整数を $r$ 進数へ変換
10 進数の整数値 $x$ を $r$ 進数に変換する手順は次のとおり。
- $x$ を $r$ で割ったときの商 $p$ と余り $q$ を求める。
- $p$ の値が 0 ならば終了。それ以外ならば $p$ を $x$ と読み替えて 1. へ戻る。
計算の終了後，これまでに求まった $q$ の値のうち，最後に求まった $q$ の値を最上位桁として順に下位方向に並べたときの数列が変換された $r$ 進数の値である。
10 進数小数を $r$ 進数へ変換
10 進数の小数値 $x$ を $r$ 進数へ変換する手順は次のとおり。
- $x$ を $r$ で乗算した結果を，整数部の数値 $i$ と $i$ を除いた小数値 $d$ に分ける。
- $d$ の値が 0 ならば終了。それ以外ならば $d$ を $x$ に読み替えて，1. に戻る。
計算の終了後，これまでに求まった $i$ の値のうち，最初に求まった $i$ の値を小数第 1 位として順に下位方向に並べたときの数列が，変換された $r$ 進数の値になる。
桁数の関係
正の整数の 10 進数表示の桁数 $D$ と 2 進数表示の桁数 $B$ との関係は，次式で表される。
\[ D \approx B\log_{10}{2} \]上式は，$10^{D} \approx 2^{B}$ の両辺の対数をとることで，求められる。
負の整数表現
負の整数を表現する代表的な方法として，次の 3 種類がある。例として，4 ビットのパターン 1101 が，以下の方法で表現された場合を考える。
1 の補数による表現
1 の補数表現では，全ビットを反転すると絶対値になる。
絶対値は 2 なので，1 の補数で表現された 1101 は「-2」を表す。
2 の補数による表現
2 の補数表現では，全ビットを反転して 1 を加えると絶対値になる。
絶対値は 3 なので，2 の補数で表現された 1101 は「-3」を表す。
絶対値に符号を付けた表現（左端ビットが 0 の場合は正，1 の場合は負）
左端の 1 ビットが符号ビット，残りの 3 ビットが絶対値を表す。左端の 1 ビットは 1 なので負数，残りの 3 ビットは 101 なので絶対値は 5 となる。よって，この表現では 1101 は「-5」となる。
(2) 数値の表現
コンピュータの中では，整数だけでなく負数や小数点数なども，すべて 0 と 1 の 2 進数で表される。
固定小数点数
固定小数点数（fixed-point number）とは、コンピュータが実数を扱うときの表現形式の一つで、小数点が特定の位置に固定されているもの。
浮動小数点数
浮動小数点（floating point number）とは，コンピュータにおける数値の表現形式の一つで、数値を桁の並びを表す仮数部と小数点の位置を表す指数部に分割して表現する方式。小数点以下の値を含む数値の表現法として最も広く利用されている。
浮動小数点数は，小数点の位置を固定せずに小数点数を表現する方法である。数値を指数形式（± f × re）で表した時の，「符号（正を 0，負を 1）」，「仮数 f」，「指数 e」を下図の順に並べて表現する。これを浮動小数点形式という。ここで，r は基数を意味し，通常，基数は 2 である。また，仮数 f は「0.1xxx」となるように，指数 e と桁合わせをする。
単精度浮動小数点数（float 型）
単精度浮動小数点数型（single precision floating point number type）とは、プログラミング言語などで用いられる数値データ型の一つで、32 ビット長の浮動小数点数を格納することができるもの。多くの言語では実数を表すことができる最も基本的な型として用意されている。
倍精度浮動小数点数（double 型）
倍精度浮動小数点数型（double precision floating point number type）とは、プログラミング言語などで用いられる数値データ型の一つで、64ビット長の浮動小数点数を格納することができるもの。多くの言語では最も幅広い範囲の実数を表すことができる型として用意されている。この形式で表すことができる値は 10 進数で概ね -1.79769 × 10308 ～ 1.79769 × 10308 の範囲で，精度は 15 桁である。
BCD
BCD（Binary-Coded Decimal，2 進化 10 進数）とは、10 進数の値を 2 進数で表現する方式の一つで、10 進数の一つの数字を 4 桁の 2 進数に対応させたもの。IBM 社がメインフレームで用いていた方式が広まったもので、これをアルファベットや記号を含む文字コードに拡張したものは EBCDIC として知られる。
| 10 進数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| BCD | 0000 | 0001 | 0010 | 0011 | 0100 | 0101 | 0110 | 0111 | 1000 | 1001 |
パック 10 進数
2 進化 10 進数（BCD）を拡張し、末尾に数値の符号を表すコードを追加したものをパック 10 進数（packed BCD）という。1 バイトで 1 桁を表すゾーン 10 進数（アンパック 10 進数）に比べ少ないデータで数値を表すことができる。
(3) 算術演算と精度
論理シフト
全ビットを一律に移動させるものを「論理シフト」（logical shift）という。
算術シフト
最上位ビットは変化させず残りのビット列でシフトを行うものを「算術シフト」（arithmetic shift）という。
桁落ち
値のほぼ等しい二つの数値の差を求めたとき，有効桁数が減ることによって発生する誤差
情報落ち
絶対値の非常に大きな数値と小さな数値の加算や減算を行ったとき，小さい数値が計算結果に反映されないことによって発生する誤差
丸め誤差
指定された有効桁数で演算結果を表すために，切捨て，切上げ，四捨五入などで下位の桁を削除することによって発生する誤差
打切り誤差
無限級数で表される数値の計算処理を有限項で打ち切ったことによって発生する誤差
オーバーフロー（あふれ）
オーバーフロー（overflow）とは、あふれ（る）、あふれ出たもの、という意味の英単語。IT の分野では、数値の計算結果がその格納領域に収まる範囲を超えること（算術オーバーフロー/桁あふれ）や、与えられたデータが多すぎて指定の領域に収まりきらないこと（バッファオーバーフローなど）を指す。
アンダーフロー
アンダーフロー（underflow）とは、コンピュータで実数の計算をした結果、絶対値が小さすぎて正確に表現・計算できなくなってしまうこと。
単精度
数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を32ビットのデータで表現する方式のこと。多くのプログラミング言語などでは単に浮動小数点といえば単精度を意味し、“float” などの名称で表されるデータ型が用意されている。
倍精度
数値を仮数部と指数部に分けて表現する浮動小数点数の形式の一つで、一つの数値を32ビットのデータで表現する方式のこと。多くのプログラミング言語などが高精度な数値計算のために組み込みデータ型として用意しており、"double" などの名称で表される。
(4) 集合と命題
和集合
$\cup$ は，和集合を表す。
積集合
$\cap$ は積集合を表す。
部分集合
部分集合とは、ある集合 $X$ の全ての要素が他の集合 $Y$ に含まれる（内包される）という 2 つの集合同士の関係を表し、数学記号 "$\subseteq$" を用いて「$X \subseteq Y$」と表記する。
(5) 論理演算
否定（NOT）
否定の論理式は次式，真理値表は次表で表される。
| A | F |
|---|---|
| 0 | 1 |
| 1 | 0 |
論理和（OR）
論理和の論理式は次式，真理値表は次表で表される。
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
論理積（AND）
論理積の論理式は次式，真理値表は次表で表される。
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
排他的論理和（XOR，EOR，EXOR）
排他的論理和は次式，真理値表は次表で表される。
| A | B | F |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
否定論理和（NOR）
否定論理和の論理式は次式，真理値表は次表で表される。
| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
否定論理積（NAND）
否定論理積の論理式は次式，真理値表は次表で表される。
| A | B | F |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
相補演算
相補演算とは，集合演算によって得られる結果が互いにもう一方の演算の補集合となっている関係をいう。すなわち A と ¬A のような関係である。
ド・モルガンの法則
ド・モルガンの法則は，否定論理はおよび否定論理積をそれぞれ論理和と論理積に変換するものである。
\[ \overline{A\cdot B}=\overline{A}+\overline{B} \] \[ \overline{A+B}=\overline{A}\cdot\overline{B} \]カルノー図
カルノー図は、行・列それぞれの論理変数の組合せの結果が "真" となる場合に「1」を、"偽" となる場合に「0」を、その該当セルに書きこむことで論理式を図で表す方法である。
カルノー図から論理式を導くには、表の中のすべての「1」が記入されているセルをグループ化して共通項を取り出すが、このグループ化は、以下の 3 つのルールに則って行う。
- グループ化するすべてのセルの値は 1 であること
- グループ化するセルの数は 2N であること
- カルノー図の上下の端、および左右の端は連続していると考える
| CD | |||||
|---|---|---|---|---|---|
| 00 | 01 | 11 | 10 | ||
| AB | 00 | 1 | 0 | 0 | 1 |
| 01 | 0 | 1 | 1 | 0 | |
| 11 | 0 | 1 | 1 | 0 | |
| 10 | 0 | 0 | 0 | 0 | |
カルノー図と等価な論理式は，次式となる。
\[ \overline{A}\cdot\overline{B}\cdot\overline{D} + B\cdot D \]応用数学
- 確率・統計の計算，分析手法を修得し，応用する。
- 線形代数，行列などの数値計算を修得し，応用する。
- 数値解析，グラフ理論，待ち行列理論など，数学的原理を修得し，応用する。
(1) 確率と統計
① 確率
確率とは，ある事象（結果）が発生する可能性を表す数値である。事象 A の確率 $P(A)$ は，事象 A の起こりうる場合の数（$r$）と全ての事象の数（$n$）から，次のように求める。
\[ P(A)=\frac{r}{n} \]加法定理（addition theorem）
確率における加法定理は，$k$ 個の事象 $E_1$，$E_2$，...，$E_k$ があって，このうちのどの二つも同時に起こることはないとする。すなわち，事象 $E_1$，$E_2$，...，$E_k$ が排反事象であるとする。このとき，事象 $E_1$，$E_2$，...，$E_k$ のうちの少なくとも一つが起こるという確率 $p$ は，各事象 $E_i$ の起こる確率 $p(E_i)$ の和に等しい。
\[ p = p(E_1)+P(E_2)+...+p(E_k) \]乗法定理
事象 $A$ が起こり，続いて $B$ が起こる確率 $P$ は，$A$ が起こる確率と，$A$ が起こったという条件のもとで $B$ が起こる確率の積で求められる。
\[ P(A \cap B) = P(A)P(B|A) \]正規分布
正規分布はガウス分布とも呼ばれ，統計学では最もよく用いられる連続型の確率分布である。自然界でも多く見られ，理論的にもとても都合の良い性質を持っている。実用面でも多くの場面で誤差関数（仮定した理論的な値と観測された値との差）として正規分布が仮定されている。
確率変数（実数）を $x$，平均を表すパラメータ（実数）を $\mu$，標準偏差を表すパラメータ（正の実数）を $\sigma$ とすれば，正規分布の確率密度関数は次式で表される。
\[ f(x)=\frac{1}{\sqrt{2\pi \sigma^2}}\exp\{-\frac{(x-\mu)^2}{2\sigma^2}\} \]平均が 50，標準偏差が 5，10，20 である正規分布の確率密度関数を表すグラフを下図に示す。形状は平均値 50 を中心に左右対称で，標準偏差が小さければ，データの分布は平均値付近にまとまる。
演習問題
受験者 1,000 人の 4 教科のテスト結果は表のとおりであり，いずれの教科の得点分布も正規分布に従っていたとする。90 点以上の得点者が最も多かったと推定できる教科はどれか。
| 教科 | 平均点 | 標準偏差 |
|---|---|---|
| A | 45 | 18 |
| B | 60 | 15 |
| C | 75 | 8 |
| D | 75 | 5 |
各教科の得点分布は下図のようになり，90 点以上の得点者が最も多かったと推定できる教科は B である。
ポアソン分布
非常に大きな集団において，きわめて起こりにくい事象を対象としたときの分布である。
② 統計
標準偏差
標準偏差は，データの分布のばらつきを表す尺度で，正規分布では平均値と標準偏差 σ，および度数の間には次の関係が成り立つ。
- 平均 ± σ の範囲に全体の約 68 % が含まれる
- 平均 ± 2σ の範囲に全体の約 95 % が含まれる
- 平均 ± 3σ の範囲に全体の約 99 % が含まれる
相関係数
相関係数は、2 つの項目の関連度合いを示す値である。値として -1 ～ +1 の間の実数値をとり、-1 に近ければ負の相関、+1 に近ければ正の相関があるという。逆に値が 0 に近いときには 2 項目間の相関は弱いと判断される。
(2) 数値計算
(3) 数値解析
ニュートン法
非線形方程式 $f(x)=0$ の近似解法であり，次の手順によって解を求める。ここで，$y=f(x)$ には接線が存在するものとし，手順 3. で $x_0$ と新たな $x_0$ の差の絶対値がある値以下になった時点で繰返しを終了する。
- 解の近くの適当な $x$ 軸の値を定め，$x_0$ とする。
- 曲線 $y=f(x)$ の，点 ($x_0$, $f(x_0)$) における接線を求める。
- 求めた接線と，$x$ 軸の交点を新たな $x_0$ とし，手順 2. に戻る。
(4) 数式処理
(5) グラフ理論
無向グラフ（undirected graph）
向きがなく，一つのエッジとつながっているノードが両方元にも先にもなっている。
有向グラフ（directed graph）
全てのエッジに向きがあり，元と先がはっきりしている。
完全グラフ（complete graph）
全てのノード間にエッジがあるグラフ。
(6) 待ち行列理論
キューとは、最も基本的なデータ構造の一つで、要素を入ってきた順に一列に並べ、先に入れた要素から順に取り出すという規則で出し入れを行うもの。順番を待つ人の行列と同じ仕組みであるため「待ち行列」とも訳される。
M/M/1 待ち行列モデル
待ち行列モデル M/M/１ では，条件としてトランザクションの到着間隔はランダムであり，待ち行列内のトランザクション数は一定であるとしている。（平衡状態）
待ち行列モデルでの平均待ち時間とは，サービス（処理）要求が発生してから，実際にサービスを受けるまでの時間を指す。平均待ち時間を求める公式を次式に示す。
通信回線を使用したデータ伝送システムに M/M/1 の待ち行列モデルを適用すると，平均回線待ち時間，平均伝送時間，回線利用率の関係は，次に式で表すことができる。
回線利用率が 0 % から徐々に増加していく場合，平均回線待ち時間が平均伝送時間よりも最初に長くなるのは，回線利用率 0.5 を超えたときである。
リトルの法則
リトルの法則（Little's law）とは，待ち行列理論において「安定な系において長時間平均化した顧客数 $L$（与えられた負荷）は，長時間平均化した到着率 $\lambda$ と長時間平均化した顧客が形に費やす時間 $W$ に等しい」というものであり，次式が成り立つ。
\[ L=\lambda W \](7) 最適化問題
動的計画法
動的計画法（どうてきけいかくほう、英 : Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の 1 つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法。
連続最適化問題
連続最適化問題（英: continuous optimization problem）とは、制約条件の集合 A がユークリッド空間 $\displaystyle \mathbb {R} ^{n}$ の部分集合の物。
組合せ最適化問題
組合せ最適化問題とは、様々な制約の下で多くの選択肢の中から、ある指標（価値）を最も良くする変数の値（組合せ）を求めること。
ナップサック問題
幾つかの種類の品物があり，それぞれの容積と価値が与えられているとき，選んだ品物の容積の合計が定められた値以下であるという条件（容量制限）を満たし，かつ，価値の合計（以下，価値合計という）が最大になるような品物の組合せを求める問題をナップザック問題（Knapsack Problem）という。
巡回セールスマン問題
巡回セールスマン問題は、都市間の距離のリストが与えられた際に、セールスマンが複数の都市をどのように訪問すれば、最短の移動経路（最適経路）で済むかを求める問題となる。ただし，それぞれの都市には一度ずつしか訪問しないとする。都市数が少なければすべて全ての解候補をしらみつぶしに調べることが可能である。しかし、都市数が例えば 30 都市に増えると、候補数が爆発的に増加し、その組合せの数は 10 の 30 乗という驚異的な値となる。このように、組合せ最適化問題はパラメータが増えると、厳密解を得ることが途端に難しくなる特徴がある。
情報に関する理論
- 情報理論，符号理論の考え方，仕組みを修得し，応用する。
- コードによる文字の表現を修得し，応用する。
- 述語論理，形式言語，オートマトンなど，情報に関する理論の考え方，仕組みを修得し，応用する。
- 正当性理論の考え方，仕組みを修得し，応用する。
- AI（人工知能）の考え方，仕組み，代表的なモデルを修得し，応用する。
- コンパイラ理論，プログラム言語論や意味論の考え方，仕組みを修得し，応用する。
(1) 情報理論
(2) 符号理論
コンピュータ同士の通信においては，次の点を考慮する必要がある。
- 通信路上で起きた誤りの検出・訂正を受信側で行えること
- 送信する元の情報を短くし，通信効率を高めること
上記を実現する方法はさまざまあるが，その 1 つとして符号化がある。
ハフマン符号
ハフマン符号化方式は、可変長の符号化方式で、出現確率が高いデータには短い符号を、低いデータには長い符号を与えることで圧縮を効率よく行う方法である。特に、出現確率に差がある場合には固定長の符号化よりも高い圧縮率になる。
例えば，a，b，c，d の 4 文字からなるメッセージを符号化してビット列にする方法を考える。符号化されたビット列から元のメッセージが一意に復号可能であり，ビット列の長さが最も短くなるようにすると，次表のようになる。
| 文字列 | 出現頻度 | 符号化 |
|---|---|---|
| a | 50 % | 0 |
| b | 30 % | 10 |
| c | 10 % | 110 |
| d | 10 % | 111 |
各文字の出現頻度を考慮すると，1 文字を表現するのに必要な平均ビット列は，1.7 ビットとなる。
情報源符号化（データ圧縮）
データ圧縮（data compression）とは、データを一定の計算手順で加工し、実質的な内容を損なわずにより短い符号列で表すこと。原則として得られた圧縮符号は逆の計算手順により元のデータに復元することができ、データの一部を損なって容量を減らす削減や間引きとは異なる。
(3) 文字の表現
ASCII コード
ASCII（American Standard Code for Information Interchange）とは、アルファベットや数字、記号などを収録した文字コードの一つ。最も基本的な文字コードとして世界的に普及しており、他の多くの文字コードが ASCII の拡張になるよう実装されている。文字を 7 ビットの値（0～127）で表し、128 文字が収録されている。
ECU (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 という。
UTF-7
ASCII 文字だけを使用することが前提の電子メールで利用するために，7 ビットで表現する。
UTF-8
UTF-8 は、ASCII と同じ文字は 1 バイト、その他の文字については 2 ～ 6 バイトを用いて世界中の文字を表現する文字符号化形式である。ASCII の上位互換であるため、従来のシステムとの親和性が高く、また ASCII 主体のテキストであればデータ量をそれほど増加させずに多言語対応の恩恵を受けられる利点がある。UTF-8 は世界中で使用されていますが、特に Web ページを記述する際の文字コードとしてはスタンダードと呼ばれるほど普及している。
UTF-16
2 バイトで表現する領域に収まらない文字は，上位サロゲートと下位サロゲートを組み合わせて 4 バイトで表現する。
UTF-32
各符号位置が4バイトの固定長で表現される符号化形式である。
(4) 述語論理
関係データベース（リレーショナルデータベース）とは，データベースの構造の一つで、一件のデータを複数の属性の値の組として表現し、組を列挙することでデータを格納していく方式。属性を列、組を行とする表（テーブル）の形で示されることが多い。最も普及している方式で、単にデータベースといった場合は関係データベースであることが多い。
(5) 形式言語
コンピュータで使用する言語は，明確な定義のもとで作成した形式（フォーマット）に従い，文字やプログラムを読み，理解する。これを形式言語と呼ぶ。形式言語の代表的な表記方法として，正規表記，BNF がある。
逆ポーランド表記法
通常の式を，逆ポーランド表記法（後置表記法）で表現するための基本は，「A+B」を「AB+」で表すことである。1 回変換した部分は 1 つの項としてみなすことに注意して，普通に計算式を解くのと同じ順番で変換を行っていくことで逆ポーランド表記法の式になる。
例として，式 A+B×C の逆ポーランド表記法による表現に変換する。
最初に「B×C」の部分を変換する。
次に「BC×」を 1 つの項とみなして，A との + 演算部分を変換する。
正規表現
正規表現とは，文字列などの記号列を表現する形式言語である。正規表現では，有限個の記号に対して，規則を表すメタ文字を組み合わせて表現する。
| メタ文字 | 意味 |
|---|---|
| [A-Z] | 半角の英字の大文字 1 文字を表す |
| * | 直前の正規表現の 0 回以上の繰返し |
| + | 直前の正規表現の 1 回以上の繰返し |
| ? | 直前の正規表現の 0 個または 1 個あることを表す |
| | | 左右にある正規表現のいずれかを表す。 |
BNF
BNF（Backus-Naur Form）とは、コンピュータが扱う人工言語の文法を定義する際に用いられるメタ言語（言語を記述するための言語）の一つ。コンピュータ言語の多くはその仕様は BNF で記述している。構文規則には，順次，反復，選択があり，次表の記号を用いる。
| 記号 | 意味 |
|---|---|
| <x> | x という構文要素を表す |
| ::= | 左に示す構文要素に対し，右の構文規則を定義することを表す |
| ... | 左の構文要素を繰り返すことを表す |
| | | 左右の構文要素のどちらかを表す |
| [ ] | [ ] に囲まれた構文要素は省略可能を表す |
(6) オートマトン
オートマトン（automaton）とは、計算機の構造や動作を抽象化したモデルの一つで、内部に固有の状態と、状態を変化させる規則の集合を持ち、外部からの入力に応じて状態を変化させるもの。複数形は “automata” （オートマタ）。
(7) 正当性理論
(8) 計算量
アルゴリズムの効率性を評価する基準として，処理を行うデータ件数を $n$ としたときの実行時間の目安を表す計算量がある。計算量は，「$O$」（英字の大文字で，オーダと読む）の記号を用いて，「$O(n)$」と表す。計算量が $O(n)$ の場合は，処理件数 $n$ に計算量が比例し，$O(1)$ は処理件数に関わらず計算量は変わらないことを示す。
(9) AI（Artificial Intelligence : 人工知能）に関する技術
① AI の基本的な考え方
人工知能とは、人間にしかできなかったような高度に知的な作業や判断をコンピュータを中心とする人工的なシステムにより行えるようにしたものである。
エキスパートシステム
ある特定の分野に特化した知識を基にルールベースの推論を行うことによって，専門家と同じレベルの問題解決を行う。
② 機械学習
機械学習は，機械に与えるデータを AI 自身が解析してルールや法則を反復的に学習し，人間が行う知的な振る舞いを人工的に再現する技法である。機械学習における学習方法は，次表に示す 3 つがある。
| 種類 | 内容 |
|---|---|
| 教師あり学習 | 学習データに正解ラベルを付けて学習する方法。主に入力と出力の関係を学習させる |
| 教師なし学習 | 学習データに正解ラベルを付けないで学習する方法。主にデータの構造を学習させる。 |
| 強化学習 | 正解ラベルの代わりに，与えられた環境でとった行動に対して報酬（評価）を与える学習方法。将棋，囲碁や株の売買など，場面に応じてとるべき最良の行動を学習させる。 |
教師あり学習
AI の機械学習における教師あり学習で用いられる手法として，幾つかのグループに分かれている既存データ間に分離境界を定め，新たなデータがどのグループに属するかはその分離境界によって判別するパターン認識手法がある。
教師なし学習
AI の機械学習における教師なし学習で用いられる手法として，データ同士の類似度を定義し，その定義した類似度に従って似たもの同士は同じグループに入るようにデータをグループ化するクラスタリングがある。
強化学習
AI の機械学習における強化学習で用いられる手法として，数式で解を求めることが難しい場合に，乱数を使って疑似データを作り，数値計算をすることによって解を推定するモンテカルロ法がある。
③ ディープラーニング（深層学習）
神経回路網を模倣した方法であり，多層に配置された素子とそれらを結ぶ信号線で構成されたモデルにおいて，信号線に付随するパラメタを調整することによって入力に対して適切な解が出力される。
ディープラーニング（Deep Learning）は、人間や動物の脳神経をモデル化したアルゴリズムを多層化したものを用意し、それに「十分な量のデータを与えることで、人間の力なしに自動的に特徴点やパターンを学習させる」ことをいう。人工知能の機械学習分野における要素技術の 1 つで、深層学習とも呼ばれる。従来の機械学習方式と異なり、中間層の多層化によって複雑なパターンの表現と計算を可能にしていることが特徴であり，あるデータから結果を求める処理を，人間の脳神経回路のように多層の処理を重ねることによって，複雑な判断をできるようにする。
④ 自然言語処理，音声・画像・動画の認識・合成・生成などへの応用
(10) コンパイラ理論
中間言語
中間コードとは、人間が読み書きしやすいプログラミング言語で書かれたソースコードと、コンピュータが直に実行可能なネイティブコードの中間の特徴を持つ形式のプログラムコード。命令を表すコードを 1 バイトで表現するものは特に「バイトコード」（byte code）と呼ばれる。
目的プログラム
オブジェクトコードとは、コンピュータプログラムの形式の一つで、コンピュータによる解釈・実行に適した言語やコード体系で記述されたもの。通常は人間が直接記述することはなく、ソースコードから変換して生成する。
形式言語
コンピュータで使用できるよう，明確な定義の下で作成した形式（フォーマット）に従い，文字やプログラムを記述したもの。
オートマトン
オートマトンとは、計算機の構造や動作を抽象化したモデルの一つで、内部に固有の状態と、状態を変化させる規則の集合を持ち、外部からの入力に応じて状態を変化させるもの。複数形は “automata” （オートマタ）。
(11) プログラム言語論・意味論
手続型言語（procedural language）
手続き型言語とは、プログラミング言語の分類の一つで、コンピュータが実行すべき命令や手続きを順に記述していくことでプログラムを構成する言語。
関数型言語（functional language）
関数型言語とは、プログラミング言語の分類の一つで、プログラム中の処理や制御を関数の定義と適用の組み合わせとして記述していくもの。そのようなスタイルでコードを記述することを「関数型プログラミング」（functional programming）という。
オブジェクト指向言語（object-oriented programming language）
オブジェクト指向言語とは、プログラミング言語のうち、互いに関連するデータの集合とそれらに対する手続き群をひとまとめにした「オブジェクト」（object）をプログラムの基本的な構成単位として扱うことができるもの。
通信に関する理論
- 情報を伝送するための技術について，代表的な方式の考え方，仕組みを修得し，応用する。
(1) 伝送理論
① 伝送路
② 変復調方式
③ 多重化方式
④ 誤り検出・訂正
ハミング符号
ハミング符号は、情報ビットに検査ビットを付加することで 2 ビットまでの誤りを検出し、1 ビットの誤りを訂正できる手法である。ECC メモリ（Error Check and Correct memory）や RAID2 の誤り訂正符号として使用されている。
演習問題
ハミング符号とは，データに冗長ビットを付加して，1 ビットの誤りを訂正できるようにしたものである。ここでは，X1，X2，X3，X4 の 4 ビットから成るデータに，3 ビットの冗長ビット P3，P2，P1 を付加したハミング符号 X1X2X3P3X4P2P1 を考える。付加ビット P1，P2，P3 は，それぞれ
となるように決める。ここで ⊕ は排他的論理和を表す。
ハミング符号 1110011 には 1 ビットの誤りが存在する。誤りビットを訂正したハミング符号はどれか。
- 0110011
- 1010011
- 1100011
- 1110111
正解は，1. である。
ハミング符号 1110011 をデータビットと冗長ビットに分け，各ビットを問題文中の 3 つの式に当てはめ，誤りを検証する。
1 ビットの誤りが存在し，3 つの式の結果が 0 ではないということは，すべての式に含まれている X1 が誤りのビットであると判断できる。
パリティチェック
パリティチェックは、データ通信やメモリチェックなどにおいてデータのビット誤りを検出する最もシンプルな方法の一つである。一定長のビット列（通常は 7～8 ビット）ごとに 1 ビットの検査ビット（パリティビット）を付加し、検査側が受信データとパリティビットを照合することで誤りを検出する。
奇数パリティ
奇数パリティは、データを構成するビット全体の中でビット「1」の数が奇数になるようにパリティビットを付加する方式である。1 ビットの誤りを検出することができる。
水平パリティ
水平パリティは、データの水平方向を対象としてパリティビットを付加する方式である。垂直方向と組み合わせた垂直水平パリティチェックでは 1 ビットの誤りを訂正できるが、水平パリティだけでは 1 ビットの誤りのみが検出可能である。
垂直水平パリティ
パリティチェックは基本的には誤りの検出を目的とし、誤りを検出したときには送信元に再送を依頼するが、垂直水平パリティ方式ではビット誤りの検出にとどまらず、垂直・水平の併用で誤り位置を特定することにより、1 ビットであれば正しいデータに訂正することが可能となる。
垂直水平パリティの例として，下表のように 16 ビットのデータを 4 × 4 の正方形状に並べ，行と列にパリティビットを付加する。
| 1 | 0 | 0 | 0 | 1 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 0 | 0 | 0 | 1 | - |
チェックサム
チェックサムは、データの合計値を検査用に付加し、誤りが発生しているかを検査する方式である。
⑤ 信号同期方式
通信の分野では、機器やソフトウェアなどの間で信号やデータの送受信のタイミングを合わせ、正しく伝送されるよう制御することを同期という。
コンピュータ内部の通信では、一定周期のクロック信号に合わせて各回路や装置が信号を送り出すクロック同期が行われることが多い。クロック同期はデータの伝送だけでなく処理や制御のタイミングを合わせるのにも用いられる。
⑥ 暗号化
⑦ データ圧縮
ハフマン符号
出現度の高い文字を短いビット列で，出現率が低い文字を長いビット列で表現することで，1 文字を表現するのに必要な平均ビット長を最小とする圧縮技術をハフマン符号化という。
計測・制御に関する理論
- 信号処理に関する考え方，仕組みを修得し，応用する。
- 制御の必要性，考え方，仕組みを修得し，応用する。
- 代表的なセンサ・アクチュエータの種類と動作特性を修得し，応用する。
(1) 信号処理
(2) 制御に関する理論
① 制御の考え方，仕組み
② センサ・アクチュエータの種類と動作特性
TFO（Time of Flight）方式のセンサ
TOF 方式は、光源から発せられた光が対象物に当たり、その反射光が光源と同じ位置にあるセンサに返ってくるまでの時間によって対象物との距離を測定する方式である。カメラを用いる方式と比較すると、カメラが不要な単純な構成、昼夜及び天候の影響を受けないなどの利点がある。
地磁気センサ
飛行方向の制御に使用される。
ジャイロセンサ
ドローン，マルチコプタなどの無人航空機に搭載されるセンサのうち，機体を常に水平に保つ姿勢制御のために使われる。
超音波センサ
超音波センサは，発出した超音波が対象物に当たり，その反射が返ってくるまでの時間を計測することで対象物までの距離を測定するセンサである。障害物の検知に使用される。
気圧センサ
飛行高度および飛行速度の制御に使用される。
サーミスタ
サーミスタは，温度の変化により抵抗値が大きく変化する半導体で，流れる電流量によって温度を測定することができる。-50 °C から 150 °C 程度の範囲に使えるので、一般的な温度センサとして用いられる。
体温を測定するのに適切なセンサで，電子体温計の感温部がサーミスタである。
③ 計測システムの種類と動作特性
GPS
複数の衛星からの電波を受け取り，電波に含まれる情報から発信と受信の時刻差を求め，電波の伝播速度をかけることによって，各衛星との距離を割り出し，それを基に緯度及び経度を特定する。