高度午前 - 基礎理論のバックアップ(No.5)

バックアップ一覧
差分を表示
現在との差分を表示
ソースを表示
高度午前 - 基礎理論へ行く。
- 1 (2019-03-17 (日) 16:49:33)
- 2 (2019-03-17 (日) 18:46:28)
- 3 (2019-03-17 (日) 22:38:08)
- 4 (2019-03-24 (日) 21:05:23)
- 5 (2019-03-30 (土) 16:54:40)
- 6 (2019-05-13 (月) 23:48:45)
- 7 (2019-05-14 (火) 00:38:20)
- 8 (2019-05-14 (火) 08:53:44)
- 9 (2019-08-12 (月) 13:28:24)
- 10 (2020-05-01 (金) 03:06:19)

「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。

戻る

目次 †

↑

概要 †

↑

基礎理論 †

↑

離散数学 †

連続でない、とびとびの対象をあつかう数学のこと

参考
- 離散数学―離散数学とは？
  離散数学の入門知識を整理。問題もあり
  https://learning.zealseeds.com/contents/text/IPA/technology/risansuugaku/index.html#jump0

↑

基数(XX進数 †

2-XX進数

10進数をXXで因数分解した結果を逆に読む。
４の二進数は、100なので...、

2 )4...0
  ---
2 )2...0
  ---
   1

↑

演算精度 †

丸め誤差
打ち切り誤差
桁落ち
情報落ち

↑

集合 †

─────
Ａ∪Ｂ∪Ｃ = 空集合

https://upload.wikimedia.org/wikipedia/commons/4/42/Inclusion-exclusion.svg

参考
- Wikipedia
  - 集合の代数学
    https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E3%81%AE%E4%BB%A3%E6%95%B0%E5%AD%A6
  - 和集合
    https://ja.wikipedia.org/wiki/%E5%92%8C%E9%9B%86%E5%90%88
  - 差集合
    https://ja.wikipedia.org/wiki/%E5%B7%AE%E9%9B%86%E5%90%88
  - 積集合
    https://ja.wikipedia.org/wiki/%E5%85%B1%E9%80%9A%E9%83%A8%E5%88%86_(%E6%95%B0%E5%AD%A6)
  - 集合間の関係を表す記号
    https://ja.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E9%96%93%E3%81%AE%E9%96%A2%E4%BF%82%E3%82%92%E8%A1%A8%E3%81%99%E8%A8%98%E5%8F%B7
  - 論理演算
    https://ja.wikipedia.org/wiki/%E8%AB%96%E7%90%86%E6%BC%94%E7%AE%97

↑

カルノー図と論理式 †

論理回路などにおいて論理式を簡単化するための表

CD AB	00	01	11	10
00	1	0	0	1
01	0	1	1	0
11	0	1	1	0
10	0	0	0	0

カルノー図の論理式化
- 1が記入されている部分をグループ化
  - 隣り合ったチェックを四角形で囲む
  - 四隅の 4 ますがグループ化できる
- グループ化した部分を論理積の論理式で表す
- グループ内の共通項を抽出する。
- 共通項の論理和の論理式にする。

グループA

                _  _  _  _
AB=00、CD=00 -> A・B・C・D
                _  _     _
AB=00、CD=10 -> A・B・C・D
                _  _     _
                A・B・   D

グループB

                _     _
AB=01、CD=01 -> A・B・C・D
                _
AB=01、CD=11 -> A・B・C・D
                      _
AB=11、CD=01 -> A・B・C・D

AB=11、CD=11 -> A・B・C・D

AB=11、CD=01 ->    B・   D

参考
- カルノー図 - Wikipedia
  https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%AB%E3%83%8E%E3%83%BC%E5%9B%B3
- カルノー図とは―説明、やり方、練習問題（解答付き）。
  https://learning.zealseeds.com/contents/text/IPA/technology/risansuugaku/logical-operation/karnaugh-map/index.html

↑

応用数学 †

↑

相関係数 †

標本点が
- 一直線上にある：線形（linear）
  - 右上がり（傾きが正）：相関係数＝＋1
  - 右下がり（傾きが負）：相関係数＝－1
- 一直線上にない：非線形（nonlinear）
  - 外れが多い程、相関係数は０に近くなる。
  - 相関係数＝０なら無相関

参考
- 相関係数 - Wikipedia
  https://ja.wikipedia.org/wiki/%E7%9B%B8%E9%96%A2%E4%BF%82%E6%95%B0
  - https://upload.wikimedia.org/wikipedia/commons/d/d4/Correlation_examples2.svg

