可计算性与计算复杂性

《大学计算机基础与计算思维》课后习题参考答案目录第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年）。

计算机逻辑元件逐步由电子管改为晶体管，体积与功耗都有所降低。

主存储器采用铁淦氧磁芯器，外存储器采用先进的磁盘，计算机的速度和可靠性有所提高。

理解计算机中的计算理论与复杂性计算机中的计算理论与复杂性计算理论是计算机科学的重要分支之一，它研究计算过程的本质和性质，为计算机科学提供了理论基础。

而复杂性理论则研究计算问题的复杂性，即问题的难解程度。

在计算机发展的不断推动下，计算理论与复杂性的研究越发重要。

本文将从计算理论和复杂性两个方面对相关概念和研究进行介绍和探讨。

一、计算理论计算理论是计算机科学中关于计算概念和过程的研究。

它主要分为可计算性理论和形式语言与自动机理论两大部分。

1. 可计算性理论可计算性理论研究的是什么问题可以用计算机算出，以及如何判断一个问题是否可计算。

它的核心思想是“图灵机”，即由英国数学家图灵提出的一种理论模型，用于描述计算过程。

可计算性理论的研究对象包括了函数的计算性、计算问题是否可判定、可计算函数的分类等。

2. 形式语言与自动机理论形式语言与自动机理论研究的是描述和处理信息的形式化语言和自动机模型。

形式语言的研究对象包括了正则语言、上下文无关语言和上下文敏感语言等。

而自动机模型则包括了有限状态自动机、下推自动机和图灵机，用于描述和处理形式语言。

二、复杂性理论复杂性理论是研究计算问题的复杂性的学科。

它关注的是问题的求解难易程度，即问题的复杂性。

复杂性理论主要分为计算复杂性理论和各类计算问题的复杂性。

1. 计算复杂性理论计算复杂性理论研究的是计算问题的复杂性度量和分类。

其中最具代表性的是时间复杂性和空间复杂性。

时间复杂性研究的是计算问题在计算时间上的耗费，空间复杂性研究的是计算问题在计算空间上的耗费。

常用的时间复杂性度量是“大O记号”，用于表示问题在最坏情况下的耗时增长趋势。

2. 计算问题的复杂性计算问题的复杂性研究的是不同类型问题的复杂性分类以及它们之间的关系。

其中最经典的研究是关于P类问题和NP类问题的划分。

P 类问题指的是可以在多项式时间内求解的问题，而NP类问题指的是可以在多项式时间内验证的问题。

复杂性理论的研究则主要集中在P与NP问题之间的关系。

什么是时间复杂度？请举例说 明。
时间复杂度是评价算法执行时 间快慢的一个指标，通常用大O 表示法来表示。例如，对于一 个简单的顺序查找算法，其时 间复杂度为O(n)，表示随着问 题规模n的增加，算法的执行时 间线性增长。
计算模型习题答案详解
习题1
解释图灵机的基本原理和工作过程。
答案
图灵机是一种理论上的计算模型，由一条无限长的纸带和一个读写头组成。读写头可以读取、写入和移动纸带上 的符号，根据当前状态和读取的符号来决定下一步的动作和状态转移。图灵机的工作过程可以模拟任何计算机程 序的执行过程。
RAM模型的扩展与优化
包括引入并行计算、分布式计算等概念，以 提高RAM模型的计算能力和效率。
其他计算模型
量子计算模型
利用量子力学原理进行计算的模型，具有在某些特定 问题上比传统计算机更高的计算效率。
生物计算模型
模拟生物体内信息处理过程的计算模型，如神经网络、 基因算法等。
光计算模型
利用光学原理进行计算的模型，具有高速并行处理和 低能耗等优点。
形式语言与自动机习题答案详解
习题1
解释什么是形式语言，并给出其定义和性质 。
答案
形式语言是பைடு நூலகம்于描述计算机程序的语法和语 义的一种数学工具。它由一组符号和一组规 则组成，可以表示各种不同类型的数据结构 和算法。形式语言具有确定性、封闭性和可 计算性等性质，这些性质使得我们可以对计
算机程序进行精确的描述和分析。
Python语言基础 掌握Python语言的基本语法、数 据类型、控制结构、函数等，以 及常用的Python库和框架。
其他编程语言 了解其他常见的编程语言，如C#、 JavaScript、Go等，以及它们的 特点和应用场景。

