跳到主要内容

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

Author​

itsuitsuki

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)

Description (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

Kai​

Divide and conquer algorithm

A methodology including three parts: dividing, conquering and merging. An divide-and-conquer algorithm first divides a problem into smaller subproblems (e.g. with 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 , following this formula:

And we can solve by building a tree to analyze with Master theorem.

For example, when , there are calls.

B-tree

A data structure which is based on a -ary tree, where the number of entries (keys) stored in every node is if it has subtrees. It satisfies that for an -order B-Tree, (1) Space Constraint: except the root node must have ≥ 2 subtrees or zero, other internal nodes must have at most and at least subtrees; (2) Ordering: the stored keys are ordered: for a node represented by , where ’s are keys and ’s are subtrees, ; (3) Balance: the leaves are all at the same depth.

In application, B-tree is used to store data in disk or databases. When querying data in disks, disk I/O is time-consuming (proportional to tree height) and B-tree can tackle that with a small height and wide nodes (with multiple entries, but without much cost since disk I/O uses a page with some 4KB data as an unit so an entry or multiple contiguous entries do not differ much).

For a tree with nodes, any query, insertion or deletion takes times. This makes B-tree better in disk I/O than binary tree data structures.

目录