Skip to content

DNET_AdvancedAMBasicTheory

Jump to bottom
nishi_74322014 edited this page Sep 11, 2026 · 1 revision

高度午前 - 基礎理論

概要

基礎理論（高度：午前Ⅰ、午前Ⅱ）

基礎理論

離散数学

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

基数(XX進数

2-XX進数

  • 10進数をXXで因数分解した結果を逆に読む。

  • 二進数
    ４の二進数は、100

    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
 A  B  C  D  E  F  G  H  I  J  K  L  M

13 14 15 16 17 18 19 20 21 22 23 24 25
 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

カルノー図と論理式

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

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

※ 元 Wiki の表では、各軸に以下の変数のラベルが添えられている。

  • 列（CD）：00・01 が ¬C、11・10 が C／00・10 が ¬D、01・11 が D

  • 行（AB）：00・01 が ¬A、11・10 が A／00・10 が ¬B、01・11 が B

  • カルノー図の論理式化

    • 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
--------------------------
                   B・   D

  • 参考

応用数学

相関係数

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

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

  • 特徴

    • 分布

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

    • 待ち行列

      • 窓口は１つ。
      • 長さに制限はない。

  • 前提条件

    • 到着順に処理される。
    • 末尾に並び、途中で抜けない。

情報に関する理論

データ可逆圧縮方式

  • ハフマン符号（可変長二進符号）

    • よく出現する文字には短いビット列を、
    • あまり出現しない文字には長いビット列を

    割り当てる

BNF

バッカス・ナウア記法

  • 文脈自由文法を定義するのに用いられるメタ言語

  • 現在はBNFを拡張したEBNF (Extended BNF) が一般的。

  • EBNFは正規表現を用いてより簡単に記述でき、
    ASN.1、SQL、XMLなどの構文定義にも利用されている。

  • 拡張BNFにある繰り返しがBNFには無いので、この場合、再帰で書く。

    <digit>  ::= ("0"|"1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9")
<digits> ::= <digit> | <digit> <digits>

  • 参考

有限オートマトン

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

通信に関する理論

誤り検出/訂正

計測/制御に関する理論

センサ

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

データ構造

ポーランド記法

木構造の走査法

  • 幅優先探索
    解を見つける時間は均等になる。メモリが必要。

  • 深さ優先探索
    解を見つける時間にばらつきがある。
    探索履歴を削除できるため消費メモリが少ない。

    • 前順・先行順・前置順・行きがけ順
      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

探索手法

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

    • 線形探索
      探索の前にソートしておく必要があり、
      またランダムアクセスが可能でなければならない。

      • 先頭から順に比較を行い、それが見つかれば終了する。
      • 使用頻度順に並べれば、平均検索速度が向上する。

    • 二分探索 = 2分探索木
      分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良い。

      • 中央の値を見て、検索したい値との大小関係を用い、
      • 検索したい値が中央の値の右にあるか、左にあるかを判断し、
        片側には存在しないことを確かめながら検索していく。

    • 内挿探索

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

  • 文字列探索

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

  • ハッシュ

  • 木探索

  • グラフ探索固有

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

  • 参考

比較ソート

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

再帰

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

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

    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 と比べて非常に小さい。

参考

※ 元 Wiki では見出しのみで、本文は書かれていない。

移行メモ

  • 「ル-プには、終了条件を記載する。」の「-」を長音記号に改め「ループ」とした。
  • 「探索手法」の「線形探索」に付いている 「探索の前にソートしておく必要があり、またランダムアクセスが可能でなければならない。」、 「二分探索」に付いている 「分布が偏っていないソートされた大きなリストでは二分探索よりも性能が良い。」は、 それぞれ「二分探索」「内挿探索」の性質と思われるが、原文ママとした。
  • 26進数の対応表とカルノー図は、元 Wiki では 26 列・7 列（結合セル付き）の表だったが、GitHub Wiki では再現できないため、 前者はコードブロック、後者は値のみの 5 列の表に整理し、 各軸の変数ラベルは表の直後に注記した。
  • 元 Wiki の行頭空白による筆算・論理式・擬似コードは、 フェンス付きコードブロックにした。
  • 元 Wiki で見出しそのものが他ページへのリンクになっていた箇所 （「演算精度」「相関係数」「センサ」）は、 GitHub Wiki では見出しからアンカが生成されるため、 見出しをプレーン・テキストとし、リンクは直下の本文に置いた。
  • マイクロソフト系技術情報 Wiki（techinfoofmicrosofttech.osscons.jp）への URL リンクは、移行済みの 数値の計算方法 に張り替えた。
  • PukiWiki のページ内アンカ（#xxxxxxxx）は GitHub Wiki では再現できないため、 同一ページ内のアンカは見出しから生成されるアンカに張り替え、 他ページのアンカを指すリンクは「〜（ページ名 の該当節を参照）」の形に置き換えた。

Tags: 移行, 資格, 高度午前, 基礎理論, 離散数学, 基数変換, カルノー図, 待ち行列, ハフマン符号, BNF, オートマトン, 誤り検出訂正, ハミング符号, センサ, ポーランド記法, 木構造, 探索, ソート, 再帰

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

NetDevInfraWiki

マイクロソフト系技術情報 Wiki
Open 棟梁 Wiki

（未着手）

開発基盤部会 Wiki

移行管理: DONE ／ TODO

Clone this wiki locally