ソフトウェア開発技術者/コンピュータ科学基礎

情報の基礎理論

「情報の基礎理論」も参照

数値表現・データ表現

基数変換

基数変換とは、ある基数で表された数値を、別の基数に変換する操作のことです。コンピュータでは主に2進法、8進法、16進法が使用されますが、ヒトは一般に10進法での数値表現を使うので基数変換が重要になります。

10進法から2進法への変換: 10進数を2で繰り返し割り、余りを下位から順に並べることで2進数が得られます。例えば、10進数の25は、25/2の余り1、12/2の余り0、6/2の余り0、3/2の余り1、1/2の余り1となり、2進数では11001と表せます。
2進法から10進法への変換: 2進数の各桁の値を2の対応する累乗で表し、それらを足し合わせると10進数になります。例えば、2進数の11001は、 $1\times 2^{4}+1\times 2^{3}+0\times 2^{2}+0\times 2^{1}+1\times 2^{0}=16+8+0+0+1=25$ と10進法で表せます。
16進法と2進法の相互変換: 16進数は2進数を4ビットずつグループ化して表したものとして扱えます。16進数の1桁は4ビットの2進数に対応しています。例えば、16進数のA5は2進数で 1010 0101 となります。

基数変換は、コンピュータが様々な数値表現方式で数値を表現・処理するために欠かせない基礎操作です。アプリケーションによっては、基数変換がデータの入出力の過程で不可欠になります。

数値表現

コンピュータ内部では、数値をビット列として表現する必要があります。主な数値表現方式は以下の通りです。

符号付き符号なし表現: 最上位ビットを符号ビットとして使い、残りのビットで値を表す方式です。符号ビットが0なら正の値、1なら負の値を表します。例えば8ビットなら、00000000(0)から01111111(127)が正の値、10000000(-128)から11111111(-1)が負の値になります。
1の補数: 負の数値を表すときに、正の数値のビット模様を反転させる方式です。例えば8ビットで-5は00000101の反転である11111010で表されます。
2の補数: 負の数値を表すとき、1の補数に1を加える方式です。8ビットで-5は11111011になります。2の補数は1の補数よりも扱いが簡単なため、現代のコンピュータで広く採用されています。
浮動小数点数: 実数を近似的に表現する方式で、符号と指数部と仮数部からなります。代表的な形式にIEEE 754があり、単精度(32ビット)と倍精度(64ビット)などが定義されています。
固定小数点数: 小数点の位置を固定し、整数と同様にビット列で表す方式です。一定の桁数で表現できるため、簡単ですが表現範囲が制限されます。

このように、数値をビット列で表現する方式はいくつか存在します。表現範囲、精度、演算の効率など、用途に応じて適切な方式を選ぶ必要があります。

文字表現

コンピュータでは文字をビット列として表現する必要があります。主な文字表現方式は以下のとおりです。

ASCIIコード: 7ビットで英数字、一部の記号などを表現する文字コード体系です。コード値0x00から0x7Fの範囲で128文字が割り当てられています。メモリ効率が良く、英語中心の環境で広く利用されてきました。
ISO/IEC 8859コード: 8ビットを使うことで、アクサン付き文字などASCIIでカバーできない欧州言語の文字を追加した文字コード体系です。複数の異なるコード体系があり、ISO/IEC 8859-1がラテン文字をサポートしています。
Unicode: 世界中の文字を統一的にエンコーディングする業界標準の文字コード体系です。最大21ビット(UTF-8では最大4バイト)で約14万文字が割り当てられています。UTF-8、UTF-16、UTF-32などの可変長エンコーディング方式が定義されています。
JISコード、Shift-JISコード、EUC-JPなど: 日本語を表現するための文字コード体系です。英数字をASCIIコード、残りの領域に日本語の文字を割り当てています。Unicodeの普及に伴い次第に使われなくなってきました。
GB18030、BIG5など: 中国語を表現する文字コード体系です。地域や規格によって複数の異なる表現方式が存在します。

このように、コンピュータで文字を表現するには様々な文字コードが使われてきました。言語の違いや文字の追加などの要求から、次第に高ビット長な文字コードが登場しています。特にUnicodeは文字の統一的な扱いを可能にした重要な技術です。

数値計算（演算方式と精度，近似解法と方程式ほか）

演算方式と精度

コンピュータでの数値計算は、基本的には足し算、引き算、掛け算、割り算の4則演算が適用されます。これらの演算は、ビット演算による加算器、乗算器などのハードウェア回路で高速に処理されます。

しかし、特に浮動小数点数の場合、有限の桁数で実数を近似表現するため、丸め誤差や打ち切り誤差が生じます。この誤差は、演算を重ねるごとに蓄積していきます。精度を確保するには、適切な有効桁数を確保する必要があります。

