基礎科目対策のうち情報・論理について 最終更新:2007.02.12

ビット計算

1つの回路に電流を流すか流さないかによって、「オンかオフか」(1か0か)という2つの情報を送る(処理する)ことができます。
これがデジタルデータの基本単位で、「ビット」といいます。1ビット回路の処理量は、1か0かの2つだけです。
回路を2つにすれば、(0,0)、(0,1)、(1,0)、(1,1)、すなわち
 (1) 回路Aが0で回路Bが0
 (2) 回路Aが1で回路Bが0
 (3) 回路Aが0で回路Bが1
 (4) 回路Aが1で回路Bが1

の4つの組み合わせができますから、処理量は4になります。回路が2つなので2ビットになります。
さらに回路を3つにしてみましょう。
 回路A 0 0 0 0 1 1 1 1
 回路B 0 1 0 1 0 1 0 1
 回路C 0 0 1 1 0 0 1 1

の8つの組み合わせができますから、処理量は8になります。回路が3つなので3ビットになります。
つまり、nビットの処理量Nは、N=2n、2のべき乗となるのです。
逆にいうと、Nのデータ数が扱える回路のビット数nは、n=log2N、2を底とした対数値になります。
ちなみに、現在のパソコンは32ビットCPUなので、一度に扱えるデータ量は232=4,294,967,296(約43億)となります。さらにゲーム機で使われている64ビットCPUは、264(約1,846京 )のデータ処理能力があります。さらに余談になりますが、昔の「ファミリーコンピュータ」や、人類初の月面着陸を果たしたアポロ宇宙船のCPUは8ビットで、データ処理量は28=256でした。
このように、ビット数が多くなると処理量(組み合わせ数)は、膨大になるので、2nでなく、nを「情報量」として定義しています。すなわち、nビットの扱える情報量はnであるということです。正確にいうと、nビットの扱える情報量は、nビットの処理量N(=2n)の2を底とした対数値です。

もしnビットの回路が2つあった場合、処理量は2×2=22nとなります。情報量はlog222nですから2nになります。同様に回路が3つあった場合、処理量は2×2×2=23n、情報量はlog223n=3nとなります。つまり、処理量の掛け算は情報量の足し算になります。これは高校数学で、べきと対数の単元で習いますね。

以下、過去問題を見ながら解説を進めます。

==============過去問題(平成13年度)==============
文字による情報を電子メール等の文字符号で送る場合と、FAX等の文字画像で送る場合の情報量について比較する。ここで、情報量とは、どれだけのものを区別できるかを示す量であり、その単位の1ビットの情報とは、0と1又は白と黒など、2つのうちどちらかであるかを示せることを意味している。2ピットの情報は、1ビットの情報を2つ組み合わせることにより、4つのものを区別することができる。FAXでは32×32=1024の白黒の点配列で漢字を含む日本語の1文字を表すものとすると、この点配列の持つ情報量は1024ビットとなり、この点配列で表せる異なる画像の数は2**1024(注:**はべき乗を表す)となる。この情報を文字画像情報と呼ぼう。
 実際に伝えたい文字の数は65536以下であるものとしよう。これらの文字のどれかということを示す情報は、16ビットあれば十分である。これを文字符号情報と呼ぼう。
 1文字伝えるのに、点配列で表された文字画像情報の情報量は、文字符号情報の情報量の何倍になるか。


(1) 1倍
(2) 16倍
(3) 32倍
(4) 64倍
(5) 1024倍


問題文の中でビット定義なども説明しているため長々としたものになっていますが、要は
 1024ビットの情報量は、16ビットの情報量の何倍か
と聞いているのです。
前述のように、
nビットの扱える情報量はnですから、1024ビットの情報量は1024、16ビットの情報量は16で、1024÷16=64、正解は(4)となります。

==================================================
==============過去問題(平成14年度)==============
ジョーカーを除くトランプカード52枚のうちから1枚を抜き取った。
・このカードがハートであることを知った時の情報量は
     log
