「アルゴリズム」カテゴリーアーカイブ

【基本情報・応用情報】
・アルゴリズム、流れ図の考え方、表現方法を習得し、応用する。
・代表的なアルゴリズムを習得し、応用する。
・アルゴリズムの設計方法を習得し、応用する。

【ITパスポート】
・アルゴリズムと流れ図の基本的な考え方と表現方法を理解する。

アルゴリズム(概要)

情報処理技術者試験での学習内容

【基本情報・応用情報】
・アルゴリズム、流れ図の考え方、表現方法を習得し、応用する。
・代表的なアルゴリズムを習得し、応用する。
・アルゴリズムの設計方法を習得し、応用する。

【ITパスポート】
・アルゴリズムと流れ図の基本的な考え方と表現方法を理解する。

(1)アルゴリズムと流れ図 ITパスポート 基本情報 応用情報

アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。

用語例:端子、処理、定義済み処理、判断、ループ端、データ、線

(2)代表的なアルゴリズム

1.整列、併合、探索のアルゴリズム ITパスポート 基本情報  応用情報

整列のアルゴリズム、併合のアルゴリズム、探索のアルゴリズムを理解する。

用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート、線形探索法、二分探索法、ハッシュ表探索法、シノニム対策

2.再帰のアルゴリズム 基本情報  応用情報

再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。

3.グラフのアルゴリズム 基本情報 応用情報

グラフのアルゴリズムを理解する。

用語例:深さ優先探索、幅優先探索、最短経路探索

4.文字列処理のアルゴリズム 基本情報 応用情報

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

5.ファイル処理のアルゴリズム 基本情報 応用情報

バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。

6.近似アルゴリズム 応用情報

近似アルゴリズムを理解する。

用語例:近似計算

7.確率アルゴリズム 応用情報

モンテカルロ法を例として、確率アルゴリズムを理解する。

8.遺伝的アルゴリズム 応用情報

最適化問題への進化論の適用例であることを理解する。

9.自然言語処理のアルゴリズム 応用情報

情報検索、機械翻訳などを例に、自然言語処理のアルゴリズムを理解する。

10.データ圧縮のアルゴリズム 応用情報

データ圧縮のアルゴリズムを理解する。

用語例:ランレングス法。ハフマン法

11.図形に関するアルゴリズム 応用情報

3次元図形処理アルゴリズムを理解する。

用語例:Zバッファ法、スキャンライン法、レイトレーシング法

12.記憶域管理アルゴリズム 応用情報

OSのメモリ管理の方法について、空きメモリ管理のためのデータ構造、メモリの割当、開放などのアルゴリズムを理解する。

(3)アルゴリズム設計 基本情報 応用情報

アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。また。アルゴリズムの設計方法を理解する。

用語例:再帰、分割統治法

 

アルゴリズムと流れ図

この記事での学習内容 ITパスポート 基本情報 応用情報

アルゴリズムや流れ図(フローチャート)の考え方、記号、順次、判定、繰り返しなど、処理手順の表現方法を理解し、流れ図を描く方法を理解する。

用語例:端子、処理、定義済み処理、判断、ループ端、データ、線

アルゴリズム

アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。

同じ結果を出すための処理であっても、より整理されたアルゴリズムで行うほうが、効率よく結果を得ることが出来ます。プログラムを作るときは、特にどんなアルゴリズムを使うかが重要になります。

流れ図

流れ図は「フローチャート」ともいい、処理のアルゴリズムを視覚的に表現できる図解法です。プログラムの設計によく用いられます。

流れ図は以下の記号類を使って、上から下に流れていくように描きます。

アルゴリズムの基本構造

アルゴリズムの基本構造には、順次型、分岐型、反復型があります。

  • 順次型: 順番に処理を実行していく。

    流れ図では、上から順に、四角系の中に処理を描いていきます。

  • 分岐型: 条件によって異なる処理を実行する。

    流れ図では、ひし形の中に分岐の条件を書き、矢印を分岐させます。

  • 反復型: 繰り返しを終える条件が満たされるまで、同じ処理を繰り返す。

    繰り返しを終える条件を、角を切り取った四角形(=ループ端)の中に描き、繰り返す処理を2つのループ端の間に描いていきます。


    繰り返しの図形を使わずに、右記のように分岐のひし形を使って描く方法もあります。

