计算理论习题答案CHAP3new

3.3 修改定理3.10以得到推论3.12的证明，即证明一个语言是可判定的当且仅当有非确定的TM判定它。

证明：若M是一个确定型判定器则，则M也是一个非确定型判定器。

现在设N是一个非确定的判定器，将构造一个与之等价的确定型判定器

M。模拟过程使用深度搜索。

设N的不确定性分支的最大个数为b。

M有三个带：一个输入带，一个工作带，一个地址带。M按深度优先方

式搜索N的不确定计算分支树。

M= “输入w，

1)初始化，第一带上为w, 第二带为空，第三带为1;

2)将第一带的内容复制到第二带上，

3)按当前地址位数字选择N的一个不确定性分支，在第二带上模拟N

运行一步；

4)若当前地址位为i

态，则将当前地址位改为i+1, 转第2步；

5)若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状

态，则将当前地址位改为空格, 左移并将当前地址位改为空格直

到找到一个地址位其值

到了地址带的最左端仍有当前地址位为b，则拒绝；

6)若N进入接受状态，则接受；否则，右移一格，将空格上写入1，

转第三步。”

由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。

3.4给出枚举器的形式定义。

解：枚举器E=(Q,∑,Γ,δ,q0,q accept,q reject), 其中转移函数δ为：

δ：Q×Γ→Q×Γ×{L,R}×∑*

δ (q,a)=(r,b,s1,c)

表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于ε，则不打印。

另外E的起始格局只能是q0v，这里v表示一个空格。

3.5检查图灵机的形式定义，回答下列问题并解释你的推测：

a．图灵机能在它的带子上写下空白符吗

b．带字母表Γ和输入字母表∑能相同吗？

c．图灵机的读写头能在连续的两步中处于同一个位置吗？

d．图灵机能只包含一个状态吗？

解：

a．能。因为空白符属于带字母表Γ；

b．不能。因为空白符不属于输入字母表∑；

c．能。当读写头处于左端点时，如果转移是向左转移，因为不准机器从带的左端点移出，所以下一个格局读写头仍在左端点。

d．不能。因为q accept≠q reject，至少应有两个状态。

3.6解：因为M不一定是判定器，可能会在运行某个s i时不停机，则L(M)中

按字典序大于s i的字符串不可能被枚举出来。

3.7解：因为图灵机的一个本质要求是一步之内，只能做有限的工作，而第

1)步中取所有可能的值，这有无限多种情况。

3.8构造具有3条带的图灵机。

对于问题a.

1)w 先读入第一条带，然后读到0就把0写入第2条带，读到1就把1

写入第3条带，直到读到空格为止。

2)然后把3个读写头都返回到最左边。

3)开始读第2条带和第3条带，每次都是读一个字符，如果同时遇上空

格符，则接收，否则拒绝。

对于问题b:

1)和a的第1步相同。

2)和a的第2步相同。

3)每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，

就接收，否则拒绝。

对于问题c:

1)和a的第1步相同。

2)和a的第2步相同。

3)每次读带3的一个字符就读带2的两个字符，如果同时遇上空格符，就

拒绝，否则接受。

3.9由题知,1-pda代表一个栈的下推自动机,2-pda代表两个栈的下推自动机。

如果能用2-pda模拟一个图灵机,而我们已经知道图灵机比下推自动机强大，那么就有2-pda比1-pda更强大。设有TM S。下面构造2-pda P，且记其两个栈分别为A，B：

P＝“对于输入w,

1) 将w读入栈A，再全部从栈A中依次弹出并读入栈B。

2) 模拟S在w上运行。记录S的当前状态，并且栈B的栈顶字符为S的

读写头所指方格的字符：

a)若S执行一个右移δ(q,a)=(r,b,R)，则将栈B的栈顶字符a替换为

b，弹出b，推入栈A，记录S的当前状态r。

b)若S执行一个左移δ(q,a)=(r,b,L)，首先将栈B的栈顶字符a替换

为b；若栈A不空，则将栈A弹出一个字符推入栈B；若栈A为空(对

应于S处于工作带最左端)，则不作栈操作。记录S的当前状态r。

3) 若S进入接受状态，则进入接受状态。”

由上知.我们用2-pda模拟了图灵机,所以2-pda比1-pda强大.

下面用一个四带TM S来模拟一个3-pda P，要求P进入接受状态之前排空栈，并且或者推入或者弹出：

记P的三个栈为A,B,C。S的四个带，第一带用来模拟P的输入带，第二,三,四带分别模拟栈A,B,C：

S＝“对于输入字符串w，

1)初始化，第一带放入w，第二，三，四带为空。

2)模拟P分别在四个带上按如下方式动作：

a．若P在输入带上读一个非空字符，则读第一带字符并右移一格；

若P在输入带上读一个ε，则在第一带上不读字符，且读写头

保持不动。

b．栈A,B,C中若有弹出，则在相应带上当前格改写为空格，并左移一格；若有推入a，则在相应带上右移一格，并写入a。

3) 若P进入接受状态，则接受。”

3.10证明双无限带图灵机识别图灵可识别语言。

证明思路：利用双无限单带图灵机模拟普通单带图灵机时，只需要设计一个左端点。我们的证明是让它在第一格左边标记“$”作为

左端点。

证明：

首先用单带双无限带图灵机模拟普通单带图灵机：

设有普通图灵机M1＝( Q1, ∑, Γ1, δ1, q0, q accept, q reject )。下面构造与之等价的单带双无限带图灵机M2＝( Q2, ∑, Γ2, δ2, q s, q accept, q reject )，其中

Q2=Q1?{q s,q t}, q s为新的起始状态；Γ2＝Γ1?{$}.

对任意q∈Q2, a∈Γ2,

.

$a , Q q ,a , Q q ,q q ,q q R)$, (q,a),(q,R),,$,q (L),a,,q ()a ,q (111t s 1

0t 2=∈Γ∈∈==???????=若若若若，δδ 再用普通单带图灵机模拟单带双无限带图灵机：

设有单带双无限图灵机M 1＝(Q,∑,Γ,δ,q 0,q accept ,q reject )，下面构造普通单带图灵机M 2：

M 2=“输入串w ，

1) 将带上字符串改写为$w, 将读写头放在w 的第一个字符上，

2) 按照M 1的转移函数运行，

3) 每当读写头移到了$上，就将$右边的所有字符右移一格，并在$右

边的方格里写上空格符，再将读写头放在这个方格上，转第二步，

4) 若进入接受状态，则接受；若进入拒绝状态则拒绝。”

也可以用普通双带图灵机模拟单带双无限带图灵机：

设有单带双无限图灵机M 1＝(Q,∑,Γ,δ,q 0,q accept ,q reject )，下面构造普通双带图灵机M 2：

M 2=“输入串w ，

