読み込み中...
読み込み中...
読み込み中...
読み込み中...
読み込み中...
コンピュータは内部で 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進数)
2進数 → 10進数 への変換は、各桁に2の累乗を掛けて合計します。
例: 1101(2進数)→ 1×2³ + 1×2² + 0×2¹ + 1×2⁰ = 8 + 4 + 0 + 1 = 13
2進数は桁数が多くなるため、人間が扱いやすい 8進数 や 16進数 もよく使われます。
| 基数 | 使用する数字 | 2進数との対応 | 用途 |
|---|---|---|---|
| 2進数 | 0, 1 | ― | コンピュータ内部 |
| 8進数 | 0〜7 | 3桁ずつまとめる | ファイルのパーミッション |
| 10進数 | 0〜9 | ― | 日常の計算 |
| 16進数 | 0〜9, A〜F | 4桁ずつまとめる | メモリアドレス、色コード |
16進数では 10=A, 11=B, 12=C, 13=D, 14=E, 15=F と表記します。例えば 2進数 11111111 は16進数で FF(= 10進数 255)です。
コンピュータで負の数を表現するには 2の補数 を使います。2の補数は「ビットを反転して1を加える」ことで求められます。
例: 8ビットで -5 を表現する場合
000001011111101011111011(= -5)2の補数を使うと、加算回路だけで減算も実現できるため、コンピュータにとって効率的です。
小数を含む数値は 浮動小数点数 として表現します。IEEE 754 規格では、符号部(正負)・指数部(桁の位置)・仮数部(有効数字)の3つに分けて格納します。浮動小数点数には 丸め誤差 が生じるため、金額計算などでは注意が必要です。丸め誤差が生じる理由は、10進数の 0.1 のような一見単純な小数が、2進数では 0.0001100110011... という無限小数になるためです。有限のビット数で打ち切るため、わずかな誤差が発生します。
コンピュータは文字も数値として扱います。文字と数値の対応表を 文字コード と呼びます。
| 文字コード | 説明 |
|---|---|
| ASCII | 7ビットで128文字(英数字・記号)を表現。最も基本的な文字コード |
| Unicode | 世界中の文字を統一的に扱うための規格。10万文字以上を収録 |
| UTF-8 | Unicode のエンコーディング方式。ASCII と互換性がありWebで標準的に使用 |
| Shift_JIS | 日本語用の文字コード。レガシーシステムで使用されることがある |
ポイント
2進数を使う理由: 電子回路のON/OFFで確実に判別できるため。10進数との相互変換、8進数・16進数への変換方法を理解することが重要。負の数は 2の補数 で表現し、小数は 浮動小数点数(IEEE 754)で表現する。浮動小数点数では丸め誤差に注意(10進数の0.1は2進数で無限小数になる)。文字は 文字コード(ASCII、Unicode、UTF-8)によって数値に対応づけられる。
用語
論理演算 は、真(1)と偽(0)の2つの値を対象とした演算です。コンピュータのCPUは、論理演算の組み合わせですべての計算を行っています。
基本的な論理演算は次の3つです。
論理演算のすべての入力と出力を表にしたものが 真理値表 です。
| A | B | AND | OR | XOR | NAND | NOR |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
論理式を変換するための重要な法則です。
直感的に理解するには、日常の言葉で考えるとわかりやすくなります。「雨が降っていて寒い、のではない」は「雨が降っていない または 寒くない」と同じ意味です。「AかつBでない」は「Aでない、またはBでない」に変換できます。
この法則を使うと、ANDとORを相互に変換できます。回路設計やプログラムの条件式の変換に活用されます。
例: 「20歳以上 かつ 男性」の否定 = 「20歳未満 または 女性」
論理演算を電気回路で実現したものが 論理回路 です。
| 回路 | 記号名 | 機能 |
|---|---|---|
| AND回路 | MIL記号: D型 | 2入力が両方1のとき出力1 |
| OR回路 | MIL記号: 曲線型 | 2入力のどちらかが1のとき出力1 |
| NOT回路 | MIL記号: 三角+丸 | 入力を反転して出力 |
| NAND回路 | AND+丸 | ANDの出力を反転 |
| NOR回路 | OR+丸 | ORの出力を反転 |
| XOR回路 | OR+曲線 | 排他的論理和 |
コンピュータのCPU内部では、全加算器を複数並べることで多桁の加算を高速に実行しています。
ポイント
基本論理演算は AND・OR・NOT の3つ。これに XOR・NAND・NOR を加えた6種類を理解する。ド・モルガンの法則 で AND と OR を相互変換できる。論理回路は論理演算をハードウェアで実現したもので、半加算器 は XOR と AND で構成される。
用語
アルゴリズム とは、問題を解くための手順を明確に定義したものです。料理のレシピのように、「何を」「どの順番で」行うかを正確に記述します。
アルゴリズムには次の3つの基本構造があります。
この3つの組み合わせで、あらゆるアルゴリズムを表現できます。これを 構造化定理 といいます。
アルゴリズムを視覚的に表現する図が フローチャート です。JIS(日本産業規格)で記号が定められています。
| 記号 | 名称 | 用途 |
|---|---|---|
| 角丸四角形 | 端子 | 処理の開始・終了 |
| 長方形 | 処理 | 演算・代入などの処理 |
| ひし形 | 判断 | 条件分岐(Yes/No) |
| 平行四辺形 | 入出力 | データの入力・出力 |
| 矢印 | 流れ線 | 処理の流れ・方向 |
| 円 | 結合子 | フローチャートの接続点 |
線形探索(リニアサーチ) はデータを先頭から順に調べる方法です。データが整列されていなくても使えますが、データ件数 n に比例して時間がかかります。
二分探索(バイナリサーチ) はデータが整列済みである場合に使える高速な探索方法です。中央の値と比較して探索範囲を半分に絞り込みます。
| 探索方法 | 前提条件 | 計算量(最悪) | 特徴 |
|---|---|---|---|
| 線形探索 | なし | O(n) | 単純だがデータが多いと遅い |
| 二分探索 | 整列済み | O(log n) | 高速だが事前ソートが必要 |
O(n) と O(log n) の差は、データ量が大きくなるほど劇的に開きます。データ1,000件の場合、線形探索は最大1,000回の比較が必要ですが、二分探索なら最大約10回で済みます。100万件では線形探索が最大100万回に対し、二分探索は最大約20回です。
バブルソート は隣接する要素を比較・交換を繰り返して並べ替えるアルゴリズムです。n 個の要素に対し、外側ループ n 回 × 内側ループ約 n 回 ≒ n² 回の比較が必要なため、計算量は O(n²) になります。
| 整列方法 | 計算量(平均) | 計算量(最悪) | 特徴 |
|---|---|---|---|
| バブルソート | O(n²) | O(n²) | 実装が簡単だが遅い |
| 選択ソート | O(n²) | O(n²) | 最小値を見つけて先頭に移動 |
| 挿入ソート | O(n²) | O(n²) | ほぼ整列済みのデータに強い |
| クイックソート | O(n log n) | O(n²) | 平均的に最も高速。ピボットの選び方が悪いと最悪ケース |
| マージソート | O(n log n) | O(n log n) | 安定ソート。データ量が多い場合に有効 |
クイックソートは平均 O(n log n) で実用上最も高速ですが、すでに整列済みのデータに対してピボットの選び方が悪いと最悪 O(n²) になります。
アルゴリズムの効率を表す指標が 計算量 です。データ件数 n に対して処理回数がどのように増えるかを O(オーダー)記法 で表します。
| 計算量 | 名称 | 増え方 | 例 |
|---|---|---|---|
| O(1) | 定数時間 | データ量に関係なく一定 | 配列の添字アクセス |
| O(log n) | 対数時間 | データが倍になっても1回増える程度 | 二分探索 |
| O(n) | 線形時間 | データ量に比例 | 線形探索 |
| O(n log n) | 準線形時間 | nとlog nの積 | クイックソート |
| O(n²) | 二乗時間 | データ量の2乗に比例 | バブルソート |
計算量が小さいほど効率の良いアルゴリズムです。
ポイント
アルゴリズムの基本構造は 順次・分岐・反復 の3つ。探索: 線形 O(n)、二分 O(log n)。ソート: バブル/選択 O(n²)、クイック O(n log n)。計算量の大小比較は頻出。O(1) < O(log n) < O(n) < O(n log n) < O(n²) の順で効率が良い。
用語
データ構造 とは、データをメモリ上でどのように整理・格納するかを定めた仕組みです。適切なデータ構造を選ぶことで、プログラムの処理速度やメモリ効率が大きく変わります。
データを連続したメモリ領域に並べた構造です。添字(インデックス) で任意の要素に即座にアクセスできます(O(1))。ただし、途中への挿入・削除はデータの移動が必要なため効率が悪くなります。
LIFO(Last In, First Out: 後入れ先出し) 方式のデータ構造です。最後に追加したデータを最初に取り出します。
用途: Webブラウザの「戻る」ボタン、関数の呼び出し履歴
身近な例で理解すると、ブラウザの「戻る」ボタンはまさにスタックです。ページA → B → C と訪問した場合、「戻る」を押すと最後に訪れた C から順に B → A と戻ります(LIFO)。
FIFO(First In, First Out: 先入れ先出し) 方式のデータ構造です。最初に追加したデータを最初に取り出します。
用途: プリンタの印刷待ち行列、メッセージキュー
身近な例で理解すると、プリンタの印刷待ちはキューです。Aさん → Bさん → Cさんの順で印刷を依頼した場合、Aさんの文書から順に印刷されます(FIFO)。
| データ構造 | 方式 | 追加 | 取り出し | 主な用途 |
|---|---|---|---|---|
| スタック | LIFO | push(上に積む) | pop(上から取る) | ブラウザの戻る、Undo機能 |
| キュー | FIFO | enqueue(末尾に追加) | dequeue(先頭から取る) | 印刷待ち、タスク管理 |
各要素がデータと ポインタ(次の要素への参照) を持つ構造です。配列と異なり、途中への挿入・削除が高速(O(1))ですが、特定の位置へのアクセスには先頭からたどる必要があります(O(n))。
データが親子関係で階層的に接続された構造です。最上位のノードを 根(ルート)、末端を 葉(リーフ) と呼びます。
二分木 は各ノードの子が最大2つの木構造です。二分探索木 では、左の子 < 親 < 右の子という規則でデータを格納するため、効率的な探索が可能です。なぜ効率的かというと、各ノードで左右どちらに進むかを判断するたびにデータの半分を除外できるため、計算量は O(log n) になります。これは二分探索と同じ原理です。
ノード(頂点) と エッジ(辺) でデータ間の関係を表す構造です。木構造はグラフの一種です。
| 種類 | 説明 |
|---|---|
| 有向グラフ | エッジに方向がある(A→B) |
| 無向グラフ | エッジに方向がない(A―B) |
| 重み付きグラフ | エッジにコスト(距離・時間等)がある |
ポイント
スタックは LIFO(後入れ先出し)、キューは FIFO(先入れ先出し) で覚える。配列は添字アクセスが高速(O(1))だが挿入・削除は遅い。リストは挿入・削除が高速だがアクセスは遅い。木構造 は階層的なデータ表現、グラフ はノードとエッジで関係を表す。
用語