Basic 情報処理試験(ソフトウェア開発技術者)カンニングペーパー

2024-04-192024
29.9% (109.7/366)
April
62.6% (18.7/30)
Week 16
68.3% (4.7/7)
Day 19 Fri
78.3% (18.8/24)

訪問者

total: 26496
today: 3
yesterday: 13
now: 2

更新

MenuBar

単位系
2進数
- MSB/LSB
- Little Endian/Big Endian
- 補数
浮動小数点
誤差
論理演算と集合
- 論理記号と集合記号
- 逆・裏・対偶
情報量
- 情報量とは？
- 平均情報量
- 最大平均情報量
- シャノンの法則(回線容量)
逆ポーランド記法
グラフ
- グラフの種類
- ダイクストラ法
- マルコフ過程
- 隠れマルコフモデル
確率・統計
- 代表値
- 分散・標準偏差・標準化スコア
- 正規分布
ネットワーク階層モデル
IPv4
Routing
SNMP
通信制御
- 衝突制御
- 同期制御
パケット交換方式
- X.25
- フレームリレー
- ATM
アーラン
待ち行列(M/M/S)
バランス木
- AVL木
- B木
探索アルゴリズム
ソート(整列)
- 逐次添加法
- クイックソート
- ヒープソート
- マージソート
プロセッサ
- CISC/RISC
- パイプライン
- 並列化
メモリ/キャッシュ
- メモリへの平均アクセス時間
- キャッシュの書き戻し方法
- キャッシュとメモリのマッピング
- メモリ保護機構
- 仮想記憶
ディスク
- 容量
- アクセス時間
- ディスクキャッシュがある場合のアクセス時間
- RAID
- XORパリティ
- ハミング符号
ＯＳ（プロセス管理）
- プロセスの状態遷移
- プロセスのCPUへの割り当て(Dispatch)アルゴリズム
- プロセス間通信
システムの信頼性
- スループット
- 並行実行・スタンバイ
- 高信頼化設計
システムの信頼性評価
- MTBF、MTTR
- RASIS
- ISO9000
システム開発手法
- CASEツール
- CMM
- システム分析
- プログラムのモジュール分割
- テスト手法
- 集積テスト
- 開発管理
- 見積もり
データベース
- データベース設計
- ANSI/SPARC三層スキーマ
- ACID
- RDB
- 正規化
- SQL(DDL)
- SQL(DML)
- SQL(ストアードプロシージャ)

単位系 †

	エクサ	exsa-	E	10^18
*	ペタ	peta-	P	10^15
*	テラ	tera-	T	10^12
*	ギガ	giga-	G	10^9
*	メガ	mega-	M	10^6
*	キロ	kilo-	k	10^3
	ヘクト	hecto-	h	10^2
	デカ	deca-	da	10^1
				10^0
	デシ	deci-	d	10^-1
	センチ	centi-	c	10^-2
*	ミリ	milli-	m	10^-3
*	マイクロ	micro-	μ	10^-6
*	ナノ	nano-	n	10^-9
	ピコ	pico-	p	10^-12
	フェムト	femto-	f	10^-15
	アト	atto-	a	10^-18

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

↑

2進数 †

↑

MSB/LSB †

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

Most Significat Bit
Least Significant Bit

↑

Little Endian/Big Endian †

0x12345678

Little Endian(IA32)
```
0x78 0x56 0x34 0x12
```
Big Endian(MC68000,PDP10,IBM360,SPARC)
```
0x12 0x34 0x56 0x78 
```
Middle Endian(PDP11,VAX)
```
0x34 0x12 0x78 0x56
```
現行のプロセッサのほとんどは、Endianを切り替えることが出来る。
- ARM, PPC, Alpha, SPARC V9, MIPS, PA-RISC, IA64

↑

補数 †

N進数のNの補数
```
12345678(10進) の 10の補数 = 87654322
```
- 繰り上がりが起きる最小の数
N進数の(N-1)の補数
```
12345678(10進) の  9の補数 = 87654321
```
- 繰り上がりの起きない最大の数

(2進数の)2の補数

                 -128(10000000B)
127(01111111B) + -127(10000001B) = 0(00000000B)
126(01111110B) + -126(10000010B) = 0(00000000B)
              ...
  1(00000001B) +   -1(11111111B) = 0(00000000B)
  0(00000000B)

絶対値が同じ数を足し合わせると、オーバーフローして0になる
MSB = 1 : 負数
MSB = 0 : 正数

(2進数の)1の補数

127(01111111B) + -127(10000000B) = 0(11111111B)
126(01111110B) + -126(10000001B) = 0(11111111B)
              ...
  1(00000001B) +   -1(11111110B) = 0(11111111B)
  0(00000000B) +                 = 0(11111111B)

絶対値が同じ数を足し合わせると、全てのビットが1になる
0の表現方法が二通りある( 0 = 00000000B = 11111111B )
MSB = 1 : 負数
MSB = 0 : 正数

↑

浮動小数点 †

IEEE754

 1     8               23           
