[ホームへ戻る]


(基本情報技術者 Web学習室)
ここでは、(アルゴリズムの基本)について学習します。


NO 項目 学習内容
1 アルゴリズム コンピュータでプログラムを記述する際に、どのような手順で行うか考え、整理することを一般的に「アルゴリズム」と言います。
通常、アルゴリズムには、以下のものがあります。
変数
データを格納するみのです。変数には基本的に自由な名前が付けられます。
●値の代入
変数には、値を代入することができます。例えば、100→A。これは、Aという変数に100という値を代入しています。
変数の代入
変数には、他の変数の値を代入することができます。例えば、A→Z。これは、Aという変数の値をZという変数に代入しています。ここで注意点としては、Aの変数の内容は変化しません。
演算結果の代入
変数には、演算結果を代入できます。例えば、A+50→B。これは、Aの値に50を加算してBへ代入しています。
変数の型
変数には、取り扱うデータによって以下の3種類があります。
・整数型 整数を格納出来る変数を言う。
・実数型 実数を格納出来る変数を言う。
・文字型 文字や文字列(文字が複数集まったもの)を格納出来る変数を言う。
流れ図
アルゴリズムでは、流れ図で表現する場合が多いようです。基本的に流れ図は、
順次構造」 命令を順番に記述する。
判断構造」 命令を条件によって分岐する。
反復構造」 命令を条件を満たすまで繰り返す(ループ処理)
より構成されます。しかし、流れ図は、上記の3種類の構造以外にも、どのようなアルゴリズムでも表現できてしまいます。つまり、GoTo文と言って、いくらでもアルゴリズムを複雑にできてしまいます。そこで、情報技術者試験では、「擬似言語」を導入しました。これは、GoTo文が一切、使用することが出来ず、かつ、上記の3種類の構造でアルゴリズムを表現することです。このような方法論を「構造化プログラミング」と言います。
2 流れ図入門 ここで実際に流れ図について考え見ましょう。以下の例は、1から100までの総和を求める流れ図です。
この流れ図は、「i」という変数に初期値として「1」を代入しています。そして「goukei」という変数に「0」を格納しています。ループ処理は、条件である「i > 100」を満たすまで、ルーブ内の2個の命令を実行しています。ここで、goukeiへ1から100までの加算処理を行っています。
3 擬似言語 上記の同様の処理を擬似言語で記述すると以下のようになります。
擬似言語は、「宣言部」「処理部」から構成されます。宣言部では。プログラム名や変数の宣言を行っています。処理部が実際のアルゴリズムとなります。ここで流れ図との違いは、変数の代入が逆です。また。ループ処理には、■の横に条件を記述します。ここでの条件は、条件を満たしている間、ループ内の命令を実行します。
4 配列 配列とは、変数の1種類で、「型が同じで変数名が同じである複数の要素をもつ変数の集まりです」。配列の要素を識別するためには「添字(インデックス)」を使用します。
例えば、Aとい名前の配列で100個の要素の場合、A(1)、A(2)・・・A(99)、A(100)というように表現します。配列は、ループ処理と使用することによりアルゴリズムを簡潔なものにします。
例えば、100個の配列のデータの内容を1から50までの要素は、G1に格納して51〜100までの要素の内容はG2へ格納する処理を擬似言語で記述すると以下のようになります。尚、配列の添字は、「1から始まる」場合と「0から始まる」場合があります。
ここでループ処理は、iが100以下の時実行されます。その中で、iが50以下の場合は、G1へ加算して、それ以外の場合は、G2へ配列の値を加算しています。ここで、▲は判断構造です。つまり、擬似言語では以下のようになります。
●「順次構造」「
●「判断構造」「▲」
●「反復構造」「■」
また、配列には、「次元」というものがあります。上記の例では1次元の配列です。2次元の配列の場合は、A(1,1)というように表現します。3行2列の配列Aという名前の場合は、以下のように表現します。
A(1,1) A(1,2)
A(2,1) A(2,2)
A(3,1) A(3,2)
5 最大値・最小値 以下は、配列の中から最大値を求めるアルゴリズムです。
ここで、コード表という配列とその要素数を外部参照で受取っています。ポンイトは、初期処理の2行の命令です。ループ処理の添え字「I」を「2」にセットして、最初のコード表の1番目の要素を変数「最大値」にセットしています。あとは、要素数分反復処理を行い、最大値とより大きいか判断して、そうであるならば、最大値を変更しています。この判断処理を逆にすれば、最小値を求めるアルゴリズムになります。
6 線形検索 線形検索」とは、「逐次検索」とも言います。これは、配列などに格納されているあるデータを探し出す処理のことを言います。例えば、配列に社員番号の「コード表」が格納されていて、これよりある人の社員番号を検索する場合を考えて見ましょう。
線形検索処理では、コーど表の配列より要素数分反復処理を行います。その際、社員番号が等しくない時は、次の要素と比較しています。等しかった場合はループの脱出して返却値を返します。この際、「i」が要素数と等しいか大きい場合は、検索出来なかったとして、0を返却値に返しています。
検索のループ回数は(要素数がN個の時)
・最小1回
・最大N回
・平均(N+1)/2回
7 2分検索 2分検索」とは、前提条件として、検索対象の配列が昇順か降順に並んでいる時に、有効な方法です。これは、検索値と「配列の中央の要素」を比較します。これにより、検索値の方が大きければ、求める要素は右側に存在します。逆の場合は左側に存在します。この方法で検索を行っていきます。前節と同様に、配列に社員番号の「コード表」が格納されていて、これよりある人の社員番号を検索する場合を考えて見ましょう。
2分検索の場合には、添字として、3個用意します。つまり、「先頭」と「末尾」の範囲で中央の添字で社員番号を比較しています。この結果、見つかった場合の判断は、先頭が末尾以下の場合です。
検索のループ回数は(要素数がN個の時)
・最小 1回
・最大 Log2N+1回
・平均 Log2N回
8 整列 整列とは。「ソート処理」のことを言います。データを昇順または降順に並べ替えます。
整列には単純なものとして、以下の方法があります。
・選択法
・交換法(バブルソート)
・挿入法
また、高速に整列の方法としては以下のものがあります。
・クイックソート
・シェルソート
・マージソート
・ヒープソート
9 選択法 選択法」は、起点となる要素とそれに+1した隣の要素をループして比較してデータを交換していきます。これにより、起点となる要素を+1していき、最終的に並び替えが完了します。
左記のアルゴリズムは、コード表の配列を降順に並び替えています。変数「I」が起点となる要素です。変数「J」が比較するためのループで使用しています。MAXは起点となる要素のIを格納して、これとjを比較して大きければ、MAXの値を変更しています。これにより交換処理が行われます。
整列の比較回数は(要素数がn個の時)
(n2-n)/2」回
10 バブルソート
(交換法)
バブルソート」とは、その名の通り、要素を交換しながら、並び替えを行います。つまり、起点となる要素を要素数-1から開始して、比較する要素を最初からループさせて大小比較により交換を行います。この処理を起点となる要素を-1していきます。
左記のアルゴリズムは、コード表の配列を降順に並び替えています。
整列の比較回数は(要素数がn個の時)
最大交換回数はn2
最小交換回数はn-1
11 挿入法 挿入法」は、配列が整列済みと未整列部分から構成されている場合に有効な方法です。
基本的に、3つの添字を使用します。
・「I」未整列部分の先頭の添字
・「J」挿入位置を検索するための添字
・「M」挿入位置を確保する添字
左記のアルゴリズムは、コード表の配列を降順に並び替えています。
整列の比較回数は(要素数がn個の時)
最大交換回数はn2
12 クイックソート クイックソート」は、整列の対象の配列を分割しながら整列を進めます。具体的には、全データから基準値を選び、その値より「大きいデータ」と「小さいデータ」に振り分けます。この作業を繰り末して行います。また、クイックソートは、「再帰呼出し」と言って、「ある手続きの中から自分自身を呼び出す」方法を用いても実現できます。
整列の比較回数は(要素数がn個の時)
平均比較回数はn*Log2n
最大交換回数はn2
13 シェルソート
(挿入法の応用)
シェルソート」は、ある程度整列されたデータに対して有効である。この方法は、「挿入法」を応用して、一定間隔ごとにデータを振り分け、これを挿入法で整列させて、その間隔を順次、狭くしていく方法です。
14 マージソート マージソート」は、既に整列された2個以上の配列を1つの配列に併合する処理を繰り返すことでソートを実現しています。つまり、「分割」して「整列」して「併合」を繰り返します。この方法は、補助記憶装置の大量のデータの並び替えなどに使用される「外部整列法」です。
15 ヒープソート
(選択法の応用)
ヒープソート」は、「選択法」を応用した方法で、配列を「ヒープ」に変換します。ヒープとは、ルートに最大値が入り、親ノード>=子ノードの条件を満たした完全二分木のことを言います。昇順の場合は、ルートに最小値が入ります。
整列の比較回数は(要素数がn個の時)
平均比較回数はn*Log2n
16 時間計算量 アルゴリスムの評価の方法のひとつに「繰り返し回数」に着目して、処理時間の評価尺度を「時間計算量」と言います。例えば、N個の要素がある場合、「N-1」回の繰り返し回数の時、処理時間がデータ数Nに比例していることを「オーダ記法」を用いて、O(N)と表現します。
以下に今までのアルゴリズムをオーダ記法で表現します。
種類 時間計算量
線形検索 O(N)
2分検索

O(Log2N)

選択法 O(LogN)
交換法(バブルソート) O(N2)
挿入法 O(N2)
クイックソート O(NLogN)
シェルソート O(N3/2)
マージソート O(NLogN)
ヒープソート O(NLogN)
17 再帰アルゴリズム 再帰」とは、ある手続の中で、その手続自体を使用することです
例えば、以下の例を考えて見ましょう。

(問題)
関数F(S)で、S=5の時のこの関数の関数値はいくつか?
関数の仕様は
 F(0)=0、F(1)=1
 F(S)=F(S-1)+F(S-2) 但しSは2以上とする

(解説)
ここで、S=5であるため、S=0〜S=5までの計算を行います。
S=0の時、F(0)=0
S=1の時、F(1)=1
S=2の時、F(2)=F(2-1)+F(2-2)=F(1)+F(0)=1+0=1
S=3の時、F(3)=F(3-1)+F(3-2)=F(2)+F(1)=1+1=2
S=4の時、F(4)=F(4-1)+F(4-2)=F(3)+F(2)=2+1=3
S=5の時、F(5)=F(5-1)+F(5-2)=F(4)+F(3)=3+2=5
よって、5が解答となります。  

ここでの質問は、こちらよりお願い致します。


メニューへ戻る