単位系

エクサexsa-E10^18
*ペタpeta-P10^15
*テラtera-T10^12
*ギガgiga-G10^9
*メガmega-M10^6
*キロkilo-k10^3
ヘクトhecto-h10^2
デカdeca-da10^1
10^0
デシdeci-d10^-1
センチcenti-c10^-2
*ミリmilli-m10^-3
*マイクロmicro-μ10^-6
*ナノnano-n10^-9
ピコpico-p10^-12
フェムトfemto-f10^-15
アトatto-a10^-18

※ * … ソフトウェアに関係ありそうな単位

2進数

MSB/LSB

MSB                                   LSB
↓                                     ↓
 0001 0010 0011 0100 0101 0110 0111 1000

Little Endian/Big Endian

0x12345678

補数

浮動小数点

誤差

丸め誤差10進→2進
情報落ち値の大きく違う浮動小数の演算
けた落ち有効桁の違う値の演算
打切り誤差漸近法

論理演算と集合

論理記号と集合記号

論理演算集合演算ベン図
論理和
AND
・ ∧set_and.png
A∩B
論理積
OR
+ ∨set_or.png
A∪B
否定
NOT
 ̄ ¬set_not.png
¬A
排他的論理輪
NOR / XOR
⊕ ⊻
(対象差)
set_xor.png
A△B
set_minus.png
A−B

逆・裏・対偶

reverse.png

情報量

情報量とは?

平均情報量

     n
H =  Σ I(Ji)*P(Ji)
    i=0

最大平均情報量

生起確率に偏りがないとき、もっとも平均情報量が大きくなる

        n                n
Hmax =  Σ I(Ji)*P(Ji) = Σ P(Ji) * -log2( P(Ji) )
       i=0              i=0
       
        n
     =  Σ (1/n) * -log2(1/n) = n * (1/n) * -log2(1/n)
       i=0
     
     = log2(n)

これは、場合の数を2進数で表したときのビット数と同じ。

シャノンの法則(回線容量)

逆ポーランド記法

グラフ

グラフの種類

単純グラフ自己ループ、並列辺がないグラフg_loop.pngg_duplicate.png
完全グラフどの2点も編で結ばれるグラフg_complete.png
2部グラフ点を二つのグループV1,V2に分けたとき、全ての辺の端点がV1,V2に属するグラフg_2part.png
オイラーグラフ全ての辺を一度通って一筆書き出来るグラフg_euler.png
ハミルトングラフ全ての点を一度通って一筆書き出来るグラフg_hamilton.png
正則グラフ各点の価数が等しいグラフg_regular.png

ダイクストラ法

  1. スタート点Sの距離を0で確定し、その他の点の仮の距離を∞にする
    dijkstra1.png
  2. 確定点(S)の隣接点(p,q,r)の仮の距離を計算する
    dijkstra2.png
  3. 仮の距離が一番小さい点(q)が、最短経路が見つかった確定点になる
    dijkstra3.png
    • なぜ q が確定点になるのか?
    • たとえば、(S-p)の最短距離は、大回りすることにより 4 より小さくなる可能性がある。
    • ここで、大回りする場合には、現時点での仮の距離が p よりも小さい点を通るはず
    • 従って、たとえ(S-p)の最短距離が 4 より小さくなったとしても、現時点での仮の距離が最小の 1 を下回ることはない
  4. 確定点(S,q)の隣接点(p,r,G)の仮の距離を計算する
    dijkstra4.png
  5. pが確定点となる
    dijkstra5.png
  6. rが確定点となる
    dijkstra6.png
  7. Gが確定点となる
    dijkstra7.png
  8. 結局 S-q-p-G が最短経路で、その距離は6であることが分かった

マルコフ過程

隠れマルコフモデル

確率・統計

代表値

分散・標準偏差・標準化スコア

正規分布

ネットワーク階層モデル

階層TCP/IP接続装置
7アプリケーション層HTTP/FTPゲートウェイ
6プレゼンテーション層××
5セッション層××
4トランスポート層TCP/UDP×
3ネットワーク層IPルーター
2データリンク層Etherブリッジ
1物理層ケーブルリピーター

IPv4

Routing

SNMP

Simple Network Management Protocol

snmp.png
  1. SNMP Agent が、時系列データを MIB(Management Information Base)に蓄える
  2. それとは非同期に、SNMP Manager が、Agent を呼び出して MIB に格納されているデータを取得し、レポートにまとめるなり警告を出したりする。
    • そのときやり取りされる情報が PDU(Protocol Data Unit) で、
    • UDP/IP上で通信がなされる

通信制御

衝突制御