前判定型と後判定型の繰り返し

反復型には、先に繰り返しを行うかどうかの条件判定をしてから、一通りの処理を行う「前判定型」と、処理を一通り実行した後で、終了するかどうかの条件判定を行う「後判定型」の2種類があります。

反復処理の「1回め」をどのように扱うかで、前判定型と後判定型を使い分けます。

前判定型では、1回目の条件判定で終了条件を満たすと、繰り返しの処理は1回も実行されません。
対して後判定型では繰り返し処理の後で終了条件を判定するので、少なくとも1回は処理が実行されます。

流れ図を使った例

二人で行うゲームを例に、流れ図を見てみましょう。

互いにじゃんけんをし、勝ったほうがピコピコハンマーで相手の頭を叩きます。同時に、負けた方はヘルメットで防御します。
ハンマーが頭にヒットすれば叩いた方の勝ちとなる、というゲームです。(いわゆる「たたいてかぶってジャンケンポン」)

 

整列-代表的なアルゴリズム1

この記事での学習内容 ITパスポート 基本情報 応用情報

整列のアルゴリズムを理解する。

用語例:選択ソート、バブルソート、マージソート、挿入ソート、シェルソート、クイックソート、ヒープソート

整列(ソート)

整列とは、データを大きい順(降順)または小さい順(昇順)になるように並び替えることです。

 昇順降順
数値「32514」1234554321
英字「BDAEC」ABCDEEDCBA
かな「いあえおう」あいうえおおえういあ

数値データは値の大小順に整列され、文字データは文字コードの値の大小順で整列されます。
英字はアルファベット順に、ひらがな、カタカナは50音順に文字コードが割り振られているため、英字同士はアルファベット順、ひらがな同士、カタカナ同士は50音順で並び替えが可能になります。

代表的なソートアルゴリズムと計算量・速度の比較
名称オーダー(計算量)処理速度備考
バブルソートO(n2)遅い処理が単純で実装が容易。
選択ソートO(n2)遅い処理が単純で実装が容易。
挿入ソートO(n2)遅い処理が単純で実装が容易。
O(n2) のアルゴリズムの中では高速。
シェルソートO(n1.2)~O(n2)程度やや遅い挿入ソートの改良版だが、場合によっては挿入ソートと速度が変わらない。
マージソートO(n log2n)高速「再帰」の概念の理解が必要。
クイックソートO(n log2n)高速「再帰」の概念の理解が必要。
ヒープソートO(n log2n)やや高速「ヒープ木」の概念の理解が必要。

バブルソート

代表的な整列のアルゴリズムに、バブルソートがあります。バブルソートは一つとなりと比べては入れ替える、という処理を繰り返していく方法です。
隣同士のうち、大きい方が前に並ぶように入れ替えていくと、結果的に全体が降順で並びます。逆に小さいほうが前に並ぶようにすると昇順となります。

例:「1・5・7・3・9」の5枚のカードをバブルソートで降順に並び替える。

  1. 要素[1]と[2]を比較して、大きい方が前になるように入れ替える。
  2. 続いて[2]と[3]、[3]と[4]、[4]と[5]の順に比較と入れ替えを行う。
    この時点で、要素[5]が最小値になるので、要素[5]の位置が確定する。
  3. 要素[1]~[4]について、同様に比較と入れ替えを繰り返し、各要素の位置を確定する。
バブルソートの計算量

n個の要素をバブルソートで整列する時の比較の回数は、 ( n ( n - 1 ) ) ÷ 2 であり、n の2乗に比例します。。
オーダ記号で表すと、O(n2) となります。

選択ソート

選択ソートは、最小値の要素を選択して、先頭の要素と置き換える整列アルゴリズムで、基本選択法ともいいます。
処理効率は、バブルソートと変わらず、計算量はO(n2) となります。