1) 在第一个带上放上$, 读写头放在$上；

第二个带子上放入#w, 读写头放在第二个方格上。

2) 当第一带读写头位于$上，而第二带读写头不在＃上时，在第二带

上按照M 1的转移规则运行，直到停机或读写头移到#上。若进入接

受状态则接受，若进入拒绝状态则拒绝。若读写头移到#上，则将

第一带上读写头右移一格。

3) 当第二带读写头位于#上，而第一带读写头不在$上时，在第一带上

按照M 1的转移规则运行，但是每一步要将读写头移动方向反向，

直到停机或读写头移到$上。若进入接受状态则接受，若进入拒绝

状态则拒绝。若读写头移到$上，则将第二带上读写头右移一格，

转第二步。”

3.11只写一次图灵机是一个单带图灵机，它在每个带方格上最多只能改变其

内容一次(包括带上得输入区域)。证明图灵机模型的这个变形等价于普通的图灵机模型。

证明：普通单带图灵机总是可以模拟只写一次图灵机。下面说明怎样用一个只写一次TM T 模拟一个普通单带TM S。

T=“对于输入w=w1w2?w n,

1) 在w1w2?w n上并模拟S运行。

2) 每当S要改写工作带时(例如设S要将当前方格内容改写为b，并且左

移或右移一格)，T按如下方式动作：

a. 将当前方格改写为“b*”，在带子右边第一个空格写下“#”。

b. 将“#”左边的字符抄写到“#”右边(注：每抄写一个字符，需要

将此格字符改写一次以作上标记，但是“b*”不用再作另外标记，而且将“b*”抄写为“b~”)。

c. 找到带有标记“~”的字符，再模拟S左移或右移一格。

然后继续模拟S。

3) 若S接受则接受；若S拒绝则拒绝。”

3.12对于普通图灵机N，构造与之等价的带左复位的图灵机E：

E＝“对于输入w,

1)在w上模拟N的一步动作：

若N要将当前格由a改为b且右移，则照此动作；

若N要将当前格由a改为b且左移，则将当前格由a改为b#且复位：

a)以~标记当前位，右移一格；

b)若当前位没有标记#，则复位，右移直到找到标记有~的字符，去掉

此标记，右移一格转步(a);

c)若当前位有标记#，则去掉标记#并复位，右移或直到找到标记有~

的字符，去掉此标记；

2)若N进入接受状态，则接受；若进入拒绝状态，则拒绝；否则转第

一步。”

L(E)=L(N)。因此左复位的图灵机识别图灵可识别语言类。

3.13 以停留代替左移的图灵机识别什么语言类？

解：正则语言类。首先一个DFA可以被一个以停留代替左移的图灵机模拟。下面证明一个以停留代替左移的图灵机S=(Q,∑,Γ,δ,q1,q accept,q reject)，可以被一个NFA M=(Q1,∑,δ1,q0,F)模拟。

M的构造如下：

令Q1= Q×Γε?{q end}， F={q end}，q0=(q1,ε),

1)对任意q∈Q-{q accept,q reject}, a∈∑,令

δ1( (q,ε) , a )={(q,a)};

2)对任意q∈Q-{q accept,q reject}, a∈Γ,

若有转移δ(q,a)=(r,b,R)，则令δ1( (q,a), ε )={(r, ε)};

若有转移δ(q,a)=(r,b,S)，则令δ1( (q,a), ε )={(r,b)};

3)对任意a∈Γε, b∈Γ，

令δ1( (q accept,a) , b )={(q accept, ε)};

4)对任意q∈Q，令S q=(Q,∑,Γ,δ,q,q accept,q reject),

若ε∈L(S q)，则令δ1( (q,ε) , ε )={q end}。

其中第一类转移是用来读字符的。

第二类转移是用来模拟S的读写头的移动的。由于S没有左移，所以右移一格之前改写的内容b可以舍去。

第三类转移用来处理当S已进入接受状态，但是字符串还没有读完的情况的。即先由δ1( (q accept,a) , b )={ (q accept,ε) }读完所有剩余字符，再由第四类转移中的δ1((q accept,ε),ε)={q end}进入接受状态。

第四类转移用来处理S的读写头移出输入区域的情况的，在这种情况下，S是进入接受状态，还是进入拒绝状态，还是不停机，完全取决于进入空白区域时的状态q：即若ε∈L(S q)，则S最终会进入接受状态；若ε?L(S q)，则S最终会进入拒绝状态或不停机。

3.15证明可判定语言类在下列运算下封闭。

a. 并。

证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M：M＝“输入w，

1)分别在w上运行M1和M2，每运行一步M1就运行一步M2。

2)若M1和M2中有一个接受，则接受。

若都拒绝，则拒绝。”

M为识别A1?A2的判定器。所以可判定语言类对并运算封闭。

b. 连接。

证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M：M＝“输入w，

1)列出所有将w分成两段的方式(|w|+1种).

2)对于每一种分段方式，在第一段上运行M1，在第二段上运行M2。

若都接受，则接受。

3)若没有一种分段方式被接受则拒绝。”

M为识别A1 A2的判定器。所以可判定语言类对连接运算封闭。

c. 星号。

证明：设M1为识别可判定语言A的判定器。

M＝“输入w，

1)列出w的所有分段的方式(2|w|-1种)。

2)对于每一种分段方式，重复下列步骤：

3)分别在每一段上运行M1，若每一段都能被M1接受，则接受。

4)若没有一种分段方式被接受则拒绝。”

M为识别A*的判定器。所以可判定语言类对星号运算封闭。

d. 补。

证明：设M1=(Q,∑,Γ,δ,q0, q1, q2)为识别可判定语言A的判定器，其中q1为接受状态，q2为拒绝状态。令M=(Q,∑,Γ,δ,q0, q2, q1)，其中q2为接受状态，q1为拒绝状态。则M为识别A的判定器。所以可判定语言类对补运算是封闭的。

e. 交。

证明：设M1，M2为识别可判定语言A1,A2的判定器。构造图灵机M：M＝“输入w，

1)分别在w上运行M1和M2，每运行一步M1就运行一步M2。

2)若M1和M2中都接受，则接受。

若M1和M2中有一个拒绝，则拒绝。”

M为识别A1?A2的判定器。所以可判定语言类对交运算是封闭的。

3.16证明图灵可识别语言类在下列运算下封闭：

a．并 b．连接 c．星号 d．交

证明：要证这四种运算下图灵可识别语言类封闭，只需设计出图灵机来识别此种语言。设A和B是图灵可识别语言，A=L(M1)，B=L(M2)，M1和M2是两个图灵机。

a．M=“对于输入w：

1) 在输入w上并行运行M1和M2；

2) M1和M2中有一个停机且接受，则接受；若都停机且拒绝，则拒绝。”