方式実装例備考
CSMA/CDEtherすべての端末が回線を共有。回線が使われていたら、ランダム秒待って再試行
トークンリングFDDI端末がリング状につながり(A--B--C--D--E--(A))、伝言ゲームでパケットを受け渡す。隣の人としか話さない(AはBEのみと直接通信し、Cと通信したいときにはBに中継してもらう)ので、衝突は起きない
TDMA携帯電話通信を行う前にタイムスロットを予約して、チャンネルを確立

同期制御

キャラクタ制御ACKなどを送りあう
フラグ制御HDLC (High Level Data Link Control)
調歩同期(start bit)文字(stop bit)(start bit)文字(stop bit) ...。全銀プロトコル

パケット交換方式

X.25

フレームリレー

ATM

4アプリ任意長のデータをAALに渡せる
3AAL(ATM Adaptation Layer)
2ATM53byte固定長パケット通信(48byte+制御5byte)
1物理

アーラン

待ち行列(M/M/S)

  1. 1CPU(S=1)のとき
    queue.png
    1. JOB投入
      λ JOB/sec = 15 JOB/sec
    2. JOB処理能力
      μ JOB/sec = 20 JOB/sec
    3. CPU利用率
      ρ = λ/μ = 15 / 20 = 0.75
    4. 系内のJOB数
      L = (待たされる確率) / (待たされない確率) = ρ / (1-ρ) = 0.75 / (1-0.75) = 3
    5. 待ち行列内のJOB数
      Lq = (系内のJOB数) * (待たされる確率) = L * ρ = 3 * 0.75 = 2.25
    6. 待ち時間
      tq = L * ts = 3 * (1/20) = 0.15 sec
    7. 応答時間
      t = tq + ts = 0.15 + (1/20) = 0.20 sec
  2. nCPU(S=n)のとき
    CPU利用率が、1/n になる。
    すなわち、
    ρ = (15 / 20) / n = 0.75 / n
    後は1CPUのときと同じ
  3. 納得いかん!
    • なんでCPUの能力以下のJOB投入量で待ち行列が発するのか?
    • たとえば、CPU処理能力 10 sec/JOB、JOB投入 30 sec/JOB とすると、CPU利用率 1/3
    • 問題を簡単にするために、60 sec の内 20 sec だけCPUが動くとすると、下図のようにJOBが処理されていくことになる。
      queueDigest.png
    • ごらんの通り、CPU能力が余っていても、JOB投入のタイミングによっては待ち行列が発生し、それがなかなか解消されないことで、1JOB〜2JOBの定常的な待ち行列は生まれることが分かる。

バランス木

AVL木

左右の部分木の高さの差が1以下の木

B木

多分木、節は子へのポインタとキー値からなる。
下図の例では、L1 < k1 < L2 < k2 < L3 < k3 < L4 < k4 < L5 < k5

 

部分木のバランスを保つために以下の規則を保たなければならない。

探索アルゴリズム

アルゴリズム平均比較回数最大比較回数概要
線形探索法(N+1)/2N要は端から見ていく探索法。最小1回でヒット、最大N会でヒット。平均(N+1)/2回でヒット
二分探索法log2(N)(log2(N))+1整列済みのリストから目的の値を探す。半分づつに絞り込んでいくので、log2(N)+1 回でヒットする(+1は、最後の一回)
ハッシュ法11ハッシュ値からダイレクトにデータを発見する。シノニム(ハッシュ値の衝突)が起きる可能性がある

ソート(整列)

逐次添加法

アルゴリズム概要
基本交換法(バブルソート)[32]1 -> 231 -> 2[31] -> 213 -> [21]3 -> 123隣同士で比較して大きい物を後ろに持っていく。泡が浮いてくるようなので、バブルソート
基本選択法[321,] -> [32,1] -> [3,12] -> [,123]未成列リストの中で一番小さい値を抜き出して、整列済みリストの右端に追加
基本挿入法[321,] -> [21,3] -> [1,23] -> [,123]未成列リストの左端を、整列済みリストのしかるべきところに挿入する

計算量はともに、n(n-1) / 2 = O(n^2)

クイックソート

 [3  7  2   4    1  5   6 ]

 [3  2  1] *4* [ 7  5   6 ]       4を軸として二つに分ける

 [1 *2* 3]  4  [   *5*  7  6 ]    2を軸として部分リスト(321)を二つに分ける
                                    5を軸として部分リスト(756)を二つに分ける

 [1  2  3]  4  [    5  [6 *7*] ]  7を軸として部分リスト(76)を二つに分ける
-------------------------------
   1   2  3   4       5   6  7      全てが部分リストに分解されたので整列済み

ヒープソート