24=2bit
 である。
・このカードがキングであることを知った時の情報量は
     log
213=3.7bit
 である。
このカードがハートのキングであることを知った時の情報量は次のどれか。

(1) 1.2
(2) 1.85
(3) 3.1
(4) 5.7
(5) 7.4


今度は情報量の足し算です。
AND条件(AかつB)は、通常は掛け算になります。ハートである確率は1/4、キングである確率は1/13ですから、「ハートかつキング」である確率は1/4×1/13=1/52になります。
ここでは確率の分母を処理量として、2を底とした対数値である情報量(ビット)にしていますから、「ハートかつキング」の情報量は、処理量の掛け算結果の2を底とした対数値になります。
つまりlog2(4*13)=log252=5.7、正解は(4)になります。
・・・・と、こういったややこしいことをしなくても、処理量の掛け算は情報量の足し算と理解していれば、あっさりと2+3.7=5.7と解けます。間違えて掛け算してしまうと、選択肢(5)になるというワナも用意されています。ビットは掛け算しないと覚えておきましょう。
===========================================
==============過去問題(平成16年度)==============
レジスタに正の整数値aを入れ、左に5ビットシフトしてから、aを引く。この結果、レジスタの数値はaの何倍の値となるか、次の中から選べ。
ただし、レジスタ内で数値は2進数として扱われ、上記の操作中であふれは生じないものとする。

(1) 4    (2) 5    (3) 15    (4) 31    (5) 33

「レジスタ」を知らないと途方にくれてしまうかもしれませんが、データ格納場所、下駄箱のようなものだとでも思ってください。ただし横には並びますが、縦には1段だけです。箱の位置は「桁」を表します。つまり、1番右の箱は第1桁(1の位)、右から2番目は第2桁(10の位)です。たとえば「1」という数値を1番右の箱に入れたら1、右から2番目の箱なら10、3番目なら100になります。
ただし、入れる数値はビットの基本単位、デジタルデータですから2進数です。
問題は、aを入れるのですが、入れたあとで左に5ビットシフトします。用語が理解できないと何のことかわかりませんが、つまり、5つ左の箱に入れなおしています。ということは、5桁大きくなっています。これが10進数ならa→a×105ということになりますが、2進数ですから、5桁大きくなったということは、a→a×25です。25は32ですから、a→32aになったということです。
問題文では5ビットシフトの後でaを引いていますから、32a−a=31aとなり、もとのaの32倍、正解は(4)となります。
===========================================

最後に練習問題をやってみましょう。
(練習問題)
 ディスク装置にアクセスするための4ビットのレジスタがある。
 1ビット目には、読み取り許可権が設定されており、ここに信号として1が入力されるとディスク上のファイル読み取りができるようになる。同様に、2ビット目にはファイル作成(新規書き込み)許可権が、3ビット目にはファイル更新(更新書き込み)権が、また4ビット目にはファイル消去権が、それぞれ設定されている。
 このレジスタに、10進数の数値13を入力した場合、ファイルの読取・作成・更新・消去のどれが可能な状態になるか。
 読取   作成   更新   消去 
(1) 不可 不可
(2) 不可 不可
(3) 不可
(4) 不可 不可
(5) 不可 不可
答え

戻る

アルゴリズム(繰り返し計算)

繰り返し計算のあるアルゴリズムは、プログラム構造わかりにくいという人が多いと思います。こういう人は、多少なりともなじみのある形(たとえばフロー図)に整理すると理解しやすくなります。
16年度の問題1-2-5を例にとって、フロー図による整理をやってみましょう。

================過去問題(H16問題1-2-5)================
ファイルから整数データ(最後のデータは0又は負数とする)を読み込んで計算を行なう、以下のプログラムについて、間違った記述を次の中から選べ。

・xの値を0とする
・aに整数データを読み込む
・aが正であれば以下のことを繰り返す
  { ・ x<aならばxにaの値を代入する
    ・ aに整数データを読み込む
  }
