# m, nが整数の場合。
# (1)
(a**m) * (a**n) = a**(m + n)
→ (2**3) * (2**2) = 2**5

# (2)
a**m / a**n =  a**(m - n)
→ (2**3) / (2**2) = 2**1

# (3)
(a**m)**n = a**m*n
→ (2**3)**2 = 2**(3*2)

文字コード

コンピュータでは文字の 1 つ 1 つに特定の 2 進数が割り当てられていて、文字という情報をコード化している。

名称	意味
`ASCIIコード`	英数字と特殊文字のみ。漢字・かなに関する規定はない。
`シフトJISコード`	ASCII コードと漢字・かなが混在可能。
`EUC`	UNIX や Linux で用いられる文字コード。漢字・かなが使用可能。
`UNICODE`	世界の文字の多くを１つの体系で表現するコード。UTG-8 は UNICODE の符号化方式の 1 つ。

基数変換

基数:各桁の重み付けの基本となる数。(10 進数の基数は 10、2 進数の基数は 2、8 進数の基数は 8…)
基数変換:ある進数で表していた数を別の進数に直す事。(2 進数 →10 進数、8 進数 →10 進数)

# 基数の重み
小数点を基準に左へ N**0, N**1, N**2...
小数点を基準に右へ N**-1, N**-2...

例)2 進数の重みの遷移

2**3	2**2	2**1	2**0	.	2**-1	2**-2	2**-3	2**-4

10 進数、2 進数、8 進数、16 進数の関係は以下の表のようになる。

10 進数	2 進数	8 進数	16 進数
0	0	0	0
1	1	1	1
2	10	2	2
3	11	3	3
4	100	4	4
5	101	5	5
6	110	6	6
7	111	7	8
8	1000	10	8
9	1001	11	9
10	1010	12	A
11	1011	13	B
12	1100	14	C
13	1101	15	D
14	1110	16	E
15	1111	17	F
16	10000	20	10

N 進数から 10 進数の基数変換

各桁に N 進数の重みを掛けて足す。

例)2 進数から 10 進数

101.101
を上記の基数の重みに従って変更すると、
(1*4)+(0*4)+(1*2).(1*1/2)+(0*1/4)+(1*1/8)
これを足し合わせると10進数5.625が求められる。

10 進数から N 進数の基数変換

(整数) 10 進数の整数部を 2 進数で表すには、以下のように 2 で割って、あまりを下から並べる。

(少数) 10 進数の少数部を 2 進数で表すには、以下のように各少数に 2 を掛けて、整数部を並べる。

10 進数 →N 進数変換ルール

(整数部): Nで割って下から余りを並べる。
(少数部): Nを掛けて順に整数を並べる。

2 進数から 8 進数、16 進数への変換

2 進数から 8 進数への変換の場合は以下のように、小数点を基準に 3 桁ずつ区切ってそれぞれを 8 進数で表す。(3 桁にならない場合は 0 を補う。)
2 進数から 16 進数への変換の場合は以下のように、小数点を基準に 4 桁ずつ区切ってそれぞれを 16 進数で表す。(4 桁にならない場合は 0 を補う。)

補数表現と固定少数点表示

補数:「ある数」を「決められた数」にするために「補う数」の事。(例:10 に対する３の補数は７)
補数を用いる事でマイナス記号をしようせず、負の数の表現ができる。

# 補数で負の数を表現する例

以下のような計算をしたい場合、

15 - 3 = 12

15は2桁の数字なので100がベースとなり、3の100に対する補数は97なので、97を15に足す。

15 + 97 = 112

ここで、桁上がりした左端の1を取り除くと、答えである12が得られる。

上の式を分解すると以下のようになっている。

15 + (100 - 2) = (100 + 12)

それぞれ100を取り除くと元の式と同じになっている事がわかる。

つまり上記では負の記号を用いず-3を表している。

2 進数の補数

2 進数には以下の２つの補数がある。