M识别A1?A2。所以图灵可识别语言类对并运算是封闭的。

b. M＝“输入w，

1)出所有将w分成两段的方式(|w|+1种).

2)对于i=1,2,?重复以下步骤：

3)对于每一种分段方式，在第一段上运行M1i步，在第二段上运行

M2 i步，或者直到停机。若都接受，则接受。”

M识别A1 A2。所以图灵可识别语言类对连接运算是封闭的。

c．M＝“输入w，

1)列出w的所有分段的方式(2|w|-1种).

2)对于i=1,2,?重复以下步骤：

3)对于每一种分段方式，分别在每一段上运行M1i步，或者直到停

机。

若M1接受所有段，则接受。”

M识别A*。所以图灵可识别语言类对星号运算是封闭的。

d．M= “对于输入w：

1)在输入w上运行M1。若M1接受，则转(2)；若M1拒绝，则拒绝。

2)在w上运行M2。若M2接受，则接受；若M2拒绝，则拒绝。”

M识别A?B。所以图灵可识别语言类对并运算封闭。

3.21

1) 由c max≥|c1|知，当|x|≤1，则欲判定不等式明显成立。

2) 当|x|>1时，由

c1x n + c2x n-1 + …+ c n x + c n+1 = 0

?c1x =－(c2 + …+ c n x2-n + c n+1x1-n)

?|c1| |x| = |c2 + …+ c n x2-n + c n+1x1-n|

< |c2| +…+ |c n||x|2-n + |c n+1| |x|1-n

≤ |c2| +…….|c n| + |c n+1||x0|

≤ n c max

< (n + 1) c max

?|x| < (n + 1) c max / |c1|.

由(1)和(2)可知结论成立。

3.22解：A是可判定的。

因为若上帝存在，则s=0，A={0}是可判定的。

若上帝不存在，则s=1，A={1}是可判定的。

计算机组成原理_第四版课后习题答案(完整版)[]

第一章 1．比较数字计算机和模拟计算机的特点 解：模拟计算机的特点：数值由连续量来表示，运算过程是连续的；数字计算机的特点：数值由数字量（离散量）来表示，运算按位进行。两者主要区别见 P1 表 1.1 。 2．数字计算机如何分类？分类的依据是什么？ 解：分类：数字计算机分为专用计算机和通用计算机。通用计算机又分为巨型机、大型机、 中型机、小型机、微型机和单片机六类。分类依据：专用和通用是根据计算机的效率、速度、价格、运行的经济性和适应性来划分的。 通用机的分类依据主要是体积、简易性、功率损耗、性能指标、数据存储容量、 指令系统规模和机器价格等因素。 3．数字计算机有那些主要应用？（略） 4．冯 . 诺依曼型计算机的主要设计思想是什么？它包括哪些主要组成部分？ 解：冯 . 诺依曼型计算机的主要设计思想是：存储程序和程序控制。存储程序：将解题的程序（指令序列）存放到存储器中；程序控制：控制器顺序执行存储的程序，按指令功能控制全机协调地完成运算任务。 主要组成部分有：控制器、运算器、存储器、输入设备、输出设备。 5．什么是存储容量？什么是单元地址？什么是数据字？什么是指令字？ 解：存储容量：指存储器可以容纳的二进制信息的数量，通常用单位KB MB GB来度量，存储 容 量越大，表示计算机所能存储的信息量越多，反映了计算机存储空间的大小。单元地址：单元地址简称地址，在存储器中每个存储单元都有唯一的地址编号，称为单元地 址。 数据字：若某计算机字是运算操作的对象即代表要处理的数据，则称数据字。指令字：若某计算机字代表一条指令或指令的一部分，则称指令字。 6．什么是指令？什么是程序？ 解：指令：计算机所执行的每一个基本的操作。程序：解算某一问题的一串指令序列称为该问题的计算程序，简称程序。 7．指令和数据均存放在内存中，计算机如何区分它们是指令还是数据？ 解：一般来讲，在取指周期中从存储器读出的信息即指令信息；而在执行周期中从存储器中读出的信息即为数据信息。

《数值计算方法》试题集及答案