・xの値を出力して終了する


(1) 読み込まれた正整数の中から最大値を選んでその値を出力する。
(2) 0又は負の整数が読み込まれると、計算結果を出力してプログラムは終了する。
(3) 最大値を選ぶ対象の整数は何個あってもよい。
(4) 最初に読み込まれる整数が負の場合、出力は行なわれない。
(5) 0又は負数の後に正整数があっても、読み込まれない。


プログラム部分をフローにします。右図を見てください。

●「〜する」というような、無条件に処理していく部分は、長方形の枠の中に実施内容を書いて、順に並べて矢印で実施手順を示す。
実施内容は、「Xの値を0とする」と、そのまま書いてもかまいませんが、「X=0」というように式にできるものは式にしたほうが楽です。
●「〜ならば」といった、条件分岐は、ひし形の枠の中に判断基準を書き、YES/NO判断で左右に分かれるようにする。ここでも「aが正」→「a>0」というように式にします。
●繰り返し部分は、どこからどこまでが繰り返し処理内容かを読み取り(プログラムでは、インデントで字下げして、前後を「{」「}」などで囲って表示されることがよくある)、最後はどこへ戻るのかを把握する。
●処理終了部分には「END」と明示する。なお、開始部分が見難い場合は、処理開始箇所に「START」と明示するとわかりやすくなる。


これを見ながら、選択肢を検討していってみましょう。

(1) 読み込まれた正整数の中から最大値を選んでその値を出力する。
よくわかりませんね。実はこのアルゴリズムは最大値検索を目的としたルーチンなのですが、別にそんなことわからなくてもかまいません。明らかな間違いが見つかればそれでいいのですから、とりあえず正誤判断はせず、放っておきます。
(2) 0又は負の整数が読み込まれると、計算結果を出力してプログラムは終了する。
最初の条件分岐(ひし形部分)でa>0?に対してNOですから、「Xを出力」して「END」に行きます。よって記述内容は正しいとわかります。
(3) 最大値を選ぶ対象の整数は何個あってもよい。
よくわからないので放っておきます。
(4) 最初に読み込まれる整数が負の場合、出力は行なわれない。
フローより明らかなように、「aに整数代入」の後はa>0?の分岐に行きます。ここでa<0であれば「Xを出力」に行きます。よって、「出力は行われない」ことはありません。
ここで明らかな間違いが見つかったので、正解は(4)とし、検討を終了してもかまいません。

(5) 0又は負数の後に正整数があっても、読み込まれない。
最初の分岐でa>0でなければ「Xを出力」して「END」に行き、プログラムは終了しますから、読み込み(aに整数代入)はもう行われません。よって記述内容は正しいとわかります。
==========================================================

もう1問、過去問題を使って、フロー図化の練習をしてみましょう。

================過去問題(H13問題1-2-1)================
次に示すアルゴリズムを実行した結果、表示される値はいくらか。

アルゴリズムE
 ・整数変数xの値を70とする;整数変数yの値を50とする;
 ・xをyで割り算し、余りを整数変数rに代入する;
 ・r=0の条件が成立しない時は、以下の手順を繰り返す:(下の注を参照のこと)
   {・yをxに代入する;
    ・rをyに代入する;
    ・xをyで割り算し、余りを整数変数rに代入する;}
 ・yの値を表示する;
注)まず、r=0の条件が成立するか調べ、成立しなければ{ }内の命令文を実行し、その後r=0の条件が成立するかどうかを調べる。成立しなければ{ }内の命令文を実行する。これを繰り返し、条件が成立したら繰り返しを終了して、次の表示命令文を実行する。

(1) 0
(2) 5
(3) 10
(4) 20
(5) 50


