唐常杰翻译的计算理论导引19

《唐常杰翻译的计算理论导引19》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、可根据提供的ＰPT素材+参考以前同学的报告，修改成为有自己见解的讨论报告建议：底色用浅色（象牙白，浅黄，白色等）适合色盲色弱观众字体颜色选择余地大在投影机效果差时也还能能看见Chap8空间复杂度1空间复杂度定义定义８.1M的空间复杂度对于在所有输入上都停机的确定型图灵机f:N→N；n为输入长度，f(n)为扫描带方格的最大数对于在所有输入上都停机的非确定型图灵机f:N→N；n为输入长度，f(n)为任何计算分支上扫描带方格的最大数实践中是存储器（内外存）消耗问题定义８.2SPACE(f(n))={L

2、

3、L是被O(f(n))空间的确定型TM判定的语言}NSPACE(f(n))={L

4、L是被O(f(n))空间的非确定型TM判定的语言}2SpaceCanBeReused例８.3NP完全问题SAT的空间复杂度算法说明：输入<φ>，φ是布尔公式①对φ中的每个变量xi赋真值②计算φ值③φ为1则接受，否则拒绝分析输入长度为n，所以变量个数m≤n输入占带子n格，变量赋值占m格（且可反复使用），共占m+n≤2n格所以空间复杂度f(n)=O(n)3Savitch定理定义８.2SPACE(f(n))={L

5、L是被O(f(n))空

6、间的确定型TM判定的语言}NSPACE(f(n))={L

7、L是被O(f(n))空间的非确定型TM判定的语言}定理８.5对于任何f:N→N，f(n)>n，有：SPACE(f2(n))ÊNSPACE(f(n))说明确定图灵机在O(f2(n))的空间下能够判定的语言集合包含了非确定图灵机在O(f(n))空间下能够判定的语言集合说明一个O(f2(n))空间下的TM可以替代O(f(n))空间下的NTM作判定８4Savitch定理证明思路错误思路TM模拟NTM的方法参见P152，定理8.10证明广度优先的分支模拟，导致2

8、O(f(n))的空间消耗证明思想可产生性问题:判定NTM能否在t步内从格局c1变到c2如c1=cstart，c2=caccept，则可判定NTM是否接受输入递归算法如存在cm，使得NTM可在t/2步内c1→cm且NTM可在t/2步内cm→c2问题递归为两个可产生性问题，可重用空间5Savitch定理证明递归函数boolCanYield(c1,c2,t)if(t==1&&(c1==c2

9、

10、c1→c2只需一步))returntrue;if(t>1){for(每个格局cm){boolr1=CanYield(c1,c

11、m,ceil(t/2));boolr2=CanYield(cm,c2,ceil(t/2));if(r1&&r2)returntrue;}}returnfalse;实际上就是求CanYield(cstart,caccept,2O(f(n)))分析分析递归深度log2t，t是步数，所以就是所有分支上的最大可能时间t=2O(f(n))，log2t=O(f(n))每递归一层，需要补充O(f(n))的空间因此最大空间：O(f(n))×log2t=O(f2(n))68.3.3广义地理学报告人：7主要内容8.2PSPACE

12、类。1个定义，几个关系搞清楚（p184图9-1）8.3PSPACE完全性。1个定义，理解定义和NP完全问题定义不同的内涵；TQBF及其PSAPCE完全定理证明8报告人：ＸXXPSPACE完全性P1879内容提要８.3.2博弈的必胜策略博奕论定理８.10８.3.3广义地理学地理学定理８.1110８.3.2博弈的必胜策略博奕论-TheGameTheory日光浴者海滩1/43/4博奕论：关于包含相互依存情况中理性行为的研究。P18711博奕论：每个游戏常有2个以上的参加者，他们（局中人）在游戏中都有自己的切身利益，

13、每个局中人都有自己的可行行动集供自己选择，这种选择毫无疑问地会影响到其他局中人的切身利益。游戏中各个局中人理性地采取/选择自己的策略行为，使得在这种相互制约相互影响的依存关系中，尽可能提高自己的利益所得，这正是游戏理论的关键所得。P187８.3.2博弈的必胜策略博奕论-TheGameTheory12棋手间的对弈问题敌我双方在作战过程中每一阶段的排兵布阵问题特点：一招制敌，见招拆招，以静制动，主动出击，把握关节点，争取主动权等关键：互博最终分出胜负P187８.3.2博弈的必胜策略13TQBF={

14、f是真的

15、全量词化布尔公式}P185８.3.2博弈的必胜策略TQBF语言问题表达式布尔表达式：包含布尔变量、常数0,1、布尔运算符与/或/非量词化布尔表达式：包含存在量词和全称量词全量词化布尔表达式（句子）：每个变量都出现在某一量词的辖域内语言：所有真的全量词化布尔表达式的集合14寻求一种策略，使一方只要采取一定的策略，无论对方采取什么策略，己方都能找到相应的对策，使最终的结果为己方获胜.TQBF(真全量词化