本サイトはプロモーション（広告）が含まれています。

応用情報技術者

【応用情報技術者】アルゴリズムとプログラミングの用語メモ

【応用情報技術者】アルゴリズムとプログラミングの用語メモ

LIFO

再帰的な処理では A1→A2→A3 の順でプログラムを呼び出した場合、A3→A2→A1 というように後から入れたものから順にその値を使用します。つまり再帰的な処理は、LIFO（Last-In First-Out，後入れ先出し）の記憶管理方式を用いて実現されています。

2分探索木

2分探索木（Binary Search Tree、BST）は、データを格納するためのデータ構造の一つです。BSTは、データを整列された形で格納し、検索、挿入、削除などの操作を高速に行うことができる特徴を持っています。

平均探索回数は log2N 回

アルゴリズム設計としての分割統治法

分割統治法（Divide and Conquer）は、アルゴリズム設計の一般的な方法論です。このアプローチでは、大きな問題をより小さなサブ問題に分割し、それらのサブ問題を解決し、最終的な解を合成する方法を採用します。

  • 全体を幾つかの小さな問題に分割して，それぞれの小さな問題を独立に処理した結果をつなぎ合わせて，最終的に元の問題を解決する方法である。

 

クイックソート

クイックソートは、整列対象のデータ群をある基準値以下のグループと基準値以上のグループに分割し、さらに分割後の各グループで基準値を選んで二つのグループに分割するという処理を繰り返してデータを整列するアルゴリズムです

分割統治を利用した整列法

スタック

スタックは、データ挿入の時はデータの最後に追加し、データ取り出し(削除)の時はデータの最後から取り出す(削除)後入れ先出し(LIFO:Last-in First-out)の構造をもっています。スタックにおけるデータ操作は、データを挿入するPUSH命令、データを取り出すPOP命令を使用して行います。

配列を用いてスタックを実現する場合の構成要素

  • スタックに最後に入った要素を示す添字の変数

線形リスト

線形リスト（Linear List）は、データを一列に並べて格納するリストデータ構造の一つです。線形リストは、要素が順番に並んでおり、各要素が次の要素へのリンク（参照）を持つ単純なデータ構造です。

  • ポインタによって指定されている要素の後ろに，新たな要素を追加する計算量は，要素の個数や位置によらず一定である。

先頭ポインタと末尾ポインタをもち，多くのデータがポインタでつながった単方向の線形リストの処理のうち，先頭ポインタ，末尾ポインタ又は各データのポインタをたどる回数が最も多いもの

  • 末尾のデータを削除する処理

幅優先探索

幅優先探索（Breadth-First Search、BFS）は、グラフや木のデータ構造を探索するアルゴリズムの一つです。幅優先探索は、特定のノードから始めて、隣接するノードを優先的に探索し、次にその隣接ノードの隣接ノードを探索するという方法を取ります。このアルゴリズムは、最短経路を求めたり、グラフ内の特定の要素を見つけたりするのに役立ちます。

配列A[1]，A[2]，…，A[n]で，A[1]を根とし，A[i]の左側の子をA[2i]，右側の子をA[2i＋1]とみなすことによって，2分木を表現する。

バブルソート

バブルソート（Bubble Sort）は、シンプルなソートアルゴリズムの一つです。このアルゴリズムは、隣接する要素を比較し、必要に応じて交換することによって、データの要素を昇順または降順に並び替えます。バブルソートは理解しやすいが、効率性には欠けるため、小さなデータセットに対してのみ有用であり、大きなデータセットでは避けるべきです。

  • 隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。

ヒープソート

ヒープソート（Heap Sort）は、選択ソートやバブルソートなどの単純なソートアルゴリズムとは異なる、効率的なソートアルゴリズムの一つです。ヒープソートは、データをヒープと呼ばれる特別なデータ構造を使用してソートします。ヒープは通常、完全二分木の形状を持ち、親ノードが子ノードよりも大きい（または小さい）という性質を持っています

  • 未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。

ベストフィット方式

ベストフィット方式（Best Fit Algorithm）は、メモリ管理において使用されるアルゴリズムの一つです。特に、メモリ確保の際に空き領域（フリーブロック）からプロセスやデータを配置するために利用されます。ベストフィット方式は、利用可能な空き領域の中から、最も小さいが要求されたメモリサイズ以上の領域を探し、その領域にデータを配置する方法です。

  • 空きブロック群のうち，要求された大きさを満たす最小のものを割り当てるので，最終的には小さな空きブロックが多数残る傾向にある。

マージソート

マージソート（Merge Sort）は、効率的なソートアルゴリズムの一つで、分割統治法（Divide and Conquer）を基にしています。このアルゴリズムは、リストを分割し、それらを再帰的にソートし、最終的にソートされたリストを合併（マージ）して最終的なソート済みリストを得る方法を採用しています。

モンテカルロ法

モンテカルロ法は、数値解析の分野において、確率を近似的に求めるために使われる手法です。乱数によるn回のシミュレーションを行い、ある事象がm回起これば、その事象の起こる確率は m／nで近似できます。試行回数nが大きくなるほどよりよい近似値を得ることができます。

  • 正方形の中に一様乱数を用いて多数の点をとったとき，その点の個数と正方形に内接する円の中にある点の個数の比が，点の個数を多くすると両者の面積比である4:πに近づくことを用いて求める。
PAGE TOP