最初の2行は単純処理ですから、長方形枠を手順通りに並べます。処理内容は、「整数変数xの値を70とする」と、そのまま書いてもかまいませんが、「x=70」というように簡潔にしたほうがわかりやすくなります。2行目も「x÷y=z ...r」というように式にします。
3行目は条件分岐です。「r=0」が条件で、YES(成立する)時は繰り返し部分(「{」と「}」で囲まれた部分)を飛ばして、その先にいきます。つまり「yの値を表示する」に行きます。「r=0」がNO(成立しない)場合は、繰り返しになります。
繰り返し内容は、単純処理が3つです。それぞれを式化し、長方形枠に書きます。
「yをxに代入する」→「x=y」
「rをyに代入する」→「y=r」
「xをyで割り算し、余りを整数変数rに代入する」
                  →「x÷y=z 余りr」
その後、繰り返しの頭部分、すなわち条件分岐のところに戻ります。これをみると、r=0かどうかの判断をして、r≠0であれば、繰り返し内の処理(3ステップ)を行い、またr=0かどうかの判断をして、r≠0であれば・・・・というような繰り返し処理であることが理解できます。
==========================================================

なお、H13問題は値(最後に表示されるyの値)を聞いています。処理内容の正誤を聞くH16問題とは、問う内容が異なります。
値を聞いてくる問題で、かつ、フロー化しなくてもプログラム手順通りの実行ができる(トライアル計算できる)場合は、トライアルしてしまったほうが速くなります。
この視点で過去問題を見ると、
   H13・・・・値を聞くので、トライアルのほうが速い
   H14・・・・処理内容を理解しないと答えられないので、フローを作成
   H15・・・・2問とも、処理内容を理解しないと答えられないので、フローを作成
   H16・・・・処理内容を理解しないと答えられないので、フローを作成

となり、フローを書いたほうがいい問題例が圧倒的に多くなっています。

最後に練習問題をやってみましょう。

(練習問題)
 大小に関係なくランダムに並んだ100個の数値データがある。この中から最小値を抽出するプログラムを作ろうとするとき、下記の[ ]に入る処理内容として適当なものはどれか。

(プログラム)
・変数xに数値データから値を読み込む
・変数aにxの値を読み込む
・数値データが残っていれば次の繰り返し処理を行う
 {
  
[ ]場合は、aにxの値を代入する  
  xに数値データから値を読み込む
 }
・aの値を出力して終了する

 (1) aがxより小さい
 (2) aがxより大きい
 (3) aとxが等しい
 (4) 数値データの終わりまで来た
 (5) 数値データが残っている
答え

戻る

構文図

構文図は、文法を図化したもので、厳密な、あいまいさのない文法が必要な世界、つまりプログラミングの世界でよく使われます。

最も単純な構文図を右図に示します。
文章(文字列)を左から流すと、1文字ずつ流れていきます。枝分かれして、数字の0〜9のどれかと合致すると、その先に行きます。文字列が終わっていれば(文章を構成する文字が全部通過したら)終了、そうでなければ戻って、次の文字を枝分かれに流します。
もし文字列の中に条件に合致しない文字、(右の例だと数字以外の文字)が入っている場合、通過できずにエラーとなります。逆に言うと、この構文図に合致する文字列は、数字のみから構成される文字列、つまり「数字」だということになります。

次に、図−1のような構文図を考えてみます。ここで、○で囲まれた記号を終端記号といいます。また□で囲まれた記号を非終端記号と呼び、これらは別の構文図で定義されています。ここでは、「数字」は右上の構文図により定義されているものとします。
図−1では、数字のあとに「だ」という文字が無条件にくっついていないと通過できません。ですから、たとえば「123」という文字列は通過できません。
図−2のようにすると、文字なしでも通過できるようになりますから、「123」でもOKになります。しかし「123よ」は通過できません(文字がないわけでもなく、「だ」でもないため)。
そこで、図−3のようにして「あ」〜「ん」と濁音・半濁音を「50音」として定義します。その上で、図−4のようにすれば、「123だ」「123よ」「123だよ」「123かもしれない」などが通過できるようになります。
図−1 図−2 図−3 図−4