+-+--------+-----------------------+
|S| Exp    | Fraction              |
+-+--------+-----------------------+
31 30    23 22                    0

値
value Exp(指数部) Fraction(仮数部)
0 0 0
非正規数 0 ゼロ以外
正規数 1～254 任意
無限大 255 0
非数 255 ゼロ以外

value	Exp(指数部)	Fraction(仮数部)
0	0	0
非正規数	0	ゼロ以外
正規数	1～254	任意
無限大	255	0
非数	255	ゼロ以外

Overflow / Underflow

Over +------------+ Under +------------+ Over
flow |            | flow  |            | flow
-----+------------+---+---+------------+------->
   -Vmax        -Vmin 0  Vmin         Vmax

Overflow 演算結果が大きすぎてあらわせない
Underflow 演算結果が小さすぎてあらわせない

↑

誤差 †

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

↑

論理演算と集合 †

↑

論理記号と集合記号 †

	論理演算	集合演算	ベン図
論理和 AND	・ ∧	∩	A∩B
論理積 OR	＋ ∨	∪	A∪B
否定 NOT	￣￢	￣	￢A
排他的論理輪 NOR / XOR	⊕ ⊻	△ (対象差)	A△B
差		－	A－B

↑

逆・裏・対偶 †

↑

情報量 †

↑

情報量とは？ †

情報量 I(J) : 状態Jを表すのに必要なビット数
```
I(J) = - log2(P(J))

ただし、P(J)はJの生起確率
```
例
- さいころを振って１がでる状態の情報量
```
I(Jd) = - log2( 1/6 ) = log2(6) = 2.58 = 3
```
  3bitあれば、さいころの状態を表すことが出来る
- コインを投げて表がでる状態の情報量
```
I(Jc) = - log2( 1/2 ) = log2(2) = 1
```
  1bitあれば、さいころの状態を表すことが出来る
情報量は加法性が成り立つ
- さいころを振って１がでて、コインを投げて表がでる状態の情報量
```
I(Jcd) = I(Jc) + I(Jd) = 1 + 2.58 = 3.58 = 4
```

↑

平均情報量 †

     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進数で表したときのビット数と同じ。

↑

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

回線容量の理論値
C ＝ w * log2( 1 + S/N ) [bps]
- w : 周波数
- S/N : シグナル電力 / ノイズ電力

モデムの回線容量

3 kHz * log2 ( 1 + 20dB )
= 3000 * log2 ( 1 + 100 )
= 20kbps

cf.デシベル
```
LB = 10 * log10( A/B ) [dB]
```
- d(デシ) = 10分の1
- 比率の単位 B(ベル) 、日常生活では dB が使われる
- 20db => A:B = 100:1
cf.マグニチュード
```
log10(E) = 4.8 + 1.5M
```
- E の単位は J(ジュール)
- マグニチュードが1上がると、エネルギーは 10^1.5 = 32 倍

↑

逆ポーランド記法 †

計算式の表記法。
```
  4  3  *  2  +  5  -
 --------
 12  2  +  5  -
 --------
 14  5  -
 --------
  9
```
- 左から(値,値,演算子)の組を処理していけば答えを出せる。
- 計算機で処理しやすい。

計算式を表す木構造を再起処理していると見なすことも出来る

int main(){
  eval(root);
}

void eval( node ){
  if( isTerminal( node ) ){
    return node->value;
  }
  
  switch(node){
  case "+":
    node->value = eval(node->left) + eval(node->right);
    break;
  case "-":
    node->value = eval(node->left) - eval(node->right);
    break;
  case "*":
    node->value = eval(node->left) * eval(node->right);
    break;
  case "/":
    node->value = eval(node->left) / eval(node->right);
    break;
  case "=":
    node->left = eval(node->right);
    break;
  }
}

一般的な計算式を逆ポーランド記法にする方法 → 優先度の低い演算子を後ろにとばしていく

 x  =  4  *  3  +  2  -  5  |
 x     4  *  3  +  2  -  5  |  =
 x     4  *  3  +  2     5  |  -  =
 x     4  *  3  +  2        |  5  -  =
 x     4  *  3     2        |  +  5  -  =
 x     4  *  3              |  2  +  5  -  =
 x     4     3              |  *  2  +  5  -  =
 x     4                    |  3  *  2  +  5  -  =
 x                          |  4  3  *  2  +  5  -  =
                            |  x  4  3  *  2  +  5  -  =

普通は "x=" は出てこないんだけど・・・情報処理試験的ではこういう扱いのようです( 左から処理していけば答えが出るという本来の趣旨に反するが・・・)

↑

グラフ †

↑

グラフの種類 †

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

↑

ダイクストラ法 †

最短経路問題

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

↑

マルコフ過程 †

今日の天気と明日の天気の相関が分かったとき

今日の天気と明後日の天気の相関は？