例:「1・5・7・3・9」の5枚のカードを選択ソートで昇順に並び替える。

  1. 要素[1]~[5]の値を調べて、最小値を求める。
  2. 1.で求めた最小値を先頭の要素と交換する。
  3. 残りの要素について、1と2を繰り返す。

挿入ソート

挿入ソートは、前の方の整列済みの並びの途中へ、直後の要素を挿入する整列アルゴリズムで、基本挿入法ともいいます。
計算量はO(n2) となります。

例:「1・5・7・3・9」の5枚のカードを挿入ソートで昇順に並び替える。

  1. 先頭の要素を1要素だけの整列済みの並びと見立てる。
  2. 整列済みの並びの要素と、その直後の要素を比較して、バブルソートと同じ要領で並び替えを行う。
  3. 最後の要素を処理するまで、2を繰り返す。

マージソート

マージソートは、並びを2等分しながら、分割された部分同士を併合(マージ)することによって、全体を整列させるアルゴリズムです。

例:「2・7・5・3・8・1・4・6」の8枚のカードをマージソートで昇順に並び替える。

  1. 並びを2等分することを、整列済みの部分並びが見つかるまで反復する。(要素が1つになれば整列済みとみなすので、反復は必ず終了する。)
  2. 整列済みの部分並び同士を、整列状態を保つように併合して、1つの部分並びにする。
  3. 全体が1つの部分並びになるまで、2を反復する。

シェルソート

シェルソートは、シェル氏によって考案された挿入ソートの改良版の整列アルゴリズムです。

  1. 適当な間隔を決めて、等間隔の飛び飛びの要素で作った部分的な並びに対して挿入ソートを適用する。
  2. 間隔を狭めながら、間隔が1になるまで1を繰り返す。

例:「2・7・5・3・8・1・4・6」の8枚のカードをシェルソートで昇順に並び替える。

挿入ソートは、元々の並びが整列状態に近いほど高速になる性質があるため、間隔を空けて部分的な並びを作って徐々に整列させることで速度の向上を図っています。

クイックソート

クイックソートはその名の通り、特に高速な整列アルゴリズムです。

  1. 適当な基準値を定めて、その値より小さい要素を前の方に移し、その値以上の要素を後の方へ移す。
  2. 分割したそれぞれのグループへ、1の処理を反復して、全てのグループに属する要素数が1になるまで繰り返す。

例:「9・2・7・5・3・8・1・4・6」の9枚のカードをクイックソートで昇順に並び替える。

反復する毎に、分割されたグループの数は2倍、4倍、8倍というペースで増えていくので、各グループに含まれる要素の数は急激に減っていきます。
基準値と要素の値を比較する回数が急速に減っていくことが、クイックソートが特に高速である理由です。

ヒープソート

ヒープソートは、ヒープを経由する整列アルゴリズムです。

ヒープは「小さい山」という意味の言葉であり、親の値が必ず子の値以上であることを保つ二分木です。

  1. 要素の並びを元にして、ヒープを構築します。子の処理には、木構造アルゴリズムの一種である、ヒープ構築アルゴリズムを用います。
  2. 根に当たる要素を取り出して、並びの端へ移します。
  3. ヒープに残った要素に対して、ヒープ再構築アルゴリズムを適用します。
  4. 2と3をヒープの要素がなくなるまで繰り返します。

例:「2・7・5・3・1・4・6」の7枚のカードをヒープソートで降順に並び替える。

二分木は木の階層ごとに、部分木の数が2倍、4倍、8倍と増えていきます。値の大小比較の回数は2つの部分木の根を比較するだけなので、ヒープソートは特に高速とされています。

 

探索、併合、再帰-代表的なアルゴリズム2

この記事での学習内容 ITパスポート 基本情報 応用情報

探索、併合のアルゴリズムを理解する。
再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。

用語例:線形探索法、二分探索法、ハッシュ表探索法、シノニム対策

探索

