跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2024年8月実施 情報学基礎 F2-1

标签：

Author​

itsuitsuki

Description​

Q.1​

Let S=(3,−1,2,−4,5,−1,3,−3,4,−2,1,−2)S = (3, -1, 2, -4, 5, -1, 3, -3, 4, -2, 1, -2) be a number sequence of length 12 and s(i)s(i) is the value of the ii-th element of SS. For example, s(1)=3s(1) = 3 holds. Let us define maxSum(i,j)=max⁡i≤a≤b≤j∑k=abs(k)\text{maxSum}(i, j) = \max_{i \leq a \leq b \leq j} \sum_{k=a}^{b} s(k) and M=maxSum(1,12)M = \text{maxSum}(1, 12).

(1) Derive the value of maxSum(1,4)\text{maxSum}(1, 4).

(2) Derive MM and all the values of (a,b)(a, b) that satisfy ∑k=abs(k)=M\sum_{k=a}^{b} s(k) = M.

(3) Derive all the values of (a,b)(a, b) that satisfy ∑k=abs(k)=M−1\sum_{k=a}^{b} s(k) = M - 1.

Q.2​

Consider an algorithm for generating an undirected graph using random numbers, whose pseudocode is given below.

let G1(V1,E1)G_1(V_1, E_1) be an undirected graph with V1={v0,v1}V_1 = \{v_0, v_1\} and E1={{v0,v1}}E_1 = \{\{v_0, v_1\}\};

for i=2i = 2 to nn do

begin

    let viv_i be a new vertex;

    let vjv_j and vkv_k be distinct vertices randomly selected from Vi−1V_{i-1};

    let Gi(Vi,Ei)G_i(V_i, E_i) be an undirected graph with Vi=Vi−1∪{vi}V_i = V_{i-1} \cup \{v_i\} and

        Ei=Ei−1∪{{vi,vj},{vi,vk}}E_i = E_{i-1} \cup \{\{v_i, v_j\}, \{v_i, v_k\}\};

end

Note that for any pair of distinct vertices (vj,vk)(v_j, v_k), the selection probability is positive. Obviously, any graph Gn(Vn,En)G_n(V_n, E_n) constructed by this algorithm is connected, has n+1n+1 vertices, and does not contain a self-loop or a multi-edge. In the following, we use GnG_n to denote Gn(Vn,En)G_n(V_n, E_n).

For a graph GnG_n, deg⁡Gn(vp)\deg_{G_n}(v_p) denotes the degree of a vertex vp∈Vnv_p \in V_n (i.e., the number of edges connecting to vpv_p), and distGn(vp,vq)\text{dist}_{G_n}(v_p, v_q) denotes the length (i.e., the number of edges) of the shortest path (i.e., the path consisting of the minimum number of edges) between two distinct vertices vpv_p and vqv_q in VnV_n. Note that deg⁡Gn(vp)\deg_{G_n}(v_p) and distGn(vp,vq)\text{dist}_{G_n}(v_p, v_q) are positive integers depending on randomly selected vertices in the algorithm.

In the following, nn is an even number greater than or equal to 4. Let Gn\mathcal{G}_n be the set of all possible undirected graphs GnG_n generated by this algorithm. For example, for any nn, min⁡Gn∈Gn{ min⁡vp∈Vn{deg⁡Gn(vp)} }=2\min_{G_n \in \mathcal{G}_n} \{~ \min_{v_p \in V_n} \{\deg_{G_n}(v_p)\} ~\} = 2 and max⁡Gn∈Gn{ min⁡vp∈Vn{deg⁡Gn(vp)} }=2\max_{G_n \in \mathcal{G}_n} \{~ \min_{v_p \in V_n} \{\deg_{G_n}(v_p)\} ~\} = 2 hold because deg⁡Gn(vn)=2\deg_{G_n}(v_n) = 2 always holds and deg⁡Gn(vp)≥2\deg_{G_n}(v_p) \geq 2 always holds for any vertex vp∈Vnv_p \in V_n.

Derive the following values. Note that the values may be given as mathematical expressions of nn.

(1) max⁡Gn∈Gn{ max⁡vp∈Vn{deg⁡Gn(vp)} }\max_{G_n \in \mathcal{G}_n} \{ ~\max_{v_p \in V_n} \{\deg_{G_n}(v_p)\}~ \}

(2) min⁡Gn∈Gn{ max⁡p<q,vp∈Vn,vq∈Vn{distGn(vp,vq)} }\min_{G_n \in \mathcal{G}_n} \{~ \max_{p < q, v_p \in V_n, v_q \in V_n} \{\text{dist}_{G_n}(v_p, v_q)\} ~\}

(3) max⁡Gn∈Gn{ max⁡p<q,vp∈Vn,vq∈Vn{distGn(vp,vq)} }\max_{G_n \in \mathcal{G}_n} \{~ \max_{p < q, v_p \in V_n, v_q \in V_n} \{\text{dist}_{G_n}(v_p, v_q)\} ~\}

题目描述​

  1. 令 S=(3,−1,2,−4,5,−1,3,−3,4,−2,1,−2)S=(3,-1,2,-4,5,-1,3,-3,4,-2,1,-2)，并定义
    maxSum⁡(i,j)=max⁡i≤a≤b≤j∑k=abs(k),M=maxSum⁡(1,12).\operatorname{maxSum}(i,j)= \max_{i\le a\le b\le j}\sum_{k=a}^b s(k),\qquad M=\operatorname{maxSum}(1,12).
    求 maxSum⁡(1,4)\operatorname{maxSum}(1,4)；求 MM 及全部使区间和为 MM 的 (a,b)(a,b)；再求全部使区间和为 M−1M-1 的 (a,b)(a,b)。
  2. 随机图算法从边 {v0,v1}\{v_0,v_1\} 开始。对 i=2,…,ni=2,\ldots,n，新建 viv_i，从已有顶点中随机选不同的 vj,vkv_j,v_k，加入边 {vi,vj},{vi,vk}\{v_i,v_j\},\{v_i,v_k\}。设 n≥4n\ge4 为偶数，Gn\mathcal G_n 为所有可能输出。求：
    1. 所有图中最大可能顶点度；
    2. 所有图中最小可能直径；
    3. 所有图中最大可能直径。 答案可写成 nn 的表达式。

考点​

  • 最大连续子数组和：计算最大和及次优和，并完整枚举达到指定和的区间。
  • 图度数与直径的极值构造：分析每个新顶点连接两个旧顶点的生成规则，构造并证明最大度、最小直径和最大直径界。
本页目录