アルゴリズムとデータ構造 ITパスポート対策テクノロジ系基礎理論編⑥
3 views
2023-10-222023-10-21
アルゴリズム
アルゴリズムとは、特定の目的を達成するための処理手順のことです。ただこれでは非常に範囲が広いため、通常アルゴリズムの授業等では、様々な問題で共通に使用される処理手順（探索、並べ替えなど）が解説されます。
最終的な結果が同じでも、アルゴリズムは複数存在する場合が多く、処理にかかる時間やメモリ使用量でアルゴリズム間の優劣が判断されます。
アルゴリズムの表現方法
アルゴリズムは実際のプログラミング言語やこれを模した疑似言語で書かれる他、以下のような流れ図（フローチャート）で表現されることもあります。
| 記号 | 機能 |
|---|---|
 | 処理の開始、終了を表す。 |
 | 様々な具体的処理を表す。 |
 | 条件を判断して処理を分岐する。 |
 | ループの始まり、終わりを表す。この記号の代わりに条件と矢印で表現される場合もあります。 |
アルゴリズムの基本構造
アルゴリズムの基本構造には順次，選択，繰返しの3つがあります。
順次構造
上から下に書かれた順番に従って処理を行っていきます。
選択構造
分岐点の選択条件に従って処理の流れを枝分かれさせます。
繰返し構造
条件を満たしている間、同じ処理を繰り返します。ループの最初で条件判定を行う方式と最後で行う方式があります。永遠に条件を満たし続ける場合は無限ループに陥ります。
代表的なアルゴリズム
整列のアルゴリズム
| バブルソート | 隣のデータと比較し、大小の順が逆であれば入れ替えるという動作を繰り返すことで整列を行う。 |
|---|---|
| 選択ソート | 最小値を探して、未整列部分の先頭と交換するという動作を繰り返すことで整列する。 |
| クイックソート | 基準値をもとに大小2グループに分けるという動作を繰り返すことで整列する。 |
| マージソート | その中で整列するまでデータを2等分した後、分割したデータを併合するで整列する |
この中で一番早い（計算量が小さい）ソート方法はマージソートです。
探索のアルゴリズム
| 線形探索法 | 先頭から順に1つずつ探索値と比較していく方法。 |
|---|---|
| 2分探索法 | 中央の値と比較し、大きければ後半、小さければ前半のデータの大して同じことを繰り返す（データが事前に整列されていることが条件）。 |
データ構造
変数
もっとも基本的なデータの格納方法で、変数と呼ばれるデータの入れ物にデータを代入することで使用します。
変数にはどんなデータでも入れることができる型なしの変数と入れることのできるデータの種類（文字、整数、真理値など）が決まっている型付きの整数があります。
配列
配列は同じ型のデータを集めて順序付けたデータ構造です。個々の要素にはその配列の中の位置であるインデックスを利用してアクセスすることができます。
リスト
リストは配列と似ていますが、次のデータ位置をポインタと呼ばれる情報によって示すことでより柔軟性を高めたデータ構造です。
キュー
先に入れたものから先に取り出すことのできる先入れ先出し（FIFO）方式のデータ構造です。
スタック
後に入れたものから先に取り出すことのできる後入れ先出し（LIFO）方式のデータ構造です。
木構造
木のように上部から下部に行くにしたがって枝分かれしていくデータ構造です。各節をノードといい、ノードの数が最大でも2個になるツリーを2分木（バイナリツリー）といいます。
確認問題（過去問）
ITパスポート試験令和5年問69
配列に格納されているデータを探索するときの, 探索アルゴリズムに関する記述のうち、 適切なものはどれか。
ITパスポート試験令和3年問74
流れ図 X で示す処理では,変数 i の値が, 1 → 3 → 7 → 13 と変化し,流れ図 Y で示す処理では,変数 i の値が, 1 → 5 → 13 → 25 と変化した。図中の a, b に入れる字句の適切な組合せはどれか。
ITパスポート試験平成30年春問96
先入れ先出し(First-In First-Out, FIFO)処理を行うのに適したキューと呼ばれるデータ構造に対して“8","1","6","3" の順に値を格納してから、取出し を続けて2回行った。2回目の取出しで得られる値はどれか。
ITパスポート試験平成30年問76
複数のデータが格納されているスタックからのデータの取出し方として、 適切なものはどれか。
ITパスポート試験平成28年秋問92
後に入れたデータが先に取り出されるデータ構造 (以下, スタックという)がある。これを用いて, 図に示すような, 右側から入力されたデータの順番を変化させて, 左側に出力する装置を考える。 この装置に対する操作は次の3通りである。
- 右側から入力されたデータをそのまま左側に出力する。
- 右側から入力されたデータをスタックの1番上に積み上げる。
- スタックの1番上にあるデータを取り出して左側に出力する。
この装置の右側から順番にデータ A, B, C, D を入力した場合に,この1～3の操作を組み合わせても, 左側に出力できない順番はどれか。
これだけで受かるITパスポート
https://ja.mondder.com