「探索」とは配列などに格納されたデータの集まりから、特定のデータを探すことです。その値が見つかる場合と、見つからない場合があり、複数ある場合には最初の一つを見つければ良い場合と、全てを見つける必要がある場合があります。

つまり、探索の結果も見つかったかどうかだけではなく、何番目に見つかったか、いくつあったか、という情報を帰す場合があります。

線形探索法(リニアサーチ)

線形探索法とは、配列の先頭から1つずつ調べてゆき、求めるデータが見つかるか、又は配列の最後まで探し終わったとき探索を終了する方法です。

以下に、線形探索法の場合の流れ図を示します。ここでは、4つの数が入った配列の中から、「5」を探すものとします。

探索する数「5」を変数 x とし、探索対象の数を n [ i ] と表します。
先頭の n [ i ] から順に x と比較していき、同じものが見つかったら、その添字 i を表示して探索を終了、最後まで探して見つからなかった場合は、「無し」と表示して終了します。

なお、線形探索法を行なった場合の探索回数は以下の通りとなり、オーダ記号で表すと O(n) となります。(データは n 個とする)

  • 最小探索回数: 1回
  • 最大探索回数: n回
  • 平均探索回数: (n+1)÷2回

番兵を使った線形探索法

線形探索をより簡単にするために、配列の最後に「番兵」と呼ばれるデータを追加する方法があります。

探すデータと同じ値を、配列の最後尾の次に追加しておくことで、反復の終了条件として、添字の範囲を毎回チェックする必要がなくなります。

但し、配列を拡張できないケースではこの方法は使用できません。

二分探索法

二分探索法は、整列済みのデータの並びを二等分しながら、目的のデータを探す探索アルゴリズムです。

例えば、昇順に整列済みの配列であれば、以下のような流れとなります。

  1. 並び全体の中央のデータと目的のデータを比較する。一致すれば終了。
  2. 目的のデータが中央のデータより小さければ、前半の部分並びにを対象にして、大きければ後半の部分並びを対象にして、1を繰り返す。
  3. 最終的に部分並びの要素が1つになったら、見つからなかったことになる。

なお、二分探索法を行なった場合の探索回数は以下の通りとなり、オーダ記号で表すと O(log2n) となります。(データは n 個とする)

  • 最小探索回数: 1回
  • 最大探索回数: ( log2n)+1回
  • 平均探索回数:  log2n 回

例えば、要素の数が65,536個(216)であった場合、線形探索法なら、最大で65,536回、平均でも32,768回かかります。
対して、二分探索法の場合、比較を行うたびに、部分並びの数が、216、215、214、・・・22、21、20 と減っていき、最大でも17回で済みますので、二分探索法の方がはるかに高速なアルゴリズムです。

ハッシュ表探索

ハッシュ表探索法は、データの格納位置をデータの値から決めることで、目的のデータを直接得られる方法です。
ハッシュ表という配列の複数の要素に、探索対象の部分並びを所属させておき、目的のデータの値に対してある種の計算を行い、一つの部分並びだけを探索対象として選択する探索アルゴリズムです。

例えば、目的のデータを100で割った余りは、必ず0~99の数になります。この値を100個の要素の配列の索引として、一つの部分並びを選択することが出来ます。
この例の「目的のデータを100で割った余り」といったような、目的のデータを範囲内の値に換算する関数のことを「ハッシュ関数」といいます。

ハッシュ表探索では、最初の1回目の検索で多くの部分並びの中から1つを選択することで、初めの時期の検索回数を減らしています。

ハッシュ関数と衝突

ハッシュ関数を適用した結果、値が重複してしまうことを衝突(シノニム)といいます。

ハッシュ表を使う場合、ハッシュ関数を検討する際に極力シノニムが発生しないようにすることも重要ですが、余りハッシュ表を大きくすると無駄も多いので、シノニム発生時の対処法もあわせて検討しておく必要があります。
例えば、データの件数が1万件だからといって、1万件のハッシュ表を作るのでは、メモリをムダに消費してしまいます。

シノニム対策としては、以下のようなパターンが主流です。

  • ハッシュ表の隣接する要素を使う。
  • シノニム用の領域を別途用意する。

