アルゴリズムとデータ構造（IT、コンピューター分野）

一般的じゃなくて、IT、コンピューター分野。アルゴリズムとデータ構造について、流れ図（フローチャート）からわかりやすく！を心がけて説明していきます。

▲記事トップへ

アルゴリズムとは

アルゴリズムという言葉は、ITやコンピューターに限らず、広くさまざまな場面で使われています。 アルゴリズムとは、一般的には「問題を解決する手順」という説明になります。

ITやコンピューター分野におけるアルゴリズムは、コンピュータで問題を処理するためにプログラムとして表現するのに向いている解決法です。

例をあげると、グラフ理論、オペレーションズリサーチ、数値計算、データ構造の操作、整列、数式処理、言語処理などです。

詳細

流れ図（フローチャート）

アルゴリズムといえば、まずは流れ図（フローチャート）ですね。流れ図について説明していきます。

流れ図は、変数に実際の値を代入して処理後の値を確かめるのに用います。

流れ図の例１

次の流れ図において、
　　　　①→②→③→⑤→②→③→④→②→⑥
の順に実行させるために、①においてmとnに与えるべき初期値aとbの関係はどれかを確かめることにします。 a、bはともに正の整数です。

初期値の候補
[ア]a=2b、[イ]2a=b、[ウ]2a=3b、[エ]3a=2b

順番	設問	選択肢
①	m(a),n(b)	[ア]a=2b(○) [イ]2a=b(○) [ウ]2a=3b(○) [エ]3a=2b(○)
②	ｍ(a)≠ｎ(b)	[ア]a=2b(○) [イ]2a=b(○) [ウ]2a=3b(○) [エ]3a=2b(○)
③	ｍ(a)＜ｎ(b)	[ア]a=2b(×) [イ]2a=b(○) [ウ]2a=3b(×) [エ]3a=2b(○)
⑤	ｎ(b)－ｍ(a)→ｎ(b－a)	[イ]2a=b(○) [エ]3a=2b(○)
②	ｍ(a)≠ｎ(b－a)	[イ]2a=b(×) [エ]3a=2b(○)
③	ｍ(a)＞ｎ(b－a)	[エ]3a=2b(○)
④	m(a)－ｎ(b－a)→m(2a－b)	[エ]3a=2b(○)
⑥	mの値を印字	[エ]3a=2b(○)

[エ]3a=2bが①→②→③→⑤→②→③→④→②→⑥の順に実行させる初期値であることが分かりました。

流れ図の例２

次の流れ図は、シフト演算と加算の繰り返しによって2進数の乗算を行う手順を表したものです。 ここで、乗算と被乗算は符号なしの16ビットで表されます。 X、Y、Zは32ビットのレジスタであり、けた送りには論理シフトを用いる。

ここで、a、bに着目してみます。 Xは被乗数、Yは乗数、Zは乗算結果であることに注意して流れ図を見ます。

1. a
   　乗算Yの最下位ビットが1であれば、加算「Z+Y→Z」が必要です。
   　したがって、空欄aには、Yの最下位ビットが入ります。
2. b
   　乗数Yの1つ上位のけたの乗算を行うために、被乗数Xを1ビット左シフト、乗数Yを1ビット右シフトします。
   　したがって、空欄bには、Yを1ビット左シフト、Yを1ビット右シフトが入ります。

探索

線形探索法

線形探索は、配列の先頭から順番に目的のデータが見つかるまで探索する方法です。

線形探索法の平均探索回数

ｐ個のデータを線形探索するときの平均探索回数はｐ／２です。

たとえば、相異なるｎ個のデータが昇順に整列された表があり、 この表を１ブロックm個に分割し、各ブロックの最後尾のデータだけ線形探索することによって、 目的のデータの存在するブロックを探し出し、 次に該当ブロック内を線形探索して目的のデータを探し出すという探索のとき、 このときの平均探索回数は次のようになります。

なお、ｍ＜ｎとし、目的のデータは必ず表の中に存在するものとします。

ｎをｍ個づつブロックに分けて、その最後尾だけを探索することは ブロック数分の線形探索を行うことなので検索回数は(ｎ／m)／２回となります。

また、ブロック内の検索はｍ個の線形探索なのでｍ／２となります。

よって、平均探索回数はｍ／２＋(ｎ／m)／２回になります。

2分探索法

2分探索は、探索されるデータが昇順、または降順に整列している場合に使用できます。 探索データの中央の値と目的のデータを比較し、一致しなければ、中央の値の上下どちらにあるかを判断し、 探索データを半分に絞り込み、比較を続けていく方法です。

たとえば、昇順に整列済の配列要素A(1)、A(2)、…A(n)から、A(m)＝kとなる配列要素A(m)の添字mを ２分探索法によって見つける処理を図に示すと次のようになります。

　この流れ図を見ても分かるように、(x＋y)／2→mで中央値を求めて解の選択の幅を狭めていることが分かります。 なお、終了時点でm＝0の場合、A(m)＝kとなる要素は存在しません。

データ構造

スタックとキュー

キューとは、1次元配列に格納されたデータの一方からデータを格納し、 他方の端からデータを取り出すデータ構造のことです。 このようなデータの出し入れをFIFO(First-In First-Out：先入れ先出し)と呼びます。

また、スタックとは、1次元配列に格納された後から入れたデータを 先に取り出すデータ構造のことをいいます。 このようなデータの出し入れをLIFO(Last-In First-Out：後入れ先出し)と呼びます。

なお、

　データyをスタックに挿入することをpush(y),
　スタックからデータを取り出すことをpop(),
　データyをキューに挿入することをenq(y),
　キューからデータを取り出すことをdeq(),

とそれぞれ表わします。

たとえば、

push(a)
push(b)
enq(pop())
enq(c)
push(d)
push(deq())
x←pop()

としたとき、次のような処理がおこなわれます。

よって、変数xにはbが入ります。

知識の幅を広げるための参考

• ITスキル体系

  ITスキルを体系的に把握するコンテンツとしてzealseedsのITスキル体系をまとめています。

戻る