トップ その他 ITスキル体系 アルゴリズムとデータ構造

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

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

アルゴリズムとは

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

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

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

詳細

流れ図(フローチャート)

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

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

流れ図の例1

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

流れ図の例1

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

順番 設問 選択肢
m(a),n(b) [ア]a=2b(○)
[イ]2a=b(○)
[ウ]2a=3b(○)
[エ]3a=2b(○)
m(a)≠n(b) [ア]a=2b(○)
[イ]2a=b(○)
[ウ]2a=3b(○)
[エ]3a=2b(○)
m(a)<n(b) [ア]a=2b(×)
[イ]2a=b(○)
[ウ]2a=3b(×)
[エ]3a=2b(○)
n(b)-m(a)→n(b-a) [イ]2a=b(○)
[エ]3a=2b(○)
m(a)≠n(b-a) [イ]2a=b(×)
[エ]3a=2b(○)
m(a)>n(b-a) [エ]3a=2b(○)
m(a)-n(b-a)→m(2a-b) [エ]3a=2b(○)
mの値を印字 [エ]3a=2b(○)

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

流れ図の例2

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

流れ図の例2

ここで、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ビット右シフトが入ります。

探索

線形探索法

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

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

p個のデータを線形探索するときの平均探索回数はp/2です。

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

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

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

また、ブロック内の検索はm個の線形探索なのでm/2となります。

よって、平均探索回数はm/2+(n/m)/2回になります。

2分探索法

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

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

2分探索法

 この流れ図を見ても分かるように、(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が入ります。

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

戻る

スポンサーリンク

サイト内のページ

言語
C・C++ /HTML /Java /JavaScript /PHP /シェルスクリプト

開発環境
Ant /Bcc /Eclipse /gcc /gdb /g++ /JDK /JUnit /ZAP

技術・仕様
Ajax /CORBA /Java EE(旧称J2EE) /JNI

ライブラリ/Framework/CMS
jQuery /Lucene /MyBatis /RESTEasy /Spring /Struts /Seasar2 /WordPress

ITインフラ OSとミドルウェア
Linux /Windows /シェル
Apache/Tomcat /MySQL /Redis /Solr /vsftpd

ITインフラ PC 製品
ZOTAC

ITインフラ サーバー
Web公開サーバー構築

ITインフラ ネットワーク
プログラミング /機器 /構築

ITインフラ セキュリティ
公開サーバーのセキュリティ

SI
ホームページの作り方 /小さな会社のISMS

その他
IT用語 /ITスキル体系 /トレンド履歴

スポンサーリンク