1.1計算の基礎理論(1)
1.1.1 信息量,信息源,逻辑运算
这本书讲得不详细,似乎只是个大纲。这些在大学学过的课程早就忘了,今天还要查查资料。
計算の基礎理論
1.情報量の計算:
有る事件の発生確率はP(j)とすると、この事件が確定するため必要な情報量I(j)は
I(j)=-log_2 P(j) bit
だから、発生確率が1/2の事件は1bitの情報量がある。(なぜならば、発生確率1/2は1bitの0または1で確定できるから)
これは大学の「informatics」の基礎の基礎だった。ここまでは覚えている。
次の平均情報量H(エントロピー)はすっかりと忘れた。(注:平均情報量H(エントロピー)=entropy就是熵的意思)
j1・・・jnというn個事件を確定するために、平均的に必要な情報量は:
H=P(j1)×I(j1)+P(j2)×I(j2)+・・・+P(jn)×I(jn)=ΣP(ji)×I(ji)
上記の平均情報量は、j1・・・jnのn個事件の発生確率は等しい時は最大である。
Hmax=ΣP(ji)×I(ji)=log_2 n
2.情報源
马尔科夫(Markov)信息源
マルコフ情報源:ある時点で起こった事件の発生確率が、その前に起こったn個事件の発生確率に依存する情報源である。
n=1の時に、単純マルコル情報源と言う。
エルゴード情報源
情報源で起こる事件の発生確率は長い期間にわたり統計的に観察すると、ある値に収束することがある。このような情報源はエルゴード情報源である。
例えば、サイコロのある値が出る確率は長期間で観察する時、1/6に収束する。
<すっかり忘れた。>
3.論理演算(逻辑运算)
x and y ⇒ x・y
x or y ⇒ x+y
not x ⇒^x (xの上に横線)
同一の法則(同一律):x・x=x x+x=x
交換法則(交换律):x・y=y・x x+y=y+x
結合法則(结合律):x・(y・z)=(x・y)・z x+(y+z)=(x+y)+z
分配法則(分配率):x・(y+z)=x・y+x・z x+(y・z)=(x+y)・(x+z)
ド・モルガンの法則(中文叫啥来着?):not(x・y)=not(x)+not(y) not(x+y)=not(x)・not(y)
4.カルノー図
論理演算式を簡略化するツールである。大学時代は結構得意だったが、今は全然できなくなった。後で資料を探す。
Labels: AP考试, 第一章 コンピューターの基礎知識