可计算性与计算复杂性导引第二版教学设计课程概述本课程主要介绍可计算性和计算复杂性理论的基本概念和方法，旨在帮助学生理解计算机科学的核心思想和方法，培养学生的计算思维和解决问题的能力。

课程目标1.了解可计算性和计算复杂性理论的基本概念和方法。

2.了解主要的计算模型和算法设计技术。

3.学会分析算法的时间和空间复杂度。

4.学会证明计算问题的不可解性和不可近似性。

5.培养学生的抽象思维和解决问题的能力。

教学内容1.可计算性理论介绍可计算性理论的基本概念，包括图灵机、递归函数、停机问题、可计算函数和不可计算函数等。

2.计算复杂性理论介绍计算复杂性理论的基本概念，包括时间复杂度、空间复杂度、P、NP、NP 完全问题、NP难问题等。

3.算法设计介绍常见的算法设计技术，包括贪心、动态规划、分治、回溯、随机化等。

4.算法分析介绍算法分析的基本方法和技巧，包括渐进符号、递归方程、对数级数等。

5.不可解性与不可近似性介绍一些经典的不可解性和不可近似性结果，包括halting problem、cook定理、PCP定理等。

教学方法本课程采用理论讲授和实践演练相结合的方式进行教学。

1.理论讲授通过讲授理论知识和解释实例，介绍可计算性和计算复杂性理论的基本概念和方法。

2.实践演练通过设计算法，分析算法复杂度，并完成一些经典问题的求解，锻炼学生的算法分析和实现能力。

教学评估1.平时成绩：作业和实验占比30%，课堂表现占比20%，出勤占比10%。

2.考试成绩：闭卷笔试，占比40%。

3.课程设计和报告：占比10%。

学生需要设计一个算法或证明一个不可解性或不可近似性定理，并完成一篇报告。

参考书目1.Sipser, M. (2012), Introduction to the Theory of Computation, 3rd edition, Cengage Learning.2.Papadimitriou, C. (1994), Computational Complexity, Addison-Wesley.3.Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms, 3rd edition, MIT Press.结语通过本课程的学习，学生可以深入了解计算机科学的核心理论，掌握算法设计和分析技术，以及认识到一些计算问题的不可解性和不可近似性。

8
2、计算理论（Theory of computation）
(3) 串行计算类：P，NP，NPC，NPH
• • • • P类问题：在确定图灵机上多项式（Polynomial）时间内可求解的一类问题。 NP类问题：在非确定图灵机上多项式时间内可求解的一类问题（所有NP问题均必 须在有限步内是可判定的）。 NPC问题：对于L∈NP的问题，且NP类中的每一个L’均可在多项式时间内归约 （转换）到L，L’≤P L，则称L为NPC（NP完全）的（第一个被证明是NPC问题的 是布尔满足性问题：Boolean Satisfiability Problem，SAT）。 NPH（难）问题：一个问题H称为NP难的，当且仅当存在着一个NPC问题L，L可 在多项式时间内图灵归约（Turing-Reduction）到H。简记之为：L(NPC) ≤T H(NPH) （例如判定停机问题是NPH问题）。
2
目 录
1. 1. 计算科学与计算问题分类 计算机科学与计算问题分类 (1) (1) 计算科学 计算机科学的经典定ቤተ መጻሕፍቲ ባይዱ (2) 算法定义的数学解释 计算机科学定义的数学解释 (2)
(2) 支撑点空间的定义 (3) 举例 (4) 完全支撑点空间
6.
数据的划分技术
(1) 超平面划分 (2) 有利点划分 (3) 包络球划分
•
14
4、度量空间：大数据统一化抽象表示
supinf d x, y
xX yY
supinf d x, y
yY xX
d H X , Y max{supinf d x, y , supinf d x, y }
xX yY yY xX
15
4、度量空间：大数据统一化抽象表示