《数值计算方法》复习试题 一、填空题： 1、????? ?????----=410141014A ，则A 的LU 分解为 A ??? ?????????=? ?????????? ?。 答案： ?? ????????--??????????--=1556141501 4115401411A 2、已知3.1)3(,2.1)2(,0.1)1(===f f f ，则用辛普生（辛卜生）公式计算求得 ?≈3 1 _________ )(dx x f ,用三点式求得≈')1(f 。 答案：， 3、1)3(,2)2(,1)1(==-=f f f ，则过这三点的二次插值多项式中2 x 的系数为 ， 拉格朗日插值多项式为 。 答案：-1， )2)(1(21 )3)(1(2)3)(2(21)(2--------= x x x x x x x L 4、近似值*0.231x =关于真值229.0=x 有( 2 )位有效数字； 5、设)(x f 可微,求方程)(x f x =的牛顿迭代格式是( )； （ 答案 )(1)(1n n n n n x f x f x x x '--- =+ 6、对1)(3 ++=x x x f ,差商=]3,2,1,0[f ( 1 ),=]4,3,2,1,0[f ( 0 )； 7、计算方法主要研究( 截断 )误差和( 舍入 )误差； 8、用二分法求非线性方程 f (x )=0在区间(a ,b )内的根时，二分n 次后的误差限为 ( 1 2+-n a b )； 9、求解一阶常微分方程初值问题y '= f (x ,y )，y (x 0)=y 0的改进的欧拉公式为

( )] ,(),([2111+++++=n n n n n n y x f y x f h y y )； 10、已知f (1)＝2，f (2)＝3，f (4)＝，则二次Newton 插值多项式中x 2系数为( )； 11、 两点式高斯型求积公式?1 d )(x x f ≈( ?++-≈1 )] 321 3()3213([21d )(f f x x f )，代数精 度为( 5 )； 12、 解线性方程组A x =b 的高斯顺序消元法满足的充要条件为(A 的各阶顺序主子式均 不为零)。 13、 为了使计算 32)1(6 )1(41310-- -+-+ =x x x y 的乘除法次数尽量地少，应将该表 达式改写为 11 ,))64(3(10-= -++=x t t t t y ，为了减少舍入误差，应将表达式 19992001-改写为 199920012 + 。 14、 用二分法求方程01)(3 =-+=x x x f 在区间[0,1]内的根,进行一步后根的所在区间 为 ，1 ,进行两步后根的所在区间为 ， 。 15、 、 16、 计算积分?1 5 .0d x x ,取4位有效数字。用梯形公式计算求得的近似值为 ，用辛卜 生公式计算求得的近似值为 ，梯形公式的代数精度为 1 ，辛卜生公式的代数精度为 3 。 17、 求解方程组?? ?=+=+042.01532121x x x x 的高斯—塞德尔迭代格式为 ?????-=-=+++20/3/)51()1(1)1(2)(2)1(1 k k k k x x x x ，该迭 代格式的迭代矩阵的谱半径)(M ρ= 121 。 18、 设46)2(,16)1(,0)0(===f f f ,则=)(1x l )2()(1--=x x x l ，)(x f 的二次牛顿 插值多项式为 )1(716)(2-+=x x x x N 。 19、 求积公式 ?∑=≈b a k n k k x f A x x f )(d )(0 的代数精度以( 高斯型 )求积公式为最高，具 有( 12+n )次代数精度。

计算方法引论课后答案.

第一章 误差 1. 试举例,说明什么是模型误差,什么是方法误差. 解: 例如,把地球近似看为一个标准球体,利用公式2 4A r π=计算其表面积,这个近似看为球体的过程产生 的误差即为模型误差. 在计算过程中,要用到π,我们利用无穷乘积公式计算π的值: 12 222...q q π=? ?? 其中 11 2,3,... n q q n +?=?? ==?? 我们取前9项的乘积作为π的近似值,得 3.141587725...π≈ 这个去掉π的无穷乘积公式中第9项后的部分产生的误差就是方法误差,也成为截断误差. 2. 按照四舍五入的原则,将下列各数舍成五位有效数字: 816.956 7 6.000 015 17.322 50 1.235 651 93.182 13 0.015 236 23 解: 816.96 6.000 0 17.323 1.235 7 93.182 0.015 236 3. 下列各数是按照四舍五入原则得到的近似数,它们各有几位有效数字? 81.897 0.008 13 6.320 05 0.180 0 解: 五位 三位 六位 四位 4. 若1/4用0.25表示,问有多少位有效数字? 解: 两位 5. 若 1.1062,0.947a b ==,是经过舍入后得到的近似值,问:,a b a b +?各有几位有效数字? 解: 已知4311 d 10,d 1022 a b --

计算机组成原理第二版课后习题答案

第1章计算机系统概论 1. 什么是计算机系统、计算机硬件和计算机软件？硬件和软件哪个更重要？ 解： 计算机系统：由计算机硬件系统和软件系统组成的综合体。 计算机硬件：指计算机中的电子线路和物理装置。 计算机软件：计算机运行所需的程序及相关资料。 硬件和软件在计算机系统中相互依存，缺一不可，因此同样重要。 2. 如何理解计算机的层次结构？ 答：计算机硬件、系统软件和应用软件构成了计算机系统的三个层次结构。 （1）硬件系统是最内层的，它是整个计算机系统的基础和核心。 （2）系统软件在硬件之外，为用户提供一个基本操作界面。 （3）应用软件在最外层，为用户提供解决具体问题的应用系统界面。 通常将硬件系统之外的其余层称为虚拟机。各层次之间关系密切，上层是下层的扩展，下层是上层的基础，各层次的划分不是绝对的。 3. 说明高级语言、汇编语言和机器语言的差别及其联系。 答：机器语言是计算机硬件能够直接识别的语言，汇编语言是机器语

言的符号表示，高级语言是面向算法的语言。高级语言编写的程序（源程序）处于最高层，必须翻译成汇编语言，再由汇编程序汇编成机器语言（目标程序）之后才能被执行。 4. 如何理解计算机组成和计算机体系结构？ 答：计算机体系结构是指那些能够被程序员所见到的计算机系统的属性，如指令系统、数据类型、寻址技术组成及I/O机理等。计算机组成是指如何实现计算机体系结构所体现的属性，包含对程序员透明的硬件细节，如组成计算机系统的各个功能部件的结构和功能，及相互连接方法等。 5. 冯?诺依曼计算机的特点是什么？ 解：冯?诺依曼计算机的特点是：P8 ●计算机由运算器、控制器、存储器、输入设备、输出设备五大 部件组成； ●指令和数据以同同等地位存放于存储器内，并可以按地址访 问； ●指令和数据均用二进制表示； ●指令由操作码、地址码两大部分组成，操作码用来表示操作的 性质，地址码用来表示操作数在存储器中的位置； ●指令在存储器中顺序存放，通常自动顺序取出执行； ●机器以运算器为中心（原始冯?诺依曼机）。

计算理论试题及答案

一、证明：设M是一台识别语言B的DFA，交换M的接受状态与非接受状态得到一台新的DFA，则这台新DFA识别B的补集。因而，正则语言类在补运算下封闭。(8分) 参考答案： 设M’是一台将DFA M的接受态与非接受态交换后的DFA，接下来证明M识别B语言，则M’识别B的补集： 假定M’识别x，则对于x 在M’上运行将结束于M’的一个接受态，因为M和M’交换了接受态与非接受态，因此对于x运行于M，将会结束于一个非接受态，所以x∈/B。类似地，如果x不被M’接受，则它一定被M接受。故M’恰好接受所有不被M接受的那些串，因此M’识别B的补集。 既然B是任意的正则语言，且我们已构造出一台自动机识别它的补集，它表明任何正则语言的补也是正则的。因此，正则语言类在补运算下封闭。 二、令∑＝｛0，1，＋，＝｝和ADD＝｛x=y+z | x，y，z是二制整数，且x是y与z的和｝，证明ADD不是正则的。(8分) 参考答案： 假定ADD是正则的。让P作为泵引理中的泵长度，选择S的串形式为1P＝0P＋1P作为ADD的一个成员。因为S有长度大于P，由泵引理保证它能分割成形如：S＝xyz的三部分，满足泵引理的条件。泵引理的第三个条件有｜xy｜≤P，《它表明对于K≥1，y就是1K。这是xy2z是串1P＋K＝OP＋1P，而它不是ADD的成员，由泵引理导出矛盾，因此ADD不是正则的。 三、请将下述CFG转换成等价的乔姆斯基范式文法。(8分) A→BAB｜B｜ε B→00｜ε 参考答案： S0→AB｜CC｜BA｜BD｜BB｜ε A→AB｜CC｜BA｜BD｜BB B→CC C→0 D→AB 四、请用泵引理证明语言A＝｛0n＃02n＃03n | n≥0 ｝不是上下文无关的。(8分) 参考答案： 由泵引理，让P作为泵长度，s=0p＃02p＃03p ，接下来证明s=uvxyz不能进行泵抽取。 v和y都不能包含＃，否则，xv2wy2z将超过2个＃s ，因此，如果我们按＃’s将s分成三段如：0p，02p，03p，至少有一段不包含v或y。因此，由于段之间的1：2：3的比例不再维持，xv2wy2z也不语言A中。故语言A＝｛0n＃02n＃03n | n≥0 ｝不是上下文无关。的 五、下面的语言都是字母表｛0,1｝上的语言，请以实现描述水平级给出判定这些语言的图灵机：(8分)

计算方法的课后答案

《计算方法》习题答案 第一章 数值计算中的误差 1．什么是计算方法？（狭义解释） 答：计算方法就是将所求的的数学问题简化为一系列的算术运算和逻辑运算，以便在计算机上编程上机，求出问题的数值解，并对算法的收敛性、稳定性和误差进行分析、计算。 2．一个实际问题利用计算机解决所采取的五个步骤是什么？ 答：一个实际问题当利用计算机来解决时，应采取以下五个步骤： 实际问题→建立数学模型→构造数值算法→编程上机→获得近似结果 4．利用秦九韶算法计算多项式4)(5 3 -+-=x x x x P 在3-=x 处的值，并编程获得解。 解：400)(2 3 4 5 -+?+-?+=x x x x x x P ，从而 所以，多项式4)(5 3 -+-=x x x x P 在3-=x 处的值223)3(-=-P 。 5．叙述误差的种类及来源。 答：误差的种类及来源有如下四个方面： （1）模型误差：数学模型是对实际问题进行抽象，忽略一些次要因素简化得到的，它是原始问题的近似，即使数学模型能求出准确解，也与实际问题的真解不同，我们把数学模型与实际问题之间存在的误差称为模型误差。 （2）观测误差：在建模和具体运算过程中所用的一些原始数据往往都是通过观测、实验得来的，由于仪器的精密性，实验手段的局限性，周围环境的变化以及人们的工作态度和能力等因素，而使数据必然带有误差，这种误差称为观测误差。 （3）截断误差：理论上的精确值往往要求用无限次的运算才能得到，而实际运算时只能用有限次运算的结果来近似，这样引起的误差称为截断误差（或方法误差）。 （4）舍入误差：在数值计算过程中还会用到一些无穷小数，而计算机受机器字长的限制，它所能表示的数据只能是一定的有限数位，需要把数据按四舍五入成一定位数的近似的有理数来代替。这样引起的误差称为舍入误差。 6．掌握绝对误差（限）和相对误差（限）的定义公式。 答：设* x 是某个量的精确值，x 是其近似值，则称差x x e -=* 为近似值x 的绝对误差（简称误差）。若存在一个正数ε使ε≤-=x x e * ，称这个数ε为近似值x 的绝对误差限（简称误差限或精度）。 把绝对误差e 与精确值* x 之比* **x x x x e e r -==称为近似值x 的相对误差，称

计算方法习题答案

计算方法第3版习题答案 习题1解答 1.1 解：直接根据定义得 *411()102x δ-≤?*411()102r x δ-≤?*3*12211 ()10,()1026 r x x δδ--≤?≤?*2*5331()10,()102r x x δδ--≤?≤ 1.2 解：取4位有效数字 1.3解：433 5124124124 ()()() 101010() 1.810257.563 r a a a a a a a a a δδδδ----++++++≤≤=?++? 123()r a a a δ≤ 123132231123 ()()() a a a a a a a a a a a a δδδ++0.016= 1.4 解：由于'1(),()n n f x x f x nx -==，故***1*(())()()()n n n f x x x n x x x δ-=-≈- 故** * ***(()) (())()0.02()r r n f x x x f x n n x n x x δδδ-= ≈== 1.5 解： 设长、宽和高分别为 ***50,20,10l l h h εεωωεεεε=±=±=±=±=±=± 2()l lh h ωωA =++，*************()2[()()()()()()]l l l h h l h h εδωωδδδωδδωA =+++++ ***4[]320l h εωε=++= 令3201ε<，解得0.0031ε≤， 1.6 解：设边长为x 时，其面积为S ，则有2()S f x x ==，故 '()()()2()S f x x x x δδδ≈= 现100,()1x S δ=≤，从而得() 1 ()0.00522100 S x x δδ≈ ≤ =? 1.7 解：因S ld =，故 S d l ?=?，S l d ?=?，*****()()()()()S S S l d l d δδδ??≈+?? * 2 ()(3.12 4.32)0.010.0744S m δ=+?=, *** ** * () () 0.0744 ()0.55%13.4784 r S S S l d S δδδ= = = ≈ 1.8 解：（1）4.472 （2）4.47 1.9 解：(1) （B ）避免相近数相减 (2)（C ）避免小除数和相近数相减 (3)（A ）避免相近数相减 (3)（C ）避免小除数和相近数相减，且节省对数运算 1.10 解 （1）357sin ...3!5!7!x x x x x =-+-+ 故有357 sin ..3!5!7! x x x x x -=-+-， （2） 1 (1)(1)1lnxdx ln ln ln N+N =N N +-N N +N +-? 1 (1)1ln ln N +=N +N +-N 1.11 解：0.00548。 1.12解：21 16 27 3102 ()()() -? 1.13解：0.000021

计算理论课后题及答案2

第三章 上下文无关语言 3.1 略。 3.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20，证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ，A ,B 也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进而知道B A ?为CFL ，由DeMorgan 定律B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。 3.3 略。 3.4和3.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A 0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε

计算理论导引--研究生考试试卷格式

东华大学 2010~ 2011学年第二学期研究生期末考试试题参考答案 和评分标准 考试学院：计算机 考试专业：计算机科学与技术 考试课程名称：计算理论导引与算法复杂性 一、单项选择题（每空2分，本题共20分） 1. DFA和NFA的区别在于（B ）。 A、NFA能够识别的语言DFA不一定能够识别 B、对同一个输入串两者的计算过程不同 C、DFA能够识别的语言NFA不一定能够识别 D、NFA比DFA多拥有一个栈 2. 若一个语言A是非正则的，对于个给定的一个泵长p,若存在一个串s=xyz,|s|≥p，则 （ A ）。 A、|y|可能大于等于0 B、xz∈A C、xyyz∈A D、|xy|不可能小于等于p 3. 下推自动机与图灵机的不同之处是( B )。 A、下推自动机比图灵机识别的语言多 B、下推自动机比图灵机识别的语言少 C、下推自动机识别的语言是不可判定 D、拥有一个无限的存储带 4. 如果一个语言是图灵可判定的，则（A）。 A、对于一个不属于它串s，图灵机计算s时，一定能够到达拒绝状态 B、对于一个不属于它串s，不一定有一个判定器判定s C、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态 D、对于一个不属于它串s，图灵机计算s时，一定不会停机 5. 一个集合在条件（ C ）下是不可数的。 A、该集合为无限集合 B、组成该集合的元素是实数 C、该集合的规模大于自然数集合的规模 D、该集合是一个有限的集合 6. 对于一个语言，（ C ）的说法是正确的。 A、如果它属于Turing-recognizable，那么，一定属于EXPTIME B、如果它是NP-hard，那么，一定属于NP C、如果它是NP-complete，那么，一定属于NP D、它一定能被图灵机识别 7. 如果A≤m B且B是可判定的，则（A）。

计算理论习题答案CHAP1newedit

练习 1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题. a. M 1的起始状态是q 1 b. M 1的接受状态集是{q 2} c. M 2的起始状态是q 1 d. M 2的接受状态集是｛q 1，q 4｝ e. 对输入aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1 f. M 1接受字符串aabb 吗？否 g. M 2接受字符串ε吗？是 1.2 给出练习 2.1中画出的机器M 1和M 2的形式描述. M 1=(Q 1,Σ,δ1,q 1,F 1) 其中 1）Q 1={q 1,q 2,q 3,}; 2）Σ={a,b}; 3 415）F 1={q 2} M 2=(Q 2,Σ,δ2,q 2,F 2) 其中 1）Q 2={q 1,q 2,q 3,q 4}; 2）Σ={a,b}; 3 324）F 2={q 1,q 4} 1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。试画出此机器的状态图。 d

1.6 画出识别下述语言的DFA 的状态图。 a){w | w 从1开始以0结束} b){w | w 至少有3个1} c) {w | w 含有子串0101} d) {w | w 的长度不小于3，且第三个符号为0} e) {w | w 从0开始且为奇长度，或从1开始且为偶长度} 或

