情報処理のWeb教科書―IPA情報処理試験対策のお供に!

アルゴリズムとデータ構造―基本情報など情報処理試験対策用の解説

トップ 情報処理の知識体系 テクノロジ系 基礎理論 アルゴリズムとプログラミング アルゴリズムとデータ構造

アルゴリズムとデータ構造について、基本情報や応用情報など情報処理試験対策用の解説をまとめています。

目次

このページの目次です。

1. データ構造

2. アルゴリズム

もっと知識を広げるための参考

更新履歴

1. データ構造

データ構造の考え方などデータ構造とは何か、まとめていきます。

データ構造とは

データ構造とは、コンピュータがデータ処理や計算を行う際に、あらかじめデータを扱いやすいように加工しておき、 計算速度が速くなるようにしたものです。

データ構造の種類

データ構造の種類についてまとめていきます。

配列

配列の考え方を理解し、データの格納方法,取出し方法などの操作を見ていきます。

配列とは

配列とは、内部構造を持つデータ構造で、同じ型の要素の並びで添字式を持つデータ構造のことを言います。

配列(数値)要素の並べ替えの例

配列の例として、数値の配列の要素の並べ替えについて見ていきます。 以下ではグループ内では、処理がおこなわれた数値を左から順に並べるものとして、手順に従って6個の数値の配列「180、315、282、410、645、525」を並べ替えます。

手順
手順1並びの左から順に、数値の1の位の値によって0~9のグループに分ける。
手順2次に0のグループの数値を左側から順に取り出して並べ、その右側に1のグループ、以下順に2~9のグループの数値を並べていく。
手順3手順2で得られた数値の並びの左側から順に、数値の10の位によって0~9のグループに分ける。
手順4手順2と同様に、0のグループの数値から順に並べる。
手順1

並べの左側から順に、数値の1の位の値によって0~9のグループに分けます。

 1の位が0のグループ180、410
 1の位が1のグループ
 1の位が2のグループ282
 1の位が3のグループ
 1の位が4のグループ
 1の位が5のグループ315、645、525
手順2

0のグループの数値を左側から順に取り出して並べ、その右側に1のグループ以下順に2~9のグループの数値を並べて行きます。

180、410、282、315、645、525

となります。

手順3
 10の位が0のグループ
 10の位が1のグループ410、315
 10の位が2のグループ525
 10の位が3のグループ
 10の位が4のグループ
 10の位が5のグループ
 10の位が6のグループ645
 10の位が7のグループ
 10の位が8のグループ180、282
 10の位が9のグループ
手順4

手順2と同様に、0のグループの数値から順に並べます。

410、315、525、645、180、282

リスト

リストの考え方,その操作を理解します。

スタックとキュー

スタックとキューの考え方,その操作を理解します。

スタック

再帰的な処理を実現するためには、再帰的に呼び出したときのレジスタ及びメモリの内容を保存しておく必要あります。 これを実現する記憶管理にはスタックが用いられます。

スタックとは

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

スタックの例―データ構造とアルゴリズム
スタックの例
複数のデータが格納されているスタックからのデータの取り出し方

複数のデータが格納されているスタックからのデータの取り出す場合は最後に格納されたデータを最初に取り出します。

キュー

キューとは、英語でqueueといい、1次元配列に格納されたデータの一方からデータを格納し、他方の端からデータを取り出すデータ構造のことです。 先に入力したデータが先に出力される(先入れ先だし:First In First Out)という特徴をもつデータ構造です。

データ構造のキューを実現する方法について

片方向リンクで実現したキューの場合、片方向でしかデータの挿入・取り外しが行えないため、途中への挿入・取り外しを行う場合一旦全てを取り外してから挿入しなければいけません。

一方、双方向リンクの場合、双方向の走査や指定されたノードの前に挿入したり、指定されたノードが削除できるので片方向に比べて途中への挿入・取り外しが容易です。

補足)双方向リンクで実現されるキューは、例えば最初のデータが後で実行したいけど、一番最後に回すのはちょっと問題がある場合に、 通常はキューの最後に追加しますが、キューの最初に追加すれば、1回分だけ後回しができるといった使い方が可能になります。

スタックとキューに関連したIPA情報処理試験の過去問題

以下ではスタックとキューに関連したIPA情報処理試験の過去問とそのの解説をまとめています。

木構造

木は、要素同士の階層関係を表現するための問題向きデータ構造です。 詳細で、木構造の種類についてまとめています。根、葉、枝などの用語のやさしい説明から、順序木、2分木、多分木、b木、b+木、バランス木などの考え方やイメージ、計算量、ヒープ、幅優先探索など、情報処理の過去問と合わせてまとめました。

