授業展開#9: - 埼玉大学工学部 応用化学科

中間試験確認
1.情報について、どういう概念か簡単に示せ。(5)
多くの人にとって価値、関心のあるデータである。
2.確率が100分の1の情報量と、百万分の1の情報量を有効
数字3桁で示せ、但し、log102=0.301とする。(3×2)
100分の1 :I(a)=-log2P(a)=-log2(0.01)
=2log2(10)=2log10(10)/log10(2)
=2/log10(2)=6.64bit
百万分の1 :I(a)=-log2P(a)=-log2(0.000001)
=6log2(10)= 6log10(10)/log10(2)
=6/log10(2)=19.9bit
中間試験確認
3.情報の通信手段をいくつか示し、情報伝達の際に
起こる問題点を示せ。(2+3)
手段:伝令、飛脚、伝書鳩、のろし、手旗信号、モー
ルス信号、電話など。
問題点:ノイズが入る。機密が漏れる。
4.12bitで表現できる記号の数は何通りか。また、
8192 bitは何byteか。(2×2)
12bit:212=4096
8192 bit = 8192/8 = 1024 byte
中間試験確認
5.デジタルの欠点を簡潔に述べよ。(5)
サンプリング(A-D変換)時に情報の劣化がある
データが不連続である(時間の離散、値の離散)
6.十万字の漢字を取り扱いたい場合には最低何bit必
要か。整数で答えよ。必要であればlog102=0.301を
用いよ。(5)
2n>105 になるようなnを求める。両辺のlogをとる。
n・log102 > 5
n > 5 / 0.301 = 16.6
ゆえに17ビット必要である。
中間試験確認
7.SXGA(横1280×縦1024ドット)、RGB各8ビット
の場合の1画面の情報量は何kbyteになるか。(5)
1280×1024×8×3 bit
=1280×1024×3 byte = 1280×3 kbyte
=3840 kbyte
8.画像情報は音声情報に比べて情報量が大きいた
めその扱いが困難になることが多い。そのための対
策について簡潔に答えよ。また、その際に用いるソ
フトのことを何と呼ぶか。(2×2)
圧縮する。 コーディック。
中間試験確認
9.以下の2進数を10進数に、10進数を2進数に変換
せよ。(5×2)
101.1011 (2進)
=1×22+1×20+1×2-1+1×2-3+1×2-4
=4+1+0.5+0.125+0.0625
=5.6875
17.625(10進)= 16+1+0.5+0.125
=1×24+1×20+1×2-1+1×2-3
=10001.101
中間試験確認
10. 10進数103を8ビット固定長の2進数で表せ、
また、-103を1の補数表現、2の補数表現で表
せ。(3×3)
10進 103 =64+32+4+2+1
= 01100111
1の補数表現 10進 -103 = 2進 10011000
2の補数表現 10進 -103 = 2進 10011001
中間試験確認
11.コンピュータの5大機能について5つ挙げよ。
制御、演算、記憶、入力、出力(5)
12.OSの役割を3つ挙げよ。(5)
 ハードウエア資源の管理(キーボードやメモリの管
理など)
 アプリケーションソフトに共通する機能の提供(メ
ニュー表示など)
 ファイルシステムの提供(FDD、HDDなどのファイ
ル管理)
中間試験確認
13.RAMとROMについてそれぞれの特徴を説明せよ。
(3×2)
RAMは、電源を切ると内容が消える。書き込み可能。
ROMは、あらかじめ情報が書き込まれている。電源を
切っても情報は消えない(不揮発性)。書き込みはできな
い。
14.バス幅32 bit、クロック数800 MHzの時の転送速
度は何byte/sか。(5)
32×800×106 bit/s = 32×108byte/s
中間試験確認
15.機械語を人間が読み易いように表現したものを何
と言うか。また、それを機械語に変換するソフトをな
んと言うか。(2×2)
ニーモニック、アセンブラ
16.記憶面数:2、トラック数:80/面、セクタ長:512
byte、セクタ数:18/トラックのFD(フロッピーディ
スク)がある。この記録容量を計算してbyte単位で
答えよ。(5)
記憶容量=2×80×512×18=1,474,560byte
中間試験確認
17.以下の略号の省略する前の用語を英字で[ ]内に書き、1行程
度で意味を説明せよ。(3×4)
(1)CPU [Central Processing Unit]
コンピュータの演算や制御を行う中心部分
(2)SPEC [Standard Performance Evaluation
Corporation]
コンピュータの処理速度を計測し、比較する組織
(3)BIOS [Basic Input/Output System]
コンピュータの電源を入れてから立ち上がるまでの処理を行うシス
テム
(4)GUI [Graphical User Interface]
アイコンやマウスを使って操作し易くしたコンピュータの操作環境
授業展開#9
並べ替えと一筆書きのアルゴリズム
勝ち抜き戦のアルゴリズム
お立ち台方式
① 全員を一列に並べる。
② お立ち台を用意して、1番目の人を立たせる。
③ お立ち台の1番目は2番目と対戦させる。
④ 1番目が勝った場合:2番目を戻し、3番目と対戦
させる。
2番目が勝った場合:1番目を戻し、2番目をお立
ち台に立たせ、3番目と対戦させる。
・・・3番目以降との対戦を次々と行い、負けると元の
位置に戻り、交代する。これを最後のn番目まで繰り
返す。