f) {w | w 不含子串110} g) {w | w 的长度不超过5} h){w | w 是除11和111以外的任何字符} i){w | w 的奇位置均为1} j) {w | w 至少含有2个0，且至多含有1个1} k) {ε,0} l) {w | w 含有偶数个0，或恰好两个1} 0,1 1

计算方法练习题与答案

练习题与答案 练习题一 练习题二 练习题三 练习题四 练习题五 练习题六 练习题七 练习题八 练习题答案 练习题一 一、是非题 1.–作为x的近似值一定具有6位有效数字，且其误差限。() 2.对两个不同数的近似数，误差越小，有效数位越多。() 3.一个近似数的有效数位愈多，其相对误差限愈小。()

4.用近似表示cos x产生舍入误差。 ( ) 5.和作为的近似值有效数字位数相同。 ( ) 二、填空题 1.为了使计算的乘除法次数尽量少，应将该表达式改写 为； 2.–是x舍入得到的近似值，它有位有效数字，误差限 为，相对误差限为； 3.误差的来源是； 4.截断误差 为； 5.设计算法应遵循的原则 是。 三、选择题 1．–作为x的近似值，它的有效数字位数为( ) 。 (A) 7； (B) 3； (C) 不能确定 (D) 5. 2．舍入误差是( )产生的误差。 (A) 只取有限位数 (B) 模型准确值与用数值方法求得的准确值 (C) 观察与测量 (D) 数学模型准确值与实际值 3．用 1+x近似表示e x所产生的误差是( )误差。 (A). 模型 (B). 观测 (C). 截断 (D). 舍入 4．用s*=g t2表示自由落体运动距离与时间的关系式 (g为重力加速度)，s t是在时间t内的实际距离，则s t s*是（）误差。 (A). 舍入 (B). 观测 (C). 模型 (D). 截断 5．作为的近似值，有( )位有效数字。 (A) 3； (B) 4； (C) 5； (D) 6。