詳細

2. アルゴリズム

アルゴリズムとは何かの意味から、代表的なアルゴリズムについてまとめています。

ITにおけるアルゴリズムとは

ITやコンピューター分野におけるアルゴリズムは、コンピュータで問題を処理するためにプログラムとして表現するのに向いている解決法です。 例をあげると、グラフ理論、オペレーションズリサーチ、数値計算、データ構造の操作、整列、数式処理、言語処理などです。

参考)アルゴリズムとは

アルゴリズムとは、一般的には算法と訳されます。一般的な意味、ITや医療などで使われるアルゴリズムの意味をまとめています。

詳細

流れ図

流れ図とは、フローチャートともいわれ、データの流れや問題解決の手順(アリゴリズム)を表す図のことを言います。

有名なアルゴリズムにユークリッドの互除法がありますが、以下はその流れ図の例になります。 ユークリッド互除法は、2つの整数の割算を繰り返して最大公約数を求める方法です。

【問14】ユークリッドの互除法―平成20年秋期ソフトウェア開発技術者

流れ図に関連したIPA情報処理試験の過去問題

以下では流れ図に関連したIPA情報処理試験の過去問とそのの解説をまとめています。

代表的なアルゴリズム

代表的なアルゴリズムを修得し、応用できるようにしていきます。

整列・併合・探索のアルゴリズム

整列のアルゴリズム、併合のアルゴリズム、探索のアルゴリズムを理解していきます。

挿入ソート

挿入ソートは、単純挿入整列法とも呼ばれ、整列済みの要素と追加する要素を比較し ながら適切な場所に挿入するアルゴリズムです。

挿入ソートの例

文章で説明するより、例を見た方が分かりやすいです。

挿入ソート(単純挿入整列法)で昇順に並べる例)
[2][4][1][3]
⇒ [2][4][1][3] ・・・ [2]と[4]を比較、[2]の方が小さいのでそのまま
⇒ [2][1][4][3] ・・・ [4]と[1]を比較、[4]の方が大きいので入れ替え
⇒ [1][2][4][3] ・・・ [2]と[1]を比較、[2]の方が大きいので入れ替え
⇒ [1][2][4][3] ・・・ [2]と[4]を比較、[2]の方が小さいのでそのまま
⇒ [1][2][3][4] ・・・ [4]と[3]を比較、[4]の方が大きいので入れ替え

挿入ソートのオーダー

整列済みのものを整列するので入れ替えが発生しないため、n-1回の比較で整列が完了します。 なので、オーダー的にはnとなります。

クイックソート

クイックソートは以下のように並べ替えを行うソート方法です。

①適当な基準値を選び、それよりも小さな値のグループと大きな値のグループにデータを分割する。
②同様にして、グループの中で基準値を選び、それぞれのグループを分割する。
①②の操作を繰り返していく方法です。

ヒープソート

ヒープソートでは、木構造を配列で表現するデータ構造を利用したソートアルゴリズムで、利用する木構造は半順序木とよばれる順序木を使用します。 未整列の部分を順序木にし、そこから最小値を取り出して整列済の部分に移します。 この操作を繰り返して、未整列の部分を縮めていきます。

線形探索法

線形探索法は、先頭のデータから順に目的のデータがあるかを比較していく探索法です。 最短で1回、最長でn回、平均で(1+n)/2回の探索が行われます。

2分探索

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

ハッシュ表探索法

ハッシュは、データを高速に検索するための方法の1つです。

データ項目の1つの値(キー項目の値)を使って、格納アドレスに変換し、そこにデータを格納します。 アドレスの変換に用いる関数をハッシュ関数、得られた値をハッシュ値といいます。

データを探索する場合も同じハッシュ関数を用いて格納アドレスを求め、目的のデータを得ます。 ハッシュ関数によって得た格納アドレスがすでに使われている場合、「シノニムが発生した」といいます。

再帰のアルゴリズム

再帰的アルゴリズムは、関数の定義中にその関数自身への参照が定義中に表れるアルゴリズムです。

再帰的アルゴリズムの例

再帰的アルゴリズムの例としては、n!や自然数の定義、木構造の探索、クリックソート、マージソートのアルゴリズムなどがあります。

代表的なアルゴリズムに関連したIPA情報処理試験の過去問題

以下ではアルゴリズムに関連したIPA情報処理試験の過去問とそのの解説をまとめています。

もっと知識を広げるための参考

更新履歴

戻る

スポンサーリンク

情報処理の知識体系

プログラミング

各試験の問題と解説

ランダム出題・採点アプリ

スポンサーリンク