東京大学 情報理工学系研究科 創造情報学専攻 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, (1) Space Constraint: except that the root node has at least two subtrees or is a leaf, other internal nodes have at most $m$ and at least $\lceil m/2\rceil$ subtrees; (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, any query, 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.