基本情報の用語と解説

スタックは後入れ先出し（LIFO）で、最後に入れたデータから取り出します（積み重ねた皿を上から取る形）。 【関連】キューは先入れ先出し（FIFO）で、先に入れたデータから取り出します。

キューは先入れ先出し（FIFO）で、先に入れたデータから順に取り出します（レジの行列と同じ順）。 【関連】スタックは後入れ先出し（LIFO）で、最後に入れたデータから取り出します。

論理積（AND）は、2つの入力が両方とも1のときだけ出力が1になります。 【関連】論理和（OR）は、どちらか一方でも1なら出力が1になります。

排他的論理和（XOR）は、2つの入力が異なるときだけ出力が1になります。 【関連】論理和（OR）は、両方が1のときも出力が1になる点が異なります。

二分探索は、整列済みのデータの中央と比べて探索範囲を半分ずつ絞り込む方法です。使う前にデータを整列しておく必要があります。 【関連】線形探索は、先頭から1つずつ順に調べる方法です。

線形探索（逐次探索）は先頭から順に調べる方法です。整列していなくても使えますが、データが多いと時間がかかります。

木構造は、根から枝分かれして親子関係（階層）を表すデータ構造です。 【関連】リスト構造は、要素を一列につないで表します。フォルダの階層構成も木構造の例です。

ビットは0か1かを表す情報の最小単位です。8ビットをまとめると1バイトになります。

バブルソートは、隣り合う要素どうしを比べて、順序が逆なら入れ替えることを繰り返す整列法です（値が泡のように端へ移ることが名前の由来）。 【関連】選択ソートは、最小値を探して先頭と交換していきます。

真理値表は、入力の組合せごとに出力の値を一覧にした表です。 【関連】ベン図は、集合の関係を円の重なりで表します。

選択ソートは、未整列の部分から最小値を選び、先頭の要素と交換していく整列法です。 【関連】挿入ソートは、整列済みの列の適切な位置に要素を差し込んでいきます。

挿入ソートは、要素を1つずつ取り出し、整列済みの列の正しい位置に差し込む整列法です。 【関連】選択ソートは、最小値を選んで先頭と交換していきます。挿入ソートは、ほぼ整列済みのデータなら非常に速く終わります。

ハッシュ法は、キーから計算した値（ハッシュ値）で格納位置を求め、直接アクセスする探索法です。 【関連】二分探索法は、整列済みのデータを半分ずつ絞り込みます。

否定論理積（NAND）は論理積を反転したもので、両方が1のときだけ出力が0になります。 【関連】否定論理和（NOR）は、両方が0のときだけ出力が1になります。

和集合は、2つの集合の少なくとも一方に含まれる要素をすべて集めた集合です。 【関連】積集合は、両方に共通する要素だけを集めた集合です。

幅優先探索は、出発点に近い頂点から一段ずつ範囲を広げて調べる探索法です。 【関連】深さ優先探索は、行けるところまで先に進んでから戻ります。幅優先探索はキュー、深さ優先探索はスタックや再帰で実現できます。

深さ優先探索は、1本の道を行けるところまで奥へ進み、行き止まりで戻って別の道を調べる探索法です。 【関連】幅優先探索は、近い頂点から順に広げていきます。深さ優先探索はスタックや再帰、幅優先探索はキューで実現できます。

連結リストは、各要素がポインタで次の要素を指してつながるデータ構造です。 【関連】配列は、要素が連続した記憶領域に並びます。連結リストの挿入・削除はポインタの付け替えだけで済みます。

二分木は、どの節点も子を2つまでしか持たない木構造です。 【関連】B木は、1つの節点がより多くの子を持てる多分木です。

2の補数は、全ビットを反転して1を足して作ります。負の数の表現に使われます。 【関連】1の補数は、全ビットを反転するだけで作ります。2の補数を使うと、引き算を足し算の回路で行えます。

クイックソートは、基準値（ピボット）より小さいか大きいかで2つに分けることを繰り返す整列法です。 【関連】マージソートは、半分に分けて整列した列を後で併合します。

マージソートは、列を分割し、整列済みの短い列どうしを併合（マージ）していく整列法です。 【関連】クイックソートは、基準値で2つに分けることを繰り返します。

ド・モルガンの法則は、全体の否定をとると、各項の否定どうしで論理積と論理和が入れ替わるという法則です（¬(A・B)＝¬A＋¬B、¬(A＋B)＝¬A・¬B）。 【関連】分配法則は、括弧を展開するときの法則です。

再帰呼出しは、関数（手続）が実行中に自分自身を呼び出すことです。 【関連】コールバックは、引数として渡した別の関数を後で呼び出してもらう仕組みです。終了条件（再帰を止める条件）がないと、呼出しが止まらなくなります。

ランレングス符号化は、同じ値が続く部分を「値と連続する回数」で表して圧縮する方式です。 【関連】ハフマン符号化は、出現頻度に応じて符号の長さを変えます。