1の補数:足しても桁上がりしない数のうち最大の数。
2の補数:足す事で桁上がりさせる数。

1 の補数の計算

1の補数はある 2 進数のビットを反転する事で求められる。

# 1の補数の計算例

0101の1の補数は1010となる。

2 の補数の計算

ビットを反転する事で求めた1の補数に 1 を加える事で求められる。

# 2の補数の計算例

0101の1の補数は1010となる。

↓ (これに1を加える。)

1011が0101の2の補数となる。

固定小数点

コンピュータ内部の数値表現方法には固定少数点表示と有働小数点表示が存在する。

固定小数点表示:小数点があらかじめ決められた位置に固定されている表現方式。

浮動小数点表示

浮動小数点表示:実数を M ×B**e の形で表したもの。(例えば、十進法で 12345.67 を 1.234567×10**4 と表せる。)

ここで M の部分を仮数部,B の部分を基数、そして e の部分は指数と呼ばれます。
浮動小数点表示では指数を使用する事で、大きな数や小さな数を少ないビット数で表現できる。

以下の様にして指数を用いて同じ数を別の方法で表現する。

123 * 10**0
12.3 * 10**1
1.23 * 10**2
0.123 * 10**3

上記の様に小数点の位置がふわふわと浮いて移動している様に見える事から、浮動小数点表示と呼ばれる。

【基本情報】浮動小数点表示【おぼえがき】 : 日々、徒然プログラミング。

正規化:仮数部と指数部を調整して一意に決める事。

誤差

誤差:コンピュータ内部では数値を指定されたビット数で表しているので、それによって発生する真の値との間に差のこと。
桁あふれ誤差:演算結果がコンピュータの表現できる範囲を越える事によって発生する誤差。

※表現できる最大値を越える事をオーバーフロー、最小値を越える事をアンダーフローと呼びます。

丸め誤差:指定された有効桁数で演算結果を表すために、切り捨て、切り上げ、四捨五入などを行うために発生する誤差。
桁落ち:絶対値のほぼ等しい 2 つ数の差を求めた時、有効桁数が減るために発生する誤差。
情報落ち:絶対値の非常に大きな数と小さな数の加算・減算を行なった時、小さい数が演算結果に反映されないために発生する誤差。
打ち切り誤差:浮動小数点数の計算処理の打ち切りを、指定した規則で行うことによって発生する誤差。

シフト演算

シフト演算:左右に桁をずらす事で簡単に乗算や除算を行う操作の事。
論理シフト:符号を考慮せず、左シフト・右シフト共にあふれたビットは捨てられ、空いたビットには 0 が入る。

算術シフト:符号を考慮してシフトを行う。

算術左シフト:符号ビットはそのままの位置にとどまる。あふれたビットは捨てられ、空いたビットには 0 が入る。
算術右シフト:符号ビットはそのまま、あふれたビットは捨てられ、空いたビットには符号と同じビットが入る。

計測・制御

アナログとデジタル

アナログデータ:数や量を連続的な物理量（長さ・角度・電流など）で表現する方式。
デジタルデータ:コンピューターで処理可能な 0 と 1 の 2 進法で書き換えられた映像・音・数値・テキストなどのデータ。
A/D変換:アナログデータをデジタルデータに変換する事。

PCM 方式(パルス符号変調方式)

PCM(パルス符号変調方式):A/D 変更を行う代表的な方法。

PCMでは標本化→量子化→符号化の順に変換を行う。

標本化(サンプリング):時間的に連続したアナログ信号の波形を、一定の時間感覚で測定する。
量子化:測定した信号をあらかじめけめられた一定の間隔(2,8,216..等)に区切り数値化する。
符号化:量子化された値を 2 進数のデジタル符号に変換する。

制御技術

エアコンでで温度の上げ下げをする際に、センサが計測した室温をアナログ電圧として出力し、コンピュータがデジタルデータに変換して設定した値と比較している。これがコンピュータ制御の例。

コンピュータ制御には主に以下の要素を用いる。

