1、计算理论计算理论第二章第二章 计算模型计算模型2.2 寄存器机寄存器机n 寄存器机寄存器机：n与图灵机等价。与图灵机等价。n介于图灵机与实际数字计算机之间的一种抽介于图灵机与实际数字计算机之间的一种抽象机。象机。n用于分析算法效率和与机器代码相关的研究。用于分析算法效率和与机器代码相关的研究。 2.2 寄存器机寄存器机n寄存器机的一般结构寄存器机的一般结构：n 寄存器寄存器n 指令集指令集n 控制器控制器n 输入输出带输入输出带n 指令标号指令标号2.2 寄存器机寄存器机n典型寄存器机典型寄存器机n计数器机计数器机n指针机指针机nRAM(Random Access Machine)nRASP(
2、Random Access Stored Program Machine)2.2.1 RAM机器机器n RAM（ Random Access Machine ）:n哈佛结构哈佛结构.n带有间接寻址和扩充的指令集带有间接寻址和扩充的指令集.2.2.1 RAM机器机器读写读写Ri读读头头X1X2XiXn只读输入带只读输入带位置计数器位置计数器程程 序序R0R1R2Ri累加器累加器寄寄存存器器Y1Y2YiYm只写输出带只写输出带写写头头控制器控制器n指令指令：n格式：指令格式：指令 操作数操作数n指令分类：指令分类：n寄存器取寄存器取 LOAD n寄存器存寄存器存 STOREn跳转跳转 JUMP J
3、GTZ JZERO n运算运算 ADD SUB MULT DIVn输入输入 输出输出 READ WRITEn结束结束 HALT2.2.1 RAM机器机器n直接寻址直接寻址n寄存器中存放的是操作数。寄存器中存放的是操作数。n间接寻址间接寻址n寄存器中存放的是操作数的地址。寄存器中存放的是操作数的地址。2.2.1 RAM机器机器n操作数：操作数：ni表示表示Ri寄存器的内容，记为寄存器的内容，记为C(i)；n*i表示间接寻址，操作数的地址是表示间接寻址，操作数的地址是Ri 内容，内容， j=C(i)，即其值是，即其值是C(C(i)，若，若j 0，则位置计数器，则位置计数器 lJZERO l: 若若
4、C(0) = 0，则位置计数器，则位置计数器 lHALT: 停机停机2.2.1 RAM机器机器2.2.1 RAM机器机器nRAM机的初始状态机的初始状态n C(i) = 0，对任意，对任意 i 0；n位置计数器指向程序位置计数器指向程序P的第一条指令；的第一条指令；n输入串放在输入带上，读头指向输入串的第输入串放在输入带上，读头指向输入串的第一个符号；一个符号； n输出带空白。输出带空白。2.2.1 RAM机器机器nRAM程序程序P：n指令或带标号的指令的有限序列，并且最后指令或带标号的指令的有限序列，并且最后一条指令为一条指令为HALT。n含义：输入到输出的函数含义：输入到输出的函数 f(x
5、1, , xn) = (y1, , ym)例例：输入：输入X1 X2XiXn0，其中，其中Xi为为1或或 2，判断，判断1和和2出现的个数是否相同？出现的个数是否相同？ 设计思路：读到设计思路：读到1则加一，读到则加一，读到2则减一，则减一，若结果为若结果为0则个数相等则个数相等。2.2.1 RAM机器机器nR0: 累加器累加器nR1:存放读入字符存放读入字符nR2:存放差值存放差值R0R1R22.2.1 RAM机器机器n 初始化初始化：n LOAD =0 （累加器清零）（累加器清零） n STORE 2 （差值寄存器（差值寄存器2清零）清零）n READ 1 （读入第一个数）（读入第一个数）
6、2.2.1 RAM机器机器n 读入字符读入字符1：n LOAD 2 (将差值寄存器的数读入将差值寄存器的数读入 累加器累加器)n ADD =1 (读入的数为读入的数为1，所以差值加，所以差值加1）n STORE 2(将结果传回差值寄存器将结果传回差值寄存器)2.2.1 RAM机器机器n读入字符读入字符2：nLOAD 2 （则将差值寄存器的数读入累加器）（则将差值寄存器的数读入累加器）nSUB =1 （因为是（因为是2，所以差值减，所以差值减1）nSTORE 2 （将结果传回差值寄存器）（将结果传回差值寄存器）2.2.1 RAM机器机器程序如下：程序如下： LOAD =0 （累加器清零）（累加器
7、清零） STORE 2 （差值寄存器（差值寄存器2清零）清零） READ 1 （读入第一个数）（读入第一个数）REPEAT: LOAD 1 （将寄存器（将寄存器1中的数读入累加器中）中的数读入累加器中） JZERO END （如果为零，说明结束）（如果为零，说明结束） SUB =1 (将读入的数减将读入的数减1，使得，使得1变为变为0，2变为变为1) JZERO ONE （如果是零（如果是零,则跳到则跳到ONE） SUB =1 JZERO TWO HALTONE: LOAD 2 ADD =1 STORE 2 JMP NEXT TWO LOAD 2 SUB =1 STORE 2 JMP NEXT
8、NEXT: READ 1 （读入输入带上的下一个数）（读入输入带上的下一个数） JMP REPEAT （跳回（跳回REPEAT进行检查）进行检查）END: LOAD 2 (结束，将差值寄存器的值读入累加器结束，将差值寄存器的值读入累加器) JZERO EQUAL（如果为零，说明（如果为零，说明1和和2的个数相等，的个数相等， 跳到跳到EQUAL） WRITE =0 （将不相等的结果（将不相等的结果0写到输出带中）写到输出带中） HALT （程序结束，系统停机）（程序结束，系统停机） EQUAL: WRITE =1 （相等，则输出（相等，则输出1到输出带中）到输出带中） HALT （程序结束，系
9、统停机）（程序结束，系统停机） 2.2.2 RASPn RASP机：随机存取存储程序机机：随机存取存储程序机n 冯诺伊曼结构冯诺伊曼结构n 程序存储在寄存器中，可以修改。程序存储在寄存器中，可以修改。n特点：特点：1. 不允许间接寻址，除此之外，指令集与不允许间接寻址，除此之外，指令集与RAM机机器相同。器相同。2. 每条指令占两个寄存器，第一个存放操作码，第每条指令占两个寄存器，第一个存放操作码，第二个存放操作地址，操作码在寄存器中表现为数二个存放操作地址，操作码在寄存器中表现为数值，不是符号。值，不是符号。2.2.2 RASP机器机器2.2.2 RASP机器机器 指令指令 编码编码nLOA
10、D i1nLOAD =i2nSTORE i3nADD i4nADD =i5nSUB i6nSUB =i7nMULT i8nMULT =i9 指令指令 编码编码nDIV i10nDIV =i11nREAD i12nWRITE i13nWRITE =i 14nJUMP i15nJGTZ i16nJZERO i17nHALT182.2.2 RASP机器机器n 定理：定理： 对于任意一个对于任意一个RASP程序程序PS，存在一个，存在一个等价的等价的RAM程序程序P。2.2.2 RASP机器机器 证明：如右图所示，证明：如右图所示， R1:存放间接寻址的信息存放间接寻址的信息 R2:存放存放RASP中
11、的位置计数器。中的位置计数器。 R3:存放存放RASP中的累加器的内容。中的累加器的内容。 R0R1R2R3R4程序程序PSRAM程序程序P2.2.2 RASP机器机器n程序程序PS从从R4开始存放，开始存放，R2 初始时值为初始时值为4。nRAM程序程序P由一个循环组成，循环开始处的标号由一个循环组成，循环开始处的标号为为A，每次循环读取一条，每次循环读取一条PS指令，指令， 即即 LOAD *2。n根据根据C(C(2)的值，解码形成的值，解码形成18个分支。例如：个分支。例如： 设设C(C(2)=6，则程序，则程序PS的当前指令为的当前指令为SUB i，此，此时，寄存器时，寄存器C(2)1
12、即为所要的操作数地址。即为所要的操作数地址。2.2.2 RASP机器机器n翻译过程：翻译过程：将位置计数器加一，使其指向当前指令的下一个将位置计数器加一，使其指向当前指令的下一个寄存器，取到操作数寄存器，取到操作数iLOAD 2；ADD =1；STORE 2； /*此时，此时，R2中即为中即为SUB操作的目标数所在的寄存操作的目标数所在的寄存器编号，即器编号，即SUB指令的下一个寄存器。指令的下一个寄存器。2.2.2 RASP机器机器将寄存器将寄存器Ri映射到映射到Ri+3（因为（因为R1、R2和和R3均已被均已被使用，程序将向后移使用，程序将向后移3格）。格）。LOAD *2； /*取出取出
13、R2指向的值，就是所要操作指向的值，就是所要操作 的数所在的逻辑寄存器号的数所在的逻辑寄存器号ADD =3； /*加上加上3，使其指向正确的实际寄存，使其指向正确的实际寄存 器号器号STORE 1； /* R1用于间接寻址，此时用于间接寻址，此时R1的值即的值即 为目标数在为目标数在RASP机器中物理寄存器号机器中物理寄存器号2.2.2 RASP机器机器执行减法执行减法 LOAD 3；/* R3中存放的是上一次的累加器的中存放的是上一次的累加器的 内容，现在恢复到累加器中内容，现在恢复到累加器中 SUB *1； /* R1中存放的是目标数的寄存器号，中存放的是目标数的寄存器号， 用间接寻址求得
14、实际数用间接寻址求得实际数 STORE 3；/*返回结果，并保存在返回结果，并保存在R3中，下一中，下一 次需要时可恢复使用次需要时可恢复使用2.2.2 RASP机器机器位置计数器加位置计数器加1，返回循环入口，返回循环入口LOAD 2；ADD =1；STORE 2；/*加一，使其指向下一条指令加一，使其指向下一条指令JUMP A2.2.2 RASP机器机器2.3 复杂度复杂度n 数量级数量级n设设n为自然数，为自然数，f(n)是是n的一个函数。的一个函数。O 表示表示量级，令量级，令O(f(n)表示不超过表示不超过f(n)数量级的量数量级的量.n例如：例如：O(n) = 常数，常数，3n，1
15、08n ， O(n2) = O(n), , a n2+bn+c, . 2.3 复杂度复杂度n 多项式数量级多项式数量级n 设：设：f(n) = aKnK + aK-1nK-1 + + a1n + a0 为为n的的K阶任意多项式，系数相对阶任意多项式，系数相对n来说是个常来说是个常数。则：数。则：O(f(n) = O(nK)，称，称O(nK)为多项式为多项式数量级数量级。2.3 复杂度复杂度n量级演算性质：量级演算性质： 若若A、B为量级，且为量级，且AB，则，则nABBn有限个有限个B相加，相加，BBBBn任意常数与任意常数与B相乘，相乘，kBBn 时间复杂度时间复杂度 ，空间复杂度，空间复杂
16、度n 算法的输入为算法的输入为n，算法对时间的需求，算法对时间的需求T(n)，对空间的需求对空间的需求S(n) 。 n 最坏情况时间（空间）复杂性：最坏情况时间（空间）复杂性： 设设X是输入，是输入，|X| = n（指输入（指输入X的规模，的规模，n个基个基本符号），本符号），L(X)表示算法接受输入表示算法接受输入X，执行计，执行计算所需要的时间算所需要的时间：( )()maxnXT nT Xn平均情况时间平均情况时间（空间）（空间）复杂性复杂性 ()( )1nXnXT XT nn问题复杂性问题复杂性n求解一个问题的任意一个算法至少花费的时求解一个问题的任意一个算法至少花费的时间间。即问题的
17、固有复杂性即问题的固有复杂性。n问题的所有的算法问题的所有的算法的的复杂性将不小于此问题复杂性将不小于此问题的复杂性的复杂性。2.3 复杂度复杂度n一致性标准：一致性标准： n 为简化问题求解，定义时间、空间单位为简化问题求解，定义时间、空间单位: : 每条指令执行需要一个时间单位，即需要每条指令执行需要一个时间单位，即需要 时间为时间为1 1；每个寄存器占用一个空间单位。；每个寄存器占用一个空间单位。n用于用于数据科学计算，如解方程，矩阵等，因数据科学计算，如解方程，矩阵等，因其数据一般采用科学法表示，其数据一般采用科学法表示，数据长度固定数据长度固定。2.3 复杂度复杂度n对数标准：对数标
18、准：n每条指令需要执行的时间和空间与操作数的长每条指令需要执行的时间和空间与操作数的长度成正比。度成正比。 操作数的长度：操作数的长度： 当当k k0 0，l(k)=1l(k)=1 当当k k0 0，l(k)=lint(log(k) + 1 l(k)=lint(log(k) + 1 其中，其中，lint()lint()表示向表示向下取整。下取整。n用于用于一般的非数值计算一般的非数值计算。如处理字符串处理，如处理字符串处理，其数据长度变化剧烈其数据长度变化剧烈。n 如上例中，按照如上例中，按照一致性标准程序空间复杂度为一致性标准程序空间复杂度为O(1)，时间复杂度为，时间复杂度为O(n)。n按
19、照按照对数标准对数标准，上例，上例空间复杂度为空间复杂度为O(logn)，时时间复杂度为间复杂度为O(nlogn)。n线性算法：对于线性算法：对于O(n)这样复杂度的算法，这样复杂度的算法，称为线性复杂度算法。称为线性复杂度算法。 n拟线性算法：对于拟线性算法：对于O(nlogn)这样复杂度的这样复杂度的算法，称为拟线性复杂度算法。算法，称为拟线性复杂度算法。n定理：定理： 在一致性或对数标准下，对任意一个时在一致性或对数标准下，对任意一个时间复杂性为间复杂性为T1(n)的的RAM程序程序P，都存在，都存在一个等价的一个等价的RASP程序程序PS和一个常数和一个常数k，使得使得PS的时间复杂性
20、的时间复杂性T2(n)k*T1(n)。n a a表示表示RAMRAM程序程序P P中直接寻址的指令数中直接寻址的指令数n 2a2a为一个指令从为一个指令从RAMRAM到到RASPRASP转换中，每条转换中，每条指令占用两个寄存器指令占用两个寄存器。n b b表示表示RAMRAM程序程序P P中间接寻址的指令数中间接寻址的指令数n 2 2* *6b6b表示一条表示一条RAMRAM间接寻址指令均可以用间接寻址指令均可以用6 6条条RASPRASP指令来完成，每条指令占用两个寄指令来完成，每条指令占用两个寄存器存器n预留预留R R1 1存放存放RASPRASP机器的累加器机器的累加器 R0R1RiR
21、0R12(a+6b)R1+tRi+t累加器累加器t=2(a+6b)+1RASP机器机器RAM机器机器n例：例：SUB *i指令转换成指令转换成RASP机器的指令机器的指令n将将RASP累加器暂存累加器暂存R1n将将RASP中的中的Ri+t内容存到累加器中内容存到累加器中n将将RAM地址加地址加tn将将RAM地址加地址加t后的值放入后的值放入SUB指令的地址寄存器指令的地址寄存器n恢复恢复RASP累加器的内容累加器的内容n执行减法执行减法STORE 1LOAD i+tADD =tSTORE j+11LOAD 1SUB -该值在运该值在运行中填入行中填入j+0j+1j+2j+3j+4j+5j+6j
22、+7j+8j+9j+10j+11311i+t5t3j+11116-l(j) + l(1) + l(C(0)l(j+2) + l(i+t) + l(C(i)l(j+4) + l(C(i) + l(t)l(j+6) + l(j+11) + l(C(i)+t)l(j+8) + l(1) + l(C(0)l(j+10)+l(C(i)+t)+l(C(0)+l(C(C(i)n l(j) + l(1) + l(C(0)n l(j+2) + l(i+t) + l(C(i)n l(j+4) + l(C(i) + l(t)n l(j+6) + l(j+11) + l(C(i)+t)n l(j+8) + l(1)
23、+ l(C(0)n l(j+10) + l(C(i)+t) + l(C(0) + l(C(C(i)n 对数标准分析时间复杂性对数标准分析时间复杂性n在在RAM机器中，机器中，SUB *i的执行时间复杂性的执行时间复杂性为为M= l(C(0) + l(i) + l(C(i) + l(C(C(i) n在在RASP机器中，机器中，6条指令共需执行时间：条指令共需执行时间： (6 + 11l(t)*M 其中其中(6 + 11l(t)为一常数。为一常数。n 图灵机的复杂性：图灵机的复杂性：n时间时间单位单位：一个格局转换：一个格局转换为为一个时间单位一个时间单位。n空间单位：空间单位：线性带上一格占用一
24、个空间单位线性带上一格占用一个空间单位。2.3 复杂度复杂度n 一个以一个以为输入的计算，为输入的计算，n=|：n时间复杂性为时间复杂性为C(n)：从初始格局到终止格从初始格局到终止格局的转换次数。局的转换次数。n空间复杂性为空间复杂性为S(n)：格局转换过程中占用：格局转换过程中占用的最多格数。的最多格数。 2.3 复杂度复杂度n定理定理： 给定一台给定一台Turing机机M，则存在一个，则存在一个RAM程序程序P（或（或RASP程序程序PS），使得），使得P（PS）与与M等价，反之亦然。等价，反之亦然。2.3 复杂度复杂度n多项式相关多项式相关： 若程序若程序P1和和P2的复杂性分别为的复
25、杂性分别为T1(n)、T2(n) ，存在多项式，存在多项式p(n)，使得，使得： T2(n)=p(n)*T1(n) 则称则称P1和和P2是多项式相关。是多项式相关。2.3 复杂度复杂度n定理定理： 给定一台给定一台Turing机机M，则存在一个，则存在一个RAM程序程序P（或（或RASP程序程序PS），使得），使得P（PS）与与M计算能力计算能力等价，等价，计算时间计算时间多项式多项式相关。相关。2.3 复杂度复杂度2.3 复杂度复杂度nP问题：问题：n可以由一个确定型图灵机在多项式时间内解可以由一个确定型图灵机在多项式时间内解决的问题。决的问题。nNP问题：问题：n可以在非确定图灵机上在多项式时间内解决可以在非确定图灵机上在多项式时间内解决的问题。的问题。2.3 复杂度复杂度