↑

M/M/1 待ち行列モデル †

昨今queueが冗長化、多重化されているので、結構、実践向きでなかった。

特徴

分布
- 要求の発生の分布はランダム
- 平均到着率（所与の時間内での生起回数の確率）はポアソン分布
- サービス時間（生起期間の確率）は指数分布

待ち行列
- 窓口は１つ。
- 長さに制限はない。

前提条件
- 到着順に処理される。
- 末尾に並び、途中で抜けない。

↑

情報に関する理論 †

↑

データ可逆圧縮方式 †

ハフマン符号（可変長二進符号）
- よく出現する文字には短いビット列を、
- あまり出現しない文字には長いビット列を

割り当てる

↑

BNF †

バッカス・ナウア記法

文脈自由文法を定義するのに用いられるメタ言語
現在はBNFを拡張したEBNF (Extended BNF) が一般的。
EBNFは正規表現を用いてより簡単に記述でき、
ASN.1、SQL、XMLなどの構文定義にも利用されている。

参考
- バッカス・ナウア記法 - Wikipedia
  https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%83%E3%82%AB%E3%82%B9%E3%83%BB%E3%83%8A%E3%82%A6%E3%82%A2%E8%A8%98%E6%B3%95

↑

有限オートマトン †

状態遷移表

現在状態→ 入力 ↓	状態A	状態B	状態C
入力X	状態...へ遷移	状態...へ遷移	状態...へ遷移
入力Y	状態...へ遷移	状態...へ遷移	状態...へ遷移
入力Z	状態...へ遷移	状態...へ遷移	状態...へ遷移

参考
- 有限オートマトン - Wikipedia
  https://ja.wikipedia.org/wiki/%E6%9C%89%E9%99%90%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3

↑

通信に関する理論 †

↑

誤り検出/訂正 †

誤り検出のための符号

誤り検出符号 (EDC, error detecting code)
- パリティ・ビットは、最も単純な誤り検出符号
- 奇数個のビットの誤りしか検出できない。

チェックサム
- 誤り検出符号の一種で、ワード列の個々のワードの総計の下位1ワードを符号値とする。
- 信頼性は低いが、99.5%以上の検出率がある上にアルゴリズムが簡単

CRC（巡回冗長検査）
- 誤り検出符号の一種で、生成多項式で除算した余りを検査データとして付加する。
- 主にデータ転送などに伴う偶発的な誤りの検出によく使われている。

誤り訂正のための符号

誤り訂正符号 (ECC, error correcting code)
- 高速のため、メモリ・ディスクで使用されている。
- 垂直水平パリティ符号では、1 bitの誤り検出/訂正が可能。
- ハミング符号では、誤り検出 2 bit / 訂正 1 bit(効率的だが訂正力は高くない)。

奇数(odd) or 偶数(even)パリティ
- 奇数(odd)パリティ
  - データとパリティの1の数を数えて奇数になるようにする。
  - ビット列中に含まれる「1」の個数が奇数個なら「0」を設定する。
- 偶数(even)パリティ
  - データとパリティの1の数を数えて偶数になるようにする。
  - ビット列中に含まれる「1」の個数が偶数個なら「0」を設定する。

参考
- Wikipedia
  - 誤り検出訂正
    https://ja.wikipedia.org/wiki/%E8%AA%A4%E3%82%8A%E6%A4%9C%E5%87%BA%E8%A8%82%E6%AD%A3
  - チェックサム
    https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%83%E3%82%AF%E3%82%B5%E3%83%A0
  - 巡回冗長検査
    https://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB
  - パリティ符号
    https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AA%E3%83%86%E3%82%A3%E3%83%93%E3%83%83%E3%83%88
  - ハミング符号
    https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%9F%E3%83%B3%E3%82%B0%E7%AC%A6%E5%8F%B7

↑

計測/制御に関する理論 †

↑

センサ †

ジャイロは角速度センサ。
加速度センサは反力センサ。

参考
- 加速度センサは重力を検知できない - nhara1942の日記
  http://d.hatena.ne.jp/nhara1942/20120512/1336783082
- ジャイロスコープ - Wikipedia
  https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A3%E3%82%A4%E3%83%AD%E3%82%B9%E3%82%B3%E3%83%BC%E3%83%97

↑

アルゴリズム・プログラミング †

↑

データ構造 †

↑

ポーランド記法 †

