跳到主要内容

大阪大学 情報科学研究科 情報数理学専攻 2019年8月実施 情報数理学 情報基礎

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

1​

(1) 正の実数 nn 個からなるリスト AA に、次の SORT-1 を適用する時間計算量を求めよ。

SORT-1(A)
    for j ← 2 to n do
        s ← A[j]
        i ← j-1
        while i > 0 and A[i] > s do
            A[i+1] ← A[i]
            i ← i-1
        end while
        A[i+1] ← s
    end for

(2) 正の実数を最大値で割り、(0,1](0,1] に正規化した A[1],…,A[n]A[1],\ldots,A[n] を、次の SORT-2 で整列する。⌈x⌉\lceil x\rceil は切上げを表す。

SORT-2(A)
    B[1],...,B[n] ← 空リスト
    for i ← 1 to n do
        A[i] を B[ceil(n A[i])] に挿入
    end for
    for i ← 1 to n do
        SORT-1(B[i])
    end for
    B[1],...,B[n] を順に連接

(i) A[i]A[i] が独立に (0,1](0,1] 上で一様分布すると仮定する。各バケットの要素数の期待値・分散と、SORT-1(B[i])(B[i]) の平均時間計算量を求めよ。

(ii) SORT-2 の平均・最悪時間計算量を求めよ。

2​

nn 桁の正整数の乗算で必要な1桁整数同士の乗算回数を考える。

(1) nn が偶数のとき x=a10n/2+bx=a10^{n/2}+b, y=c10n/2+dy=c10^{n/2}+d と分けると

xy=ac10n+{ac+bd−(a−b)(c−d)}10n/2+bdxy=ac10^n+\{ac+bd-(a-b)(c-d)\}10^{n/2}+bd

である。この3回の部分乗算を再帰的に用いる回数 T(n)T(n) の漸化式を示し、T(n)=O(nlog⁡23)T(n)=O(n^{\log_2 3}) を示せ。

(2) 再帰的に3分割して乗算するときの回数 S(n)S(n) の漸化式を示し、S(n)=O(nlog⁡36)S(n)=O(n^{\log_3 6}) を示せ。

(3) 十分大きい nn で T(n),S(n)T(n),S(n) を比較せよ。log⁡23<1.6\log_2 3<1.6 を用いてよい。

3​

自己ループを持たず、各頂点間に高々1本の辺がある有向グラフの接続行列 B=(bij)∈R∣V∣×∣E∣B=(b_{ij})\in\mathbb R^{|V|\times|E|} を、辺 eje_j が頂点 viv_i から出るとき −1-1、入るとき 11、それ以外を0として定義する。

BBTBB^T と BTBB^TB の各要素の意味を説明し、次のグラフについて両行列を求めよ。頂点順は v1,…,v7v_1,\ldots,v_7、辺順は e1,…,e11e_1,\ldots,e_{11} とする。

Kai​

1​

(1) SORT-1 は挿入ソートである。最悪の場合、第 jj 回に j−1j-1 個を移動するので

∑j=2n(j−1)=n(n−1)2\sum_{j=2}^n(j-1)=\frac{n(n-1)}2

より、最悪時間計算量は Θ(n2)\boxed{\Theta(n^2)}。無作為な順列に対する平均も Θ(n2)\Theta(n^2)、既に整列済みの場合は Θ(n)\Theta(n) である。

(2)(i) バケット ii の要素数を NiN_i とする。各要素が入る確率は 1/n1/n なので Ni∼Bin⁡(n,1/n)N_i\sim\operatorname{Bin}(n,1/n)、したがって

E[Ni]=1,V[Ni]=1−1n,E[Ni2]=2−1n.\boxed{E[N_i]=1,\qquad V[N_i]=1-\frac1n},\qquad E[N_i^2]=2-\frac1n.

挿入ソートの時間は O(1+Ni2)O(1+N_i^2) で抑えられるから、平均は Θ(1)\boxed{\Theta(1)}。

