下载文档原格式
《大学计算机基础与计算思维》课后习题参考答案目录第1章计算、计算机与计算思维 (1)第2章数据的计算基础 (3)第3章计算机硬件系统 (5)第4章操作系统基础 (9)第5章算法与数据结构 (11)第6章程序设计及软件工程基础 (14)第7章数据库技术 (16)第8章计算机网络 (19)第9章信息安全与职业道德 (21)第10章计算软件 (24)第11章办公软件Office 2010 (25)算机科学与技术学院计算机基础教学部2015年9月第1章计算、计算机与计算思维1.1 举例说明可计算性和计算复杂性的概念。
答：对于给定的一个输入，如果计算机器能在有限的步骤内给出答案，这个问题就是可计算的。
数值计算、能够转化为数值计算的非数值问题（如语音、图形、图像等）都是可计算的。
计算复杂性从数学上提出计算问题难度大小的模型，判断哪些问题的计算是简单的，哪些是困难的，研究计算过程中时间和空间等资源的耗费情况，从而寻求更为优越的求解复杂问题的有效规则，例如著名的汉诺塔问题。
1.2 列举3种电子计算机出现之前的计算工具，并简述其主要特点。
答：（1）算盘通过算法口诀化，加快了计算速度。
（2）帕斯卡加法器通过齿轮旋转解决了自动进位的问题。
（3）机电式计算机Z-1，全部采用继电器，第一次实现了浮点记数法、二进制运算、带存储地址的指令等设计思想。
1.3 简述电子计算机的发展历程及各时代的主要特征。
答：第一代——电子管计算机（1946—1954年）。
这个时期的计算机主要采用电子管作为运算和逻辑元件。
主存储器采用汞延迟线、磁鼓、磁芯，外存储器采用磁带。
在软件方面，用机器语言和汇编语言编写程序。
程序的编写与修改都非常繁琐。
计算机主要用于科学和工程计算。
第二代——晶体管计算机（1954—1964年）。
计算机逻辑元件逐步由电子管改为晶体管，体积与功耗都有所降低。
主存储器采用铁淦氧磁芯器，外存储器采用先进的磁盘，计算机的速度和可靠性有所提高。
![大数据计算理论基础[2014-05]](https://img.taocdn.com/s1/m/94c241fd4693daef5ef73d73.png)
计算理论习题答案计算理论，也称为理论计算机科学，是研究算法和计算过程的数学理论基础的学科。
以下是一些计算理论习题的答案示例：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类问题是指可以在多项式时间内验证一个解的问题。
计算方法（C）目录第1章绪论1.1 数值计算1.2 数值方法的分析1.2.1计算机上数的运算1.2.2算法分析第2章线性代数方程组2.1 Gauss消去法2.1.1消去法2.1.2主元消去法2.2 矩阵分解2.2.1Gauss消去法的矩阵意义2.2.2矩阵的LU分解及其应用2.2.3其他类型矩阵的分解2.2.4解三对角矩阵的追赶法2.3线性方程组解的可靠性2.3.1向量和矩阵范数2.3.2残向量与误差的代数表征2.4解线性方程组解的迭代法2.4.1基本迭代法2.4.2迭代法的矩阵表示2.4.3收敛性第3章数据近似3.1 多项式插值3.1.1插值多项式3.1.2Lagrange插值多项式3.1.3Newton插值多项式3.1.4带导数条件的插值多项式3.1.5插值公式的余项3. 2 最小二乘近似3.2.1 最小二乘问题的法方程3.2.2 正交化算法第4章数值微积分4.1 内插求积，Newton-Cotes公式4.1.1Newton-Cotes公式4.1.2复化求积公式4.1.3步长的选取4.1.4Romberg方法4.1.5待定系数法4.2数值微分4.2.1插值公式方法4.2.2Taylor公式方法(待定系数法)4.2.3外推法第5章非线性方程求解5.1 解一元方程的迭代法5.1.1简单迭代法5.1.2Newton法5.1.3割线法5.1.4区间方法5.2 收敛性问题5.2.1简单迭代——不动点5.2.2收敛性的改善5.2.3Newton法的收敛性5.2.4收敛速度第1章绪论1.1数值计算现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。
通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。
一、本课程的任务：寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学（算术）的方法求解——了解计算的基础方法，基本结构（否则只须知道数值软件）——并研究其性质。
可计算性与计算复杂性1.可计算性：可计算性研究的是什么样的问题可以通过其中一种计算模型解决。
早期的计算模型是图灵机（Turing machine），后来发展出其他等效的计算模型，例如递归函数、Lambda演算等。
根据这些计算模型，可以定义一类问题为可计算问题，也就是可以通过计算模型求解的问题。
1.1停机问题：停机问题是可计算性的典型例子，它是指根据给定的程序和输入，判断这个程序是否会在有限的时间内停止运行。
根据图灵在20世纪30年代证明的停机问题的不可判定性，他证明了不存在一个通用的算法能够判断任意程序是否停机，这个结论被称为图灵不可判定性定理。
1.2基本计算问题：除了停机问题，可计算性还研究了一些其他的基本计算问题。
例如，可计算性研究了自动机是否可以接受一些字符串，或者函数是否可以被一个特定的计算模型计算等。
1.3计算模型的等效性：在可计算性理论中，研究了不同计算模型之间的等效性。
图灵机、递归函数和Lambda演算等计算模型之间可以相互转化，这意味着它们的计算能力是等价的。
这个等价性的概念对理解可计算性是至关重要的。
2.计算复杂性：计算复杂性研究的是什么样的问题可以在多项式时间内解决，以及在不同条件下求解问题所需要的计算资源（例如时间、空间等）。
计算复杂性理论的核心是研究问题的复杂度类别和难度。
2.1多项式时间可解问题：计算复杂性理论将问题分为多项式时间可解问题和非多项式时间可解问题。
多项式时间可解问题是指那些可以在多项式时间内求解的问题。
这些问题的解决方法被认为是高效的，因为随着输入规模的增加，所需计算资源的增长是可接受的。
2.2难解问题：非多项式时间可解问题是那些不可以在多项式时间内求解的问题。
例如，图的旅行商问题（TSP）和布尔可满足性问题（SAT）等问题被认为是难解问题。
难解问题的求解需要指数级的时间或空间复杂度，因此在实际中很难找到有效的算法。
2.3复杂度类别：计算复杂性理论还研究了不同问题的复杂度类别。
计算复杂性一、引言计算问题，应该是一种从人类有文明起便一直纠缠着人类的问题；为了解决这些问题，人类需要进行计算，需要设计算法。
显然，如果时间是无限的，计算机器性能也是无比的，那么选择什么算法并不是问题；但这不可能。
人类计算的时间是有限的，人类的计算设备也不是万能的。
因此，我们需要评判一种算法的复杂性。
那么，计算复杂性到底是什么，它的意义是什么，它的进展如何，应用如何，本文试图进行一部分回答。
二、相关概念1.计算复杂性、时间复杂性、空间复杂性：计算复杂性包括两个方面：时间复杂性，空间复杂性。
时间复杂性反映了问题计算所需的时间耗费, 一般是用计算的运算次数来衡量。
空间复杂性则代表进行计算需要耗费的存储空间。
例如，我们C语言作业的在线测评系统之中，会有内存和用时的要求；这两个方面分别体现了空间复杂性和时间复杂性。
2.多项式时间、指数时间：多项式时间指的是一种算法的时间复杂度可以用含有n的一个多项式表示。
这种情况下一般把操作数作为时间复杂度的衡量标准。
而指数时间指的是一种算法的时间复杂性不能够用多项式进行表示。
指数时间的算法效率较低，而且随着n的增大用时显著增加，被认为是相当于不存在的算法。
3.确定性图灵机、非确定性图灵机：两者都为图灵机模型；但是确定性图灵机在一定的条件下，只会选择一种操作；而非确定性图灵机则会根据生成的（伪）随机数在多种方法中选择一种进行。
4.P问题、NP问题、NPC问题：NP是指“在非确定性图灵机上有多项式时间算法的问题”的集合，而P是指“在确定性图灵机上有多项式时间算法的问题”的集合。
另外一种表述是，P问题在多项式时间内可以解决，而NP问题在多项式时间内可以得到检验。
P问题是NP问题的特例，而往往NP问题都被视作【但未被证明为】“不可”解决的问题。
经过多项式变换能够变成所有NP问题的问题称为NPC问题。
三、特色思想进行问题求解时，人们往往会关心：1.这个问题能否被算法求解；2.求解问题的过程需要消耗什么？而这正是计算复杂性研究的内容。
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}i){w | w 的奇位置均为1}j) {w | w 至少含有2个0，且至多含有1个1}k) {ε,0}0,11l) {w | w 含有偶数个0，或恰好两个1}m) 空集 n) 除空串外的所有字符串1.29利用泵引理证明下述语言不是正则的。
a. A 1={0n 1n 2n| n ≥0}。
证明：假设A 1是正则的。
设p 是泵引理给出的关于A 1的泵长度。
令S=0p 1p 2p,∵S 是A 1的一个成员且S 的长度大于p ，所以泵引理保证S 可被分成3段S=xyz 且满足泵引理的3个条件。
根据条件3，y 中只含0，xyyz 中，0比1、2多，xyyz 不是A 1的成员。
违反泵引理的条件1，矛盾。
∴A 1不是正则的。
b. A 2={www | w ∈{a,b}*}.证明：假设A 2是正则的。
设p 是泵引理给出的关于A 2的泵长度。
令S=a pba pba pb,∵S 是A 2的一个成员且S 的长度大于p ，所以泵引理保证S 可被分成3段S=xyz 且满足泵引理的3个条件。
根据条件3，y 中只含a ，所以xyyz 中第一个a 的个数将比后两个a 的个数多，故xyyz 不是A 2的成员。
违反泵引理的条件1，矛盾。
∴A 2不是正则的。
c. A3={a2n | n≥0}.(在这里，a2n表示一串2n个a .)证明：假设A3是正则的。
设p是泵引理给出的关于A3的泵长度。
令S= a2p，∵S是A2的一个成员且S的长度大于p，所以泵引理保证S可被分成3段S=xyz且满足泵引理的3个条件。
即对任意的i≥0，xy i z都应在A3中，且xy i z与xy i+1z的长度都应是2的幂. 而且xy i+1z的长度应是xy i z的长度的2n倍(n≥1)。
于是可以选择足够大的i，使得|xy i z|=2n>p. 但是|xy i+1z|-|xy i z|=|y|≤p. 即|xy i+1z|<2n+1, 矛盾。
∴A3不是正则的。
1.46 证明：a)假设{0n1m0n|m,n≥0}是正则的，p是由泵引理给出的泵长度。
取s＝0p1q0p，q>0。
由泵引理条件3知，|xy|≤p，故y一定由0组成，从而字符串xyyz中1前后0的数目不同，即xyyz不属于该语言，这与泵引理矛盾。
所以该语言不是正则的。
b) 假设{0n1n|n≥0}的补集是正则的，则根据正则语言在补运算下封闭可得{0n1n|n≥0}是正则的，这与已知矛盾，故假设不成立。
所以该语言不是正则的。
c) 记c={0m1n|m≠n}，┐c为c的补集，┐c∩0*1*={0n1n|n≥0}，已知{0n1n|n ≥0}不是正则的。
若┐c是正则的，由于0*1*是正则的，那么┐c∩0*1*也应为正则的。
这与已知矛盾，所以┐c不是正则的。
由正则语言在补运算下的封闭性可知c也不是正则的。
d) {w | w∈{0,1}*不是一个回文}的补集是{w | w∈{0,1}*是一个回文}，设其是正则的，令p是由泵引理给出的泵长度。
取字符串s=0p1q0p，显然s是一个回文且长度大于p。
由泵引理条件3知|xy|≤p，故y只能由0组成。
而xyyz不再是一个回文，这与泵引理矛盾。
所以{w | w∈{0,1}*是一个回文}不是正则的。
由正则语言在补运算下的封闭性可知{w | w∈{0,1}*不是一个回文}也不是正则的。
2.4和2.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|1Ad. {w | w 的长度为奇数且正中间的符号为0}S →0S0|1S1|0S1|1S0|0e. {w | w 中1比0多}S →A1AA →0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε0,ε→ε 0,ε→0 0,0→ε 0,ε→0 1,0→ε 0,1→εf. {w | w=w R }S →0S0|1S1|1|0 g. 空集S →S2.15 用定理2.6中给出的过程，把下述CFG 转换成等价的乔姆斯基范式文法。
A →BAB|B|εB →00|ε解：添加新起始变元S 0,去掉B →ε S 0→AS 0→AA →BAB|B|ε A →BAB|AB|BA|B|εB →00|εB →00去掉A →ε, 去掉A →B S 0→AS 0→AA →BAB|AB|BA|B|BB A →BAB|AB|BA|00|BB B →00B →00去掉S 0→A,添加新变元 S 0→BAB|AB|BA|00|BB S 0→VB|AB|BA|UU|BB A →BAB|AB|BA|00|BB A →VB|AB|BA|UU|BB B →00 B →UU V →BAU →00,ε→00,0→ε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,∑,Γ,δ,q, q1, q2)为识别可判定语言A的判定器，其中q1为接受状态，q2为拒绝状态。
令M=(Q,∑,Γ,δ,q, 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步，在第二段上运行M2i步，或者直到停机。
若都接受，则接受。
”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.211) 由cmax ≥|c1|知，当|x|≤1，则欲判定不等式明显成立。
2) 当|x|>1时，由c 1x n + c2x n-1 + …+ cnx + cn+1= 0⇒c1x =－(c2 + …+ c n x2-n + c n+1x1-n)⇒|c1| |x| = |c2 + …+ c n x2-n + c n+1x1-n|< |c2| +…+ |cn||x|2-n + |cn+1| |x|1-n≤ |c2| +…….|c n| + |c n+1||x0|≤ n c max< (n + 1) cmax⇒|x| < (n + 1) c max / |c1|.4.11 设A={<M>|M是DFA，它不接受任何包含奇数个1的字符串}。
证明A是可判定的。
证明：构造DFA N，使L(N)={含奇数个1的字符串}。
构造图灵机F=“对于输入<M>，其中M是DFA，1)构造DFA D，使L(D)=L(M)∩L(N)。
2)检测L(D)是否为空。
(EDFA可判定检测)。
3)若L(D)＝∅，则接受；否则拒绝。
”4.13 “检查一个CFG是否派生1*中某个串问题”解： LX={<G>|G是{0，1}*上的CFG，且1*∩L(G)≠∅}证明：构造TM TT＝“对于输入<A>，A为CFG1)将终结符“1”和“ε”做标记。
2)重复下列步骤，直至无可做标记的变元。
3)如G有规则A→U1U2…Un，且U1U2…Un中每个符号都已做过标记，则将A做标记，其中Ui为终结符或非终结符。
4)如果起始变元没有被标记则拒绝，否则接受。
”T判定LX。
5.7证明：如果A是图灵可识别的，且A≤m A，则A是可判定的。
证：∵A≤m A⇔A≤m A且A为图灵可识别的∴A也为图灵可识别的∴由A和A都是图灵可识别的可知A是可判定的.5.1 证明EQCFG是不可判定的。
解：只须证明ALLCFG ≤mEQCFG即可。
构造CFG G1，使L(G1)=∑*。
设计从ALLCFG到EQCFG的归约函数如下：F=“对于输入＜G＞，其中G是CFG：1）输出＜G,G1＞。