ヒープは、どの親の値も子の値以上（またはどの親も子以下）に保つ木で、前者では根が最大値になります。 【関連】二分探索木は、左の子孫に小さい値、右の子孫に大きい値を置きます。

二分探索木は、各節点の左の部分木に小さい値、右の部分木に大きい値を置く二分木です。 【関連】ヒープは、親の値が子の値以上（または以下）という関係を保つ木です。

二分探索は1回の比較ごとに探索範囲が半分になるため、計算量はO(log n)です。データが2倍になっても比較は1回増えるだけです。 【関連】線形探索の計算量はO(n)です。

番兵法は、データの末尾に探す値（番兵）を置いて必ず見つかるようにし、範囲の終わりの判定を省く方法です。線形探索を速くする工夫です。

逆ポーランド記法（後置記法）は、演算子を演算の対象の後ろに書く記法です。 【関連】ポーランド記法（前置記法）は、演算子を前に書きます。逆ポーランド記法の式は、スタックを使って先頭から順に計算できます。

ハフマン符号は、出現頻度の高い記号に短い符号を割り当て、全体の長さを縮める符号です。 【関連】ハミング符号は、誤りの検出と訂正のための符号です。

優先度付きキューは、入れた順ではなく優先度の高い要素から取り出すデータ構造です。 【関連】デックは、列の両端から出し入れできるデータ構造です。優先度付きキューは、ヒープを使うと効率よく実現できます。

シノニムは、ハッシュ法で異なるキーが同じ格納位置（同じハッシュ値）になったときのキーどうしのことです。 【関連】ダイジェストは、ハッシュ値そのものを指します。シノニムが発生することを衝突（コリジョン）と呼びます。

有限オートマトンは、有限個の状態と入力による状態遷移だけで、入力列を受理するかを判定するモデルです。 【関連】有限オートマトンにスタックを加えたものがプッシュダウンオートマトンです。

BNF（バッカス・ナウア記法）は、生成規則を記号で書いてプログラム言語の構文を定める記法です。 【関連】構文図式は、同じ規則を矢印の図で表します。BNFでは「または」を縦棒（|）で表します。

動的計画法は、部分問題の答えを記録しておき、使い回して全体の答えを求める手法です。 【関連】分割統治法は、問題を分割してそれぞれ解き、結果を合わせます。

先行順（行きがけ順）は、節点自身を先に処理してから左、右の部分木へ進む走査順です。 【関連】後行順（帰りがけ順）は、左右の部分木を処理した後に節点自身を処理します。

チェイン法は、ハッシュ値が衝突したデータを連結リストでつないで格納する方法です。 【関連】オープンアドレス法は、表の中の別の空き位置を探して格納します。

ダイクストラ法は、始点から近い頂点の順に最短距離を確定させていく最短経路の算法です。 【関連】プリム法は、似た手順で最小全域木を求めます。ダイクストラ法は、負の重みの辺があると正しく求められません。

安定ソートは、同じキーを持つ要素どうしの元の順番を整列後も崩さない整列法です。 【関連】内部ソートは、主記憶の中だけで整列する方式のことです。バブルソートやマージソートは安定ソートです。

クラスカル法は、重みの小さい辺から順に、閉路ができないものを選んで最小全域木を作ります。 【関連】プリム法は、1つの頂点から木を広げていきます。

中間順（通りがけ順）は、左の部分木、節点自身、右の部分木の順に処理する走査順です。 【関連】後行順は、左、右、節点自身の順に処理します。二分探索木を中間順でたどると、値が小さい順に並びます。

吸収法則は、A＋A・B＝A のように、AとAかつBの論理和がAになるという法則です。 【関連】べき等法則は、A＋A＝A のようにAとAの論理和がAになる法則です。

貪欲法は、その時点で最もよい選択を積み重ねる手法です。高速ですが、最適解になるとは限りません。 【関連】最小全域木を求めるクラスカル法は、貪欲法の一例です。

チューリングマシンは、無限に長いテープを読み書きしながら状態を変える、計算の理論モデルです。 【関連】有限オートマトンは、有限個の状態のほかに記憶を持ちません。

AVL木は、どの節点でも左右の部分木の高さの差を1以下に保つ平衡二分探索木です。 【関連】赤黒木は、節点の色の規則によって釣り合いを保ちます。

停止問題は、プログラムが停止するかを判定する一般的な手順が存在しない、決定不能な問題です（チューリングが証明）。 【関連】巡回セールスマン問題は、時間をかければ解ける（決定可能な）問題です。

プッシュダウンオートマトンは、有限オートマトンにスタックを加えた計算モデルです。 【関連】テープを読み書きするのはチューリングマシンです。

基数ソートは、下の桁から順に、桁ごとに並べ直していく整列法です。 【関連】分布数え上げソートは、値ごとの個数を数えて並べます。

正規言語は、有限オートマトンで受理できる言語（正規表現で表せる言語）です。 【関連】文脈自由言語の受理には、プッシュダウンオートマトンが必要です。