(ii) 分配と連接に Θ(n)\Theta(n)、全バケットの平均整列時間に ∑iO(E[Ni2]+1)=O(n)\sum_iO(E[N_i^2]+1)=O(n) を要する。よって平均は Θ(n)\boxed{\Theta(n)}。全要素が同一バケットに入り逆順に並ぶ場合は挿入ソートが Θ(n2)\Theta(n^2) を要するので、最悪は Θ(n2)\boxed{\Theta(n^2)}。

2​

(1) n=2kn=2^k とすると、T(1)=1T(1)=1, T(n)=3T(n/2)T(n)=3T(n/2) より

T(n)=3k=nlog⁡23.\boxed{T(n)=3^k=n^{\log_2 3}}.

一般の桁数も上位に0を補えば同じオーダとなる。

(2) R=10n/3R=10^{n/3} とし、x=aR2+bR+cx=aR^2+bR+c, y=dR2+eR+fy=dR^2+eR+f と分ける。6積

ad, be, cf, (a−b)(d−e), (a−c)(d−f), (b−c)(e−f)ad,\ be,\ cf,\ (a-b)(d-e),\ (a-c)(d-f),\ (b-c)(e-f)

を求めれば、例えば ae+bd=ad+be−(a−b)(d−e)ae+bd=ad+be-(a-b)(d-e) のように交差項が得られ、

xy=adR4+(ae+bd)R3+(af+be+cd)R2+(bf+ce)R+cfxy=adR^4+(ae+bd)R^3+(af+be+cd)R^2+(bf+ce)R+cf

を再構成できる。よって S(1)=1S(1)=1, S(n)=6S(n/3)S(n)=6S(n/3) であり、n=3kn=3^k なら

S(n)=6k=nlog⁡36.\boxed{S(n)=6^k=n^{\log_3 6}}.

(3) 65=7776>6561=386^5=7776>6561=3^8 より log⁡36>8/5=1.6>log⁡23\log_3 6>8/5=1.6>\log_2 3。したがって T(n)=o(S(n))\boxed{T(n)=o(S(n))} であり、十分大きい nn では2分割法の方が少ない乗算回数で済む。

3​

BBTBB^T の対角成分は頂点の次数（入次数と出次数の和）、非対角成分は隣接していれば −1-1、そうでなければ0である。

BTBB^TB の対角成分は2。異なる2辺について、共通端点がなければ0、共通端点に両方が入るか両方が出るなら1、一方が入り他方が出るなら −1-1 である。

BBT=(2−1−10000−130−1−100−103−10−100−1−15−1−1−10−10−130−100−1−103−1000−1−1−13).\boxed{BB^T=\begin{pmatrix} 2&-1&-1&0&0&0&0\\ -1&3&0&-1&-1&0&0\\ -1&0&3&-1&0&-1&0\\ 0&-1&-1&5&-1&-1&-1\\ 0&-1&0&-1&3&0&-1\\ 0&0&-1&-1&0&3&-1\\ 0&0&0&-1&-1&-1&3 \end{pmatrix}}.
BTB=(21−10−1000000120−10−100000−10211011−1000−1120111−100−101020−100−100−101020−100−10011−1021−11000110−112−10100−1−100−1−12110000−101012100000−101112).B^TB=\begin{pmatrix} 2&1&-1&0&-1&0&0&0&0&0&0\\ 1&2&0&-1&0&-1&0&0&0&0&0\\ -1&0&2&1&1&0&1&1&-1&0&0\\ 0&-1&1&2&0&1&1&1&-1&0&0\\ -1&0&1&0&2&0&-1&0&0&-1&0\\ 0&-1&0&1&0&2&0&-1&0&0&-1\\ 0&0&1&1&-1&0&2&1&-1&1&0\\ 0&0&1&1&0&-1&1&2&-1&0&1\\ 0&0&-1&-1&0&0&-1&-1&2&1&1\\ 0&0&0&0&-1&0&1&0&1&2&1\\ 0&0&0&0&0&-1&0&1&1&1&2 \end{pmatrix}.
本页目录