卷別

資料結構與演算法

選擇

國立臺灣大學 2024 · 考試 · 第 12 題

(5 points) Consider a directed acyclic graph $G = (V, E)$ of $n$ tasks where every node is a task and every edge is a dependency. If there is an edge from a task $v$ to another task $w$ , that means we need to finish $v$ before starting $w$ . We have $p$ processors of the same capability and every processor can finish any task in one unit of time.

We define a schedule function $s$ to map a task $v$ to a positive integer time step $s(v)$ . Since we have only $p$ processors, so the system can only process at most $p$ tasks in one time step. Also, a schedule needs to respect the dependency of edges.

(A)
For every positive integer $i$ , $|\{v \mid s(v) \le i\}| \le p$ .
(B)
If there is a path $(v_{i_1}, \dots, v_{i_k})$ in $G$ , then $s(v_{i_j}) < s(v_{i_k})$ for $1 \le j \le k$ .
(C)
The number of time steps required is at least $\min(\lceil n/p \rceil, L)$ , where $L$ is the number of tasks along the longest path in $G$ .
(D)
Without loss of generality, we can always assume $s(v) = 1$ for all $v$ 's without incoming edges.
(E)
If the number of processors is infinite, then we can finish all tasks in $L$ time steps, where $L$ is the number of tasks along the longest path in $G$ .

標準解析

AI 已複查