浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。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
多波束测深和图像数据处理
本书详细讲解了多波束测深的原理、侧扫声呐在海底地形绘制、水下目标识别的应用、可以供水声等相关专业科研人员参考国家“十一五”重点图书地球空间信息学丛书/李德仁主编多波束测深及图像数据处理■赵建虎刘经南著WUHAN UN∨ ERSITY PRESS武汉大学出版社图书在版编目(CIP)数据多波束测深及图像数据处理/赵建虎,刘经南著.一武汉:武汉大学出版社,2008.9国家“十一五”重点图书地球空间信息学丛书/李德仁主编ISBN978-7-307065000Ⅰ.多…Ⅱ.①赵…②刘…Ⅲ.海洋测量一测深一卫星图像一图像处理Ⅳ.P229-39中国版本图书馆CP数据核字(2008)第129252号责任编辑:任翔责任校对:黄添生版式设计:马佳出版发行:武汉大学出版社(430072武昌珞珈山)(电子邮件:wdp4@whu.edu.cn网址:ww.wdp.com.cn)印刷:武汉中远印务有限公司开本:720×10001/16印张:24.25字数:446千字插页:1版次:2008年9月第1版208年9月第1次印刷ISBN978-7-30706500-0/P·138定价:45.00元版权所有,不得翻印;凡购我社的图书,如有缺页、倒页、脱页等质量问题,请与当地图书销售部门联系调换。前言随着陆地资源的还渐匮乏,人类已将资源开发和利用的重点转向了占整个地球面积71%、蕴藏着丰富自然资源的海洋。我国已于20世纪末制定了21世纪海洋强国战略,其宗旨是将我国建设成为世界级的海洋强国。在这一世纪性战略中,海洋测量作为人类一切海洋活动的基础,必将扮演着十分重要的作用。随着电子、计算机、信息等相关技术的迅速发展,当今的海洋测量正呈现蓬勃的立体发展态势。在这一大背景下,基于船载测量设备的海洋调查和勘测技术、手段及方法在我国也取得了日新月异的成就,尤其是自20世纪90年代引进的多波束系统,无论是测点的精度、密度和代表性,均是以往传统水下地形测量方法所不能比拟的,真正地实现了从“点”、“线”水下地形测量到条带式、全覆盖、“面”测量的变革,给我们真实、详细地呈现出了海底的精细地形和地貌,使人类能够首次全面地认识“漆黑”的海底世界。然而,由于多波束系统引进的时间较短,我国对该系统的认知还基本处于初始阶段,许多拥有多波束系统的测量单位到目前为止还停留在依照系统参考手册和操作规范实施作业的初始应用阶段,远没有最大限度地发挥该系统的应用潜力。另外,由于对相关知识的了解和认识不足,系统的应用远没有达到预期的精度。为了改善多波束系统在我国当前的应用状况,提高系统的应用和开发潜力,本书围绕多波束系统具有测深和获取声呐图像两大功能,在论述多波束系统的发展历史和工作原理的基础上,对多波束测量中涉及的平面基准及其相互转换、潮汐调和分析及海洋垂直基准面、声速及声线跟踪、辅助参数的测定、滤波及补偿、多波束测深数据滤波、基于已有软件的多波束数据处理过程及分析、声强数据的处理及声呐图像的形成、声呐图像的处理、多波束声呐图像的应用、多波束测量信息和侧扫声呐测量信息的融合等主题展开了深人的研究,详细地介绍了这些研究目前取得的最新进展研究所采用的理论和方法,同时还给出了这些理论和方法的实际应用效果。这些研究成果对从事多波束研究和实际工程应用具有一定的借鉴作用。本书共分12章,第1至2章主要由刘经南院士赵建虎完成,着重介绍了船多波東测深及图像数据处理载测深系统的发展历史以及多波束数据处理技术的现状和发展趋势,第3至8章着重介绍了测深数据的处理方法、理论及实际应用。在这部分中,从第3章到第7章由赵建虎和刘经南院士完成,第8章由陈义兰、杨琨、吴永亭、周丰年完成;第9至11章着重介绍了基于多波束回波强度信息所生成的声呐图像的形成、处理及应用,由赵建虎和刘经南院士完成。第12章在系统分析了多波束和侧扫声呐测量内容特点的基础上,提出了综合二者测量信息,通过信息的有机融合处理获取海底高精度声呐图像和高分辨率地形的思想和方法,对二者的信息融合方法、理论进行了探讨,并对其应用前景进行了展望。由于本书涉及的内容比较多,许多领域是目前国内外研究的热点问题,加之作者水平有限,书中有不妥之处,敬请各位专家与读者批评指正。编者2007年8月目录第1章绪论…1.1引言甲鲁···船载测深系统的发展历史1.2.1原始测深方法看·曲单非·鲁非看P即·鲁。看4451.2.2常规测深系统……1.2.3多波束测深系统1.2.4多波束测深系统的最新进展1.2.5我国的多波束测深系统………………101.3多波束数据处理技术的现状和发展趋势……1.3.1声速及其声线跟踪1.3.2多波束辅助参数的测定和滤波1.3.3深度数据滤波…131.3.4图像处理……………………………131.3.5多波束数字信息与侧扫声呐图像信息的融合……………141.4本书的结构体系141.5本章小结15参考文献16第2章多波束系统的工作原理··········………………182.1多波束系统的组成182.2多波束系统的声学原理…202.2.1相长干涉和相消干涉以及换能器的指向性202.2.2换能器基阵的束控…b·●量垂看·杳·有242.2.3波束的形成………252.3波束的发射、接收流程及其工作模式鲁自·t··。命272.4波束的能量衰减及其时间增益补偿……302.5底部检测及系统探测能力的估算……30多波束测深及图像数据处理2.6波束脚印的归位问题…312.7本章小结34参考文献中自●非·幽35第3章平面基准及其相互转换3.1地心坐标系…373.1.1地心坐标系的定义……………………373.1.2地心坐标系的建立383.1.3已有的地心坐标系统及其参数423.2参心坐标系433.2.1参心坐标系的定义433.2.2参心坐标系的建立4432.3我国常用的参心坐标系及其参数……453.3坐标系间的相互转换……………………………………473.3.1大地坐标系与空间大地直角坐标系转换的数学模型473.3.2不同的三维空间直角坐标系转换的数学模型483.3.3不同大地坐标系转换的数学模型…493.4高斯投影·鲁·513.4.1高斯投影概述3.4.2椭球面元素到高斯投影面的转换曾·q。鲁普鲁看曹鲁·鲁543.4.3高斯投影的邻带坐标换算553.5UTM(通用横轴墨卡托)投影…鲁由申鲁由563.6独立坐标系583.6.1独立坐标系概述583.6.2独立坐标系的建立583.6.3独立坐标系与其他几种典型坐标系的转换613.7本章小节…63参考文献…………63第4章潮汐调和分析及海洋垂直基准面∴644.1平衡潮理论……644.1.1引潮力(势)644.1.2引潮力势的调和展开………鲁·664.1.3平衡潮及其主要结论68日录4.1.4实际潮汐的潮高……84.2潮汐、潮流分析704.2.1潮汐分析……………………………704.2.2潮流分析…………724.2.3溯汐动力学理论734.3垂直基准764.3.1平均海平面……………………………………………774.3.2国家高程基准794.3.3海图深度基准面…804.4基准传递与推估……854.4.1短期验潮站平均海平面的确定854.4.2深度基准面传递与推估874.4.3平均海平面和深度基准面的综合传递884.5海洋垂直基准统一框架894.5.1平均海平面作为海洋统一垂直参考基准…894.5.2以椭球面作为海洋统一垂直参考基准…894.6本章小结……………………………………………………92参考文献………………………………………92第5章声速及声线跟踪945.1海洋声学…·日945.1.1海洋声速…965.1.2声波在海水中的传播特性………………………………975.1.3声道…1005.1.4海洋噪声…………1015.2海水中声速的确定…………1015.2.1声速剖面的直接测量申鲁·杳·………10252.2声速的间接确定1045.3基于自组织神经网络的声速剖面分类方法1125.3.1SOFM神经网络1125.3.2声速剖面的描述1135.3.3用于划分声速剖面类别的S0FM神经网络的构造和训练…1145.3.4实验和分析1155.4局域空间声速模型的建立120多波東测深及图像数据处理5.4.1局域空间声速模型的建立∴…………………1205.4.2实践及分析…………………………1215.5声线跟踪法1245.5.1 Harmonic平均声速1255.5.2基于层内常声速假设下的声线跟踪算法…1265.5.3基于层内常梯度假设下的声线跟踪算法1275.6等效声速剖面法1285.6.1一个重要事实的证明1285.6.2误差修正法12956.3等效声速剖面法1305.7声线跟踪过程及各方法的比较鲁鲁·着·。鲁非·。…1325.7.1声线跟踪法的计算过程1325.7.2误差修正法和等效声速剖面法的计算过程1335.7.3各种方法的比较13458实践及分析……………1355.9声速对多波束测量成果的影响……4··1375.9.1声速剖面测量误差的产生…………………………1375.9.2声速误差的影响1385.10本章小结……………………141参考文献141第6章辅助参数的测定、滤波及补偿…………1436.1多波束测量中的定位技术●寺章萨。1436.2局部无缝垂直参考基准面的建立1466.2.1精密局域大地水准面的确定1476.2.2局域海图基准高程模型的建立p●曹D●14862.3建立 Saint John河无缝垂直参考基准的实践和过程分析……1486.3GPS船姿测量…····“··1566.3.1坐标系统的定义及其相互关系1566.3.2船体姿态测量原理…1576.3.3实验及分析1586.4船姿分析及其补偿…l616.4.1船姿受动因素分析1616.4.2船姿对多波束测量的影响……………………162
- 2020-12-05下载
- 积分：1
|
联系客服（QQ：3324461878）