併合のアルゴリズム

併合のアルゴリズムは、二つの整列済みのデータの並びを一つの整列されたデータの並びにするアルゴリズムです。

  1. 二つの配列のそれぞれ先頭の要素を比較して、値の小さい要素を併合先の配列の先頭に移す。
  2. 残りの配列について、それぞれの配列の最後の要素を移し終わるまで1の処理を繰り返す。

再帰のアルゴリズム(リカーシブ)

再帰とは、定義自身の一部にその定義が含まれるという性質です。

再帰のアルゴリズムは、反復を含むアルゴリズムと似ていますが、それよりも簡潔になります。

例えば、1からnまでの自然数の和を表す関数を f( n ) とします。
・n=1のときは、f(1) は値として「1」を返す。
・n>1のときは、f( n )は値として「n+f( n-1 )」を返す。

この関数を使って、1から4までの和を計算する場合、以下のように再帰が進行していきます。

f(4) = 4+f(3)
 =4+3+f(2)
 =4+3+2+f(1)
 =4+3+2+1
 =10

再帰のアルゴリズムは、これまでに紹介した整列や探索のアルゴリズム(マージソート、クイックソート、二分探索法)でも活用されているアルゴリズムです。

グラフのアルゴリズム-代表的なアルゴリズム3

この記事での学習内容 基本情報 応用情報

グラフのアルゴリズムを理解する。

用語例:深さ優先探索、幅優先探索、最短経路探索

グラフのアルゴリズム

グラフは節(ノード)とそれらを連結する結線(リンク)で結ばれた一つの図です。通信網、木構造、あるいは流れ図がその例です。(木構造の場合は、結線のことを枝とも呼ぶ)

これらのグラフを扱うアルゴリズムをグラフのアルゴリズムといいます。

木の巡回法(再掲)

木構造からデータを探して読み出すことを「木の巡回」といいます。二分木の巡回法には幅優先探索と深さ優先探索があります。

木の幅優先探索

幅優先探索は、階層が浅いデータを優先して検索する方法です。

幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、1階層目の節や葉のデータを左から右へと順番に読み出していきます。1階層目のデータが検索したデータでない場合は、次は2階層目と進んでいく、という方法です。

木の深さ優先探索

深さ優先探索は、左部分木を優先して、階層が下のデータを先に読み出す方法です。

葉以外の節のデータと、葉のデータを読み出す順番の違いにより、先行順探索、中間順探索、後行順探索の3種類があります。

先行順探索

先行順は、節、左部分木、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると、最初の節である根のデータ1を読み出し、次に左部分木の節のデータ2を読み出します。
その次は2階層目の左部分木のデータ3を読み出します。
3階層目はないので、2階層目の右部分木のデータ4を読み出します。

中間順探索

中間順は、左部分木、節、右部分木の順番で読み出す方法です。

右の図を例にとって説明すると。根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次に、上の階層に戻ってデータ2を読み出します。
その次に2階層目の右部分木のデータ3を読み出します。
2階層目の読み出しが終わると、次は根のデータ4を読み出します。

後行順探索

後行順は、左部分木、右部分木、節の順番で読み出す方法です。

右の図を例にとって説明すると、根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。
次は2階層目の右部分木のデータ2を読み出します。
その次は、上の階層に戻ってデータ3を読み出します。
その次は、1階層目の右部分木ですが、そこからは左部分木が出ているので、左部分木のデータ4を読み出します。

最短経路探索

最短経路とは、グラフのある出発点の節から終着点の節へ到達するのに、結線ごとに要する時間や距離の合計が最短である結線の並びです。この最短経路をたどることを「最短経路探索」といいます。
結線ごとに要する時間や距離を総称して「コスト」といいます。

