计算机复杂性导引1-2.ppt

计算复杂性导引 第1章 程序设计语言和可计算函数 1.3 1.4 1.5 内 容 1.3 程序设计语言严格描述 1.4 可计算函数 1.5 宏指令 回忆：程序设计语言 符号： 输入变量 X1,X2,… （值可取任何数） 输出变量 Y （初值为0） 中间变量 Z1,Z2,… （初值为0） 标号 A1,A2,… 语句： 增量语句 V?V+1 减量语句 V?V-1 （若V=0，则V值不变） 条件转移语句 IF V?0 GOTO L 1.3 程序设计语言严格描述 变量，标号，语句 1．变量 输入变量 X1,X2,… 输出变量 Y 中间变量 Z1, Z2,… 2．标号 A1, A2,… 3．语句 增量语句 V?V+1 减量语句 V?V-1 空语句 V?V （用来改变程序长度而保持程序功能不变） 条件转移语句 IF V?0 GOTO L 指令，程序 4、指令 无标号指令：一条语句 带标号指令：标号[L]后面跟一个语句 5、程序 程序：一张指令表，即有穷的指令序列（程序的指令个数称为程序的长度） 空程序：长度为0的程序（不包含任何指令） 状态 6、状态 程序P的一个状态?：?是形如等式V=m的有穷集合，V是变量，m是数 （1）对于每个变量V，?中至多有一个等式V=m （2）若在程序P中出现变量V，则?中含有等式V=m 规定：若?中不含关于V的等式（V不在程序P中出现），则V的值自动取0 例如，{X=5,Y=3}， {X1=5,X2=4,Y=3}， {X=5, Z=6, Y=3} 都是程序 [A] X?X-1 Y?Y+1 IF X?0 GOTO A 的状态，{X=5,X=6,Y=3}不是任何程序的状态，{X=5}不是上述程序的状态 快相 7、快相（Instantaneous Description） 快相（瞬时描述）：一个有序对(i,?)，?是程序状态，即将执行第i条指令。1?i?q+1，q是程序长度，i=q+1表示计算结束 终点快相：(q+1,?)，q是程序长度 初始快相：(1,?)，?是初始状态（除初始变量外，所有变量的值为0的状态） 8、后继 程序P的非终点快相(i,?)的后继是(j,?)： 情况1：P的第i条指令是V?V+1（无论有无标号，下同），?包含等式V=m， 则j=i+1，把?中的V=m换成V=m+1就得到?。 情况2：P的第i条指令是V?V-1，?包含等式V=m， 则j=i+1，当m0时把?中的V=m换成V=m-1就得到?；当m=0时?=?。 情况3：P的第i条指令是V?V， 则j=i+1，?=? 情况4：P的第i条指令是IF V?0 GOTO L，?包含等式V=m，则?=?。 当m=0时j=i+1； 当m0时，若P中有带标号L的指令，则j是带标号L的指令的最小序号（允许有多条带标号L的指令，但只能跳转到第一条）；若P中无带标号L的指令，则j=q+1，q是程序长度。 后继解释语句的执行语义。 计算 9、计算 程序P的一个计算： 程序P的快相序列s1,s2,……，序列长度为k（对于无穷序列k=?）， （1）s1是初始快相 （2）对于每个i(1?ik)，si+1是si的后继 （3）当k?时，sk是终点快相 例1.5中程序的计算 1.4 可计算函数 程序P计算的n元部分函数 规定：初始状态?包含等式 X1=x1, X2=x2,…, Xn=xn, Y=0, 对于P中其他变量V均有V=0. 初始快相s1=(1,?)，有两种可能： (1) 若从s1开始的计算是有穷序列s1, s2,…, sk, 则 等于Y在终点快相sk中的值 (2) 若从s1开始的计算是无穷序列s1,s2,……，则 当nm（程序P中自变量个数）时，多出自变量xm+1,…,xn不起作用 当nm时，多余输入变量Xn+1,…,Xm的初始值为0 例如，设P有两个自变量，?(2)(x1,x2)= x1+x2 则?(1)(x)=x+0=x，?(3)(x1,x2,x3)=x1+x2 可计算函数 定义1.1 设f(x1,x2,…,xn)是一个部分函数，如果存在程序P计算f，即对任意x1,x2,…,xn，有