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

标签：

• Tokyo-University
• Nondeterministic-Polynomial-Time-Completeness
• Tail-Recursion
• Step-Response
• Transfer-Function
• Discrete-Cosine-Transform
• Public-Key-Cryptography
• Domain-Name-System
• Translation-Lookaside-Buffer
• Left-to-Right-Leftmost-Derivation-One-Lookahead-Parsing

Author

itsuitsuki

Description

日本語

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

1. NP 完全性
2. 末尾再帰
3. ステップ応答と伝達関数
4. 離散コサイン変換(DCT)
5. 公開鍵暗号
6. DNS (Domain Name Service)
7. TLB (Translation Lookaside Buffer)
8. LL(1)構文解析

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. NP-complete
2. Tail recursion
3. Step response and transfer function
4. Discrete Cosine Transform, DCT
5. Public-key cryptosystem
6. DNS (Domain Name Service)
7. TLB (Translation Lookaside Buffer)
8. LL(1) parsing

题目描述

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

1. NP 完全性。
2. 尾递归。
3. 阶跃响应与传递函数。
4. 离散余弦变换（DCT）。
5. 公钥密码体制。
6. DNS（域名系统）。
7. TLB（地址转换后备缓冲器）。
8. LL(1) 语法分析。

Kai

NP-complete

NP complete is a NP problem $Y$ that every NP problem $X$ can (Karp) reduce to,

i.e. $Y\in NP\land (\forall X\in NP,X\le_P Y)$,

where a NP (nondeterministic polynomial) problem is that can be verified in polynomial time, but not necessarily able to be solved in polynomial time.

Note that NP-Complete problems are the intersection of NP and NP-Hard problems, which means they are the supremum of NP and the infimum of NP-Hard.

The “first” NP-Complete problem is Circuit-SAT that asks if there is a way of input (with $n$ bits) to so that the output of a logic digital circuit is 1.