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

Author

itsuitsuki

Description (English)

Select four items out of the following eight items concerning information systems, and explain each item in approximately from four to eight lines. If necessary, use examples, figures or equations.

1. Dynamic programming
2. Zero Moment Point (ZMP)
3. BNF (Backus-Naur Form or Backus Normal Form)
4. Transparent cache in wide area networks
5. Dynamic map in self-driving car system
6. Thread-level parallel speculative execution
7. Procedural modeling
8. k-nearest neighbor algorithm

Kai

Dynamic Programming

An algorithm paradigm that stores the optimal solution structures of subproblems to avoid redundant computation in traversal. It consists of several factors: initial conditions, the definition of the subproblem, the state transition equation (and the order of updating).

k-nearest neighbor algorithm

A classification algorithm which selects a list of nearest neighboring data points from the query vector in a space (usually Euclidean) and assign the class of the query as the majority class among the list. The error of this classifier is not less than that of an optimal Bayesian classifier, but not greater than 2 times the error of that Bayesian classifier. (Also, this algorithm can be implemented by a KD-Tree or Ball Tree to efficiently search neighbors.)