中間試験確認１．質の良い情報とは、どういう情報をいうか簡単に示せ。（５）必要な内容が網羅されている。よく更新されている。間違いがない。２．確率が百万分の1の情報量を有効数字３桁で示せ、但し、log102=0.301とする。（５） I(a)=-log2P(a)=-log2(0.000001) =6log2(10)= 6log10(10)/log10(2) =6/log10(2)=6/0.301＝19.9bit 中間試験確認３．符号語集合体（00000, 11111）がある。最小符号語間距離dminはいくらか。また、符号語00101は、どの符号に訂正されるか。（２ｘ２）最小符号語間距離 dmin ＝ 5 00101 → 00000 ４．一組のトランプ（ジョーカーを除く）を表現するためには、何bit必要か。（５） 25＝32 ＜ 52 ＜ 2６＝64 なので、６ bit 必要中間試験確認５．アナログとデジタルの違いについて、簡潔に述べよ。（５）デジタル（離散量）：１個、２個と数えることができる量アナログ（連続量）：厳密に量ればいくらでも細かく測れる量６．通信を行う際のデジタルの利点について説明せよ。（５）情報の劣化がない。高速通信。暗号化可能。圧縮可能中間試験確認 7.ニ十万字の漢字を取り扱いたい場合には最低何bit 必要か。整数で答えよ。必要であれば log102=0.301を用いよ。（５）２ｎ＞２X１０５になるようなｎを求める。両辺のｌｏｇをとる。ｎ・ｌｏｇ10２＞ log１０２+5 ｎ＞１ + 5 / 0.301 ＝ 17.6 ゆえに18ビット必要である。中間試験確認８．ＳＸＧＡ（横１２８０×縦１０２４ドット）、ＲＧＢ各８bit 階調とする。１画面のデータ容量をkbyteで答えよ。（５） 1280×1024×8×3 bit ＝1280×1024×3 byte = 1280×3 kbyte ＝3840 kbyte 中間試験確認 9.以下の10進数、２進数、16進数を、10進数、２進数、16進数に変換せよ。但し、16進数は1-9の後はA, B, C, D, E, Fと続けて繰り上がる記数法とする。（２ｘ６） 108（10進）＝01101100（２進）＝６C（16進） 89（10進）＝01011001（２進）＝59（16進） 38（10進）＝00100110（２進）＝26（16進）中間試験確認 10. 10進数123を８ビット固定長の２進数で表せ、また、 -123を１の補数表現、２の補数表現で表せ。（２ｘ3） 10進 123 ＝ 01111011 ２進１の補数表現 10進 -123 ＝ 10000100 ２進２の補数表現 10進 -123 ＝ 10000101 ２進１１．次の真理値表を完成させよ。（3ｘ2） x y z x and (y or z) x or (not y) 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 1 1 0 1 1 中間試験確認１２．CPUの機能を３つ示せ。（３）制御、演算、記憶１3．ＯＳの役割を３つ挙げよ。（6）  ハードウエア資源の管理（キーボードやメモリの管理など）  アプリケーションソフトに共通する機能の提供（メニュー表示など）  ファイルシステムの提供（ＦＤＤ、ＨＤＤなどのファイル管理）中間試験確認１４．RAMとROMについてそれぞれの特徴を説明せよ。（3×２）ＲＡＭは、電源を切ると内容が消える。書き込み可能。ＲＯＭは、あらかじめ情報が書き込まれている。電源を切っても情報は消えない（不揮発性）。書き込みはできない。１５．バス幅32 bit、クロック数800 MHzの時の転送速度は何byte/sか。（５） 32×800×106 bit/s = 32×108byte/s 中間試験確認 1６．機械語を人間が読み易いように表現したものを何と言うか。また、それを機械語に変換するソフトをなんと言うか。（3×２）ニーモニック、アセンブラ 1７. ブートストラップローダとは何か説明せよ。（5）コンピュータの電源をONした後、OSをロードして起動するための特殊なプログラム１８．レジスタとは何か説明せよ。（5）一時的なデータの記憶を行うCPUにある記憶装置授業展開＃９並べ替えと一筆書きのアルゴリズムアルゴリズム  コンピュータを使ってある特定の目的を達成するための情報処理の方法、処理手順。  あるグループで代表一人だけを決める勝ち抜き戦のアルゴリズム、一筆書きのアルゴリズムを検討今、ｎ人の勝ち抜き戦で優勝者一人を決定する勝ち抜き戦のアルゴリズムお立ち台方式 ① 全員を一列に並べる。 ② お立ち台を用意して、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 オイラー閉路演習奇数次数オイラー閉路である一筆書き可能オイラー閉路でない一筆書き可能