問題 1 （微分積分）

(1) ∫_{x}^{∞} te^{−t^{2}}dt を求めよ．

(2) f, g を

f(x) = ∫_{x}^{∞} e^{−t^{2}}dt, g(x) = \frac{1}{2x}e^{−x^{2}}

で定義される (0, ∞) 上の関数とするとき， f(x) ≤ g(x), x > 0, であることを示せ．

(3) 次の極限の値を求めよ．

lim_{x→∞} \frac{f(x)}{g(x)}

問題 2 （線形代数）

(1) ３次元実線形空間 R^{3} から部分空間 W = \{( \begin{matrix}x \\ y \\ z \end{matrix} ) | 3x + 4y − z = 0\} への正射影

を表す行列 A を求めよ．

(2) A の固有値および固有ベクトルを求めよ．

(3) A を対角化せよ．

(4) n 次元実線形空間から m 次元部分空間への正射影を表す行列の固有多項式を求めよ．（定義． A が部分空間 W への正射影を表す行列 ↔ すべての x⃗ に対して， (i)Ax⃗ ∈ W (ii) (x⃗ − Ax⃗)⊥Ax⃗)

問題 3 （数値解析）

1010 の３乗根を求めるため， f(x) = (1 + x)^{1/3} (|x| < 1) とし， f(x) の n 次マクローリン展開を

f_{n}(x) = ∑_{k=0}^{n} \frac{f^{(k)}(0)}{k!}x^{k}

とする．

(1) 3 次マクローリン展開 f_{3}(x) を求めよ．

(2) x > 0 のとき f_{2}(x) < f(x) < f_{3}(x) であることを示せ．

(3) 1010 の３乗根を，小数点以下４桁まで正確に求める計算法を述べ，近似値を実際に求めよ．

問題 4 （離散数学Ａ）

次の I,II のうち，\underline{いずれか１つを選択して}答えよ．

I. 自然数 n に対して，

μ(n) = \begin{cases}1 & (n = 1), \\ (−1)^{l} & (n は異なる l 個の素数の積), \\ 0 & (その他) \end{cases}

により関数 μ(n) を定義する．

1. 任意の自然数 n に対して，

∑_{d|n} μ(d) = \begin{cases}1 & (n = 1), \\ 0 & (n > 1) \end{cases}

を示せ．ただし， ∑_{d|n} は n の全ての正の約数 d に関する和である．

2. 任意の N 上の関数 f に対して， g(n) = ∑_{d|n} f(d) とすれば，任意の自然数 n に対して，

f(n) = ∑_{d|n} μ(d)g(\frac{n}{d})

であることを示せ．

3. Euler 関数 φ に対して， ∑_{d|n} φ(d) = n が成立することを利用して，

φ(n) = n ∏_{p|n}(1 − \frac{1}{p})

を証明せよ．ただし， ∏_{p|n} は n の全ての正の素因数 p に関する積である． II. p を素数， N_{p} = {1, 2, …, p − 1} とする． N_{p} 上の 2 項演算 • を， x • y = z (ここで z は x × y を p で割った余り) により定める．このとき， ⟨N_{p}, • ⟩ は 1 を単位元として持つ可換群である．すなわち，以下の性質が成り立つ．

(A) 任意の x, y, z ∈ N_{p} について， (x • y) • z = x • (y • z)

(E) 任意の x ∈ N_{p} について， x • 1 = 1 • x = x

(I) 任意の x ∈ N_{p} について， x • y = y • x = 1 を満たす y ∈ N_{p} が一意に存在する (このとき， y を x の逆元と呼び，これを\overline{x} で記す)

(C) 任意の x, y ∈ N_{p} について， x • y = y • x

以下では， i 個の x を • で結んだ ((⋯ (\overbrace{x • x) • ⋯) • x) • x}^{i} を x^{i} と表す．また， ((⋯ (1 •

2) • ⋯) • x − 1) • x を x! と表す．このとき，以下の問いに答えよ．ただし，解答に性質 (A),(E),(I),(C) や，前問の結果

などを用いた場合には，それらを明記すること．

(1) p = 7 とするとき，以下の各々の値を求めよ．

(i) 3 • 5  (ii) 2^{6}  (iii) \overline{6}

(2) 次が成立することを示せ．

任意の x, y, z ∈ N_{p} について， x • y = x • z ならば y = z．

(3) 任意の正の整数 j について次が成立することを帰納法により示せ．