例:ダイクストラのアルゴリズム

  1. 出発点から各説へのコストの表は、出発点の節だけゼロとし、それ以外の節へのコストは初期値として無限大とする。
  2. 出発点の節から、結線の一つをたどって、節のデータを調べる。
    1. その節へのコストの記録が、今回の経路のコストより大きいなら、今回の経路のほうが短いので、今回の経路のコストを記録し、直前の節の記号をその節に関するデータとして記録する。(その節へのコストが初期値の無限大だったのなら必ずこちらの処理)
    2. その節へのコストの記録が、今回の経路のコスト以下なら、今回の結線は最短経路に含まれないので、それ以降の処理対象から除外する印を記録する。
  3. 以上の処理を、処理していない結線について反復する。
  4. すべての処理が終わったら、終着点の節から最短のコストを回答する。また、直前の節を次々と逆行して、出発点から終着点までの節の順序を経路として回答する。

 

文字列処理のアルゴリズム-代表的なアルゴリズム4

この記事での学習内容 基本情報 応用情報

文字列処理のアルゴリズムを理解する。

用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)

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

文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。

  • 連結: 一つの文字列の後へ別の文字列を追加して、一つの文字列にします。
  • 挿入: 文字列の途中に別の文字列を挿入して、一つの文字列にします。
  • 削除: 文字列の一部の文字を取り除いて、残りを一連の文字列にします。
  • 照合: 文字列が別の文字列の中に含まれるか、有無を調べて位置を特定します。

順次探索法

  1. 対象の文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。
    すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。
  2. 対象の文字列の1文字後ろから1の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。

ボイヤ・ムーア法(BM法)

ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。

  1. 特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の2表を作成する。
  2. 対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。
    一致したら全体の処理を終了して、対象の文字列の位置を返す。
  3. 一致しなかったら、比較時に得られた情報と1で作った表を元にして、文字をスキップし、2の処理に戻る。

 

ファイル処理のアルゴリズム-代表的なアルゴリズム5

この記事での学習内容 基本情報 応用情報

バッチ処理などで使用される整列処理、併合処理、コントロールブレイク処理、編集処理のアルゴリズムを理解する。

ファイル処理のアルゴリズム

ファイル処理とは、入力装置や外部記憶装置から読み取ったファイルを処理することです。処理対象のデータが主記憶装置の中にないため、以下のような手順が基本となります。

  1. 前処理: ファイルを開き、内容を主記憶装置の中に展開します。
  2. 主処理: 開いたファイルに対して、1レコードずつ所定の処理を行います。
  3. 後処理: ファイルを閉じます。

なお、ここでいうファイルは以下の定義となります。

  • レコード: 型の異なる幾つかの項目(=フィールド)を持つ
  • ファイル: 同じフィールドを持つレコードの集まり

ファイルの性質として、データ件数が膨大になることがあるため、ハードディスクなどの外部記憶装置に作業ファイルを作成し、中間結果を一時退避しながら処理をすすめることもある。その場合、外部記憶装置に十分な空き容量が必要となる。

ファイルの併合処理

ファイルの併合処理は、二つの整列済みのレコードの並びで構成されるファイルを、一つの整列されたレコードのファイルにする処理です。

例:ファイルAとBから、ファイルCを作成する

  1. 前処理: ファイルA、B、Cをそれぞれ開く。
  2. 主処理: ファイルA、Bを1レコードずつ読み込み、値の小さい方のレコードをファイルCに出力し、出力した方のファイルの次のレコードを読み込む。
    これを両ファイルの終端まで繰り返す。
  3. 後処理: ファイルA、B、Cをそれぞれ閉じる。

コントロールブレイク処理

コントロールブレイクとは、同じキー値を持つレコード軍の切れ目のことです。

コントロールブレイク処理とは、コントロールブレイクに出会ったらそのレコード群の処理を終了し、複数のレコード群の処理を反復することです。レコード群の中のレコードごとの処理の反復とあわせて、二重の反復になります。

例:社員の給与の部署ごとの合計

  1. 社員の給与一覧ファイルをあらかじめ部署で整列
  2. 部署が同じである間、社員毎の給与を計算用変数に加算していく。
  3. 違い部署コードが出現したら「コントロールブレイク」
    部署名と計算用変数の値を中間ファイルに出力し、計算用変数0で初期化。
  4. 2と3をファイルの終端まで繰り返す。
  5. ファイル終端まで来たら、部署名と計算用変数の値を中間ファイルに出力。中間ファイルの内容を処理の最終結果として書き出す。

