浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。28.文法是CFG的推广,任何CFG都是文法。G=(V,∑,R,S)29.语言被文法生成ⅲ它是re的。30.所有数值函数都是原始递归的31.原始递归函数集是递归可枚举的。32.特殊语言/问题H={"M"w":M在w上停机}lH={"M"w":M是一台在"w"上不停机的TM}H1={"M":M在“M”上停机}H1={w:要么w不是一台TM的编码,要么w是M的编码,M是一台在"M"上不停机的TM}H:re.;H1:re.;-H,-H1:非r.e.;2-SAT∈P;SAT∈NPThe world as We Dont Know itreAsumming P≠APCo『eHrecursiveSATSATCO-A伊II Asumming P=Npr, eCo-r.erecursiveNP= cO-Np= p33没有算法的问题称作不可判定的or不可解的,如TM的停机问题34.证明不可判定通用图灵机U通过递归函数归约到L如果L是递归的则U是递归的ic若L1非递归,并存在L1到L2的归约,则L2也非递归。递归函数是 Turing Computable的35.语言是图灵可枚举的,证存在枚举它的图灵机。(M通过空格代开始,周期性的经过特殊状态q来枚举L,任意顺序且可重复)6.不可判定语言与递归语言互为补集,与rc语言有交集。37语言是re.,if它是图灵可枚举的;语言是递归的,i它是以字典序 turing可枚举的。8.P在并交连接和补运算下封闭NP在并、连接运算下封闭。若NP在补下封闭则NP=P39.H={M"wM在最多2w步后停机}唾P40.所有正则语言和所有CFL都属于P41.NPA.机器角度去定义:被多项式界限非确定型图灵机判定的所有语言的类。B.基于 verifier的定义:NP问题上建立的非确定机包含两步1)非确定地猜一个解2〕用一个确定的算法判定该解是否为可行解判定一个给定猜测值是否满足该问题(可满足性)的算法称作 verifier,一个问题称作NP问题当且仅当存在一个多项式时间的 verifier这两个定义是不矛盾的,因为如果一台非确定TM在多项式时间内可以判定一个非确定选择的翰入是否满足,就是基于 verifier的定义。P和NP的区别a problem is in P if we can decide them in polynomial time. It is in NP if we candecide them in polynomial time, if we are given the right certificate42.若存在计算函数f的多项式界限的图灵机M,则f称为多项式时间可计算的43.若τ1是L1->l2的多项式归约,τ2是L2->I3的多项式归约,则τ1τ2是L1->l3的多项式归约44.证明NP完全法一、按定义:LΣ*,若(a)L∈NP,且(b)对每个语言L∈NP,存在从L到L的多项式归约则L称为NP完全的。法二、归约,对于语言L,(a)若L∈NP(b)一个NP完全问题可以在多项式时间规约到L,ie. SAT 0 is context-free but not regular49.L=L1L2,L是CFL,则L1一定是CFL(x50. Regular-CFL不一定是CFL,如a*b*c*-anbn包含 anben51. 2-way PDalie PDa whose input heads can move both left and right] are more powerfulthan 1-way pda52. Given a PDa M1 and an fa M2, the problem l(M1)cl(M2)is decidable53.DFA/NFA识别的是 exactly正则语言54.Re.只在补和差下不封闭,CFL在交下也不封闭55.非正则语言的可能是正则语言。比如A:[W=w}及所有回文,A=*,为正则语言56.典型非正则:w=wR57.正则语言的子集可能非正则,如 anben是a*b*c*的子集;又如Σ*是正则语言,H≌Σ*58.归约:X到Y的归约可以理解为X到Y问题的映射, reduction可以解释为 at least asdifficult as….比如ⅹ可以被Y的算法解决,则 X is no more difficult than yⅩ可以约到Y,记X≤Y。e.gx2可以归约到任意两数的乘积。若有A≤B,A是不可判定问题>B不可判定A不递归->B不递归B可判定>A可判定B是递归的->A是递归的59.若X多项式时间归约到Y,Y多项式时间可解,则X多项式时间可解若X多项式时间归约到Y,Ⅹ多项式时间不可解,则Y多项式时间不可解60.X多项式时间归约到Y,Y多项式时间归约到Z,则X多项式时间归约到Z61.PRME( COMPOSITE)多项式时间归约到 Factor,但是 Factor多项式时间不能归约到PRIME COMPOSITE )o62.若A≤PB,B∈NP,则A∈NP。证明A≤PB→存在确定图灵机X,可将A归约到B。B∈NP→存在一个非确定图灵机N可判定B。我们希望构造一个新的TM(ⅹN)是的ⅹ*N非确定多项式时间求解A,则A∈NPRunning time of X*N≤1+p(mB>+qp(m)(B多项式时间非确定判定是多项式时间所以A∈NP63若AsPB,B∈P,则A∈P64.若X是NPC的,则X在多项式时间内可解ifP=NP65.SAT多项式时间归约到3SA(3AT是NPC的)66.证明语言L是R/Re, Non rea) Intuitively想想有没有半判定(判定)的TM,有则Rc、(R)。若非R执行下一步。b)用能否由Re.( Non re.)语言归约到该语言,能则Re而非R( Non re)严格用归约函数定义f:A≤B,r1∈A当且仅当r1∈Beg1∈H,M∈L证明Recg2∈非H,iM∈L证明 Non rc注意方向:是从A的实例经过递归函数推向B的实例。详细介绍http://www.cs.rice.edu/nakhleh/comp481/finalreviewsp06sol.pdf67.递归与μ递归等价68.PDA中,若每一个格局至多有一个格局接在它后面,则为确定型的。确定型CF在补下封闭69.M半判定L:w∈L,ifM在w上停机,注意半判定图灵机中不存在“拒绝”状态。只要不接受w,就不停机。70. Chomsky hierarchyElements of the Chomsky HierarchyRecursively enumerable languagesRecursive languageContext sensitive languagesContext ee languageseterministccontext free languagesRegularanguages71.俩证明7.6证明P在并、交、 Kleene*连接和补运算下封闭(1)并:对任意L,LEP,遴n时间图灵机M1和nb时间图灵机M2判定它们且c=max{ab}对L1L2构造判定器MM=“对于输入字符串w1)在W上运行M1,在w上运行M22)若有一个接受则接受,否则拒绝。时间复杂度:设M1为0(n)M2为0(m)。令c=max{ab}第一步用时0(n+n),因此总时间为Oma+n)=0(n9所以L1L2属于P类,即P在并的运算下封闭。(2)连接对任意L1,L2属于P类,设有n时间图灵机M1和m时间图灵机M2判定它们,且c=max{ab}。对L1l2构造判定器MM=“对于输入字符串w=w2灬,Wn对k=0,1,21…,n重复下列步骤。在wW2…wk上运行M1,在wk1wk+2…n上运行M若都接受,则接受。否则继续。若对所有分法都不接受则拒绝。时间复杂度:(n+1x0(n+0m-0(m+4)+0(nb+4=0(nc+),F以L1oL2属于P类,即P在连接的运算下封闭。对任意L属于P类,设有时间0(n)判定器M判定它,对构造判定器MM=“对于输入字符串〔1)在w上运行M12)若M1接受则拒绝,若M1拒绝则接受。时间复杂度为:0(m)。所以属于P类,即P在补的运算下封闭。77证明NP在并和连接运算下封闭。1)并对任意L1,L2∈NP,设分别有n时间非确定图灵机M1和n时间非确定图灵机M2判定它们,且c=max{a,b}。构造判定LL2的非确定图灵机M:M=“对于输入字符串w1)在W上运行M1,在w上运行M2。2)若有一个接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时为O(n-)+O(n),因此总时间为On+n)=0(n。所以LLz∈NP,即NP在并的运算下封闭2)连接对任意L,L2∈NP设分别有na时间非确定图灵机M1和m时间非确定图灵机M2判定它们,且c=max{ab}。构造判定L1oL2的非确定图灵机M:M=“对于输入字符串w:1〕非确定地将分成两段xy,使得w=xy。2)在x上运行M1,在y上运行M23)若都接受则接受,否则拒绝。对于每一个非确定计算分支,第一步用时O(n,第二步用时为0(n)+0(m),因此总时间为o(n+m)=0(n。所以L1oL2∈NP,即NP在连接运算下封闭。专题一一图灵机可判定性问题判定以下问题是否可判定:声明:思路—想证明B问题不可解,1.从一个不可解问题A入手(如停机问题)2.创建B的—个实例,从中推出如果能解决B,A也就可以解决了3.所以B是不可解的1.一个图灵机有至少481个状态。我们可以给出这样一个TMN进行cnc(M)a)数M中状态数,直到481b)如果达到了481,N就接受,否则拒绝2.给定图灵机在空串上走了481步还没停机。构造2带图灵机N,a)2a带:写481个0b)1s带在空串上模拟M,每走一步,第2带就删掉一个0c)如果M在所有0都删掉之后停机,则N接受,否则不接受给定图灵机,判定它是否在一些输入上经过481步还没停机?a)按字典序找出所有 length
- 2020-12-01下载
- 积分：1
ZYNQ中文资料书
中文版详细的ZYNQ基础知识，可以使刚接触ZYNQ有系统的认识。The zong book基于含有 ARM Cortex9的 Xilinx Zyng网-7000全可编程片上系统的嵌入式处理器se h. crockett ross a elliotMartin A. Enderwitz robert w. stewartJianfeng Lu(中文痂)Department of Electronic and Electrical EngineeringUniversity of StrathclydeScotland, uK翁恺博士Dr.K.Wen(h文翻译浙江大学(中国)第一版(中文版)This edition first published June 2016 by Strathclyde Academic MediaLouise h. crockett ross a. elliot, martin a. enderwitz and robert w. stewart开源许可此书既有印刷版又有电子版(PDF格式)。在衍生文件中明确标注参考内容初始来源的前提下,本书中任何文本和图表可以被复制,并用于非营利性的学术目的。参考格式应当遵循以下格式L.H. Crockett, R. A. Elliot, M. A. Enderwitz and R W. Stewart, The Zynq Book: Embedded Processing withthe ARM Cortex-A9 on the Xilinx Zynq-7000 All Programmable Soc, First Edition, Strathclyde AcademicMedia, 2016将本书中内容用于其他非营利性学术目的的,请联系info@zyngbook.com。此书不能以原始的格式使用,也不能被末授权的第三方机构销售。习题教材习题教材在本书的官方网站上发布:www.zynqbook.com参考此习题教材同样适用于开源许可条及在本页其他位看提到的警告和免麦声明警告和免责声明作者、出版人在硏究所包含的课趑和编写例懃时,已经尽了最大的努力来提供准确、最新的信息。本着倣得最好的理念,书中包含的材料以“原样”的形式提供,但是无论是作者还是出版人没有任何明确或者隐含的承诺来保证书中所包含内容的准确性。书中包含的任何信息直接或间接导致的任冋损失、损坏,作者和岀版人将不会承担法律责任。商标ARM, Cortex,AMBA, Thumb和 Trustzone都是ARM有限公司(或其子公司)在欧洲和(或)世界其他各地注册的商标。保留所有权利NECN是ARM有跟公司(或其子公司)在欧洲和(或)世界其他各地的商标。保留所有权利。此出版物是独立的,不属于ARM有限公司。ARM有限公司也没有认可、赞劻或授权此出版物Xinx(xinx公司的logo),Artⅸ,ISE, Kintex, LogiCORE, Petalogix, Spartan, virtex,vⅳado,zynq,和Web pAck是 Xilinx注册的商标。保留所有权利。MATLAB和 Simulink是 MathWork5公司注册的商标。Linux的是 Linus torvalds在美国和其他国家注册的商标。本书中使用的所有其他商标属于其各自的公司。本书中使用这些商标并不意味着本书拥有、认可这些商标。目录前言作者简介XXI鸭谢章节引言鲁鲁D自。自。自d看非鲁鲁。音D鲁。111zynq的片上系统12嵌入式SoC的简单剖析…..13设计重用14提升抽象层级1.5S0C设计流16实践单元17关于本书18参考文献PART A开始了解Zynq…13章节2Zynq芯片(“是什么”)1521处理器系统211应用处理器单元(APU)212关丁ARM模式…202.1.3处理器系统外部接口2122可编程逻辑22221逻辑部分2.2.2特殊资源:DSP48E1和块RAM522.3通用输入/输出28224通信接口2.2.5其他可编程逻辑扩展接1|……2923处理器系统与可编程逻辑的接口………30231AXI标准…3023.2AXⅠ互联和接口…23.3EMI0接口…342.34共他PL-PS信号3424安全241安仝引导,3524.2硬件支持3624.3运行时刻安全3625Zynq-7000系列成员…3926本章回顾4027架构参考指南4128参考文献4章节3zynq设计指南(“如何使用它?”)…473.1入门∴1483.11获取设计工具…3.12开发工具内部版本和证书31.3设计工具功能3.14第三方工具3.1.5系统安装和需求513.2设计流程概述32.1需求和技术参数…3.2,2系统设计···543.2.3硬件开发和测试324软件开发和测试…583.2.5系统集成和测试603.3S0C设计团队6034使用 Vivado进行以IP为重点的系统级设计35ISE和 Vivado设计套件3.51特性比较64352升级到Vl vado3.6开发板3.6.1 Zynq-7000 SoC ZC702 Evaluation Kit .....673.6.2 Zynq-7000 Soc video imaging kit693.6.3 Zyng-7000 ZC706 Evaluation kit693.6.4 ZedBoard63.6.5ZYB06936.6第三方开发板70367附件和扩展36.8使用开发板工作723.7支持和文档38章节回顾39参考文献章节4芯片比较(“为什么我需要Zyna?”)中中4.1芯片选择的条件42比较一:Zynq对FPGA80421Ⅶ icroblaze处理器8042,2Ⅶ icroblaze单片机系统844.2.3 Picoblaze854.2.4 ARM Cortex-M8542.5其他处理器类型…8542.6总结说明8743比较二:Zynq对标准处理器89431处理器操作89432执行分机433总结说明9444比较三:Zynq对分立的FPGA处理器组合45拓展Zynq架构和设计流9646本章回顾47参考文献…99章节5应用和机会(“拿它能做什么?”).1015.1应用的概述,10251.1汽车102512通信5.1.3防务和航空航大∴1035.14机器人、控制和仪器1045.1.5图像和视频处理l0451.6医药1055.1.7高性能计算(HPC)1055.18其他及未来的应用10552何时Zynq真的有用...1065.3通信:软仆定义无线电(SDR)107531在无线通信中的趋势10753,2介绍软件定义无线电(SDR)l08533SDR的实现和授权技术108534认知无线电54智能系统和智能网络11154.1什么是智能系统542智能系统的例子112543智能网络:智能系统的通信114544相关桃念∴5.5图像和视频处理,及计算机视觉5.5.1图像与视频处理1155.5,2计算机视觉…116553抽象的层级…..1175.54图像处理系统的实现1185.55Zynq上的计算机视觉的例子:道路标识识别…12056动态片上系统12156.1运行时刻系统灵活性121562动态部分重配置(DPR)12156.3DPR应用的例子…564DPR的好处…..124571什么是生态系统?系统57更多的机会:zynq的“生态,125125572有什么机会?12658本章回顾1285.9参考文献………128章节6 The Zedboard∴1336.1介绍Zed…336.2 edboard系统架构1346.3 Zedboard设计流程13664 SeaBoard入门」137641盒子里有什么?137642使件安装13764.3烧写 Zedboard1386.5 MicroZed14266文档,教程和支持14266.1关」 Zedboard的文档…126.62演小和教程14366.3在线课程…14366,4其他 Zedboard资源和支持14467 Zedboard.org社区…144671社区工程44672博客144673支持论坛14568本章回顾14569参考文献146章节7教育、研究和培训∴…自看·鲁。非。鲁自。自。鲁。鲁自普●。。●音。。鲁D。。。。自着垂··。音。鲁D1477.1技术趋势和SoC教育1487.2大学用Zynq教学149721用 Xilinx工具和板教学149722数字设计和FPGA教学…150723计算机科学…150724嵌入式系统和SOC设计1507.2.5算法实现(如信号、图像和视频处理15172.6设计重用152727新的和正在出现的设计方法15372.8传感、机器人和原型154729一个例子课程15473项日和竞争74学术研究75 Xilinx大学计划(XUP)15875,1介绍XUP752软件技术和许可158753XUP开发和教学板…159754XUP研讨会和培训材料159755对大学的投术支持1607.5.6资格160757联系XUP1607.6企业培训1607.6.1诛程的授权的培训提供者…1607.6.2其他资源16176.3在线视频l6177本章回顾16178参考文献章节8 Zynq的第一个工程.658.1软件安装指导目标和结果16683练习1A概述…ss………s……I6684练习1B概述1678.5练习1C概述l6886可能的扩展16987接下来是什么?16988参考文献169PART BZynq Soc&硬件设计。告D。垂D。0。春DD。。。。B看D。。。l71章节9嵌入式系统和FPGA.7391什么是嵌入式系统?173911应用1174912一般嵌入式系统架构…..17592处理器2.1协处理器17922处理器 cache177923执行周期179924中断18393总线184
- 2020-12-11下载
- 积分：1