j ∈ N_{p} ならば ∀x ∈ N_{p}.(⋯ ((x • 1) • (x • 2)) • ⋯) • (x • j) = j! • x^{j}

(4) (2) より， {x • 1, x • 2, …, x • (p − 1)} = {1, 2, …, p − 1} が成立する．この両辺の集合のそれぞれについて全ての要素を • で結んで得られる式を等号で結び，性質 (A) と (C) を繰り返し適用することにより

(⋯ ((x • 1) • (x • 2)) • ⋯) • (x • (p − 1)) = (p − 1)! · · · · · · (α)

が導ける． (α) を利用して，任意の x ∈ N_{p} に対して， x^{p−1} = 1 が成立することを示せ．

問題 5 （離散数学Ｂ）

単純無向グラフ G = (V, E) において、頂点部分集合 S ⊆ V の任意の（異なる） 2 頂点間に辺が存在するとき、 S は G のクリークと呼ばれ、逆にどの 2 頂点間にも辺が存在しないなら、独立集合と呼ばれる。 V 自身がクリークであるとき、 G を完全グラフという。

任意整数 k に対し、十分に多くの頂点をもつグラフには、必ず大きさ k 以上のクリークもしくは大きさ k 以上の独立集合が存在することが知られている。そこで次のように関数 R を与える：

R(k) = min \{n |{n 頂点からなるグラフには、必ず大きさ k 以上のクリークもしくは独 \atop 立集合が存在する} \}

例えば、 R(2) = 2 である。

1. R(3) > 5 であることを示せ。

2. n 頂点をもつ完全グラフから、各辺を独立に 1/2 の確率で取り除いてグラフ G をつくる。頂点部分集合 S について、「S は G のクリークもしくは独立集合である」という事象を、 A_{S} で表す。確率 P (A_{S}) を求めよ。

3. 事象 B = ⋂_{S:|S|=k}\overline{A}_{S} について、

nC_{k} < 2^{_{k}C_{2}−1}  (1)

が成立するとき、 P (B) > 0 となることを示せ。

4. 式 (1) が成立するとき、 R(k) > n となることを説明せよ。

問題 6 （オートマトン理論）

アルファベットを {a, b} とする言語を考える．言語 L を aaa または aba を含む全ての文字列の集合とするとき，以下の問いに答えよ．

(1) L を受理する非決定性オートマトンのうち、状態数が 4 以下のものを一つ図示せよ。 (2) L を受理する決定性オートマトンのうち、状態数が 5 以下のものを一つ図示せよ。

問題 7 （数理論理学）

次の I,II のうち，\underline{いずれか１つを選択して}答えよ．

I. N = {0, 1, 2, 3, ⋯ } とする．すべての n ∈ N に対し，集合 A_{n} と集合 B_{n} が与えられていて |A_{n}| < |B_{n}| をみたしているとする．ただし， |A_{n}| は A_{n} の濃度である． Π_{n∈N}B_{n} は次の条件を満たす関数 f すべてから成る集合とする：

関数 f の定義域は N で，すべての n ∈ N に対し f(n) ∈ B_{n}

このとき， | ⋃_{n∈N} A_{n}| < |Π_{n∈N}B_{n}| を証明せよ．

II. 本問では，次のような論理結合子および等号を用いることとする．

連言選言否定含意
(conjunction) (disjunction) (negation) (implication)
∧ ∨ ¬ →
全称限量子存在限量子等号
(universal quantifier) (existential quantifier) (equality symbol)
∀x  ∃x  =

結合の強さは，限量子，否定，連言，選言，含意の順とする． N = {0, 1, 2, … } とする． N の要素の有限列の集合を N^{∗} で表す．頂点 (vertex) が N の要素であるような無向グラフ (undirected graph)G が与えられ

たとき， 2 引数関数記号 ∘， 1 引数述語記号 V, P ， 2 引数述語記号 E の N^{∗} 上での解釈 G[[∘]], G[[V]], G[[E]], G[[P]] を， G に基づいて次のように定める．任意の i_{1}, …, i_{m} ∈ N に対して，

• G[[∘]](i_{1} ⋯ i_{l}, i_{l+1} ⋯ i_{m}) = i_{1} ⋯ i_{l}i_{l+1} ⋯ i_{m} とする．ただし， 0 ≤ l ≤ m とする．

• G[[V]](i_{1}) = true のときかつそのときに限り， i_{1} は G の頂点である．