四、计算题 1．，，分别作为的近似值，各有几位有效数字？ 2．设计算球体积允许的相对误差限为1%，问测量球直径的相对误差限最大为多少？ 3．利用等价变换使下列表达式的计算结果比较精确： (1)， (2) (3) ， (4) 4．真空中自由落体运动距离s与时间t的关系式是s=g t2，g为重力加速度。现设g是精确的，而对t有秒的测量误差，证明：当t增加时，距离的绝对误差增加，而相对误差却减少。 5*. 采用迭代法计算，取 k=0,1,…, 若是的具有n位有效数字的近似值，求证是的具有2n位有效数字的近似值。 练习题二 一、是非题 1.单点割线法的收敛阶比双点割线法低。 ( ) 2.牛顿法是二阶收敛的。 ( ) 3.求方程在区间[1, 2]内根的迭代法总是收敛的。( ) 4.迭代法的敛散性与迭代初值的选取无关。 ( ) 5.求非线性方程f (x)=0根的方法均是单步法。 ( ) 二、填空题

计算机组成原理课后习题答案(一到九章)

作业解答 第一章作业解答 1.1 基本的软件系统包括哪些内容？ 答：基本的软件系统包括系统软件与应用软件两大类。 系统软件是一组保证计算机系统高效、正确运行的基础软件，通常作为系统资源提供给用户使用。包括：操作系统、语言处理程序、数据库管理系统、分布式软件系统、网络软件系统、各种服务程序等。 1.2 计算机硬件系统由哪些基本部件组成？它们的主要功能是什么？ 答：计算机的硬件系统通常由输入设备、输出设备、运算器、存储器和控制器等五大部件组成。 输入设备的主要功能是将程序和数据以机器所能识别和接受的信息形式输入到计算机内。 输出设备的主要功能是将计算机处理的结果以人们所能接受的信息形式或其它系统所要求的信息形式输出。 存储器的主要功能是存储信息，用于存放程序和数据。 运算器的主要功能是对数据进行加工处理，完成算术运算和逻辑运算。 控制器的主要功能是按事先安排好的解题步骤，控制计算机各个部件有条不紊地自动工作。 1.3 冯·诺依曼计算机的基本思想是什么？什么叫存储程序方式？ 答：冯·诺依曼计算机的基本思想包含三个方面： 1) 计算机由输入设备、输出设备、运算器、存储器和控制器五大部件组成。 2) 采用二进制形式表示数据和指令。 3) 采用存储程序方式。 存储程序是指在用计算机解题之前，事先编制好程序，并连同所需的数据预先存入主存储器中。在解题过程（运行程序）中，由控制器按照事先编好并存入存储器中的程序自动地、连续地从存储器中依次取出指令并执行，直到获得所要求的结果为止。 1.4 早期计算机组织结构有什么特点？现代计算机结构为什么以存储器为中心？ 答：早期计算机组织结构的特点是：以运算器为中心的，其它部件都通过运算器完成信息的传递。 随着微电子技术的进步，人们将运算器和控制器两个主要功能部件合二为一，集成到一个芯片里构成了微处理器。同时随着半导体存储器代替磁芯存储器，存储容量成倍地扩大，加上需要计算机处理、加工的信息量与日俱增，以运算器为中心的结构已不能满足计算机发展的需求，甚至会影响计算机的性能。为了适应发展的需要，现代计算机组织结构逐步转变为以存储器为中心。 1.5 什么叫总线？总线的主要特点是什么？采用总线有哪些好处？ 答：总线是一组可为多个功能部件共享的公共信息传送线路。 总线的主要特点是共享总线的各个部件可同时接收总线上的信息，但必须分时使用总线发送信息，以保证总线上信息每时每刻都是唯一的、不至于冲突。 使用总线实现部件互连的好处： ①可以减少各个部件之间的连线数量，降低成本； ②便于系统构建、扩充系统性能、便于产品更新换代。 1.6 按其任务分，总线有哪几种类型？它们的主要作用是什么？ 答：按总线完成的任务，可把总线分为：CPU内部总线、部件内总线、系统总线、外总线。

