丸め誤差、打切り誤差、桁落ち、情報落ちの違い

桁落ち 例えば、以下のような場合を考えてみましょう。 0.6582×105−0.6581×105=0.0001×105=0.1×102 有効数字4桁の数同士の引き算を行った結果、有効数字2桁の数字に変化しました。

TPS

TPS(transaction Per Second)・・・1秒間に処理できるトランザクション量を示す。
トランザクションとは一連の単位を失敗か成功をひとまとめにできる処理を単位にします。Web系であれば1リクエストを1トランザクションとして言うことも多々あります。

【平成22年・秋】

Q.

商品検索と発注入力を行うWebシステムについて、時間帯別のトランザクション数を表1に、TPS(Transaction Per Second)と必要なCPU数の関係を表2に示す。このWebシステムに必要なCPU数は最低幾つか。ここでOSのオーバーへっど　などの処理については虫でき、トランザクションは、それぞれの時間帯の中で均等に発生するものとする。

	9:00～10:00	11:00～12:00	13:00～14:00
商品検索	12,000	48,000	24,000
発注入力	6,000	24,000	12,000

TPS	～10	～20	～30
必要なCPU数	1	2	3

A.

一番トランザクション数が多い場所に着目。11:00～12:00に48,000+24,000 = 72,000トランザクション。
1秒あたりだと 72,000÷3600 = 20。
20までならぎりぎりCPU2個で大丈夫。

標本化と量子化

音声信号のようなアナログ信号をメモリに保存できるようなディジタルデータに変換するためには、以下を行います。

・時系列にデータを抽出する標本化

・離散量に変換する量子化

標本化から量子化をのプロセスを行うのがA/D(アナログ/ディジタル)変換器。

D/A変換器はその逆でディジタル信号からアナログ信号のような連続量に変換を行う。

【平成22年・秋】

Q.

マイクロホンから入力された音声信号をメモリに記録する機能と、メモリに記録された音声データをスピーカから出力する機能とをもつディジタル録音・再生システムに関する記述のうち、適切なものはどれか。

ア・・・A/D変換器の出力及びD/A変換器の入力を、メモリのデータ線に接続する。

イ・・・音質はサンプリング周波数で決まり、量子化ビット数は関係しない。

ウ・・・録音時にはD/A変換、再生時にはA/D変換を行う。

エ・・・録音と再生とを同時に行わないならば、1個のA/D変換器だけで録音もできる。

A.

ア・・正解。

イ・・音質を向上させるには、両方大事。サンプリング周波数は時系列により微細化したデータが得られます。別名は標本化周波数。量子化ビット数

ウ・・逆

エ・・A/D変換器、D/A変換器は別もの。

DMAコントローラ

DMA(Direct Memory Access)は、CPUを介さずにメモリ間のデータ転送や、メモリと入出力装置とのデータ伝送を行う手法です。CPUに比べれば、低速な入出力装置によってCPUの待ち時間が発生しないように、DMAコントローラを用いてデータバスやアドレスバスを直接制御します。ハードディスクなどの補助ディスク装置やネットワークインターフェースなど制御に用いるとCPUを効率よく利用することができます。

【平成22年・秋】

Q.

DMAコントローラの説明として適切なものはどれか。

ア・・・MPUでは時間がかかる積和演算を、高速に行う。

イ・・・仮想メモリ機能、メモリ保護機能などのメモリ管理機能を提供する。

ウ・・・動作クロックに合わせてカウントするカウントレジスタをもち、それによって時間の経過を保持する。

エ・・・メモリと入出力装置との間、又はメモリとメモリとの間でのデータ交換を、MPUを介さずに行う。

A.

ア・・・・DSP(Digital Singal Processor)の説明。ディジタル信号処理に必要となる積和演算を高速に行うために専用の積和演算器をもち、これを並列動作させることでディジタル信号のリアルタイム処理を可能にします。

イ・・・・MMU(Memory Management Unit)の説明。CPUの要求するメモリアクセスを処理し、仮想メモリ管理機能、メモリ保護機能、複数のメモリバンクの切り替え機能、複数のメモリバンクの切り替え機能、バスの調停管理機能などを提供します。

