2 情報の理論に関すること

論理演算

コンピュータでは、データはすべて2進数の1,0で表現しますが、1と0の値はこのほかにも、真・偽の論理値として使われます。 これは、たとえば“○か×か”、“正しいか正しくないか”など、条件を判断する場合にも使用されます。

ベン図

ベン図は、条件が成立するときには円の内側、不成立の時には円の外側に属していることを表す図です。

集合表記の意味、たとえば、X∪YはXとYの和集合つまり「または」の意味、 X∩YはXとYの積集合つまり「かつ」の意味、X―はXの補集合つまり「でない」の意味を 理解していればベン図を読んだり書いたりするとき簡単です。

ここでは、ベン図を読む例として(A―∩B∩C)∪(A∩B∩C―)の例を示します（基本情報H18春[問7]）。

以上のことから、上のベン図は「(A―∩B∩C)∪(A∩B∩C―)」となります。

シフト演算

コンピュータは、シフト演算という方法で掛け算を行います。 シフト演算は、データのビットの並びを左右に何ケタかずらす演算です。

論理シフト演算

論理シフト演算はデータを数値として扱うのではなく、 単にビットの並びとして扱うときに使われます。

8ビットのデータを左に2ビット論理シフトする例を次の図に示します。 左に2ビット論理シフトした結果、あふれた2ビットはそのまま捨てられます。 また、空いた左側の2ビットは0で埋められます。

図8ビットのデータを左に2ビット論理シフトする例

正の数値を扱うだけであれば、論理シフトで掛け算と割り算が行えます。 2倍、4倍、8倍、…や2分の1、4分の1、8分の1、…を行う2進数の乗算や除算は、論理シフトで実現できます。 ただし、論理シフトでは負の数値を扱うことは出来ません。

論理演算の利用

論理演算は、コンピュータ内部でビット列の操作に使われています。 補数を求める場合のビットの反転や特定のビットを反転することにより、 コードの変換などさまざまなビット列の操作に応用されています。

パリティチェック方式での利用

パリティチェック方式とは伝送データの誤りを検出する方式の1つです。 これは伝送するデータの一文字ごとに1ビットのパリティを付加し、 パリティビットを含めて１ビットの数が偶数になるように規定したものを偶数パリティ、 奇数になるようにしたものを奇数パリティといいます。

なお、パリティビット(parity bit)とは、 パリティチェック方式で伝送データの1文字ごとに付加される1ビットのことで冗長ビットともいいます。

たとえば、データを10101010としたとき、16進数7FとのANDをとると、 最上位をパリティビットとする８ビット符号において、 パリティビット以外の下位7ビットを得るためのビット演算（基本情報H18春[問6]）となります。

パリティチェック方式での利用の例

論理回路

NAND回路

NAND回路（）は、論理積の否定になります。

ここで、NAND回路の例を示すと次のようになります（基本情報H18春[問16]）。

なお、ド・モルガンの法則は、次のとおりです。
X・Y―――――＝X――＋Y――
X＋Y―――――＝X――・Y――

状態遷移

状態遷移図

状態遷移図とは、状態の移り変わりを図で表したものです。 時間の経過や事象の発生に基づいて記述していきます。

なお、次の例のように表形式で表す場合もあります。

状態遷移表は現在の状態と与えられた条件により次の状態を求めるための表です。 現在の状態である表の縦軸と、与えられた条件である横軸の交点を次の状態とします。

Status Tigger tableとも呼ばれ、状態(Status)と条件(Tigger)によって状態の遷移のルールを表しています。

入力信号の検査の例

次の状態遷移表をもつシステムの状態がS1であるときに、 入力信号（t1、t2、t3、t4、t1、t2、t3、t4）を順次入力したとき、最後の状態をしらべます。 なお、、空欄は状態が変化しないことします（基本情報H14秋[問10]）。

状態 信号	S1	S2	S3	S4
t1		S3
t2	S3		S2
t3			S4	S1
t4		S1		S2

ここで、初期状態をS1として（t1、t2、t3、t4、t1、t2、t3、t4）の信号が入力されると状態は次のように変化します。
(S1+t1)＝S1⇒(S1+t2)＝S3⇒(S3+t3)＝S4⇒(S4+t4)＝S2⇒
(S2+t1)＝S3⇒(S3+t2)＝S2⇒(S2+t3)＝S2⇒(S2+t4)＝S1

文字列の検査の例

下の表は、文字列を検査するための状態遷移表です。 検査では、「12.2」について、初期状態aとし、文字列の検査しています（基本情報H18春[問9]）。

		文字列
		空白	数字	符号	小数点	その他
現 在 の 状 態	a b c d	a a e a	b b b e	c e e e	d d d e	e e e e

		文字列
		空白	数字	符号	小数点	その他
現 在 の 状 態	a① b③⑤ c d⑦	a a e a	b② b④ b e⑧	c e e e	d d d⑥ e	e e e e

ポーランド表記法

ポーランド記法とは、演算子をそのオペランドの前(または後)に置く表記法をいいます。 演算子を後におく記法を逆ポーランド記法ともいいますが、 単にポーランド記法ということも多いようです。

たとえば、「a＋b」は「ab＋」となります。 ポーランド記法は、評価の容易さと括弧などの区切りを用いずに式を一意的に表記できることなどから、 言語プロセッサで利用されています。

なお、をポーランド記法で表すときは、以下のように木で表現し、節から上に出るときにそこの記号を書いていくと便利です。

ここでは、Y＝(A＋B)×(C－(D÷E))という式をポーランド表記法で表現する例を説明します（基本情報H18春[問10]）。
木で表現し、節から上に出るときにそこの記号を書いていくと
となります。

最後に「Y＝」の部分を加えると、

YAB＋CDE÷－×＝ となります。

三角グラフ

正三角形の内部の点から、各辺に下ろした垂線の長さの和は一定で(図1参照)、 三角グラフは、この性質を利用して、三つの辺に対応させた要素の割合を各辺への垂線の長さとして表したグラフです。

図2の三角グラフは、3種類のソフトについて、A～Dの4人の使用率を図示したものです（基本情報H18春[問11]）。

この解釈の例として、点Aはワープロフトのあたりの上にあるので、ワープロソフトの辺に対応して垂線を下ろせません。

これより、Aさんはデータベースと表計算ソフトを同程度に使用していることが分かります(図3)。 また、図4のように、Bさんは表計算ソフトの使用率が他のソフトの使用率に比べて高いことが分かります。

戻る