七天太乐
0%

复杂性理论复习

发表于 更新于 分类于 ， ，

复杂性理论复习综述

理论计算机的核心目标：

把计算任务按照其本质难度进行分类 ![image-20230626150513090](https://qitiantaile.oss-cn-guangzhou.aliyuncs.com/blog/image-20230626150513090.png) 复习重点：判定问题；图灵机构造和基本思想；什么是P、NP、NPC问题及NP问题之间的规约和常见的NPC问题；SAT、2SAT、3SAT问题；递归算法和非递归算法特点和区别；复杂度分析方法区别；会写素数判定的递归和非递归算法

1.什么是可计算问题？什么是不可计算问题？

可计算问题当且仅当该问题可以在图灵机上经过有限步骤后可以得到正确的结果。相反地，不能由图灵机解决的问题叫做不可计算问题。 ## 2.什么是计算复杂性？计算复杂性理论主要研究什么？ 计算复杂性就是用计算机求解问题的难易程度，使用数学方法对计算中所需的各种资源消耗作定量的分析，并研究各类问题之间在计算复杂程度上的相互关系和性质。 主要研究计算问题时所需要的资源，比如时间和空间，以及如何尽可能的节省这些资源。 ## 3.什么是算法？算法有哪些特点？ 算法是对解决方案的准确而完整的描述。 特点：有穷性，可行性，确定性，输入和输出 ## 4.描述算法的方法有？ 自然语言、流程图、N-S图、伪代码、程序设计语言 ## 5.如何分析算法的效率？

算法的效率分析指对算法在运行时间和存储空间这两种资源的利用效率进行研究。对于一般算法，关注其输入规模，运行时间的度量单位，增长效率和算法的最优最差平均效率；对于递归算法，则需要关注递归的深度，先对算法建立一个递归关系，设置初始条件，再求解分析。

6.渐进表达式O(g(n))，Θ(g(n))，Ω(g(n))的定义和表达含义？

O(g(n))：如果函数t(n)包含在O(g(n))中，对于所有足够大的n，t(n)的上界由g(n)的常数倍确定，即存在大于0的常数和非负的整数n0使得对于所有的 n≥n0 ，有 cg(n)≥t(n) 表达含义：g(n)≥该算法的时间复杂度 Θ(g(n))：如果函数t包含在Θ(g(n))中，对于所有足够大的n，t(n)的上下界都由g的常数倍确定，即存在大于0的常数c1,c2和非负的整数n0使得所有 n≥n0 ，有 c1g(n)≥t(n)≥c2g(n) 表达含义：g(n)=该算法的时间复杂度 Ω(g(n))： 表达含义：该算法的时间复杂度≥g(n) ## 7.递归和非递归算法时间效率的数学分析方法区别？

见5

  • 思维方式：递归通过将一个复杂问题层层转化为一个与原问题规模更小的同类问题，通过不断缩小问题规模，最终到达基本情况，再将各个小问题的解合起来得到整体解决方案。非递归则是从问题的初始状态逐步迭代到最终解的思维方式。
  • 实现方式：递归的实现方式是通过函数自身的调用来解决问题。非递归通常使用循环结构，通过迭代更新变量来逐步解决问题。
  • 空间和时间复杂度：递归在某些情况下会导致大量的函数调用和堆栈空间的使用，可能会占用更多的内存空间，非递归在空间上会更加高效；时间上的效率取决于具体实现的方式和算法。

8.Fibonacci numbers F(N) = F(N-1) + F(N-2)的时间复杂度表达式？

递归法：O(2^N) 公式计算法：O(1) ## 9.经典排序问题的算法时间复杂度下界？ | 排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 | 稳定性 | | :------: | :--------------: | :--------------: | :--------------: | :--------: | :----: | | 插入排序 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 | | 希尔排序 | O(n^1.3) | O(n^2) | O(n) | O(1) | 不稳定 | | 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | | 堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 | | 快速排序 | O(nlogn) | O(n^2) | O(nlogn) | O(logn) | 不稳定 | | 冒泡排序 | O(n^2) | O(n^2) | O(n) | O(n) | 稳定 | | 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 | | | | | | | | | 基数排序 | O(n*k) | O(n*k) | O(n*k) | O(n+k) | 稳定 | | 计数排序 | O(n+k) | O(n+k) | O(n+k) | O(n+k) | 稳定 | | 桶排序 | O(n+k) | O(n^2) | O(n) | O(n+k) | 稳定 | ## 10.算法性能提升的本质是什么？提升算法效率的四个层次是什么？ 提升的本质：本质是效率，就是让计算机少做事情。效率=产出/所做的事，产出难提高，所做事情可以减少 四个层次：正确性；易读性；健壮性；时空性。 ## 11.为什么超越多项式时间复杂度的精确算法一般是不可接受的？ 时间复杂度并不表示一个程序解决需要多少时间，而是当问题规模扩大后，程序需要的时间随规模的增长有多快。 一个优化问题如果已经找到了多项式时间算法，称该问题为多项式时间可解问题，并将这类问题的集合记为P，即多项式时间可解问题为P类问题。 一个问题没有找到多项式时间算法，在直觉上他是“难解”的，但又无法证明多项式时间算法的不存在性。一方面证明一个问题不存在多项式时间算法是困难的；另一方面，有越来越多的问题无法给出多项式时间算法。 NP-完全性理论的核心思想：如果一个问题是NP类问题，并且存在一个能够在多项式时间内转换为该问题的解的算法，那么该问题就是NP-完全问题。一个问题是NP-完全问题意味着他是NP类问题中最困难的问题之一。其重要性在于：如果能够证明某个问题是NP-完全问题，那么就可以推导出其他许多问题也是NP-完全问题。 ## 12.什么是图灵机？什么是图灵测试？什么是图灵命题？ 图灵机：又称图灵计算机，指一种抽象的计算模型，即将人使用纸笔进行数学运算的过程进行抽象，由一个虚拟机器替代人类进行数学运算。 其有一个无限长的纸带，纸带分成一个一个方格，每个方格有不同颜色，一个机器头在纸带上移动。机器头有一组内部状态和一些固定程序。每个时刻，机器头从当前纸带读入一个方格的信息，然后结合内部状态查找程序表，根据程序输出信息到纸带方格中，并转换自己的内部状态，进行移动。 图灵测试：指测试者和被测试者隔开的情况下，通过一些装置向被测试者随意提问。进行多次测试后，如果机器让平均每个参与者做出了超过30%的误判，那么这台机器就通过了测试，并认为具有人类智能。 图灵命题：可计算性理论的基本论题，一个函数是可计算的当且仅当可由一部图灵机来计算它。 ## 13.图灵机的基本原理及组成部分？什么是格局？ 图灵机基本原理：其有一条无限长的纸带，纸带分成一个一个小方格，每个方格有不同的颜色。一个机器头在纸带上移动。机器头有一组内部状态和一些固定程序。每个时刻，机器头从当前纸带读入一个方格的信息，然后结合内部状态查找程序表，根据程序输出信息到纸带方格中，并转换自己的内部状态，进行移动。 组成部分： a.纸带，被分成许多个方格，符号可以写入或者读出； b.可以移动的读写头，能从纸带读取或写入符号； c.指示读写头下一步如何操作的一组规则。 d.状态寄存器：保存图灵机当前的状态。 格局：格局是图灵机的一个快照。将图灵机计算过程每一个步骤都找一份快照，通过轨迹将这些快照联系在一起，就可以得到一个数据结构。包括纸带内容，读写头位置和控制机状态。 ## 14.为什么说所有计算或算法都可以由一台图灵机来执行？

邱奇-图灵论题最基本的观点表明，所有计算或算法都可以由一台图灵机来执行。以任何常规编程语言编写的计算机程序都可以翻译成一台图灵机，反之任何一台图灵机也都可以翻译成大部分编程语言的程序，所以该论题和一下说法等价：常规的编程语言可以足够有效地来表达任何算法。该论题被普遍认定为真。

15.如何从图灵机视角看待算法的时间复杂度和空间复杂度？

图灵机程序的复杂度由外部的输入和输出来决定图灵机内部的算法的时间和空间的复杂度。 图灵机的时间复杂度T(n)是它处理所有长度为n的输入所需要的最大计算步数。如果对于某个长度为n的输入，图灵机不停机，则T(n)对这个值无定义。 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在纸带上所使用过的方格总数。如果某个读写头无限的向右移动而不停机，S(n)也无定义。 ## 16.什么是确定性图灵机、非确定性图灵机和概率图灵机？ 确定性图灵机(DTM)：在DTM中，其控制规则规定了在任何给定的情况下最多只能执行一个动作。确定性图灵机具有转换功能，对于磁带头下的给定状态和符号，该转换功能指定了三件事：要写入磁带的符号，头部应移动的方向，以及有限控制的后续状态。 非确定性图灵机(NDTM)：在理论计算机科学中，非确定性图灵机是一种理论计算模型，其控制规则在某些给定情况下指定了多个可能的动作。NDTM的下一个状态不是完全由其动作和它所看到的当前符号决定的。 概率图灵机(PTM)：一种非确定型图灵机，每走一步在两个转移函数之间随机地选取一个。概率图灵机是依照随机带上写下的0和1来决定下一步怎么走。 ## 17.什么是识别问题？什么是判定问题？什么是PT验证器？ 识别问题：当且仅当图灵机接受字符串时，当提供的输入位于语言中时，语言才是可识别的。此外，如果TM终止并拒绝字符串或根本不终止，则可以识别语言。这意味着当提供的输入不在语言中时，TM继续计算。然而，当且仅当由一台机器在提供的输入位于该语言中时接受字符串并在提供的输入不在该语言中时拒绝该字符串，该语言才是可判定的。 判定问题：有些语言可被判定器判定。如果存在不可判定语言，那么必然存在不可识别语言。就是无法构造一个图灵机，接受这个语言的每一个字符串。所以如果一个语言不可判定，必然它或者它的补是不可识别的。不可识别的语言是存在的。一个不可判定的语言就是一个不可计算的问题。那是一个超出了计算机能力的问题，一个不能被任何有步骤的、确定性的算法所能解决的问题。即不用求解，判定是否是解,判定比识别要更加严格 PT验证器：多项式图灵机 ## 18.什么是P，NP，NPC，NP-hard？ P：一个问题如果在图灵机上所需时间不会超过一个确定的多项式，称此类问题的集合为P，通俗来讲，P问题就是多项式时间可解的问题； NP：可以在非确定型图灵机上在多项式时间内找出解的问题的集合。如果一个问题，可以在多项式时间内验证它的解是否正确，则该问题是一个NP问题。显然 P∈NP(注：到目前为止，P!=NP) NPC(NP-Complete)：一个决定性问题C若是NPC，则代表它对NP是完备的，这表示： 
1
2
a.该问题是一个NP问题
b.所有属于NP的问题都可以归约成该问题
对于一个NPC问题，我们不可能尝试将所有的NP规约到它，所以通常采用一下方法证明一个问题是NPC问题： 
1
2
a.证明给定问题的一个解，可以在多项式时间验证该问题
b.可以将一个已知的NPC问题归约到该问题
在计算复杂度理论中，第一个被证明的NPC问题是布尔可满足性问题。所以 
1
可满足问题属于NPC问题。
1
2
可满足性问题(SAT)：
可满足问题是判断仍以给定的一个布尔表达式是否存在一个真赋值，存在则称该布尔表达式可满足
NP-hard:相较于NPC问题，NP-hard问题只满足条件2 
1
2
3
即所有的NP问题都可以归约到NP-hard问题，即NPC问题可以归约到NP-hard
其次他不一定是NP问题，如下图所示
通常通过将一个已知的NPC问题归约到该问题证明NP-Hard
image-20230626195253002 ## 19.为什么说计算复杂性理论的首要问题是P=NP？它的内涵是什么？为什么说P=NP不可思议？ a.自从P=NP问题被正式提出后，有NP完备理论赋予其在实践上的重要性，有证明复杂性理论赋予其纯数学理论上的重要性，有PCP理论和NP完备理论赋予其算法理论上的重要性。这些理论从根本上依赖P与NP关系问题的某些假设，或者本身就是试图去理解NP和P关系问题而发展出来的。计算复杂性理论的基本的主题之一是算法所需资源的下界。 b.“P/NP”问题，这里的P指多项式时间，假如NP问题能找到算法使其在多项式时间内解决，也就证明了P=NP c.如果P=NP，那么每个答案很容易得到验证的问题也同样可以轻松求解，这将对计算机安全构成巨大威胁。目前加密系统的破解就相当于要将一个整数分解成几个因数的乘积，正是其求解过程的繁琐，才能杜绝黑客入侵。如果证明了P=NP，那么依据计算复杂性的密码就没有用途。如果P=NP，那么所有的NP问题都存在有效的解决方案，而对于NP-hard问题，及时P=NP，也不一定有解。同时如果证明了P!=NP，那么大素数的分解还是不是NPC的？证明RSA、DES等密码的安全性比证明P/NP还困难。 ## 20.简述Cook-Levin定理，为什么该定理如此重要？ Cook-Levin定理：表明布尔可满足问题是NPC的。也就是说，NP中的任何问题都可以通过DTM在多项式时间内减少到确定布尔公式是否可满足的问题。如果可以在多项式时间内通过非确定性算法求解，则决策问题在NP中。 为什么如此重要：给定NP中的任何决策问题，构造一个在多项式时间内解决它的非确定性机器。然后，对于该机器的每个输入，构建一个布尔表达式，表示输入传递给机器，机器正确运行并停止回答“是”。证明表明NP中的任何问题都可以在多项式时间中减少到布尔可满足问题的实例。这意味着如果布尔可满足问题可以通过确定性图灵机在多项式时间内解决，则NP中的所有问题都可以在多项式时间内求解，因此证明P=NP ## 21.什么是归约？常见的归约方法？ 归约：一个问题A可以归约到一个问题B的含义是可以用解决B的方法解决A，也就是说找到了解决A的方法。因此可知，问题A不一定比问题B难，即B更难至少两个问题是同样难度的。 详细定义： 
1
对于问题A和问题B，如果存在一个可计算的函数f，使得对于任意问题A的实例x有：
$$ A(x) = B(f(x)) $$ 
1
2
我们就说问题A可以被归约到问题B
归约方法：Many-one归约，图灵归约，Karp归约，Levin归约，Cook归约
## 22.如何判定一个问题是NPC问题？ 
1
2
3
a.是一个NP问题
b.所有NP问题都可归约到它
（见18）

23.什么是停机判定问题？其哲学思想是什么？

1
2
3
4
5
停机判定：给定一个图灵机T和一个任意语言集合S，T是否会最终停机于每一个s∈S。
        即判定一个程序是否会在有限的时间内结束运行。
意义：其意义相同与可确定语言。显然任意有限S是可判定性的，可列S也是停机的。
     即所有能行和计算的算法都是可以得到确定性答案而停机；或
     不存在可以解决问题的确定性算法。
注：“停机问题”不可判定意味着“可计算的”机器不能肯定自己的“可计算性”，停机问题这种悖论式解释判定问题只会让问题更难。

24.求解NP问题的一般方法？

a.动态规划法与分支界限法：对于许多NPC问题来说，用此方法可以得到较高的解题效率？
b.概率分析：对于许多NPC问题，其困难实例出现概率小，平均性能好
c.近似算法：近似解代替最优解
d.启发式算法：别的方法不奏效

25.2SAT为什么是P问题？

2SAT问题之所以属于P问题，是因为存在一种多项式时间复杂度的算法来解决它，也就是强连通分量算法。其将2SAT问题转化为有向图问题，并查找图中的强连通分量。此算法可以在多项式时间内完成。 证明如下： ![image-20230627212515843](https://qitiantaile.oss-cn-guangzhou.aliyuncs.com/blog/image-20230627212515843.png) [注]：如果xi和 ¬xi属于同一强连通分量，即互相可达，肯定是矛盾式。 构造一张有向图G，把其中的每个变量拆成两个节点**2i**和**2i+1**，分别表示**xi**为假和**xi**为真，最后要为每个变量选择其中一个节点打标记。对于“**xi**为假或**xj**为假”这样的条件，我们连一条有向边 $$ 2i+1=>2j $$ 表示**xi**为真时**xj**必须为假，同理，还需要连一条有向边 $$ 2j+1=>2i $$ 其他条件类似，每个条件对应两条“**对称**”的边，整张图实际上描述了一系列必须满足的关系，选择**u**的情况下必须选择它所能到的所有点。 对于一个没有打标记的变量**xi**，我们先假定它为假，然后标记节点**2i**，并且沿着有向边标记所有能标记的节点。如果标记过程中发现某个变量对应的两个节点都被标记，则“**xi**为假”这个假定不成立，需要改成“**xi**为真，然后重新标记。整个算法没有回溯过程，如果当前考虑的变量不管赋值为真还是假都会引起矛盾，可以证明整个2SAT问题无解。 ## 26.什么是随机算法？作用和意义？举例 随机算法是一种使用概率和统计方法在其执行过程中对于下一计算步骤做出随机选择的算法。通常包括：随机生成的随机数和根据这些随机数做出的决策 作用和意义： + 避免陷入局部最优解 + 探索解空间 + 增加解多样性 + 提高效率举例 举例：数值概率算法、蒙特卡洛算法、拉斯维加斯算法、舍伍德算法； + 蒙特卡洛算法 
1
2
3
4
5
用于求问题的准确解
对于许多问题来说，近似解无意义，如判定问题；
但所得到的解不一定正确
求得正确解的概率依赖于算法所用的时间，时间越多，概率越大
缺点：无法有效地判别解的正确性
+ 拉斯维加斯算法 
1
2
3
拉斯维加斯算法会得到正确的解；
但算法有时会找不到解
多次求解可减小求解失效的概率
+ 舍伍德算法 
1
2
3
4
5
算法总能求得解，并且解是正确的
当一个确定性算法
在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，
可在这个确定性算法中引入随机性；
将其改造为舍伍德算法，减少差别
## 27.单向函数的意义及作用？举例 单向函数： 
1
2
对于每一个输入，函数值在多项式时间内可解；
对于随机的函数值，无法在多项式时间内使用确定性图灵机计算；
意义和作用： 
1
2
3
4
5
作用：单向函数一般用于产生消息摘要、密钥加密等，常见有MD5，SHA；
提供数据的保密性、完整性和认证性。
它们为密码学和信息安全领域提供了可靠的工具，使得加密和安全通信成为可能。

意义：如果单向函数存在，将证明复杂性类P/NP问题中，P不等于NP。
## 28.交互式证明思想和方法？举例 完备性：如果x∈L，则存在一个证明者P使得验证者V能以多项式时间接受x（且接受的概率大于2/3） 可靠性：如果x∉L，对于所有的证明者P，V接受x的概率不会超过1/3 能被交互式系统解决的问题记为IP类问题，可以证明NP ⊆ IP 应用：对典型的实际应用就是零知识证明 图的三色问题：为一个无向图的每个节点涂色(红、绿、蓝)，使得相邻节点颜色不同、在交互式证明中，证明者可以声称找到了一个图的有效的三色方案，并于验证者进行交互验证方案的正确性。交互过程如下： + 验证者随机选择图的一些节点，并要求证明者提供这些节点的颜色方案。 + 证明者根据自己的声称方案提供节点的颜色，并将这些颜色发给验证者。 + 验证者检查证明者提供的颜色方案是否满足相邻节点颜色不同的条件。 + 如果这个验证者发现任何错误，他可以指正并要求证明者提供更多的证据或者修正错误。 + 这个过程可以继续，知道验证者对证明者的声称满意。 除了该问题，交互式证明思想还用于素性测试(?)、证明性密码学等领域。 ## 29.对角线方法思想？举例 思想：利用对角线上的值做反证法。 证明 **N != R**,自然数集与实数集不存在一一对应: + 假设：自然数集N和实数集R之间，一定存在映射，即**N**可以进行一一列举出来，f(1)，f(2)....f(n), f(n)对应的是实数，将其限制在[0,1]之间； [0,1]之间的实数与整个实数集一定存在一一对应关系。 + 证明自然数集N和[0,1]区间内的实数，不可能存在一一对应关系： f(n)是一个[0,1]区间内的实数，则可以写成 f(1) = 0.a11a12a13... f(2) = 0.a21a22a23... **.** **.** **.** f(n) = 0.an1an2...ann，其中a的值是0-9中的一个数字； 假设存在一个f是从自然数集N和[0,1]区间内的实数的一一映射，对于对角线上的元素a11，a22，...，ann 设计一个实数 b = b1b2...bn，其中要求：bi != aii

如果自然数集N和[0,1]区间内的实数是一一对应的，那么一定可以找到一个自然数k，与实数b = b1b2…bn对应，实数b一定等于f(k);

与假设矛盾，设计过程要求bk != akk，而f(k)中第k个数值一定是akk，因此两个值不可能相等。

30.三种基本算法设计范式

  • 有理论保证的算法
    • 精确算法
    • 近似算法
  • 启发式算法
    • 在现实中往往有很好的性能
    • 但有时候会崩溃或者性能很差
  • 机器学习习得的算法
    • 让机器自己学习一个算法
    • 有一定通用性，但可解释性比较差

31.剖析计算复杂性和密码安全的关系

计算复杂性理论和密码安全之间存在密切的关系。计算复杂性理论研究问题的难度和解决方案所需的计算资源之间的关系，而密码安全关注如何设计和实现安全的加密和解密算法以保护敏感信息。

在密码学中，我们希望设计的加密算法具有“计算上的安全性”，即使在有限的计算资源下，攻击者无法有效地破解加密算法。计算复杂性理论提供了关于问题的困难程度和计算资源的理论界限的概念，这对于评估和设计安全的密码算法至关重要。

例如，基于大整数因子分解问题的RSA加密算法，其安全性依赖于计算大整数的因子分解的困难性。如果存在一种高效算法可以在多项式时间内分解大整数，那么RSA算法的安全性将受到威胁。因此，计算复杂性理论的发展对于验证和加强RSA算法的安全性至关重要。

此外，计算复杂性理论还为密码学提供了一些基本的概念和工具，例如多项式时间算法、随机性、非确定性等，这些概念和工具被广泛应用于密码学的设计和分析中。

总之，计算复杂性理论为我们提供了一种理论基础和工具，帮助我们分析和评估密码算法的安全性，并为设计和实现安全的加密算法提供指导。它在密码学的研究和实践中起着重要的作用，确保我们能够设计出抵御计算攻击的强密码系统。

32.如何理解：计算复杂性理论是计算机科学的哲学

  1. 抽象与本质：计算复杂性理论关注问题的本质难度和计算资源之间的关系，它不仅关注具体的算法和实现细节，而是更关注问题的可计算性和难解性。这使得计算复杂性理论具有哲学性质，它探索问题的本质特征和计算的边界。

  2. 问题的可计算性：计算复杂性理论关注哪些问题是可计算的，哪些问题是不可计算的。它探讨了计算问题的可解性和难解性，帮助我们理解问题的边界和局限性。这与哲学中的思考问题的可知性和认知边界的思想密切相关。

  3. 算法和计算模型的研究：计算复杂性理论研究了各种算法和计算模型的性质和特征，包括多项式时间算法、非确定性算法、随机算法等。这些研究使得计算复杂性理论具有对计算机科学中基本概念和模型的哲学思考。

  4. 计算的局限性：计算复杂性理论探讨了计算的局限性和困难性，例如NP完全性理论表明一类问题的解决是困难的，没有高效算法可以解决这些问题。这使得计算复杂性理论与哲学中的认识论和存在论等思想产生共鸣。

33.如何理解随机算法在密码学中的作用和地位？

随机算法生成的随机数在密码学中占有重要的地位，几乎所有的密码算法都要用到一些对攻击者来说必须是秘密的数据，而其中密钥必须是随机数。

34.简述素数问题PRIME及其复杂性分析？

1
给定M，求[0,M]中素数的个数

复杂性分析：

穷举法：

检测到根号N：

埃拉托色尼筛选算法：

欧拉筛选法：

35.简述零知识证明的基本思想

证明者能够在不向验证者提供任何新知识的情况下，使验证者相信某个断言或定理的真实性。

36.一个算法问题交给你后，应该怎么处理？

1
2
3
4
a.建模：对输入参数和解给出形式化或半形式化的描述
b.设计算法：采用什么算法设计
	 正确性：是否所有实例均有正确解
c.分析：分析算法效率

37.计算复杂性理论的认识？对今后学习的启发？

计算复杂性理论是计算机科学的一个重要分支，它研究计算问题的难解性和可解性。通过分析问题的复杂性，计算复杂性理论可以帮助我们理解何时可以期望找到高效算法来解决问题，以及何时问题可能是困难甚至是不可解的。

对于今后的学习，计算复杂性理论给我们带来了以下几个方面的启发：

  1. 算法设计的重要性：计算复杂性理论告诉我们，并非所有的问题都可以通过高效的算法解决。对于某些问题，可能不存在多项式时间内解决它们的算法。因此，在学习算法设计和问题求解时，需要考虑问题的复杂性，并寻找合适的算法来解决。

  2. 问题的可证明性：计算复杂性理论研究问题的难解性和可解性，它提供了一种形式化的框架来研究问题是否可以在有效的时间内解决。这启发我们思考问题的本质和边界，以及寻找问题的可证明性和难解性。

  3. 理论与实践的结合：计算复杂性理论不仅仅关注问题的理论分析，还与实际问题密切相关。它为算法设计和问题求解提供了基本的指导原则和方法。通过理解计算复杂性理论，我们可以更好地理解和设计高效的算法，提高计算问题的解决效率。

  4. 密码学和安全性的研究：计算复杂性理论对密码学和安全性的研究有重要的影响。它提供了分析密码算法安全性的工具和方法，帮助我们设计和评估安全的加密算法。

综上所述，计算复杂性理论对于我们理解问题的复杂性、算法设计和问题求解具有重要的启发作用。它提醒我们在实际问题中注重算法效率，并帮助我们更好地理解问题的可解性和难解性，促进了密码学和安全性领域的研究。

38.结合计算复杂性理论浅谈对云计算、大数据、物联网、人工智能安全思考？

计算复杂性理论在云计算、大数据、物联网和人工智能安全方面提供了一些重要的思考和指导。下面是对每个领域的简要讨论：

  1. 云计算：云计算涉及大规模的计算和存储资源共享，因此安全性是一个关键问题。计算复杂性理论可以帮助我们评估云计算中的安全性问题，例如数据隐私和身份验证。通过分析问题的复杂性，我们可以确定哪些安全问题是难解的，需要采取特定的安全措施来保护数据和系统。

  2. 大数据：大数据处理涉及海量的数据集和复杂的数据分析算法。计算复杂性理论可以帮助我们设计高效的算法来处理大数据，并评估算法的可扩展性和计算成本。在大数据安全方面，计算复杂性理论也可以帮助我们研究数据加密和访问控制的有效方法，以保护敏感数据的安全。

  3. 物联网：物联网连接了大量的设备和传感器，因此安全性成为物联网应用的一个重要问题。计算复杂性理论可以帮助我们分析物联网中的安全协议和算法的复杂性，以确定它们是否足够安全和可行。此外，计算复杂性理论还可以帮助我们设计高效的认证和密钥管理方案，以确保物联网设备和通信的安全性。

  4. 人工智能：人工智能的发展越来越依赖于大规模的数据和复杂的算法模型。计算复杂性理论可以帮助我们评估人工智能算法的计算复杂性，并指导我们选择适当的算法和优化方法来提高性能和效率。在人工智能安全方面，计算复杂性理论还可以帮助我们分析和评估人工智能模型的鲁棒性和防御性，以抵御对抗性攻击和隐私侵犯。

综上所述，计算复杂性理论为云计算、大数据、物联网和人工智能安全提供了思考和指导。它可以帮助我们评估问题的复杂性和可解性，设计高效的算法和安全方案，以保护数据和系统的安全性。

39.N个乒乓球中有一个和其他的质量不同，用天平最少几次能称出来？

不考虑最后得到的乒乓球质量和正常质量相比是大是小，最少需要[log3(2n+1)]；

考虑最后乒乓球质量的大小，最少需要[log3(2n+3)]；

40.图灵机相关问题

image-20230627213831778

image-20230627213850389

image-20230627213943465

image-20230627214049933

image-20230627214329899

例题：image-20230627214558204

image-20230627214910488

![image-20230627214828247](https://qitiantaile.oss-cn-guangzhou.aliyuncs.com/blog/image-20230627214828247.png)

image-20230627214828247

image-20230627215324421

image-20230627215626212

image-20230627220346752

image-20230627220402800

41.NP问题之间归约？常见的NPC问题？

NP问题归约：(从上到下)

image-20230627205644167

常见NPC问题：

  • 布尔可满足性问题：是否存在一组变量使得问题可满足。
  • 0-1整数规划

  • 分团问题：一个图中是否有大小是k个的团。任意挑出k个点，可判断是不是一个团，所以问题是NP；

    • setpacking
    • 最小顶点覆盖

  • 图着色问题

  • 背包问题

    image-20230627211504443

42.SAT、2SAT、3SAT

image-20230627212725004

43.素数判定的递归和非递归算法

递归：

1
2
3
4
5
def isPrime(n,i):
	if(n<=2): return n==2
	if n%i == 0: return false
	if i*i>n: return true
	return isPrime(n,i+1)

非递归：

1
2
3
4
5
def isPrime(n):
	if n<=1: return false
	for(i in range(2,n**0.5)+1):
		ifn%i == 0:return false
	return ture

44.为什么停机问题是不可判定的？

参考资料

(118条消息) NP完全性理论简介_np完整性_liusiqian0209的博客-CSDN博客

(118条消息) NP完全性理论简介_np完整性_liusiqian0209的博客-CSDN博客

算法学习笔记(71): 2-SAT - 知乎 (zhihu.com)

科学网—什么是“判定问题”？（2）－悖论、停机问题与NP - 柳渝的博文 (sciencenet.cn)

：https://link.zhihu.com/?target=https%3A//www.bilibili.com/video/BV1qb41187AG%3Fshare_source%3Dcopy_web