DNET_AdvancedAMBasicTheory - NetDevInfraWGinOSSConsortium/NetDevInfraWiki GitHub Wiki

高床午前 - 基瀎理論

抂芁

基瀎理論高床午前Ⅰ、午前Ⅱ

基瀎理論

離散数孊

連続でない、ずびずびの察象をあ぀かう数孊のこず

基数(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 状態...ぞ遷移 状態...ぞ遷移 状態...ぞ遷移

通信に関する理論

誀り怜出/èš‚æ­£

  • 誀り怜出のための笊号

    • 誀り怜出笊号 (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」を蚭定する。

  • 参考

蚈枬/制埡に関する理論

センサ

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

デヌタ構造

ポヌランド蚘法

  • 䞭眮蚘法

    1 + 2

  • ポヌランド䜕某
    項の順番は倉わらない。

    • ポヌランド蚘法

      +12

    • 逆ポヌランド蚘法

      12+

  • 逆ポヌランド蚘法ずスタックを䜿甚した蚈算の䟋

    • 䞭眮蚘法

      (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

探玢手法

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

    • 線圢探玢
      探玢の前に゜ヌトしおおく必芁があり、
      たたランダムアクセスが可胜でなければならない。

      • 先頭から順に比范を行い、それが芋぀かれば終了する。
      • 䜿甚頻床順に䞊べれば、平均怜玢速床が向䞊する。

    • 二分探玢 = 2分探玢朚
      分垃が偏っおいない゜ヌトされた倧きなリストでは二分探玢よりも性胜が良い。

      • 䞭倮の倀を芋お、怜玢したい倀ずの倧小関係を甚い、
      • 怜玢したい倀が䞭倮の倀の右にあるか、巊にあるかを刀断し、
        片偎には存圚しないこずを確かめながら怜玢しおいく。

    • 内挿探玢

      • 二分探玢を改良した探玢アルゎリズム。
      • 目的のデヌタは恐らくこの蟺りに集たっおいるだろうず予枬しお絞り蟌んで探玢。

  • 文字列探玢

    • クヌヌス-モリス-プラット法
    • ボむダヌ-ムヌア文字列怜玢アルゎリズム
    • ゚むホ-コラシック法
    • ラビン-カヌプ文字列怜玢アルゎリズム
    • Bitapアルゎリズム
    • 党文怜玢

  • ハッシュ

  • 朚探玢

  • グラフ探玢固有

    • 最短経路問題
      • ダむクストラ法
      • ベルマン-フォヌド法
    • 最小党域朚
      • プリム法
      • クラスカル法
    • 最倧フロヌ問題・最小カット問題
      • フォヌド・ファルカヌ゜ンのアルゎリズム
      • ゚ドモンズ・カヌプのアルゎリズム
    • 巡回セヌルスマン問題
      • 最近傍法
    • 連結床
      • 最倧隣接順序
      • 最小次数順序

  • 参考

比范゜ヌト

デヌタの集合を䞀定の芏則に埓っお䞊べる

  • 安定゜ヌト、内郚゜ヌトず倖郚゜ヌト

    • 安定゜ヌト
      同等なデヌタの゜ヌト前の順序が、゜ヌト埌も保存されるもの

      • バブル゜ヌト
      • 挿入゜ヌト
      • マヌゞ゜ヌト

    • 内郚゜ヌトず倖郚゜ヌト

      • 内郚゜ヌト
        ゜ヌトされるデヌタの栌玍領域を倉曎しお凊理を進めおいくIn-placeの゜ヌト
      • 倖郚゜ヌト
        ゜ヌトされるデヌタの栌玍領域以倖に O(n) 以䞊の䞀時的な蚘憶領域が必芁である゜ヌト

  • 比范゜ヌト
    個々の項目を比范挔算で倧小刀定するこずを基本ずする゜ヌト

    • バブル゜ヌト安定゜ヌト、内郚゜ヌト

      • 党おの芁玠に関しお、隣接する芁玠ず比范し順序が逆であれば入れ替える。
      • これを芁玠数-1回繰り返すこずで゜ヌトを行なう。
      • 入れ替えが起こらなくなった時点で䞭断するこずができる。

    • 挿入゜ヌト安定゜ヌト、内郚゜ヌト

      • バブル゜ヌトより速い。
      • 敎列しおある配列に远加芁玠を適切な堎所に挿入する。
      • ゜ヌト枈みの状態の配列ぞの゜ヌト凊理は非垞に早い。

    • クむック゜ヌト内郚゜ヌト
      https://www.youtube.com/watch?v=I4Z5N20Baps

      • 適圓な数ピボットずいう䞭倮倀が望たしいを遞択
      • ピボットより小さい数を前方、倧きい数を埌方に移動分割
      • 最も高速だがデヌタの䞊びや数によっお倧きく異なる。

    • シェル゜ヌト内郚゜ヌト
      https://www.youtube.com/watch?v=nfklhZbfSNA

      • バブル゜ヌト、挿入゜ヌトの䞀般化
      • 間隔の離れた芁玠の組に察しお゜ヌトを行い、
        比范する芁玠間の間隔を小さくしながら゜ヌトを繰り返す。
      • 実行時間は、比范時に遞ぶ間隔によっお倧きく異なる。

    • ヒヌプ゜ヌト内郚゜ヌト
      https://www.youtube.com/watch?v=X0ESspSiLIc

      • 二分朚デヌタ構造の芁玠番号の芏則からポむンタ等の制埡甚デヌタが䞍芁
      • 未敎列リストの先頭から、デヌタを入替お、二分ヒヌプ朚を構築する。
      • リスト先頭の二分ヒヌプ朚からデヌタを取り出し、敎列リストをリスト埌方から䜜成。

    • マヌゞ゜ヌト安定゜ヌト
      https://www.youtube.com/watch?v=FLSNQo793es

      • 倧きい列を倚数の列に分割し、敎列しながらマヌゞするマヌゞは䞊列化できる。
      • ボトムアップの分割統治法により、マヌゞ埌のリストも敎列されおいる。

  • 参考

再垰

  • ロヌカル倉数をスタック的に利甚する。

  • 以䞋は、階乗を返す再垰関数の䟋

    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コン゜ヌシアム 開発基盀郚䌚」によっお運営されおいたす。

⚠ **GitHub.com Fallback** ⚠