• G[[E]](i_{1}, i_{2}) = true のときかつそのときに限り， G において頂点 i_{1} と頂点 i_{2} を結ぶ辺 (edge) がある．

• G[[P]](i_{1}i_{2} ⋯ i_{m}) = true のときかつそのときに限り， m > 1 かつ各々の 1 ≤ k < m に対して G に頂点 i_{k} と頂点 i_{k+1} を結ぶ辺があり，かつ， i_{1}, i_{2}, …, i_{m} はすべて異なる．

関数記号 ∘，述語記号 V, E, P から構成される一階述語論理式 (first order predicate formula) （以下では単に論理式という）に関する以下の問に答えよ．

(1) 次の論理式を冠頭標準形 (prenex normal form) に変換せよ． (a) ∀i∀j(V (i) ∧ V (j) ∧ ¬(i = j) → ∃xP ((i ∘ x) ∘ j))

(b) ∀i(V (i) → ∀j(V (j) → (E(i, j) → E(j, i))))

(c) ∀i∀j(V (i) ∧ V (j) ∧ ¬(i = j) ∧ ∀x∀y(P ((i ∘ x) ∘ j) ∧ P ((i ∘ y) ∘ j) → x = y))

(2) (1) の各々の論理式が図１の無向グラフ G_{1} に対する解釈の下で成り立つか否かを答えよ．

(3) (1) の各々の論理式が図１の無向グラフ G_{2} に対する解釈の下で成り立つか否かを答えよ．

(4) G_{1} に対する解釈の下で，次の論理式が成り立つような G_{1} の頂点 a を列挙せよ．

\begin{matrix}V (a) ∧ ∃i∃j(V (i) ∧ V (j) ∧ ¬(a = i) ∧ ¬(a = j) ∧ ¬(i = j)∧ \\ (∀x(P ((i ∘ x) ∘ j) → ∃x_{1}∃x_{2}(x = (x_{1} ∘ a) ∘ x_{2})))) \end{matrix}

(5) G_{2} に対する解釈の下で，次の論理式が成り立つような G_{2} の頂点 a を列挙せよ．

V (a) ∧ ∀i∀j(E(a, i) ∧ E(a, j) → i = j))

(6) 次のことを表す論理式を書け．

(a) G は木である．すなわち， G は連結 (connected) であり、かつ、閉路 (loop) をもたない．

(b) G は２連結グラフである．すなわち，互いに異なるすべての頂点 i, j, a に対して， a を通らないような i から j への経路 (path) がある．

[figure: 0; 2; 1; 4; 3; 6; 5; 8; 7; 0; 1; 2; 3; 4; 5; 6; 8; 7; G_{1}; G_{2}; 図１無向グラフ G_{1}, G_{2}]

問題 8 （確率論）

X, Y を独立でそれぞれパラメータ λ, μ (λ, μ > 0), のポアソン分布に従う確率変数とする：

P (X = r) = e^{−λ} \frac{λ^{r}}{r!} ,  P (Y = r) = e^{−μ} \frac{μ^{r}}{r!} ,  r = 0, 1, 2, ...

(1) X の平均を求めよ．

(2) X + Y はどのような確率分布に従うか．

(3) k, n を k ≤ n である自然数とするとき，条件 X + Y = n のもとでの X = k の条件付き確率を求めよ．また，この条件付き確率分布はどのような確率分布か．

問題 9 （微分方程式）

a, b を正定数として， x(t) に関する微分方程式の初期値問題

\frac{dx}{dt} = bx^{2} − ax (t > 0), x(0) = x_{0} (x_{0} > 0)

を考える．

(1) 解 x(t) を求めよ．

(2) x_{0}, a, b の関係で分類し， t → ∞ のときの解の振る舞いを調べ，その様子を図示せよ．

問題 10 （情報システム）

次の問いについて答えよ．

(1) ヒューマン・インタフェースのモデルである， Norman による行為の７段階モデルと， Rasmussen による行為の３階層 (SRK) モデルを，それぞれモデルの概要がわかるように図示し，説明せよ．

(2) ERP （Enterprize Resource Planning）， SCM （Supply Chain Management）， CRM （Customer Relationship Management）の３つの情報システムについて，それぞれのシステムの目的，特徴，期待される効果がわかるように説明せよ．

問題 11 （アルゴリズム設計法）

次の I,II のうち，\underline{いずれか１つを選択して}答えよ．

