東京大学 情報理工学系研究科 創造情報学専攻 2007年8月実施 筆記試験 第4問

标签：

• Tokyo-University
• Divide-and-Conquer
• B-Tree
• Sampling-Theorem-and-Aliasing
• Impulse-and-Step-Response-Relationship
• Vector-Quantization
• Out-of-Order-Execution
• Regular-Grammar-and-Regular-Language
• Common-Gateway-Interface

Author

itsuitsuki, 祭音Myyura

Description

日本語

以下に示す情報システムに関する8項目から4項目を選択し、各項目を4～8行程度で説明せよ。必要に応じて例や図を用いてよい。

1. 分割統治法 (divide and conquer algorithm)
2. B 木 (B-tree)
3. ナイキスト周波数
4. インパルス応答とステップ応答とその関係
5. ベクトル量子化
6. アウトオブオーダ (out-of-order) 実行
7. 正規文法と正規言語（必ず例を挙げて説明のこと）
8. Web システムにおける CGI (Common Gateway Interface)

English

Select four items out of the following eight items concerning information systems, and explain each item in approximately 4~8 lines of text. If necessary, use examples or figures.

1. Divide and conquer algorithm
2. B-tree
3. Nyquist frequency
4. Impulse response and step response and their relationship
5. Vector quantization
6. Out-of-order execution
7. Regular grammar and regular language (Examples are mandatory.)
8. CGI (Common Gateway Interface) in Web systems

题目描述

从下列八个信息系统相关主题中任选四个，每个用约 4～8 行说明；必要时可使用示例或图。第 7 项必须举例。

1. 分治算法。
2. B 树。
3. 奈奎斯特频率。
4. 冲激响应、阶跃响应及二者关系。
5. 向量量化。
6. 乱序执行。
7. 正则文法与正则语言。
8. Web 系统中的 CGI（Common Gateway Interface，公共网关接口）。

Kai

Divide and conquer algorithm

A methodology including three parts: dividing, conquering and merging. An divide-and-conquer algorithm first divides a problem into $a$ smaller subproblems (e.g. with $n/b$ size), then conquers them by solving them (the solution is also got by a recursive call, breaking into smallest constant-size pieces and gathering usually), and finally merges the solutions.

Some examples are Merge sort, binary search and binary tree traversal.

The time complexity for such an algorithm is $T(n)$, following this formula:

$$T(n)=aT(n/b)+f(n)$$

And we can solve $T(n)$ by building a tree to analyze with Master theorem.

For example, when $T(n)=T(n/2)+\Theta(n)$, the work over all recursion levels is $\Theta(n+n/2+n/4+\cdots)=\Theta(n)$.

B-tree

A data structure which is based on an $m$-ary tree, where the number of entries (keys) stored in every internal node is $r-1$ if it has $r$ subtrees. It satisfies that for an $m$-order B-tree with $m\ge3$, (1) Space Constraint: every node has at most $m-1$ keys, and every non-root node, including a leaf, has at least $\lceil m/2\rceil-1$ keys. An internal node with $r-1$ keys has $r$ children; an internal root has between 2 and $m$ children. An empty tree may have a root with no keys; (2) Ordering: the stored keys are ordered: for a node represented by $S_0,K_1,S_1,\dots,K_{r-1},S_{r-1}$, every key in $S_{i-1}$ is smaller than $K_i$, and every key in $S_i$ is larger than $K_i$; (3) Balance: the leaves are all at the same depth.

In application, B-tree is used to store data on disk or in databases. When querying data on disks, disk I/O is time-consuming and proportional to tree height. A B-tree tackles that with a small height and wide nodes: disk I/O uses a page, for example 4 KB, as a unit, so reading one entry or multiple contiguous entries need not require more I/O.

For $N$ stored keys, a single-key search, insertion or deletion uses $O(\log_m N)$ node accesses when $m$ is treated as fixed (more precisely, the height is $O(\log_{\lceil m/2\rceil}N)$). This makes a B-tree better in disk I/O than binary-tree data structures.

Out-of-order execution

The processor issues an instruction when its operands and a functional unit are ready, even if an earlier independent instruction is stalled. Register renaming removes false dependencies, and a reorder buffer commits results in program order to preserve precise state. This exploits instruction-level parallelism without changing program semantics.

Regular grammar and regular language

A right-linear grammar has productions of the form $A\to aB$, $A\to a$, or $A\to\varepsilon$. The languages generated by such grammars are exactly those recognized by finite automata (and denoted by regular expressions). For example, $S\to aS\mid b$ generates the regular language $\{a^n b\mid n\ge0\}$, whose regular expression is a*b.

Nyquist frequency

For a sampling rate $f_s$, the Nyquist frequency is $f_s/2$. Frequency components above it can alias into the lower frequency range after sampling. To reconstruct a signal bandlimited to $|f|\le B$ without endpoint ambiguity, choose $f_s>2B$ and apply an appropriate analog anti-aliasing filter before sampling. For example, sampling at $8$ kHz gives a Nyquist frequency of $4$ kHz. This is different from the Nyquist rate $2B$, which is the rate associated with a specified signal bandwidth.

Impulse and step responses

For a continuous-time linear time-invariant system initially at rest, the impulse response $h(t)$ is the output to $\delta(t)$, while the step response $g(t)$ is the output to the unit step $u(t)$. Convolution gives

$g(t)=(h*u)(t)=\int_{-\infty}^{t}h(\tau)\,d\tau,\qquad h(t)=\frac{d g(t)}{dt}.$

The derivative is understood in the distributional sense if the system has an instantaneous feedthrough or jumps. For a causal system the integral may be written from $0^-$, retaining any impulse at zero. In discrete time the corresponding relations are $g[n]=\sum_{k=-\infty}^n h[k]$ and $h[n]=g[n]-g[n-1]$. These identities require linearity, time invariance and the specified zero initial state; they are not general identities for nonlinear systems.

Vector quantization

Vector quantization replaces an input vector $x\in\mathbb R^d$ by a representative vector from a finite codebook $\{c_1,\ldots,c_K\}$. For squared-error distortion, the encoder selects $k=\arg\min_j\|x-c_j\|^2$ and transmits or stores its index. The decoder reconstructs $c_k$, so the representation is generally lossy. A fixed-length index requires $\lceil\log_2K\rceil$ bits per vector, with the codebook shared in advance. Codebooks may be learned by alternating nearest-neighbor assignment and centroid updates, as in $k$-means. Jointly quantizing correlated components can use bits more efficiently than treating each component independently.

CGI in Web systems

CGI defines an interface between a Web server and an external program used to generate a response. The server passes request metadata through variables such as REQUEST_METHOD and QUERY_STRING, and passes request-body data through the program's standard input. The program writes response headers, including a content type, followed by a body to standard output; the server forwards the response to the client. For example, a form submission can invoke a program that queries a database and generates an HTML result. Traditional CGI commonly starts a process per request, which can incur substantial overhead; CGI itself specifies the interface rather than a programming language. The interface is described in RFC 3875.