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はこの条件を満たす。
ゆえに擬似逆行列の概念は逆行列の概念の一般化を与えており、一般化逆行列とも呼ばれる。

2010-8 第2問 (1)

1)
2オペランド命令形式はa = a + bのような命令は1命令で表現できるが、a = b + cのような命令は1命令では表現することができない。
3オペランド命令形式ではa = b + cのような命令も1命令で表現できるが、オペランド数が多いことにより多くのビットを消費してしまうため、オペコードを短くするか命令長を長くする必要がある。

2)
算術命令等がメモリオペランドを持つ形式ではメモリアクセスを伴う処理を少ない数の命令で記述できるが、命令の実行速度が一定せず、効率が悪い。
ロード・ストア命令を算術命令等とは別に持つ形式では、算術命令等のオペランドにはレジスタしか指定できないが、命令セットが単純化され命令の実行時間等もほぼ一定となるため高速化しやすくなる。

2010-8 第1問 (4)

t_l+1 - t_l = t_l より、t_l+1 = 2t_l

また、t₀ = 1 は明らかなので、

t_l = 2^l

よって、2ⁿ回

2010-8 第1問 (3)

全ての商品の価格の総和がq_min以下であるとき、ステップ4における集合S'は選択された要素を除いた後のSと等しいため、再帰呼び出しされるback手続き内でのback手続きの呼び出し回数は最大となる。
また、解が存在しないことからこのback手続きはSが空になるまで続けられる。

以上から、全ての商品の価格の総和がq_min以下であるときback手続きの呼び出し回数は最大となる。

このback手続きから直接呼び出されるi回目のback手続きの第二引数の要素数はl-iなので、
t_l = 1 + Σ_i=0^l-1t_i
となる。

2010-8 第1問 (1) (2)

(1)
(ε, {G₁, G₂, G₃, G₄})
→ (<G₄>, {G1, G₂, G₃})
→ (<G₃, G₄>, {G₁, G₂})
→ (<G₁, G₃, G₄>, ε)
→ (<G₂, G₃, G₄>, ε)

(2)
n = 3, p₁ = 3, p₂ = 3, p₃ = 4, q_min = 5, q_max = 7 のとき、

(ε, {G₁, G₂, G₃})
→ (<G₃>, ε)
→ (<G₂>, {G₁})
→ (<G₁, G₂>, ε)