親<子 を見たすヒープ木から、根を取り、ヒープ木を再構成し、また根を取る・・・

  1. 初期状態のヒープ木
        2
       /\
      5  11
     /\ / \
    8 13 12  15
  2. ヒープ木の根[2]を取り、整列済みリストに追加。代わりに適当な葉を根に持ってくる
        15
       /\
      5  11
     /\ / \
    8 13 12  ×   [2]
  3. 5と15を入れ替え
        5
       /\
      15  11
     /\ / \
    8 13 12  ×   [2]
  4. 8と15を入れ替え、ヒープ木になった。
        5
       /\
      8  11
     /\ / \
    13 15 12  ×   [2]
  5. [5]を取り、整列済みリストに追加。代わりに適当な葉を取ってくる
        12
       /\
      8  11
     /\
    13 15            [2,5]
  6. 8と12を入れ替え、ヒープ木になった。
        8
       /\
      12  11
     /\
    13 15
  7. (以下同様)

マージソート

整列済みリスト同士をマージしていく

[6] [1] [3] [4] [7] [2] [8] [5] 最初の整列済みリストは長さ1のリスト
|-----| |-----| |-----| |-----|
[1   6] [3   4] [2   7] [5   8] 隣同士をマージ
|-------------| |-------------|
[1   3   4   6] [2   5   7   8] 隣同士をマージ
|-----------------------------|
[1   2   3   4   5   6   7   8] 完成

プロセッサ

CISC/RISC

CISCComplex Instruction Set Computerマイクロプログラムをファームウェアに格納して起動時に読み込む変更容易
RISCReducted Instruction Set Computerワイヤードロジック変更不可

パイプライン

並列化

メモリ/キャッシュ

メモリへの平均アクセス時間

TE = TC * P + TM * (1-P)

TE : 平均アクセス時間
TC : キャッシュアクセス時間
TM : メモリアクセス時間
P : キャッシュヒット率

キャッシュの書き戻し方法

キャッシュとメモリのマッピング

メモリ保護機構

境界レジスタプログラム毎にアクセスできる領域を決めておく
実行モードユーザモード、特権モード
保護キーメモリ領域に鍵を掛けておき、合い鍵を持っているプログラムのみアクセスを許す
リング方式メモリ領域に重要度に従ってリング番号を付ける。プログラムのリング番号の方が高ければアクセス可能。ベン図でアクセス可能領域を書くとリング状になることから

仮想記憶

ディスク

容量

B(Byte/Sector) * S(Sector/Track) * T(Track/Sylinder) * N(Sylinder)

アクセス時間

アクセス時間 = 平均ヘッド待ち時間                + データ転送時間
             = 平均シーク時間 + 平均回転待ち時間 + データ転送時間
             = 平均シーク時間 + (1/回転数)*(1/2) + データ転送時間

ディスクキャッシュがある場合のアクセス時間

TE = TC * P + TD * (1-P)

TE : 平均アクセス時間
TC : キャッシュアクセス時間
TD : ディスクアクセス時間
P : キャッシュヒット率

RAID

XORパリティ

D1 XOR D2 = P12

とすると、

D1 XOR P12 = D2
D2 XOR P12 = D1

ハミング符号

OS(プロセス管理)

プロセスの状態遷移

┌──────┐
│プロセス生成│
└──────┘
   |  ┌───────┐ Dispatch     ┌───────┐
   ; 筥⊆孫垈椎従態  │───※; 筥⊆孫埔態      │
      │ready state   │       │running state │──
      └───────┘<─────└───────┘  |
          ∧     Preemption      |      |
          |     (タイマ割り込みなど)|      V
          |               |   ┌──────┐
          |   ┌───────┐   |   |プロセス終了|
          |   |待ち状態      |   |   └──────┘
          エ;; wait state    |<──
       入出力終了  └───────┘  入力待ちなど

プロセスのCPUへの割り当て(Dispatch)アルゴリズム

プロセス間通信

システムの信頼性

スループット

20MIPSのCPUで、80万ステップのトランザクションを何件実行できるか?
CPU利用率は80%とする。

一秒で、20M step/sec * 0.8 = 16M step/sec 実行可能だから、
16M step/sec ÷ 80万 step/transaction = 16M ÷ 0.8M = 20 transaction/sec

並行実行・スタンバイ

高信頼化設計

システムの信頼性評価

MTBF、MTTR

RASIS

RASIS = ISO/IEC9126(JIS-X-0129)

Reliability信頼性MTBF
Avility可用性稼働率
Serviceability保守性MTTR
Integrity保全性データが無くならないこと
Security安全性

ISO9000

ISO9000系 (品質管理・品質保証に関する規格群)

ISO9000理念
ISO9001実務。ISO9000に統合
ISO9002
ISO9003
ISO9004ガイドライン

システム開発手法

CASEツール

Computer Aided Software Engineering

CMM

Capacity Maturity Model

