基礎理論とアルゴリズム

コンピュータは内部で 2進数（基数2） を使ってすべてのデータを処理しています。人間が普段使う 10進数（基数10） との変換方法を理解することが、ITの基礎理論の第一歩です。

なぜコンピュータは2進数を使うのでしょうか。電子回路は電圧の ON（1） と OFF（0） の2状態で安定動作します。もし10段階の電圧でデータを表現しようとすると、微妙な電圧差を正確に区別するのが困難で誤動作の原因になります。一方、2段階であれば確実に判別できるため、2進数が採用されています。

2進数の各桁は ビット（bit） と呼ばれ、8ビットをまとめて 1バイト（byte） とします。1バイトで表現できる値は 0〜255（2^8 - 1）の256通りです。

基数変換の方法

10進数 → 2進数 への変換は、10進数を2で割り続けて余りを下から読む方法が基本です。

例: 13（10進数）→ 1101（2進数）

• 13 ÷ 2 = 6 … 余り 1
• 6 ÷ 2 = 3 … 余り 0
• 3 ÷ 2 = 1 … 余り 1
• 1 ÷ 2 = 0 … 余り 1
• 下から読む → 1101

2進数 → 10進数 への変換は、各桁に2の累乗を掛けて合計します。

例: 1101（2進数）→ 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 8 + 4 + 0 + 1 = 13

8進数と16進数

2進数は桁数が多くなるため、人間が扱いやすい 8進数 や 16進数 もよく使われます。

16進数では 10=A, 11=B, 12=C, 13=D, 14=E, 15=F と表記します。例えば 2進数 11111111 は16進数で FF（= 10進数 255）です。

負の数の表現（補数）

コンピュータで負の数を表現するには 2の補数 を使います。2の補数は「ビットを反転して1を加える」ことで求められます。

例: 8ビットで -5 を表現する場合

1. +5 = 00000101
2. ビット反転 → 11111010
3. +1 → 11111011（= -5）

2の補数を使うと、加算回路だけで減算も実現できるため、コンピュータにとって効率的です。

浮動小数点数

小数を含む数値は 浮動小数点数 として表現します。IEEE 754 規格では、符号部（正負）・指数部（桁の位置）・仮数部（有効数字）の3つに分けて格納します。浮動小数点数には 丸め誤差 が生じるため、金額計算などでは注意が必要です。丸め誤差が生じる理由は、10進数の 0.1 のような一見単純な小数が、2進数では 0.0001100110011... という無限小数になるためです。有限のビット数で打ち切るため、わずかな誤差が発生します。

文字コード

コンピュータは文字も数値として扱います。文字と数値の対応表を 文字コード と呼びます。

論理演算 は、真（1）と偽（0）の2つの値を対象とした演算です。コンピュータのCPUは、論理演算の組み合わせですべての計算を行っています。

基本的な論理演算は次の3つです。

• AND（論理積） — 両方とも1のときだけ1
• OR（論理和） — どちらか一方でも1なら1
• NOT（否定） — 0と1を反転

真理値表

論理演算のすべての入力と出力を表にしたものが 真理値表 です。

• XOR（排他的論理和） — どちらか一方だけ1のとき1（両方同じなら0）
• NAND（否定論理積） — ANDの否定。NANDだけですべての論理回路を構成できる（NOT、AND、ORのすべてをNANDの組み合わせで作れるため、IC設計ではNANDゲートが基本部品として使われる）
• NOR（否定論理和） — ORの否定

ド・モルガンの法則

論理式を変換するための重要な法則です。

• NOT（A AND B）= NOT A OR NOT B
• NOT（A OR B）= NOT A AND NOT B

直感的に理解するには、日常の言葉で考えるとわかりやすくなります。「雨が降っていて寒い、のではない」は「雨が降っていない または 寒くない」と同じ意味です。「AかつBでない」は「Aでない、またはBでない」に変換できます。

この法則を使うと、ANDとORを相互に変換できます。回路設計やプログラムの条件式の変換に活用されます。

例: 「20歳以上 かつ 男性」の否定 = 「20歳未満 または 女性」

論理回路

論理演算を電気回路で実現したものが 論理回路 です。

半加算器と全加算器

• 半加算器 — 1桁の2進数の加算を行う回路。XOR回路（和）とAND回路（桁上げ）で構成される
• 全加算器 — 下の桁からの桁上げ入力も含めた加算を行う回路。半加算器を2つ組み合わせて構成

