創造情報学専攻入試メモ

(a)
m = 1のとき、C = 1, C_max = 1 は明らか

m = 2のとき、
v = p₂ ならば比較は1回
そうでなければ比較は2回
よって、
C = (1 + 2 * 3) / 2² = 7/4
C_max = 2

m = 3のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が2²通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * (2² + 1)) / 2³ = 5/2
C_max = 3

m = 4のとき、
比較が1回の場合が1通り
比較が2回の場合が2通り
比較が3回の場合が2²通り
比較が4回の場合が2³通り + 探索が失敗する場合
よって、
C = (1 + 2 * 2 + 3 * 2² + 4 * (2³ + 1)) / 2⁴ = 53/16
C_max = 4


(b)
比較回数iで探索が成功する場合が2^i-1通り存在し、また探索が失敗する場合の比較回数はm回なので、
C = ( Σ_{k∈[1, m]} ( k * 2^k-1 ) + m ) / 2^m

ここで、S = Σ_{k∈[1, m]} ( k * 2^k-1 ) とすると、
S = 1 * 1 + 2 * 2 + 3 * 2² + ・・・ + m * 2^m-1
2S =           1 * 2 + 2 * 2² + ・・・ + (m-1) * 2^m-1 + m * 2^m

よって、
-S = 1 + 2 + 2² + ・・・ + 2^m-1 - m * 2^m
S = (m - 1) * 2^m + 1

以上より、
C = ((m - 1) * 2^m + 1 + m) / 2^m
　= m - 1 + (m + 1) / 2^m
C_max = m

(a)
v = k_j のとき比較回数は j回
探索失敗の場合、比較回数は n回

よって、
C = Σ_j∈[1,n] ( j / 2n ) + n / 2 = (3n + 1) / 4
C_max = n

(b)
C = Σ_j∈[1,n] ( j / 2^j ) + n / 2ⁿ

まず、C = 1 + Σ_j∈[1,n-1] (1 / 2ⁿ) を示す。

n = 1のとき、C = 1

Σ_j∈[1,k] ( j / 2^j ) + k / 2^k = 1 + Σ_j∈[1,k-1] (1 / 2^k) とすると、
Σ_j∈[1,k+1] ( j / 2^j ) + (k + 1) / 2^k+1
= Σ_j∈[1,k] ( j / 2^j ) + (k + 1) / 2^k
= 1 + Σ_j∈[1,k-1] (1 / 2^k) + 1 / 2^k
= 1 + Σ_j∈[1,k] (1 / 2^k)

よって、数学的帰納法より、
C = 1 + Σ_j∈[1,n-1] (1 / 2ⁿ)

Σ_j∈[1,n-1] (1 / 2ⁿ) < 1 なので、C < 2

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

Unicodeとは、世界中で用いられるすべての文字を共通の方法で符号化して扱うための標準規格である。
はじめは16ビットで全ての文字を表現することを目指していたが、現在では32ビットで定義されている。

マルチプロセッサにおいてキャッシュの一貫性を保つために、各々のキャッシュが自身及び他のキャッシュの状態を把握しておき、最新のデータがどのキャッシュに存在するかを知ることで、必要なときに最新データを取得できるようにする手法。
複数のプロセッサが主記憶メモリを共有していて、メモリアクセスが全て同一のバスを通るような場合に有効なシステムであり、共通のバスを持たない分散メモリシステムでは用いることが困難である。