大多数研究者认可 的包容关系
L m
计算复杂度的影响因素
简化模型：模型2
计算复杂度的影响因素
简化模型：模型3。
计算复杂度的影响因素
建模假设 例：高空抛球的运动轨迹。 ----抛物线模型 假设1.没有空气阻力； 假设2.地面是平面。 ----椭圆模型
计算复杂度的影响因素
探索空间1 探索空间1---解的近似度、满意度
例：0—10之间的整数解：1-9共9个可行解（一维） 0—10之间的实数解：精确到小数点后6位 共有107个可行解（一维）； 107n个可行解（n维）
n! 10141世紀 → 10120世紀 102551世紀 → 102530世紀
问题与算法
每个問題都可能有多个算法存在． 每个算法的计算量（速度）都不同。 例： 赝品金币問題： 问题：9個外观完全一样的金币.，有一个是假的 （重量轻）． 提问：用天秤来鉴别真伪，天秤需要使用几次？
贋品金币問題算法 問題算法
优化技术与方法
計算量(1) 計算量
＋,－,×,÷ 比較：≠，≤，≥，＜，＞ 5种基本演算都是用1step 可以实现. 実際上,×比＋多占用時間. 「四舍五入」不算基本演算.
計算量(2) 計算量
｛a1, a2,..., an｝：n個整数 Q1. 求和（1）： a1+a2+･･･+an. 1 + +a n-1 steps → O(n)算法. Q2. 求和（2）： (1) 2×a1+･･･+ 2×an , 2n-1 steps→ O(n)算法. (2) 2×(a1+･･･+an) , n steps→ O(n)算法.
尚未确信能否用多項式時間算法求解的问题的 集合称为NP （non-deterministic polynomial）问题 某一个问题不属于NP问题的証明 如能够找到一个多項式時間算法 （簡単） 某一个问题属于NP问题的証明 可以归结为某一类既知的NP类问题（现阶段7类））

图灵奖：１９４６年，世界上第一台电子计算 机诞生；１９６６年，ACM决定设立“图灵 奖”——计算机科学中杰出的科学家，每年一 般一名
数学家与图灵奖
大部分图灵奖获得者是学数学出生或数学家， 例如：
M. Minsky, 1969 E.W. Dijkstra, 1972 D.E. Knuth, 1974 S.A.Cook,1982 D.M. Ritchie, 1983 R.M.Karp, 1985 R.E. Tarjan, 1986 J.Cocke, 1987 W.V. Kahan, 1989 R. Milner,1991, 还有很多计算复杂性的获奖者如 J.Hartmanis
经典计算的简要历史背景（续）
1940’s和1950’s, 另一类更简单的计算模型— —有限自动机及形式文法的提出（文本处理、 编译程序、硬件设计、自动控制、人工智能 等）。
1960’s S.Cook发展Church-Turing命题，提出 计算复杂性——NP完全问题，如可满足性 (SAT)。
1960’s S.Cook发展Church-Turing命题， 提出计算复杂性——NP完全问题，如可 满足性问题。
经典计算理论（ACM)
自动机理论 可计算性 计算复杂性
FOCS (IEEE-CS) STOC (ACM) Journal of the ACM SIAM Journal on Computing (SIAM) Information and Computation Journal of Computer and System Sciences Theoretical Computer Science
亚里士多德：“明天波斯和雅典将发生海战”。 事物的“势态”，人的“情态”以及过程的变

