名古屋大学情報学研究科複雑系科学専攻 2021年8月実施情3

标签：

Author

祭音Myyura

Description

[1]

Napier 数（自然対数の底， $2.718281828\cdots$ ） $e$ の $x$ 乗 $\exp(x)$ を考える。

(1) $\exp(x)$ をマクローリン展開せよ。

(2) C 言語で，double 型の値を仮引数 x として受け取り，マクローリン展開に基づき計算した $\exp(x)$ の値を返す関数 exp_mac を次のように作成する。空欄 (1)，(2) を適切に埋めよ。ただし，展開の項数は 100 とする。

double exp_mac(double x) {
    double exponent = 0.0, term = (1);
    int n;

    for (n = 1; n < 101; n++) {
        exponent += term;
        term = (2)
    }

    return exponent;
}

(3) $x$ が大きくなるに従い，2. で作成した関数を用いて $\exp(x)$ を計算する場合と， $\exp(-x)$ を計算する場合のどちらが数値的に不安定になりやすいかを，その説明も付けて述べよ。また，その数値的不安定性を回避する方法を記述せよ。

[2]

10 進数 $k$ 桁の正の整数を，各桁の値を比較し，小さい順に並べ替える基数ソート（radix sort）を考える。桁数が $k$ より小さい整数は，上位桁に 0 を補って表すものとする。例えば $k=3$ の場合，整数 23，3 はそれぞれ 023，003 と表す。

(1) 基数ソートが成立するために必要な，各桁のソート結果が満たすべき条件を述べよ。

(2) (1) の条件を満たす各桁のソート法を用いて， $k$ 桁の整数 $n$ 個を基数ソートするアルゴリズムを示せ。

(3) 次の 3 桁の整数 5 個を基数ソートする過程を示せ。

(4) $k$ 桁の数値 $n$ 個の基数ソートを効率的に行う場合の計算量のオーダを，その説明も付けて見積もれ。

Kai

[1]

(1)

$\exp(x)$ のマクローリン展開は

\boxed{ \exp(x) =\sum_{m=0}^{\infty}\frac{x^m}{m!} =1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots }

である。

(2)

第 $m$ 項を

T_m=\frac{x^m}{m!}

とすると，

T_0=1,\qquad T_m=T_{m-1}\frac{x}{m}

である。したがって空欄は

\boxed{(1)=1.0},\qquad \boxed{(2)=\texttt{term * x / n;}}

となる。

完成した関数は次の通りである。

double exp_mac(double x) {
    double exponent = 0.0, term = 1.0;
    int n;

    for (n = 1; n < 101; n++) {
        exponent += term;
        term = term * x / n;
    }

    return exponent;
}

このループでは， $n=1,\ldots,100$ の各回で $T_{n-1}$ を加えるため，

\sum_{m=0}^{99}\frac{x^m}{m!}

という 100 項を計算している。

(3)

数値的に不安定になりやすいのは，正の大きな $x$ に対して $\exp(-x)$ を級数から直接計算する場合である。

\exp(-x) =1-x+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots

では，絶対値の大きい正負の項を加減した結果として，非常に小さい値が残る。浮動小数点演算ではこの相殺によって有効桁が失われ，丸め誤差が大きく増幅される（桁落ち）。

一方， $\exp(x)$ の級数は $x>0$ なら各項が非負なので，この種の相殺は生じない。ただし，極端に大きい $x$ ではオーバーフローや 100 項で打ち切ることによる誤差には注意が必要である。

直接計算を避け，

\boxed{\exp(-x)=\frac{1}{\exp(x)}}

を用いればよい。例えば，

double exp_stable(double x) {
    if (x < 0.0) {
        return 1.0 / exp_mac(-x);
    }
    return exp_mac(x);
}

とする。さらに大きい引数まで扱うには， $x=m\log 2+r$ として

\exp(x)=2^m\exp(r)

とする引数縮小も有効である。

[2]

(1)

各桁に対するソートは 安定ソートでなければならない。すなわち，現在比較している桁の値が等しい要素について，ソート前の相対順序を保存する必要がある。

これにより，すでに整列済みの下位桁の順序が，次の桁を処理したときにも壊れない。

(2)

10 進整数 $a$ の下から $j$ 桁目（ $j=0$ を一の位とする）を

d_j(a)=\left\lfloor\frac{a}{10^j}\right\rfloor\bmod 10

とする。次のように，一の位から最上位桁まで安定ソートする。

A: n 個の k 桁整数の配列

for j = 0, 1, ..., k-1:
    A をキー d_j(a) により昇順に安定ソートする

return A

各桁の処理には，0～9 の 10 個のバケット，または安定な計数ソートを用いればよい。

帰納的に， $j$ 桁を処理した時点で下位 $j$ 桁について整列している。次の桁で安定ソートすれば，同じ桁値を持つ要素の中では下位桁の順序が保存される。したがって $k$ 桁すべてを処理した後，全体が数値の昇順になる。

(3)

初期列を

223, 755, 058, 226, 735

とする。

一の位で安定ソート：

223, 755, 735, 226, 058

十の位で安定ソート：

223, 226, 735, 755, 058

百の位で安定ソート：

058, 223, 226, 735, 755

したがって最終結果は

\boxed{058,\ 223,\ 226,\ 735,\ 755}

である。

(4)

各桁を安定な計数ソートで処理する場合，1 回の処理は

$n$ 個の要素を 10 個のバケットへ分配する： $O(n)$
10 個のバケットを順に回収する： $O(n+10)$

である。これを $k$ 桁について繰り返すので，

O\bigl(k(n+10)\bigr)

となる。基数 10 は定数であるから，

\boxed{\text{時間計算量 }O(kn)}

である。補助配列とバケットに必要な空間は

\boxed{O(n+10)=O(n)}

である。特に $k$ を定数とみなせる場合，時間計算量は $O(n)$ である。

Author​

Description​

[1]​

[2]​

Kai​

[1]​

(1)​

(2)​

(3)​