今日の天気と明日の天気の相関を行列で表す
明日
晴れ曇り雨
今日晴れ 0.50 0.30 0.20
曇り 0.40 0.20 0.40
雨 0.30 0.30 0.40
```
    | 0.50  0.30  0.20 |
M = | 0.40  0.20  0.40 |
    | 0.30  0.30  0.40 |
```

今日の天気と明後日の天気の相関 = M * M

        | 0.50  0.30  0.20 | | 0.50  0.30  0.20 |   | 0.43 0.27 0.30 |
M * M = | 0.40  0.20  0.40 | | 0.40  0.20  0.40 | = | 0.40 0.28 0.32 |
        | 0.30  0.30  0.40 | | 0.30  0.30  0.40 |   | 0.39 0.27 0.34 |

↑

隠れマルコフモデル †

システムが、パラメータ不明のマルコフ過程であると仮定して、実験や観測結果からパラメータを求めるシステム分析法
形態素解析など(名詞の次は動詞が来やすいなど)

↑

確率・統計 †

↑

代表値 †

平均値
中央値(Median)
- データを昇順にソートしたときの中央に来る値
- データ数が n(奇数) のとき、(n+1)/2 番目のデータ
- データ数が n(偶数) のとき、n/2 番目のデータと n/2+1 番目のデータの平均
最頻値(Mode)

↑

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

分散(平均値との差の平均の二乗)
標準偏差(平均値との差の平均)
標準化スコア
- 偏差値
- IQ

↑

正規分布 †

正規分布
- 標準正規分布
- 偏差値
- IQ
確率分布

標準化スコア範囲左の範囲に含まれるデータの割合
μ±1σ 68.3%
μ±2σ 95.4%
μ±3σ 99.7%
μ±4σ 99.994%
EXCEL関数
- NORMDIST(x,平均,標準偏差,FALSE)
  - グラフ上の x に対応する値を求める
  - NORMDIST(1,0,1,FALSE)=0.24
- NORMDIST(x,平均,標準偏差,TRUE)
  - グラフ上の -∞ ～ x の面積を求める。
  - 従ってデータがの 1σ 近傍に含まれる確率は
  - NORMDIST(1,0,1,TRUE) - NORMDIST(-1,0,1,TRUE) = 0.841-0.158 = 0.683
- NORMINV(s,平均,標準偏差)
  - グラフ上の -∞ ～ x の面積から x を求める
  - NORMINV(0.841,0,1) = 1

標準化スコア範囲	左の範囲に含まれるデータの割合
μ±1σ	68.3%
μ±2σ	95.4%
μ±3σ	99.7%
μ±4σ	99.994%

↑

ネットワーク階層モデル †

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

↑

IPv4 †

Class A

   8byte    24byte
+--------|--------+--------+--------+
|0 NET   | HOST ID                  |
+--------|--------+--------+--------+

Class B

   16byte            16byte
+--------+--------|--------+--------+
|10 NETWORK ID    | HOST ID         |
+--------+--------|--------+--------+

Class C

   24byte            8byte
+--------+--------+--------|--------+
|110 NETWORK ID            | HOST ID|
+--------+--------+--------|--------+

↑

Routing †

静的(static)
動的(dynamic)
- RIP(Routing Information Protocol)
  あるサーバーまでのメトリック数(経由するルーター数)をルーター同士が30秒ごとにやり取りする
- OSPF(Open Shortest Path First)
  回線状態を考慮して最短経路を調べる

↑

SNMP †

Simple Network Management Protocol

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

↑

通信制御 †

↑

衝突制御 †

方式	実装例	備考
CSMA/CD	Ether	すべての端末が回線を共有。回線が使われていたら、ランダム秒待って再試行
トークンリング	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) ...。全銀プロトコル

HDLC
AからBへの送信内容本文+(0,0) 本文+(1,0) 本文+(2,1) 本文+(3,1) …
BからAへの送信内容本文+(0,2) 本文+(1,4) …
本文に続いて、何パケット送受信したかのフラグをつける方式

↑

パケット交換方式 †

↑

X.25 †

階層
3 ネットワーク層 X.25
2 データリンク層 HDLC
1 物理層 X.21
装置
- DCE(Data Circuit-terminating Equipment：回線終端装置)
- DTE(Data Terminal Equipment：端末装置)
  - PT(Packet Terminal) : そのままDCEとパケット通信できる
  - NPT(Not Packet Terminal) : そのままではDCEとパケット通信できないので、PAD(Packet Assembly Disassembly)を経由して DCE と通信を行う。

↑

フレームリレー †

パケット交換網の実用的な実装
X25のエラー訂正機能を簡略化( 基本的に End to End でなんとかして )
CIR(Commited Information Rate:最低保障帯域)
輻輳制御
- BENCH : 送信者に輻輳が起きていることを通知
- FENCH : 受信者に輻輳が起きていることを通知

↑

ATM †

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

↑

アーラン †

1hあたりの呼量

a = c(呼量) * 保留時間(h) / 時間(h)

負荷表
- 呼損率 0.05 で、呼量 2アーランを満たすには、5回線必要
- 呼損率
- 回線数と呼損率から呼量を求める (Javaプログラム)