中置記法
```
1 + 2
```
ポーランド記法
```
+12
```
逆ポーランド記法
```
12+
```

逆ポーランド記法とスタックを使用した計算の例
- 中置記法
```
(3+4) * (1-2)
```
- 逆ポーランド記法
  順にpushしていき演算子で項をpopする。
  この際、項はpop順ではなくpush順に並べて計算する。
```
34+12-*
```
  - 3
  - 3, 4
  - 7
  - 7, 1
  - 7, 1, 2
  - 7, -1
  - -7

参考
- Wikipedia
  - ポーランド記法
    https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
  - 逆ポーランド記法
    https://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95

↑

木構造の走査法 †

幅優先探索

深さ優先探索

前順・先行順・前置順・行きがけ順
2分探索木のコピーを作る。構文木からポーランド記法の表現を得る。
- 根ノードを調査する。
- もしあれば、左の部分木を前順走査する。
- もしあれば、右の部分木を前順走査する。

間順・中間順・通りがけ順
2分探索木では走査順がソートされた順序になる（多分木では定義されない）。
- もしあれば、左の部分木を間順走査する。
- 根ノードを調査する。
- もしあれば、右の部分木を間順走査する。

後順・後行順・後置順・帰りがけ順
- もしあれば、左の部分木を後順走査する。
- もしあれば、右の部分木を後順走査する。
- 根ノードを調査する。

参考
- 木構造 (データ構造) - Wikipedia
  https://ja.wikipedia.org/wiki/%E6%9C%A8%E6%A7%8B%E9%80%A0_(%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)

↑

アルゴリズム †

↑

フローチャート †

アルゴリズムを問われた場合、
適当な値を当てハメて計算して結果を確認してみる。

ル-プには、終了条件を記載する。
- 前判定型ループ
- 後判定型ループ

↑

ハッシュ †

連想配列、連想リスト、連想コンテナ、辞書、ディクショナリ、ハッシュ、マップ

問題
- alphabetのASCIIコードを使用
- ハッシュ関数は10進数の1の桁
- 衝突する組み合わせは？
  # 0 1 2 3 4 5 6 7 8 9
  1 a b c d e f g h i j
  2 k l m n o p q r s t
  3 u v w x y z
- AのASCIIコードは65だが、
  A=1で計算しても結果は同じになる。

#	0	1	2	3	4	5	6	7	8	9
1	a	b	c	d	e	f	g	h	i	j
2	k	l	m	n	o	p	q	r	s	t
3	u	v	w	x	y	z

参考
- ハッシュ関数 - Wikipedia
  https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E9%96%A2%E6%95%B0

↑

探索手法 †

リスト探索
おそらく最も基本的な探索アルゴリズム

線形探索探索の前にソートしておく必要があり、
またランダムアクセスが可能でなければならない。
- 先頭から順に比較を行い、それが見つかれば終了する。
- 使用頻度順に並べれば、平均検索速度が向上する。

二分探索 = 2分探索木分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良い。
- 中央の値を見て、検索したい値との大小関係を用い、
- 検索したい値が中央の値の右にあるか、左にあるかを判断し、
  片側には存在しないことを確かめながら検索していく。

内挿探索
- 二分探索を改良した探索アルゴリズム。
- 目的のデータは恐らくこの辺りに集まっているだろうと予測して絞り込んで探索。

文字列探索
- クヌース-モリス-プラット法
- ボイヤー-ムーア文字列検索アルゴリズム
- エイホ-コラシック法
- ラビン-カープ文字列検索アルゴリズム
- Bitapアルゴリズム
- 全文検索

ハッシュ

木探索

グラフ探索固有
- 最短経路問題
  - ダイクストラ法
  - ベルマン-フォード法
- 最小全域木
  - プリム法
  - クラスカル法
- 最大フロー問題・最小カット問題
  - フォード・ファルカーソンのアルゴリズム
  - エドモンズ・カープのアルゴリズム
- 巡回セールスマン問題
  - 最近傍法
- 連結度
  - 最大隣接順序
  - 最小次数順序

参考
- Wikipedia
  - 探索
    https://ja.wikipedia.org/wiki/%E6%8E%A2%E7%B4%A2
  - 二分探索
    https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2
  - 線型探索
    https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%9E%8B%E6%8E%A2%E7%B4%A2
  - 文字列探索
    https://ja.wikipedia.org/wiki/%E6%96%87%E5%AD%97%E5%88%97%E6%8E%A2%E7%B4%A2

↑

比較ソート †

