基礎理論とアルゴリズム(計算量・待ち行列・符号化)

本章は応用情報技術者試験(IPA)シラバスの大分類「基礎理論」及び中分類「アルゴリズムとプログラミング」に対応し、午前試験(四肢択一80問)で毎回複数問が出題される得点源である。まず計算量の表記であるオーダー記法(O記法)を押さえる。O記法はデータ件数nが十分大きいときの処理時間の増え方を漸近的に表す指標であり、定数倍や低次の項は無視する。増加が緩やかな順にO(1)＜O(log n)＜O(n)＜O(n log n)＜O(n²)＜O(2ⁿ)と並ぶ。代表例は、配列の添字アクセスがO(1)、二分探索がO(log n)、線形探索がO(n)、クイックソートやマージソートの平均がO(n log n)、バブルソートがO(n²)、部分集合の全列挙がO(2ⁿ)である。本試験では「データ件数を2倍にしたとき処理時間が約4倍になるアルゴリズムの計算量はどれか」のように、オーダーと実処理時間の対応を問う形式が頻出する(この例の答えはO(n²))。

探索アルゴリズムは3方式を比較して整理する。線形探索は先頭から順に比較する方式で、目的データが等確率で存在する場合の平均比較回数は(n+1)/2回、計算量はO(n)である。二分探索は昇順又は降順に整列済みのデータが前提で、探索範囲の中央と比較して範囲を半分に絞り込むため、最大比較回数は約log₂n回、計算量はO(log n)となる。例えば100万件ならlog₂1,000,000≒20回で探索できる。ハッシュ探索はキーからハッシュ関数で格納位置を直接計算する方式で、衝突がなければ件数によらずO(1)で探索できる。異なるキーが同一のハッシュ値をもつことを衝突といい、衝突したキー同士をシノニムと呼ぶ。対策にはチェイン法(同一位置のデータを連結リストでつなぐ)とオープンアドレス法(再ハッシュ等で空き位置を探す)がある。午前ではハッシュ関数として除算法(キーを表の大きさで割った余りを位置とする)の性質を問う出題実績がある。

整列アルゴリズムは方式の説明文と名称の対応が最頻出である。基本交換法(バブルソート)は隣接要素の比較・交換を繰り返す方式で、比較回数はn(n-1)/2回、計算量はO(n²)。基本選択法・基本挿入法も同じくO(n²)である。クイックソートは基準値(ピボット)を決め、それより小さい値のグループと大きい値のグループに分割する操作を再帰的に繰り返す方式で、平均はO(n log n)だが、既に整列済みのデータに偏ったピボットを選ぶと最悪O(n²)に劣化する。マージソートは分割した部分列を整列しながら併合(マージ)する方式で常にO(n log n)を保つが、作業用領域が別途必要になる。ヒープソートは未整列部分をヒープ(親が子以上または子以下となる完全二分木)に構成し、根を取り出す操作を繰り返す方式でO(n log n)である。同一キーの要素の相対順序が整列後も保存される性質を安定というが、バブル・挿入・マージは安定、クイック・ヒープ・選択は不安定である。

待ち行列理論では、モデルをケンドール記法「到着分布/サービス時間分布/窓口数」で表す。基本のM/M/1モデルは、客の到着がポアソン分布に従い(到着間隔は指数分布)、サービス時間が指数分布に従い、窓口が1つで、待ち行列の長さに制限がなく先着順にサービスするという前提をもつ。窓口の利用率はρ=λ/μ(λ:平均到着率、μ:平均サービス率)であり、ρ=平均到着率×平均サービス時間とも表せる。平均待ち時間はW=ρ/(1-ρ)×Ts(Ts:平均サービス時間)、平均応答時間はこれにサービス時間自体を加えたW+Ts=Ts/(1-ρ)である。ρが1に近づくと待ち時間が急激に増大して発散する点が本質であり、例えばρが0.5から0.8に上がると平均待ち時間はTsの1倍から4倍へと一気に4倍化する。午前では「利用率と待ち時間の関係」や「平均待ち時間を一定以下に抑えられる最大の利用率」を問う計算問題が繰り返し出題されている。

情報の符号化の基礎は情報量である。生起確率pの事象がもつ情報量は-log₂p(ビット)で定義され、情報源全体の平均情報量(エントロピー)はH=-Σp×log₂pで与えられる。この理論的下限に平均符号長を近づける代表的な方式がハフマン符号であり、出現頻度の高い記号ほど短いビット列を、低い記号ほど長いビット列を割り当てる可変長符号である。どの符号語も他の符号語の先頭部分(語頭)にならないため、区切り記号なしで一意に復号できる。例えば出現確率がA:0.5、B:0.3、C:0.1、D:0.1のとき、符号長を1、2、3、3ビットと割り当てると平均符号長は0.5×1+0.3×2+0.1×3+0.1×3=1.7ビットとなり、固定長2ビットより短くなる。このほか、同一データの連続を「データ+繰返し回数」の組に置き換えるランレングス符号化があり、白黒2値画像やFAXの圧縮に用いられる。いずれも復元時に元データが完全に戻る可逆圧縮に分類される。

伝送路の誤り制御では、検出のみ可能な方式と訂正まで可能な方式を区別する。パリティチェックは検査ビットを1ビット付加し、「1」のビット数を偶数(偶数パリティ)又は奇数(奇数パリティ)にそろえる方式で、奇数個のビット誤りは検出できるが、誤り位置は特定できず訂正は不可能であり、2ビットのような偶数個の誤りは検出すらできない。垂直方向と水平方向の両方にパリティを付加する垂直水平パリティでは、1ビット誤りの位置を行と列の交点で特定でき、訂正が可能になる。CRC(巡回冗長検査)は送信データを生成多項式で割った余りを検査ビットとして付加する方式で、連続したビット誤り(バースト誤り)の検出に強く、HDLC手順やイーサネットのFCSに用いられる。ハミング符号はデータに複数の冗長ビットを付加することで2ビットの誤り検出と1ビットの誤り訂正を可能にする符号で、サーバ用メモリのECCに採用されている。各方式が「検出まで」か「訂正まで」かの対応が午前の頻出論点である。

アナログ信号のディジタル化(PCM:パルス符号変調)は、標本化→量子化→符号化の3段階で行う。標本化は一定の時間間隔で信号の値を取り出す処理であり、標本化定理(シャノンの標本化定理)により、元の信号に含まれる最高周波数の2倍以上の周波数で標本化すれば元の波形を復元できる。例えば約4kHzまでの電話品質音声は8kHzで、可聴域約20kHzを対象とする音楽CDは44.1kHzで標本化される。量子化は標本値を有限個の段階値に丸める処理で、量子化ビット数が多いほど量子化誤差は小さくなる。データ量は「標本化周波数×量子化ビット数×チャネル数×時間」で求められ、ビットからバイトへの換算(8で割る)を含む計算問題が午前で頻出する。本章全体を通じ、公式の暗記にとどまらず「nが増えたら・ρが上がったら・ビット数が増えたら値がどう動くか」という増減の方向感覚まで身に付けることが、応用情報の正答率を安定させる鍵である。