コンピュータサイエンス レポート課題回答例 2004年7月
=============================
1、２進数どうしの計算
1-1 ・11010 + 1111 =
=============================
答: 101001
(１０進数に直して計算した場合は、 26+15=41となり、
41を2進数に変換して同じ答えとなる)
=============================
1-2 ・11010 - 1111 =
=============================
答: 1011
(１０進数に直して計算した場合は、26-15=11となり、
11を2進数に変換して標記の答えになる)
=============================
1-3 ・1-2の答に1111を足し、11010になることを確認せよ。
=============================
1011 + 1111 = 11010 で確認できる。
(１０進数に直して計算する場合は、
11 + 15 = 26となり、26を２進数に変換すると
11010となる)
=============================
2、２進数・10進数の変換
2-1 ・508(１０進数）を2進数に変換せよ。
=============================
答: 111111100
(508 = 256 + 128 + 64 + 32 + 16 + 8 + 4と
分解できるため)
(別解: 508= 511 - 3であり、
２進数で書くと 111111111 - 11 となり、
結果として 111111100 となる)
============================
2-2 ・10101111(２進数) を１０進数に変換せよ。
============================
答: 175
(128 + 0 + 32 + 0 + 8 + 4 + 2 + 1){
============================
3、情報エントロピー
3-1 あるさいころを投げたとき、必ずそのさいころは1の目が出るという。
さいころを一回投げたときに得られる平均情報量を求めよ。
============================
答:
平均情報量をHとおく。それぞれの事象に対応する確率をPとおくと、
H = - P1 log P1 - P2 log P2 - ..... - Pn log Pn
= - 1 log 1 = 0
(重要: log 1 = 0 となる。グラフを見直し、確認せよ)
============================
3-2 コインを投げたとき、表が出る確率が1/2、裏が出る確率が1/2のときの、
コインを一回投げたときに得られる平均情報量を求めよ。
============================
答:
平均情報量をHとおく。それぞれの事象に対応する確率をPとおくと、
H = - P1 log P1 - P2 log P2 - ..... - Pn log Pn
= - 1/2 log 1/2 - 1/2 log 1/2
= -1/2 (-1) - (1/2) (-1) = 1
(log 1/2 = log (2)^(-1) = -1 であるため)
============================
3-3 3-1,3-2で得られた情報量の単位は何か。
============================
答:bit (ビット)
============================
3、論理式
★この中での計算はすべて論理演算(ブール代数)を使って考えよ。
3-1
論理和、論理積、否定、のそれぞれの演算について、真理値表を作成せよ。
============================
答:Ａ、Ｂ、を論理変数だとする
Ａ Ｂ Ａ＋Ｂ(論理和) Ａ・Ｂ(論理積)
-----------------------------------------
０ ０ ０ ０
０ １ １ ０
１ ０ １ ０
１ １ １ １
Ａ not Ａ(否定)
-------------------
０ １
１ ０
============================
3-2
「+」「・」はそれぞれどの演算に対応するか延べよ。
============================
答: それぞれ、論理和・論理積を表す。
============================
3-3
・以下の自販機の動作についての真理値表をつくり、論理式に表し、
論理回路で表せ。
・100円を入れてボタン1を押すとジュースがでてくる。
・100円を入れてボタン2を押すとパンと20円のお釣りがでてくる。
============================
答1: (答えを2種類掲載します)
＜真理値表1＞
100円 ボタン１ ボタン２ ジュース パンと20円
A B C X Y
--------------------------------------------------------------
０ ０ ０ ０ ０
０ ０ １ ０ ０
０ １ ０ ０ ０
０ １ １ ０ ０
１ ０ ０ ０ ０
１ ０ １ ０ １
１ １ ０ １ ０
１ １ １ １ １
★ボタンを同時に二つ押すと、ジュースもパンとお釣りもでてくる
というのは自販機としては変ですが、ボタンを同時に押す人はいない
と仮定しています。あくまでも問題をときやすくするための方便として
答1 ではこうしています。
＜論理式1＞
X = A ・B・(not C) + A・B・C = A・B・(C + not C) = A・B
Y = A ・(not B) ・C + A・B・C = A・(B + not B)・ C = A・C
★not の論理記号をテキストでは書きにくいので、 not A という表記を
使っています。
＜訂正版:論理回路1＞
■B■----------------|-------|
| AND |------- X
|-------|------ |
■A■--------|
|-------|-------|
| AND |----------Y
C----------------|-------|
★論理記号の代わりに四角に AND・OR等の名前を入れたものを
使っています。正しい記号に読み直してください。
答2: (答えを2種類掲載します)
＜真理値表2＞
100円 ボタン１ ボタン２ ジュース パンと20円
A B C X Y
--------------------------------------------------------------
０ ０ ０ ０ ０
０ ０ １ ０ ０
０ １ ０ ０ ０
０ １ １ ０ ０
１ ０ ０ ０ ０
１ ０ １ ０ １
１ １ ０ １ ０
１ １ １ ０ ０
★ボタンを同時に二つ押すとなにもでないとしました。
＜論理式2＞
X = A ・B・(not C)
Y = A ・(not B) ・C
★not の論理記号をテキストでは書きにくいので、 not A という表記を
使っています。
＜論理回路2＞
A----------------|-------|
| AND |-------|
|-------|------ | |---|-----|
B--------| | AND |--- X
|-------| |---|-----|
C--------------- | NOT |-------|
|-------|
A----------------|-------|
| AND |-------|
|-------|------ | |---|-----|
C--------| | AND |--- Y
|-------| |---|-----|
B--------------- | NOT |-------|
|-------|
★論理記号の代わりに四角に AND・OR・NOT 等の名前を入れたものを
使っています。正しい記号に読み直してください。
この図では、Xについて、Yについてをわけて、二つの図にわけて書きましたが、
まとめて書いてもかまいません。
=================================
4、アルゴリズム
4-1 人の年齢から、
・自動車の免許をとることが出来るかどうか
・原動機付き自転車の免許をとることができるかどうか
を判断できるアルゴリズムを図に表せ。
=================================
回答例:
START(端子)
↓
N に年齢を入力(処理)
↓
N<16 (判断) -----|
↓ ↓ YES
↓NO ↓
|---- n >=18(判断) 原付の免許・自動車の免許
|YES ↓ の両方をとることができない(処理）
↓ ↓NO ↓
↓ 原付の免許はとれ ↓
↓ 自動車の免許は ↓
↓ とれない(処理） ↓
原付の免許も ↓ ↓
自動車の免許 ↓ ↓
も取れる(処理) ↓ ↓
↓ ↓ ↓
↓ ↓ ↓
-------------------------------
↓
END (端子)
★端子、判断、処理に関しては適切な記号で囲むこと。
★これは回答例である。回答は他に多くの可能性がある。
======================================
4-2 1から5を足すアルゴリズムを図に表せ。
======================================
回答例:
START(端子）
↓
↓
i ← 1
S ← 0 (処理）
↓
↓
→ i > 5 (判断) → |
↑ ↓ ↓ NO
↑ ↓YES ↓
↑ ↓ S← S+i
↑ ↓ i← i+1 (処理)
↑ ↓ ↓
-----------------------
↓
Sを出力(処理）
↓
END(端子)
★端子、判断、処理に関しては適切な記号で囲むこと。
★これは回答例である。回答は他に多くの可能性がある。
======================================
4、データ構造
待ち行列とスタックのデータ構造の特徴をそれぞれ書け。
======================================
回答例:
待ち行列:
1、入ってきたデータはそれ以前に発生したデータ列の最後に
付け加えられる。
2、データを取り出す際には、データ列の先頭から、
順に一つづつデータを取り出される。
という特徴があるデータ構造である。
FIFO(First-In First-Out)とも呼ばれる。
スタック:
1、発生したデータはをそれ以前に発生したデータの上に積み重ねて
保存される。
2、データを取り出す際は、積み重ねられたデータの一番上、
すなわち最後に保存されたデータが一番最初に取り出される。
という特徴があるデータ構造である。
LIFO(Last-In First-Out)とも呼ばれる。
(ここまで)
※連絡は、授業で配った吉野のメールアドレスまで。