コンピュータのCPU内部では、全加算器を複数並べることで多桁の加算を高速に実行しています。

アルゴリズム とは、問題を解くための手順を明確に定義したものです。料理のレシピのように、「何を」「どの順番で」行うかを正確に記述します。

アルゴリズムには次の3つの基本構造があります。

• 順次（Sequence） — 処理を上から順に実行する
• 分岐（Selection） — 条件によって処理を切り替える（if-else）
• 反復（Iteration） — 条件が満たされる間、処理を繰り返す（ループ）

この3つの組み合わせで、あらゆるアルゴリズムを表現できます。これを 構造化定理 といいます。

フローチャート（流れ図）

アルゴリズムを視覚的に表現する図が フローチャート です。JIS（日本産業規格）で記号が定められています。

代表的な探索アルゴリズム

線形探索（リニアサーチ） はデータを先頭から順に調べる方法です。データが整列されていなくても使えますが、データ件数 n に比例して時間がかかります。

二分探索（バイナリサーチ） はデータが整列済みである場合に使える高速な探索方法です。中央の値と比較して探索範囲を半分に絞り込みます。

O(n) と O(log n) の差は、データ量が大きくなるほど劇的に開きます。データ1,000件の場合、線形探索は最大1,000回の比較が必要ですが、二分探索なら最大約10回で済みます。100万件では線形探索が最大100万回に対し、二分探索は最大約20回です。

代表的な整列アルゴリズム

バブルソート は隣接する要素を比較・交換を繰り返して並べ替えるアルゴリズムです。n 個の要素に対し、外側ループ n 回 × 内側ループ約 n 回 ≒ n² 回の比較が必要なため、計算量は O(n²) になります。

クイックソートは平均 O(n log n) で実用上最も高速ですが、すでに整列済みのデータに対してピボットの選び方が悪いと最悪 O(n²) になります。

計算量（オーダー記法）

アルゴリズムの効率を表す指標が 計算量 です。データ件数 n に対して処理回数がどのように増えるかを O（オーダー）記法 で表します。

計算量が小さいほど効率の良いアルゴリズムです。

データ構造 とは、データをメモリ上でどのように整理・格納するかを定めた仕組みです。適切なデータ構造を選ぶことで、プログラムの処理速度やメモリ効率が大きく変わります。

配列（Array）

データを連続したメモリ領域に並べた構造です。添字（インデックス） で任意の要素に即座にアクセスできます（O(1)）。ただし、途中への挿入・削除はデータの移動が必要なため効率が悪くなります。

スタック（Stack）

LIFO（Last In, First Out: 後入れ先出し） 方式のデータ構造です。最後に追加したデータを最初に取り出します。

• プッシュ（push） — データを上に積む
• ポップ（pop） — 一番上のデータを取り出す

用途: Webブラウザの「戻る」ボタン、関数の呼び出し履歴

身近な例で理解すると、ブラウザの「戻る」ボタンはまさにスタックです。ページA → B → C と訪問した場合、「戻る」を押すと最後に訪れた C から順に B → A と戻ります（LIFO）。

キュー（Queue）

FIFO（First In, First Out: 先入れ先出し） 方式のデータ構造です。最初に追加したデータを最初に取り出します。

• エンキュー（enqueue） — データを末尾に追加
• デキュー（dequeue） — 先頭のデータを取り出す

用途: プリンタの印刷待ち行列、メッセージキュー

身近な例で理解すると、プリンタの印刷待ちはキューです。Aさん → Bさん → Cさんの順で印刷を依頼した場合、Aさんの文書から順に印刷されます（FIFO）。

リスト（連結リスト）

各要素がデータと ポインタ（次の要素への参照） を持つ構造です。配列と異なり、途中への挿入・削除が高速（O(1)）ですが、特定の位置へのアクセスには先頭からたどる必要があります（O(n)）。

木構造（ツリー）

データが親子関係で階層的に接続された構造です。最上位のノードを 根（ルート）、末端を 葉（リーフ） と呼びます。

二分木 は各ノードの子が最大2つの木構造です。二分探索木 では、左の子 < 親 < 右の子という規則でデータを格納するため、効率的な探索が可能です。なぜ効率的かというと、各ノードで左右どちらに進むかを判断するたびにデータの半分を除外できるため、計算量は O(log n) になります。これは二分探索と同じ原理です。

グラフ

ノード（頂点） と エッジ（辺） でデータ間の関係を表す構造です。木構造はグラフの一種です。