式时间内可以验证其解的正 问题规模的增大而急剧增加，
确性，但至今尚未找到多项 导致在实际应用中往பைடு நூலகம்难以
式时间算法来求解的问题。
求解。
所有NP完全问题在多项式时间 内可以相互转化，即如果一个 问题能够在多项式时间内求解 ，那么其他所有NP完全问题也 能够在多项式时间内求解。
NP完全问题涵盖了计算机科 学、数学、物理学等多个领
03
探讨利用光的物理特性进行计算的新方法，包括光计算基本原
理、光量子计算技术、光计算应用等。
近似算法与启发式算法研究动态
近似算法设计与分析
研究在多项式时间内求解NP难问题的近似算法，分析其时间复杂度和近似比等性能指标 。
启发式算法原理及应用
探讨模拟自然界现象或过程的启发式算法，如遗传算法、蚁群算法、粒子群算法等，以及 它们在组合优化、机器学习等领域的应用。
丘奇-图灵论题
1 2
丘奇-图灵论题的定义
所有可有效计算的函数都可以用图灵机来计算。
丘奇-图灵论题的意义
奠定了计算机科学的基础，为计算机程序设计提 供了理论支持。
3
丘奇-图灵论题的应用
用于证明某些问题的不可解性，如停机问题等。
不可计算性证明
01
不可计算性的定义
指某些问题无法用图灵机在有限步骤内得出答案。
可满足性问题（SAT Problem）：给定一个布尔表 达式，求解是否存在一种变量赋值使得表达式为真。
NP完全问题在实际应用中的意义
算法设计挑战
NP完全问题的存在为 算法设计领域提供了持 续的挑战和动力，推动 了计算机科学领域的发 展。
评估问题难度
NP完全问题作为一类 难解问题的代表，为评 估其他问题的难度提供 了一个基准。如果一个 新问题被证明是NP完 全的，那么我们可以认 为这个问题是难解的。

可计算性与计算复杂性1.可计算性：可计算性研究的是什么样的问题可以通过其中一种计算模型解决。

早期的计算模型是图灵机（Turing machine），后来发展出其他等效的计算模型，例如递归函数、Lambda演算等。

根据这些计算模型，可以定义一类问题为可计算问题，也就是可以通过计算模型求解的问题。

1.1停机问题：停机问题是可计算性的典型例子，它是指根据给定的程序和输入，判断这个程序是否会在有限的时间内停止运行。

根据图灵在20世纪30年代证明的停机问题的不可判定性，他证明了不存在一个通用的算法能够判断任意程序是否停机，这个结论被称为图灵不可判定性定理。

1.2基本计算问题：除了停机问题，可计算性还研究了一些其他的基本计算问题。

例如，可计算性研究了自动机是否可以接受一些字符串，或者函数是否可以被一个特定的计算模型计算等。

1.3计算模型的等效性：在可计算性理论中，研究了不同计算模型之间的等效性。

图灵机、递归函数和Lambda演算等计算模型之间可以相互转化，这意味着它们的计算能力是等价的。

这个等价性的概念对理解可计算性是至关重要的。

2.计算复杂性：计算复杂性研究的是什么样的问题可以在多项式时间内解决，以及在不同条件下求解问题所需要的计算资源（例如时间、空间等）。

计算复杂性理论的核心是研究问题的复杂度类别和难度。

2.1多项式时间可解问题：计算复杂性理论将问题分为多项式时间可解问题和非多项式时间可解问题。

多项式时间可解问题是指那些可以在多项式时间内求解的问题。

这些问题的解决方法被认为是高效的，因为随着输入规模的增加，所需计算资源的增长是可接受的。

2.2难解问题：非多项式时间可解问题是那些不可以在多项式时间内求解的问题。

例如，图的旅行商问题（TSP）和布尔可满足性问题（SAT）等问题被认为是难解问题。

难解问题的求解需要指数级的时间或空间复杂度，因此在实际中很难找到有效的算法。

2.3复杂度类别：计算复杂性理论还研究了不同问题的复杂度类别。

