浙江大学计算理论复习总结
计算理论复习总结,但是考试快要结束了，估计大家也没有什么需要了。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
数据中心场地基础设施运维管理标准.pdf
随着大数据、云计算、智慧城市、移动互联网和物联网等应用的快速发展，各行各业对于数据中心场地基础设施的需求也越来越大。数据中心单体规模越大、系统越复杂，其脆弱性也越高，对于数据中心运行维护管理水平的要求也就越高。中国数据中心产业发展联盟为了提升整个数据中心行业在数据中心场地基础设施的运维管理水平，特发起了本标准的制定。本标准适用于：政府及企业信息化管理负责人、数据中心负责人、数据中心场地基础设施的运维管理人员。本标准可为以上人群进行数据中心场地基础设施的运维管理提供系统性的建议，也可作为用户评价数据中心场地基础设施运维服务水平的参考。本标准专注于数据中心场地基础设施层面。本标 现代数据中心网www.DCJChina.com.cn世纪互联数据中心有限公司曙光云计算技术有限公司招商银行股份有限公司中国电信股份有限公司云计算分公司中国移动通信集团公司政企客户分公司支持单位:北京企商在线数据通信科技有限公司蓝汛首鸣数据中心南京诚嬴软件科技有限公司润泽科技发展有限公司山东银澎百盛云计算技术有限公司上海迪佑拂科技咨询服务有限公司上海数讯信息技术有限公司苏州国科综合数据中心有限公司太极计算机股份有限公司万国数据服务有限公司中铁程科技有限责任公司广州宽带主干网络有限公司中金数据系统有限公司本标准将定期更新,以适应数据中心技术及管理最佳实践发展的新趋势。相关单位及个人对于本标准有仼何改进建议或意见,请发邮件至秘书处,联系邮箱:mishuchu@chinabda org现代数据中心网w.DCJChina.com.cn目录数据中心场地基础设施运维管理标准、规范性引用文件6二、术语和缩略语62.1术语62.2缩略语8、管理范畴3.1管理目标3.2参与数据中心建设过程93.3测试验证.103.4技术文档3.5管理边界四、安全管理和质量管理124.1人员安全124.2物理环境安全124.3质量管理13五、人员管理145.1组织及人员145.2培训及认证155.3运维外包服务商16六、设施管理176.1资产数据库176.2预防性维护176.3操作流程..186.4工具及备件管理196.5供应商管理19现代数据中心网w.DCJChina.com.cn6.6生命周期管理206.7运维管理系统.20七、运行管理217.1运行管理制度217.2设施监控、巡检、及交接班管理227.3机房清洁管理227.4标签标识管理227.5变更管理227.6事件管理27.7应急响应27.8容量管理247.9能效管理247.10预算管理25数据中心场地基础设施运维管理等级评估指南、运维管理等级的界定....271.1运维分级的目的1.2各等级典型的行为特征271.3设定运维管理等级目标27评估体系282.1评估框架2.2评估原则2.3评估细则28数据中心场地基础设施运维人员资格认证体系、认证体系概述及主要范围37二、认证内容382.1认证标准38现代数据中心网w.DCJChina.com.cn2.2基础知382.3技能要求.392.4认证矩阵图44现代数据中心网w.DCJChina.com.cn数据中心场地基础设施运维管理标准现代数据中心网www.DCJChina.com.cn、规范性引用文件下列文件对于本文件的应用是必不可少的。凡凡是注明日期的引用文件,仅注日期的版本适用于本文件。凡是不注明日期的引用文件,其最新版本(包括所有的修改单)适用于本文件。GB50174电子信息系统机房设计规范GB26860电力安全工作规程发电厂和变电站电气部分DL408电业安全工作规程、术语和缩略语2.1术语2.1.1数据中心( Data center)主要功能为容纳一个计算机房和该计算机房的各个支持区的一栋建筑或者一栋建筑的一部分。包括容纳信息技术系统的主机房、支持信息技术系统运行的辅助区和行政管理区。2.1.2场地基础设施( Site Infrastructure)数据中心内为信息技术系统提供运行保障和运行环境的场地设施。包括容纳系统的主机房,支持「系统运行的供电系统、制冷系统、消防系统、安防系统、监控系统及其路由等配套设施及维护杄系统的辅助设施2.1.3运维管理( Operation and Maintenance Management对数据中心场地基础设施进行日常运行和维护,确保各项基础设施系统安全稳定地运行。运维管理包括制定运维制度和计划、执行运维计划响应场地基础设施故障、突发事件等紧急情况。2.1.4生命周期( Life cycle)通常指数据中心从投产到经济寿命结束的全过程。但也有将投产前的规划期、设计期、建设期、测试验证期作为生命周期一部分(孕育期)的说法。2.1.5测试验证( Commissioning)验证并记录数据中心设施作为一个整体及其所有的设备、子系统满足用户的设计目标和运行要求2.1.6健康评估( Health assessment)全面系统性地对机房现有使用状态、设备运行情况、运维管理制度及流程等进行全方位的检查。现代数据中心网w.DCJChina.com.cn2.1.7预防性维护( Preventive Maintenance)为降低产品发生失效或功能退化的概率,按预定的时间间隔或按既定的准则实施的维护。2.1.8风险评估( Risk assessment)针对运行的设备所面临的威胁、存在的弱点、造成的影响,以及三者综合作用所带来风险的可能性的评估,同时确定风险是否可容许的全过程。2.1.9容量管理( Capacity Management)对于基础设施在空间、电力承载能力、制冷能力等方面的评估,以满足「T数据存储和处理的需要容量。为了实现其目标,容量管理需要与业务及杄战略流程保持密切的联系。2.1.10资产管理( Asset Management)对于数据中心基础设施中每个资产建立独有的标识,并详细进行资产描述、制造商、型号、安装日期、保修期等信息的记录管理2.1.11可用性( Availability)在所有要求的外部资源得到提供的情况下,数据中心在规定的时刻或规定的时间段内处于能执行要求的功能状态的能力。它是衡量数据中心等级、运维水平的重要指标。可用性的计算如下可用性平均无故障时间平均无故障时间 平均故障修复时间2.1.12绿色运行( Green Operation)指数据机房中的制冷、照明和电气等能取得最大化的能源效率和最小化的环境影响。2.1.13负载(Load)指连接在电路中的电源输出的设备。负载是把电能转换成其他形式的能的装置。2.1.14气流组织(Ar- Flow Organization)指在机房內对冷热气流的流向按一定要求进行疏导和组织。现代数据中心网www.DCJChina.com.cn2.2缩略语22.1PUE( Power∪ sage Effectiveness,电力使用效率)PUE是评价数据中心能源效率的指标,是数据中心消耗的所有能源与T负载使用的能源之比。PUE三数据中心总设备能耗川T设备能耗PUE是一个比值,越接近1表明能效水平越好2.2.2SLA( Service Level Agreement,服务等级协议)服务提供商和客户之间签署的、描述服务范围和约定服务级别的协议。2.2.3MOP( Method of Procedure,维护作业程序)M○尸是维护作业程序,用于规范和明确数据中心基础设施运维工作中各项设施的维护保养审批流程、操作步骤。2.2.4SOP( Standard Operating procedure,标准操作流程)S○P即标准操作流程,是将某一项工作的标准操作步骤和要求以统一的格式描述岀来,用来指导和规范日常的运维工作。2.2.5EOP( Emergency Operating procedure,应急操作流程)E○P是应急操作流程,用于规范应急操作过程中的流程及操作步骤。确保运维人员可以迅速启动,确保有序、有效地组织实施各项应对措施。2.2.6 CMMS( Computerized Maintenance Management System计算机化维护管理系统)用以系统性地设置并跟踪运维仼务的执行情况,存储操作流程及相应运维人员的操作权限等维护工作相关信息。
- 2020-06-08下载
- 积分：1
