《大学计算机基础》课件+第1章――自学完整版(2014_10_9)【OK】

大学计算机基础第1章自学版,北京航空航天大学计算机学院,2,课程目录,求解显示，交互（2学时）,问题的抽象与建模（4学时）,3,第1章计算机与计算思维,1.3为什么计算机能够计算,1.6计算机模型与计算思维（自学）,1.2理论思维，实验思维和计算思维,1.1从图灵测试看思维,1.4计算机的理论模型与物理实现,1.5计算思维主要思维方法的案例,4,本课件说明,说明：本课件为大学计算机基础第1章中关于计算机基础知识的详细课件供同学们自学和参考,5,1.6计算机模型与计算思维,1.6.1图灵机模型1.6.2现代计算机模型1.6.3计算机之逻辑基础1.6.4信息在计算机中的表示1.6.5现代计算机系统,6,1.6.1图灵机模型,计算机之所以能够计算，或者具备智能，其思维类比于人脑：语言单元神经元单元数字及其编码语言的关系神经元的链接数据结构、数据关系思维神经元网络的自动链接数据的模型和算法感知和动作肢体和器官计算机的输入和输出,我们如果能有一台机器，可以存储，可以运算，可以输入输出，那么，就可以具备计算的能力,我们来看看这个抽象的过程-图灵机模型,7,图灵其人,图灵其人阿兰麦席森图灵（AlanMathisonTuring,19121954)，出生于英国伦敦，19岁入剑桥皇家学院，22岁当选为皇家学会会员英国数学家、逻辑学家、密码学家，计算机逻辑的奠基者，提出了“图灵机（TuringMachine）”和“图灵测试”等重要概念1937年，提出了图灵机模型，这是图灵对人类的最大贡献1950年，发表了划时代的文章“机器能思考吗?”,成为了人工智能的开山之作被誉为“计算机科学之父”和“人工智能之父”计算机界于1966年设立了最高荣誉奖：ACM图灵奖,8,图灵机缘起,什么是计算？一个问题：1900年，德国数学家希尔伯特提出“23个数学难题”中，逻辑的完备性问题，即是否所有数学问题原则上都可解一篇文章：1937年，图灵发表“论可计算数及其在判定问题中的应用”(OnComputableNumbersWithanApplicationtotheEntscheidungsProblem)图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”的设想可解的问题是能够用图灵机的自动机理论模型表达的问题一个大神：图灵，1912-1954一个模型：可计算模型,9,图灵机模型,图灵的基本思想是用机器来模拟人们用纸笔进行数学计算的过程（）根据计算需求在纸上写下相应的公式或符号；（2）根据眼睛看到的符号，在脑中思考相应的计算方法；（3）在纸上写上或擦除某个符号；（4）把视线从纸的一个位置移动到另一个位置；（5）转到第（2）步，重复以上步骤，直到认为计算停止为止在每个阶段，人要决定下一步的动作，依赖于（a）人当前所关注的纸上某个位置的符号（b）人当前思维的状态为了模拟人的这种数学计算过程，图灵构造出一台假想的机器图灵机,10,图灵机模型的组成,图灵机模型由3个部件组成无穷纸带（符号集合）两端可无限延长，纸带被分为一系列均匀的方格，每个方格中可填写一个来自有限字母表的符号读写头（读、改写、左移、右移）有穷控制器（有限状态机）拥有预定的有限个互不相同的状态，并能根据输入改变自身的状态；可控制读写头工作,11,图灵机模型是如何抽象的？,图灵机模型是如何抽象的？将所有具体的输入、输出、转换细节抛弃，定义一个五元组图灵机是一个五元组（K，s，H），其中：K是有穷（有限）个状态的集合；是字母表，即符号的集合；sK，是初始状态；HK，是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；是转移函数，即控制器的规则集合。,12,图灵机的工作原理：计算“x+1”的图灵机,图灵机的工作原理图灵机的计算：由控制器控制执行的一系列动作图灵机从纸带上的某个起始点出发，动作完全由初始状态和指令组决定其计算结果是从图灵机停止时纸带上的信息得到的,【例1】计算“x+1”的图灵机目标：利用二进制设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头回归原位x由0、1串组成，“*”为x的分隔符、界定符（当纸带上有多个数时，用*将它们隔开）,13,计算“x+1”的图灵机首先进行抽象,确定图灵机五元组的内容状态集合K：start，add，carry，noncarry，overflow，return，halt字母表：0，1，*初始状态s：start停机状态集合H：halt规则集合规则：如果A那么B，形式化表示为：AB,图灵机控制器的规则：（控制器当前状态，读写头当前位置的符号）(读写头写入新符号，读写头移动动作指示，控制器新状态),14,规则集合,1,2,3,4,5,6、7,8,9,步骤,15,“51”的计算过程（1）,初始状态,第1步完成后状态,第1步：,16,“51”的计算过程（2）,第3步完成后状态,第2步：,加1，新符号变成0,第2步完成后状态,加上进位，新符号变成1,第3步：,17,“51”的计算过程（3）,第5步完成后状态,第4步完成后状态,第4步：,第5步：,18,“51”的计算过程（4）,第9步：停机（停止计算）,运算结果,第8步完成后状态,停机状态,19,课后练习,给出计算“7+1”的图灵机运算过程，列出每一步的指令和指令完成后的状态,20,通用图灵机,图灵机本质是进行字符串的处理图灵机输入是一个字符串图灵机输出也是一个字符串如果将图灵机的有限个内部状态与读写头的有限个动作用字符串表示那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，新符号，动作，新状态）图灵机可以由一个较长字符串完全表示通用图灵机,满足这样一个有穷规则有限状态的可以对字符串处理的机器，就是计算机；而可描述成这样的科学问题，就是可以计算的；而其具体实现，则是冯诺伊曼机。,21,通用图灵机实现“5+1”计算（1）,【例2】通用图灵机实现“5+1”计算,编码方案,22,通用图灵机实现“5+1”计算（2）,3带通用图灵机M,图灵机输入字符串：00100001000000010010（对应*101*）,图灵机的所有规则，每个规则20位字符（当前状态，当前符号，新符号，动作，新状态）,当前状态：0101对应start状态,利用编码描述的规则：,01010010001000110110,23,通用图灵机实现计算的过程,发现了什么？,计算过程与具体的编码方案和规则都不相关！,意味着什么？,程序可以重复执行,24,图灵机的思想,图灵机的思想图灵机不是具体的机器，而是一种思想模型，可制造一种十分简单但运算能力极强的计算装置，用来计算所有能想象得到的可计算函数。基本思想是用机器来模拟人们用纸笔进行数学运算的过程,10001110110,0110101,10001,0110101,由“程序”控制输入“转换”为输出,输入,输出,程序,通用机器,所谓计算就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程,图灵机的计算：由控制器控制执行的一系列动作,25,图灵机的思想（Cont.）,图灵机的思想是数据、指令、程序及程序/指令自动执行的基本思想,输入被制成一串0和1的纸带，送入机器中-数据。如00010000100011机器可对输入纸带执行的基本动作包括：“翻转0为1”，或“翻转1为0”,“左移一位”,“右移一位”，“停止”对基本动作的控制-指令，机器是按照指令的控制选择执行哪一个动作，指令也可以用0和1来表示：01表示“翻转0为1”(当输入为1时不变)，10表示“翻转1为0”(当输入0时不变),11表示“前移一位”,00表示“停止”输入如何变为输出的控制可以用指令编写一个程序来完成,如：011110110111011100机器能够读取程序，按程序中的指令顺序读取指令，读一条指令执行一条指令。由此实现自动计算,26,图灵机引出的计算理论问题,图灵机引出的计算理论问题计算理论是研究使用计算机解决计算问题的数学理论有三个核心领域：自动机理论、可计算性理论和计算的复杂性理论自动机是将离散数学系统的构造、作用和关系作为研究对象的数学理论（描述通用计算机计算能力的图灵机模型）可计算性理论的中心问题是建立计算的数学模型，进而研究哪些是可计算的，哪些是不可计算的计算的复杂性理论研究算法的时间复杂性和空间复杂性,27,图灵机引出的计算方法论问题,图灵机引出的计算方法论问题计算机学科的方法论有三个过程：抽象、理论和自动化设计及实现最根本的问题在于：问题如何进行描述？哪些部分能够被自动化？如何进行自动化描述？建立物理符号系统并对其实施等价变换是计算机学科进行问题描述和求解的重要手段“可行性”所要求的“形式化”及其“离散特征”使得数学成为重要的工具而计算模型无论从方法还是工具等方面，都表现出它在计算机上科学中的重要作用,28,图灵机蕴含的计算思想,图灵机蕴含的计算思想（1）程序也是数据“x+1”图灵机功能是固定的，相当于一个程序通用图灵机的功能根据编码方案（主要是规则集合）的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上（2）通用图灵机的所有规则构成指令集指令指示了操作的对象（当前符号）指令指示了待实施的操作（改写符号，移动读写头）,29,图灵机蕴含的计算思想（Cont.）,（3）通用图灵机模型是计算机的计算能力的极限因为，根据丘奇-图灵论题（Church-Turingthesis）：不能用图灵机完成的计算任务是不可计算的邱奇-图灵论题认为，如果某种方法（算法）可进行运算，那么该运算也可被图灵机执行（也可被递归定义的函数或函数执行）（4）计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等,30,冯诺依曼机对图灵机的实现,1944年，冯诺依曼参与ENIAC研究小组1945年，在ENIAC基础上，冯诺依曼等人提出了EDVAC设计方案,计算机的组成包括：运算器、控制器、存储器、输入和输出设备,31,1.6.2现代计算机模型,1.6.2.1冯诺伊曼计算机的基本思想1.6.2.2冯诺伊曼计算机的组成及其特点1.6.2.3冯诺伊曼计算机的局限性1.6.2.4冯诺伊曼计算机的改进-探索新的计算模型,自学,重点,32,需要思考的若干问题,请带着以下问题学习本节内容（1）冯诺依曼机的基本思想是什么？冯诺依曼机有哪些特点？（2）冯诺依曼机包括哪五大部件？其作用分别是什么？为什么计算机能够像人一样进行加减乘除各种算术运算，甚至能够进行各种逻辑运算？为什么计算机能够自动工作？（3）以存储器为中心的结构与以运算器为中心的结构有何不同？（4）冯诺伊曼计算机的局限性表现在哪几个方面？这几十年以来，人们是如何努力改进冯诺伊曼计算机，探索新的计算模型的？,33,1.6.2.1冯诺伊曼计算机的基本思想,冯诺伊曼其人约翰冯诺依曼（JohnVonNeuman，19031957）美藉匈牙利人，20世纪最重要的数学家之一，在现代计算机、博弈论和核武器等诸多领域内有杰出建树的最伟大的科学全才之一“电子计算机之父”，“博弈论之父”布达佩斯数学博士。先后执教于柏林大学和汉堡大学。历任普林斯顿大学、普林斯顿高级研究所教授，美国数学会主席，美国原子能委员会会员。美国全国科学院院士,34,冯诺伊曼思想的提出,关于ENIAC1946年2月14日，世界第二台电子计算机ENIAC（ElectronicNumericalIntegratorAndCalculator，电子数字积分计算机）（音译埃尼阿克）在美国宾夕法尼亚大学诞生研制小组：埃克特、约翰莫克利、赫尔曼戈尔斯坦、亚瑟博克斯17468只电子管，每秒5000次加法运算或400次乘法运算，运算速度是继电器计算机的1000倍并具有按事先编好的程序自动执行算术运算、逻辑运算和存储数据的功能体重30吨，占地170M2，耗电150kW,35,ENIAC的缺陷,ENIAC机存在两大缺陷采用十进制进行运算逻辑元件多，结构复杂，可靠性低没有存储器，操纵运算的指令分散存储在许多电路部件内计算题目前必须预先编写指令，再按指令手工连接好控制线路，然后启动它才能自动运行每次计算一个题目都必须重新连线，繁琐耗时，在很大程度上抵消了ENIAC的计算速度,1944年夏，戈尔斯坦介绍冯诺依曼加入ENIAC研制小组，担任技术顾问,36,第一台现代意义的通用电子计算机EDVAC,1945年6月底，ENIAC研制小组发表“存储程序通用电子计算机方案”EDVAC（ElectronicDiscreteVariableAutomaticCompUter，离散变量自动电子计算机）冯诺伊曼起草了“关于EDVAC的报告草案”，长达101页EDVAC1949年交付，1951年开始运行使用二进制而不是十进制；一条加法指令约864微秒，乘法指令2900微秒6000个电子管，12000个二极管，重7850kg，占地面积45.5平方米，功率56kW，使用时需要30个技术人员同时操作,37,冯诺依曼思想,冯诺依曼思想二进制：在电子计算机中采用二进制，将极大简化机器的逻辑线路存储程序（StoredProgram）：运算程序和数据均存储在机器的存储器中，程序设计员只需在存储器中寻找运算指令，机器就会自行计算。使计算机的结构大大简化，实现运算控制自动化和提高运算速度,为什么计算机能够像人一样进行加减乘除各种算术运算，甚至能够进行各种逻辑运算呢？计算机为什么能够自动工作呢？,38,1.6.2.2冯诺伊曼计算机的组成及其特点,以运算器为中心,五大部件构成：运算器、控制器、存储器、输入设备和输出设备,运算器（ALU）：执行算术运算和逻辑运算控制器：读取指令、分析指令并执行指令存储器：存储数据和指令输入设备：将程序和指令输入计算机中输出设备：将计算机处理结果显示或打印,重点,39,冯诺依曼计算机的特点,（1）二进制：指令和数据都用二进制代码表示；（2）存储程序方式：指令和数据不加区别以同等地位事先混合存于存储器中，可按地址寻访，连续自动执行；（3）存储器的地址和位数：存储器是按地址访问的线性编址的一维结构，每个存储单元的位数是固定的；（4）指令的形式：指令由操作码和地址码组成，操作码指明指令所要完成操作的性质和功能，地址码指明操作数及其在存储器中的位置；（5）五大部件构成：运算器、控制器、存储器、输入设备和输出设备；（6）指令的执行：指令按照执行的顺序存放在存储器中，由指令计数器指明要执行的指令所在存储单元的地址；（7）以运算器为中心：输入设备、输出设备与存储器之间的数据传送都要经过运算器，控制器负责解释指令，运算器负责执行指令。,40,现代计算机的演化,冯诺依曼计算机早期的结构是以运算器为中心输入、输出数据或程序都要经过运算器，运算也要通过运算器来进行两种操作都要争夺运算器资源，二者不能同时进行势必影响计算机的工作效率,现代计算机一般采用以存储器为中心的体系结构输入的数据或程序直接存储在存储器中，不经过运算器；运算器只负责运算；运算结果直接从存储器中取出，送给输出设备，也不经过运算器存储器可支持运算器与输入设备或输出设备的并行工作,41,以存储器为中心的现代计算机构成图,优点存储器的一部分在进行输入、输出时，另一部分可为运算器提供存取服务有效提高了计算机的工作效率,42,计算x*a的工作过程,42,运算器,存储器,控制台,控制器,(1)启动控制器工作,(2)发送第1条指令地址,(3)取出指令并分析指令,(4)执行指令：发送操作数x所在地址,(5)执行指令：取出操作数x,(10)执行指令：通知运算器计算a乘x,(11)继续后续指令的取指、执行,(6)发送下一条指令地址,(7)取出指令并分析指令,(8)执行指令：发送操作数a所在地址,(9)执行指令：取出操作数a,43,1.6.2.3冯诺伊曼计算机的局限性,现代计算机大多遵循冯诺依曼机结构冯诺依曼机的基本结构特征是“程序存储，共享数据，顺序执行”计算机最初是为解决复杂的数值计算而研制现在，除科学计算外，计算机还应用于数据处理、过程控制、计算机辅助（CAD、CAM、CAI）、网络通信、人工智能、多媒体应用、嵌入式系统等各个领域非数值计算冯诺伊曼计算机结构上的局限性成为影响计算机发展和应用的瓶颈，主要原因在于：（1）在存储器和CPU之间，是通过一条公共的数据总线来传送指令和数据CPU与共享存储器间的信息通路成为影响系统性能的“瓶颈”“冯诺伊曼瓶颈”,44,冯诺伊曼计算机的信息通路,指令和数据要从同一个存储空间存取，经由同一数据总线传输，因而取指和存取数据冲突CPU在数据输入或输出内存时造成闲置，使CPU的高速处理速度得不到充分的发挥,45,冯诺伊曼计算机的局限性（Cont.）,（2）冯诺依曼计算机本质上是串行顺序处理的工作机制，即指令是串行顺序执行的指令是按执行顺序依次存放在存储器中的，所以必须按顺序串行执行各条指令即使某条指令的数据已经准备好了，也必须先执行完它前面的指令才能执行该条指令，而不能与其他指令并行执行这在很大程度上限制了计算机的整体工作速度,46,1.6.2.4冯诺伊曼计算机的改进,针对冯.诺依曼体系结构的局限性，探索新的计算模型努力突破传统计算机体系结构的框架非冯诺依曼计算机并行计算机数据流计算机光计算机生物计算机量子计算机从运算速度、存储容量、能耗等各方面取得了新的突破，显著提高了计算机的性能,本节自学,47,1、哈佛结构的计算机,解决冯.诺依曼机性能瓶颈的关键在于改变体系结构，使其能够进行并行处理哈佛结构是一种将程序指令存储和数据存储分开的存储器结构将程序和数据分别存储在两个独立的存储器中，每个存储器独立编址、独立访问两个存储器有各自的数据总线和地址总线,哈佛结构的计算机由CPU、程序存储器和数据存储器组成优势1：不存在“冯诺伊曼瓶颈”，克服了取指和取数冲突。分离的程序总线和数据总线允许在一个机器周期内同时获得指令字和操作数提高了执行速度和数据的吞吐率,48,哈佛结构的计算机（Cont.）,优势2：取指和执行指令可以完全重叠。当处理多条指令时，取指令和存取数据分别经由不同的存储空间和不同的总线，执行某条指令时可以预先读取下一条指令，使得各条指令可以重叠执行克服了冯诺伊曼计算机其指令执行的串行性，提高了运算速度,49,2、光计算机,光计算机的定义光计算机（OpticalComputer），又称光子计算机（PhotonComputer），是一种用光信号进行数字运算、逻辑操作、信息存储和处理的新型计算机它由激光器、光学反射镜、透镜、滤波器等光学元件和设备构成，靠激光束进入反射镜和透镜组成的阵列进行信息处理，以光子代替电子，光互连代替导线互连，光硬件代替电子计算机中的电子硬件，光运算代替电运算。基础部件是空间光调制器，采用光内连技术，在运算部分与存储部分之间进行光连接，运算部分可直接对存储部分进行并行存取，运算速度极高,50,光计算机的历史和研发现状,光计算机的历史1969年，研究光计算机的序幕由美国麻省理工学院的科学家们揭开1982年，英国赫罗特一瓦特大学物理系教授德斯蒙德史密斯研制出光晶体管1983年，日本京都大学电气工程系佐佐木昭夫教授、腾田茂夫副教授也研制出光晶体管1986年，美国贝尔实验室发明了用半导体做成的光晶体管，其具有开关特性。科学家运用集成光路技术，把光晶体管、光源、光存贮器等元件集成在一块芯片上，制成集成光路，与集成电路相似,51,光计算机的历史和研发现状（Cont.1）,光计算机的历史1990年，贝尔实验室研制出世界上第一台光计算机。它采用砷化镓光学开关，由激光器、透镜、反射镜等组成，运算速度达每秒10亿次。这是光计算机领域中的一大突破,美国贝尔实验室研制的世界上第一台光计算机,52,光计算机的历史和研发现状（Cont.2）,光计算机的研发现状2004年前，没人能够用硅制造出速度大于20MHz的光调制器2004年2月，Intel新研发的光调制器速度已达千兆Hz2005年，英特尔推出1Gbps传输速度的光调制器，即相当于在一条光纤上每秒传输10亿比特的信息2007年7月24日，Intel研发出能够对数据以40Gbps的速度进行编码的激光调制器2011年12月14日，英国光纤实验室的研究人员通过对普通光纤的直径在纳米尺度上进行微调，使光纤成为制造光子计算机必需的微谐振器，为研制光计算机开辟了新方法,53,光计算机的优势,传输和处理的信息量极大光计算机具有极为理想的光辐射源激光器光器件允许通过的光频率高、范围大，也即带宽非常大光子的传导可以不需要导线，而且即使在相交的情况下，它们之间也不会产生丝毫影响因为两束光要发生干涉，必须频率相同，振动方向一致和有不变的初始相位差。同一根光纤中能并行地传输很多波长不同或波长相同但振动方向不同的光波，它们之间不会发生干涉光计算机无导线传递信息的平行通道，其密度实际上是无限的，据计算每边长1.5厘米左右的三棱镜，信息通过能力比全世界现有的全部电话电缆的通过能力还要大许多倍,54,光计算机的优势（Cont.1）,超高速的运算速度光子既可以在半真空中传播，也可以在介质中传播，其传播速度（3105km/s）比电子在导线中的传播速度（593km/s）快得多，光子携带信息传递的速度比电子快光器件的开关速度比电子器件快得多光计算机的运算速度理论上可达到每秒1000亿次，信息存储量达到1018位,55,光计算机的优势（Cont.2）,能量消耗小，散发热量低除激光源需要一定的能量外，光在传输和转换时，能量消耗却极低光计算机的驱动，只需要同类规格的电子计算机驱动能量的一小部分这不仅降低了电能消耗，大大减少了机器散发的热量，而且有利于光计算机的微型化和便携化,光计算机的许多关键技术，如光存储技术、光互连技术、光电子集成电路等都已获得突破,56,3、生物计算机,生物计算机的定义仿生学：即通过对自然界生物特性的研究与模仿，来达到为人类社会更好地服务的目的生物计算机（BiologicalComputer）又称仿生计算机（BionicComputer）或生物电脑，它是以生物芯片取代在半导体硅片上集成数以万计的晶体管制成的计算机它利用蛋白质具有“开”与“关”的特性，用蛋白质分子作为元件制成生物芯片生物芯片存储点只有一个分子大小，所以它的存储容量可以达到普通计算机的十亿倍。蛋白质集成电路，大小只相当于硅集成电路的十万分之一；而运行速度更快，只有10-11秒，大大超过人脑的思维速度,57,生物芯片和生物计算机,像花布一样五彩斑斓的生物芯片,“拆拆拼拼”基因分子生物计算机,58,生物计算机的历史和研发现状,生物计算机涉及计算机科学、脑科学、神经生物学、分子生物学、生物物理、生物工程、电子工程、物理学和化学等有关学科生物计算机的历史和研发现状1982年，在法国阿尔卑斯举行了首届生物计算机国际会议1983年，美国公布了研制生物计算机的设想，美国、日本、德国和俄罗斯等国积极开始生物芯片的开发研究1994年11月，美国南加州大学教授雷纳德阿德勒曼（L.Adleman）博士，在科学杂志上发表论文“组合问题的生物电脑解决方案”，首次提出分子计算机，即用DNA（脱氧核糖核酸）分子构建电脑的设想,59,阿德勒曼生物计算机实验,他利用所发明的DNA生物电脑，解决了著名的数学难题“旅行商问题”，即TSP问题（TravellingSalesmanProblem），“由14条单行道连接着7座城市，请找出走过上述全部城市的最近路途，而且不能走回头路。”通过7天时间的系列生化反应，DNA电脑自动找出了解决问题的唯一答案，即只经过每座城市一次且顺序最短的DNA分子链,DNA电脑与生物电脑之父,用生物学方法模拟的逻辑运算，仅用一周时间完成了电子计算机几年才能完成的工作，表明了用DNA技术处理高难度数学问题的巨大优势,60,生物计算机的历史和研发现状（Cont.1）,2000年3月17日，美国威斯康星大学的研究人员制造出一台生物计算机。它由大约100万亿个人工合成的DNA链状结构组成，能进行一些相对复杂的运算2001年11月，以色列科学家成功研制出世界上第一台可编程DNA电脑，它的输入、输出和软硬件全由在活性有机体中储存和处理编码信息的DNA分子组成。这种电脑即使有一万亿“台”，其体积也不超过一滴水的大小,61,生物计算机的历史和研发现状（Cont.2）,2005年3月6日，以色列以色列海法理工大学的研究人员研制出能运行更多程序、有潜力对生物分子进行更复杂分析的生物计算机。在一块镀金芯片上，使用数种酶为计算机“硬件”，DNA为“软件”，输入和输出的“数据”都是DNA链。把溶有这些成分的溶液恰当地混合，就可以使其自动发生反应，进行“运算”。2008年5月21日，美国戴维森学院、北卡罗来那大学和密苏里西部大学等多个高校生物和数学专业的研究人员，通过对埃希氏菌属大肠杆菌添加基因，成功创造出细菌计算机。,62,生物计算机的优势,密集度高，存储能力强DNA生物电子元件比硅芯片上的电子元件小很多，而且生物芯片本身具有天然独特的立体化结构，其密度要比平面型硅集成电路高5个数量级，因此具有巨大的存储能力生物芯片在1mm2面积上可容纳数亿个电路。如体积为1m3的液体生物计算机，存储的信息比世界上所有计算机存储的信息总和还要多，而分子集成电路的密集度可以达到现有半导体超大规模集成电路的10万倍,63,生物计算机的优势（Cont.）,可自我修复，可靠性高生物芯片同一般的生物体一样，具有“自我修复”机能，一旦出现故障，可自我修复生物计算机的可靠性非常高，经久耐用，具有“半永久性”,速度快，能耗低分子逻辑元件的开关速度比硅半导体元件开关速度高1000倍以上。如果让几万亿个DNA分子在某种酶的作用下进行化学反应，就能使生物计算机同时运行几十亿次生物芯片内流动电子间碰撞的可能极小，几乎不存在电阻，故生物计算机的能耗极小，仅相当于普通计算机的十亿分之一,64,4、量子计算机,量子计算机的定义和原理量子（Quantum）：在微观领域中，某些物理量的变化是以最小的、不可分割的单位跳跃式进行的，而不是连续的，这个最小的基本单位叫做量子量子理论认为，非相互作用下，原子在任一时刻都处于两种状态，称之为量子超态。原子会旋转，即同时沿上、下两个方向自旋，这正好与电子计算机的0与1完全吻合量子计算机（QuantumComputer）是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的计算机。它通过控制原子或小分子的状态，来记录和运算信息,65,量子计算机的原理,在经典计算机中，基本信息单位为比特在量子计算机中，基本信息单元为量子比特或者qubit（昆比特），它是按照性质四个一组组成的单元。qubit不仅能在相应于传统计算机位的逻辑状态0和1稳定存在，而且也能在相应于这些传统位的混合或重叠状态存在。也就是说，量子位（qubit）可以是0或者1，也可以同时是0和l量子计算机对每一个叠加分量实现的变换相当于一种经典计算，所有计算同时完成，并按一定的概率振幅叠加起来，给出量子计算机的输出结果，这种计算称为量子并行计算如果把一群原子聚在一起，它们不是像电子计算机那样进行线性运算，而是同时进行所有可能的运算，因此，量子计算机比起经典计算机有着速度上的绝对优势,66,量子计算机的原理（Cont）,应用量子信息的产生、载荷、传播和处理，构造高性能的量子计算机，在提高运算速度、确保信息安全、增大信息容量和提高检测精度等方面将大大突破经典计算机量子计算机可用作各种大信息量数据的处理，如密码分析和密码破译等,量子计算机,硅芯片上16位量子比特的光学照片,67,量子计算机的历史和研发现状,量子计算机的历史和研发现状史蒂芬威斯纳在1969年最早提出“基于量子力学的计算设备”。亚历山大豪勒夫（1973）、帕帕拉维斯基（1975）、罗马印戈登（1976）和尤里马尼（1980）先后发表了关于“基于量子力学的信息处理”的文章二十世纪八十年代科学家们一系列的研究使得量子计算机的理论变得丰富起来，但量子计算机仍是处于理论推导等纸上谈兵状态1982年，诺贝尔奖获得者物理学家理查德费曼（RichardFeymnan）在一个著名的演讲中提出利用量子体系实现通用计算的想法,68,量子计算机的历史和研发现状（Cont.1）,1985年，大卫杜斯提出了量子图灵机模型1994年，贝尔实验室的专家彼得秀尔（PeterShor）提出量子质因子分解算法，该算法能够破解主流的非对称（公钥）密码算法如RSA密码算法，不少学者开始着力于研究利用各种量子系统来实现量子计算机2007年2月，加拿大D-Wave系统公司研制成功16位量子比特的超导量子计算机“Orion”（猎户座），但其作用仅限于解决一些最优化问题，与科学界公认的能运行各种量子算法的量子计算机仍有较大区别2009年，耶鲁大学的科学家制造了首个固态量子处理器2009年11月15日，世界首台可编程的通用量子计算机在美国诞生,69,量子计算机的历史和研发现状（Cont.2）,2012年，美国国家标准技术研究院的科学家们研制出一台可处理2量子比特数据的量子计算机2013年5月3日，德国马克斯普朗克量子光学研究所的科学家格哈德瑞普领导的科研小组，首次成功实现了用单原子存储量子信息将单个光子的量子状态写入一个铷原子中，经过180s后将其读出。这一突破有望助力科学家设计出功能强大的量子计算机，并让其远距离联网构建“量子网络”2013年6月8日，由中国科学技术大学潘建伟院士领衔的量子光学和量子信息团队的陆朝阳、刘乃乐研究小组，在国际上首次成功实现了用量子计算机求解线性方程组的实验,70,量子计算机的历史和研发现状（Cont.3）,2013年11月19日，悉尼大学和澳大利亚国立大学的研究人员在单个元件上聚集了迄今数量最大的量子回路，将此前14个的世界纪录刷新为10000个，提高了3个数量级2014年1月3日，美国国家安全局（NSA）正在研发一款用于破解加密技术的量子计算机，希望破解几乎所有类型的加密技术,量子处理器,71,量子计算机的优势,存储能力强经典计算机的一个bit只能存储一位数字（0或1），n个二进制位只能存储n个一位二进制数或者1个n位二进制数而在量子计算机里，一个量子重叠态运行一个qubit可以同时存储0和1。两个qubit能同时存储所有的4个二进制数。三个qubit能储存8个二进制数000、001、010、011、100、101、110和111。n个qubit可以同时存储2n个数据量子计算机只用300个光子（或300个离子等）就能存储比宇宙中的原子数还多的数字，而且对这些数字的计算可以同时进行,72,量子计算机的优势（Cont.）,并行运算能力强与经典计算机相比，量子计算机最重要的优越性体现在量子并行计算上。1994年，彼得秀尔证明量子计算机能完成大数因式分解和离散对数运算，且速度远胜于经典计算机。对1000位的大数进行因数分解，量子计算机只需几分之一秒，而经典计算机则需1025年因为量子不像半导体只能记录0与1，它可以同时表示多种状态，一次运算可以处理多种不同状况。一个40昆比特的量子计算机，能在很短时间内解开1024位计算机花上数十年解决的问题例如RSA算法是基于大整数素因子分解问题的公钥密码算法，如果利用经典计算机破解，花费时间为指数时间。而如果利用量子计算机，秀尔算法可以在多项式时间内破解RSA算法,73,1.6.3计算机之逻辑基础,1.6.3.1为什么计算机中采用二进制而不是十进制1.6.3.2逻辑代数的相关概念1.6.3.3二进制数的逻辑运算1.6.3.4组成计算机的基本元器件,了解即可,重点,74,需要思考的若干问题,请带着以下问题学习本节内容（1）为什么冯诺伊曼机要采用二进制数而不是十进制数表示指令和代码？用什么器件可以很方便地表示二进制的0和1？（2）计算机为什么能像人一样进行加减乘除各种算术运算？逻辑运算又是什么运算？有什么用途？（3）构造计算机或者数字电路（逻辑电路）的基本元器件是什么？数字电路中的主要开关器件有哪些？,75,1.6.3.1为什么计算机中采用二进制而不是十进制,采用十进制的计算机1642年，法国科学家BlaisePascal（16231662）研制成功一种齿轮式计算机器帕斯卡机，这是世界上第一台机械计算机。它用齿轮来表示和存储十进制各数位上的数字，通过齿轮比解决进位问题：低位的齿轮转动10圈，高位的齿轮只转动1圈。数在计算过程中自动存储，机器可自动执行一些计算规则。,76,采用十进制的计算机,1946年在美国宾夕法尼亚大学诞生的世界第二台电子计算机ENIAC，它使用电子器件进行所有计算操作，而不是滚轮、棘轮或者机械开关。ENIAC计算机也是一台十进制的计算机，它采用十个真空管来表示一位十进制数,冯诺依曼等人觉得ENIAC采用十进制的表示和实现方式十分麻烦，故在研制EDVAC时，提出了二进制的表示方法程序和数据都用二进制表示，从此改变了整个计算机的发展历史,ENIAC,77,计算机采用二进制的原因,（1）二进制运算规则简单十进制包括09共10个数码，遵循进位原则“逢10进1，借1当10”二进制只包括“0”和“1”两个数码，进位原则为“逢2进1，借1当2”二进制的加法运算、乘法运算都只有四条规则,加法运算规则00001110111(1)0,乘法运算规则0*000*101*001*11,十进制的运算规则复杂得多！比如乘法运算，要记住除0以外的每一个数码与19数字的乘法运算规则一共9*9=81条,重点,78,计算机采用二进制的原因（Cont.1）,（2）采用半导体器件表示二进制的两种状态具有诸多优势半导体器件具有开关特性在不同的输入条件下，有两个完全不一样的状态（导通和截止），正好对应二进制的0和1抗干扰能力强只要电信号在一定范围之内，就能够可靠地区分高、低电平两种状态从一种状态转换为另一种状态很方便硅二极管，只要加在其两端的电压大于0.7V，它就导通；如果小于0.7V，它就截止。对于三极管，只要在输入端加上两种不同幅值（3V和0.3V）的信号，就可以控制它的导通或截止,79,计算机采用二进制的原因（Cont.2）,状态转换速度非常快即开关速度非常快，这是开关电路的重要性能指标，它决定了计算机的运算速度。开关电路一般用平均传输延迟时间tpd来衡量其速度，三极管的tpd一般在几ns几十ns的范围体积小随着微电子技术和集成电路制造技术的进步，晶体管的尺寸越来越小，在一片硅片上，可以集成几万、几十万甚至上亿个晶体管，使得集成电路的集成度越来越高。则整个计算机的体积减小，可靠性更高工作时消耗的电能低，即功耗（能耗）低则整个计算机的功耗很小。功耗是计算机的一项重要指标，因为能耗会导致芯片发热，极大地影响芯片的集成度，从而限制了计算机的运行速度,80,计算机采用二进制的原因（Cont.3）,（3）二进制算术运算与逻辑运算能够统一起来可以用逻辑运算实现算术运算（可以采用移位、逻辑与、逻辑或等运算进行加减乘除运算）在计算机中，正是将具有逻辑与、逻辑或、逻辑非等功能的门电路组合起来，实现加法运算的对于减法、乘法、除法等运算，则利用特殊的技术，将其转化为加法来实现，使得运算器的设计变得简单,81,计算机采用二进制的原因（Cont.4）,（4）二进制数据便于存储采用二进制表示数据，物理上容易实现数据的存储二进制数据除了可以利用半导体器件来存储外，还可以利用磁盘、光盘等来存储磁盘是根据电磁学原理，使得涂敷在磁盘片上的磁粉被磁头磁化时具有两种不同的磁化方向来记录二进制信息的在刻录CD-ROM或DVD-ROM等只读型光盘时，通过大功率激光照射盘片的染料层，使相应部位的染料层发生化学变化，形成一个凹坑；激光没有照射到的部位仍然是平面，凹点表示二进制信息“0”，凸点表示二进制信息“1”,82,1.6.3.2逻辑代数的相关概念,1、逻辑和逻辑代数所谓“逻辑”，指事物间的因果关系，或者说条件与结果的关系。“因”是条件，条件之间用基本逻辑关系进行组合，根据不同的条件进行运算得到“结果”1847年，英国数学家和逻辑学家乔治布尔（GeorgeBoole）（18151864）发表了论文“逻辑的数学分析”，并出版了著作逻辑的数学分析，论演绎推理的演算法，提出描述客观事物逻辑关系的数学方法，即利用代数的方法来研究推理、证明等逻辑问题，形成了代数学的一个独立的分支，在此基础上建立了逻辑代数，又称布尔代数（Booleanalgebra）逻辑代数是捕获了集合运算和逻辑运算二者的根本性质的一个代数系统。它处理集合运算交集、并集、补集以及逻辑运算与、或、非,了解即可,83,逻辑代数与普通代数的比较,逻辑代数不仅是研究逻辑学的数学基础，也是分析和设计逻辑电路的数学基础,逻辑代数与普通代数的相似之处都是由变量、常量及各种运算符组成的代数系统。逻辑代数与普通代数的不同之处逻辑代数表达的是电路输入与输出间的逻辑关系，而不是数量关系。逻辑代数中的变量和常量只能取值为0或1，这里的0或1不是表示数值的大小，而是表示两种对立的关系。逻辑代数的基本运算为与、或、非；普通代数的基本运算为加、减、乘、除。,84,2、逻辑常量与逻辑变量,2、逻辑常量与逻辑变量当两个二进制数码表示不同的逻辑状态时，它们之间可以按照指定的某种因果关系进行推理运算，称为逻辑运算如逻辑与、逻辑或、逻辑非、逻辑与非、逻辑异或等在逻辑运算中其值不会改变的量称为逻辑常量最基本的逻辑常量是0和1（还有高阻z、未知x）。用0和1表示一个事物的两种不同逻辑状态，如一件事情的是和非、真和假、有和无、好和坏，电平的高和低、电流的有和无、灯的亮和灭、开关的闭合和断开等这种只有两种对立逻辑状态的逻辑关系称为二值逻辑,85,2、逻辑常量与逻辑变量（Cont.）,86,3、表示逻辑关系的不同方法,在逻辑代数中，可以用真值表、逻辑函数表达式、逻辑符号来表示逻辑关系真值表（TrueTable）是用0和1表示逻辑输入与输出之间全部关系的表格逻辑函数是由逻辑变量、常量通过逻辑运算符连接起来的代数式。如果有若干个逻辑变量（如A、B、C、D）由逻辑运算符连接在一起，得到一个表达式L。对逻辑变量的任意一组取值（如0000、0001、0010）L有唯一的值与之对应，则称L为逻辑函数。逻辑变量A、B、C、D的逻辑函数记为：L=f(A、B、C、D)用逻辑运算符把各种逻辑的输出与输入之间的关系连接起来形成的函数表达式称为逻辑函数表达式另外，还可以将与、或、非等各种逻辑关系用特定的图形符号来表示，这种图形符号称为逻辑符号,87,表示逻辑关系的不同方法举例,假定A、B是两个输入逻辑变量，P是输出逻辑变量，A和B进行逻辑与运算，得到P。则这种逻辑关系可以描述为：P=AB,逻辑函数表达式,88,1.6.3.3二进制数的逻辑运算,逻辑代数的基本逻辑运算：逻辑与、逻辑或、逻辑非实际的逻辑问题往往比基本逻辑复杂，但都可以用与、或、非组合成的复合逻辑来实现，如与非、或非、与或非、异或、同或等,1、逻辑与（AND）运算只有决定事件结果的全部条件（输入）同时具备时，结果（输出）才发生，这种因果关系叫做逻辑与（或逻辑乘）,了解即可,89,1、逻辑与（AND）运算,“与”运算电路,用两个开关A和B串联来控制指示灯P的亮灭。规定：输入条件（开关A、B）：闭合表示为1，断开表示为0；输出结果（灯P）：亮表示为1，灭表示为0。只有当开关A、B同时闭合时，指示灯P才会亮逻辑函数表达式：P=AB=AB,逻辑乘运算符号也可以省略,又称逻辑乘,这里的例子只有2个输入变量，但实际上，逻辑与可以有2个以上的输入，比如P=ABC,运算规则000010100111,90,2、逻辑或（OR）运算,“或”运算电路,开关A和B并联只要A或B有一个闭合，灯P就会亮逻辑函数表达式：P=A+B,2、逻辑或（OR）运算在决定事件结果的诸多条件中只要有任何一个满足，结果就会发生，这种因果关系叫做逻辑或（逻辑加）,91,逻辑或运算的真值表和运算规则,运算规则000011101111,运算规则：只要输入中有一个1，输出就为1；只有输入全为0时，输出才为0。,92,3、逻辑非（NOT）运算,3、逻辑非（NOT）运算只要条件具备了，结果便不会发生；而条件不具备时，结果一定发生，这种因果关系叫做逻辑非（也称逻辑反）逻辑非对单一的逻辑变量进行求反运算，是将一个二进制数据的0变为1，1变为0,开关A和灯P并联A闭合时，灯P不亮；A断开时，灯P反而亮,93,逻辑非的表示方法和运算规则,逻辑函数表达式,逻辑与、逻辑或都有2个或2个以上输入变量，而逻辑非只有1个输入变量,94,4、逻辑运算的用途,4、逻辑运算的用途逻辑运算通常用来测试各种逻辑关系的真假值逻辑运算常用作条件语句中的条件最常见到的逻辑运算就是循环的处理，逻辑运算的结果用作是否执行循环的条件，用来判断是否该离开循环或继续执行循环内的指令,【例1.1】对于阳历1900年2100年之间的任何一年，写出判断其是否为闰年（leapyear）的逻辑函数表达式。并以此判断2014年、2016年、2100年是否为闰年。,95,【例1.1】分析,【分析】一回归年的时间为365天5时48分46秒。阳历把一年定为365天，所余的时间约每4年积累成一天，加在二月里。这样的方法，在历法上叫做闰阳历四年一闰，在二月末加一天，这一天叫做闰日（leapday）。阳历有闰日的一年叫做闰年，闰年有366天所以阳历平常年份每年365天，二月为28天；闰年为366天，二月为29天每400年中有97个闰年,96,【例1.1】解答,解：满足以下两个条件之一的阳历年为闰年：能被4整除、且不能被100整除的年为闰年（如1904年）能被400整除的年为闰年（如2000年），不能被400整除的年则为平年（如1900年）整除可以用求模（即求余）运算符（%）来表示，若x与y的求模运算结果为0，说明x能被y整除。假定要判断的年份用变量year表示。(year%4=0)and(not(year%100=0)（1-1）(year%400=0)（1-2）整合后：(year%4=0)and(not(year%100=0)or(year%400=0)（1-3）,97,【例1.1】解答（Cont.）,将2014代入（1-3）式中，计算该式的值是否为1(2014%4=0)and(not(2014%100=0)or(2014%400=0)=0and(not(0)or0=0and1or0=0该式的值为0，说明2014年不是闰年,请自行根据（1-3）式计算2016年、2100年是否为闰年,98,逻辑运算在信息检索中的应用,逻辑运算的另一个用途，是在信息检索中，通过逻辑运算限定检索条件，来缩小搜索范围、提高搜索精