データの集合を一定の規則に従って並べる

安定ソート、内部ソートと外部ソート

安定ソート
同等なデータのソート前の順序が、ソート後も保存されるもの
- バブルソート
- 挿入ソート
- マージソート

内部ソートと外部ソート
- 内部ソート
  ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソート
- 外部ソート
  ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソート

比較ソート
個々の項目を比較演算で大小判定することを基本とするソート

バブルソート（安定ソート、内部ソート）
- 全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。
- これを要素数-1回繰り返すことでソートを行なう。
- 入れ替えが起こらなくなった時点で中断することができる。

挿入ソート（安定ソート、内部ソート）
- バブルソートより速い。
- 整列してある配列に追加要素を適切な場所に挿入する。
- ソート済みの状態の配列へのソート処理は非常に早い。

クイックソート（内部ソート）
- 適当な数（ピボットという中央値が望ましい）を選択
- ピボットより小さい数を前方、大きい数を後方に移動（分割）
- 最も高速だがデータの並びや数によって大きく異なる。

シェルソート（内部ソート）
- バブルソート、挿入ソートの一般化
- 間隔の離れた要素の組に対してソートを行い、
  比較する要素間の間隔を小さくしながらソートを繰り返す。
- 実行時間は、比較時に選ぶ間隔によって大きく異なる。

ヒープソート（内部ソート）
- 二分木データ構造の要素番号の規則からポインタ等の制御用データが不要
- 未整列リストの先頭から、データを入替て、二分ヒープ木を構築する。
- リスト先頭の二分ヒープ木からデータを取り出し、整列リストをリスト後方から作成。

マージソート（安定ソート）
- 大きい列を多数の列に分割し、整列しながらマージする（マージは並列化できる）。
- ボトムアップの分割統治法により、マージ後のリストも整列されている。

参考
- ソートを極める！〜なぜソートを学ぶのか〜 - Qiita
  https://qiita.com/drken/items/44c60118ab3703f7727f
- Wikipedia
  - ソート
    https://ja.wikipedia.org/wiki/%E3%82%BD%E3%83%BC%E3%83%88
  - バブルソート
    https://ja.wikipedia.org/wiki/%E3%83%90%E3%83%96%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88
  - 挿入ソート
    https://ja.wikipedia.org/wiki/%E6%8C%BF%E5%85%A5%E3%82%BD%E3%83%BC%E3%83%88
  - クイックソート
    https://ja.wikipedia.org/wiki/%E3%82%AF%E3%82%A4%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
  - シェルソート
    https://ja.wikipedia.org/wiki/%E3%82%B7%E3%82%A7%E3%83%AB%E3%82%BD%E3%83%BC%E3%83%88
  - ヒープソート
    https://ja.wikipedia.org/wiki/%E3%83%92%E3%83%BC%E3%83%97%E3%82%BD%E3%83%BC%E3%83%88
  - マージソート
    https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

↑

再帰 †

ローカル変数をスタック的に利用する。

以下は、階乗を返す再帰関数の例

fact(n)
{
  n = 0 then return 1
  else return n * fact(n - 1)
}

↑

近似計算 †

実際の値を数パターン入力して展開し、展開式と近似式から条件を考察。
展開式が難しいので、結局、一番簡単な n = 2 のケースぐらいしか扱えない。

近似式
```
       n
(1 + a)  = 1 + na
```

展開式

          2
1 + 2a + a
           2   3
1 + 3a + 3a + a
           2    3   4
1 + 4a + 6a + 4a + a
           2                    n-2  n-1 n
1 + na + n(n-1)a + ... + n(n-1)a + na + a

2乗がゼロに近くなるような条件。
≒ a が 1 と比べて非常に小さい。

↑

高度午前 - 基礎理論 のバックアップ(No.5)

目次 †

概要 †

基礎理論 †

離散数学 †

基数(XX進数 †

演算精度 †

集合 †

カルノー図と論理式 †

応用数学 †

相関係数 †

M/M/1 待ち行列モデル †

情報に関する理論 †

データ可逆圧縮方式 †

BNF †

有限オートマトン †

通信に関する理論 †

誤り検出/訂正 †

計測/制御に関する理論 †

センサ †

アルゴリズム・プログラミング †

データ構造 †

ポーランド記法 †

木構造の走査法 †

アルゴリズム †

フローチャート †

ハッシュ †

探索手法 †

比較ソート †

再帰 †

近似計算 †

参考 †

高度午前 - 基礎理論のバックアップ(No.5)