2008-8 第2問 (3)
(2)で求めた回路を次のように変更する。
このカウンタを利用して、以下のように回路を構成する。
このカウンタを利用して、以下のように回路を構成する。
スポンサーサイト
2008-8 第1問 (4)
逐次探索はプログラムが非常に単純で実装が容易だが、エントリ数が多いと実行速度が遅くなってしまう。
2分探索はO(logN)で動作するため、エントリ数が増えても高速に動作するが、事前にデータをソートしておく必要がある。
ハッシュ表はエントリ数が増えても定数時間で探索が可能であり、2分探索よりも更に高速だが、メモリの使用量が非常に大きいという問題がある。
2分探索はO(logN)で動作するため、エントリ数が増えても高速に動作するが、事前にデータをソートしておく必要がある。
ハッシュ表はエントリ数が増えても定数時間で探索が可能であり、2分探索よりも更に高速だが、メモリの使用量が非常に大きいという問題がある。
2008-8 第1問 (3)
(a) 衝突回避はチェイン法による
0 : (k3, r3)
1 : (k2, r2)
2
3
4 : (k5, r5), (k6, r6)
5 : (k7, r7), (k8, r8)
6
7
8
9
10 : (k1, r1)
11
12 : (k4, r4)
13
14
15
16
(b)
v = k1, k2, k3, k4, k5, k7 のとき、比較回数は1回
v = k6, k8 のとき、比較回数は2回
よって、
C = (1 * 6 + 2 * 2) / 8 = 5 / 4
Cmax = 2
0 : (k3, r3)
1 : (k2, r2)
2
3
4 : (k5, r5), (k6, r6)
5 : (k7, r7), (k8, r8)
6
7
8
9
10 : (k1, r1)
11
12 : (k4, r4)
13
14
15
16
(b)
v = k1, k2, k3, k4, k5, k7 のとき、比較回数は1回
v = k6, k8 のとき、比較回数は2回
よって、
C = (1 * 6 + 2 * 2) / 8 = 5 / 4
Cmax = 2
2008-8 第1問 (2)
(a)
m = 1のとき、C = 1, Cmax = 1 は明らか
m = 2のとき、
v = p2 ならば比較は1回
そうでなければ比較は2回
よって、
C = (1 + 2 * 3) / 22 = 7/4
Cmax = 2
m = 3のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が22通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * (22 + 1)) / 23 = 5/2
Cmax = 3
m = 4のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が22通り
比較が4回の場合が23通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * 22 + 4 * (23 + 1)) / 24 = 53/16
Cmax = 4
(b)
比較回数iで探索が成功する場合が2i-1通り存在し、また探索が失敗する場合の比較回数はm回なので、
C = ( Σk∈[1, m] ( k * 2k-1 ) + m ) / 2m
ここで、S = Σk∈[1, m] ( k * 2k-1 ) とすると、
S = 1 * 1 + 2 * 2 + 3 * 22 + ・・・ + m * 2m-1
2S = 1 * 2 + 2 * 22 + ・・・ + (m-1) * 2m-1 + m * 2m
よって、
-S = 1 + 2 + 22 + ・・・ + 2m-1 - m * 2m
S = (m - 1) * 2m + 1
以上より、
C = ((m - 1) * 2m + 1 + m) / 2m
= m - 1 + (m + 1) / 2m
Cmax = m
m = 1のとき、C = 1, Cmax = 1 は明らか
m = 2のとき、
v = p2 ならば比較は1回
そうでなければ比較は2回
よって、
C = (1 + 2 * 3) / 22 = 7/4
Cmax = 2
m = 3のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が22通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * (22 + 1)) / 23 = 5/2
Cmax = 3
m = 4のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が22通り
比較が4回の場合が23通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * 22 + 4 * (23 + 1)) / 24 = 53/16
Cmax = 4
(b)
比較回数iで探索が成功する場合が2i-1通り存在し、また探索が失敗する場合の比較回数はm回なので、
C = ( Σk∈[1, m] ( k * 2k-1 ) + m ) / 2m
ここで、S = Σk∈[1, m] ( k * 2k-1 ) とすると、
S = 1 * 1 + 2 * 2 + 3 * 22 + ・・・ + m * 2m-1
2S = 1 * 2 + 2 * 22 + ・・・ + (m-1) * 2m-1 + m * 2m
よって、
-S = 1 + 2 + 22 + ・・・ + 2m-1 - m * 2m
S = (m - 1) * 2m + 1
以上より、
C = ((m - 1) * 2m + 1 + m) / 2m
= m - 1 + (m + 1) / 2m
Cmax = m
2008-8 第1問 (1)
(a)
v = kj のとき比較回数は j回
探索失敗の場合、比較回数は n回
よって、
C = Σj∈[1,n] ( j / 2n ) + n / 2 = (3n + 1) / 4
Cmax = n
(b)
C = Σj∈[1,n] ( j / 2j ) + n / 2n
まず、C = 1 + Σj∈[1,n-1] (1 / 2n) を示す。
n = 1のとき、C = 1
Σj∈[1,k] ( j / 2j ) + k / 2k = 1 + Σj∈[1,k-1] (1 / 2k) とすると、
Σj∈[1,k+1] ( j / 2j ) + (k + 1) / 2k+1
= Σj∈[1,k] ( j / 2j ) + (k + 1) / 2k
= 1 + Σj∈[1,k-1] (1 / 2k) + 1 / 2k
= 1 + Σj∈[1,k] (1 / 2k)
よって、数学的帰納法より、
C = 1 + Σj∈[1,n-1] (1 / 2n)
Σj∈[1,n-1] (1 / 2n) < 1 なので、C < 2
v = kj のとき比較回数は j回
探索失敗の場合、比較回数は n回
よって、
C = Σj∈[1,n] ( j / 2n ) + n / 2 = (3n + 1) / 4
Cmax = n
(b)
C = Σj∈[1,n] ( j / 2j ) + n / 2n
まず、C = 1 + Σj∈[1,n-1] (1 / 2n) を示す。
n = 1のとき、C = 1
Σj∈[1,k] ( j / 2j ) + k / 2k = 1 + Σj∈[1,k-1] (1 / 2k) とすると、
Σj∈[1,k+1] ( j / 2j ) + (k + 1) / 2k+1
= Σj∈[1,k] ( j / 2j ) + (k + 1) / 2k
= 1 + Σj∈[1,k-1] (1 / 2k) + 1 / 2k
= 1 + Σj∈[1,k] (1 / 2k)
よって、数学的帰納法より、
C = 1 + Σj∈[1,n-1] (1 / 2n)
Σj∈[1,n-1] (1 / 2n) < 1 なので、C < 2
2010-8 第4問 (6)
行列 A に対し、A の随伴行列（複素共役かつ転置行列）を A* とするとき、以下の条件を満足する行列 A+ はただ一つに定まる：
A+ は広義可逆元である：
> AA+A = A
> A+AA+ = A+
AA+ および A+A はエルミート行列である：
> (AA+)* = AA+
> (A+A)* = A+A
この行列 A+を A の擬似逆行列と呼ぶ。
A が正則でなくとも A+は定まるが、A が正則ならば逆行列 A-1はこの条件を満たす。
ゆえに擬似逆行列の概念は逆行列の概念の一般化を与えており、一般化逆行列とも呼ばれる。
A+ は広義可逆元である：
> AA+A = A
> A+AA+ = A+
AA+ および A+A はエルミート行列である：
> (AA+)* = AA+
> (A+A)* = A+A
この行列 A+を A の擬似逆行列と呼ぶ。
A が正則でなくとも A+は定まるが、A が正則ならば逆行列 A-1はこの条件を満たす。
ゆえに擬似逆行列の概念は逆行列の概念の一般化を与えており、一般化逆行列とも呼ばれる。
2009-8 第4問 (7)
Unicodeとは、世界中で用いられるすべての文字を共通の方法で符号化して扱うための標準規格である。
はじめは16ビットで全ての文字を表現することを目指していたが、現在では32ビットで定義されている。
はじめは16ビットで全ての文字を表現することを目指していたが、現在では32ビットで定義されている。
2009-8 第4問 (6)
マルチプロセッサにおいてキャッシュの一貫性を保つために、各々のキャッシュが自身及び他のキャッシュの状態を把握しておき、最新のデータがどのキャッシュに存在するかを知ることで、必要なときに最新データを取得できるようにする手法。
複数のプロセッサが主記憶メモリを共有していて、メモリアクセスが全て同一のバスを通るような場合に有効なシステムであり、共通のバスを持たない分散メモリシステムでは用いることが困難である。
複数のプロセッサが主記憶メモリを共有していて、メモリアクセスが全て同一のバスを通るような場合に有効なシステムであり、共通のバスを持たない分散メモリシステムでは用いることが困難である。
2009-8 第4問 (5)
チューリングマシンは無限に長いテープとそのテープを読み書きするヘッド、及び内部状態を保持するためのメモリからなる。チューリングマシンはその内部状態に従ってヘッドを動かし、テープから情報を読んで状態を変更したり、テープに情報を書き込んだりする。
チューリングマシンの動作は非常に単純だが、チューリングマシンで解くことのできる問題のクラスは実際の計算機の解くことのできる問題のクラスと同一であり、計算機のモデルとしてよく利用される。
チューリングマシンの動作は非常に単純だが、チューリングマシンで解くことのできる問題のクラスは実際の計算機の解くことのできる問題のクラスと同一であり、計算機のモデルとしてよく利用される。
2009-8 第4問 (4)
関係データベースの正規化とは、関連するデータをグループ化したり、同一データを重複して持つことが無いようにテーブルを分割・整理したりすることにより、データベースを正規形と呼ばれる形式に統一することを言う。
正規化を行うことで、データの更新による矛盾の発生を防ぐことができ、データの一貫性が保たれる。
正規化されていないデータベースはしばしば非効率であり、データベースの活用の妨げとなる。
正規化のうち特によく知られているのが第1〜第5正規形とボイス・コッド正規形であり、特に第3正規形までのものは実務でもよく用いられている。
正規化を行うことで、データの更新による矛盾の発生を防ぐことができ、データの一貫性が保たれる。
正規化されていないデータベースはしばしば非効率であり、データベースの活用の妨げとなる。
正規化のうち特によく知られているのが第1〜第5正規形とボイス・コッド正規形であり、特に第3正規形までのものは実務でもよく用いられている。
2009-8 第4問 (3)
スペクトル拡散通信とは、デジタル信号を送信する際に冗長性を付加して本来必要とされる帯域より広い帯域に拡散させて通信を行う通信方式。受信側では送信側と同じ拡散符号を利用して元のデジタル信号を復元する。
冗長性が非常に高いためノイズの影響を受けにくく、妨害や干渉に非常に強い。また、デジタル信号の復元には送信側と同じ拡散符号が必要なため、情報の秘匿性にも優れる。
冗長性が非常に高いためノイズの影響を受けにくく、妨害や干渉に非常に強い。また、デジタル信号の復元には送信側と同じ拡散符号が必要なため、情報の秘匿性にも優れる。
2009-8 第4問 (2)
決定木の学習では訓練データを何らかの指標に基づいて幾つかの集合に分割し、分割したそれぞれのデータを部分木とする木を作成する。それぞれの部分木に対しても再帰的に分割を行い、最終的な木構造を得る。
良い決定木を得るためには訓練データの分割の指標の定め方が問題となる。この指標の定め方には様々な種類があり、例えばID3やC4.5と呼ばれる手法では情報量(エントロピー)を基に指標を定める。
良い決定木を得るためには訓練データの分割の指標の定め方が問題となる。この指標の定め方には様々な種類があり、例えばID3やC4.5と呼ばれる手法では情報量(エントロピー)を基に指標を定める。
2009-8 第4問 (1)
事象Aの確率(事前確率)をP(A)とし、条件Aの下で事象Bが成立する確率(事後確率・条件付き確率)をP(B|A)とする。
このとき、P(B|A)はP(A), P(B), P(A|B)を用いて次のように記述できる。
P(B|A) = P(A|B) * P(B) / P(A)
ベイズの定理はベイズ統計学の基礎であり、迷惑メールのフィルタリングなど、様々な応用がなされている。
このとき、P(B|A)はP(A), P(B), P(A|B)を用いて次のように記述できる。
P(B|A) = P(A|B) * P(B) / P(A)
ベイズの定理はベイズ統計学の基礎であり、迷惑メールのフィルタリングなど、様々な応用がなされている。
2009-8 第3問 (5)
X = { xi }, Y = { yi }, Z = { zi }, Z = X + Y とすると、
z0 = x0 ∧ y0
z1 = x1 ∧ y0 ⊕ x0 ∧ y1
z2 = x2 ∧ y0 ⊕ x1 ∧ y1 ⊕ x0 ∧ y2 ⊕ x0 ∧ x1 ∧ y0 ∧ y1
...
のように、任意のiに対してziはx0,...,xi-1とy0,...,yi-1で表せる。
各論理積の計算は並列的に計算可能であり、それぞれの計算コストはO(logN)
排他的論理和の計算コストもO(logN)なので、全体の計算コストはO(logN)
z0 = x0 ∧ y0
z1 = x1 ∧ y0 ⊕ x0 ∧ y1
z2 = x2 ∧ y0 ⊕ x1 ∧ y1 ⊕ x0 ∧ y2 ⊕ x0 ∧ x1 ∧ y0 ∧ y1
...
のように、任意のiに対してziはx0,...,xi-1とy0,...,yi-1で表せる。
各論理積の計算は並列的に計算可能であり、それぞれの計算コストはO(logN)
排他的論理和の計算コストもO(logN)なので、全体の計算コストはO(logN)
2009-8 第3問 (1)
半加算器
全加算器
| X | Y | Z | C0 |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 |
全加算器
| X | Y | CI | Z | CO |
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
2009-8 第1問 (3)
Algorithm 1 の計算量はMain Loopの式より明らかに O(|E||V|) なので、
Algorithm 1-ALLの計算量はO(|E||V|2)
Algorithm 2 の計算量はMain Loopの式より明らかにO(|V|3) なので、
|E| < |V| のときは Algorithm 1-ALL が有利であり、
|E| > |V| のときは Algorithm 2 が有利である。
Algorithm 1-ALLの計算量はO(|E||V|2)
Algorithm 2 の計算量はMain Loopの式より明らかにO(|V|3) なので、
|E| < |V| のときは Algorithm 1-ALL が有利であり、
|E| > |V| のときは Algorithm 2 が有利である。
2009-8 第1問 (2)
D(0)
D(1) : w = v0
D(2) : w = v1
D(3) : w = v2
D(4) : w = v3
D(5) : w = v4
| v0 | v1 | v2 | v3 | v4 | |
| v0 | 0 | 1 | ∞ | 5 | 9 |
| v1 | ∞ | 0 | 1 | 3 | ∞ |
| v2 | ∞ | ∞ | 0 | -1 | ∞ |
| v3 | ∞ | 1 | ∞ | 0 | 1 |
| v4 | 1 | ∞ | ∞ | ∞ | 0 |
D(1) : w = v0
| v0 | v1 | v2 | v3 | v4 | |
| v0 | 0 | 1 | ∞ | 5 | 9 |
| v1 | ∞ | 0 | 1 | 3 | ∞ |
| v2 | ∞ | ∞ | 0 | -1 | ∞ |
| v3 | ∞ | 1 | ∞ | 0 | 1 |
| v4 | 1 | 2 | ∞ | 6 | 0 |
D(2) : w = v1
| v0 | v1 | v2 | v3 | v4 | |
| v0 | 0 | 1 | 2 | 4 | 9 |
| v1 | ∞ | 0 | 1 | 3 | ∞ |
| v2 | ∞ | ∞ | 0 | -1 | ∞ |
| v3 | ∞ | 1 | 2 | 0 | 1 |
| v4 | 1 | 2 | 3 | 5 | 0 |
D(3) : w = v2
| v0 | v1 | v2 | v3 | v4 | |
| v0 | 0 | 1 | 2 | 1 | 9 |
| v1 | ∞ | 0 | 1 | 0 | ∞ |
| v2 | ∞ | ∞ | 0 | -1 | ∞ |
| v3 | ∞ | 1 | 2 | 0 | 1 |
| v4 | 1 | 2 | 3 | 2 | 0 |
D(4) : w = v3
| v0 | v1 | v2 | v3 | v4 | |
| v0 | 0 | 1 | 2 | 1 | 2 |
| v1 | ∞ | 0 | 1 | 0 | 1 |
| v2 | ∞ | 0 | 0 | -1 | 0 |
| v3 | ∞ | 1 | 2 | 0 | 1 |
| v4 | 1 | 2 | 3 | 2 | 0 |
D(5) : w = v4
| v0 | v1 | v2 | v3 | v4 | |
| v0 | 0 | 1 | 2 | 1 | 2 |
| v1 | 2 | 0 | 1 | 0 | 1 |
| v2 | 1 | 0 | 0 | -1 | 0 |
| v3 | 2 | 1 | 2 | 0 | 1 |
| v4 | 1 | 2 | 3 | 2 | 0 |
2010-8 第2問 (1)
1)
2オペランド命令形式はa = a + bのような命令は1命令で表現できるが、a = b + cのような命令は1命令では表現することができない。
3オペランド命令形式ではa = b + cのような命令も1命令で表現できるが、オペランド数が多いことにより多くのビットを消費してしまうため、オペコードを短くするか命令長を長くする必要がある。
2)
算術命令等がメモリオペランドを持つ形式ではメモリアクセスを伴う処理を少ない数の命令で記述できるが、命令の実行速度が一定せず、効率が悪い。
ロード・ストア命令を算術命令等とは別に持つ形式では、算術命令等のオペランドにはレジスタしか指定できないが、命令セットが単純化され命令の実行時間等もほぼ一定となるため高速化しやすくなる。
2オペランド命令形式はa = a + bのような命令は1命令で表現できるが、a = b + cのような命令は1命令では表現することができない。
3オペランド命令形式ではa = b + cのような命令も1命令で表現できるが、オペランド数が多いことにより多くのビットを消費してしまうため、オペコードを短くするか命令長を長くする必要がある。
2)
算術命令等がメモリオペランドを持つ形式ではメモリアクセスを伴う処理を少ない数の命令で記述できるが、命令の実行速度が一定せず、効率が悪い。
ロード・ストア命令を算術命令等とは別に持つ形式では、算術命令等のオペランドにはレジスタしか指定できないが、命令セットが単純化され命令の実行時間等もほぼ一定となるため高速化しやすくなる。
2010-8 第1問 (3)
全ての商品の価格の総和がqmin以下であるとき、ステップ4における集合S'は選択された要素を除いた後のSと等しいため、再帰呼び出しされるback手続き内でのback手続きの呼び出し回数は最大となる。
また、解が存在しないことからこのback手続きはSが空になるまで続けられる。
以上から、全ての商品の価格の総和がqmin以下であるときback手続きの呼び出し回数は最大となる。
このback手続きから直接呼び出されるi回目のback手続きの第二引数の要素数はl-iなので、
tl = 1 + Σi=0l-1ti
となる。
また、解が存在しないことからこのback手続きはSが空になるまで続けられる。
以上から、全ての商品の価格の総和がqmin以下であるときback手続きの呼び出し回数は最大となる。
このback手続きから直接呼び出されるi回目のback手続きの第二引数の要素数はl-iなので、
tl = 1 + Σi=0l-1ti
となる。
2010-8 第1問 (1) (2)
(1)
(ε, {G1, G2, G3, G4})
→ (<G4>, {G1, G2, G3})
→ (<G3, G4>, {G1, G2})
→ (<G1, G3, G4>, ε)
→ (<G2, G3, G4>, ε)
(2)
n = 3, p1 = 3, p2 = 3, p3 = 4, qmin = 5, qmax = 7 のとき、
(ε, {G1, G2, G3})
→ (<G3>, ε)
→ (<G2>, {G1})
→ (<G1, G2>, ε)
(ε, {G1, G2, G3, G4})
→ (<G4>, {G1, G2, G3})
→ (<G3, G4>, {G1, G2})
→ (<G1, G3, G4>, ε)
→ (<G2, G3, G4>, ε)
(2)
n = 3, p1 = 3, p2 = 3, p3 = 4, qmin = 5, qmax = 7 のとき、
(ε, {G1, G2, G3})
→ (<G3>, ε)
→ (<G2>, {G1})
→ (<G1, G2>, ε)
2011-8 第4問 (8)
クライアント・サーバーシステムは特定のサーバーのみで全てを管理することができるが、サーバに負担が集中するためクライアントの数が増えると処理が極端に重くなる欠点を持つ。
P2Pシステムではユーザ数が膨大になっても特定のコンピュータに処理が集中することはないため、非常にスケーラビリティが高いと言える。しかし、P2Pシステムは全てを管理するサーバを持たないため、特定のデータの削除などが不得意である。また、P2Pシステムはクライアント・サーバーシステムと比べて複雑になりやすく、実装が非常に難しい。
P2Pシステムではユーザ数が膨大になっても特定のコンピュータに処理が集中することはないため、非常にスケーラビリティが高いと言える。しかし、P2Pシステムは全てを管理するサーバを持たないため、特定のデータの削除などが不得意である。また、P2Pシステムはクライアント・サーバーシステムと比べて複雑になりやすく、実装が非常に難しい。
2011-8 第4問 (7)
マイクロプログラム制御方式とは、CPU内部の処理を小さな命令(マイクロプログラム)と考え、マイクロプログラムを組み合わせることで様々な命令を実現するプロセッサの制御方式。
比較的容易に命令の追加・変更が可能で、異なる命令セットのCPUのエミュレート等も可能である。
しかし、複雑な命令の増加によりパイプライン化が妨げられるなど、実行時間を増加させてしまう欠点がある。
比較的容易に命令の追加・変更が可能で、異なる命令セットのCPUのエミュレート等も可能である。
しかし、複雑な命令の増加によりパイプライン化が妨げられるなど、実行時間を増加させてしまう欠点がある。
2011-8 第4問 (6)
パイプラインハザードとは、命令同士の依存関係によりパイプライン化が無駄になる、もしくは不可能となる事を指す。例えば、ある命令が直前の命令の結果を利用する場合、直前の命令が完了するまでその命令は実行することができない。これをデータハザードと呼ぶ。また、分岐命令が存在するとき、その結果によって実行すべき命令が変わってしまうため、パイプラインを止めて分岐の結果が出るのを待つ必要がある。これを制御ハザード(または分岐ハザード)と言う。
