sigma-se

目的

この記事では、応用情報技術者試験の出題分野であるアルゴリズムに関する覚書きを列挙する。

フローチャート

フローチャート（流れ図）
基本3構造と呼ばれる、順次、選択、繰返しを用いて、プログラムの処理の流れを図式化したもの。
順次は、上から下へ順番に命令を実行する処理を指す。
選択は、if文やswitch文等の分岐処理を指す。
繰返しは、for文やwhile文等のループ処理を指す。

探索アルゴリズム

データ群から目的のデータを探すためのアルゴリズムで次の代表的なアルゴリズムがある。

※ \(n\) は、データの個数を表すものとする。
計算量については、
応用情報技術 - 基礎覚書き：情報技術に関する理論 > 計算量を参照。

線形探索
先頭から順番に一つずつ評価して探索するアルゴリズム。

計算量は、\(O\ (n)\) となる。
2分探索
事前にデータを整列させた探索されるデータに対して中間データの比較を繰返して探索するアルゴリズム。

計算量は、\(O\ (log\ n)\) となる。
ハッシュ表探索
ハッシュ関数を用いて探索するアルゴリズム。
探索されるデータのハッシュテーブルに対して、探索するデータのハッシュ値でデータ（値）を逆引きし探索する。

データ数に関係なく \(1\) 回の探索となるため、計算量は、\(O\ (1)\) となる。
シノニム（synonym）
ハッシュテーブルにおいて、同じハッシュ値（同じデータ）を持つデータ群または、その状態を指し、衝突とも表現される。

また、上記ハッシュ表探索でもシノニムデータを考慮しないため、ハッシュ値の衝突が起こりうる。
チェイン法（分離連鎖法）
シノニム問題の解決法の一つ。

ハッシュ値にシノニム（衝突）が発生した場合、個々のデータを連結リスト（互いに参照できる仕組みを持つ）で繋ぎ、衝突を解決する方法のこと。
オープンアドレス法（ハッシュ法、閉番地法）
シノニム問題の解決法の一つ。

ハッシュ値にシノニム（衝突）が発生した場合、再ハッシュ（別バケットにデータを格納する）の繰返しにより、衝突を解決する方法のこと。

整列アルゴリズム

データを昇順または、降順にソートするためのアルゴリズムで次の代表的なアルゴリズムがある。

※ \(n\) は、データの個数を表すものとする。

バブルソート
隣合うデータを大小比較し、ソート順と逆ならば順番を入替えてソートするアルゴリズム。

すべての隣合うデータに対して大小比較を繰返すため、計算量は、\(O\ (n^2)\) となる。
挿入ソート
整列済のデータに対して線形探索で挿入位置を決め、データを挿入してソートするアルゴリズム。

線形探索分の挿入有無を評価するので、計算量は、\(O\ (n^2)\) となる。
選択ソート
未整列のデータ群からソート順に応じた最大値（最小値）を検索（特定）後、整列済データに分類し、ソートするアルゴリズム。

最大値（最小値）の探索をデータ数分行うため、計算量は、\(O\ (n^2)\) となる。
クイックソート
中間的な基準値を決め、大小2つの部分列に分け、さらにそれぞれで同じ操作を繰返し行いソートするアルゴリズム。

部分列の分解を繰返し結果を統合する分割統治法を利用しており、計算量は、\(O\ (n\ log\ n)\) となる。
シェルソート
挿入ソートの改良版。
一定間隔おきのデータを対象にした部分列をそれぞれ挿入ソートで整列させ、その間隔が1になるまで狭めてソートするアルゴリズム。

計算量は \(O\ (n\ log\ n)\) となる。
ヒープソート
選択ソートの改良版。
未整列データでヒープを構成することによって、最大値（最小値）となる根を整列済データとし、未整列データがなくなるまで繰返しソートするアルゴリズム。

計算量は、\(O\ (n\ log\ n)\) となる。

※ ヒープについては、応用情報技術 - 基礎覚書き：データ構造 > ヒープを参照。
マージソート
まず、未整列データを前後2つのグループに分け、この操作をデータ数が \(1\) になるまで再帰的に繰返す。
次に、データ数が小さい方から順に前後2つのグループをソートしつつ併合（マージ）する操作を分割したグループ分、繰返してソートするアルゴリズム。

クイックソートと同じ分割統治法を利用しており、計算量は、\(O\ (n\ log\ n)\) となる。
ただし、マージに伴うメモリ消費が多い。

再帰アルゴリズム

再帰アルゴリズム
その名の通り、再帰（自分自信を呼出す）するアルゴリズム。
- 例：\(0\) を含む自然数 \(n\) に対して、\(n\) の階乗を返す関数 \(fact\ (n)\) を再帰的に定義する。
※ Javaで書いた場合
```
if (n = 0) {
    return 1
} else {
    return n*fact(n-1)
}
```

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

文字列処理のアルゴリズム
文字列探索後に挿入、削除、置換、連結等を行うアルゴリズム。
文字列探索のアルゴリズムについて、次の代表的な方法がある。
順次探索法
下記（＊1）、（＊2）の要領で先頭から探索する文字列を一つずつ探す文字列照合アルゴリズム。

単純に先頭から順に探索をかけるため（一度評価した探索も再度を実行する）、非常に遅い。

以下（＊1）、（＊2）を探索される文字列がなくなるまで繰返す。
- （＊1）探索
  探索される文字列（初回は先頭文字）と探索する文字列（初回は先頭文字）を1文字照合する。
- （＊2）照合判断
  - 照合一致の場合、探索される文字列の対象を次の文字列とし、（＊1）を実行する。
  - 照合不一致の場合、探索する文字列の対象を次の文字列とし、（＊1）を実行する。
BM法（ボイヤームーア法）
下記（＊1）～（＊3）の要領で探索する文字列の末尾から先頭へ照合し、照合不一致の場合は不要な評価をスキップする高速な文字列照合アルゴリズム。
- （＊1）事前準備
  下記（a）、（b）の対応表（記憶領域）を準備する。
  - （a）探索する文字列がどの文字で探索される文字列の何文字目に出現するか。
  - （b）照合一致した文字列のパターンとその照合結果によってスキップできる文字数。
以降、（＊2）、（＊3）を探索される文字列がなくなるまで繰返す。
- （＊2）探索
  - 初回の場合
    探索される先頭文字と探索する文字列の先頭文字が一致するように2行に並べた状態で探索する文字列の末尾と探索される文字列と同じ列（位置）にある文字を1文字照合する。
  - 2回目以降の場合
    探索する文字列の末尾と探索される文字列と同じ列（位置）にある文字を1文字照合する。
- （＊3）照合判断
  - 照合一致の場合
    一致した時の状態を（a）、（b）に保持した上で、照合一致した位置まで探索する文字列の位置を進めて、（＊2）を実行する。
  - 照合不一致の場合
    探索する文字列の対象を先頭へに1文字ずらし、（＊2）を実行する。

上記以外にも代表的なアルゴリズムとして、メモリ管理、データ圧縮、グラフ、近似/統計確率、図形描画、遺伝的なアルゴリズムなどがある。

参考文献

瀬戸美月（\(2020\)）『徹底攻略応用情報技術者教科書』株式会社インプレス

SIGMA-SE Tech Blog