サンプル問題１n 次三重対角行列
2 −1
 −12 −1.
.. ...
An = 
−1..
.

2 −1 −12について，以下の設問 (1), (2), (3) に答えよ．

(1) An の行列式の値を求めよ．
(2) 方程式 An x = b に対するヤコビ (Jacobi) 法が収束することを証明せよ．
(3) 行列 An は，どのような工学的あるいは物理的な問題から生じるか，具体的な例を挙げて説明せよ．

注．一般の n 元連立 1 次方程式 Ax = b に対するヤコビ法は，適当な初期ベク
トル x(0) からスタートして，k = 1, 2, . . . に対して，漸化式
X1 (k−1)(k)aij xj+ bi 
(i = 1, . . . , n)−xi =aii
j6=iによって近似ベクトルの列 x(1) , x(2) , . . . を生成する反復法である．ここで，b =(k)(bi | i = 1, . . . , n), x(k) = (xi | i = 1, . . . , n) であり，行列 A = (aij | i, j =1, . . . , n) の対角成分 aii (i = 1, . . . , n) はどれも 0 でないと仮定する．

上のサンプル問題の出題意図を説明します．数理情報学専攻では，数学（論理・計算の世界）と応用分野（現実・現象の世界）の繋がりを重視しています．
例えば，行列については，線形代数学で論じられるような数学的な性質だけでなく，(a) 行列はどのように生じるか，(b) どのような行列が生じるか，(c) どのように計算するか，1

などの観点も大切であると考えています．
行列はいろいろな分野で登場しますが，「(a) 行列はどのように生じるか」を理解するためには，それぞれの分野の基本的な概念や手法を理解することが必要です．例えば，微分方程式の離散化，統計データの共分散，線形計画問題の記述，符号理論における検査行列，グラフ理論における接続行列などで行列が登場しますが，ここに現れた「離散化」，「共分散」，「線形計画」，「検査行列」，「接続行列」などの言葉は，行列がそれぞれの文脈でどのような意味と役割をもっているかを表しています．上の問 (3) では，行列が生まれる文脈がテーマです．
数学的に言えば，行列とは数を長方形に並べたものですが，応用分野で生じる行列は，それぞれ，特徴的な形（パターン）をもっています．上の例では三重対角の形です．行列の行列式の値を陽に求めることは一般にはできませんが，三重対角であることから det An に関する三項漸化式を導くことができ，これを解いて det An の値が求められます．ついでに，det An が 0 でないことから，Anが正則であることが分かります．上の問 (1) では，行列のパターンがテーマです．
応用分野で行列を使うとき，数値計算をする必要が生じます．上の問 (2) では，行列に関する数値計算法がテーマであり，数値線形計算アルゴリズムの振るまいを解析するための数学的技量を見ようとしています．反復法の収束性が反復行列の固有値で決まるという基本的事実の理解と，反復行列の固有値を計算・評価する力がポイントです．

2サンプル問題２ある棒の長さを測定する実験を行なう．測定には誤差がともなうため，n 回の測定をおこなって得られる値 X1 , X2 , . . . , Xn の標本平均

X̄ =1(X1 + X2 + · · · + Xn )n

を棒の長さ µ の推定量とする．以下の設問 (1), (2), (3) に答えよ．

(1) 測定の誤差 εi (i = 1, . . . , n) が独立に平均 0，分散 1 の正規分布にしたがうものとする．棒の長さの各測定値 Xi = µ + εi (i = 1, . . . , n) のもつFisher 情報量 (注１) を求めよ．X̄ が µ の不偏推定量であり，Cramér-Rao1の不等式 (注２) の与える不偏推定量の分散の下限 nI(µ)
を達成することを示せ．
(2) 測定の誤差 εi (i = 1, . . . , n) が，正規分布とは限らない平均 0 で有限の分散をもつある確率分布に独立にしたがうものとする．誤差の分布はなめらかな確率密度関数 g(x) をもち，任意の x ∈ R で g(x) > 0 であるとする．
棒の長さの各測定値 Xi = µ + εi (i = 1, . . . , n) のもつ Fisher 情報量がI(µ) =¾Z ∞½ 0g (x) 2g(x) dx−∞ g(x)で与えられること，またZ ∞xg 0 (x)dx = −1−∞となることを示せ．ただし，I(µ) は有限値であるとする．