I. 以下の各問に答えよ。

1. x と整数 n(≥ 1) が入力のとき、 x^{n} を O(log n) 回の乗算で求める再帰的アルゴリズムを書け。

2. n+1 個の整数 a_{1}, a_{2}, ⋯, a_{n}, b が与えられたとき、 a_{i}(1 ≤ i ≤ n) の中から適当に何個かを選んで、それらの総和がちょうど b になるようにできるか否かを判定する時間計算量が O(nb) のアルゴリズムを書け。（ヒント: f(i, j) を次のような関数とする。 a_{1}, a_{2}, ⋯, a_{i} の中から適当に何個かを選んで、それらの総和がちょうど j になるようにできるとき f(i, j) = 1、そうでないとき f(i, j) = 0 である。すると、問題は f(n, b) を求めることに帰着する。動的計画法を用いよ。 )

II. 連結無向グラフ G = (V, E) の各辺 e ∈ E にコスト w_{e} が付けられているとする。 G のすべての頂点を含む部分グラフで木になっているものを、 G のスパンニング木と呼ぶ。いま G の部分グラフ H のコストを、 H に含まれる辺の重みの最小値 min{w_{e} | e ∈ H} とする。

1. コスト最小のスパンニング木を計算する、なるべく簡単なアルゴリズムを与えよ。（注：プログラムではなく、読んで解りやすいアルゴリズムを記述すること）

2. コスト最大のスパンニング木を計算する、なるべく効率のよいアルゴリズムを与えよ。（(1) の注に同じ）

3. (2) のアルゴリズムの正当性を証明し、その計算量を解析せよ。

問題 12 （プログラミング）

次の I,II のうち，\underline{いずれか１つを選択して}答えよ．

I. 以下に示すプログラムは，素数（prime number）を小さい順に求める C 言語によるプログラムである．このプログラムに関する以下の問いに答えよ．なお，プログラムの左側の数字は，行の番号を示すもので，プログラムの一部ではない．また，プログラム中の % は，剰余演算（remainder operation）を行う演算子である．

     1:    #include <stdio.h>
     2:
     3:    #define M 5
     4:
     5:    int n;
     6:    int table[M];
     7:
     8:    int check(int k)
     9:    {
    10:        int j;
    11:
    12:        j = 0;
    13:        while (j < n) {
    14:            if (k % table[j] == 0) {
    15:                return 0;
    16:            }
    17:            j = j + 1;
    18:        }
    19:        return 1;
    20:    }
    21:
    22:    main()
    23:    {
    24:        int i;
    25:
    26:        n = 0;
    27:        i = 2;
    28:        while (n < M) {
    29:            if (check(i) != 0) {
    30:                printf("%d\n", i);
    31:                table[n] = i;
    32:                n = n + 1;
    33:            }
    34:            i = i + 1;
    35:        }
    36:    }

(1) このプログラムで，変数 n と配列 table は何を保持するためのものであるか説明せよ．

(2) このプログラムを実行する場合を考える．

(ア) このプログラムが出力する文字列を答えよ．

(イ) 14 行めの剰余演算が実行される回数は何回か．

(ウ) 14 行めの if 文を最後に実行する時の j， k， n の値はそれぞれいくらか．

(3) ある数が素数であるかを調べるためには，その数の平方根（square root）以下の数で割り切れないことを確認すればよいが，このプログラムはこの性質を活用していない．

(ア) この性質を活用して実行効率を改善したプログラムを示せ．ただし，平方根を求める関数を用いてはならず，乗算（multiplication operation）の実行回数ができる限り少なくなるようにすること．プログラムの修正箇所が少ない場合には，元のプログラムとの差分のみを示してもよい．

(イ) 改良後のプログラムを実行した場合に，剰余演算と乗算が実行される回数はそれぞれ何回か．

II. タイプＡとタイプＢのＣ言語プログラムは，同じ計算を実行するものであるが，一方は誤差が生じやすい．誤差が生じやすいタイプを示し，その理由を記せ．

• タイプＡ

#include <stdio.h>
int main()
{
int i;
float sum=0.0;
for (i=1; i<=1000; i++)
    sum=sum+i/10.0;
printf("%f \n",sum);
return 0;
}

• タイプＢ

#include <stdio.h>
int main()
{
float x, sum=0.0;
for (x=0.1; x<=100.0; x+=0.1)
    sum=sum+x;
printf("%f \n",sum);
return 0;
}