ウ・・・・TSC(Time Stamp Counter)の説明。TSCはDPUの動作クロックごとに加算されるレジスタ。これを用いることできわめて高い精度のタイマを実現することができる。

エ・・・・正しい。

CPUが情報を取得する平均アクセス時間

CPUのキャッシュメモリ、主記憶に対する平均アクセス時間を求める問題です。

キャッシュメモリとはCPUと主記憶の性能差を埋めるために用いる高速小容量メモリのことです。
データはどちらかに入っています。

CPUが情報を取得する平均アクセス時間は以下となります。
(キャッシュメモリへのアクセス速度)×(データがキャッシュメモリに存在する確率) + (主記憶へのアクセス速度) × (データが主記憶に存在する確率)

ちなみに以下の式も成立します。
(データがキャッシュメモリに存在する確率)  + (データが主記憶に存在する確率) = 1

【平成22年・秋】

Q.

容量がaMバイトでアクセス時間がxナノ秒のキャッシュメモリと、容量がbMバイトでアクセス時間がyナノ秒の主記憶をもつシステムにおいて、CPUからみた、主記憶とキャッシュメモリとを合わせた平均アクセス時間を表す式はどうなるか？。ここで読み込みたいデータがキャッシュメモリに存在しない確率をrとし、キャッシュメモリ管理に関するオーバーヘッドを無視できるものとする。

A.

 (1-r)・x　+  r・y

パイプライン、スーパースカラ

パイプライン・・・命令を、取り込みや実行、結果の保存など複数のステップに細分化し、CPU内の資源を共有しないそれぞれを並列して同時に実行できるようにすることで、CPUの高速化を行う。
スーパーパイプライン・・・パイプラインの命令の実行ステップをさらに細分化、より深い多重化を行うよう改良されたパイプライン。
スーパースカラ・・・複数のパイプラインを用いて、複数の命令を同時に実行できるようにすうる手法。スーパースカラを実現するためには、CPU内に命令実行ユニットなどの機能ユニットを複数用意する必要があります。


【平成22年・秋】

Q.

スーパースカラの説明はどれか。
ア・・・処理すべきベクトルの長さがベクトルレジスタより長い場合、ベクトルレジスタ長の組に分割して処理を繰り返す方式。
イ・・・パイプラインを更に細分化することによって、高速化を図る方式である。
ウ・・・複数のパイプラインを用い、同時に複数の命令を実行可能にすることによって、高速化を図る方式である。
エ・・・命令語を長く取り、一つの命令で複数の機能ユニットを同時に制御することによって、高速化を図る方式。

A.
ア・・・ベクトル演算に関する手法
イ・・・スーパーパイプライン
ウ・・・正解
エ・・・VLIWに関する説明。

Ｈｚ（Hertz）、クロック、ＭＩＰＳ

Hz・・・1秒間あたりの振動数のこと。1Hzは、1秒間に1クロック。Hzが大きいほど高速に動作します。
クロック・・・コンピュータ内の動作のタイミングを取るために、規則正しく出される信号のことをいいます。
MIPS・・・（Million Instructions Per Second）つまり１秒あたりの命令数を百万単位で表したものです。

【平成22年・秋】

Q.

動作クロック周波数が700MHzのCPUで、命令の実行に必要なクロック数及び、その命令の出現率が表に示す値である場合、このCPUの性能は約何MIPSか？

命令の種別	命令実行に必要なクロック数	出現率(%)
レジスタ間の演算	4	30
メモリ・レジスタ間演算	8	60
無条件分岐	10	10

A.
命令実行に必要な平均クロック数
3×0.3 + 8×0.6+10×0.1 = 7クロック

700Mhz = 1秒あたり700 × 10⁶クロック

700 × 10⁶/7 = １秒あたり 100 × 10⁶命令実行できる。

答え：100MIPS

再使用可能（リユーザブル）プログラム

