浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。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
ArcGIS Engine 10 开发中文帮助
不可得的学习资料，详细介绍AE开发技术……esrChinaBEIJING内部文档,请勿外传刷定及修订记录版本完成日期编写/修订纪要编写者备注文档目录结林雪淋构刘宇完善控件介绍和空间数刘宇据库的介绍完善柵格数刘宇据介绍完善符号化刘宇介绍完善网络分刘宇析功能完善参考系刘宇的介绍完善儿何对刘宇象的介绍esrChinaBEIJING内部文档,请勿外传目录介绍和开发相关的知识三.使用控件创建第一个桌面应用程序四.空间数据库五.几何对象和空间参考六.矢量数据空间分析七.符号化八.栅格数据分析九.编辑十.地图输出十实战十二安装部署esrChinaBEIJING内部文档,请勿外传介绍软件架构ArcPadArcGIs标准测览器MobileEngineArcGISExplorerArclnfoPArcEditorOnline GisNetworkArcviewArcReaderArCGIS ServerArcImsArcsDE文件DBMS是在全面整合了与数据库、软件程、人Ⅰ智能、网络技术及其它多方面的计算机主流技术之后,成功地推出了代表最高技术水平的全系列产品是一个全面的,可伸缩的平台,为用户杓建一个完善的系统提供完整的解决方案的基本体系能够让用户在任何需要的地方部署功能和业务逻辑,无论是在桌面、服务器、还是在野外:桌面(桌面软件产品是用来编辑、设计、共享、管理和发布地理信息和概念。桌面可伸缩的产品结构,从,向上扩展到和。目前被公认为是功能最强大的产品。通过一系饥的可选的软件扩展模块,产品的能力还可以进一步得到扩展嵌入式(是一个完整的嵌入式组件库和工具包,开发者能用它创建一个新的、或扩展原有的可定制的桌面应用程序。使用开发者能将功能嵌入到已有的应用程序中,如基于工业标准的产品以及一些商业应用,也可以创建自定义的应用程序,为组织机构中esrChinaBEIJING内部文档,请勿外传的众多用户提供功能。服务器(和用丁创建和管理基丁服务的应用程序在大型机构和互联网上众多用户之间共享地理信息是一个中心应用服务器,它包含一个可共享的软件对象库,能在企业和计算框架中建立服务器端的应用。是通过开放的协议发布地图、数据和元数据的可伸缩的网络地图服务器。是在各种关系型数据库管理系统中管理地理信息的高级空门数据服务器。栘动(支持的无线移动设备,越来越多地应用在野外数据采集和信息访问中。桌面和可以运行在使携式电脑或平板电脑上,用户可以在野外进行数据采集、分析和乃至制定决策。介绍是一组完备的并且打包的嵌入式组件库和工具斥,开发人员可用来创建新的或扩展已有的桌面应用程序。使用开发人员可以将功能嵌入刭已有的应用软件中,如自定义行业专用产品:或嵌入到业生产应用软件中,如和;还可以创建集中式自定义应用软件,并将其发送给机构内的多个用户由两个产品组成:构建软件所用的开发工具包以及使已完成的应用程序能够运行的可再发布的(运行时环境)。开发工具包是一个基于组件的软件开发产品,可用于构建自定义和制图应用软件。它并不是一个终端用户产品,而是软件开发人员的工具包,适于为或用户构建基础制图和综合动态应用软件是一个使终端用户软件能够运行的核心组件产品,并且将被安装在每一台运行应用程序的计算机上◆ Arcgis engine是基于COM技术的可嵌入的组件库和工具包, ArcGis engine可以帮助我们很轻松的构建自定义应用程序esrChinaBEIJING内部文档,请勿外传令使用 ArcGIS Engine,开发人员可以将(iS功能嵌入到已有的应用软件中,如自定义行业专用产品;或嵌入到业生产应用软仵中,如 Mirosoftf Word和 Excel;还可以创建集中式自定义应用软件,并将其发送给机构内的多个用户ArcGis Engine由两个产品组成:◇面向开发人员的软件开发包(ArcG| S Engine developer kit面向最终用户的运行时( ArcGIs Engine Runtime开发工具包是一个基于组件的软件开发产品,可用于构建自定义和制图应用软件。它并不是一个终端用户产品,而是软件开发人员的工具包,支持四种开发环境(十十,以及),适于为用户构建基础饲图和综合动态应用软件。是一个使终端用户软件能够运行的核心组件产品,并且将被安装在每一台运行应用程序的计算机上reGIS Engine的逻辑体系结构包含了 ArcGIS Engine中最核心的 ArcObjects组件,几乎所有的GS组件需要调用它们,如 Geometry| Extensions和 Display等DeveloperComponents包含了访问矢量或栅格数据的 GeoDatabase所有的接口和类组件。MapPresentationData包含了GiS应用程序用于数据显示、数据符号化、要素标注和专题图制作等需要的接凵和类组件AccessBaseServices包含了进行快速开发所需要的全部可视化控件,如和控件等,除了这些,该库还包括大量可以有调用的内置它们可以极大地简化二次开发工作。在图中我们可看出的开发体系是一条纵线,功能丰富,层次清晰。最上层的esrChinaBEIJING内部文档,请勿外传包含了许多高级开发功能,如、空间分析、维分析、网络分析、逻缉示意图以及数据与操作等。标准版并不包含这些许可,他们只能作为扩展存在,需要特定的才能运行。扩展模块3D三维分析Spatial空间分析Network网络分析Maplex智能标注Data Interoperability数据互操作Schematics逻辑示意图Tracking跟踪分析Geostatistical地理统计分析注意:运行时有多种版木级别,从标准版木一直到全业版木。标准的运行时提供所有应用程序的核心功能。这个级别的运行时可以操作几种不同的栅格和矢量格式、进行地图表达和创建以及通过执行各种空间或属性查询查找要素。这个级别的运行时还可以进行基本数据创建、编辑和简单的个人地理数据库(及分析但是如果遇到企业级数据库数据库的编辑以及复杂数捱模型的创建网络拓扑就需要运行时的标准许可相当于桌面级别的功能而许可相当于桌面级别的功能esrChinaBEIJING内部文档,请勿外传中的类库开发中,为了更好的管理这些对象,将这些对象放在不同的组件库中,而他们被物理的防盜目录下的中,而逻辑上被分散到不同的命名空间中下面我们详细对一些类库进行介绍库是新出来的一个类库,该类库包含了将独立应用程厅绑定到特定的系列产品的函数和方法该类库是在运行的应用程序的时侯库是架构中最底层的库。该库包含了暴露组成的其它库所使用的服务的组件。库中定义了许多接口,它们可以由开发者来实现。对象在中定义;所有开发者必须使用该对象在使用功能的应用程序中初始化和开发者不扩展该库,但可以通过实现其中的接口来扩展系统。库中包含了可在屮扩展的用户界面组件的接口定义,包括和接口。开发者使用这些接口来扩展组件。该库所包含的对象是对象,开发者可用于简化某些用户界面的开发。开发者不扩展该库,但可以通过实现其中的接口来扩展系统。库处理存储在特征类其它图形要素中的特征的或大多数用户交互的基本几何对象有。除了这些顶层的实体,还有作为和构建模块的几何体这些是组成几何体的基元它们是由形成一条的依次相连的组成包含两个不同的点,起点和终点,和一个定义从起点到终点的曲线的要素类型。这种有和所有的几何对象都可以有与它们顶点相关的、和esrChinaBEIJING内部文档,请勿外传基本的几何对象都支持几何操作,如和开发者不可以扩展几何基元。中的实体是指现实世界中的特征:这些现实世界中的特征的位置由具有空间参考的几何体來定义。投影和地理坐标系统的空间参考对象都包含在库中。开发者可以通过在空间参考间添加新的空间参考和投影来扩展空间参考系统库包含了用于数据显示的对象。除了负责实际图像输出的主要显示对象,该库屮还包含了表示颜色和符号的对象,这些颜色和符号用于控制显示上所绘制实体的属性。库中也包含了为用户在与显示交互时提供可视化反馈的对象。开发者大都通过类似于或对象提供的视图与显示交互。该库的所有部分都可以被扩展,常被扩展的有符号、颜色和显示反馈库被用于创建图形输出到设备,如打印杋、绘图仪和硬拷仄格式,如增强型图元文件和栅格影像格式、等。开发者使用该库和系统其它部分中的对象来创建图形输岀。通常这些是和厍中的对象。开发者可以扩展库用于定制的设备和输出格式。库提供了用于的编程是一个构建在标准工业关系和对象数据库技术基础上的地理数据储存库。库中的对象为攴持的所有数据源提供了统一的编稈模型。库定义了许多由架构中较高层次数据源提供者实现的接口。开发者可以扩展来支持特殊的数据对象等类型。此外,还可以使用对象添加自定义的矢量数据源。支持的数据类型不可以被扩展库包含用于基于文件数据源的的实现。这些基于文件的数据源包括N和开发者不能扩展库包含了用于数据库数据源的的实现。这些数据源包括软件支持的开发者不能扩展库
- 2021-05-06下载
- 积分：1
