中間試験確認 多くの人にとって価値、関心のあるデータである。 １．情報について、どういう概念か簡単に示せ。（５） 　　多くの人にとって価値、関心のあるデータである。 ２．確率が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７ビット必要である。 画像情報は音声情報に比べて情報量が大きいためその扱いが困難になることが多い。そのための対策について簡潔に答えよ。（５） 画像情報を圧縮する。静止画ではJPEG、動画ではMPEGなどの方式がある。 ５．ＲＡＭの特徴を３０文字程度で説明せよ。（５点） 書き換え可能であるが、揮発性のため電源を切ると内容が消える。（３０文字）

中間試験確認 7.ＳＸＧＡ（横１２８０×縦１０２４ドット）、ＲＧＢ各８ビットの場合の１画面の情報量は何ｋbyteになるか。（５） 1280×1024×8×3 bit ＝1280×1024×3 byte = 1280×3 kbyte ＝3840 kbyte ８．画像情報は音声情報に比べて情報量が大きいためその扱いが困難になることが多い。そのための対策について簡潔に答えよ。また、その際に用いるソフトのことを何と呼ぶか。（2×2） 　圧縮する。　コーディック。　

中間試験確認 9.以下の２進数を１０進数に、１０進数を２進数に変換せよ。（5×2） 101.1011 （２進） 　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行程度で意味を説明せよ。（３×４） １7．以下の略号の省略する前の用語を英字で[　]内に書き、1行程度で意味を説明せよ。（３×４） （１）CPU　[Central Processing Unit] 　コンピュータの演算や制御を行う中心部分 （２）SPEC　[Standard Performance Evaluation Corporation] 　コンピュータの処理速度を計測し、比較する組織 （３）BIOS　[Ｂａｓｉｃ　Ｉｎｐｕｔ／Ｏｕｔｐｕｔ　Ｓｙｓｔｅｍ] 　コンピュータの電源を入れてから立ち上がるまでの処理を行うシステム （４）GUI　[Ｇｒａｐｈｉｃａｌ　Ｕｓｅｒ　Ｉｎｔｅｒｆａｃｅ] 　アイコンやマウスを使って操作し易くしたコンピュータの操作環境

授業展開＃９ 並べ替えと一筆書きのアルゴリズム

勝ち抜き戦のアルゴリズム お立ち台方式 ① 全員を一列に並べる。 ② お立ち台を用意して、1番目の人を立たせる。 ①　全員を一列に並べる。 ②　お立ち台を用意して、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 a b c d g f e d e f g

オイラー閉路を求めるアルゴリズム ある連結な離散グラフＧのすべての節点の次数が偶数であるとする。 　　ある連結な離散グラフＧのすべての節点の次数が偶数であるとする。 ①　Ｇに辺の重複のない１つの閉路Ｌを描く。（その閉路Ｌがすべての辺を含んでいれば、オイラー閉路完成）。 ②　ＧからＬを除いて得られる残りのグラフも、すべての節点が偶数であるから、残りのグラフも、閉路Ｌ上の節点からＬに含まれていない辺をつないで同じ節点に戻る閉路Ｌ’が必ず構成できる。ＬとＬ’からなる図形は、一つの閉路と見なせ、それを新たに離散グラフＧの閉路Ｌとする。 ③　②の手順をすべての辺がＬに含まれるまで続ければ、得られた閉路Ｌはオイラー閉路である。

アルゴリズムの検証 オイラー閉路！

オイラー閉路演習 奇数次数 オイラー閉路である 一筆書き可能 オイラー閉路でない 一筆書き可能