近似解法

多くの数値計算では、解析的な解を求めることが困難か不可能な問題に直面します。そのような場合、近似解を求める手法が用いられます。

ニュートン法、ニュートン・ラプソン法などの数値解析手法
モンテカルロ法などの確率的手法
陽的オイラー法、ルンゲ・クッタ法などの常微分方程式の数値解法

このように、問題の性質に応じて適切な手法を選ぶ必要があります。近似解なので一定の誤差を許容しなければならず、収束条件や打ち切り誤差の評価が重要になります。

方程式と最適化

連立方程式や非線形方程式の解を求める問題や、制約条件下での最適化問題なども、数値計算の対象となります。

ガウス・ザイデル法などの反復法
最小二乗法などの回帰分析手法
シンプレックス法などの最適化手法

数値計算では、入力データの値によっては解が発散したり、精度保証が難しくなるなどの問題に留意する必要があります。アルゴリズムの収束性、数値的安定性、計算量などを考慮した適切な手法の選択が重要です。

数理最適化

数理最適化とは、与えられた目的関数と制約条件の下で、最適な解を見つける問題を扱う分野です。様々な分野で応用されており、以下のようなタイプの問題があります。

線形計画問題: 目的関数と制約条件がすべて線形の場合です。生産計画、輸送問題、投資ポートフォリオ最適化などで重要です。代表的な解法にシンプレックス法があります。
非線形計画問題: 目的関数や制約条件の一部が非線形の場合です。工業プロセスの最適化、トラス構造設計、経路最適化などで現れます。ラグランジュ乗数法、KKT条件、内点法などが知られた解法です。
離散最適化問題: 解の値が離散的な場合です。施設配置、スケジューリング、組合せ最適化などの問題が含まれます。分岐限定法、メタヒューリスティクス(遺伝的アルゴリズム、シミュレーティッドアニーリングなど)が用いられます。
確率的最適化問題: 確率変数が含まれる場合です。ポートフォリオ理論、待ち行列理論、リスク管理などで現れます。ストールの方程式、シナリオ解析、モンテカルロ法などが利用されます。
多目的最適化問題: 複数の目的関数を同時に最適化する問題です。目的関数間でトレードオフが生じます。パレートフロンティアやスカラー化手法などが用いられます。

目的関数の形状や制約条件次第で、適切な解法が異なります。問題を正しくモデル化し、解の性質を理解することが重要です。最適化技術は、多くの産業分野で生産性や効率性の向上に貢献しています。

情報と理論

論理演算

論理演算とは、真理値(真または偽)を扱う演算のことです。コンピュータでは論理演算がデータ処理の根幹を成しており、ハードウェアとソフトウェアの両面で重要な役割を果たしています。

論理積(AND): 2つの命題が共に真の時だけ真となる演算です。A・Bと表し、AとBが共に真の時だけ真になります。ハードウェアでは集積回路の論理ゲートで実現されます。
論理和(OR)

2つの命題のいずれかが真であれば真となる演算です。A+Bと表し、AまたはBが真であれば真になります。ハードウェアの論理ゲートで実現されます。

論理否定(NOT): 命題の真理値を反転させる演算です。ÂまたはA'と表します。真を偽に、偽を真に反転させます。
排他的論理和(XOR): 2つの命題の真理値が異なる時だけ真になる演算です。A⊕Bと表します。パリティ計算などに用いられます。

論理演算は、プログラムの条件分岐、論理回路の設計、ブール代数などで不可欠です。NANDゲートやNORゲートなど、他の論理ゲートは基本的な論理演算の組み合わせで構成できます。論理演算を基礎とすることで、コンピュータは複雑な処理を行えるようになります。

符号理論

符号理論は、データの信頼性を確保するための理論体系です。通信路やストレージ媒体におけるノイズや障害による誤りを検出・訂正する仕組みを提供します。

パリティ検査: 最も単純な誤り検出方式で、データのビットに対してパリティビット(偶数性または奇数性を示すビット)を付加します。受信側でパリティを確認することで、1ビットの誤りを検出できます。
ハミング符号: パリティ検査を拡張し、複数ビットの誤り検出と1ビット訂正が可能な符号化方式です。データビットにいくつかの冗長ビットを付加します。ハミング距離に基づいて誤り訂正を行います。
CRC符号: cyclicコードの一種で、データ全体に対して残余を求めることで誤りを検出する方式です。データ転送時の誤り検出によく利用されています。残余を求めるための生成多項式が重要なパラメータとなります。
BCH符号: 多数の誤りに対して、高能力な訂正が可能な符号です。コンピュータメモリへの実装例があります。構造化された冗長ビットパターンを利用します。
RS符号: BCH符号の特殊な種類で、バースト誤りに強い符号です。CD、DVDなどの光ディスクに利用されています。有限体上の多項式を利用した符号化法です。

