计算机的过去、现在与未来.ppt

计算机过去现在未来,Lecture5-Turing机计算机程序算法及应用,AlanTuring的抽象计算机图灵机,1936年,阿兰图灵提出了一种抽象的计算模型图灵机(TuringMachine)，其基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：(a)在纸上写上或擦除某个符号；(b)从纸的一个位置移动到另一个位置；,图灵机-横向视图,图灵机,为模拟人的这种运算过程，图灵机器包括：一条(无限长)纸带(tape)。纸带被划分为一个接一个的小格子(cell)，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依此被编号为0,1,2,.，纸带的右端可以无限伸展。一个读写头(read-writeHead)。该读写头可在纸带上左右移动，它能读出当前格子上的符号(Characters)，并能改变当前格子上的符号。一个状态寄存器(Register)，用来保存图灵机当前所处状态。图灵机的所有可能状态的数目是有限的，且有1个特殊的状态，称为停机状态。(Halt),图灵机,一套控制规则。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态，纵向视图如下，,无限长的带子,读写头,状态寄存器,控制规则,图灵机-工作原理,首先，读写头在纸带上读出一个方格的信息，并且根据它当前的内部状态开始对程序进行查表，然后得出一个输出动作，也就是是否往纸带上写信息，还是移动读写头到下一个方格(cell)。程序同时告诉它下一时刻内部状态转移到哪一个。具体的程序就是一个列表，也叫做规则表(transi-tiontable)，形式如下：当前内部状态s输入数值i输出动作o下一时刻的内部状态sB1前移CA0往纸带上写1BC0后移A,图灵机,图灵机只要根据每一时刻读写头读到的信息(纸带格子里的符号)和当前的内部状态进行查表，就可以确定它下一时刻的内部状态和输出动作了。图灵机虽然简单，但只要变化它的程序（也就是上面的规则表），那么它就可能为你做任何计算机能够完成的工作。因此可以说，图灵机就是一个最简单的计算机模型！,如何理解图灵机-小虫模型？,小虫的比喻,考虑这样一个问题。假设一个小虫在地上爬，那么我们应该怎样从小虫信息处理的角度来建立它的模型？首先，我们需要对小虫所在的环境进行建模。我们不妨就假设小虫所处的世界是一个无限长的纸带，这个纸带上被分成了若干小的方格，而每个方格都仅仅只有黑和白两种颜色。,如何理解图灵机？,显然，这个小虫要有眼睛或者鼻子或者耳朵等等感觉器官来获得世界的信息。首先，为简化问题，假设它仅仅具有1个感觉器官：眼睛，且它的视力短得可怜，也就是说它仅仅能够感受到它所处的方格的颜色。因而这个方格所在的位置的黑或者白色的信息就是小虫的输入信息。另外，还需要为小虫建立输出装置，即让它能动起来。我们仍然考虑最简单的情况：小虫的输出动作就是往纸带上前爬一个方格或者后退一个方格。,小虫I代模型,仅仅有了输入装置以及输出装置，小虫还不能动起来，原因很简单，它并不知道该怎样在各种情况下选择它的输出动作。于是我们就需要给它指定行动的规则，这就是程序！假设我们记小虫的输入信息集合为：I=黑色，白色它的输出可能行动的集合就是：O=前移，后移那么程序就是要告诉它在给定了输入，比如“黑色”情况下，它应该选择什么输出。,程序1(小虫I代模型)：输入输出黑色前移白色后移,小虫I代模型,这个程序非常简单，它告诉小虫当读到一个黑色方格的时候就往前走一个方格，当读到一个白色方格的时候就后退一个格。我们不妨假设，小虫所处的世界的一个片断是：黑黑黑白白黑白，小虫从左端开始运动，,开始,小虫I代模型,小虫I代移动模型的改进I代小虫模型过于简单，为使它更贴近现实，现在假设：小虫除了可以机械地在世界上移动以外，还会对世界本身造成影响，因而改变这个世界。比如虫子会对纸带上格子里的颜色进行乱涂画等。,小虫II代模型,在新的小虫II代模型中，也就相当于必须假设小虫可以改写纸带上的信息。因而，小虫可能的输出动作集合就变成了：O=前移，后移，涂黑，涂白这个时候，可把程序1改写一下，比如：程序2：输入输出黑前移白涂黑(此处与程序1不同)纸带是黑黑白白黑，小虫会怎样行动呢？下面的图表示出了这个例子中每一步小虫的位置。,小虫II代模型,开始：小虫在最左边的方格，根据程序的第一行，读入黑色应该前移。,第二步：仍然读入黑，根据程序的第一行，前移。,第三步：这个时候读入的是白色，根据程序的第二行，应该把这个方格涂黑，而没有其他的动作。假设这张图上方格仍然没有涂黑，而在下一时刻才把它表示出来。,小虫II代模型,第四步：当前方格已经是黑色的，因此小虫读入黑色方格，前移。,第五步：读入白色，涂黑方格，原地不动。,第六步：当前的方格已经被涂黑，继续前移。,第七步：读入黑色，前移。,小虫II代模型,小虫的动作还会持续下去。我们看到，小虫将会不停的重复上面的动作不断往前走，并会把所有的纸带涂黑。显然，还可以设计出其他的程序来，然而无论你的程序怎么复杂，也无论纸带子的情况如何，小虫的行为都会要么停留在一个方格上，要么朝一个方向永远运动下去，或者就是在几个方格上来回打转。II代模型归纳：比起真实世界中的虫子来说，II代小虫模型仍然有一个致命的弱点：那就是如果你给它固定的输入信息，它都会给你固定的输出信息！因为程序是固死的，因此，每当黑色信息输入的时候，无论如何它都仅仅前移一个方格，而不会做出其他的反应。,小虫III代模型,如果进一步更改小虫模型，那么它就会有所改进，至少在给定相同输入的情况下，小虫会有不同的输出情况。这就是加入小虫的内部状态！可以作这样的一个比喻：假设黑色方格是食物，虫子可以吃掉它，而当吃到一个食物后，小虫子就会感觉到饱了。当读入的信息是白色方格的时候，虽然没有食物但它仍然吃饱了，只有当再次读入黑色时候它才会感觉到自己饥饿了。因而说小虫具有两个内部状态，并将状态集合记为：S=饥饿，吃饱这样小虫行动的时候就会不仅根据它的输入信息，而且也会根据它当前的内部状态来决定它的输出动作，并且还要更改它的内部状态。,小虫III代模型,小虫的行动仍然要用程序控制，跟上面的程序比起来，现在的程序就更复杂一些了，比如：程序3：输入当前内部状态输出下时刻的内部状态黑饥饿涂白吃饱黑吃饱后移饥饿白饥饿涂黑饥饿白吃饱前移吃饱这个程序代码有四行，原因是：现在不仅需要指定每一种输入情况下小虫应该采取的动作，而且还要指定在每种输入和内部状态的组合情况下小虫应该怎样行动。再看看这只虫子在读入黑白白黑白这样的纸带的时候，会怎样？仍然用下面的一系列图来表示，红色的小虫表示饥饿的小虫，绿色的小虫表示它吃饱了。,小虫III代模型,假定它仍然从左端开始，而且开始的时候小虫处于饥饿状态。这样读入黑色+当前饥饿状态，根据程序第一行，把方格涂白，并变成吃饱（这相当于把那个食物吃了，注意吃完后，小虫并没动）。,涂白方格，变成吃饱,第二步：当前的方格变成了白色，因而读入白色+而当前的吃饱状态，那么根据程序中的第四条前移，内部状态仍然是吃饱；,前移，仍然吃饱,小虫III代模型,第三步：读入白色+当前状态是吃饱，因而会重复第二步的动作。,继续前移，保持吃饱,第四步：仍然重复上次的动作。,继续前移，保持吃饱,第五步：读入黑色+当前状态是吃饱，这时候根据程序的第二行应该后移方格，并转入饥饿状态；,后移，变成饥饿,小虫III代模型,第六步：读入白色+当前饥饿状态，根据程序第三行应该涂黑，并保持饥饿状态；,涂黑，保持饥饿,第七步，读入黑色+当前饥饿，于是把方格涂白，并转入吃饱状态。,涂白，转入吃饱,第八步，读入白色+当前吃饱，于是前移，保持吃保状态。(循环到第5步状态！),前移，保持吃饱,图灵机-小虫模型扩展,以下是小虫模型的扩展：小虫可处于一个3维空间中,而不是简简单单的纸带;小虫的视力很好，它一下子能读到方圆500米的信息。当然,小虫也可以拥有其他的感觉器官，比如嗅觉、听觉等等，而这些改变都仅仅是扩大了输入集合的维数和范围，并没有其他更本质的改变;小虫可能的输出集合也是异常的丰富，它不仅仅能移动自己，还可以随意的涂色、跳跃、甚至搞破坏。进一步的，小虫的内部状态可能非常的多，比如吃饱、饥饿、兴奋、沮丧和愤怒等，而且控制它行为的程序可能异常复杂;,图灵机-本质性内容,考虑扩展上述的模型后，小虫会有什么本事？随着小虫内部的状态数的增加，以及它所处环境的复杂度的增加，模型设计者却正在逐渐失去对小虫行为的预测能力，因为模型的输出，即小虫的行为变得越来越复杂。但是所有这些改变仍然没有逃出图灵机的模型，即以下4元组：Quadruple=输入集合、输出集合、内部状态、固定的程序就是这4样东西抓住了小虫信息处理的根本，这就是Computing(计算)的本质,从程序到算法,算法研究的起因-Hilbert提出23个世纪难题(巴黎,1900),康托尔的连续统假设*XXXXXXXXXXXX*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX,XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX丢番图方程的整数可解性判定*,Hilbert第10问题-丢番图方程可解性的判定,丢番图(Diophantus)方程，算术J是一本写于公元250年的代数著作，作者Diophantus，书中主要考虑了有一个或几个变量的整系数方程，其求解主要限制在整数范围内进行，例如或者,Hilbert第10问题陈述：,仅有1个未知数的线性丢番图方程,ax=b方程有整数解的充要条件a整除b(a|b)。此方程解可以通过简单的计算机程序求出，即x=b/a。,有2个未知数的线性丢番图方程,ax+by=ca，b是非零整数，判断以上方程是否有解的方法：先计算a，b的最大公因数，比如是d=gcd(a,b)，如果d整除c，那么方程有整数解，否则方程就无整数解。E.g2.判别方程6x+15y=12的解情况？,Euclid算法求最大公约数gcd,ax+by=c求解以上方程的整数解，存在一种机械化的程序过程，其关键是求最大公约数的”Euclid算法”。E.g3.求172和20最大公约数gcd(172,20)？,Euclid算法求解整数解,ax+by=c如果d=gcd(a,b)，且d|c，那么方程有解，假设(x0，y0)为一组特解，那么任意解(x，y)都可以表示为，E.g4:解线性丢番图方程172x+20y=1000？,算法定义,算法（粗略定义）所谓算法(Algorithm)，就是逐步执行某类计算的一套指令方法，这些指令应该遵循应当是完全的(Completeness)，并且没有二义性(noambiguous)，不允许有随意选择的余地，同时应对所有初始数据（而不仅是某些特殊数值）有效。,练习-描述Euclid辗转求余算法并判断它是否遵循算法的3个条件？,Euclid辗转求余算法Inputa,b；Calculateamodb=r1;Calculatebmodr1=r2;Untilrmodrn=0;rn即为a,b的GCD（最大公约数）,计算机程序算法+数据结构NicolasWirth,1984年图灵奖获得者,ComputationalModeofThought计算机式思维能力算法，属于所谓的“过程性知识(Imperative)”，它主要描述“如何做，即How-todosomething”,算法运用经典的数值算法问题计算的数值？,算法运用并行计算机网络（VPN）信息发送算法：这是一种基于概率的随机算法，由图灵奖获得者Rabin（拉宾,1976）的同事Valiant根据其思想设计，这种算法并不将信息直接发往目的地，而是先发送到任一节点，再由该节点发送至目的地。Valiant从理论上证明：这种看似发疯的算法能有效地减少网络里的竞争，从而避免网络堵塞(Congestion)。,算法的恶用1988年11月，在Internet出现了第一个广泛传播的病毒（蠕虫病毒，Morris病毒），它是哈佛大学的一个叫RobertMorris设计出来并加以传播的，而Morris的病毒程序的算法刚好是从他的老师Rabin(拉宾)在哈佛执教时学来的！,算法运用最古老的算法问题数字排序？Excel数据列的降序、升序排列？,插入排序算法福布斯富豪的资产,排序算法的性能插入排序数据集规模的考验,算法应用事关企业/国家命运的秘密通讯,秘密通信的密码技术的历史极为悠久，在军事、外交、商业领域都有广泛的应用，由于关系到企业的兴衰、战争输赢甚至国家的生死存亡，所以密码技术历来受到高度重视。加密通讯的原理在讯息发送方(sender)，为了把明文(plaintext)变成密文(cipheredtext)，需要一个密钥(加密密钥)和一个加密算法；在接收方，要将密文恢复成原来的明文，需要一个密钥(解密密钥)和一个解密算法。,加密算法和解密算法的保密问题,为了达到秘密通信的目的，密钥和加密算法历来是需要严格保密的，但这通常很难做得到，现代战争史上有两个著名的通讯破解事例：太平洋海战期间，日军的通讯密码被美国人破译，导致其攻击中途岛(Midway)的计划遭到惨败德国海军的Enigma密码机被英国的以Turing为首的技术小组破译。,加密技术的进步公钥密码RSA算法,1977年，在美国MIT工作的Rivest、Shamir、Adleman联合提出了一种算法，该系统里，加密密钥和加密算法都不需要保密，惟一需要保密的是解密密钥(decipherkey)，这为密码学开辟了一个新的纪元。RSA算法主要基于数论里“大整数的素数因子分解的难解性。”,RSA算法描述,随机选取两个极大的、但不同的素数p和g，并算出积r=p*g.这里，数p和g需要保密，但r不必保密。然后，随机地选取一