ここの内容に関しての質問を歓迎します。斎藤末広まで。
©
斎藤末広（ジャン） 引用・複製を許可します。
ハッシュ表探索とは、データ（レコード）のキーを元に関数を使用して、ファイル上のレコードの場所を探索するテクニックである。この関数は、ハッシュ関数といい、わり算の余りなどを使用する。ハッシュ関数の問題は、頻出である。今回もいい問題である。
ハッシュ関数を使用した探索のメリットの一つに、データ量が増えても探索にかかる時間が増えないことである。これは、計算によってしまう場所が決定するからである。データ量とは関係がない。よって、解答は、エである。
ア データ量が増えると探索時間が極端に増えるのは、？？？？
イ データ量と探索時間が正比例の関係は、順次探索。頭から順に調べていく方法であろう。
ウ データ量が増えても探索時間があまり増えないのは、２分探索であろう。
いい問題である。データ圧縮方法の一つのハフマン圧縮の話である。ハフマン圧縮は頻出である。説明に従ってビットの数を数えれば解くことができる。代入して調べるときは、ウ、イ、ア、エの順である。
このような図を状態遷移図という。状態遷移図は頻出である。
ある日の天気が雨、２日後の天気が晴れになるのは、次の通りである。
雨 雨 晴れ 0.2*0.3=0.06
雨 晴れ 晴れ 0.3*0.4=0.12
雨 曇り 晴れ 0.5*0.3=0.15
よって、解答は、0.06 + 0.12 + 0.15 = 0.33 で エである。
シフト演算を利用して乗算をするフローチャートである。いい問題である。フローチャートの問題は、難しそうに見えてもたいていは簡単である。コツは、読みとる前にどれだけ、予想できるかである。だだし、フローチャートの問題は、時間がかかるときもあるので、後回しにする。
ざっとみると、X に Y をかけて、Ｚに入れるという流れである。さらに、解答群から、Ｙの最上位もしくは最下位のビットが重要な要素であること、さらに、Ｘ、Ｙを同時にどちらかにシフトするのも重要な要素であることが分かる。さらに、シフトしながら、順に足し込んで求めるので、小さい数から足し込まれるのが想像できる。
１倍のときは、Ｙの最下位ビットに１が立っていることを利用するはずので、Ｙの最下位ビットを利用するということで、アかイが解答。だんだんＸを大きくしていくので、Ｘを左シフトするアということが分かる。
一応答えがでたところで、流れ図を確認する。
(排他的論理和の記号を変更した書いてあります）
ハミング符号とは、情報ビットに冗長ビットを付加して、１ビットの誤りを訂正できるようにしたものである。ここで、情報ビットＸ1,Ｘ2,Ｘ3,Ｘ4の４ビットに、冗長ビットとしてＰ3,Ｐ2,Ｐ1の３ビットを付加したハミング符号Ｘ1Ｘ2Ｘ3Ｐ3Ｘ4Ｐ2Ｐ1を生成する。
なお、付加ビットＰ1,Ｐ2,Ｐ3の３ビットはそれぞれ
Ｘ1 eor Ｘ3 eor Ｘ4 eor Ｐ1 ＝ ０
Ｘ1 eor Ｘ2 eor Ｘ4 eor Ｐ2 ＝ ０
Ｘ1 eor Ｘ2 eor Ｘ3 eor Ｐ3 ＝ ０
となるように決める。(eor は排他的論理和を表す)
ハミング符号１１１００１１には１ビット誤りが存在する。誤りビットを訂正し
た正しいハミング符号はどれか。
ア ０１１００１１
イ １０１００１１
ウ
１１０００１１
エ １１１０１１１
アメリカの計算機科学者のハミング氏は、このハミング符号の成果らによって、1968年にチューリング賞を受賞している。このハミング符号によって、その後のエラー訂正(ECC)の学問分野が成立した。
ハミング符号の問題は、頻出である。またこの問題は、ハミング符号の原理を試させ、いい問題になっている。ただし、この問題は時間がかかるので、後回しにすべきである。
この問題の場合、ハミング符号の論理をどこまでしっているかで解くスピードが違ってくる。情報ビットＸとパリティビットＰから、
３つの計算式は、排他的論理和で定義されているが、実はこれは、右辺は、左の偶数パリティである。右辺の上から、順位に１、２、４をかけて足すと、間違ったビットの位置になる。よって、この場合は、７ビット目が間違いで、答えはアとなる。
もし、ハミング符号の訂正の方法を知らない場合は、問題に従って一つ一つ確認する必要がある。
（確認省略）
解答 ア
MOS型ICとバイポーラ型ICの比較に置いて、
MOS型は、スピードは遅いが、集積度が高くできるのが特色である。
ウの静電気への耐性、エの雑音の影響に関しては、調査中。
頻出問題。マイクロプログラム制御方式というのは、高級言語風に複雑になった機械語をＣＰＵの中で、簡単な機械語に置き換える方式である。その置き換えに使用するプログラムのことをマイクロプログラムという。CISCの基本テクニックである。
他のＣＰＵで動く機械語をまるごとＣＰＵで受け取りその中で単純な機械語に変換することで、エミュレーションが実現できる。マイクロプログラム方式は、エミュレイーションに適している。
機械命令を配線論理で実行するのは、単純な命令であるということである。RISCのテクニックである。
頻出問題。パイプライン処理の定義である。
ア、イ、エはそれぞれ、XXXXという。
キャシュメモリは頻出である。アの説明は、キャシュ仕方の、ライトスルー方式と、ライトバック方式をいっている。
イ ミスヒットのときを「割り込み」？
ウ 仮想記憶と両立している
エ CPUの速度が向上しているので、ますますキャシュメモリの需要が高まっている。パソコンもたいてい装備されている
メモリインターリーブとは、主記憶をバンクという単位に分け、連続のアドレスをバック内で連続させないで、バンクをまたがって順にふる。連続アクセスのときに、一つのバンクから取り出している間に次のアドレスが次のバンクから取り出す準備にかかれる。
ア 仮想記憶は、主記憶の狭さを解消する目的
イ ＣＰＵ内での命令の処理をオーバーラップさせて効率アップ
ウ 複数のプログラムを同時に実行して、ＣＰＵの遊び時間を減らし、スループットの向上を目的
よって、イが解答となる。