下载文档原格式
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<b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为i+1, 转第2步；5)若当前地址位为i＝b，且当前选择无效或按当前选择进入拒绝状态，则将当前地址位改为空格, 左移并将当前地址位改为空格直到找到一个地址位其值<b，将当前地址位改为i+1, 转第2步；若到了地址带的最左端仍有当前地址位为b，则拒绝；6)若N进入接受状态，则接受；否则，右移一格，将空格上写入1，转第三步。
”由于N是非确定型判定器，所以对任意输入，由本题的提示M一定会停机。
3.4给出枚举器的形式定义。
解：枚举器E=(Q,∑,Γ,δ,q0,qaccept,qreject), 其中转移函数δ为：δ：Q×Γ→Q×Γ×{L,R}×∑*δ (q,a)=(r,b,s1,c)表示若E处于状态q,且在工作带上读到a，则状态转移为r，当前格改写为b并按s1作相应左或右移，打印带上写下字符串c，其中若c等于ε，则不打印。
另外E的起始格局只能是qv，这里v表示一个空格。
3.5检查图灵机的形式定义，回答下列问题并解释你的推测：a．图灵机能在它的带子上写下空白符吗b．带字母表Γ和输入字母表∑能相同吗？c．图灵机的读写头能在连续的两步中处于同一个位置吗？d．图灵机能只包含一个状态吗？解：a．能。
1、一个算法的优劣可以用（时间复杂度）与（空间复杂度）与来衡量。
2、回溯法在问题的解空间中，按（深度优先方式）从根结点出发搜索解空间树。
3、直接或间接地调用自身的算法称为（递归算法）。
4、 记号在算法复杂性的表示法中表示（渐进确界或紧致界）。
5、在分治法中，使子问题规模大致相等的做法是出自一种（平衡(banlancing)子问题）的思想。
6、动态规划算法适用于解（具有某种最优性质）问题。
7、贪心算法做出的选择只是（在某种意义上的局部）最优选择。
8、最优子结构性质的含义是（问题的最优解包含其子问题的最优解）。
9、回溯法按（深度优先）策略从根结点出发搜索解空间树。
10、拉斯维加斯算法找到的解一定是（正确解）。
11、按照符号O的定义O(f)+O(g)等于O(max{f(n),g(n)})。
12、二分搜索技术是运用（分治）策略的典型例子。
13、动态规划算法中，通常不同子问题的个数随问题规模呈（多项式）级增长。
14、（最优子结构性质）和（子问题重叠性质）是采用动态规划算法的两个基本要素。
15、（最优子结构性质）和（贪心选择性质）是贪心算法的基本要素。
16、（选择能产生最优解的贪心准则）是设计贪心算法的核心问题。
17、分支限界法常以（广度优先）或（以最小耗费(最大效益)优先）的方式搜索问题的解空间树。
18、贪心选择性质是指所求问题的整体最优解可以通过一系列（局部最优）的选择，即贪心选择达到。
19、按照活结点表的组织方式的不同，分支限界法包括（队列式(FIFO)分支限界法）和（优先队列式分支限界法）两种形式。
20、如果对于同一实例，蒙特卡洛算法不会给出两个不同的正确解答，则称该蒙特卡洛算法是（一致的）。
21、哈夫曼编码可利用（贪心法）算法实现。
22概率算法有数值概率算法，蒙特卡罗（Monte Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法23以自顶向下的方式求解最优解的有（贪心算法）24、下列算法中通常以自顶向下的方式求解最优解的是（C）。
工程测量理论计算习题库（含参考答案）一、单选题（共60题，每题1分，共60分）1、大坝变形测量中、视准线法可以用来测定坝体的( )。
A、水平位移B、垂直位移C、主体倾斜D、挠度正确答案：A2、已知某图幅的编号为H49 G 041095、则该地形图的比例尺为( )。
A、1:5000B、1:1万C、1:25万D、1:100万正确答案：B3、在水准测量中、若后视点A的读数大、前视点B的读数小、则有( )。
A、A点比B点低B、A点比B点高C、A点与B点可能同高D、A,B点的高低取决于仪器高度正确答案：A4、我国目前采用的高程系统是( )。
A、1956年黄海高程系B、大沽高程系C、1985国家高程基准D、2000国家高程基准正确答案：C5、甲水准仪管水准器分划值为20″、乙水准仪管水准器分划值为30″、则两台仪器的整平精度( )。
A、无法确定B、甲高于乙C、甲乙相等D、乙高于甲正确答案：B6、在进行高程控制测量时、对于地势比较平坦地区、一般采用( )。
A、水准测量B、GPS测高C、视距测量D、三角高程测量正确答案：A7、水平角测量通常采用测回法进行、取符合要求的上下半测回平均值作为最终角度测量值、这一操作可以消除的误差是( )。
A、整平误差B、对中误差C、视准误差D、读数误差正确答案：C8、建筑施工测量中、基坑抄平工作的目的是( )A、对基坑回弹进行监测B、基坑中轴线测设C、放样基坑开挖边线D、控制基槽开挖深度正确答案：D9、根据全站仪坐标测量的原理、在测站点瞄准后视点后、方向值应设置为( )。
A、90°B、0C、测站点至后视点的方位角D、后视点至测站点的方位角正确答案：C10、目前我国数据采集主要有GPS法、大地测量仪器法、数字化仪法和( )。
A、航测法B、全站仪法C、遥感法D、平板制图法正确答案：A11、某导线全长620m、算得fx=0.123m、fy=-0.162m、导线全长相对闭合差=K( )。
计算理论习题答案计算理论，也称为理论计算机科学，是研究算法和计算过程的数学理论基础的学科。
以下是一些计算理论习题的答案示例：1. 确定性图灵机（Deterministic Turing Machine, DTM）：- 习题：证明一个确定性图灵机可以模拟任何其他确定性图灵机。
- 答案：确定性图灵机可以读取输入，根据当前状态和读取到的符号，按照预定的转移规则移动磁带头并改变状态。
要模拟另一台确定性图灵机，只需要将被模拟机的状态转移表编码为模拟机的转移规则即可。
2. 非确定性图灵机（Nondeterministic Turing Machine, NTM）：- 习题：证明非确定性图灵机比确定性图灵机更强大。
- 答案：非确定性图灵机可以在多个可能的转移中选择，这使得它能够解决一些确定性图灵机无法解决的问题，例如哈密顿回路问题。
此外，任何确定性图灵机都可以被一个非确定性图灵机模拟，但反之则不成立。
3. 可计算性（Computability）：- 习题：证明某个特定的函数是可计算的。
- 答案：要证明一个函数是可计算的，需要展示一个算法或图灵机，它对于该函数的任何输入都能在有限步骤内给出输出。
例如，一个简单的加法函数f(x, y) = x + y是可计算的，因为它可以通过迭代或递归来实现。
4. 不可解问题（Undecidable Problems）：- 习题：解释停机问题（Halting Problem）为什么是不可解的。
- 答案：停机问题是不可解的，因为它涉及到预测一个图灵机是否会在有限步骤内停止。
如果存在一个算法能够解决停机问题，那么我们可以构造一个悖论，即一个图灵机可以模拟自身并决定自己是否会停止，这会导致自指的悖论。
5. 复杂性类（Complexity Classes）：- 习题：区分P类问题和NP类问题。
- 答案：P类问题是指可以在多项式时间内解决的问题，而NP类问题是指可以在多项式时间内验证一个解的问题。
第三章 上下文无关语言与下推自动机a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|εb. {w | w 以相同的符号开始和结束}S →0A0|1A1 A →0A|1A|εc. {w | w 的长度为奇数}0, ε→ε0,ε→ε 0,ε→ε1,ε→ε0,ε→εS →0A|1A A →0B|1B|ε B →0A|1Ad.{w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0e.{w | wS →A1AA →0A1|1A0|1A|AA|εf.{w | w=w R }S →0S0|1S1|1|0g.空集 S →S3.6 给出产生下述语言的上下文无关文法： a ． 字母表{a,b}上a 的个数是b 的个数的两倍的所有字符串组成的集合。
S →bSaSaS|aSbSaS|aSaSbS|εb ．语言{a n b n |n ≥0}的补集。
见问题3.25中的CFG: S →aSb|bY|Ta T →aT|bT|εc ．{w#x | w, x ∈{0,1}*且w R 是x 的子串}。
S →UV0,ε→0,0→0,ε→1,0→0,1→0,ε→0,0→U→0U0|1U1|WW→W1|W0|#V→0V|1V|εd．{x1#x2#⋯#x k|k≥1, 每一个x i∈{a,b}* , 且存在i和j使得x i＝x j R}。
S→UVWU→A|εA→aA|bA|#A|#V→aVa|bVb|#B|#B→aB|bB|#B|#W→B|ε3.14解：添加新起始变元S0, 去掉B→εS0→A S0→AA→BAB|B|εA→BAB|AB|BA|B|εB→00|εB→00去掉A→ε, 去掉A→BS0→A S0→AA→BAB|AB|BA|B|BB A→BAB|AB|BA|00|BBB→00 B→00去掉S0→A, 添加新变元S0→BAB|AB|BA|00|BB S0→VB|AB|BA|UU|BBA→BAB|AB|BA|00|BB A→VB|AB|BA|UU|BBB→00 B→UUV→BAU→03.15 证明上下文无关语言类在并,连接和星号三种正则运算下封闭---答案。
注意一些上标,也就是指数,109为10的9次方《计算机网络习题与解答》鲁士文编习题一1．在下列情况下，计算传送1000KB 文件所需要的总时间，即从开始传送时起直到文件的最后一位到达目的地为止的时间。
假定往返时间RTT 是100 毫秒，一个分组是1KB（即1024 字节）的数据，在开始传送整个的文件数据之前进行的起始握手过程需要2×RTT的时间。
（a）带宽是1.5Mbps，数据分组可连续发送。
解答：2 个起始的RTT：100×2=200 毫秒传输时间：RTT÷2=100÷2=50 毫秒1KB=8 比特×1024=8192 比特发送时间：1000KB÷1.5Mbps=8192000 比特÷1500，000 比特/秒=5.46 秒所以，总时间等于0.2+5.46+0.05=5.71 秒。
（b）带宽是1.5Mbps，但在结束发送每一个数据分组之后，必须等待一个RTT 才能发送下一个数据分组。
解答：在上一小题答案的基础上再增加999 个RTT5.71+999×0.1=105.61 秒所以，总时间是105.61 秒。
（c）带宽是无限大的值，即我们取发送时间为0，并且在等待每个RTT 后可发送多达20 个分组。
解答：1000KB÷1KB=1000 分组1000 分组÷20 分组=50 个RTT50-1=49 个RTT2×RTT+49RTT+0.5RTT=51.5RTT=0.1×51.5=5.15 秒。
（d）带宽是无限大的值，在紧接起始握手后我们可以发送一个分组，此后，在第一次等待RTT 后可发送21 个分组，在第二次等待RTT 后可发送22 个分组，。
，在第n 次等待RTT 后可发送2n 个分组。
解答：取n=91+2+4+⋯+29=29+1-1=1023这样我们就可以发送所有的1000 个分组，而且在第9 次等待RTT 后只须发送。
计算理论习题解答练习1.1图给出两台DFA M i和M2的状态图•回答下述有关问题•a. M 1的起始状态是q1b. M1的接受状态集是{q2}c. M2的起始状态是q1d. M2的接受状态集是{ q1, q4)e. 对输入aabb,M1经过的状态序列是q1, q2, q3, q1, q1f. M 1接受字符串aabb吗？否g. M 2接受字符串£吗？是1.2给出练习2.1中画出的机器M1和M2的形式描述M 1=(Q 1,2,3 1,q1,F1)其中1) Q1={q 1,q2,q3,};2) 2 ={a,b};3) 3 1 为：a bq1q2 q1q2q3 q3q3q2 q14) q15) F1={q 2}M2=(Q2,2,3 2,q2,F2)其中1) Q2={q 1,q2,q3,q4};2) 2 ={a,b};3) 3 2为：a bq1q1 q2q2q3 q4q3q2 q1q4q3 q43) q2是起始状态4) F2={q 1,q4}1.3 DFA M 的形式描述为({q1, q2, q3, q4, 机器的q5}, {u,d}, 3 ,q3, {q3}),其中3在表2-3中给出。
试画出此状态图。
1.6画出识别下述语言的DFA的状态图。
a){w | w从1开始以0结束}c) {w | w含有子串0101}彳 c n 1d) {w | w的长度不小于3,且第三个符号为0}0,1,1g) {w | w 的长度不超过 5}0,10,10,1h){w | wi){w | w 的奇位置均为1}k) { 2}斗「0,11I) {w | w 含有偶数个0，或恰好两个1}1 - 1 . 10 00 1m)空集 _0,1n)除空串外的所有字符串1.7给出识别下述语言的 NFA ，且要求符合规定的状态数。
a. {w | w以00结束}，三个状态0,1b. 语言{ w | w含有子串0101，即对某个x和y, w=x0101y }, 5个状态.c. 语言{ w | w含有偶数个0或恰好两个1}, 6个状态。
1 1d. 语言{ 0}, 2个状态。
e. 语言0*1*0*0, 3个状态。
g.语言0 , 1个状态。
一 6。
2.11证明每一台NFA都能够转换成等价的只有一个接受状态的NFA。
证明：设NFA M={Q , 2, ,q°,F} , F={r i1，……，5}.添加一个状态p后，m……，环分别向p引&箭头，将r i1, —, r ik变为非接受状态，p变为接受状态。
又因为添加&箭头不影响NFA识别语言，所以命题成立。
2.14 a证明：设M是一台语言B的DFA，交换M的接状态与非接受状态得到一台新的DFA，则这台新的DFA是识别B的补集，因此，正则语言类受在补运算下封闭。
b举例说明：设M是一台识别语言B的NFA，交换M的接受状态与非接受状态得到一台新的NFA , 这台新的NFA不一定识别B的补集。
NFA识别的语言类在补集下封闭吗？解释你的回答。
解：a. M是DFA, M是{Q,刀,S ,q°,F},令N={Q,刀,S ,q0,Q-F},设沪w血…伽是字母表上任意字符串，因为M 与N 均为DFA,所以必然存在 Q 中状态序列r o ,r i ,…,n ,使得：r o =q o , S (仃，Q +i )=r i+i ,i=0,…,n-1 1) 若5三F 贝U 3 B;2) 若rMF 则rn ・Q-F,即N 接受3,若 3B, 所以N 接受B 的补集，即B 的补集正则。
所以，正则语言类在补运算下封闭。
b. 设 B 为｛0｝。
NFA M : 可识别它。
依题对它作变换，得到 N :识别B 的补集。
但是由于NFA 识别的语言类与 DFA 识别的语言类相同，即正则语言类。
由 在补运算封闭，可知，NFA 识别的语言类---正则语言类在补运算下封闭。
若NFA 识别语言A ，必有等价的DFA 识别A,从而由a 知，可交换DFA 的接受与非接受状态构造 识别A 的补集的DFA,则必有等价的NFA 识别A 的补集。
只是，该NFA 未必有原NFA 交换接受与 非接受状态构造而成。
1.15给出一个反例，说明下述构造不能证明定理2.24，即正则语言类在星号运算下封闭。
设 N= (Q i ,羽i,q i ,F i )识别A 1。
如下构造N= (Q 1,声1,q 1,F 1)。
N 应该识别A 「。
a. N 的状态集是N 1的状态集。
b. N 的起始状态是 N 1的起始状态相同。
c. F= ｛qd U F 1。
F 的接受状态是原来的接受状态加上它的起始状态。
d. 定义3如下：对每一个 q 属于Q 和每一个a 属于2d(q,a), 若q 老 R 或 a ®<d(q,a2{q 1},若q 迂 R 且a n解：设M 识别语言A=｛至少含有一个1｝，其中输入字母表为｛0 , 1｝，可知A *=｛空串或至少含有一个 1｝。
1.16使用定理2.19中给出的构造，把下图中的两台非确定型有穷自动机转换成等价的确定型有穷自动机。
则N 识别的语言｛ £｝不是B 的子集。
所以交换 M 的接受状态与非接受状态得到的新的 NFA 不一定a 的证明，正则语言类(q,a)按上述规定构造N 的状态图如上。
可以看出b),N 不一定识别A *.a),解：a).b)a), b),2.13给出生成练习 2.4中语言的正则表达式。
(注：答案不唯一)a. {w I w 从1开始以0结束} 1 X 0. b. {w I w 至少有 3个1}丈1丈1工*1 c. {w | w 含有子串 0101} X 0101 X .d. {w | w 的长度不小于 3,且第三个符号为 0} XXX .e. {w I w 从0开始且为奇长度，或从 1开始且为偶长度 } 0( XX * _.1 X XX *.f.{w I w 不含子串 110} (0 10)*1*.g. {w | w 的长度不超过 5} . X_. XX.XXXXXXXXX X X h. {w I w 是除11和111以外的任何字符} 0丈.102* .110 X * .111X *. i. {w | w 的奇位置均为 1} (1 X )*( ■■一 1).j. {w | w 至少含有 2个0,且至多含有 1个1} 0*(00 一010 一001 一 100) 0*. k. { §0}. £ .Q l.{w I w 含有偶数个 0，或恰好两个 1} (1 *01*0)*1* 一 0*10*10*.m. 空集.■：'.n. 除空串外的所有字符串 X Q1.19对下述每一个语言，给出 4个字符串， 2个是这个语言的成员，2个不是这个语言的成员。
这里假设字母表2={a,b}.* *a. a b 成员：ab , aab 非成员：aba, ba *b. a(ba)成员： ab , abab 非成员：abb , aa * *c. a 5成员：a aa, bbb 非成员：ab , ba d. (aaa) 成员： a aa, aaaaaa非成员：a , aa* * * * e.X a X b X a X成员：a ba, aaba 非成员：aa , abb f. aba _ bab 成员： aba , bab 非成员：a , b g. ( -a)b成员： b , ab 非成员：a , bb h. (a _ba _bb) £成员 a, bb非成员：；，b1.21使用引理2.32中叙述的过程，把图2-38中的有穷自动机转换成正则表达式。
. * * *解: a) a b(a ba b)* * *b)su(ajb)a b[(aaja2b)a b] (ay).(注：答案不唯一)1.29利用泵引理证明下述语言不是正则的。
n n na. A i={0 1 2 | n_0}。
证明：假设A i是正则的。
设p是泵引理给出的关于A i的泵长度。
ppp令S=0 1 2 ,••• S是A i的一个成员且S的长度大于p,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3 个条件。
根据条件3, y中只含0, xyyz中，0比1、2多，xyyz不是A1的成员。
违反泵引理的条件1，矛盾。
••• A1不是正则的。
*b. A2={www | w w{a,b} }.证明：假设A2是正则的。
设p是泵引理给出的关于A2的泵长度。
人ppp令S=a ba ba b,••• S是A2的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3 个条件。
根据条件3, y中只含a,所以xyyz中第一个a的个数将比后两个a的个数多，故xyyz 不是A2的成员。
违反泵引理的条件1,矛盾。
•A2不是正则的。
2门2门一nc. A3={a | n _0}.(在这里，a表示一串2个a .)证明：假设A3是正则的。
设p是泵引理给出的关于A3的泵长度。
令S= a2P,••• S是A2的一个成员且S的长度大于P,所以泵引理保证S可被分成3段S=xyz且满足泵引理的3 个条件。
即对任意的「_0, xy i z都应在A3中，且xy"z与xy i+1 z的长度都应是2的幕.而且xy i+1z的长度应是xy i z的长度的2倍(n _1)。
于是可以选择足够大的i,使得|xy i z|=2 >p.但是|xy i+ z|-|xy i z|=|y^p.n+1即|xy z|<2 ,矛盾。
•A3不是正则的。
1.30下面“证明” 0*1*不是正则语言，指出这个“证明”中的错误。
(因为0*1*是正则的，所以一定错误。
)采用反证法证明。
假设0*1*是正则的。
令P是泵引定理给出的关于0*1*的泵长度。
取S为字符串0p1p。
S 是0*1*的一个成员，但是例2.38已证明S不能被抽取。
于是得到矛盾，所以0*1*不是正则的。
n n p p * * 解：在例2.38中的语言是{0 1 | n_0}，取S为字符串0 1 , S确实不能被抽取；但针对语言0 1 , S,■_ i * *是能被抽取的。
将S分成三段S=xyz，由泵引理的条件3, y仅包含0,而xyz属于语言0 1，即卩S 能被抽取，故题设中的“证明”不正确。
1.24有穷状态转换器(FST)是确定性有穷自动机的一种类型。
它的输出是一个字符串，而不仅仅是接受或拒绝。
图2—39是两台有穷状态状态转换器T1和T2的状态图。
FST的每一个转移用两个符号标记，一个指明该转移的输入符号，另一个指明输出符号。
两个符号之间用斜杠“/”把它们分开。
在T1中，从q1到q2的转移有输入符号2和输出符号1。
某些转移可能有多对输入-输出，比如T1中从q1到它自身的转移。