ファイルの編集処理

ファイルの編集処理は、既存のファイルのデータを修正する処理です。

  1. 前処理: マスターファイルM、トランザクションファイルT、新マスターファイルNを開く。
  2. 主処理: ファイルMとファイルTからから1レコードずつ読み込み、キー値を比較して以下の処理を行う。これをファイル終端まで繰り返す。
    1. Tのキー値=Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルMとファイルTの次のレコードを読み込む。(データの更新)
    2. Tのキー値>Mのキー値なら、ファイルMのレコードをファイルNに出力し、ファイルMの次のレコードを読み込む。
    3. Tのキー値<Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルTの次のレコードを読み込む。(レコードの追加)
  3. 後処理: ファイルM、ファイルT、ファイルNを閉じる。

アルゴリズム設計

この記事での学習内容 基本情報 応用情報

アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。また。アルゴリズムの設計方法を理解する。

用語例:再帰、分割統治法

アルゴリズム設計

アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。アルゴリズムを考える、設計する目的は、単に問題を解く方法を見つけるだけではなく、より効率的に、より速く、より簡単に問題を解くアルゴリズムを探す事が重要です。

同じ結果を出すための処理であっても、そのアルゴリズムが異なると、処理にかかる時間や、必要となるメモリの容量などが異なってきます。効率の良いアルゴリズムほど、処理時間が短くなり、メモリの消費量が少なく済むものなのです。

アルゴリズムの表現

プログラムを設計するときには、アルゴリズムを何らかの形式で表現します。

アルゴリズムの表現には、流れ図(フローチャート)、擬似言語、決定表(デシジョンテーブル)などの表現があります。

擬似言語

擬似言語は、人間が用いる自然言語とプログラム言語を混合した言語です。

アルゴリズムをできるだけ人間向きに自然言語で表現しつつ、反復や選択のように微妙な部分にプログラム言語を混用したりします。

プログラム言語と同様にテキストエディタで描くことが出来、図形を用いた表現に比べて修正が容易なのが特徴です。

テキストのみで表現した例

if a[mi] が a[i] より小なら then
   a[mi] と a[i] の値を交換する

図形処理の発達に伴い、情報処理技術者試験の分野では、以下のような簡易な図記号を混用したものを擬似言語と称しています。
(実際に情報処理技術者試験で使われたものを紹介します。)

擬似言語の仕様の例
実際に出題された擬似言語の記述例

決定表(デシジョンテーブル)

決定表(デシジョンテーブル)は、条件とその条件に対する処理の関係を4つの部分からなる表にして表現する技法です。

  1. 条件表題欄: 問題を処理するための条件を表します。
  2. 行動表題欄: 条件によって取りうる行動を表します。
  3. 条件記入欄: 条件表題欄の各条件について、当てはまる場合は[Y]、当てはまらない場合は[N]と記載します。条件判断を必要としない場合は[-]と記載します。
  4. 行動記入欄: 行動表題欄の各行動について、当てはまる場合に[X]と記載します。当てはまらない場合は空欄か[-]と記載します。

大きなプログラムの場合、「行動」の単位で「サブルーチン」化することがよく行われています。(=後述:分割統治法)

また、決定表を作成するときは、取りうる条件の組み合わせを網羅し、なおかつ全てのパターンに対して、必要な処理が行われるように設計することが重要です。

分割統治法

分割統治法とは、大きな問題を小さな問題に分割して、それぞれの問題ごとに解決に集中する方法です。

再帰のアルゴリズム、モジュール分割、オブジェクト指向設計などが分割統治法の具体的な例です。

また、ソートのアルゴリズムの中でも、マージソートやクイックソートは分割統治法に基づいて設計がなされています。

例えば、1からnまでの自然数の和を求めるアルゴリズムの場合、分割統治法を使わない場合と使った場合とでは、以下のように違った流れ図となります。