非确定性和Kleene定理
4 非确定性和Kleene定理
4.1 非确定型有限自动机
为了证明正则语言等价于能够被FA识别的语言，我们先对FA作一些方便性的扩充。仍然具有有限的状态数，且识别语言的能力保持不变。一些限制放宽了，更容易构造和解释。
例子4.1图4-1a显示了例子3.14构造的FA，它接受的语言是(11+110)*0，图4-1b显示了一个不同于一般FA的例子，状态q4没有转移箭头，而状态q0在输入字符为1时有两个转移箭头。
状态 q4没有转移箭头，含义是不存在一个起始字符为a（本例为0或1）的输入字符串能够使得状态从q4转移到某个接受状态，我们可以增加一个失败（或死，dead）状态f，对于输入字符a，状态q4转移到f，失败状态的含义是只有进入没有离开的转移箭头。显然任何被成功接受的字符串都不会进入失败状态，因此为了简化图面，往往省略失败状态，而不会影响自动机的接受能力。
状态q0在同一个输入字符时有多个转移箭头，看起来是对传统FA的很大的突破。我们无法象传统FA机那样线性地记录字符串在FA中的转移过程，而在某些步骤出现了歧义，因此FA机要并行地运算各种可能。
但这种带多向转移的图似乎更适合正则表达式，比如图4-1b，从q0到q0有两个循环，一个表示的字符串是(11)*，另一个表示的是(110)*，综合起来，从q0到q0的字符串是(11+110)*，则从q0到q4的字符串是(11+110)*0。反过来，根据正则表达式(11+110)*0也能够很直观地画出相应的带多向转移的FA。
由于同一个字符串可能带来FA多个状态转移路径，因此现在问题变成，是否存在一条到达接受状态的路径，这类似于根据正则表达式生成字符串，某些步骤可以有多种尝试，只要其中一种尝试生成了字符串，则认为该字符串符合这个正则表达式。
因此这类FA给正则语言的分析引入了一个新的概念，即猜测尝试。现在不考虑这种具体实现的问题，而考虑如何形式化定义这类FA。我们只需要修改（或扩充）传统FA的转移函数的定义。传统的转移函数输入一个字符，转移到一个状态，即Q中的一个元素，例子4.1中的转移函数则转移到0个或多个状态，即Q的一个子集，包括空集。我们称这种转移函数是非确定的，而这样的FA称为非确定型FA（nondeterministic FA, NFA），而传统的FA称为确定型FA（deterministic FA, DFA）。目前我们看起来NFA比DFA要强大很多，以后将证明任何一个NFA都能构造一个完全模拟它的DFA，因此非确定型没有增强FA的能力。
定义4.1 非确定型有限自动机（NFA）是一个5元组，M=（Q, ∑, q0, δ, A），Q和∑是非空有限集，q0∈Q，A?Q，转移函数定义为：
δ: Qx∑→2Q
2Q是Q的幂集，即所有Q的子集组成的集合，则函数δ的值从确定型的一个状态放松成一个状态集。
思考：初始状态可不可以由一个状态扩充成一个状态集？
类似地扩充连续转移函数（或称字符串的转移函数）δ*的定义，其形式仍然是：
δ*(p, xa) = δ(δ*(p, x), a)
自然想到用递归定义，首先，空串不影响状态变迁，但转移函数的值是一个集合，而不是单个状态，因此：
δ*(p, Λ)={p}
而对于非空字符串x=a 1a 2...a n ，δ*(p, x)的值也应该是一个集合，设q ∈δ*(p, x)，含义是存在一个状态路径：p 0, p 1, ..., p n ，其中p 0=p ，p n =q ，对每一个i ，0 p i ∈δ*(p i-1, a i ) 定义4.2a （NFA 的δ*函数的非递归定义）给定NFA M=（Q, ∑, q 0, δ, A ），p 是任意一个状态，则δ*(p, Λ)=p ，对于任意一个字符串x= a 1a 2...a n ，δ*(p, x)是所有满足下面条件的状态q 组成的集合。存在一个状态路径p 0, p 1, ..., p n ，其中p 0=p ，p n =q ，对每一个i ，0 p i ∈δ*(p i-1, a i ) 为了得到递归定义，令x=ya n 。根据定义4.2a ，对于δ*(p, x)的任意一个状态q ，都存在δ*(p, y)中的一个状态r ，使得q ∈δ(r, a n )。反过来，对于δ*(p, y)中的任何一个状态r ，δ(r, a n )的元素都属于δ*(p, ya n )，即可以递归定义如下： δ*(p, ya n ) = {q | q ∈δ(r, a n )且r ∈δ*(p, y)} 进一步的简化形式见下面的定义4.2b 。 定义4.2b （NFA 的δ*函数的递归定义）给定NFA M=（Q, ∑, q 0, δ, A ），函数δ*: Qx ∑*→2Q 定义如下： 1. δ*(q, Λ)={q} 2. δ*(q, ya)= ),() ,(*a p y p p δδ ?∈ 显然，δ*(q, a)= δ(q, a)仍然成立，因此递归的起点实际上可以是长度为1的字符串。 定义4.3 NFA M=（Q, ∑, q 0, δ, A ）接受字符串x 的条件是δ*(q0, x)?A ≠φ。M 接受（或识别）的语言由所有被M 接受的字符串组成，记为L(M)。一个语言L 被M 识别当且仅当L=L(M)。 例子4.2 M=（Q, ∑, q 0, δ, A ），Q={q0, q1, q2, q3}，∑={0, 1}，A={q3}，δ的定义如下表： 参见图4-2，现在要确定M 接受的语言。 分析：对一些字符串计算δ*(q0, x)，x 的长度逐渐增加。首先计算长度为1的字符串（直接根据上面的转移表）， δ*(q 0, 0)={q 0}，δ*(q 0, 0)={q 0, q 1} δ*(q 0, 11) δ*(q 0, 01) δ*(q 0, 111) δ*(q 0, 011) 见104页 M 接受的语言的正则表达式是：{0, 1}*{1}{0, 1}2。这是我们在例子3.15中讲到的L 3，右数第3个字符为1。参照图4-2的NFA ，能够很容易地构造出接受语言L n 的、带n+1个状态的NFA 。在例子3.14，我们说明了接受Ln 的DFA 至少需要2n 个状态，这里显示了接受同样语言的NFA 往往比最简单的DFA 具有少得多的状态。 尽管NFA 在概念上作了很有效的扩充，接受字符串的方式也简洁得多，但NFA 接受语言的能力并没有增加，任何能被NFA 接受的语言也能被DFA 接受。我们将给出一个构造性证明，显示消除NFA 的非确定性的通用方法，得到的DFA 保持了NFA 识别字符串的性质，因此识别同样的语言。我们知道NFA 状态转移函数的结果是一个集合，而DFA 相应结果是一个元素，因此将NFA 转变成一个DFA 的简单方法就是把集合看成一个更大集合（幂集）的元素，而原来的单个元素看成只有一个元素的集合，这种方法称为子集构造法（subset construction ），DFA 中的状态是NFA 的状态集的子集。 这是一种类似空间换时间的方法，假设NFA 的状态个数为n ，则DFA 的状态个数为2n （近似），但是DFA 在识别一个长度为m 的字符串时，只需要m 次状态移动，设字母表共有k 个字符，则NFA 可能需要k+k 2+...+k m 次状态转移，形成一个深度为m ，宽度为k 的搜索树。 定理4.1 对于任何一个NFA M 接受的语言L ，都存在一个DFA M 接受。 证明：设NFA M={Q, ∑, q 0, A, δ}，则构造DFA M1={Q 1, ∑, q 1, A 1, δ1}如下： Q 1=2Q q 1={q 0} δ1(q, a)= ),(a q q p δ?∈ A 1={q ∈Q 1 | q ?A ≠φ} 最后一点揭示了NFA 接受字符串x ，只需要存在一条转移路径最终到达接受状态就可以了，不需要所有的转移路径都到达接受状态。为了证明NFA M 和DFA M 1接受同样的语言，只需证明下面一个事实，对任意的字符串x ， δ1*(q 1, x)= δ*(q 0, x) 注意此处δ1*和δ*定义的不同，δ1是DFA 的连续转移函数（参见定义3.3），δ是NFA 的连续转移函数（参见定义4.3），它将状态映射到状态集的子集。 证明：字符串x 存在递归定义，因此可以在x 上使用结构归纳法来证明。 1） 归纳基础，x=Λ，要证明δ1*(q 1, x)= δ*(q 0, x)。 δ1*(q 1, x) = δ1*(q 1, Λ) = q1 = {q 0} δ*(q 0, x) = δ*(q 0, Λ) = {q 0} 因此，归纳基础成立。 2） 归纳推理，任给x ，设δ1*(q 1, x)= δ*(q 0, x)，要证明δ1*(q 1, xa)= δ*(q 0, xa)。 δ1*(q 1, xa) = δ1(δ1*(q 1, x), a) = δ1(δ*(q 0, x), a) = ),() ,(*0a p y q p δδ ?∈ = δ*(q 0, xa) 归纳推理成立，证明完毕。 字符串x 被M 接受，当且仅当δ*(q 0, x)?A ≠φ，当且仅当δ1*(q 1, x)?A ≠φ，当且仅当δ1*(q 1, x)∈A 1，当且仅当x 被M 1接受。定理4.1的证明提供了一个消除NFA 非确定性的算法，我们用下面的例子说明这个算法。 例子4.3 给例子4.2给出的NFA 构造相应的DFA 。 分析：例子4.2给出的NFA 共有4个状态，因此相应的DFA 至多有16个状态，如果采用例子3.16的方法，只保留那些初始状态能够到达的状态，则状态数将大大减少。设相应的DFA M 1={Q 1, ∑, q 1, A 1, δ1}，其中q1={q0}。则从初始状态出发，逐步构造DFA 的状态和转移函数。 δ1({q0}, 0) = {q0} δ1({q0}, 1) = {q0, q1} ---新状态 δ1({q0, q1}, 0) = δ(q0, 0)?δ(q1, 0) = {q0}?{q2} = {q0, q2} ---新状态 δ1({q0, q1}, 1) = δ(q0, 1)?δ(q1, 1) = {q0, q1}?{q2} = {q0, q1, q2} ---新状态 δ1({q0, q2}, 0) = δ(q0, 0)?δ(q2, 0) = {q0}?{q3} = {q0, q3} ---新状态 δ1({q0, q2}, 1) = δ(q0, 1)?δ(q2, 1) = {q0, q1}?{q3} = {q0, q1, q3} ---新状态 δ1({q0, q1, q2}, 0) = ... δ1({q0, q1, q2}, 1) = ... ... 上面的过程可以用一个表来描述，这个表就是前面讲到的状态转移表。表中每一格对应上面的每一行计算式。 整个过程可以用一个算法（程序）来完成，多次迭代，直到没有新状态产生才停止。而且能够保证根据这种方法构造的DFA 是对应该NFA 的最少状态DFA 。参见图4-3。 问题：写出构造NFA 的相应DFA 的算法。 例子4.4 同样的方法可用来处理例子4.1b 中NFA ，计算得到的整个转移状态表如下： 如果用q0代替{q0}，p代替{q4}，r代替{q1, q2}，s代替φ，t代替{q0, q3}，u代替{q0, q4}，则得到图4-1a。 4.2 带空转移的非确定型有限自动机 为了简化正则表达式和有限自动机的接受语言能力相当的证明，本节进一步扩充自动机的定义。下面例子显示了这种扩充的作用。 例子4.5 构造正则表达式E=0*(01)*的相应的有限自动机。 分析：显然容易构造0*和(01)*的FA，分别如图4-4a和图4-4b所示。现在考虑如何利用这两个FA完成整个FA的构造，即如何构造两个FA的连接运算。图4-4c给出了一个NFA，将这两个FA组合起来，能够接受语言L(E)。考虑的关键是给图4-4b的初始状态的添加初始字符。我们知道每个独立FA隐含的初始字符是空字符Λ，为了消除这个Λ，图4-4c增加了一条从q0到q2的连接两个FA的转移箭头。 上述方法在两个FA间添加的一些转移箭头很不直观、很不明显，不是一种很规范、可形式化的方法。为了简化两个FA的连接运算，我们允许NFA有更多猜测下一步状态的自由，即状态q0可以在未接受任何字符的情况下转移到q1，如图4-4d所示。前面显示了N F A的一个优点是比接受同样的语言的DFA需要少得多的状态数和更简洁的转移函数表，现在进一步放松条件后，新的NFA可能需要更少的状态数和转移箭头。 问题：状态q0能否和状态q1合并？ 定义4.4 带空转移的N FA（记为NFA-Λ）是一个5元组M=（Q, ∑, q0, δ, A），其中Q和∑是非空有限集，q0∈Q，A?Q，转移函数定义为： δ: Qx(∑?{Λ})→2Q 类似NFA的定义（参见定义4.1），我们需要扩展定义连续转移函数δ，以便适用于NFA-Λ，它的基本思想是一致的，即δ*(q, x)表示的是字符串在NFA-Λ中从状态q出发合法流动，最终停止在的状态。现在需要扩充定义的概念是“字符串在NFA-Λ中的合法流动”，或称为“NFA-Λ合法地处理字符串”。图4-5所示的简单例子可以说明这个概念。我们在字符串01中插入空字符Λ，得到0ΛΛ1Λ=x，显然x能够被图4-5所示NFA-Λ接受。 C，实际使用中将带来组合爆炸，问题：在一个长度为n的字符串中插入Λ，可能的结果是2 n 不是可行的方法。 类似定义4.2a ，我们给出定义4.5a 。 定义4.5a （NFA-Λ的连续转移函数δ*的非递归定义）任给一个NFA-Λ M=（Q, ∑, q 0, δ, A ），p 和q 是属于Q 的任意两个状态，任给一个∑上的字符串x=a1a2...an ，如果存在一个整数m>=n ，序列b1, b2, ..., bm ∈∑?{Λ}满足b1b2...bm=x ，存在一组状态p=p0, p1, ..., pm=q ，对于每个1<=i<=m ，都有pi ∈δ(pi-1, bi)，则在字符串x 驱动下，M 的状态从p 转移到q 。 函数δ*(p, x)的值是所有在x 驱动下，从状态p 转移到的所有状态组成的集合。 例如图4-5中，字符串01可以驱动状态从q0转移到f ，字符串Λ可以驱动状态从r 到t ，或每个状态到自身。类似定义4.2b ，我们给出递归定义，仍然利用字符串前缀计算的结果来定义整个字符串计算的结果，值得注意的是，我们还需要扩充递归基础的定义。显然δ*(q, Λ)的结果不仅包含q ，还应该包含从q 出发经过Λ转移到达的其他状态。这里引入一个新的概念，空闭包（Λ-closure ，空转移闭包），表示从某个状态（或状态集）出发经过一次或多次空转移到达的所有状态组成的集合。 定义4.6 状态集的空闭包（Λ-closure of a set of states ），给定NFA-Λ M=（Q, ∑, q 0, δ, A ），S 是Q 的子集，空闭包Λ(S)递归定义如下： 1. S 中每个元素都是Λ(S)的元素； 2. 如果q 是Λ(S)的元素，则δ(q, Λ)中的每个元素都是Λ(S)的元素； 3. Λ(S)的元素只可能通过上面两步得到。 与大多数集合的递归定义不同的是，我们能够预先确定空闭包是一个有限集，因此可以将上面的递归定义转换成一个计算空闭包的算法（参见练习2.50）。规则1提供了初始值，规则2则提供了添加元素的方法，当Λ(S)不再增加时，则算法停止。 算法（计算Λ(S)），输入状态集S ，输出S 的空闭包，设为T 。 1. T=S 2. 循环，直到T 没有增加新元素 a) 循环，逐个检查T 中的元素q ， T=T ?δ(q, Λ)。 定义4.5b （NFA-Λ的连续转移函数δ*的递归定义）给定一个NFA-Λ M=（Q, ∑, q 0, δ, A ），连续转移函数δ*: Qx ∑*→2Q 定义如下： 1. δ*(q, Λ) = Λ({q}) 2. δ*(q, ya) = Λ( ),() ,(*a p y q p δδ∈?) 问题：对于DFA 和NFA 都有δ*(q, a)= δ(q, a)，但对于NFA-Λ，此式不成立。 对照定义4.2b ，就是在NFA 的连续转移函数计算的结果上，在进行一次空闭包计算。在识 别字符串的过程中，每读入一个字符，每次状态转移都要计算一次空闭包。字符串x 被NFA-Λ M 接受的判定条件与NFA 一致，当且仅当δ*(q, x)?A ≠φ。所有被M 接受的字符串组成被M 接受的语言，记为L(M)。 例子4.6 考虑图4.6所示的NFA-Λ，我们显示如何计算空闭包和连续转移函数。 分析： Λ({s}) = Λ({s, w}) = Λ({s, w, q0}) = Λ({s, w, q0, p, t}) = Λ({s, w, q0, p, t}) ---没有新元素加入，计算结束 现在计算δ*(q0, 010)，根据递归定义，需要计算δ*(q0, 01)、δ*(q0, 0)、δ*(q0, Λ)，这里我们从底向上计算这组函数。 δ*(q0, Λ) = Λ({q0}) = {q0, p, t} δ*(q0, 0) = Λ( )0,() ,(*0p q p δδΛ∈?) = Λ(δ(q0, 0)?δ(p, 0)?δ(t, 0)) = Λ(φ?{p}?{u}) = Λ({p, u}) = {p, u} δ*(q0, 01)= Λ( )1,() 0,(*0p q p δδ∈?) = Λ(δ(p, 1)?δ(u, 1)) = Λ({r}) = {r} δ*(q0, 010) = Λ( )0,() 01,(*0p q p δδ∈?) = Λ(δ(r, 0)) = Λ({s}) = {s, w, q0, p, t} 可见由于，δ*(q0, 010)的结果含有w ，w 也是A 的元素，因此字符串010被图4-6所示的NFA-Λ接受。另外，010的同等字符串是Λ010Λ，容易发现存在状态序列q0, p, p, r, s, w 接受字符串Λ010Λ。 显然连续转移函数的定义提供了一种高效的算法来判定字符串是否被NFA-Λ接受，如果采用插入空字符，然后借用NFA 的连续转移函数的计算方法，其时间复杂度为指数级。上述方法实际上是一种dynamic programming ，Viterbi 算法。 问题1：写出计算NFA-Λ的连续转移函数的算法。 问题2：上述方法判定字符串是否被NFA-Λ接受，它能否回答判定中隐含插入的空字符位置？或判定中哪一步用到了空转移？比如能否知道010，在第一步和最后步用到了空转移？ 问题3：NFA-Λ可用于模糊查询，或两个字符串的模糊匹配，探寻如何在短的字符串中插入空字符，使得与长字符串达到最大匹配？ 在4.1节我们说明了NFA 接受语言的能力与DFA 相当，现在我们要说明NFA-Λ接受语言的能力与NFA 相当，即每个NFA-Λ能够找到一个接受能力相当的NFA 。 定理4.2 对于任何一个NFA-Λ M=接受的语言L ，都存在一个NFA M 接受。（与定理4.1对比） 证明：设NFA-Λ M={Q, ∑, q 0, A, δ}，要构造NFA M1={Q 1, ∑, q 1, A 1, δ1}。 在定理4.1（为NFA 构造相当的DFA ）的证明中，我们通过重新定义状态集，从而消除了非确定性。NFA-Λ中的空转移也是一种非确定性，例如如果一个NFA-Λ中存在： δ(p, 0)=q δ(q, Λ)=r 则状态p 在输入字符0时，有两个转移状态q 和r 。因此可以用类似δ(p, 0)=r 的式子代替δ(q, Λ)=r ，达到消除Λ的目的。显然凡是Λ(q)中的状态都可类似处理，即通过给空闭包中的每个状态添加转移箭头，就可以删除空转移。我们需要做的工作仅仅是消除一种特殊的非确定性情况。通用的方法如下。 Q1=Q q1=q0 我们利用空闭包实现NFA 的转移函数的构造。对于每个字符a ，至多插入两个空字符（非连续的空字符，因为连续的空字符相当于一个空字符），写成Λa Λ，因此在NFA-Λ中可能一个字符的转移至多两次涉及空闭包。 δ1(q, a) = Λ( ),(}) ({a p q p δΛ∈?) 由于 δ*(q, a) = δ*(q, Λa) = Λ(),() ,(*a p q p δδΛ∈?) = Λ( ),(}) ({a p q p δΛ∈?) 因此可以简写成 δ1(q, a) = δ*(q, a) ?? ?≠?Λ?=否则 如果A A q q A A φ})({}{001 我们这样定义的目的是：对任意的状态q 和字符串x ，δ1*(q, x)= δ*(q, x)都成立。我们发现一个特例，当x=Λ时，除非我们重新构造Q1，否则无论怎么构造δ1，都难以保证上式成立。所幸的是，对任意非空字符串x ，上式成立。因此仅仅对A 稍作修改，构造的A 1，就能保证正确识别空串这个特例。 现在对字符串x 实施结构归纳法来证明δ1*(q, x)= δ*(q, x)成立。 1. 归纳基础，x=a 单个字符 δ1*(q, a) = δ1(q, a) [δ1*是NFA 的转移函数]= δ*(q, a) 2. 归纳推理，设δ1*(q, y)= δ*(q, y)， δ1*(q, ya) = ),(1) ,(*1a p y q p δδ∈? = ),(1) ,(*a p y q p δδ∈? = ),(*) ,(* a p y q p δδ∈? 而δ*(q, ya) = Λ( ),() ,(*a p y q p δδ∈? )，因此需要证明 ),(*) ,(*a p y q p δδ∈? = Λ(),() ,(*a p y q p δδ∈?) ),(*),(* a p y q p δδ∈? = ?? ? ???Λ?Λ∈∈),(})({),(* a r p r y q p δδ = ? ?? ????? ????ΛΛ∈∈),(}) ({),(*a r p r y q p δδ ---空闭包可移到外面 = ??? ? ???? ????Λ∈∈),(}{),(*a r p r y q p δδ ---δ*(q, y)已经计算了空闭包， 因此可去掉一层空闭包。 = ? ? ? ???Λ∈),(),(*a p y q p δδ 现在我们证明构造NFA M1接受NFA-Λ M 相同的语言，分两种情况讨论： 1. M 中Λ({q0})?A ≠φ，此时A1=A ?{q0}，对判定的字符串x 分两种情况讨论 a) x=Λ δ*(q0, Λ)=Λ({q0})，而Λ({q0})?A ≠φ，被M 接受 δ *(q0, Λ)=δ (q0, Λ)={q0}，而{q0}?A1={q0}≠φ，被M1接受 因此Λ同时被M 和M1接受。 b) x ≠Λ δ *(q0, x )=δ*(q0, x )=B 要证明B ?A ≠φ当且仅当B ?A1≠φ。分两种情况： i. q0∈B ，则 Λ({q0})?B ，由于 Λ({q0})?A ≠φ，因此 B ?A ≠φ，x 被M 接受 另外，A1=A ?{q0}，因此 B ?A1≠φ，x 被M1接受 x 被M 和M1同时接受。 ii. q0?B ，则 B ?A= B ?(A ?{q0})= B ?A1，因此 x 要么同时被M 和M1接受，要么同时被M 和M1拒绝。 2.M中Λ({q0})?A=φ，此时A1=A，对判定的字符串x分两种情况讨论 a)x=Λ δ*(q0, Λ)=Λ({q0})，而Λ({q0})?A=φ，被M拒绝； δ *(q0, Λ)=δ (q0, Λ)={q0}，因为Λ({q0})?A=φ，则{q0}?A=φ，A1=A，因此 {q0}?A1=φ，被M1拒绝。 Λ同时被M和M1拒绝。 b)x≠Λ δ *(q0, x)=δ*(q0, x)=B，由于A1=A 因此B?A≠φ当且仅当B?A1≠φ，即x要么同时被M和M1接受，要么同时被拒绝。 上面讨论证明，任意一个字符串x，要么同时被M和M1接受，要么同时被拒绝。因此M 和M1接受同样的语言。定理4.2证明完毕。 问题1：子集构造法能否类似定理4.1那样构造出相当的NFA？ 问题2：直接从NFA-Λ构造DFA的算法？ NFA是DFA的更通用的模型，NFA-Λ是NFA的更通用模型，即我们可以说DFA是NFA 的特殊情况，NFA是NFA-Λ的特殊情况。 定理4.1和定理4.2的结论可以用下面的定理4.3来总结。 定理4.3 对于字母表∑上的任意语言L，下面三个命题是相当的 1.L可以被FA接受（此处FA就是DFA） 2.L可以被NFA接受 3.L可以被NFA-Λ接受 证明：根据定理4.1，2可以导出1；根据定理4.2，3可以导出2，现在只要证明1可以导出3。设L是FA M=(Q, ∑, q0, A, δ)接受的语言，构造接受L的NFA-Λ M1=(Q, ∑, q0, A, δ1)。仅仅需要重新定义转移函数，δ1: Q?(∑?{Λ})→2Q， δ1(q, Λ) = φ δ1(q, a) = {δ(q, a)} 容易证明M1与M接受相同的语言。 正如定理4.1，定理4.2的证明提供了一个消除NFA-Λ中空转移的算法，下面用两个例子来说明这个算法。这些例子也可用来作为消除非确定性的练习。 例子4.7 图4-7a给出了一个NFA-Λ M，它接受的语言是0*(01)*0*，下面表显示了M的转移函数和连续转移函数δ*(q, 0)和δ*(q, 1)的计算结果，这些结果可以用来构造相应的NFA M1。 M=({A, B, C, D}, {0, 1}, A, {D}, δ) 由于Λ({A})?{D}≠φ，因此， M1=({A, B, C, D}, {0, 1}, A, {A, D}, δ1)，δ1定义见上表。对图4-7a删除空转移，添加新转移，得到图4-7b，它表示的是相应的NFA。可以进一步消除NFA中的不确定性，得到相当的FA，如图4-7c所示。 例子4.8 图4-8a给出了一个NFA-Λ M，它接受的语言是0*((01)*1+1*0)，下标显示了它的转移函数和相当NFA的转移函数。 根据上表得到的NFA如图4-8b所示，注意初始状态A不是接受状态，因为Λ({A})中没有接受状态。相当的FA如图4-8c所示。 4.3 Kleene定理 本章的前两节提供了证明定理3.1的数学工具，定理3.1称为Kleene定理，我们将其中的充分必要条件分成两部分来证明。 定理4.4 （Kleene定理第一部分）任何一个正则语言都存在一个有限自动机接受。 证明：根据定理4.3，我们只需要证明存在一个带空转移的非确定型有限自动机（NFA-Λ）接受这个正则表达式表示的语言。由于正则语言存在一个递归定义，而要证明的是正则语言的一个性质，因此很适合使用结构归纳法。先构造接受三种最基本的正则语言的NFA-Λ，然后构造接受三种正则语言运算的NFA-Λ。 1.归纳基础，根据定义3.1，三种最基本的正则语言分别是：φ、{Λ}和{a}，a是字母表∑ 上的任意一个字符。参见图4-9。 2.归纳推理，证明在正则语言的三种运算下保持性质，分别为这三种运算构造有限自动 机。设接受语言L1和L2的NFA-Λ分别是： M1=(Q1, ∑, q1, A1, δ1) M2=(Q2, ∑, q2, A2, δ2) 不妨设Q1?Q2=φ（如果必要，可以更改状态名字），现在分别构造接受L 1?L 2、L 1L 2和L 1*的NFA-Λ M u 、M c 和M k 。 M u =(Q u , ∑, q u , A u , δu )，其中 q u 是既不属于Q1，也不属于Q2的新状态； Q u =Q1?Q2?{q u }； A u =A1?A2 ???? ???∈∈Λ≠∧=Λ=∧==21 2121) ,(),(},{),(Q q Q q a q q a q q a q a q q q a q u u u δδφδ 参见图4-10a ，增加了一个新状态，和从新状态到M1和M2的初始状态的空转移，完 成了一个分叉的构造。现在证明M u 接受的语言是L1?L 2。一方面，任给一个字符串x ∈L1?L 2，则x ∈L1或x ∈L2，不妨设x ∈L1，则M1接受x ，即存在M1的一组状态，p1=q1, p2, ..., pn ∈A1，接受x ，由于从q u 到q1是空转移，因此存在Mu 的一组状态，qu, p1=q1, p2, ..., pn ∈Au ，接受x 。另一方面，任给一个Mu 接受的字符串x ，即存在Mu 的一组状态，qu, p1, p2, ..., pn ∈Au ，接受x ，由于从qu 只有两个空转移到q1或q2，不妨设p1=q1，Q1?Q2=φ，因此p1, p2, ..., pn 都在M1中，且pn ∈A1，因此存在M1的一组状态p1, p2, ..., pn ，接受x ，即x ∈L1?L 2。 Mc=(Q c , ∑, q c , A c , δc )，其中 Q c =Q1?Q2； qc=q1; Ac=A2; ???????∈?∧∈Λ=∧∈Λ≠∧∈?=2111 121211) ,(),(}{),() ,(),(Q q A q Q q a A q a A q a q a q q a q a q a q c δδδδδ ---此为书上式子 或 ?? ? ??∈∈Λ=∧∈?Λ=2112121),(),(}{),(),(Q q Q q a A q a q a q q q a q c δδδδ ---此为我的简化 参见图4-10b ，增加了从M1的接收状态到M2的初始状态的空转移。设M1接受的字 符串是x1，M2接受的字符串x2，则Mc 接受的字符串是x1Λx2=x1x2。 M k =(Q k , ∑, q k , A k , δk )，其中 qk 是不属于Q1的新状态； Qk=Q1?{qk}； Ak={qk}； ?? ? ??Λ≠∧∈∨?∧∈Λ=∧∈Λ=∧=?Λ=)()(),(}{),(}{),(1111111a A q A q Q q a A q a q q a q q q q a q k k k δδδ 参见图4-10c ，增加了一个新状态作为初始状态和唯一的接受状态，增加了从新状态到 原初始状态的空转移，从原接收状态到新状态的空转移，完成了一个环的构造。设被M1接受的一组字符串是x1, x2, ..., xm ，则字符串(Λx1Λ)(Λx2Λ)...(Λxm Λ)=x1x2...xm 能够被Mk 接受。 因此在3种运算下，保持了正则语言能够被NFA-Λ接受的性质。证明完毕。 问题1：构造方法与定理3.4的区别。 问题2：构造对应多个语言的合并和连接的自动机。 以上证明提供了从正则表达式构造NFA-Λ的方法，这种方法构造的自动机不一定是最简的。 例子4.9 构造正则表达式r=(00+1)*(10)*的NFA-Λ。 分析：构成r 的最基本的两个正则语言是{0}和{1}，它们对应的NFA-Λ如图4-11a 所示。然后构造{00}和{10}的NFA-Λ，如图4-11b 。图4-11c 显示了{00+1}的NFA-Λ，图4-11d 对应{00+1}*，图4-11e 对应(10)*，最终得到的NFA-Λ如图4-11f 所示。 严格按照定理4.4的算法构造的NFA-Λ往往有许多冗余的状态，图4-12给出了相应于图4-11的简化的NFA-Λ（参见练习 4.35~4.37，简化NFA-Λ应该很小心）。尽管目前我们还没有简化NFA-Λ的形式化方法，但根据前两节的定理，我们知道如何将NFA-Λ转换成DFA ，第5章将讲述化简DFA 的形式化方法，因此最终存在一个简化自动机的方法。 定理4.5（Kleene 定理第二部分）任何一个有限自动机接受的语言都是正则语言。 证明：设L 是字母表∑上非空转移的确定型有限自动机DFA M=(Q, ∑, q0, A, δ)接受的语言，即L={x ∈∑* | δ*(q0, x)∈A}=}),(*|*{0q x q x A q =∑∈?∈δ。根据正则表达式定义，一组正则语言 的并集仍然是正则语言，我们只需要证明下面一组语言是正则语言： L(q0, q) = {x ∈∑* | δ*(q0, x)=q ∧q ∈A}， 更一般地，我们证明对M 的任意两个状态p 和q ，语言L(p, q) = {x ∈∑* | δ*(p, x)=q }是正则语言。 很自然的证明方法是归纳法，比如根据L(p, q)中字符串的长度，或被接受的字符串从状态p 到q 所经过的状态数。这些方法也许不是很容易想到的有效方法，由于L(p, q)可以是无限集，则其中的字符串可以任意长，而且我们要证明的是整个语言的性质，而不是单个字符串的性质。因此根据经过的状态数是一种更好的归纳法。 现在我们假设M 共有n 个状态，并对每个状态编号，号码从1开始，到n 结束。我们给出概念“经过状态s 的路径”的形式化定义。给定一个字符串x ，如果存在两个非空的字符串y 和z ，满足： x=yz ，δ*(p, y)=s ，δ*(s, z)=q 则称x 代表了一条从p 到q ，经过s 的路径。注意根据我们的定义，起点和终点状态不能称为经过的状态，如上例，可以说经过了s ，但不能说经过了p 和q 。 对于整数j>=0，L(p, q, j)表示所有从p 到q ，且经过状态的编号小于等于j 的字符串组成的集合。由于M 中状态的最大编号为n ，显然L(p, q)中的字符串不会经过编号大于n 的状态，因此L(p, q, n)=L(p, q)。 现在问题变成证明L(p, q, n)是正则语言。我们可以用数学归纳法证明对任意的0<=j<=n ，L(p, q, j)都是正则语言。当然事实上，既然对任意的j>=n ，L(p, q, j)=L(p, q, n)=L(p, q)，我们要证明的命题可以更通用，即对任意的j>=0，L(p, q, j)都是正则语言。 1. 归纳基础，j=0，证明L(p, q, 0)是正则语言。 既然M 中状态的最小编号是1，L(p, q, 0)中的字符串表示的路径只能是从p 直接到q ，如果p ≠q ，则字符串是单个字母；如果p=q ，还应包括空字符。空字符和单个字母都是正则语言，因此L(p, q, 0)是正则语言。 2. 归纳推理，设对每个k>=0，L(p, q, k)都是正则语言，证明L(p, q, k+1)也是正则语言。 由于k>=n 时，L(p, q, k)= L(p, q, k+1)，此处仅证明k z ∈L(k+1, k+1, k)* ---此处有起点和终点相同，存在循环，即Kleene*运算 w ∈L(k+1, q, k) 因此，第二类字符串组成的语言是， L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k)，则 L(p, q, k+1)= L(p, q, k)+ L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k) 根据正则语言的定义，正则语言的合并、连接和Kleene*运算后的结果仍然是正则语言。因此L(p, q, k+1)是正则语言，证明完毕。 定理4.5的证明提供了一个从有限自动机（确定型非空转移的有限自动机）导出相应正则表达式的方法，总结如下： ? ? ?=≠Λ?=∑∈=∑∈=q p q p q a p a q a p a q p L }{}),(|{} ),(|{)0,,(δδ L(p, q, k+1)= L(p, q, k)+ L(p, k+1, k) L(k+1, k+1, k)* L(k+1, q, k) L(p, q)=L(p, q, n) L=),(0q q L A q ∈? 例子4.10 图4-14给出了一个FA ，求它对应的正则表达式。 分析：我们用下表显示对应语言L(p, q, j)的正则表达式r(p, q, j)，0= 上表在计算中，用到了一些简化方法，如： r(1, 3, 1)=r(1, 3, 0) + r(1, 1, 0)r(1, 1, 0)*r(1, 3, 0)= φ 其中r(1, 3, 0)=φ，而空集与其他任何集合的连接运算结果仍是空集。 r(3, 2, 1) = r(3, 2, 0)+r(3, 1, 0)r(1,1,0)*r(1,2,0) = b+a(a+Λ)*b = Λb+a+b = a*b r(1,1,2) = r(1,1,1)+r(1,2,1)r(2,2,1)*r(2,1,1) = a* + a*b(a+b)*a+ = a* + a*(ba+)*ba+ = a* + a*(ba+)+ = a*(ba+)* r(3,2,3) = r(3,2,1)+r(3,2,1)r(2,2,1)*r(2,2,1) = a*b + a*b(a+b)*(Λ+a+b) = a*b + a*b(a+b)* = a*b(a+b)* 接受状态是1和2，因此要求的正则表达式r=r(1,1,3)+r(1,2,3)。 r(1,1,3) = r(1,1,2)+r(1,3,2)r(3,3,2)*r(3,1,2) = a*(ba+)*+a*(ba+)*bb(Λ+a*b(a+b)*b)*(a++a*(ba+)+) = a*(ba+)*+a*(ba+)*bb(a*(ba+)*bb)*(a++a*(ba+)+) = a*(ba+)*+(a*(ba+)*bb)+(a++a*(ba+)+) r(1,2,3) = r(1,2,2)+r(1,3,2)r(3,3,2)*r(3,2,2) = a*(ba+)*b+a*(ba+)*bb(a*b(a+b)*b)*a*b(a+b)* = a*(ba+)*b+a*(ba+)*bb(a*(ba+)*bb)*a*b(a+b)* = a*(ba+)*b+(a*(ba+)*bb)+a*(ba+)*b = (a*(ba+)*bb)* a*(ba+)*b r = r(1,1,3)+r(1,2,3) = a*(ba+)*+(a*(ba+)*bb)+(a++a*(ba+)+)+(a*(ba+)*bb)*a*(ba+)*b = a*(ba+)*+(a*(ba+)*bb)*(a*(ba+)*bb(a++a*(ba+)+)+a*(ba+)*b = a*(ba+)*+(a*(ba+)*bb)*a*(ba+)*(bba++bba*(ba+)++b) 尽管希望能够进一步简化，但没有一个好的形式化方法。 问题：状态与字符串的关系。给定一个FA，字符串与状态序列（或称路径）是一一对应关系，容易找到从字符串导出状态的方法，从状态导出字符串的方法。如果是NFA呢？如果是NFA- 呢？ 计算机组成原理简答题 第四章 1、存储器的层次结构主要体现在什么地方？为什么要分这些层次？计算机如何管理这些层次？ 答：存储器的层次结构主要体现在Cache-主存和主存-辅存这两个存储层次上。 Cache-主存层次在存储系统中主要对CPU访存起加速作用，即从整体运行的效果分析，CPU 访存速度加快，接近于Cache的速度，而寻址空间和位价却接近于主存。 主存-辅存层次在存储系统中主要起扩容作用，即从程序员的角度看，他所使用的存储器其容量和位价接近于辅存，而速度接近于主存。 综合上述两个存储层次的作用，从整个存储系统来看，就达到了速度快、容量大、位价低的优化效果。 主存与CACHE之间的信息调度功能全部由硬件自动完成。而主存与辅存层次的调度目前广泛采用虚拟存储技术实现，即将主存与辅存的一部分通过软硬结合的技术组成虚拟存储器，程序员可使用这个比主存实际空间（物理地址空间）大得多的虚拟地址空间（逻辑地址空间）编程，当程序运行时，再由软、硬件自动配合完成虚拟地址空间与主存实际物理空间的转换。因此，这两个层次上的调度或转换操作对于程序员来说都是透明的。 2. 说明存取周期和存取时间的区别。 解：存取周期和存取时间的主要区别是：存取时间仅为完成一次操作的时间，而存取周期不仅包含操作时间，还包含操作后线路的恢复时间。即： 存取周期 = 存取时间 + 恢复时间 3. 什么叫刷新？为什么要刷新？说明刷新有几种方法。 解：刷新：对DRAM定期进行的全部重写过程； 刷新原因：因电容泄漏而引起的DRAM所存信息的衰减需要及时补充，因此安排了定期刷新操作； 常用的刷新方法有三种：集中式、分散式、异步式。 集中式：在最大刷新间隔时间内，集中安排一段时间进行刷新，存在CPU访存死时间。 分散式：在每个读/写周期之后插入一个刷新周期，无CPU访存死时间。 异步式：是集中式和分散式的折衷。 4. 半导体存储器芯片的译码驱动方式有几种？ 解：半导体存储器芯片的译码驱动方式有两种：线选法和重合法。 线选法：地址译码信号只选中同一个字的所有位，结构简单，费器材； 重合法：地址分行、列两部分译码，行、列译码线的交叉点即为所选单元。这种方法通过行、列译码信号的重合来选址，也称矩阵译码。可大大节省器材用量，是最常用的译码驱动方式。 5. 什么是“程序访问的局部性”？存储系统中哪一级采用了程序访问的局部性原理？ 解：程序运行的局部性原理指：在一小段时间内，最近被访问过的程序和数据很可能再次被访问；在空间上，这些被访问的程序和数据往往集中在一小片存储区；在访问顺序上，指令顺序执行比转移执行的可能性大 (大约 5:1 )。存储系统中Cache—主存层次采用了程序访问的局部性原理。 6. Cache做在CPU芯片内有什么好处？将指令Cache和数据Cache分开又有什么好处？ 答：Cache做在CPU芯片内主要有下面几个好处： 第二讲 Peano 定理（解的存在性定理）的应用 （主讲：范进军） 例 利用 Peano 存在定理证明如下隐函数存在定理： 设D 是空间 n R R ′ 内的一个区域，函数 :?(,)(,) n F D R t x F t x ?? 是连续可微的， 而且满足条件 00 (,)0 F t x = 和 00 det{(,)}0, x F t x 1 其中初值 00 (,) t x D ? 。 则方程 (,)0 F t x = 确定一个满足条件 00 () x t x = 的隐函数 () x x t = 。 证明 由条件 00 det{(,)}0 x F t x 1 （其中 00 (,) t x D ? ）知，存在充分小的矩形区域 { } 00 (,):||,||||(,0) n Q t x R R t t a x x b a b =?′-￡-￡> , 使得当(,) t x Q ? 时矩阵 00 (,) x F t x 是可逆的. 因此函数 1 (,){(,)}(,) x t f t x F t x F t x - =- 在区域Q 上是连续的。 根据 Peano 定理知，初值问题 00 (,), () dx f t x dt x t x ì = ? í ? = ? 存在一个局部解 00 (),[,](0) x t t t h t h h j =?-+> 。 从而 1 () {(,())}(,()) x t d t F t t F t t dt j j j - =- ， 0 || t t h -￡ 。 它等价于 () (,())(,()) 0 t x d t F t t F t t dt j j j += ， 0 || t t h -￡ , 即 (,()) 0 dF t t dt j = ， 0 || t t h -￡ 。 存储程序计算机：冯·诺依曼结构计算机。其基本点是指令驱动。程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作。 兼容机：由不同公司厂家生产的具有相同系统结构的计算机。 系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的JSJ 软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。 并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠，就存在并行性。它包括同时性与并发性两种含义。 寻址方式：指令系统中如何形成所要访问的数据的地址。一般来说，寻址方式可以指明指令中的操作数是一个常数、一个寄存器操作数或者是一个存储器操作数。 流水线技术：将一个重复的时序过程，分解成为若干个子过程，而每一个子过程都可有效地在其专用功能段上与其它子过程同时执行。 Victim Cache：位于Cache和存储器之间的又一级Cache，容量小，采用全相联策略。用于存放由于失效而被丢弃（替换）的那些块。每当失效发生时，在访问下一级存储器之前，先检查Victim Cache中是否含有所需块。 机群：由多台同构或异构的独立计算机通过高性能网络或局域网互连在一起，协同完成特定的并行计算任务的并行计算机网络。 Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。 程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。包括时间局部性和空间局部性。 多处理机系统：两个或两个以上CPU通过高速互联网连接，在统一的OS管理下实现指令以上级并行的计算机系统叫处理机系统 并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统，它是将多个处理器通过网络以一定的连接方式有序地组织起来。结构相关：当硬件资源满足不了同时重叠执行的指令的要求，而发生资源冲突时，就产生了结构相关。 数据相关：当一条指令需要用到前面某条指令的结果，而这些指令都在流水线中重叠执行时，就称为数据相关。 控制相关：当流水线遇到分支指令和其他能够改变PC值的指令时，就会发生控制相关。 数据表示：硬件结构能够识别、指令系统可以直接调用的那些数据结构。 互连网络：一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。在拓扑上，互连网络是输入结点到输出结点之间的一组互连或映象。存储器的三个主要指标：速度，容量，价格 CPU 中存储操作数的存储单元：堆栈型机器，累加器型机器，通用寄存器型机器 对指令系统的基本要求：完整性，规整性，正交性，高效性，兼容性 解决流水线瓶颈问题：细分瓶颈段，重复设置瓶颈段 通道：字节多路通道，数组多路通道，选择通道 输入出系统：输入输出设备，集中式共享存储器设备，输入输出操作有关的分布式存储器设备云计算特点：可定制，弹性，虚拟化 机群系统特点：系统开发周期短，可靠性高，可扩放性强，性能价格比高，用户编程方便。 总线监听协议解决cache一致性问题衡量流水线性能主要指标：吞吐率，加速比，效率 减少流水线分支延迟的静态方法：冻结或排空流水线，预测分支失败，预测分支成功，延迟分支 8-1考虑并回答下面的问题： （a ）在确定非线性元件的描述函数时，要求非线性元件不是时间的函数，并要求有斜对称性，这是为什么 （b ）什么样的非线性元件是无记忆的什么样的非线性元件是有记忆的它们的描述函数各有什么特点 （c ）线性元件的传递函数与非线性元件的描述函数，有什么是相同的有什么是不同的线性元件可以有描述函数吗非线性元件可以有传递函数吗 （d ）非线性系统线性部分的频率特性曲线与非线性元件的负倒描述函数曲线相交时，系统一定能够产生稳定的自激振荡吗 8-2设非线性元件的输入、输出特性为 35135()()()()y t b x t b x t b x t =++ 证明该非线性元件的描述函数为 2413535 ()48 N A b b A b A =++ 式中A 为非线性元件输入正弦信号的幅值。 8-3某非线性元件的输入、输出特性如图所示。 图 习题8-3图 （a ）试求非线性元件的描述函数。 （b ）将图所示非线性元件表示为有死区继电器和有死区放大器的并联，用非线性元件并联描述函数的求法求它的描述函数，并与（a ）中的结果相比较。 8-4滞环继电特性如图（a ）所示，证明它的描述函数可以表示为 4()arcsin M a N A A A π??= ∠ ??? 且负倒描述函数的虚部为常值，负倒描述函数曲线如图（b ）所示。 （a ） （b ） 图 习题8-4图 8-5大对数控制系统的控制器后面都带有限幅器。对图（a ）所示PI 调节器输出带有限幅器的情况，在输入信号发生大的阶跃变化时，系统输出将出现比较大的退饱和超调。所谓退饱和超调是指，在大的误差信号e 作用下，PI 调节器的输出将很快将到达饱和值，经限幅器限幅后控制作用u 维持在最大值max u 。在max u 的作用下，输出c 逐渐增大，误差e 逐渐减小，但只要误差未改变符号，PI 调节器的积分项就将继续增大，0e =时积分项的值一般要远大于限幅器的限幅值max u 。当输出超调以后，误差的符号变负，调节器积分项的值开始下降，但在一段时间内仍将维持在很大的数值上，因此会导致很大的超调。 为降低或消除上述系统的退饱和超调，可以有图（b ）或图（c ）所示的限幅器设计方案，可以保证调节器的积分项被限制在限幅值以内，试分别说明它们的工作原理。 （a ） （b ） ?函数零点存在性定理： 一般地，如果函数y=f(x)在区间[a，b]上的图象是连续不断的一条曲线，并且有f(a)．f(b) 第1章计算机系统结构的基本概念 1.1 解释下列术语 层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。这些层次依次为：微程序机器级，传统机器语言机器级，汇编语言机器级，高级语言机器级，应用语言机器级等。 虚拟机：用软件实现的机器。 翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。 解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。 计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。 透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。 计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。 计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。 系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。 Amdahl定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高，受限于该部件的执行时间占总执行时间的百分比。 程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的，而是相对地簇聚。包括时间局部性和空间局部性。 CPI：每条指令执行的平均时钟周期数。 测试程序套件：由各种不同的真实应用程序构成的一组测试程序，用来测试计算机在各个方面的处理性能。 存储程序计算机：冯·诺依曼结构计算机。其基本点是指令驱动。程序预先存放在计算机存储器中，机器一旦启动，就能按照程序指定的逻辑顺序执行这些程序，自动完成由程序所描述的处理工作。 系列机：由同一厂家生产的具有相同系统结构、但具有不同组成和实现的一系列不同型号的计算机。 软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。 向上（下）兼容：按某档计算机编制的程序，不加修改就能运行于比它高（低）档的计算机。 向后（前）兼容：按某个时期投入市场的某种型号计算机编制的程序，不加修改地就能 非线性控制理论和方法 姓名：引言 人类认识客观世界和改造世界的历史进程，总是由低级到高级，由简单到复杂，由表及里的纵深发展过程。在控制领域方面也是一样，最先研究的控制系统都是线性的。例如，瓦特蒸汽机调节器、液面高度的调节等。这是由于受到人类对自然现象认识的客观水平和解决实际问题的能力的限制，因为对线性系统的物理描述和数学求解是比较容易实现的事情，而且已经形成了一套完善的线性理论和分析研究方法。但是，现实生活中，大多数的系统都是非线性的。非线性特性千差万别，目前还没一套可行的通用方法，而且每种方法只能针对某一类问题有效，不能普遍适用。所以，可以这么说，我们对非线性控制系统的认识和处理，基本上还是处于初级阶段。另外，从我们对控制系统的精度要求来看，用线性系统理论来处理目前绝大多数工程技术问题，在一定范围内都可以得到满意的结果。因此，一个真实系统的非线性因素常常被我们所忽略了，或者被用各种线性关系所代替了。这就是线性系统理论发展迅速并趋于完善，而非线性系统理论长期得不到重视和发展的主要原因。控制理论的发展目前面临着一系列严重的挑战, 其中最明显的挑战来自大范围运动的非线性复杂系统, 同时, 现代非线性科学所揭示的分叉、混沌、奇异吸引子等, 无法用线性系统理论来解释, 呼唤着非线性控制理论和应用的突破。 1.传统的非线性研究方法及其局限性 传统的非线性研究是以死区、饱和、间隙、摩擦和继电特性等基本的、特殊的非线性因素为研究对象的, 主要方法是相平面法和描述函数法。相平面法是Poincare于1885年首先提出的一种求解常微分方程的图解方法。通过在相平面上绘制相轨迹, 可以求出微分方程在任何初始条件下的解。它是时域分析法在相空间的推广应用, 但仅适用于一、二阶系统。描述函数法是 P. J.Daniel于1940 根的存在性定理：如果)(x f 在闭区间[a,b]上连续 0)(,,0)()(=∈<ξξf b a b f a f ）使得（则存在。 证明 利用构造法的思想，将)(x f 的零点范围逐步缩小。先将[a,b]二等分为],2[],2, [b b a b a a ++，如果0)2 (=+b a f 。则定理获证。如果0)2(≠+b a f ，则f(a)和f(b)中必然有一个与)2 (b a f +异号，记这个小区间为[11,b a ],它满足2-0)()(1111a b a b b f a f -=<且区间的长度。又将[11,b a ]二等分，考虑中点的函数值，要么为零，要么不为零。如果中点的函数值为零，则定理获证。如果中点的函数值不为零，那么必然可以选出一个小区间，使得f(x)在这个区间的端点值异号，记这个小区间为 ],[22b a ，它满足[a,b]?[11,b a ]],[22b a ?，0)()(2222 22<-=-a f b f a b a b 且。采用这样的方法一直进行下去，或者到有限步时，某个区间的中点的函数值为零，这样定理的结论成立。或者所有区间的中点的函数值不为零，那么我们就会得到一个无穷的区间序列{],[n n b a }，它满足:① [a,b]?[11,b a ]?????],[22b a ；②n n n a b a b 2-=-；③0)()( 计算机体系结构试题库 简答题（100题） 1．简述CISC结构计算机的缺点。 答： ●在CISC结构的指令系统中，各种指令的使用频率相差悬殊。据统计，有20％的指 令使用频率最大，占运行时间的80％。也就是说，有80％的指令在20％的运行时 间内才会用到。 ●CISC结构指令系统的复杂性带来了计算机体系结构的复杂性，这不仅增加了研制 时间和成本，而且还容易造成设计错误。 ●CISC结构指令系统的复杂性给VLSI设计增加了很大负担，不利于单片集成。 ●CISC结构的指令系统中，许多复杂指令需要很复杂的操作，因而运行速度慢。 ●在CISC结构的指令系统中，由于各条指令的功能不均衡性，不利于采用先进的计 算机体系结构技术（如流水技术）来提高系统的性能。 2．RISC结构计算机的设计原则。 答： A.选取使用频率最高的指令，并补充一些最有用的指令； B.每条指令的功能应尽可能简单，并在一个机器周期内完成； C.所有指令长度均相同； D.只有load和store操作指令才访问存储器，其它指令操作均在寄存器之间进行； E.以简单有效的方式支持高级语言。 3．影响现代微处理器主频提升的主要原因由哪些？ 答：线延迟、功耗。 4．指令集格式设计时，有哪三种设计方法？ 答：固定长度编码、可变长编和混合编码）三种设计方法。 5．简述存储程序计算机（冯·诺依曼结构）的特点。 答： （1）机器以运算器为中心。 （2）采用存储程序原理。 （3）存储器是按地址访问的、线性编址的空间。 （4）控制流由指令流产生。 （5）指令由操作码和地址码组成。 （6）数据以二进制编码表示，采用二进制运算。 6．在进行计算机系统设计时，一个设计者应该考虑哪些因素对设计的影响？ 答： 在进行计算机系统设计时，设计者应该考虑到如下三个方面因素的影响： ●技术的发展趋势； ●计算机使用的发展趋势； ●计算机价格的发展趋势。 7．简述程序翻译技术的特点。 答： 翻译技术是先把N+1级程序全部变换成N级程序后，再去执行新产生的N级程序，在执行过程中N+1级程序不再被访问。 8．简述程序解释技术的特点。 答： 解释技术是每当一条N+1级指令被译码后，就直接去执行一串等效的N级指令，然后再去取下一条N+1级的指令，依此重复进行。 9．经典体系结构的定义是什么？ 计算机体系结构是机器级程序员所看到的计算机的属性，即概念性结构与功能特性。10．“线延迟墙”指的是什么？ 第三章复习 一、名词解释： 1.RAM：随机访问存储器，能够快速方便的访问地址中的内容，访问的速度与存储位置无关。 2.ROM：只读存储器，一种只能读取数据不能写入数据的存储器。 3.SRAM：静态随机访问存储器，采用双稳态电路存储信息。 4.DRAM：动态随机访问存储器，利用电容电荷存储信息。 5.EDO DRAM：增强数据输出动态随机访问存储，采用快速页面访问模式并增加了一个数据锁存器以提高数据传输速率。 6.PROM：可编程的ROM，可以被用户编程一次。 7.EPROM：可擦写可编程的ROM，可以被用户编程多次。靠紫外线激发浮置栅上的电荷以达到擦除的目的。 8.EEPROM：电可擦写可编程的ROM，能够用电子的方法擦除其中的内容。 9.SDRAM：同步型动态随机访问存储器，在系统时钟控制下进行数据的读写。 10.快闪存储器：一种非挥发性存储器，与EEPROM类似，能够用电子的方法擦除其中的内容。 11.相联存储器：一种按内容访问的存储器，每个存储单元有匹配电路，可用于是cache中查找数据。 12.多体交叉存储器：由多个相互独立、容量相同的存储体构成的存储器，每个存储体独立工作，读写操作重叠进行。 13.访存局部性：CPU的一种存取特性，对存储空间的90%的访问局限于存储空间的10%的区域中，而另外10%的访问则分布在90%的区域中。 14.直接映象：cache的一种地址映象方式，一个主存块只能映象到cache中的唯一一个指定块。 15.全相联映象：cache的一种地址映象方式，一个主存块可映象到任何cache块。 16.组相联映象：cache的一种地址映象方式，将存储空间分成若干组，各组之间用直接映象，组内各块之间用全相联映象。 17.全写法（写直达法）：cache命中时的一种更新策略，写操作时将数据既写入cache又写入主存，但块变更时不需要将调出的块写回主存。 18.写回法：cache命中时的一种更新策略，写cache时不写主存，而当cache数据被替换出去时才写回主存。 19.层次化存储体系：把各种不同存储容量、不同访问速度、不同成本的存储器件按层次构成多层的存储器，并通过软硬件的管理将其组成统一的整体，使所存储的程序和数据按层次分布在各种存储器件中。 20.访问时间：从启动访问存储器操作到操作完成的时间。 21.访问周期时间：从一次访问存储的操作到操作完成后可启动下一次操作的时间。 22.带宽：存储器在连续访问时的数据吞吐率。 成若干页。 23.固件：固化在硬件中的固定不变的常用软件。 二、选择填空题：典型例题分析 ? ? 函数零点存在性定理： 一般地，如果函数y=f(x)在区间[a，b]上的图象是连续不断的一条曲线，并且有f(a)．f(b) 第1章 计算机系统结构的基本概念 试用实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系。 答：如在设计主存系统时，确定主存容量、编址方式、寻址范围等属于计算机系统结构。确定主存周期、逻辑上是否采用并行主存、逻辑设计等属于计算机组成。选择存储芯片类型、微组装技术、线路设计等属于计算机实现。 计算机组成是计算机系统结构的逻辑实现。计算机实现是计算机组成的物理实现。一种体系结构可以有多种组成。一种组成可以有多种实现。 计算机系统设计中经常使用的4个定量原理是什么？并说出它们的含义。 答：（1）以经常性事件为重点。在计算机系统的设计中，对经常发生的情况，赋予它优先的处理权和资源使用权，以得到更多的总体上的改进。（2）Amdahl 定律。加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中所占的重要性。（3）CPU 性能公式。执行一个程序所需的CPU 时间 = IC ×CPI ×时钟周期时间。（4）程序的局部性原理。程序在执行时所访问地址的分布不是随机的，而是相对地簇聚。 计算机系统中有三个部件可以改进，这三个部件的部件加速比为： 部件加速比1=30； 部件加速比2=20； 部件加速比3=10 （1） 如果部件1和部件2的可改进比例均为30%，那么当部件3的可改进比例为多少时，系统加速比才可以达到10？ （2） 如果三个部件的可改进比例分别为30%、30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？ 解：（1）在多个部件可改进情况下，Amdahl 定理的扩展： ∑∑+-= i i i n S F F S )1(1 已知S 1＝30，S 2＝20，S 3＝10，S n ＝10，F 1＝，F 2＝，得： ） （）（10/20/0.330/0.30.30.3-11 1033F F +++++= 得F 3＝，即部件3的可改进比例为36%。 （2）设系统改进前的执行时间为T ，则3个部件改进前的执行时间为：（++）T = ，不可改进部分的执行时间为。 已知3个部件改进后的加速比分别为S 1＝30，S 2＝20，S 3＝10，因此3个部件改进后的执行时间为： T T T T T n 045.010 2.020 3.0303.0'=++= 改进后整个系统的执行时间为：Tn = + = 那么系统中不可改进部分的执行时间在总执行时间中占的比例是： 82.0245.02.0=T T 假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示： 操作类型 程序中的数量 （百万条指令） 改进前的执行时间 （周期） 改进后的执行时间 （周期） 建设项目投资决策是选择和决定投资行动方案的过程，指对拟建项目的必要性 和可行性进行技术经济论证，对不同建设方案进行技术经 建设项目投资决策是选择和决定投资行动方案的过程，指对拟建项目的必要性 和可行性进行技术经济论证，对不同建设方案进行技术经济分析、比较及作出 判断和决定的过程。 1、投资决策阶段影响工程造价的因素建设项目投资决策阶段影响工程造价的因素主要有：项目建设规模、项目建设地点、项目建设标准、项目生产工艺和设 备方案等四个方面。 1.1项目的建设规模。要使建设项目达到一定的规模，并实现项目的投资的目的，就必须考察其合理的生产规模，并力求取得规模经济的收效。 1.1.1建设项目的生产规模。建设项目的生产规模指生产要素与产品在一个经 济实体中集中程度。通俗的讲也是“生产多少”的问题，往往以该建设项目的 年生产（完成）能力来表示。生产规模的大小，必将影响建设项目在生产工艺、设备选型、建设资源等方面的决策，进而影响投资规模的大小。生产规模过过 大或过小，均得不到较好的投资效益。比如冶金工业的炼铁，规模小，单位生 产能力的能耗就高，原料利用率较低，效益差；而规模过大，使得资源供给不足，生产能力不能得到有效发挥，或是产品供给超过需求，打乱了现有的供需 平衡，导致价格的下滑，对本项目的投资和原有市场均将产生巨大的损害。 1.1.2规模经济。规模经济，是指伴随生产规模扩大引起单位成本下降而带来 的经济效益。当项目单位产品的报酬为一定时，项目的经济效益与项目的生产 规模成正比，也即随着生产规模的扩大会出现单位成本下降和收益递增的现象。规模经济的客观存在对项目规模的合理选择有重大影响，可以充分利用规模经 济来合理确定和有效控制工程造价，提高项目的经济效益。合理确定项目的建 设规模，不仅要考虑项目内部各因素的之间的数量匹配、能力协调，还要使所 有生产力因素共同形成的经济实体在规模上大小适应，以合理确定和有效控制 工程造价。 1.2项目建设地点。建设地点选择包括建设地区和具体厂址的选择。它们之间 既相互联系又相互区别，是一种递进关系。建设地区的选择是指在几个不同地 区之间对拟建项目适宜建设在哪个区域范围的选择，厂址的选择是对项目具体 座落位置的选择。建设地区的选择对于该项目的建设工程造价和建成后的生产 成本，以及国民经济均有直接的影响。建设地区的合理与否，很大程度上决定 着拟建设项目的命运，影响着工程造价、建设工期和建设质量，甚至影响建设 项目投资目的的成功与否。因此，要根据国民经济发展的要求和市场需要以及 纳什均衡的存在性定理中的相关解释 教材（《经济博弈与应用》）p33，图2.1表明不动点是曲线()?f 与45o 线的交点。当函数()x f 定义在[]1,0∈x 区间上且因变量()x f y =的值域也为[]1,0区间时，如果()x f 是连续的，则必然存在不动点。 图2.1 [0,1]区间上的自变换函数的不动点 直接用来证明纳什存在性定理的不动点定理不是Brouwer 角谷静夫(Kakutani)不动点定理。 定义1 S 是凸的(Convex)当且仅当对任意的M M R y R x ∈∈,及满足1 ≤≤λ的λ，只要S x ∈和S y ∈，则有 ()S y x ∈-+λλ1 定义2 S 是闭的(Closed)当且仅当对每个收敛的序列()}{∞ =1j j x ，如果对每个 j 都有()S j x ∈，则有 ()S j x j ∈∞ →lim 定义3 R M 中的子集S 是开的(open)当且仅当它的补集R M /S 是闭的。 定义4 S 是有界的(bounded)当且仅当存在某个正数K 使得对S 中的每个元素x 都有 ∑ ∈≤M m m K x 定义5 当函数()x f 满足下述性质时，我们称其为凹的： ()()()()()[]n R x x x f x f x x f ∈∈-+≥-+212121, 1,0,11λλλλλ x x 第一季第二季第三季第四季)(x f x 1 如果当()1,0∈λ时上面的不等式严格成立，则称()x f 为严格凹的。一个函数 ()x f 是凸的当且仅当函数-()x f 是凹的；()x f 为严格凸函数当且仅当-()x f 为严 格凹函数。 拟凹函数是凹函数概念的一种推广，它包括了凹函数在内的一大类函数，而这类函数在经济学中有着广泛应用，关于拟凹函数的定义如下： 定义6 函数()x f 定义在R n 中的子集D 上，当且仅当()x f 满足如下性质时， ()x f 是拟凹的： ()()()()()2121,min 1x f x f x x f ≥-+λλ ∈λ[0,1] 显然，凹函数是拟凹的，但反过来并不成立，即拟凹函数不一定是凹函数。在下图中，函数()x f 是拟凹的，但不是凹的。 图 不是凹函数的拟凹函数 x 1 y x 2 x () x f 非线性系统学习控制理论的发展与展望 谢振东谢胜利刘永清 摘要：论述了学习控制的基本理论问题，给出了学习与学习控制系统的基本定义，着重讨论了学习控制方法产生的历史背景、目前非线性系统学习控制的研究状况，提出了一些有待继续研究的问题. 关键词：非线性系统；学习控制；发展与展望 文献标识码：A Development and Expectation for Learning Control Theory of Nonlinear Systems XIE Zhendong，XIE Shengli and LIU Yongqing （Depatrment of Automatic Control Engineering, South China University of Technology． Guangzhou, 510640, P.R.China） Abstract：In this paper, the problem for the basic theory of learning control is discussed. After giving the basic definition of learning and learning control, we mainly discuss the background of learning control and the research status for learning control of nonlinear systems, and put forward some problems need to be researched. Key words：nonlinear systems; learning control; development and expectation▲ 1 非线性系统学习控制的研究背景(Research background for learning control theory of nonlinear systems) 1.1 引言(Introduction) 对于高速运动机械手的控制，Uchiyama提出一个思想［1］：不断重复一个轨线的控制尝试，并以此修正控制律，能达到较好的控制效果.日本学者Arimoto［2］等人根据这种思想于1984年针对机器人系统的控制研究，提出了迭代学习控制这一新颖方法.这种控制方法只是利用控制系统先前的控制经验，根据测量系统的实际输出信号和期望信号来寻求一个理想的输入，使被控对象产生期望的运动.而“寻找”的过程就是学习的过程，在学习的过程中，只需要测量系统的输出信号和期望信号，不象适应控制那样，对系统要进行复杂的参数估计［3，4］，也不象一般控制方法那样，不能简化被控对象的动力学描述.特别是在一类具有较强的非线性耦合和较高的位置重复精度的动力学系统(如工业机器人、数控机床等)中，学习控制有着很好的应用，如T.Sugie［5］,M.Katic［6］,H.Park［7］的工作.迭代学习控制方法提出后，受到了控制界的广泛关注，人们不仅针对各种机器人系 一：名词解释 1：虚拟机：由软件实现的机器。 2：CPI：是衡量CPU执行指令效率的重要标志，指执行每条指令所需的平均时钟 周期数。 3：摩尔定律：当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月 便会增加一倍，性能也将提升一倍。 4：并发性：指两个或多个事件在同一时间间隔内发生的并行性。 5：程序局部性原理：是指程序在执行时呈现出局部性规律，即在一段时间内，整 个程序的执行仅限于程序中的某一部分。相应地，执行所访问的存储空间也局限 于某个内存区域。局部性原理又表现为：时间局部性和空间局部性。 6：CISC/RISC：CISC：即复杂指令系统计算机，指在系统中增加更多和复杂的 指令，来提高操作系统效率的计算机。RISC：即精简指令系统计算机，指在系统 中选取使用一些频率最高的、长度固定的、格式种类少的简单指令的计算机。 7：计算机系统结构：指对机器语言计算机的软、硬件功能的分配和对界面的定义。 8：系列机：指先设计好一种系统结构，而后就按这种系统结构设计它的系统软件， 按器件状况和硬件技术研究这种结构的各种实现方法，并按照速度、价格等不同 要求，分别提供不同速度、不同配置的各档机器。 9：模拟：用机器语言程序解释实现程序移植的方法。 10：仿真：用微程序直接解释另一种机器的指令系统。 11：寻址方式：寻找操作数或指令的有效地址的方式。 12：替换算法：在存储体系中，当出现页面失效时或者主存的所有页面已经全部 被占用而又出现页面失效时，按照某种算法来替换主存中某页。[由于主存中的 块比Cache中的块多，所以当要从主存中调一个块到Cache中时，会出现该 块所映象到的一组（或一个）Cache块已全部被占用的情况。这时，需要被 迫腾出其中的某一块，以接纳新调入的块。] 二：选择题 1，直接执行微指令的是（C） A 汇编程序 B 编译程序 C 硬件D微指令程序 2，对汇编语言程序员不透明的是（C） A 程序计数器B主存地址寄存器C条件码寄存器D指令寄存器 3，最早的冯·诺依曼型计算机是以（B）为中心的 A运算器B控制器C存储器 D I/O设备 4，计算机系统结构的角度的结构来看，机器语言程序员看到的机器属性是（C ） A 计算机软件所要完成的功能 B 计算机硬件的全部组成 C 编程要用到的硬件组织D计算机各部分硬件的实现 5，不同系列计算机之间实现可移植性的途径，不包括（B ） A 采用统一的高级语言B采用统一的汇编语言 C 模拟D仿真 6，利用时间重叠原理，实现并行处理的是（A） A流水处理机B多处理机 C 阵列处理机D集群系统 7，多处理机实现的并行主要是（B） A指令级并行 B 任务级并行C 操作级并行D操作步骤的级并行 函数零点存在性定理文件管理序列号：[K8UY-K9IO69-O6M243-OL889-F88688] 函数零点存在性定理： 一般地，如果函数y=f(x)在区间[a，b]上的图象是连续不断的一条曲线，并且有 f(a)．f(b) 若函数f（x）唯一的一个零点同时在区间（0，16）、（0，8）、（0，4）、（0，2）内，下列结论： （1）函数f（x）在区间（0，1）内有零点； （2）函数f（x）在区间（0，1）或（1，2）内有零点； （3）函数f（x）在区间[2，16）内无零点； （4）函数f（x）在区间（0，16）上单调递增或递减． 其中正确的有 ______（写出所有正确结论的序号）． 答案 由题意可确定f（x）唯一的一个零点在区间（0，2）内，故在区间[2，16）内无零点． （3）正确， （1）不能确定， （2）中零点可能为1， （4）中单调性也不能确定． 故答案为：（3） 例题2： 已知函数有零点，则实数的取值范围是（） 答案： 例题3： 例题4： 函数f（x）=3ax-2a+1在[-1，1]上存在一个零点，则实数a的取值范围是（）A. a ≥ 1/5; B. a ≤ -1 ; C. -1 ≤ a ≤ 1/5 ; D. a ≥ 1/5 或 a ≤ -1答案：由题意可得f（-1）×f（1）≤0，解得 ∴（5a-1）（a+1）≥0 ∴a≥ 1/5 或a≤-1 故选D ． 1.用二进制代码表示的计算机语言称为①机器语言，用助记符编写的语言称为②汇编语言。 2.计算机系统的三个层次结构由内到外分别是①硬件系统、系统软件和②应用系统。 3.编译方式是使用编译程序把源程序编译成机器代码的①目标程序，并以②机器程序的形式保留。 4.计算机系统的层次结构中，位于硬件系统之外的所有层次统称为虚拟机 5.现在主要采用总线结构作为计算机硬件之间的连接方式。 6.存储①程序，并按②地址顺序执行，这是③冯.诺依曼型计算机的工作原理。计算机中有①两股信 息在流动：一股是②控制信息，即操作命令，其发源地是③控制器，它分散流向各个部件；另一股是 ④数据信息，它受⑤控制信息的控制，从一个部件流向另一个部件，边流动边加工处理。 7. 假定基准程序A在某计算机上的运行时间为100s，其中90s为CPU时间，其余为I/O时间。若CPU速度提高50%,I/O速度不变，则运行基准程序A所耗费的时间是（70s）。 8. 至今为止，计算机中的所有信息仍以二进制方式表示，其理由是______。 A节约元件 B. 运算速度快C. 物理器件性能决定 D. 信息处理方便 9. 对计算机的软、硬件资源进行管理，是的功能。 A. 操作系统 B. 数据库管理系统 C. 语言处理程序 D. 用户程序 10. 冯诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（） A.指令操作码的译码结果 B.指令和数据的寻址方式 C.指令周期的不同阶段 D.指令和数据所在的存储单元 11. 存储字长是指（）。 A.存放在一个存储单元中的二进制代码的组合 B.存放在一个存储单元中二进制代码位数 C.存储单元的个数 D.机器指令的位数 12. 当前设计高性能计算机的重要技术途径是（） A.提高CPU主频 B.扩大主存容量 C.采用非冯诺依曼 D.采用并行处理技术 13.兼容性是计算机的一个重要性能，通常是指向上兼容，即旧型号计算机的软件可以不加修改地在新型号计算机上运行。系列机通常具有这种兼容性。（错） 14.计算机“运算速度”指标的含义是指每秒钟能执行多少条操作系统的命令（对） 15.利用大规模集成电路技术把计算机的运算部件和控制部件做在一块集成电路芯片上，这样的一块芯片叫做单片机（错）是cpu 16.冯·诺依曼计算机体系结构的基本思想是什么？按此思想设计的计算机硬件系统应由哪些部件组成？它们各起什么作用？ (1)计算机应包括运算器、存储器、控制器、输入和输出设备五大基本 部分. (2)计算机内部应采用二进制来表示指令和数据.每条指令一般具有一个操作码和一个地址码.其中操作码表示运算性质,地址码指出操作数在存储器中的地址. (3)将编好的程序送入内存储器中,然后启动计算机工作,计算机无需操作人员干预,能自动逐条取出指令和(完整版)计算机组成原理简答题
Peano定理解的存在性定理的应用主讲范进军
计算机系统结构简答。填空
自动控制原理非线性系统习题题库
函数零点存在性定理
计算机体系结构习题答案解析
非线性控制理论和方法
根的存在性证明(零点定理)
计算机体系结构试题库—简答题
组成原理
函数零点存在性定理.
计算机体系结构课后习题
建设项目投资决策是选择和决定投资行动方案的过程
纳什均衡的存在性定理中的相关解释
非线性系统学习控制理论的发展与展望
(完整版)计算机系统结构考试题目及参考答案
函数零点存在性定理图文稿
1-4测验 (2)组成原理