A/Dコンバータ:アナログ電気信号を、コンピュータが処理可能なデジタル信号に変える。
センサ:物理量を検出して、電気信号に変える。
アクチュエータ:コンピュータが出力した電気信号を回転運動・直線運動に変える。(シリンダ・モータなど。)

オートマトン

オートマトン:、計算機の構造や動作を抽象化したモデルの一つで、内部に固有の状態と、状態を変化させる規則の集合を持ち、外部からの入力に応じて状態を変化させるもの。

論理演算と論理回路

論理演算:1 と 0 という２つの値を扱う演算。(論理和(OR), 論理積(AND), 否定(NOT)が基本。)
論理回路:論理演算を実際に行う回路。(MIL記号で図式化したり、論理表で表されたりする。)

基本回路

論理和回路(OR回路):入力(A,B)の少なくとも一方が 1 であれば、出力(A+B)は 1 になる回路。

少なくとも一方が1ならば1

論理積回路(AND回路):入力(A,B)の両方が 1 であれば出力(A・B)は 1 になる回路。

AとB両方が1ならば1

否定回路(NOT回路):入力(A)が 0 であれば出力(A)は 1、入力(A)が 0 であれば出力(A)は 0 になる回路。

0ならば1、1ならば0

基本回路組み合わせ

排他的論理回路(EOR回路/XOR回路):入力(A,B)が異なれば出力は 1 になる回路。

AとBで異なれば1

否定論理和回路(NOR)回路:論理和と否定の組み合わせ。

AとBが両方0なら1
(論理和の否定)

否定論理積:論理積と否定の組み合わせ。

AとB両方が1ならば0、それ以外は1
(論理積の否定)

半加算器・全加算器

基本的な回路の組み合わせで加算を実現する回路を作る事が出来ます。

加算器:2 進数の加算を行う回路の事。

加算器には以下の 2 種類が存在する。

(1)半加算器:
- 下位桁からの桁上がりを考慮しない。
- 上位桁への桁上がりを考慮する。
- 論理和(OR)と排他的論理和(EOR回路/XOR回路)の組み合わせで実現する。

(2)全加算器:
- 下位桁からの桁上がり・上位桁への桁上がりの両方を考慮する。
- 半加算器と論理和(OR)の組み合わせで実現する。

アルゴリズム

アルゴリズム:何らかの問題を有限の時間で解くための手順の事。

フローチャートとアルゴリズム

アルゴリズムを表現する手法にはフローチャート(流れ図)と疑似言語が存在する。

フローチャート

以下の記号を用いてフローチャートを作成しアルゴリズムを記述する事ができる。

疑似言語

疑似言語を用いる事で実際のプログラミング言語で記述する場合と近いイメージで記述できる。

配列

データ構造:データの集まりをコンピュータプログラムで処理する際に扱いやすいように、一定の形式で格納したもの。
配列:同じデータ型の要素が集まったデータ構造。
インデックス(添字):要素が配列の中で何番目かを表す数字。

2次元配列の場合は行と列を区別する 2 つのインデックスが必要となる。

リスト構造

リスト:データ部とポインタ部で構成され、ポインタを辿ることによってデータを取り出す事ができるデータ構造。

リスト構造の種類

リスト構造にはポインタの指す方向によって以下の種類に分類される。

単方向リスト: 次のデータへのポインタを 1 つだけ持っているリスト構造。

双方向リスト: 次のデータへのポインタの他に、前へのデータのポインタを持っているリスト構造。

環状リスト: ポインタによって、データが環状に連結されているリスト構造。

キューとスタック

キュー(Queue)

キュー(Queue):格納した順序でデータを取り出す事ができるデータ構造。

この様な特徴をFIFO(First In First Out)と呼び、最初に格納したデータは最初に取り出す事が出来る。

エンキュー(enqueue):データをキューに格納する事。
デキュー(dequeue):キューからデータを取り出す事。

スタック(Stack)