↑

待ち行列(M/M/S) †

1CPU(S=1)のとき
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
nCPU(S=n)のとき
CPU利用率が、1/n になる。
すなわち、
ρ = (15 / 20) / n = 0.75 / n
後は1CPUのときと同じ
納得いかん!
- なんでCPUの能力以下のJOB投入量で待ち行列が発するのか？
- たとえば、CPU処理能力 10 sec/JOB、JOB投入 30 sec/JOB とすると、CPU利用率 1/3
- 問題を簡単にするために、60 sec の内 20 sec だけCPUが動くとすると、下図のようにJOBが処理されていくことになる。
- ごらんの通り、CPU能力が余っていても、JOB投入のタイミングによっては待ち行列が発生し、それがなかなか解消されないことで、1JOB～2JOBの定常的な待ち行列は生まれることが分かる。

↑

バランス木 †

↑

AVL木 †

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

AVL木
AVL木では無い木

↑

B木 †

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

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

最大n個の子を持つB木を n次B木と言う
根は、2～n個の子を持つ
根から葉までの深さはどれも同じ
葉以外の節は、その節の持つキー値の個数＋１の子を持つ
根と葉以外の節は、n/2個以上n個以下の子を持つ

↑

探索アルゴリズム †

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

ハッシュ法におけるシノニム回避法

オープンアドレス

void insert( DATA ){
  long hVal = hash(DATA);
  while( array[hVal] != null ){
    hVal++;
  }
  array[hVal] = DATA;
}
DATA search( DATA ){
  long hVal = hash(DATA);
  while( array[hVal] != DATA ){
    hVal++;
  }
  return array[hVal];
}

シノニムが発生した場合、隣のハッシュ値を使う。探索時には最悪線形探索法になる。

チェーン法

void insert( DATA ){
  long hVal = hash(DATA);
  List chain = array[hVal];
  chain.addLast( DATA );
}
DATA search( DATA ){
  long hVal = hash(DATA);
  List chain = array[hVal];
  for( cnt = 0 ; cnt < chain.length ; cnt++ ){
    if( chain[cnt] == DATA ){
      return chain[cnt];
    }
  }
  return null;
}

ハッシュ表が、リストへのポインタになっている。
探索時の計算量は、リストからDATAを線形探索法で見つけることに等しい。
データ数N ハッシュ表の大きさM とすると、計算量は O(N/M)

↑

ソート(整列) †

↑

逐次添加法 †

