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

标签：

• Tokyo-University
• Dynamic-Programming-Principle
• Zero-Moment-Point
• Backus-Naur-Form
• Transparent-Web-Cache-in-Wide-Area-Networks
• Autonomous-Vehicle-Dynamic-Map
• Thread-Level-Speculative-Execution
• Procedural-Modeling
• K-Nearest-Neighbors

Author

itsuitsuki

Description

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

题目描述

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

1. 动态规划。
2. 零力矩点（ZMP）。
3. BNF（巴科斯范式）。
4. 广域网中的透明缓存。
5. 自动驾驶系统中的动态地图。
6. 线程级推测并行执行。
7. 程序化建模。
8. $k$ 近邻算法。

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 $k$ 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.)