スタック(Stack):格納した順序とは逆の順番でデータを取り出す事ができるデータ構造。

この様な特徴をLIFO(Last In First Out)と呼び、最後に格納したデータを最初に取り出す事が出来る。

プッシュ(push):データをスタックに格納する事。
ポップ(pop):スタックからデータを取り出す事。

木構造(ツリー構造)

木構造(ツリー構造):階層の上位から下位に節点を辿る事でデータを取り出す事が出来るデータ構造。

下記の図からもわかる様に、○の部分を節(ノード)、節と節を繋いだ-を枝(ブランチ)、最上位の節を根(ルート)、最下位の節を葉(リーフ)と呼ぶ。

また、木構造には親子関係があり、上位の節を親、下位の節を子といい、節にぶら下がっている部分を部分木、中でも左側にぶら下がっているものを左部分木、右のものを右部分木と呼ぶ。

2 分木(binary tree)の種

2分木(binary tree):全ての枝の分岐が 2 つ以下である木構造。

以下の様な種類が存在する。

完全２分木(complete binary tree):根から葉までの深さが全て等しい２分木。(深さが 1 だけ深い葉があり、木全体の左から詰められているものも完全 2 分木とされる。)

2分探索木(binary search tree):各節において「左の子＜右の子」という関係を持った 2 分木。

ヒープ木:各節において「親＞子」または「子＞親」という関係を持った完全 2 分木。(データを整列するのに使用される。)

「親＞子」の場合は根の値が最大値となり、「子＞親」の場合は根が最小値となる。

逆ポーランド記法(Reverse Polish Notation, RPN):2 分木を使用して算術式を表記する方法の 1 つ。

逆ポーランド記法と木構造の絵 - Qiita

データの整列(ソート)

整列(ソート):ある規則に従ってデータを昇順または降順で並べ換える事。
昇順:データの値の大きなものから小さなものに並び替える事。
降順:データの値の小さなものから大きなものに並び替えること。

基本交換法(Bubble sort)

基本交換法(バブルソート):隣り合う要素を比較し、逆順であれば交換して、整列を行う方法。

基本選択法(Selection sort)

基本選択法(selection sort):対象の集合から最も小さい要素を順次取り出して、端においていく整列方法。

基本挿入法(Insertion sort)

基本選択法(Insertion sort):対象集合から要素を順次取り出し、それまでにソートを行なった要素の集合に順序関係を保つ様挿入して整列を行う方法。

計算量(オーダ)

O(オーダ):プログラムの計算量を表すのに用いられる。

基本交換法(Bubble sort)・選択ソート(Selection sort)・挿入ソート(Insertion sort)の計算量はO(n**2).

その他のソート

シェルソート(改良挿入法)

シェルソート - Algoful

クイックソート

クイックソート - Algoful

ヒープソート

ヒープソート - Algoful

データの探索(Search)

データの探索(search):配列などを使用して目的のデータを探し出すことをデータの探索と言います。

線形探索法(Linear search)

線形探索法(Linear search):配列の先頭から順番に目的のデータを調べていく方法。

番兵法:探索したい目的のデータを配列の最後尾に追加する方法。(線形探索法で追加した要素まで値が発見できない場合、値は存在しなかったことになる。)

# 線形探索法の計算量

最大探索回数: N回
平均探索回数: (N+1)/2

計算量: O(N)

2 分探索法

2分探索法(Binary search):リストや配列に入ったソート済のデータに対して、中央値を基準にどんどん探索範囲を絞って効率的に探索を行うアルゴリズム。
二分探索法（バイナリサーチ） - Algoful

ハッシュ探索法

ハッシュ探索法(Hash search):キーの間数値によって格納先のアドレスを算出し、直接探索する方法。(O(1) という圧倒的に小さい計算量で探索を行える)
ハッシュ探索

情報の基礎理論

Table of Contents

情報の表現

情報の単位

情報量を表す接頭語

ビット数と表現できる情報量

指数計算