CMM1初期レベル。勘に頼った作業レベル。
↓明確化
CMM2反復可能なレベル。経験が生かされるレベル。
↓標準化
CMM3定義されたレベル。ノウハウが定義化されたレベル。
↓制御
CMM4管理されたレベル。責任ある制御が出来るレベル。
↓改善
CMM5最適化されたレベル。継続した改善が出来るレベル。

システム分析

プログラムのモジュール分割

テスト手法

集積テスト

開発管理

見積もり

データベース

データベース設計

1データ分析
2概念設計概念データモデルER図(Entity Relational)
3論理設計論理データモデル階層型(1:n)・ネットワーク型(n:m)・関係型(RDB)
4物理設計物理データモデルディスク

ANSI/SPARC三層スキーマ

          (プログラム)
               |
               |<--- 論理データ独立
               ↓
+-----------------------------------------+
| 外部スキーマ                            |
| プログラムや利用者から見えるデータ構造  |
+-----------------------------------------+
               ↑
               |mapping
               ↓
+-----------------------------------------+
| 概念スキーマ                            |
| データベースの論理構造とその内容の定義  |
+-----------------------------------------+
               ↑
               |mapping
               ↓
+-----------------------------------------+
| 内部スキーマ                            |
| データを格納するための物理的な内容の定義|
+-----------------------------------------+
               ↑
               |物理データ独立性
               |
          (DISK)

ACID

Atomicity原子性COMMIT-ROLLBACK が出来ること
Consistency一貫性COMMIT-ROLLBACK によって、処理に矛盾が生じないこと
Isolation隔離性COMMIT-ROLLBACK が並行実行されても、処理に矛盾が生じないこと
Durability耐久性障害復旧(トランザクションログからの復旧=ロールフォワード)

RDB

正規化

SQL(DDL)

SQL(DML)

SQL(ストアードプロシージャ)

EXEC SQL BEGIN
EXEC SQL DECLARE カーソル名 CURSOR FOR (SELECT文)
EXEC SQL OPEN カーソル名
while(1){
  SQL FETCH カーソル名 INTO x // <--変数にカーソルの内容を入れる
  if(SQLCODE != @)break;      // <--カーソルが終了位置まで来ていたら終了
  // 処理
  //
  //
  if( 異常時 ){
    EXEC SQL CLOSE カーソル名
    EXEC SQL ROLLBACK
    exit;
  }
}
EXEC SQL CLOSE カーソル名
EXEC SQL COMMIT

Computer


添付ファイル: filesnmp.png 640件 [詳細] filehamming6.png 633件 [詳細] fileset_and.png 575件 [詳細] filehamming5.png 639件 [詳細] fileset_or.png 579件 [詳細] fileg_loop.png 562件 [詳細] fileset_not.png 548件 [詳細] filehamming7.png 689件 [詳細] filepolish.png 591件 [詳細] filemarkov.png 584件 [詳細] fileset_minus.png 561件 [詳細] filehamming3.png 543件 [詳細] fileset_xor.png 557件 [詳細] fileg_regular.png 562件 [詳細] filequeue.png 619件 [詳細] filequeueDigest.png 620件 [詳細] filereverse.png 590件 [詳細] fileg_hamilton.png 563件 [詳細] filehamming2.png 629件 [詳細] filehamming8.png 555件 [詳細] filehamming4.png 622件 [詳細] filenonAVLTree.png 676件 [詳細] filehamming1.png 637件 [詳細] fileform_avr.png 632件 [詳細] fileg_complete.png 583件 [詳細] filedijkstra6.png 654件 [詳細] fileform_normdist.png 633件 [詳細] filedijkstra7.png 633件 [詳細] fileg_2part.png 584件 [詳細] fileform_Ndeviation.png 658件 [詳細] fileform_normscore.png 624件 [詳細] fileearlangB.png 573件 [詳細] fileexce_normscore.png 632件 [詳細] fileform_Nnormscore.png 544件 [詳細] fileform_normdist2.png 646件 [詳細] fileform_deviation.png 613件 [詳細] fileg_euler.png 601件 [詳細] fileearlang.png 569件 [詳細] fileform_Niq.png 632件 [詳細] fileform_iq.png 588件 [詳細] filedijkstra5.png 610件 [詳細] fileg_duplicate.png 650件 [詳細] fileform_Nnormdistribution.png 635件 [詳細] filedijkstra1.png 608件 [詳細] filedijkstra2.png 623件 [詳細] file754Value.png 592件 [詳細] filedijkstra4.png 553件 [詳細] filedijkstra3.png 559件 [詳細] fileAVLTree.png 537件 [詳細] fileBtree.png 575件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS   sitemap
Last-modified: 2007-10-21 (日) 17:39:19 (3337d)
ISBN10
ISBN13
9784061426061