優勝旗方式
① 全員を一列に並べる。
② 優勝旗を用意して、1番目の人に持たせる。
③ 1番目は2番目とその場で対戦させる。
④ 1番目が勝った場合:2番目と場所を入れ替え、3
番目と対戦させる。
2番目が勝った場合:2番目に優勝旗を受け渡し、
3番目と対戦させる。
・・・3番目以降との対戦を次々と行い、負けたら優勝
旗を渡し、勝ったら場所を入れ替える。これを最後
のn番目まで繰り返す。
 トーナメント方式
 リーグ戦方式

並べ替え(ソート)のアルゴリズム
ソート:ある集まりをある特徴量の順に並べること。
 ソートキー:並べるために使われる特徴量
 順次法
① n人を1列に並べる。
② 身長順に並ぶ場所Pを別に作っておく。
③ 一人目をPに連れて行く。
④ 二人目をPに連れて行き、Pより大きければ後ろに、
小さければ前に入れる。
⑤ 三人目をPに連れて行き、先頭から順に比べて、
三人目より高い人がいたら、その前に割り込ませる。
いなければ、一番後ろに並べる。
・・・これを全ての人に行う。

勝ち抜き法
勝ち抜き法で優勝者を決め、1位を除いた残りの中
で2位を決定し、これを最後まで行う。

順序分類法
例えば、1-100まで書かれた紙を番号順に並べ替
える場合、1-10、11-20、・・・91-100の10個の山
に分類し、次にそれぞれの山の中でソートする。

2分分類法
順序分類法で常に分類を常に2つにする方法。

一筆書きのアルゴリズム
ケーニヒスベルグの橋
オイラーの時代に、ある貴族が出した懸賞問題「下
図において1~7のすべての橋を一度だけ渡って出
発点に戻る経路は存在するか。」。オイラーはたちど
ころに解いたとされる。

1
2
3
4
5
6
7
一筆書き
 線形図形を一筆で描くこと。
 一筆
→線を描き始めてから鉛筆を紙から離すまで。
 同じ点は何度通っても良いが、同じ線分は2
度以上なぞってはいけない。
オイラー閉路
 節点:線画において線分が接続している点や
交差している点、線分の端点。
 辺:節点と節点をつなぐ線分。
 離散グラフ(グラフ):節点と辺からなる図形。
 閉路:辺の重複がない経路の始めの節点と
終わりの節点が一致する場合。
 オイラー閉路:一筆書きの閉路のこと。
一筆書きとオイラー閉路
一筆書きの例
オイラー閉路の例
•任意の線画図形が一筆書きできるとはかぎらない。
•あるグラフにオイラー閉路があれば一筆書きできる。
•逆に、一筆書きできる図形は、全てオイラー閉路というわけではない。
オイラー閉路の存在判定問題
統計的に調べる。
①辺にラベルを付けて、あらゆる可能な並べ方を全部挙
げる。
4辺(a,b,c,d)ある場合は、4! = 24通り。
②片っ端から、閉路になっているかどうかチェックする。
 辺の数がn本ある場合は、n! 通りある。
n=10 でも 10! = 3,628,800

行き当たりばったりでは、困難。
オイラー閉路の判定には、簡単なアルゴリズムがある。
オイラーの定理
節点の次数:離散グラフで節点に出入りする辺の総
数。
 グラフが連結である:任意の2つの節点の間が何ら
かの経路でつながっていること。


オイラーの定理
ある離散グラフが連結であって、かつ、全ての節点
の次数が偶数ならば、その離散グラフにはオイラー
閉路が存在する。逆に、オイラー閉路が存在すれば、
その離散グラフは連結で、すべての節点の次数は
偶数である。
一筆書きができるグラフ
点から出ている線の数がどれも偶数本(2,4,6...)
であるグラフ
 奇数本(1,3,5...)の線が出ている点がちょうど2つ
だけあるグラフ (オイラー閉路にはならない)

3
a
b
c
d
e
f
c
a
b
d
5
g
f
e
3
3
g
オイラー閉路を求めるアルゴリズム
ある連結な離散グラフGのすべての節点の次数が偶
数であるとする。
① Gに辺の重複のない1つの閉路Lを描く。(その閉路L
がすべての辺を含んでいれば、オイラー閉路完成)。
② GからLを除いて得られる残りのグラフも、すべての節
点が偶数であるから、残りのグラフも、閉路L上の節点
からLに含まれていない辺をつないで同じ節点に戻る
閉路L’が必ず構成できる。LとL’からなる図形は、一
つの閉路と見なせ、それを新たに離散グラフGの閉路L
とする。
③ ②の手順をすべての辺がLに含まれるまで続ければ、
得られた閉路Lはオイラー閉路である。
アルゴリズムの検証
オイラー閉路!
オイラー閉路演習
奇数次数
オイラー閉路である
一筆書き可能
オイラー閉路でない
一筆書き可能