一、三大思维
计算思维的本质
二、计算机思维的本质
三、计算机的思维特征 四、计算机的基本问题
抽象+自动化
五、计算机的思维方法
六、计算机思维应用
一.三大思维 二、计算机思维的本质 三、计算机的思维特征
1.计算思维是人类求解问题的一条途径，是属于人的一种思维方式。 2.计算的思维过程可以由人执行，也可以由计算机执行。
第二节
计算机思维
一、三大思维
二、计算机思维的本 质
三、计算机的思维特 征
四、计算机的基本问 题
五、计算机的思维方 法
六、计算机思维应 用
1.理论思维
理论思维又称推理思维，以推理和演绎为特征，以数学学科为代表。
2.实验思维
验思维思实维又称实证，以观察和总结自然规律为特征。
3.计算思维
计算思维又称构造思维，以设计和构造为特征。
四、计算机的基本问题
3.计算思维是思想，不是人造物。
五、计算机的思维方法 六、计算机思维应用
4.计算思维是概念化，不是程序化。
一.三大思维 二.计算机思维的本质 三.计算机的思维特征 四.计算机的一个问题是可计算的是指：可以使用计算机在有限步骤内解决·。
1.物理领域 2.计算化学 3.计算生物学学
五.计算机的思维方法 六.计算机思维应用
4.计算经济学
2.计算复杂性
衡量标准有两个，空间复杂性、时间复杂性。
3。图灵测试 是否能和人类正常谈话？
tzalk
一.三大思维 二.计算机思维的本质 三.计算机的思维特征 四.计算机的基本问题 五.计算机的思维方法 六.计算机思维应用
计算思维核心：计算思维方法
一.三大思维 二.计算机思维的本质 三.计算机的思维特征 四.计算机的基本问题

从前，有一个酷爱数学的年轻国王向邻国一位聪明美丽的公主求婚。 公主出了这样一道题：求出48 770 428 433 377 171的一个真因子。若国王 能在一天之内求出答案，公主便接受他的求婚。国王回去后立即开始逐个 数地进行计算，他从早到晚，共算了三万多个数，最终还是没有结果。国 王向公主求情，公主将答案相告：223 092 827是它的一个真因子。国王很 快就验证了这个数确能除尽48 770 428 433 377 171。公主说：“我再给你 一次机会，如果还求不出，将来你只好做我的证婚人了。”国王立即回国， 并向时任宰相的大数学家求教，大数学家在仔细地思考后认为这个数为17 位，则最小的一个真因子不会超过9位，于是他给国王出了一个主意：按自 然数的顺序给全国的老百姓每人编一个号发下去，等公主给出数目后，立 即将它们通报全国，让每个老百姓用自己的编号去除这个数，除尽了立即 上报，赏金万两。最后，国王用这个办法求婚成功。
– 当将一个问题分解到多个处理器上解决时，由于算法中不可避 免地存在必须串行执行的操作，从而大大地限制了并行计算机 系统的加速能力。
•设f为求解某个问题的计算存在的必须串行执行的操作占整 个最计大算 的的 加百 速分 能比 力，，则p为处理器的数目，Sp为并行计算机系统
设f=1%，p→，则Sp=100。（阿达尔定律） 串行执行操作仅占全部操作1%，解题速度最多也只能提高 一百倍。 对难解性问题而言，提高计算机系统的速度是远远不够的， 而降低算法复杂度的数量级才是最关键的问题。
读写头
状态 控制器 q
图灵在1936年提出了著名的图灵机模型(计算模型)： ▪图灵机由一个无限长的带子（被划分成均匀的方格） 、一个磁带读/写头 和一个有限状态控制器组成。 ▪在每一步计算中，图灵机从磁带上读出一个符号，并由有限状态控制器决 定是否在当前的磁带区上写入不同的符号，然后决定是否需要将磁带读/写 头向前或向后移动一位。 当前的计算机，在理论上都是可以被图灵机模拟的，其原理和图灵机是相同 的，甚至还包含了存储程序的思想。

关于计算
第八讲
计算复杂性的度量方法
计算复杂性理论
计算复杂性理论研究各种可计算问题在计算过程中资源(如时间、空间等)的耗费情况。