・再使用可能（リユーザブル）とは・・・
補助記憶装置から主記憶にロードし直さずに、再び実行できるプログラムのことを指します。
複数のプログラムから同時に呼び出しが可能なプログラムは、再入可能（リエントラント）プログラムと呼びます。不可能な場合は逐次再使用可能（シリアルユーザブル）と呼びます。

【平成22年・秋】

Q.

再入可能（リエントラント）プログラムにかんする記述のうち、適切なものはどれか。
ア・・・再入可能プログラムは、逐次再使用可能プログラムから呼び出すことはできない。
イ・・・再入可能プログラムは、呼び出し元ごとに確保された記憶領域に局所変数が割り当てられる。
ウ・・・実行途中で待ち状態が発生するプログラムは、再入可能プログラムではない。
エ・・・逐次再使用可能なプログラムは、再入可能プログラムでもある。

 A.

ア・・・呼び出せる。逆に再入可能プログラムから逐次再使用可能プログラムを呼び出すと問題になる。
イ・・・○
ウ・・・待ち状態が発生するか否かはプログラム分類とは関係ない。
エ・・・逐次再使用可能は、１つのプログラムのみしか実行中にできない。

探索

2分探索・・・前提として、データが昇順 or 降順であること。中央にあるデータを比較、順序よく並んでいるのであれば、中央からどちら側にデータがあるかわかる。その片方のさらに中央にあるデータを比較。これを繰り返すことで目的のデータを見つけることができる。
線形探索・・・・先頭のデータから順に探索していく。
ハッシュ表探索・・・・キー値からデータの格納場所をハッシュ関数によってハッシュ値として求め、直接的に探索。

【平成22年・秋】

Q.

探索の平均計算量が最も小さい探索手法の組み合わせはどれか。

a.コード順に格納した探索表
b.コードの使用頻度順に格納した探索表
c.コードから一意に決まる場所に格納した探索表

ア・・・２分探索
イ・・・線形探索
ウ・・・ハッシュ表探索

A.

a.ア
b.イ
c.ウ

線形リスト

【平成22年・秋】

Q.

先頭ポインタと末尾ポインタをもち、多くのデータがポインタでつながった単方向の線形リストの処理のうち、先頭ポインタ、末尾ポインタまたは各データのポインタをたどる階数が最も多いのはどれか。ここで、単方向のリストは先頭ポインタからつながっているものとし、追加するデータはポインタをたどらなくても参照できるものとする。

ア・・・先頭にデータを追加する処理
イ・・・先頭のデータを削除する処理
ウ・・・末尾にデータを追加する処理
エ・・・末尾のデータを削除する処理

A.

 

上記の図を例に説明すると以下となります。

ア・・・

 1.先頭ポインタからアドレス１０を参照

 2.先頭ポインタを追加するデータのアドレスに更新
 3.追加するデータのアドレス部を"アドレス10"に更新

 １回

イ・・・

 1.先頭ポインタからアドレス10を参照

 2.アドレス１０からアドレス１１を参照

 3.先頭ポインタのアドレスを"11"に更新

2回

ウ・・・（アドレス１４のデータを追加するとして）
 1.末尾ポインタからアドレス１３を参照
 2.アドレス１３のアドレスを"14"に更新
 3.末尾ポインタのアドレスを"14"に更新

1回

エ・・・

 1.末尾ポインタからアドレス13を参照 (アドレス13を取得)

 2.先頭ポインタからアドレス10を参照

 3.アドレス10からアドレス11を参照

 4.アドレス11からアドレス12を参照

 5.アドレス12のアドレス部を削除

 6.末尾ポインタをアドレス12に変更

データの数＋１（上記の場合、5回)

補足）
細かく書くと上記のような説明になるが、要は、
単方向の線形リストで先頭ポインタ、末尾ポインタがある場合、 一番参照回数が増えるのは２番目の末尾データです。データが増えるほど、たどる回数は増えていきます。
それがわかっていれば、わざわざカウントしなくても解ける問題です。

ロボット