アルゴリズム	例	概要
基本交換法(バブルソート)	[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      全てが部分リストに分解されたので整列済み

適当に選んだ軸より、大きい値の集合、小さい値の集合に分ける
部分リストに分解できなくなったら整列終了
計算量は、O( n * log2(n) )
ただし、軸にいつも最小最大値が出てきた場合、逐次添加法と同じになり O( n^2 )

↑

ヒープソート †

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

初期状態のヒープ木

　　　 ２
　　　／＼
　　５　　11
　／＼　／　＼
８　13 12　　15

ヒープ木の根[２]を取り、整列済みリストに追加。代わりに適当な葉を根に持ってくる
```
　　　 15
　　　／＼
　　５　　11
　／＼　／　＼
８　13 12　　×   [2]
```

５と15を入れ替え

　　　 ５
　　　／＼
　　15　　11
　／＼　／　＼
８　13 12　　×   [2]

８と15を入れ替え、ヒープ木になった。

　　　 ５
　　　／＼
　　８　　11
　／＼　／　＼
13　15 12　　×   [2]

[５]を取り、整列済みリストに追加。代わりに適当な葉を取ってくる
```
　　　 12
　　　／＼
　　８　　11
　／＼
13　15            [2,5]
```

８と12を入れ替え、ヒープ木になった。

(以下同様)

計算量は O(n*log2(n))

↑

マージソート †

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

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

計算量は O(n*log2(n))

↑

プロセッサ †

↑

CISC/RISC †

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

↑

パイプライン †

パイプライン

 |←N命令→|
─┌─┬─┐
↑｜１｜２｜
｜└─┼─┼─┐
Ｄ　　｜３｜４｜
段　　└─┼─┼─┐
↓　　　　｜５｜６｜
―　　　　└─┴─┘
　　　　　|<->|
　　　　　 P ns

(D+N-1)*P = (3+2-1)*1 = 4ns

逐次実行

  ┌─┬─┬─┬─┬─┬─┐
  ｜１｜２｜３｜４｜５｜６｜
  └─┴─┴─┴─┴─┴─┘

6ns

分岐ハザード・データハザード
スーパースカラ（パイプラインを複数用意）
VLIW( Very Long Instruction Word ) … コンパイラががんばってハザードが起きないようにする

↑

並列化 †

並列計算機の形態

	プロセッサ	1命令で操作出来るデータ	備考
SISD (Single Instruction/Single Data)	1	1	Z80、80486
SIMD (Single Instruction/Multiple Data)	1	n	ベクトルコンピュータ、DSP、Pentium MMXなど
MISD (Multiple Instruction/Single Data)	n	1	宇宙船・深海探査船などで使われる超ミッションクリティカル・システム(３プロセッサが同じ処理をして、結果を多数決で決める)
MIMD (Multiple Instruction/Multiple Data)	n	n	普通の並列計算機

MIMDの形態

密結合

 CPU CPU CPU CPU CPU
━┻━┻━╋━┻━┻━ (内部BUS)
         RAM

疎結合

 CPU CPU CPU CPU CPU
  ┃  ┃  ┃  ┃  ┃
 RAM RAM RAM RAM RAM
─┴─┴─┴─┴─┴─ (NETWORK)

アムダールの公式

         1              (元の性能)
E = -------------- = ----------------
    (1-r) + (r/n)    (並列化事の性能)

E : 性能倍率
r : JOB内の並列化可能な箇所の割合
n : プロセッサ数

↑

メモリ/キャッシュ †

↑

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

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

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

↑

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

ライトスルー(逐次メモリに書き戻す)
ライトバック(一端キャッシュに書き込み、あとでメモリに書き戻す)
ライトバックアルゴリズム
LRU Least Recently Used
FIFO First In First Out
LIFO Last In First Out (=Stack)
LFU Least Frequently Used

↑

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

ダイレクトマッピング

メモリ　　　１　２　３　４　５　６　７　８
　　　　　　└┬┘　└┬┘　└┬┘　└┬┘
キャッシュ　　Ａ　　　Ｂ　　　Ｃ　　　Ｄ

あらかじめメモリ領域とキャッシュ領域が決められている

フル・アソシエーティブ

メモリ　　　１　２　３　４　５　６　７　８
　　　　　　└─┴─┴─┴┬┴─┴─┴─┘
キャッシュ　　　　　　 ＡＢＣＤ

キャッシュの空き領域にメモリがマッピングされる

セット・アソシエーティブ

メモリ　　　１　２　３　４　５　６　７　８
　　　　　　└─┴┬┴─┘　└─┴┬┴─┘
キャッシュ　　ＡＢ(Set)　　　　ＣＤ(Set)

セットの中では、フルアソシエーティブ

↑

メモリ保護機構 †

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

↑

仮想記憶 †

仮想記憶登場前(古代)のメモリ管理
- 単一連続割り当て方式
- 固定区画方式（パーティション方式）
  - 小さいプログラムにも広大なメモリ領域が割り振られる
  - プロセス内部のみ使用領域＝内部フラグメンテーション・ガベージ
- 可変区画方式
  - メモリ領域の確保と解放を繰り返すと、利用できない小さな断片が発生
  - （外部）フラグメンテーション
  - ガベージ・コレクション（＝メモリ・コンパクション）
- オーバーレイ方式（＝バンク切り替え）
- スワップ方式（＝バンクをディスク上のスワップファイルに作る）
仮想記憶方式
- 全プロセスに、仮想的に全メモリ領域を割り当てる。ＯＳが仮想メモリを実メモリに変換して実行する。
- ページング（＝仮想メモリと実メモリのマッピング）
  - DAT(Dynamic Address Translation)　：　ページテーブルを使い、仮想メモリと実メモリのマッピングを行う
  - マッピングアルゴリズムは、キャッシュと同じ。LRU、FIFOなど
- ページフォルト（＝仮想メモリ空間が実メモリからスワップファイルに退避されること）
- スラッシング（＝ページフォルトがガシガシ起きている状態）
- ワーキングセット（＝よく使われているメモリ領域。ワーキングセットでない領域がページフォルトする）

↑

ディスク †

↑

容量 †

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 †

Redundant Array of Independent Disks
RAID 0(ストライピング)
RAID 1(ミラーリング)

RAID 2(パリティ専用ディスクを複数用意し、２台同時に故障しても復旧可)

DISK1  DISK2  DISK3  DISK4  DISK5
|Ｄ１| |Ｄ２| |PA12| |PB12| |PC12|
|Ｄ３| |Ｄ４| |PA34| |PB34| |PC34|
|Ｄ５| |Ｄ６| |PA56| |PB56| |PC56| ※ D:Data, PA/PB/PC:Parity(ハミング符号)

パリティ専用ディスクに負荷集中
容量があんまり増えない

RAID 3,4(RAID2を簡略化、パリティ専用ディスクは一つ)
```
DISK1  DISK2  DISK3 
|Ｄ１| |Ｄ２| |Ｐ12|
|Ｄ３| |Ｄ４| |Ｐ34|
|Ｄ５| |Ｄ６| |Ｐ56| ※ D:Data, P:Parity(XOR)
```
- パリティ専用ディスクに負荷集中
- RAID 3 : ビット単位でパリティ計算
- RAID 4 : ブロック単位でパリティ計算

RAID 5(３台以上、パリティを分散し１台壊れても復旧可)

DISK1  DISK2  DISK3
|Ｄ１| |Ｄ２| |Ｐ12|
|Ｄ３| |Ｐ34| |Ｄ４|
|Ｐ56| |Ｄ５| |Ｄ６| ※ D:Data, P:Parity(XOR)

DISK1  DISK2  DISK3
| × | |Ｄ２| |Ｐ12| -> Ｄ２,Ｐ12 から Ｄ１ を復旧可
| × | |Ｐ34| |Ｄ４| -> Ｐ34,Ｄ４ から Ｄ３ を復旧可
| × | |Ｄ５| |Ｄ６| -> Ｄ５,Ｄ６ から Ｐ56 を復旧可

パリティ書き込みをラウンドロビンにすることにより、パリティ専用ディスクに負荷が集中するのを防ぐ

RAID 6(RAID 5 の拡張、パリティを２つ作り１台壊れても復旧可)

DISK1  DISK2  DISK3  DISK4
|Ｄ１| |Ｄ２| |PA12| |PB12|
|Ｄ３| |PA34| |PB34| |Ｄ４|
|Ｐ56| |PB56| |Ｄ５| |Ｄ６| ※ D:Data, PA,PB:(ハミング符号)

RAID 10
- RAID 1 をミラーリング
RAID 50
- RAID 5 をミラーリング
パリティ専用ディスクに負荷が集中するってどういうことよ？
```
DISK1  DISK2  DISK3 
|Ｄ１| |Ｄ２| |Ｐ12|
|Ｄ３| *Ｄ４* *Ｐ34*
|Ｄ５| |Ｄ６| |Ｐ56| D:Data, P:Parity(XOR)
```
D4が書き換えられたとき、DISK2 と DISK3 に書き込みを行う必要があるが、DISK1 には書き込む必要がない。
つまり、データが上書きされるときには、常にパリティ専用ディスクが動くことになる。

↑

XORパリティ †

Ｄ１ XOR Ｄ２ = Ｐ12

とすると、

Ｄ１ XOR Ｐ12 = Ｄ２
Ｄ２ XOR Ｐ12 = Ｄ１

↑

ハミング符号 †

ハミング符号
- 1bit までの誤り訂正が出来る
拡張ハミング符号
- 1bit までの誤り訂正、2bit までの誤り発見が出来る
ハミング符号の考え方
- 普通ハミング符号と言ったら、(情報4bit、ハミング符号3bit) の組を指す
- 以下、行列演算は2を法とする計算(モジュロ2の世界)
  - 要は計算結果を2で割った余りを答えとする世界
  - XORを取っているのと同じ
  - 概念を理解する上では余り深く考えない方が良いかも・・・
- 今、全ての列が異なる H を用意する。(全ての列が異なることがミソ)
- 次の条件を満たす G を求める
- ここで送信側で、4bitのデータ x に対して、7bitの y を計算し、受信側に送ったとする。(ちなみに、Ｇの先頭4列を見れば明らかなように、y の先頭 4bit は、x と同じ)
- 誤りがなければ、受信した y に H をかけると 0 行列(ベクトル)になるはずである。yの頭 4bit が x となる。
- 通信経路で1bitの誤り e が発生し、受信側では y' を受け取ったとすると、
- 受信した y' に H をかけると eH になるので、eHベクトルと等しい Hの列に対応するビットが間違っていることが分かる(ここで、Hの列が全て違うことが生きてくる)
- ということで、受信した y' の該当ビットを反転すれば、y に戻すことが出来る。yの頭 4bit が x となる。
- 拡張ハミング符号 : (情報4bit、ハミング符号3bit、パリティ1bit)
  パリティは、(情報4bit + ハミング符号3bit) の 7bit の各桁の XOR を取ったモノ
  → 2bitまでの誤り発見と 1bit の誤り訂正が可能
  
  送られてきた y をチェックするときに H' を使うとパリティ計算までできる(2を法とする加算 = XOR だから)
  結局同じことなんだけどね。

↑

ＯＳ（プロセス管理） †

↑

プロセスの状態遷移 †

┌──────┐
│プロセス生成│
└──────┘
　　　｜　　┌───────┐ Dispatch     ┌───────┐
　　　①─＞│実行可能状態  │───②──＞│実行状態      │
　　　　　　│ready state   │　　　　　　　│running state │──⑥
　　　　　　└───────┘＜──③───└───────┘　　｜
　　　　　　　　　　∧　　　　 Preemption 　　　　　｜　　　　　　｜
　　　　　　　　　　｜　　　　　(タイマ割り込みなど)｜　　　　　　Ｖ
　　　　　　　　　　｜　　　　　　　　　　　　　　　｜　　　┌──────┐
　　　　　　　　　　｜　　　┌───────┐　　　｜　　　｜プロセス終了｜
　　　　　　　　　　｜　　　｜待ち状態      ｜　　　｜　　　└──────┘
　　　　　　　　　　⑤───｜wait state    ｜＜──④
　　　　　　　入出力終了　　└───────┘　　入力待ちなど

ノンプリエンティブＯＳは、③がない (Mac OS 9 など)
- アプリケーション側で適当なときに待ち状態に戻るように制御する必要がある
- アプリケーションが無限ループにハマルとOSごと落ちる

↑

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

ラウンドロビン

┌────────┐　　　┌───────┐
│実行可能状態    │　　　│実行状態(CPU) │
│                ｜　　　｜　　　　　　　｜
│        ○ ○ ○｜――＞｜　　　●　　　｜
└────────┘　　　└───────┘
　　∧　　　　　　　　　　　　　｜タイマ割り込み
　　└─────────────┘

一定時間内にプロセスが終わらないと、タイマ割り込みが起こる
実行状態のプロセスは実行可能状態待ち行列の最後に戻される

フィードバック待ち行列

┌────────┐　　　┌───────┐
│実行可(優先度高)│　　　│実行状態(CPU) │
│                ｜　　　｜　　　　　　　｜
│        ○ ○ ○｜――＞｜　　　●　　　｜
└────────┘　　　└───────┘
　　┌─────────────┘タイマ割り込み
　　Ｖ
┌────────┐
│実行可(優先度中)│
│                ｜
│     ○ ○ ○ ○｜
└────────┘

┌────────┐
│実行可(優先度低)│
│                ｜
│           ○ ○｜
└────────┘

一定時間内にプロセスが終わらないと、タイマ割り込みが起こる
実行状態のプロセスは、優先度の一段低い実行可能状態待ち行列の最後に戻される

FIFO
- 実行可能状態になったモノから逐次実行する
イベントドリブン
- 入出力の発生や、納期管理によってプロセスの状態遷移が起きる
- リアルタイムＯＳ

↑

プロセス間通信 †

イベントフラグ : 他のプロセスの動きを制御するシステムコール
Post/Wait命令 : 他のプロセスの動きを制御するシステムコール
ENQ/DEQ命令 : 共有資源の取得を禁止・許可するシステムコール
IPC(Inter Process Communication)
- パイプ
- 共通変数
- セマフォ
  - 整数の共通変数
  - 二値セマフォ：複数のプロセスから同時にいじっちゃいけない資源をさわる処理の排他制御
```
while( s==0 ){
  wait( 100ms );
}
s=0;
排他処理が必要な処理
s=1;
```
    という感じ

↑

システムの信頼性 †

↑

スループット †

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

↑

並行実行・スタンバイ †

デュアル・システム（２系統並行稼働させ、結果を照合する）
デュプレックス・システム
電源 OS サービス
ホットスタンバイ ON ON ON
ウォームスタンバイ ON ON OFF
コールドスタンバイ OFF OFF OFF

	電源	OS	サービス
ホットスタンバイ	ON	ON	ON
ウォームスタンバイ	ON	ON	OFF
コールドスタンバイ	OFF	OFF	OFF

↑

高信頼化設計 †

フォールト・アボイダンス（故障しないように作る）

フォールト・トレランス

フェースソフト(部分回復)	フォールバック(縮退運用)が出来るように作る
フェースセーフ(危機回避)	安全な方に故障する。信号は故障すると赤になる
フールプルーフ	ユーザが危険な操作をしないような設計にする

↑

システムの信頼性評価 †

↑

MTBF、MTTR †

平均故障間隔 = MTBF(Mean Time Between Failures)
平均修理間隔 = MTTR(Mean Time To Repair)
稼働率= MTBF / (MTTR+MTBF)

↑

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

上流CASE
下流CASE
保守CASE
統合CASE
レポジトリ (CASEツールの扱うドキュメントを格納するデータベース)

↑

CMM †

Capacity Maturity Model

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

↑

システム分析 †

DFD
○ プロセス
□ データ
―> データフロー
＝データストア
変換図( DFD + 状態遷移図 )
○ プロセス
□ データ
―> データフロー
…> コントロールフロー
＝データストア
DFDのプロセス同士を、データフローとコントロールフローで結び、データの流れと状態遷移を表す。
DFDと状態遷移図を書いた方が良いような・・・
ペネリット図( 並列処理の依存関係を図示 )
○ プレース(状態)
― トランジション(事象)
・トークン

↑

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

STS分割 (Source:入力、Transform:変換、Sink:出力)
TR分割 (トランザクション分割)
共通機能分割
ジャクソン法 (入出力データの対応関係からモジュール分割。JSP木)
ワーニエ法 (入力データの構造からモジュール分割)

↑

テスト手法 †

ブラックボックステスト

             -100              0              100
…-------------+---------------+---------------+-----------…
  -150     -100|-99   -50     0|1      50   100|101     150
…-------------+---------------+---------------+-----------…
     NG                OK            OK              NG

同値分析
- 同じような振る舞いをする値の範囲の代表値でテスト
- 150,-50,50,150
限界値分析
- 値の範囲の境界をテストする
- 100,-99,0,1,100,101
因果グラフ(デシジョンテーブル)

ホワイトボックステスト
- 命令網羅
- 判定条件網羅
- 判定条件・条件網羅
- 複数条件網羅

↑

集積テスト †

増加テスト
- ボトムアップテスト
  - ドライバ=下部構造(部品)をテストするために、未完成の上位構造(業務ロジック)の代わりに使うプログラム
- トップダウンテスト
  - スタブ=上位構造(業務ロジック)をテストするために、未完成の下部構造(部品)の代わりに使うプログラム
非増加テスト
- ビックバン・テスト (止めてくれー！)
- 一斉テスト (止めてくれー！)

↑

開発管理 †

ガントチャート
PERT図
マイルストーン
クリティカルパス

トレンドチャート

マイル
ストー (実績)
ン数      +   **(予定)
↑        + **
｜       +**
｜      **
｜    ** +
｜  **  +
｜**++++
＋――――――→時間

消化すべきマイルストーン数の予定値と実績値をグラフに表したモノ

↑

見積もり †

ファンクションポイント法
```
FP = ( Σ(機能iの難易度) ) * 補正係数
```
- 利点
  - 画面・帳票を単位とした見積もりなので、ユーザから見て理解しやすい（＝合意しやすい）
  - プロジェクトの初期から適用可能
- 欠点
  - 難易度の標準化が必要
  - FPと工数・期間を対応づけるための実績データの収集が必要
COCOMO( Costruction Cost Model )
```
開発工数 = a * (予定コード行数)^b * c
開発期間 = d * 開発工数^e
```
a～eは過去のデータを元に求められた定数
- 利点
  - 単純にコード行数から見積もるので、担当者の経験に左右されない見積もりが可能
- 欠点
  - プロジェクトの初期からの導入は不可
  - そもそも開発工数を見積もれない (予定コード数が分かっている前提の見積もり)
  - 定数を決めるための実績データの収集が必要
COCOMO II : コード行数の代わりに、FP を取り入れるなど
標準値法
- WBSの積み上げで開発規模の見積もりを行う
類似法
- 過去の類似プロジェクトの実績から見積もりを行う
- デルファイ法 (デルファイの神託から)。将来予想されるシナリオを複数出し合って、リスクを見積もる方法。

↑

データベース †

↑

データベース設計 †

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

↑

ANSI/SPARC三層スキーマ †

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

↑

ACID †

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

↑

RDB †

Table

　　　列(属性)
　　　　↓
－+---+------+----------+
↑|id |name  |unit      |
　+---+------+----------+
位|1  |太郎  |広報部    |<-- 行（タプル)
数+---+------+----------+
　|2  |花子  |デザイン部|
｜+---+------+----------+
↓|3  |三郎  |経理部    | 
－+---+------+----------+
  |←――　次数　 ――→|