算法的时间度量
从算法中取一种对于研究
问题来说是基本操作的原操作
，以该基本操作重复执行的次
数作为算法执行的时间度量
计算复杂性的度量方法
算法的时间度量
算法的所需时间与问题规模的函数T（n）
(a) X=X+1
(b) for（i=1; i<=n; i++）
X=X+1
(c) for（i=1; i<=n; i++）
for（j=1; j<=n; j++）
X=X+1
以上操作执行的次数分别是
1, n, n^2
如何降低计算复杂度
常见的算法时间复杂度
指数时间
多项式时间
好的算法
多项式时间算法。

计算复杂性的度量方法
确定性问题：只有肯定和否定答案。

P类问题：具有多项式时间
算法的确定性问题形成的计
算复杂性类。

P类问题包含了大量的
已知自然问题，如计算最大
公约数、计算π值、排序问
题、二维匹配问题等。

计算复杂性的度量方法
非确定算法
猜测一个变量的真值赋值
检查该赋值是否满足NP类问题：由非确定性算法在多项式时
间内可计算的判定问题所组成的集合。

NP类问题数量巨大，如完全子图问题、
图的着色问题、汉密尔顿回路问题、以
及旅行销售员问题等。

((x1)x2(x3)) (x2(x3)x4x5) ((x4)x5) • 合取范式cnf (conjunctive normal form)
3cnf: 每个子句文字数不大于3, 2cnf: 每个子句文字数不大于2
可满足问题SAT
• 可满足性问题: SAT = { <> | 是可满足的布尔公式 }
• 思想: 将字符串对应到布尔公式 利用接受的形式定义.
• 过程: 任取ANP, 设N是A的nk时间NTM. w(|w|=n), N接受w
N有长度小于nk的接受格局序列 能填好N在w上的画面(一个nknk表格) f(w)可满足 • 结论: SAT是NP完全的
N接受w能填好N在w上的画面
# q0 w0 w1 … wn #
2)若0,1都在带上,重复以下步骤. O(n)
3) 检查带上0,1总数的奇偶性,
若是奇数,就拒绝.
O(n) log n
4) 再次扫描带,
第1个0开始,隔1个0删除1个0; O(n)
第1个1开始,隔1个1删除1个1.
总时间:
5)若带上同时没有0和1,则接受. O(n) O(nlogn)
否则拒绝.”
{0k1k|k0}TIME(nlogn)
快速验证
HP = {<G,s,t>|G是包含从s到t的 哈密顿路径的有向图}
CLIQUE={<G,k>|G是有k团的无向图} 目前没有快速算法,但其成员是可以快速验证的. 注意:HP的补可能不是可以快速验证的. 快速验证的特点: 1. 只需要对语言中的串能快速验证. 2. 验证需要借助额外的信息:证书,身份证.
• 二元可满足性问题: 2SAT = { <> | 是可满足的2cnf }

《计算理论》复习题总结《计算理论》复习题总结1、⾃动机、可计算性、复杂性内涵及关系；计算理论的三个传统的核⼼领域：⾃动机、可计算性和复杂性。

通过“计算机的基本能⼒和局限性是什么？“这⼀问题将这三个领域联系在⼀起。

可计算理论与复杂性理论是密切相关的，在复杂性理论中，⽬标是把问题分成容易计算的和难计算的；⽽在可计算理论中，是把问题分成可解的和不可解。

⾃动机阐述了计算的数学模型的定义和性质，主要包含两种模型：有穷⾃动机模型；上下⽂⽆关⽂法模型。

可计算性理论和复杂性理论需要对计算机给了⼀个准确的定义。

⾃动机理论允许在介绍与计算机科学的其他⾮理论领域有关的概念时使⽤计算的形式化定义。

2、有穷⾃动机、正则语⾔、正则表达式、⾮确定有穷⾃动机、⾮正则语⾔；有穷⾃动机：描述能⼒和资源极其有限的计算机模型。

