「.NET 開発基盤部会 Wiki」は、「Open棟梁Project」,「OSSコンソーシアム .NET開発基盤部会」によって運営されています。
目次 †
概要 †
基礎理論 †
離散数学 †
連続でない、とびとびの対象をあつかう数学のこと
基数(XX進数 †
2-XX進数
2 )4...0
---
2 )2...0
---
1
- 26進数（アルファベットが26文字）
123の26進数は、ET なんて言う問題が出る。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 |
| A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z |
26 )123...19
---
26 ) 4...4
---
0
集合 †
─────
Ａ∪Ｂ∪Ｃ = 空集合
https://upload.wikimedia.org/wikipedia/commons/4/42/Inclusion-exclusion.svg
カルノー図と論理式 †
論理回路などにおいて論理式を簡単化するための表
| # | CD | 00 | 01 | 11 | 10 | |
| AB | | ─
C | C | |
| 00 | ─
A | 1 | 0 | 0 | 1 | ─
B |
| 01 | 0 | 1 | 1 | 0 | B |
| 11 | A | 0 | 1 | 1 | 0 |
| 10 | 0 | 0 | 0 | 0 | ─
B |
| | ─
D | D | ─
D | |
- カルノー図の論理式化
- 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
応用数学 †
相関係数 †
- 標本点が
- 一直線上にある：線形（linear）
- 右上がり（傾きが正）：相関係数＝＋1
- 右下がり（傾きが負）：相関係数＝－1
- 一直線上にない：非線形（nonlinear）
- 外れが多い程、相関係数は０に近くなる。
- 相関係数＝０なら無相関
M/M/1 待ち行列モデル †
昨今queueが冗長化、多重化されているので、結構、実践向きでなかった。
- 分布
- 要求の発生の分布はランダム
- 平均到着率（所与の時間内での生起回数の確率）はポアソン分布
- サービス時間（生起期間の確率）は指数分布
- 前提条件
- 到着順に処理される。
- 末尾に並び、途中で抜けない。
情報に関する理論 †
データ可逆圧縮方式 †
- ハフマン符号（可変長二進符号）
- よく出現する文字には短いビット列を、
- あまり出現しない文字には長いビット列を
割り当てる
BNF †
バッカス・ナウア記法
- 文脈自由文法を定義するのに用いられるメタ言語
- 現在はBNFを拡張したEBNF (Extended BNF) が一般的。
- EBNFは正規表現を用いてより簡単に記述でき、
ASN.1、SQL、XMLなどの構文定義にも利用されている。
有限オートマトン †
- 状態遷移表
現在状態→
入力 ↓ | 状態A | 状態B | 状態C |
| 入力X | 状態...へ遷移 | 状態...へ遷移 | 状態...へ遷移 |
| 入力Y | 状態...へ遷移 | 状態...へ遷移 | 状態...へ遷移 |
| 入力Z | 状態...へ遷移 | 状態...へ遷移 | 状態...へ遷移 |
- 入力の下n桁がXで終わるときの状態は？と言う問題は、
どの状態から下n桁の入力を始めても最終的に、状態Yに遷移する。
通信に関する理論 †
誤り検出/訂正 †
- 誤り検出符号 (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」を設定する。
計測/制御に関する理論 †
- ジャイロは角速度センサ。
- 加速度センサは反力センサ。
アルゴリズム・プログラミング †
データ構造 †
ポーランド記法 †
- 逆ポーランド記法とスタックを使用した計算の例
- 中置記法
(3+4) * (1-2)
- 逆ポーランド記法
- 順にスタックにpushしていき演算子で項をpopする。
- この際、項はpop順ではなくpush順に並べて計算する。
34+12-*
- 計算の様子
- 3
- 3, 4
- 3, 4, +
- 7
- 7, 1
- 7, 1, 2
- 7, 1, 2, -
- 7, -1
- 7, -1, *
- -7
木構造の走査法 †
- 前順・先行順・前置順・行きがけ順
2分探索木のコピーを作る。構文木からポーランド記法の表現を得る。
- 根ノードを調査する。
- もしあれば、左の部分木を前順走査する。
- もしあれば、右の部分木を前順走査する。
- 間順・中間順・通りがけ順
2分探索木では走査順がソートされた順序になる（多分木では定義されない）。
- もしあれば、左の部分木を間順走査する。
- 根ノードを調査する。
- もしあれば、右の部分木を間順走査する。
- 後順・後行順・後置順・帰りがけ順
- もしあれば、左の部分木を後順走査する。
- もしあれば、右の部分木を後順走査する。
- 根ノードを調査する。
アルゴリズム †
フローチャート †
- アルゴリズムを問われた場合、
適当な値を当てハメて計算して結果を確認してみる。
ハッシュ †
連想配列、連想リスト、連想コンテナ、辞書、ディクショナリ、ハッシュ、マップ
- 問題
- 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で計算しても結果は同じになる。
探索手法 †
- 線形探索
探索の前にソートしておく必要があり、
またランダムアクセスが可能でなければならない。
- 先頭から順に比較を行い、それが見つかれば終了する。
- 使用頻度順に並べれば、平均検索速度が向上する。
- 二分探索 = 2分探索木
分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良い。
- 中央の値を見て、検索したい値との大小関係を用い、
- 検索したい値が中央の値の右にあるか、左にあるかを判断し、
片側には存在しないことを確かめながら検索していく。
- 内挿探索
- 二分探索を改良した探索アルゴリズム。
- 目的のデータは恐らくこの辺りに集まっているだろうと予測して絞り込んで探索。
- 文字列探索
- クヌース-モリス-プラット法
- ボイヤー-ムーア文字列検索アルゴリズム
- エイホ-コラシック法
- ラビン-カープ文字列検索アルゴリズム
- Bitapアルゴリズム
- 全文検索
- グラフ探索固有
- 最短経路問題
- 最小全域木
- 最大フロー問題・最小カット問題
- フォード・ファルカーソンのアルゴリズム
- エドモンズ・カープのアルゴリズム
- 巡回セールスマン問題
- 連結度
比較ソート †
データの集合を一定の規則に従って並べる
- 安定ソート
同等なデータのソート前の順序が、ソート後も保存されるもの
- 内部ソートと外部ソート
- 内部ソート
ソートされるデータの格納領域を変更して処理を進めていくIn-placeのソート
- 外部ソート
ソートされるデータの格納領域以外に O(n) 以上の一時的な記憶領域が必要であるソート
- 比較ソート
個々の項目を比較演算で大小判定することを基本とするソート
- バブルソート（安定ソート、内部ソート）
- 全ての要素に関して、隣接する要素と比較し順序が逆であれば入れ替える。
- これを要素数-1回繰り返すことでソートを行なう。
- 入れ替えが起こらなくなった時点で中断することができる。
- 挿入ソート（安定ソート、内部ソート）
- バブルソートより速い。
- 整列してある配列に追加要素を適切な場所に挿入する。
- ソート済みの状態の配列へのソート処理は非常に早い。
再帰 †
近似計算 †
- 実際の値を数パターン入力して展開し、展開式と近似式から条件を考察。
- 展開式が難しいので、結局、一番簡単な n = 2 のケースぐらいしか扱えない。
- 2乗がゼロに近くなるような条件。
≒ a が 1 と比べて非常に小さい。
参考 †
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