構文図の説明が見られるサイトはいくつかありますので、そちらをよく読んで理解してください。

それでは、構文図が出題された過去問題を見てみましょう。

==============過去問題(平成16年度)==============
構文図を用いて文字列の集合を定義することができる。例えば、図1の構文図は整数の加減算式を定義している。この定義に従えば、1+2−3や1−2が整数の加減算式であることがわかるが、+1や-1は加減算式ではない。
 

図1.整数の加減算式を定義する構文図 図2.a,bの文字列を定義する構文図

次の文字列のうち、図2の構文図では定義されていないものを選べ。

(1) a
(2) b
(3) ab
(4) ba
(5) aaa


図1およびその説明は、構文図の説明なので問題には無関係です。
図2を見ると、最初の「関所」は、「a」以外ならそのまま通過し、「a」ならフリーパスか、あるいはループで戻るというものです。「a」が続く限りループできますから「aaaa」もOKですね。
2番目の「関所」は「a」か「b」以外は通してくれませんから、どちらか以外の文字列を含んでいると通過できません。
選択肢(1)や(2)は第1関門をフリーパスし、第2関門でそれぞれ[a」と「b」を通って終了というものです。
また(3)は第1関門の1回目で「a」のループを通り、第1関門の2回目はフリーパス、第2関門の「b」を通っています。
(5)は第1関門の「a」ループを2回通った後、第2関門の「a」を通ったものです。
ところで第2関門の後はループがありませんから、この「a」や「b」が文末文字ということになります。「a」は第1関門のループでも出てきますから、「a」の後に文字列が続くことはありえますが、「b」の後に文字列が続くことはありえません。
よって、(4)がありえないということになります。
==================================================
==============過去問題(平成16年度)==============
あるプログラミング言語で使われる名前(変数名や関数名)は、次の構文図で規定されているものとする。この時、名前でないものを選べ。ただし、英字はa,b,・・・,z、A,B,・・・,Zのどれか、数字は0,1,・・・,9のどれかである。


(1) A   (2) name   (3) B740   (4) C6H6   (5) 11PM


「英字」「数字」とも非終端記号ですから、別途定義されており、その内容は問題文に「ただし」の後に記載されています。
第1関門が「英字」であり、それ以外の道はありませんから、1文字目が英字でない文字列は通過できません。つまり、(5)が正解になります。
==================================================


戻る

2進数

2進数とは
N進数とは、ゼロから数値を増やしていって、Nになったら桁を1つ上げて、元の桁はゼロにリセットするというものです。
私達が普通使っているのは10進数ですね。0、1、2、3・・・・と増やしていって、10になったら、2桁目(10の位)の数値を1つ増やして、1桁目はゼロに戻します。つまり、「10」になります。
では2進数はどうなるでしょう。0、1、ときて、2になったら、2桁目を1つ増やして、1桁目はゼロにします。つまり、
 0、1、2
ではなく、
 0、1、10
となります。
さらに増やしていくと、10の次は1桁目がゼロから1つ増えて1になり、11となります。その次は、1桁目が2になるので、再び2桁目を1つ増やして1桁目はゼロに戻します。
ところがこのようにすると、2桁目が1から1つ増えて2になってしまいます。そこで今度は3桁目を1つ増やして2桁目はゼロに戻します。つまり、
  11+1=12
 →1桁目の2を0にして2桁目を1つ増やす→20
 →2桁目の2を0にして3桁目を1つ増やす→100
となります。このようにして、2進数の数値と10進数の数値を比べてみましょう。

10進数 10 11 12 13 14 15 16
2進数 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

2進数では、10進数の2、4、8、16で桁が上がっていますね。これらはそれぞれ21、22、23、24に相当しますね。10進数でも桁が上がるのは10、100、1000、10000で、それぞれが101、102、103、104に相当しますから、この点は同じです。つまり、N進数ではN1、N2、N3、N4・・・・で桁が上がるのです。

2進数〜10進数変換
10進数の数値を2進数に変換するには、次のようにすればできます。
例として、10進数の13を2進数に変換してみます。

(1) 13÷2= 6 あまり 1  ↑ あまりを下から上に逆順に読んで並べる
(2) 6÷2= 3 あまり 0  ↑
(3) 3÷2= 1 あまり 1  ↑
(4) 1÷2= 0 あまり 1  ↑

このように、商がゼロになるまで2(N進数のN)で割って、あまりを(4)→(1)の順に(計算して出てきたとは逆順に)並べます。こうすると「1101」が得られます。これが10進数の13を2進数に変換した答えです。
今度は2進数を10進数に変換します。 これは、Σ(2桁数N-1×N桁目の数値)とすればOKです。
2進数の1101を10進数に変換してみましょう。
  4桁目→2(4-1)=23=8で、ここが1なので8×1=8
  3桁目→2
(3-1)=22=4で、ここが1なので4×1=4
  2桁目→2
(2-1)=21=2で、ここが0なので2×0=0
  1桁目→2
(1-1)=20=1で、ここが1なので1×1=1
  合計して、8+4+0+1=13

2進数は何に使うか
コンピュータは電子機器ですから、回路に電流が流れているか流れていないかの2つに1つです。流れている状態(ON)を1、流れていない状態(OFF)を0とすれば、この組合せで情報が伝達できます。
4つの回路のON/OFFの組み合わせで情報を送ると、
  0000、0001、0010、0011、0100、0101、0110、0111、1000、1001、1010、1011、1100、1101、1110、1111
の16通りの情報が流せます。前表のように、これは10進数で10〜15にあたります。コンピュータでは、この16通りの情報を16進数で扱います。

16進数 10
10進数 10 11 12 13 14 15 16
2進数 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000

戻る

論理演算

論理演算とは、真か偽かの2通りの結果だけを使った、集合における演算で、プログラミング言語などではビット演算とも言います。
与えられた命題が正しい場合を真(true)、正しくない場合を偽(false)といいます。
ここで「命題」とは、論理学用語で、意味に不明瞭なところがない文章のことです。
たとえば「私の身長は170cm以上である」という文書は、あいまいな点がないので命題です。一方、「私は忙しい」というのは、「忙しい」のところにあいまいさ・不明瞭さがある(「忙しい」と「忙しくない」の間の明瞭な境界がない)ので、命題とはいいません。
さて、「私の身長は170cm以上である」という命題に対し、身長175cmの人を当てはめると、命題は正しくなります。よって、真です。
身長165cmの人を当てはめると、命題は正しくなくなります。よって、偽です。
このように、同じ命題でも、当てはめる要素によって真偽は異なることがあります。

論理演算には、以下のものがあります。
ORとNOR、ANDとNANDは、それぞれの否定なのでわかりやすいと思います。ちょっとややこしいのはXORです。XOR=OR-ANDと理解してください。
試験で必要になることが考えられる知識は、上の3つ程度と思われます。

演算種類 演算結果が真となる条件 イメージ(ベン図)
論理和

OR
AとBのいずれかが真である(両方真でもOK)
論理積

AND
AとBのいずれもが真である
排他的
論理和

XOR
AとBのいずれか一方のみが真である
論理和
の否定

NOR
ORの真偽反転(ORで偽であるものが真となる)
論理積分
の否定

NAND
ANDの真偽反転(ANDで偽であるものが真となる)
論理否定

NOT
真偽反転(真であれば偽に、偽であれば真になる)

たとえば、命題Aが身長170cm以上、命題Bが体重60kg以上としてみます。これに対して、様々な身長・体重の場合に、論理演算の結果がどうなるかみてみます。なお、下表の中で○は真、×は偽です。

命題A 命題B 身長cm 体重kg OR AND XOR NOR NAND
身長170cm以上 体重60kg以上 175→真 70→真 × × ×
175→真 55→偽 × ×
165→偽 65→真 × ×
165→偽 55→偽 × × ×

戻る