是⼀个5元组（Q，∑，δ，q0,F），其中1）Q是⼀个有穷集合，称为状态集。

2）∑是⼀个有穷集合，称为字母表。

3）δ：Q×∑→Q是转移函数。

4）q0∈Q是起始状态。

5）F?Q是接受状态集。

正则语⾔：如果⼀个语⾔能被有穷⾃动机识别。

正则表达式：⽤正则运算符构造描述语⾔的表达式。

称R是正则表达式，如果R是：1）a，a是字母表中的⼀个元素；2）ε；3）?;4）（R1?R2）；5）(R1 R2)；6）(R1*)⾮确定有穷⾃动机：是⼀个5元组（Q，∑，δ，q0,F），其中1）Q是有穷状态集。

2）∑是有穷字母表。

3）δ：Q×∑ε→P（Q）是转移函数。

4）q0∈Q是起始状态。

5）F?Q是接受状态集。

3、上下⽂⽆关语⾔及上下⽂⽆关⽂法、歧义性、乔姆斯基范式、下推⾃动机、等价性、⾮上下⽂⽆关语⾔；上下⽂⽆关语⾔：⽤上下⽂⽆关⽂法⽣成的语⾔。

上下⽂⽆关⽂法：是⼀个4元组（V，∑，R，S）且1）V是⼀个有穷集合，称为变元集2）∑是⼀个与V不相交的有穷集合，称为终结符集3）R是⼀个有穷规则集，每条规则由⼀个变元和⼀个由变元及终结符组成的字符串构成，4）S∈V是起始变元歧义性：如果字符串W在上下⽂⽆关⽂法G中有两个或者两上以上不同的最左派⽣，则称G歧义地产⽣的字符串W。

可计算性与计算复杂性可计算性是研究计算问题是否具有解决方法的理论。

可计算性理论起源于上世纪30年代，由图灵（Alan Turing）等人提出。

可计算性的核心观点是，一个计算问题是否可以用一个确定的算法来解决。

如果存在一个算法解决了一些问题，那么这个问题就是可计算的。

例如，对于给定的两个整数，判断它们是否互质是一个可计算问题，因为存在一种算法可以解决这个问题。

另一方面，对于一个不可计算的问题，不存在一个算法可以解决它，如停机问题（Halting Problem）。

计算复杂性是研究计算问题所需的资源的理论。

计算复杂性理论的主要目标是研究在给定资源限制下，一个问题是否可以在合理的时间或空间内解决。

计算复杂性关注的是问题的难解程度，即需要多少资源才能解决问题。

计算复杂性理论通过引入时间和空间复杂度来描述问题的难度。

常见的时间复杂度表示方法有大O记号，如O(n)、O(nlogn)等，表示问题的解决时间与问题规模n之间的关系。

类似地，空间复杂度表示问题所需的存储空间。

计算复杂性理论中的一个重要问题是P与NP问题。

P问题（Polynomial Time）是指可以在多项式时间内解决的问题。

换句话说，对于一个P问题，存在一个多项式时间的算法可以解决它。

例如，对于给定的两个整数，判断它们是否互质就是一个P问题，因为存在一种多项式时间的算法可以解决。

P问题是计算复杂性理论中最为理想的一类问题。

NP问题（Nondeterministic Polynomial Time）是指可以在多项式时间内验证一个解的问题。

对于一个NP问题，如果一个解被提供，可以在多项式时间内验证它的正确性。

例如，对于给定的一组整数和一个目标值，判断是否存在一组整数使得它们的和等于目标值就是一个NP问题。

虽然验证解的正确性可以在多项式时间内完成，但寻找解的过程可能需要指数时间等非多项式时间，因此NP问题被认为是一类困难问题。

P问题与NP问题之间的关系是计算复杂性理论中一个重要的开放问题，即P=NP问题。

