「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。
目次 †
概要 †
基礎理論 †
離散数学 †
連続でない、とびとびの対象をあつかう数学のこと
基数(XX進数 †
2-XX進数
- 10進数をXXで因数分解した結果を逆に読む。
- 4の二進数は、100なので...、
2 )4...0
---
2 )2...0
---
1
集合 †
─────
A∪B∪C = 空集合
https://upload.wikimedia.org/wikipedia/commons/4/42/Inclusion-exclusion.svg
カルノー図 †
論理回路などにおいて論理式を簡単化するための表
応用数学 †
相関係数 †
- 標本点が
- 一直線上にある:線形(linear)
- 右上がり(傾きが正):相関係数=+1
- 右下がり(傾きが負):相関係数=-1
- 一直線上にない:非線形(nonlinear)
- 外れが多い程、相関係数は0に近くなる。
- 相関係数=0なら無相関
M/M/1 待ち行列モデル †
昨今queueが冗長化、多重化されているので、結構、実践向きでなかった。
- 分布
- 要求の発生の分布はランダム
- 平均到着率(所与の時間内での生起回数の確率)はポアソン分布
- サービス時間(生起期間の確率)は指数分布
- 前提条件
- 到着順に処理される。
- 末尾に並び、途中で抜けない。
情報に関する理論 †
データ可逆圧縮方式 †
- ハフマン符号(可変長二進符号)
- よく出現する文字には短いビット列を、
- あまり出現しない文字には長いビット列を
割り当てる
BNF †
バッカス・ナウア記法
- 文脈自由文法を定義するのに用いられるメタ言語
- 現在はBNFを拡張したEBNF (Extended BNF) が一般的。
- EBNFは正規表現を用いてより簡単に記述でき、
ASN.1、SQL、XMLなどの構文定義にも利用されている。
有限オートマトン †
状態遷移表
現在状態→ 入力 ↓ | 状態A | 状態B | 状態C |
入力X | 状態...へ遷移 | 状態...へ遷移 | 状態...へ遷移 |
入力Y | 状態...へ遷移 | 状態...へ遷移 | 状態...へ遷移 |
入力Z | 状態...へ遷移 | 状態...へ遷移 | 状態...へ遷移 |
通信に関する理論 †
誤り検出/訂正 †
- 誤り検出/訂正
- 誤り検出のための符号: 誤り検出符号 (EDC, error detecting code)
- パリティ・ビットは、最も単純な誤り検出符号
- 奇数個のビットの誤りしか検出できない。
- 訂正のための符号: 誤り訂正符号 (ECC, error correcting code)
- 垂直水平パリティ符号では、1ビットの誤りを検出可能。
- ハミング符号は、より効率的だが訂正力は高くない。
- 奇数(odd) or 偶数(even)パリティ
- 奇数(odd)パリティ
- データとパリティの1の数を数えて奇数になるようにする。
- ビット列中に含まれる「1」の個数が奇数個なら「0」を設定する。
- 偶数(even)パリティ
- データとパリティの1の数を数えて偶数になるようにする。
- ビット列中に含まれる「1」の個数が偶数個なら「0」を設定する。
計測/制御に関する理論 †
- ジャイロは角速度センサ。
- 加速度センサは反力センサ。
アルゴリズム・プログラミング †
データ構造 †
ポーランド記法 †
- 中置記法
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
木構造の走査法 †
- 前順・先行順・前置順・行きがけ順
2分探索木のコピーを作る。構文木からポーランド記法の表現を得る。
- 根ノードを調査する。
- もしあれば、左の部分木を前順走査する。
- もしあれば、右の部分木を前順走査する。
- 間順・中間順・通りがけ順
2分探索木では走査順がソートされた順序になる(多分木では定義されない)。
- もしあれば、左の部分木を間順走査する。
- 根ノードを調査する。
- もしあれば、右の部分木を間順走査する。
- 後順・後行順・後置順・帰りがけ順
- もしあれば、左の部分木を後順走査する。
- もしあれば、右の部分木を後順走査する。
- 根ノードを調査する。
アルゴリズム †
参考 †