计算机原理练习题答案

《计算机原理》练习题 一、填空题 1、为区别不同的进制，在数的末尾用字母表示，二进制为B ，十六进制为H ，十进制为D 。 2、8位二进制数组成一个字节，它是单片机中数的基本单位。 3、硬件技术中三种基本的无源器件是电阻、电容、电感。 4、电感对电流的作用效果可以总结为：阻交流、通直流，交流电流频率越高，电感对电流的阻抗效应越强。 5、电容对电流的作用效果可以总结为：隔直流、通交流，交流电流频率越高，电容对电流的阻抗效应越弱。 6、晶体二极管的一个最重要特征是单向导电。 7、晶体三极管的主要作用是电流放大作用。 8、微机硬件的五大部件是：运算器、控制器、存储器、输入设备和输出设备。 9、单片机又称为微控制器（MCU）。 10、单片机就是在一块芯片上集成了中央处理部件（CPU）、存储器（RAM、ROM）、定时器/计数器和各种输入/输出（I/O）接口等片上外设的微型计算机。 11、单片机构成的四要素是CPU 、ROM 、RAM 和片上外设，它们相互之间通过总线连接。 12、8051单片机是8 位CPU。 13、时钟电路用于产生单片机工作所需要的时钟信号。 14、时钟周期（振荡周期）是指为单片机提供时钟信号的振荡源的周期。 15、机器周期是指单片机完成某种基本操作所需要的时间，它由12 个时钟周期组成。 16、假设单片机时钟频率f=12MHz，则时钟周期为1/12 us，机器周期为1 us。 17、假设单片机时钟频率f=6MHz，则时钟周期为1/6 us，机器周期为2 us。 18、单片机的存储系统包含三大部分：程序存储器（ROM）、数据存储器(RAM) 和特殊功能寄存器(SFR) 。 19、从物理地址空间来看，MCS-51单片机有四个存储器地址空间：即片内ROM 和片外ROM 以 及片内RAM 和片外RAM 。 20、从逻辑上看，单片机存储空间可分为三个部分：64KB程序存储器、256B数据存储器和64KB 数据存储器。 21、在单片机的引脚中，XTAL1和XTAL2用于连接时钟电路。 22、在单片机的引脚中，RESET用于连接复位电路。 23、在单片机的引脚中，EA=1，表示使用内部程序存储器。 24、在单片机的引脚中，EA=0，表示使用外部程序存储器。 25、单片机的时钟电路有：外部时钟电路和内部时钟电路。 26、单片机的并行端口有：P0 、P1 、P2 、P3 。其中P0 端口外接电路时要加上拉电阻，P3 端口主要使用其第二功能。 27、当单片机外接地址总线时，P2 端口作为地址总线高8位，P0 端口作为地址总线低8位。 28、当单片机外扩存储器时，作为数据总线的是P0 端口。 29、单片机复位后，PC= 0000H ，SP= 07H ，P0~P3= 0FFH 。 30、51单片机引脚P3.2的第二功能是：INT0外部中断0输入端，P3.3的第二功能是：INT1外部中断1输入端，P3.4的第二功能是：T0外部计数脉冲输入端0 ，P3.5的第二功能是：T1外部计数脉冲输入端1 。 31、单片机最小系统是能让单片机工作起来的一个最基本的组成电路。 32、C语言程序的基本结构有：顺序结构、选择结构和循环结构。 33、C语言程序中，有且仅有一个main 函数。 34、C程序的基本单位是函数。 35、C语言程序的执行是从main 函数开始，也是在main 函数中结束。 36、在C语言程序的运行过程中，我们称其值不能被改变的量为：常量；其值可以改变的量为：变量。 37、C语言中的变量必须先定义，后使用。 38、C语言规定给变量起名时，只能使用字母、数字、下划线，而且第一个字符不能是数字。 39、C语言中，定义数组a[10]，则数组a的第一个元素是：a[0] ，最后一个元素是a[9] 。 40、C语言中，执行语句：x=7/3;则x的值为：2 。 41、C语言中，执行语句：x=7%3;则x的值为：1 。 42、单片机的片内数据存储器低128单元按照功能不同，可分为工作寄存器区、位寻址区、用户RAM 区

计算理论习题解答

计算理论习题解答 练习 1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题. a. M 1的起始状态是q 1 b. M 1的接受状态集是{q 2} c. M 2的起始状态是q 1 d. M 2的接受状态集是｛q 1，q 4｝ e. 对输入aabb,M 1经过的状态序列是q 1，q 2，q 3，q 1，q 1 f. M 1接受字符串aabb 吗？否 g. M 2接受字符串ε吗？是 1.2 给出练习 2.1中画出的机器M 1和M 2的形式描述. M 1=(Q 1,Σ,δ1,q 1,F 1) 其中 1） Q 1={q 1,q 2,q 3,}; 2） Σ={a,b}; 3） δ1为： a b q 1 q 2 q 3 q 2 q 1 q 3 q 3 q 2 q 1 4） q 1是起始状态 5） F 1={q 2} M 2=(Q 2,Σ,δ2,q 2,F 2) 其中 1） Q 2={q 1,q 2,q 3,q 4}; 2） Σ={a,b}; 3）δ2为： a b q 1 q 2 q 3 q 4 q 1 q 2 q 3 q 4 q 2 q 1 q 3 q 4 3） q 2是起始状态 4） F 2={q 1,q 4} 1.3 DFA M 的形式描述为 ( {q 1，q 2，q 3，q 4，q 5}，{u,d},δ,q 3，{q 3}),其中δ在表2-3中给出。试画出此机器的状态图。 1.6 画出识别下述语言的DFA 的状态图。 a){w | w 从1开始以0结束} b){w | w 至少有3个1} q 1 q 5 q 4 q 2 q 3 u d u u u u d d d d 0 0 1 1 1 0,1 0 0 1 0 0 1 1 0,1

《数值计算方法》试题集及答案