2.1 计算的几种视角
三、算法与计算
从不同角度看，算法的定义有多种： 从哲学角度看：算法是解决一个问题的抽象行为序列。 从抽象层次看：算法是一个将输入转化为输出的计算步骤序列 从技术层面看：算法是接收输入并产生输出的计算过程。
简而言之，算法就是计算的办法或法则。
算法无处不在，每个人每天都在 使用不同的算法来活出自己的人生。 比如你去食堂买饭会选择一个较短的 队列，而有人则可能选择一个推进速 度更快的队列。
计算复杂性：用计算机求解问题的难易程度。 度量标准： ①时间复杂度→计算所需的步数或指令条数； ②空间复杂度→计算所需的存储空间大小。
特性：确定性、有限性、机械性、可执行性和终止性。
11/48
计算理论 计算模型
2.2 计算理论
3.可计算理论的主要内容
图灵机：一种在理论计算机科学中广泛采用的抽象计算机 用于精确描述算法的特征。通用图灵机正是后来的存储程序的 通用数字计算机的理论原型。
λ转换演算：一种定义函数的形式演算系统。丘奇为精确 定义可计算性而提出的，他引进λ记号以明确区分函数和函数 值，并把函数值的计算归结为按照一定规则进行一系列转换， 最后得到函数值。
5/48
计算理论 计算模型
2.1 计算的几种视角
算法：为解决一个特定的问题所采取确定的有限步骤。 计算机用于解决数值计算，如科学计算中的数值积分、解线 性方程等计算方法，就是数值计算的算法。 计算机用于解决非数值计算，如用于管理、文字处理、图像 图形等的排序、分类和查找，就是非数值计算的算法。
算法的组成：操作、数据。 这些操作包括加、减、乘、除和判断等，并按顺序、分支、 循环等控制结构所规定的次序执行。 数据是指操作对象和操作结果，包括布尔值、字符、整数和 实数等；以及向量、记录、集合、树和图以及声1936

1 引言可计算理论建立于二十世纪三十年代。

可计算理论的研究对象有三个 : (1) 判定问题 ;(2 ) 可计算函数 ; (3 ) 计算复杂性。

判定问题主要是判定方程是否有解 ;可计算函数主要讨论一个函数是否可计算 , 建立了原始递归函数、图灵机等许多数学模型判定一个函数是否属于可计算函数 ;计算复杂性主要讨论的问题是P =?NP。

可计算理论的计算模型主要包括 : (1) Turing机 ; (2 ) 递归函数; (3 ) λ演算 ; (4) POST系统 ; (5) 正则算法。

可计算理论是理论计算机科学 , 属于计算机科学的基础研究领域 , 可计算理论是计算机软件工程、系统结构、并行运算、图像处理、人工智能、网络的数学理论基础和工具.可计算性理论是从三十年代初期开始哥德尔、丘吉、图林和波斯特等人为了解决数学基础方面的问题，（具体说.来是为了通过薮学方法来研究公理系统的性质），而发展起来的。

（其中波斯特的工作则是在二十年代前期已经作出的，但到了四十年代才公开发表。

）电子计算机产生后，可计算性理论的有些成果被应用于计算技术。

（近十年来发展起来的可行计算理论则是与计算技术直接有关并作为这一技术的数学理论而发展的。

）2 历史变迁可计算理论是关于计算机械本身的数学理论. 二十世纪前, 计算机械总是“算计”别的对象, 很少“算计”自己。

二十世纪 30年代, 为了要解决一个基础问题, 即是否存在不可判定问题, 数理逻辑学家提出了几种不同的 (后来证明是彼此等价的) 关于算法的定义, 从而建立了可计算性理论。

德国数学家希尔伯特 (Hilbert 1862-1943) 认为科学在每个时代都有它自己的问题, 而这些问题的解决对于科学发展具有深远意义。

他指出:“只要一门科学分支能提出大量的问题, 它就充满着生命力, 而问题缺乏则预示着独立发展的衰亡和终结。

” 在1900年国际数学家代表大会上, 希尔伯特发表了题为《数学问题》的著名讲演, 他根据十九世纪数学研究的成果和发展趋势, 提出了23个最重要的数学问题。