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