ドメイン
- 値の定義域
- idのドメイン = {1,2,3}
- nameのドメイン = {太郎,花子,三郎}
- unitのドメイン = {広報部,デザイン部,経理部}
- CREATE DOMAIN TEMPERATURE IS INTEGER CHECK(TEMPERATURE > -273)

↑

正規化 †

キー

スーパーキー(Super Key)	行を一意に特定できる属性の組
候補キー(Candidate Key)	スーパーキーの内、必要最小限の属性の組
主キー(Primary Key)	候補キーの内、行を特定するために使うことにした属性の組
代替キー(Althernate Key)	候補キーの内、主キーとして使われなかった属性の組
外部キー(Foreign Key)	別の表の行を参照するためのキー。参照先表の主キー(NOT NULL)

属性の従属関係
今、主キーが (A,B) の複合キーの場合
部分関数従属
- A→C ( Cは、Aが分かれば特定できる)
- B→D ( Dは、Bが分かれば特定できる)
完全関数従属
- (A,B) → E (Eは、(A,B)の組に対して特定される)
推移的関数従属
- A→F→G (Aが分かればFが特定できる、Fが特定できればGが特定できる)
- ※ A→F かつ F→A のとき、AとFは同じモノ。このとき、A と G の関係は部分関数従属

目的
更新時異常の排除 ( 一カ所一事実 = 1 fact in 1 place )

修正時異常	受注と商品マスタがごっちゃだと、商品名が変わると全受注を変えなきゃいけない
挿入時異常	受注と商品マスタがごっちゃだと、受注のない商品は登録できない
削除時異常	受注と商品マスタがごっちゃだと、受注が消えると商品情報が消える

第一正規化
```
[受注伝票]
       
       ↓
       
      1 *
[受注]---[受注明細]
```
- 繰り返し項目・集団項目の排除
- 繰り返し項目を別表にする

第二正規化

      1 *
[受注]---[受注明細]
       
       ↓
       
      1 *          1 *
[受注]---[受注明細]---[商品マスタ]

部分関数従属の排除
キー項目に従属している属性を別表にする

第三正規化

      1 *          1 *
[受注]---[受注明細]---[商品マスタ]
       
       ↓
       
      1 *          * 1
[受注]---[受注明細]---[商品マスタ]
   |*
   |
   |1
[顧客マスタ]

推移的関数従属の排除
非キー項目に従属している属性を別表にする

↑

SQL(DDL) †