このように、符号理論では様々な誤り検出・訂正方式が考案されており、用途に応じて適切な方式を選択することが重要です。これらの理論を基に、信頼性の高い高密度データ伝送や記憶が可能になっています。

述語論理

述語論理は、命題論理を拡張した論理体系です。個々のオブジェクトとそれらの性質や関係性を表現できるため、より複雑な推論が可能になります。

構文

述語論理は、以下の要素から構成されます。

個体変数: オブジェクトを表す変数(x, y, zなど)
個体定数: 特定のオブジェクトを表す定数(ソクラテス、アテネなど)
述語記号: オブジェクトの性質や関係を表す記号(P(x)、Q(x, y)など)
論理連結詞: 命題論理の連結詞(¬, ∧, ∨, →, ↔)
量化記号: すべての(∀)、存在する(∃)

意味論

述語論理式の意味は、解釈によって与えられます。解釈とは、述語記号や個体定数に具体的な関係や個体を対応させる構造です。この解釈の下で命題が真か偽かが決まります。

推論規則

命題論理の推論規則に加え、述語論理には以下の推論規則があります。

全称具体化: ∀xP(x) から P(a) を導出
存在具体化: ∃xP(x) から P(a) を導出(aは新しい個体定数)
全称一般化: P(x) から ∀xP(x) を導出(xは任意の個体変数)

述語論理は、数学の定理証明や知識ベースシステム、プログラム検証などの分野で重要な役割を果たしています。命題論理より豊かな表現力があり、より高度な推論が可能になります。

時相論理

時相論理(テンポラルロジック)は、時間の概念を取り入れた論理体系です。システムの振る舞いや状態の変化を、時間の流れに沿って記述・推論できるようになります。

線形時相論理(LTL -- Linear Temporal Logic)

時間を離散的な一次元の直線として扱う論理体系です。将来のある時点で性質が満たされるか、無限に性質が繰り返し満たされるかなどを表現できます。

記号例: □P(常にPが成り立つ)、◇P(最終的にPが成り立つ)、X P(次の状態でPが成り立つ)

分岐時相論理(CTL -- Computation Tree Logic)

時間を木構造としてモデル化します。現在の状態から複数の可能な未来が存在し、それらの経路を分岐として捉えます。

記号例: AGP(全ての経路で□Pが成り立つ)、EFP(ある経路で◇Pが成り立つ)

時相論理は主に以下の分野で応用されています。

プログラム検証: 並行プログラムやリアクティブシステムの正しい動作を保証するための検証に利用されます。モデル検査や定理証明への応用があります。
ハードウェア設計検証: ハードウェア回路の仕様をLTL/CTLで記述し、設計の正しさをモデル検査で検証します。
テンポラルデータベース: 時間軸上のデータの変化を扱うデータベース分野で、時間的な性質を表現するクエリ言語として用いられます。

このように、時相論理は時間軸上のシステムの性質を論理的に扱えるため、さまざまな分野で活用されています。とくにシステムの信頼性・安全性を確保する上で、重要な理論的基礎となっています。

状態遷移

状態遷移は、システムの状態がある条件のもとで次の状態へと移り変わる概念です。コンピュータシステムや並行プロセスのモデル化、設計検証などで重要な役割を果たします。

有限状態機械(FSM

Finite State Machine)

状態の集合と、状態間の遷移によって表現されるモデルです。各遷移には条件(入力など)が関連付けられています。FSMには以下の種類があります。

決定的FSM: 特定の現在状態と入力に対して、確定的に次の状態が決まる
非決定的FSM: 複数の次の状態が存在し得る
Moore機械: 出力は現在状態のみに依存
Mealy機械: 出力は現在状態と入力の両方に依存

状態遷移システム: より一般的なモデルで、状態と状態遷移関係から構成されます。状態は値の割り当てによって表現されます。FSMは状態遷移システムの特殊な場合に相当します。
状態遷移図: FSMや状態遷移システムを視覚的に表現する図です。状態を円で表し、矢印で遷移関係を示します。各遷移にはラベル(入力/出力など)が付けられます。
状態探索と到達可能な状態: 初期状態から出発し、可能な遷移をたどって到達できる状態の集合を求めることが重要です。breadth-first searchなどのグラフ探索アルゴリズムが用いられます。

状態遷移は、プロトコル設計、ハードウェア設計、プログラム検証など多岐にわたる分野で利用されています。モデルチェッキングツールでFSMを検証することで、システムの性質を保証できます。状態爆発が課題の1つですが、様々な対処法が研究されています。

計算量理論

計算量理論は、計算問題を解くためのアルゴリズムの効率性を分析・評価する理論体系です。具体的には、アルゴリズムが要する計算資源(時間・空間)の量を明らかにし、計算複雑さを理論的に捉えます。