《数值计算方法》复习试题 一、填空题: 1、????? ?????----=410141014A ，则A 的ＬU 分解为 A ??? ?????????=? ?????????? ?。 答案： ?? ????????--??????????--=1556141501 4115401411A 3、1)3(,2)2(,1)1(==-=f f f ,则过这三点的二次插值多项式中2 x 的系数 为 ，拉格朗日插值多项式为 。 答案:-1， )2)(1(21 )3)(1(2)3)(2(21)(2--------= x x x x x x x L 4、近似值*0.231x =关于真值229.0=x 有( 2 )位有效数字； ５、设)(x f 可微,求方程)(x f x =的牛顿迭代格式是( ）； 答案 )(1)(1n n n n n x f x f x x x '--- =+ ６、对1)(3 ++=x x x f ,差商=]3,2,1,0[f ( 1 )，=]4,3,2,1,0[f ( ０ )； 7、计算方法主要研究（ 截断 ）误差和( 舍入 )误差; 8、用二分法求非线性方程 f (x )=0在区间(a ,b )内的根时,二分n 次后的误差限为 （ 1 2+-n a b ); １０、已知f （１）＝2,f (2)=３,ｆ(４)＝5.９，则二次Ne ｗton 插值多项式中x 2系数为 ( ０.15 )； 11、 解线性方程组A x =b 的高斯顺序消元法满足的充要条件为（A 的各阶顺序主子式均 不为零)。 12、 为了使计算 32)1(6 )1(41310-- -+-+ =x x x y 的乘除法次数尽量地少，应将该

计算机操作系统(第四版)课后习题答案第五章

第五章 7.试比较缺页中断机构与一般的中断，他们之间有何明显的区别？ 答：缺页中断作为中断，同样需要经历保护CPU现场、分析中断原因、转缺页中断处理程序进行处理、恢复CPU现场等步骤。但缺页中断又是一种特殊的中断，它与一般中断的主要区别是： （ 1）在指令执行期间产生和处理中断信号。通常，CPU都是在一条指令执行完后去检查是否有中断请求到达。若有便去响应中断；否则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的。 (2)一条指令在执行期间可能产生多次缺页中断。例如，对于一条读取数据的多字节指令，指令本身跨越两个页面，假定指令后一部分所在页面和数据所在页面均不在内存，则该指令的执行至少产生两次缺页中断。 8.试说明请求分页系统中的页面调入过程。 答：请求分页系统中的缺页从何处调入内存分三种情况： （1）系统拥有足够对换区空间时，可以全部从对换区调入所需页面，提高调页速度。在进程运行前将与该进程有关的文件从文件区拷贝到对换区。 （2）系统缺少足够对换区空间时，不被修改的文件直接从文件区调入；当换出这些页面时，未被修改的不必换出，再调入时，仍从文件区直接调入。对于可能修改的，在换出时便调到对换区，以后需要时再从对换区调入。 （3）UNIX 方式。未运行页面从文件区调入。曾经运行过但被换出页面，下次从对换区调入。UNIX 系统允许页面共享，某进程请求的页面有可能已调入内存，直接使用不再调入。 19.何谓工作集？它是基于什么原理确定的？ 答：工作集：在某段时间间隔里，进程实际所要访问页面的集合。 原理：用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。 24.说明请求分段式系统中的缺页中断处理过程。 答：在请求分段系统中，每当发现运行进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入操作系统后由缺段中断处理程序将所需的段调入内存。缺段中断机构与缺页中断机构类似，它同样需要在一条指令的执行期间，产生和处理中断，以及在一条指令执行期间，可能产生多次缺段中断。

信息与编码理论课后习题答案

二章-信息量和熵习题解 2.1 莫尔斯电报系统中，若采用点长为0.2s ，1划长为0.4s ，且点和划出现的概率分别为2/3和1/3，试求它的信息速率(bits/s)。 解: 平均每个符号长为: 15 44.0312.032=?+?秒 每个符号的熵为9183.03log 3 123log 32=?+?比特/符号 所以，信息速率为444.34159183.0=?比特/秒 2.2 一个8元编码系统，其码长为3，每个码字的第一个符号都相同(用于同步)，若每秒产生1000个码字，试求其信息速率(bits ／s)。 解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特； 所以，信息速率为600010006=?比特/秒 2.3 掷一对无偏的骰子，若告诉你得到的总的点数为：(a ) 7；(b ) 12。 试问各得到了多少信息量? 解: (a)一对骰子总点数为7的概率是 36 6 所以，得到的信息量为 585.2)36 6(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以，得到的信息量为 17.5361log 2= 比特 2.4 经过充分洗牌后的一付扑克(含52张牌)，试问： (a) 任何一种特定排列所给出的信息量是多少? (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量? 解: (a)任一特定排列的概率为! 521, 所以，给出的信息量为 58.225!521log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1313 1313525213!44A C ?=

所以，得到的信息量为 21.134 log 1313522=C 比特. 2.5 设有一个非均匀骰子，若其任一面出现的概率与该面上的点数成正比，试求各点 出现时所给出的信息量，并求掷一次平均得到的信息量。 解:易证每次出现i 点的概率为 21i ,所以 比特比特 比特 比特 比特 比特 比特 398.221 log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21 log )(2612=-==============-==∑=i i X H x I x I x I x I x I x I i i i x I i 2.6 园丁植树一行，若有3棵白杨、4棵白桦和5棵梧桐。设这12棵树可随机地排列， 且每一种排列都是等可能的。若告诉你没有两棵梧桐树相邻时，你得到了多少关 于树的排列的信息? 解: 可能有的排列总数为 27720! 5!4!3!12= 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦，它有???? ??37种排法，Y 表示梧桐树可以栽种的位置，它有? ??? ??58种排法， 所以共有???? ??58*??? ? ??37=1960种排法保证没有两棵梧桐树相邻， 因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-=3.822 比特 2.7 某校入学考试中有1/4考生被录取，3/4考生未被录取。被录取的考生中有50%来 自本市，而落榜考生中有10％来自本市，所有本市的考生都学过英语，而外地落榜考生中以及被录取的外地考生中都有40%学过英语。 (a) 当己知考生来自本市时，给出多少关于考生是否被录取的信息?

计算理论习题答案CHAP2new

计算理论习题答案CHAP2new

2.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例 3.20，证 明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10)，证明上下文无关语言在补运算下不封闭。 证明：a.先说明A,B 均为上下文无关文法，对A 构造CFG C 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言，所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭，则对于(a)中上下文无关语言A,B ， A , B 也为CFL ，且CFL 对并运算封闭，所以B A ?也为CFL ，进而知道B A ?为CFL ，由DeMorgan 定律 B A ?＝A ∩B ，由此A ∩B 是CFL,这与(a)的结论矛盾，所以CFL 对补运算不封闭。 2.4和2.5 给出产生下述语言的上下文无关文法和PDA ，其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε ε,1→ 1, 0, ε,1→ ε,1→

b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A d. {w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0 e. {w | w 中1比0多} S →A1A 1,ε→ 0,ε→0,ε→1,1→ 0,0→0,ε→1,ε→0,ε→0,ε→ 0,ε→0,0→ε,ε→ ε,$→