ロボットは以下の機能で構成されています。
センサ・・・位置、圧力などの情報をとらえる。
制御システム・・・・動きを制御するための制御・判断を行う。
アクチュエータ・・・・機械・機構を物理的に動かす。
エネルギー供給システム・・・・駆動するエネルギーを供給する。

 

【平成22年・秋】

Q.

ロボットなどの制御システムを構成する構成するアクチュエーターの機能として、適切なものはどれか。

ア・・・動きを計測する。
イ・・・動きを制御するための計算・判断を行う。
ウ・・・機械・機構を物理的に動かす。
エ・・・制御システムを駆動するエネルギーを供給する。

A.

ア・・・センサ
イ・・・制御システム
ウ・・・アクチュエータ
エ・・・エネルギー供給システム

サンプリング間隔

サンプリング間隔とは、１つのサンプリング化されたデータを転送するまでにかかる時間のことです。

【平成22年・秋】

Q.
PCM伝送方式によって音声をサンプリング(標本化)して8ビットのディジタルデータに変換し、圧縮処理をしないで転送したところ、転送速度は64,000ビット/秒であった。このときサンプリング間隔は何マイクロ秒か。

A.

PCM伝送方式は、アナログデータからディジタルデータへの変換(AD変換)の一種で、この問題を解く上では知らなくても問題ありません。
１ビットを送信する時間は、1/64,000秒。
１つサンプリングしたデータを送信するのに必要な時間は、8/64,000秒=125マイクロ秒となります。

符号化

符号化とは簡単に言うとデータを別の形式に変換することです。
例えば、ビット列というのは、"0"と"1"で構成されています。
aを00
bを01
cを10
dを11
と符号化したとします。
"11011000"というデータを受け取った場合、2ビットずつ読み取って、"dbca"と解釈することができます。
『aは00ではなく、0。bは01ではなく、1じゃダメなのか？』
上記の方式の場合ダメですね。
例えば、10という情報があった場合、"c"なのか"ba"なのかわからなくなってしまいます。
符号化する場合、こういったことも考えてつくらないとダメです。

【平成22年・秋】

Q.

a,b,c,dの4文字からなるメッセージを符号化してビット列にする方法として表のア～エを考えた。この表はa,b,c,dの出現頻度は、それぞれ50%、30%、10%、10%であることが分かっている。符号化されたビット列から元のメッセージが一意に複合可能であって、ビット列の長さが最も短くなるものはどれか？

	a	b	c	d
ア	0	1	00	11
イ	0	01	10	11
ウ	0	10	110	111
エ	00	01	10	11

A.
・まず復元可能な符号化かどうかを検証する。
ア・・・符号化に問題がある。例えば、"00"というデータの場合、"aa"か"c"かわからない。
イ・・・符号化に問題がある。例えば、""01010"の場合、"bba"か"acc"かわからない。
ウ・・・復元可能
エ・・・復元可能

・ビット列の長さが短くなるものはどれか？
１文字取得した場合、平均ビットを求める。
ウ・・・(1×0.5) + (2×0.3) + (3 × 0.1) + (3×0.1) = 1.7ビット
エ・・・(2×0.5) + (2×0.3) + (2 × 0.1) + (2×0.1) = 2ビット

答えは、ウとなる。

逆ポーランド記法 (後置記法)

逆ポーランド記法は、コンピュータで処理するのに都合のいい形の、数式の書き方です。
・サンプル
  YAB+CDE/-*=

【プログラムを組むのがとても簡単。】
・先頭からひとつずつ順番に文字を読み込む。
・数字であれば、スタックに値を積む。
・演算子であればスタックから値を取り出して演算し結果をスタックに積む。
という簡単なプログラムで計算結果を求めることができます。
一方、人からするとわかりにくいですね。
まぁPCにやさしい計算書式なんです。

【平成22年・秋】
Q:以下の式を後置表記法で表現してみる。
Y=(A+B)*(C-(D/E))

A:内部から後置表記法にしていけばよい
Y=(A+B)*(C-(D/E))
↓
Y=(AB+)*(C-(DE/))
↓
Y=(AB+)*(CDE/-))
↓
Y=AB+CDE/-*
↓
YAB+CDE/-*=