時間計算量

アルゴリズムの実行にかかる時間的コストです。入力サイズnに対する演算回数の増加の仕方で表します。

例: O(1)定数時間、O(log n)対数時間、O(n)線形時間、O(n log n)、O(n^2)平方時間、O(2^n)指数時間

空間計算量

アルゴリズムが必要とするメモリ使用量のことです。同様に入力サイズに対する関数で表されます。

例: O(1)定数空間、O(n)線形空間、O(n^2)平方空間

計算量のオーダー記法: 大域的な挙動を捉えるため、入力が十分大きい場合の主要な項のみを扱う手法です。ビッグオー記法O(f(n))が代表的です。
P問題とNP問題: 決定性アルゴリズムによる多項式時間計算可能な問題がP問題、非決定性アルゴリズムによる多項式時間検証可能な問題がNP問題です。NP完全問題は最も難しいNP問題の1つです。
計算量クラス: 同種の時間・空間計算量を持つ問題を集めた分類です。P、NP、PSPACE、EXPTIMEなどが知られています。

計算量理論により、アルゴリズムの理論的な効率性が明らかになります。効率の良いアルゴリズムを設計したり、問題の計算複雑さから適切なアルゴリズムを選択できます。また、P対NPの問題なども大きな課題となっています。

形式言語理論（BNF、ポーランド表記法）

形式言語理論は、文字列の集合であるフォーマル言語の数学的な研究を行う分野です。プログラミング言語の構文規則の定義や、オートマタ理論、計算機科学の理論的基礎を与えます。

BNF (Backus-Naur Form)

BNFは、プログラミング言語の文法規則を記述するためのメタ構文記法です。以下のような構文から成ります。

終端記号: 文字や記号など、それ以上分解できない最小単位
非終端記号: さらに展開される記号

-:; 産生規則: 非終端記号をどのように展開するかを示す規則

例

<exp> ::= <exp> + <term> | <term>  
<term> ::= <term> * <factor> | <factor>
<factor> ::= ( <exp> ) | 数値

ポーランド記法

ポーランド記法は、演算子が演算対象の前(前置記法)または後(後置記法)に現れる数式の表記法です。通常の中置記法と比べ、演算の優先順位を明示する括弧が不要になります。

前置記法(ポーランド記法)の例

+ 3 5  (= 3 + 5)
* + 3 5 7 (= (3 + 5) * 7)

後置記法(逆ポーランド記法)の例

3 5 +  (= 3 + 5)
3 5 + 7 * (= (3 + 5) * 7)

ポーランド記法は、RPN(Reverse Polish Notation)と呼ばれ、電卓などで使われてきました。また、コンパイラの中間表現としても利用されます。

形式言語理論は、プログラミング言語の構文定義や処理系の設計に不可欠な理論基盤を与えています。

集合論

集合論は、数学の基礎理論の一つであり、集合という概念を研究対象とする分野です。コンピュータ科学においても、集合論の概念は理論的基盤として重要な役割を果たしています。

集合と要素

集合とは、ある性質を満たすオブジェクトの集まりです。集合に含まれるオブジェクトを要素と呼びます。集合は{ }で表され、要素はカンマで区切られます。例: A = {1, 2, 3}

集合演算

和集合(AとB): AとBの要素を併せた集合
積集合(AかつB): AとBの共通する要素からなる集合
差集合(AからBを除いた集合)
補集合: ある基となる全体集合からある集合の要素を除いた集合

集合の関係

等しい: 要素が完全に同じ
部分集合: ある集合の全ての要素が他の集合に含まれる関係

演算の性質

可換律、結合律、分配律など、代数的な性質が成り立つ

集合の表記法

積記号で要素を列挙: {1, 2, 3, ...}
内包表記: {x | xは3の倍数}
集合構成演算: A x B = {(a, b) | aはAの要素、bはBの要素}

無限集合

有限集合ではなく無限の要素を持つ集合(自然数の集合など)

集合論の概念は、論理学、データ構造、プログラム仕様記述などコンピュータ科学の様々な分野で活用されています。コンピューティングにおける理論的基盤を与えています。

ソフトウェア開発技術者/コンピュータ科学基礎

目次

情報の基礎理論

数値表現・データ表現

基数変換

数値表現

文字表現

数値計算（演算方式と精度，近似解法と方程式ほか）

数理最適化

情報と理論

論理演算

符号理論

述語論理

時相論理

状態遷移

計算量理論

形式言語理論（BNF、ポーランド表記法）

集合論

データ構造とアルゴリズム

データ構造

木構造

リスト

スタック

キュー

アルゴリズム

整列

探索

再帰

グラフ

文字列処理

アルゴリズム記述 =

疑似コード

流れ図