(3) (2) で，X̄ は µ の不偏推定量である．X̄ が Cramér-Rao の不等式の与える不偏推定量の分散の下限を達成するのは，誤差の分布が平均 0 の正規分布の場合に限ることを示せ．

注１．１つの確率変数 X が，未知パラメータ µ を含む確率密度関数 f (x; µ) をもつ確率分布にしたがうとき，

Z ∞½I(µ) =−∞¾2∂log f (x; µ) f (x; µ) dx∂µ3を，X のもつ Fisher 情報量と呼ぶ．ただし，任意の x ∈ R で f (x; µ) > 0 であると仮定する．
注２．確率変数 X1 , X2 , . . . , Xn が独立に確率密度関数 f (x; µ) をもつ確率分布にしたがうとき，µ̂(X1 , X2 , . . . , Xn ) を µ の不偏推定量，V(µ̂) を不偏推定量の分散とすると，不等式

V(µ̂) ≥1nI(µ)

が成り立つ．これを Cramér-Rao の不等式という．

上のサンプル問題の出題意図を説明します．簡単な繰り返し測定の問題をとおして，統計的推定の基礎概念と関連する数理についての理解を問う問題です．
問 (1) では，分散既知の正規分布モデルを取り上げ，不偏推定量，有効推定量，Cramér-Rao の不等式，などの基礎的な概念についての理解をみています．
問 (2) では，正規分布とは限らない，一般の位置母数モデルを取り上げています．µ に確率密度関数 g(x) をもつ確率分布にしたがう誤差が加わるとき，得られる観測値の確率密度関数が g(x − µ) で与えられることから結果を示すことができます．
問 (3) で述べられていることは，正規分布の特徴づけのひとつとして知られています．推定の精度と情報量とを関連付ける Cramér-Rao の不等式は，数学的には Schwarz の不等式を使って証明されます．Cramér-Rao の不等式に関連する数理の理解を問う問題です．

4サンプル問題３n 個の正整数 a1 , a2 , · · · , an が与えられているものとする. 以下の設問 (1),(2) に答えよ．
P(1) 与えられた正整数 b に対して, i∈S ai = b となる部分集合 S ⊆ {1, . . . , n}が存在するか否かを効率的に判定するためのアルゴリズムとデータ構造を設計し，必要とされる記憶領域と計算時間を解析せよ.
PP(2) 互いに素な部分集合
P S, T ⊆ {1, . . . , n} で, i∈S ai ≥ i∈T ai > 0 を満ai
たすもののうち, Pi∈Sが最小となる S, T の組みを効率的に見出すたi∈T ai
めのアルゴリズムとデータ構造を設計し，必要とされる記憶領域と計算時間を解析せよ.

上のサンプル問題の出題意図を説明します．基本的なアルゴリズムとデータ構造についての知識は，数理情報学を専攻する人にとって，必要不可欠なものです．リスト，スタック，木などの基本データ構造と，それを用いた探索や整列などの基本アルゴリズム，さらに分割統治や動的計画法などのアルゴリズム設
計法を理解し，実際の問題に対して，適切なデータ構造を選択し，正しくて効率のよいアルゴリズムを設計することが大切であると考えています．
問 (1) は，比較的単純な状況において，動的計画法を適用できるかをみる問
題です．アルゴリズムという概念，データ構造の選択，アルゴリズムの解析などについての基本的理解をみようとするものです．
問 (2) は，動的計画法の考え方をより一般的な状況に応用する力をみる問題です．これにより，動的計画法を汎用性のあるアルゴリズム設計法として捉えているかどうかをみようとしています．

5