计算机科学与技术导论课件

王晓峰王晓峰 合肥学院计算机科学与技术系合肥学院计算机科学与技术系 230601 230601 合肥合肥xfwangiim.ac xfwangiim.ac 2009-102009-10计算机科学与技术计算机科学与技术导导 论论内内 容容 简简 介介 第一部分第一部分 引论引论第二部分第二部分 计算机科学的概念和基本知计算机科学的概念和基本知识识第三部分第三部分 计算机科学的意义、内容和方法计算机科学的意义、内容和方法第四部分第四部分 如何学习计算机科学和健康成如何学习计算机科学和健康成长长结束结束教学要求教学要求 目标目标:本课程是计算机科学与技术专业学生与所学专本课程是计算机科学与技术专业学生与所学专业相关的业相关的第一门课程第一门课程第一门课程第一门课程。课程将系统性地阐述计算机科。课程将系统性地阐述计算机科学与技术学科中的主要基本概念和问题，引导刚进入学与技术学科中的主要基本概念和问题，引导刚进入大学学习的学生对计算机科学与技术专业有一个概括大学学习的学生对计算机科学与技术专业有一个概括而准确地了解，从而为系统地学习计算机科学与技术而准确地了解，从而为系统地学习计算机科学与技术专业的后续课程打下一个良好的基础，树立学习专业专业的后续课程打下一个良好的基础，树立学习专业的的责任感和自豪感责任感和自豪感责任感和自豪感责任感和自豪感。目的目的:要求学生掌握计算机科学与技术学科及其相关要求学生掌握计算机科学与技术学科及其相关专业中的基本概念，基本方法和基本专业术语，了解专业中的基本概念，基本方法和基本专业术语，了解本学科的基本内容、基本理论和基本技术。本学科的基本内容、基本理论和基本技术。结束结束考核方式考核方式w课程论文：课程论文：40%w单元学习体会单元学习体会(2次次):40%w课堂笔记课堂笔记:10%w课堂表现课堂表现:10%结束结束第一章第一章 引论引论结束结束返回返回 1.1 1.1 计算机发展史计算机发展史 1.1.4 4 一般的科学思想方法一般的科学思想方法 1.1.5 5 计算机科学初学者的正确选择计算机科学初学者的正确选择 1.3 1.3 学科方法简介学科方法简介 1.2 1.2 计算机科学的来历计算机科学的来历1.1 1.1 计算机发展史计算机发展史w第一代计算机第一代计算机(1946(19461956)1956)：电子管时代：电子管时代w第二代计算机第二代计算机(1957(19571963)1963)：晶体管时代：晶体管时代w第三代电子计算机第三代电子计算机(1964(19641975)1975)：集成电路时代：集成电路时代w第四代电子计算机第四代电子计算机(1976(1976至今至今)：大规模和超大规：大规模和超大规模集成电路时代模集成电路时代 w第五代计算机（正在研制）第五代计算机（正在研制）：光子、生物芯片技术：光子、生物芯片技术w第六代计算机（未来）第六代计算机（未来）：神经集成电路：神经集成电路第一代计算机(19461956)w世界上第一台电子计算机世界上第一台电子计算机19461946年诞生于美国宾夕法尼亚大学，年诞生于美国宾夕法尼亚大学，即即ENIAC(The Electronic Numerical Integrator and ENIAC(The Electronic Numerical Integrator and Computer)Computer)，重，重3030吨，占地吨，占地170170平方米平方米,使用了使用了1800018000个电子个电子管，管，7000070000个电阻器，有个电阻器，有5 5百万个焊接点，耗电百万个焊接点，耗电160160千瓦。千瓦。w1959年年9月，我国第一台每秒钟运算月，我国第一台每秒钟运算10000次的快速通用电次的快速通用电子数字计算机在北京试制成功。子数字计算机在北京试制成功。返回返回第二代计算机(19571963)w用晶体管代替电子管，出现了现代计算机的一些部件用晶体管代替电子管，出现了现代计算机的一些部件:打印打印机、磁带、磁盘、内存、操作系统等。机、磁带、磁盘、内存、操作系统等。w出现了较为高级的出现了较为高级的COBOL(Common Business-Oriented COBOL(Common Business-Oriented Language)Language)和和FORTRAN(Formula Translator)FORTRAN(Formula Translator)等语言，以单词、等语言，以单词、语句和数学公式代替了二进制机器码。语句和数学公式代替了二进制机器码。w我国第一台晶体管大型通用数字计算机我国第一台晶体管大型通用数字计算机19671967年年1010月在中国科月在中国科学院计算技术研究所试制成功学院计算技术研究所试制成功。美国IBM公司1959年生产的IBM 7090型晶体管电子计算机 第三代电子计算机(19641975)w开始使用集成电路，计算机变得更小，功耗更低，速度更快。开始使用集成电路，计算机变得更小，功耗更低，速度更快。这一时期的发展还包括使用了操作系统，使得计算机在中心这一时期的发展还包括使用了操作系统，使得计算机在中心程序的控制协调下可以同时运行许多不同的程序。程序的控制协调下可以同时运行许多不同的程序。w1973年年8月，我国第一台每秒钟运算月，我国第一台每秒钟运算100万次的集成电路电万次的集成电路电子计算机在北京试制成功。子计算机在北京试制成功。返回返回1964年，世界上第一个采用集成电路的通用计算机IBM 360 第四代电子计算机(1976至今)w大规模集成电路大规模集成电路(LSI)可以在一个芯片上容纳几百个元件，可以在一个芯片上容纳几百个元件，超大规模集成电路超大规模集成电路(VLSI)在芯片上容纳了几十万个元件，后在芯片上容纳了几十万个元件，后来的来的ULSI将数字扩充到百万级。将数字扩充到百万级。w1981年，年，IBM推出个人计算机推出个人计算机(PC)用于家庭、办公室和学校。用于家庭、办公室和学校。苹果公司的苹果公司的Apple Macintosh系列于系列于1984年推出。年推出。返回返回IBM-PC机苹果机笔记本电脑第五代计算机（正在研制）w超导计算机：使用超导体元器件，耗电量仅为半导体器件制超导计算机：使用超导体元器件，耗电量仅为半导体器件制造的电脑的几千分之一，执行一个指令只需十亿分之一秒。造的电脑的几千分之一，执行一个指令只需十亿分之一秒。w光计算机：利用光作为载体进行信息处理，运算速度比普通光计算机：利用光作为载体进行信息处理，运算速度比普通的电子计算机快的电子计算机快1000倍倍 w生物计算机：蛋白质分子作元件制成集成电路，称为生物芯生物计算机：蛋白质分子作元件制成集成电路，称为生物芯片，存储量可以达到普通电脑的片，存储量可以达到普通电脑的10亿倍，传递信息的速度也亿倍，传递信息的速度也比人脑思维的速度快比人脑思维的速度快100万倍。万倍。w量子计算机：某个装置处理和计算的是量子信息，运行的是量子计算机：某个装置处理和计算的是量子信息，运行的是量子算法时，它就是量子计算机。量子算法时，它就是量子计算机。返回返回超导芯片生物芯片第六代计算机（未来）w第六代电子计算机是模仿人的大脑判断能力和适应能力，并第六代电子计算机是模仿人的大脑判断能力和适应能力，并具有可并行处理多种数据功能的神经网络计算机。具有可并行处理多种数据功能的神经网络计算机。w人的大脑却具有能处理支离破碎、含糊不清信息的灵活性，人的大脑却具有能处理支离破碎、含糊不清信息的灵活性，第六代电子计算机将类似人脑的智慧和灵活性。第六代电子计算机将类似人脑的智慧和灵活性。w神经电子计算机的信息不是存在存储器中，而是存储在神经神经电子计算机的信息不是存在存储器中，而是存储在神经元之间的联络网中。若有节点断裂，电脑仍有重建资料的能元之间的联络网中。若有节点断裂，电脑仍有重建资料的能力，它还具有联想记忆、视觉和声音识别能力。力，它还具有联想记忆、视觉和声音识别能力。返回返回大规模神经集成电路，它模仿人脑的神经细胞结构 1.2 1.2 计算机科学一词的来历计算机科学一词的来历由于由于图灵图灵图灵图灵和和冯冯冯冯.诺伊曼诺伊曼诺伊曼诺伊曼等人的贡献，使得存储程序等人的贡献，使得存储程序式通用电子计算机在式通用电子计算机在40年代诞生，实现了人类使用年代诞生，实现了人类使用自动计算装置代替人工计算和手工劳动的梦。自动计算装置代替人工计算和手工劳动的梦。狭义的计算机科学其研究内容覆盖了对计算机问题狭义的计算机科学其研究内容覆盖了对计算机问题的一般研究。的一般研究。广义的计算机科学包括的内容不仅覆盖了计算机科广义的计算机科学包括的内容不仅覆盖了计算机科学与技术的研究范畴，而且还包含更多的内涵学与技术的研究范畴，而且还包含更多的内涵。学科类形态w所谓学科类形态是指从事一类学科研究与发展工作且具有共所谓学科类形态是指从事一类学科研究与发展工作且具有共性的文化方式。性的文化方式。w历史上一共有两大学科类形态，即历史上一共有两大学科类形态，即理论理论与与实验实验。w不同的学科类形态支持按照自己特有的方式方法和科学发展不同的学科类形态支持按照自己特有的方式方法和科学发展轨道开展学科的研究与发展，由此产生了轨道开展学科的研究与发展，由此产生了理论科学理论科学与与实验科实验科学学两个学科类。两个学科类。w随着计算机科学与技术学科研究就和应用的深化，一些学者随着计算机科学与技术学科研究就和应用的深化，一些学者开始认识到开始认识到“计算计算”已经最为理论与实验之外的第三种学科已经最为理论与实验之外的第三种学科形态出现。形态出现。w科学认识事物方式方法的三步曲：科学认识事物方式方法的三步曲：一个科学的认识：一个科学的认识：建立在对于事物性质、特点和发展变化规建立在对于事物性质、特点和发展变化规律的深入的认识基础之上；律的深入的认识基础之上；一套科学的方法：一套科学的方法：基于科学的认识，通过寻找、建立，改进基于科学的认识，通过寻找、建立，改进或引用，发展解决这个问题的一套科学的方法；或引用，发展解决这个问题的一套科学的方法；一套科学的程序：一套科学的程序：着眼于具体解决这个问题，在科学认识的着眼于具体解决这个问题，在科学认识的基础之上，依据确定的一套科学的方法，制定实际解决问题基础之上，依据确定的一套科学的方法，制定实际解决问题的一个严密的、科学的程序，确定第一步做什么，怎么做，的一个严密的、科学的程序，确定第一步做什么，怎么做，第二步做什么，怎么做，确定每一步怎么检验，出了问题怎第二步做什么，怎么做，确定每一步怎么检验，出了问题怎么处理，等等。么处理，等等。1.3 1.3 学科方法简介学科方法简介w在通才教育观下，第一流的人才应该具备三个条件：在通才教育观下，第一流的人才应该具备三个条件：具有高尚的品德和良好的人文素养；具有高尚的品德和良好的人文素养；具有坚实的专业基础和深厚的专业功底；具有坚实的专业基础和深厚的专业功底；富有创新意识，具有科学的思想方法。富有创新意识，具有科学的思想方法。w所谓通才教育观在大学教育阶段是指教学内容的重点所谓通才教育观在大学教育阶段是指教学内容的重点立足于立足于一级学科一级学科的范围内开展工作，在此基础之上，的范围内开展工作，在此基础之上，根据学生的兴趣适当拓展其他学科的知识，以学科方根据学生的兴趣适当拓展其他学科的知识，以学科方法论和科学的思想方法作为重要的工具逐步扩大自己法论和科学的思想方法作为重要的工具逐步扩大自己的学科知识结构和领域，形成良好的科学素养。的学科知识结构和领域，形成良好的科学素养。1.4 1.4 一般的科学思想方法一般的科学思想方法w学习中我们不要求低年级的同学广泛借阅图书资料，学习中我们不要求低年级的同学广泛借阅图书资料，因为一个初学者不具备同时掌握几个体系的能力和知因为一个初学者不具备同时掌握几个体系的能力和知识基础。识基础。w一本好的教材完全能够帮助同学们正确理解书本知识一本好的教材完全能够帮助同学们正确理解书本知识的含义，关键是要多读几遍，多思考！的含义，关键是要多读几遍，多思考！w如果条件允许，在理解的基础上可以多上机操作和练如果条件允许，在理解的基础上可以多上机操作和练习，从而产生更为感性的认识。习，从而产生更为感性的认识。本章结束，按下键返回本章总目录1.5 1.5 计算机科学初学者的正确选择计算机科学初学者的正确选择结束结束返回返回 2.2 2.2 存储程序式计算机的基本结构与工作原理存储程序式计算机的基本结构与工作原理 2.1 2.1 计算模型与二进制计算模型与二进制 2.3 2.3 数字逻辑与集成电路数字逻辑与集成电路 2.4 2.4 机器指令与汇编语言机器指令与汇编语言 2.5 2.5 算法、程序算法、程序与与数据组织数据组织 2.6 2.6 高级语言与程序设计技术和方法高级语言与程序设计技术和方法 2.7 2.7 系统软件与应用软件系统软件与应用软件、软件工程方法软件工程方法 2.8 2.8 计算机组织与体系结构计算机组织与体系结构 2.9 2.9 计算机网络与通信计算机网络与通信 2.102.10 数据库系统数据库系统第二章第二章 计算机科学的基本概念计算机科学的基本概念2.1 计算模型与二进制w什么是计算模型？什么是计算模型？w所谓计算模型是刻划计算这一概念的一种抽象的所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤形式系统或数学系统，而算法是对计算过程步骤（或状态）的一种刻划，是计算方法的一种能行（或状态）的一种刻划，是计算方法的一种能行实现方式。实现方式。w在计算机科学中，我们通常所说的计算模型，并在计算机科学中，我们通常所说的计算模型，并不是指在其静态或动态数学描述基础上建立求解不是指在其静态或动态数学描述基础上建立求解某一某一(类类)问题计算方法的数学模型，而是指具有问题计算方法的数学模型，而是指具有状态转换特征，能够对所处理的对象的数据或信状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变换、输出的息进行表示、加工、变换、输出的数学机器数学机器。w图灵机图灵机(Turing Machine(Turing Machine)图灵机是英国人阿兰图灵机是英国人阿兰图灵（图灵（Alan TuringAlan Turing），在），在19361936年提年提出的一种出的一种理想的计算模型理想的计算模型，其基本思想是用机器来模拟人们，其基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：简单的动作：A.A.在纸上写上或擦除某个符号；在纸上写上或擦除某个符号；B.B.把注意力从纸的一个位置移动到另一个位置。把注意力从纸的一个位置移动到另一个位置。“图灵（Turing）奖”w图灵（图灵（Turing）奖是）奖是美国计算机协会美国计算机协会（ACM，Association for Computer Machinery）干）干 1966年设立的，专门奖励那年设立的，专门奖励那些对计算机科学研究与推动计算机技术发展有卓越贡献的杰些对计算机科学研究与推动计算机技术发展有卓越贡献的杰出科学家，被公认为计算机界的出科学家，被公认为计算机界的“诺贝尔诺贝尔”奖。奖。w图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只图灵奖对获奖者的要求极高，评奖程序也极严，一般每年只奖励一名计算机科学家，目前图灵奖由英特尔公司赞助，奖奖励一名计算机科学家，目前图灵奖由英特尔公司赞助，奖金为金为100,000美元。美元。w目前为止，获此殊荣的华人仅有一位，目前为止，获此殊荣的华人仅有一位，2000年图灵奖得主姚年图灵奖得主姚期智期智(Andrew Chi-Chih Yao)。2.1 计算模型与二进制w进位计数制：就是按进位方式实现计数的一种规则。进位计数制：就是按进位方式实现计数的一种规则。w基数：它表示某种进位制所具有的数学符号的个数。基数：它表示某种进位制所具有的数学符号的个数。w权：它表示某种进位制的数中不同位置上数字的单位数值。权：它表示某种进位制的数中不同位置上数字的单位数值。w十进制：基数为十进制：基数为1010，r r的取值范围的取值范围0-90-9。2.1 计算模型与二进制w二进制：二进制：基数为基数为2 2，r r的取值范围的取值范围0 0和和1 1。在早期研制计算机时，在当时的技术条件下，从便于元器件在早期研制计算机时，在当时的技术条件下，从便于元器件的设计和制造考虑，计算机的研制很自然地选择了二进制，的设计和制造考虑，计算机的研制很自然地选择了二进制，而后来的实践也证明了这种选择具有极大的优点。而后来的实践也证明了这种选择具有极大的优点。w 二进制数与十进制数的对应关系如下：二进制数与十进制数的对应关系如下：十进制数 0 1 2 3 4 5 6 7 8 9二进制数 0000 00010010 0011 0100 0101 0110 0111 1000 1001二进制数四则运算w加法运算，采用“逢二进一”的法则 0+0=0 0+1=1 1+0=1 1+1=10 w减法运算，采用“借一当二”的法则 0-0=0 1-0=1 1-1=0 10-1=1w乘法运算 00=0 10=0 01=0 11=1 w除法运算二进制数运算示例十进制与二进制之间的转换十进制与二进制之间的转换w二进制数转换成十进制数w十进制数转换成二进制数:整数部分除2取余；小数部分乘2取整。例:将(286.8125)10转换成二进制数。(1)286/2=143(0)143/2=71(1)71/2=35(1)35/2=17(1)17/2=8(1)8/2=4(0)4/2=2(0)2/2=1(0)1/2=0(1)从后往前取出余数100011110 (2)0.81252=1.625 0.6252=1.25 0.252=0.5 0.52=1.0 从前往后取出整数数1101 (3)(286.8125)10=(100011110.1101)2w冯诺伊曼原理（“存贮程序控制”原理）1.采用二进制形式表示数据和指令；2.将程序（数据和指令序列）预先存放在主存贮器中，使计算机在工作时能够自动高速地从存贮器中取出指令，并加以执行；3.由运算器、存贮器、控制器、输入设备、输出设备五大基本部件组成计算机系统，并规定了这五大部件的基本功能。w现代计算机的工作原理基本上遵循着冯诺伊曼原理，而按照该原理所构造的体系结构也称为“冯诺伊曼”体系结构。2.22.2存储程序式计算机的存储程序式计算机的基本结构与工作原理基本结构与工作原理“冯诺伊曼体系结构”w运算器(ALU):算术逻辑单元（Arithmetic Logic Unit），主要完成算术运算和逻辑运算以及移位、比较、传送等运算。w控制器：根据指令需要完成的功能，向各部件发出执行各种操作的命令，从而指挥计算机的各个部件进行工作。w中央处理单元（CPU）:通常把运算器、控制器合在一起称为CPU。数据流程信号流程w存储器:计算机中存储数据和程序的装置,也称计算机的记忆部件。w输入设备：把程序、数据等信息，通过输入接口转换成电信号。w输出设备：输出设备能把计算机运行结果或过程，通过输出接口转换成人们所要求的直观形式。w总线(bus)：在两个以上数字设备之间提供传送信息的公共通路。冯诺伊曼体系结构主要特点w单处理机结构，以运算器为中心；单处理机结构，以运算器为中心；w存储程序工作方式，数据和程序以二进制代码形式存储在单存储程序工作方式，数据和程序以二进制代码形式存储在单元是定长的一维空间存储器中元是定长的一维空间存储器中,存储器按线性编址结构进行存储器按线性编址结构进行地址访问；地址访问；w通过控制器进行集中控制；通过控制器进行集中控制；w指令的串行执行指令的串行执行,控制器根据存放在存储器中的指令序列控制器根据存放在存储器中的指令序列(程程序序)进行工作，并由一个程序计数器控制指令的执行；进行工作，并由一个程序计数器控制指令的执行；w使用低级机器语言，指令由操作码和地址码组成。使用低级机器语言，指令由操作码和地址码组成。计算机硬件方向w在学科的发展历程中，习惯上，人们将不带在学科的发展历程中，习惯上，人们将不带有软件系统的存储程序式电子数字计算机系有软件系统的存储程序式电子数字计算机系统称为统称为硬件裸机硬件裸机;w将硬件裸机、参与构成硬件裸机的各类部件将硬件裸机、参与构成硬件裸机的各类部件及其研究范畴统称为及其研究范畴统称为硬件（方向）硬件（方向）。2.3 2.3 数字逻辑与集成电路数字逻辑与集成电路 数字电路的基本知识：数字电路的基本知识：w模拟信号，即连续变化的物理量；数字信号，即离模拟信号，即连续变化的物理量；数字信号，即离散的物理量。散的物理量。w数字电路：对数字信号进行传输、控制或变换的电数字电路：对数字信号进行传输、控制或变换的电子电路。子电路。w数字系统：是用数字逻辑电路构成的，并由成千上数字系统：是用数字逻辑电路构成的，并由成千上万个电子器件来组成，由它们控制电路中电流的流万个电子器件来组成，由它们控制电路中电流的流向和程序的执行，完成各种算术和逻辑运算。向和程序的执行，完成各种算术和逻辑运算。数字电路的特点w工作信号是工作信号是二进制二进制的数字信号，在时间上和的数字信号，在时间上和数值上是数值上是离散离散的，反映在电路上就是只有低的，反映在电路上就是只有低电平和高电平两种状态，表示电平和高电平两种状态，表示0 0和和1 1两个逻辑两个逻辑值。值。w组成数字电路的元器件对精度要求不高，只组成数字电路的元器件对精度要求不高，只要在工作时能够可靠地区分要在工作时能够可靠地区分0 0和和1 1两种状态即两种状态即可。可。数字电路的分类w按集成度的不同：按集成度的不同：小规模小规模(SSI(SSI，每片数十器件，每片数十器件)、中规模、中规模(MSI(MSI，每片数，每片数百器件百器件)、大规模、大规模(LSI(LSI，每片数千器件，每片数千器件)和超大规模和超大规模(VLSI(VLSI，每片器件数目大于，每片器件数目大于1 1万万)LSIVLSI数字逻辑数字逻辑u数字逻辑是数字电路逻辑设计的简称，其内容是应用数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统的逻辑设计。数字电路进行数字系统的逻辑设计。u电子数字计算机是由具有各种逻辑功能的逻辑部件组电子数字计算机是由具有各种逻辑功能的逻辑部件组成的，这些逻辑部件成的，这些逻辑部件按其结构和工作原理不同按其结构和工作原理不同可分为可分为组合逻辑电路和时序逻辑电路。组合逻辑电路和时序逻辑电路。组合逻辑电路是由组合逻辑电路是由与门与门、或门或门和和非门非门等门电路组合形等门电路组合形成的逻辑电路成的逻辑电路,没有记忆功能，其输出信号只与当时没有记忆功能，其输出信号只与当时的输入信号有关的输入信号有关；时序逻辑电路是由触发器和门电路组成的具有记忆能时序逻辑电路是由触发器和门电路组成的具有记忆能力的逻辑电路力的逻辑电路,其输出信号不仅和当时的输入信号有其输出信号不仅和当时的输入信号有关，而且与电路以前的状态有关关，而且与电路以前的状态有关。门电路门电路w布尔布尔(逻辑逻辑)运算的操作数为是运算的操作数为是0(假假)和和1(真真)；P P ANDAND Q P Q P OROR Q Q NOTNOT P Pw当二进制的加法、乘法等运算与布尔代数的运算建立当二进制的加法、乘法等运算与布尔代数的运算建立了对应关系后，就可以用逻辑部件来实现二进制数据了对应关系后，就可以用逻辑部件来实现二进制数据的加法、乘法等各种运算。的加法、乘法等各种运算。w门（门（gategate）：一个当给定一个布尔运算的输入值时能）：一个当给定一个布尔运算的输入值时能够产生该布尔运算的输出值的设备。够产生该布尔运算的输出值的设备。“与与”、“或或”、“非非”三种门电路示意图三种门电路示意图 P P P A B C A B C A （a）“与与”门电路门电路 （b）“或或”门电路门电路 （c）”非非“门电路门电路“与与”门电路门电路w“与与”门电路一般有两个以上的输入和一个输出。门电路一般有两个以上的输入和一个输出。图图(a)(a)表示了一个表示了一个“与与”门电路，其输出门电路，其输出P P和输入和输入A A、B B、C C之间的逻辑关系可用下面的式子表示：之间的逻辑关系可用下面的式子表示：P PABCABCw电路设计中，用高电平信号表示电路设计中，用高电平信号表示1 1，低电平信号表示，低电平信号表示0 0。那么，。那么，“与与”门电路只有当输入门电路只有当输入A A、B B、C C同时为同时为1 1时，输出时，输出P P才为才为1 1，否则，否则，P P为为0 0。“或或”门电路门电路w“或或”门电路可以用图门电路可以用图(b)(b)表示。一般地说，其是表示。一般地说，其是一种具有逻辑加法功能的电路，它有两个以上的输一种具有逻辑加法功能的电路，它有两个以上的输入和一个输出，其输出入和一个输出，其输出P P和输入和输入A A、B B、C C之间的逻辑之间的逻辑关系可用下面的式子表示：关系可用下面的式子表示：P PA AB BC Cw“或或”门电路仅当输入门电路仅当输入A A、B B、C C中有一个为中有一个为1 1时，输时，输出出P P就为就为1 1，否则，否则，P P为为0 0。“非非”门电路门电路w“非非”门电路可以用图门电路可以用图(c)(c)表示。一般地说，其是表示。一般地说，其是一种具有逻辑取反功能的电路，它只有一个输入和一种具有逻辑取反功能的电路，它只有一个输入和一个输出，其输出一个输出，其输出P P和输入和输入A A之间的逻辑关系可用下之间的逻辑关系可用下面的式子表示：面的式子表示：P PA A “非非”门电路当输入门电路当输入A A为为0 0时，输出时，输出P P就为就为1 1，否则，否则，当输入当输入A A为为1 1时，输出时，输出P P为为0 0。将布尔代数和前面谈到的二进制联系起来，我们将布尔代数和前面谈到的二进制联系起来，我们可以看到，可以看到，“与与”、“或或”、“非非”门电路的作门电路的作用与集合运算用与集合运算“交交”、“并并”、“补补”是一致的。是一致的。一旦门电路中仅使用两个电平信号一旦门电路中仅使用两个电平信号0 0和和1 1，引入二，引入二进制及其运算规则，那么，用门电路及其组合就进制及其运算规则，那么，用门电路及其组合就可以实现二进制的各种运算，而对复杂电路的计可以实现二进制的各种运算，而对复杂电路的计算，如电路的化简就有可能通过布尔代数的方法算，如电路的化简就有可能通过布尔代数的方法进行，事实上也正是如此。进行，事实上也正是如此。2.4 2.4 机器指令与汇编语言机器指令与汇编语言 用用计计算算机机求求解解一一个个问问题题，必必须须事事先先编编制制好好程程序序。程程序序是是由由指指令令组组成成的的。每每一一台台计计算算机机都都设设计计规规定定了了一一组组指指令集合，称为机器指令系统。令集合，称为机器指令系统。机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示：指令格式：指令格式：操作码操作码 地址部分地址部分 其中，操作码指出运算的种类，如，其中，操作码指出运算的种类，如，跳，跳转等，地址部分用来指示参与运算的数据保存在什么地转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。方，如存储器的某个地址或某个寄存器等。操作码和地操作码和地址部分都用二进制代码表示。址部分都用二进制代码表示。机器指令的分类机器指令的分类w算术运算指令：实现基本的算术运算操作，如：加算术运算指令：实现基本的算术运算操作，如：加(ADD)(ADD)、减、减(SUB)(SUB)、乘、乘(MUL)(MUL)、除、除(DIV)(DIV)等指令；等指令；w逻辑运算指令：实现基本的逻辑运算操作，如逻辑运算指令：实现基本的逻辑运算操作，如 ：与：与(AND)(AND)、或、或(OR)(OR)、非、非(NOT)(NOT)、异或、异或(XOR)(XOR)等指令；等指令；w移位指令：实现对操作数进行移位、比较等操作。如：移位指令：实现对操作数进行移位、比较等操作。如：逻辑左移逻辑左移(SHL)(SHL)、逻辑右移、逻辑右移(SHR)(SHR)、算术左移、算术左移(SAL)(SAL)、算术右移算术右移(SAR)(SAR)等指令；等指令；w数据传送指令：实现数据传送指令：实现CPUCPU的寄存器之间及寄存器和存的寄存器之间及寄存器和存储器之间的数据传送，如：传送储器之间的数据传送，如：传送(MOV)(MOV)、入栈、入栈（PUSHPUSH）和出栈）和出栈(POP)(POP)等指令；等指令；w程序控制指令：程序控制指令：改变程序计数器的值，使计算机执改变程序计数器的值，使计算机执行指令的顺序按要求改变。如转移行指令的顺序按要求改变。如转移(JMP)(JMP)，子程序，子程序调用调用(CALL)(CALL)，返回，返回(RET)(RET)等指令；等指令；w输入输出指令：实现计算机主机通过输入输出指令：实现计算机主机通过I IO O接口和外接口和外部设备之间数据传送，如：端口输入指令部设备之间数据传送，如：端口输入指令(IN)(IN)，端，端口输出指令口输出指令(OUT)(OUT)；wCPUCPU控制指令：如停机指令控制指令：如停机指令(HLT)(HLT)等。等。w应当注意的是，应当注意的是，机器机器指令可以被机器直接理解和执指令可以被机器直接理解和执行行，因此对于不同的机器，其指令系统是不同的。，因此对于不同的机器，其指令系统是不同的。w指令系统的日渐增大虽然给用户的程序设计带来了指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的增加和因译码、方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而使运算速度下降。存储、寻址等开销的增大而使运算速度下降。w研究发现，研究发现，指令系统存在着改进的必要和可能。指令系统存在着改进的必要和可能。机器语言w机器语言：机器指令的集合机器语言：机器指令的集合。10111000 00000101 00000000 00000101000000110000000010100011000000000000001011100100机器语言的优点：机器语言的优点：能利用机器指令精致地描述算法，编能利用机器指令精致地描述算法，编程质量高；程质量高；所占存储空间小；所占存储空间小；执执行速度快。行速度快。机器语言的缺点：机器语言的缺点：难记、难读、难修改；难记、难读、难修改；需要人工需要人工分配内存；分配内存；程序通用性差程序通用性差 。8086机器语言示例机器语言示例汇编语言w汇编指令：用某个西文字符串的缩写来表示其所代表汇编指令：用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进的操作，用符号来代表数据的二进制、八进制和十进制数字序列。制数字序列。w汇编语言：是由一组汇编指令构成的语言，汇编语言：是由一组汇编指令构成的语言，也被称为也被称为符号语言。符号语言。MOV AX,5ADD AX,3MOV 200H,AXHLT汇编语言示例汇编语言示例优点优点：易于理解与记忆易于理解与记忆；能利用机能利用机器指令精致地描述算法，器指令精致地描述算法，编程质量高；编程质量高；所占存储空间小；所占存储空间小；执行速度较快。执行速度较快。缺点缺点：程序通用性也差；程序通用性也差；与计算机与计算机硬件直接相关，故称为低级语言。硬件直接相关，故称为低级语言。w有了汇编语言，就得编写和设计汇编语言翻译程序有了汇编语言，就得编写和设计汇编语言翻译程序（简称（简称汇编程序汇编程序），专门负责把使用汇编语言书写），专门负责把使用汇编语言书写的程序翻译成可直接执行的机器指令程序。一般说的程序翻译成可直接执行的机器指令程序。一般说来，来，汇编程序被看成是系统软件的一部分。汇编程序被看成是系统软件的一部分。源程序（汇编语言源程序（汇编语言）目标程序（机器语言）目标程序（机器语言）汇编程序汇编程序汇编过程过程2.5 2.5 算法、过程与程序算法、过程与程序w算法：算法：为解决一个特定问题而采取的确定的有限的步骤，在计为解决一个特定问题而采取的确定的有限的步骤，在计算机科学中，算法是指令的有限序列，算机科学中，算法是指令的有限序列，是一个可终止的、有序是一个可终止的、有序的、无歧义的、可执行的指令的集合的、无歧义的、可执行的指令的集合。w例子：判断一个大于或等于例子：判断一个大于或等于3 3的正整数是不是一个素数。的正整数是不是一个素数。对于该问题的求解过程可用文字描述如下：对于该问题的求解过程可用文字描述如下：Step 1Step 1:给出需要判断的正整数给出需要判断的正整数x x；Step 2Step 2:给一个变量给一个变量i i，令，令i=2i=2；Step 3Step 3:让让x x除以除以i i，得余数，得余数r r；Step 4Step 4:若若r=0r=0，则表示，则表示x x不是素数，算法结束，否则执行不是素数，算法结束，否则执行 下一步下一步 ；Step 5Step 5:将将i i1 1的值再次赋给的值再次赋给i i，若这时，若这时i i的值等于的值等于x x，则表示，则表示x x 是素数，算法结束，否则回到是素数，算法结束，否则回到Step 3Step 3重新开始。重新开始。算法与问题求解w用计算机进行问题的求解，大致需要经过以下几个步骤：用计算机进行问题的求解，大致需要经过以下几个步骤：分析问题分析问题-建立模型建立模型-设计算法设计算法-编写程序编写程序-上机调试上机调试 其中算法的设计是问题求解过程中最具有挑战性的步骤。其中算法的设计是问题求解过程中最具有挑战性的步骤。w问题求解的几个阶段：问题求解的几个阶段：阶段阶段1 1：理解问题；：理解问题；阶段阶段2 2：提出解决这个问题的算法思想；：提出解决这个问题的算法思想；阶段阶段3 3：形式地描述这个算法，将它表示为程序；：形式地描述这个算法，将它表示为程序；阶段阶段4 4：评价这个程序的精确度。：评价这个程序的精确度。算法复杂性算法复杂性w使用计算机计算各种问题，需要存储使用计算机计算各种问题，需要存储空间空间、计算、计算时时间间。不同的算法计算所需要的时间和空间是不同的。不同的算法计算所需要的时间和空间是不同的。所谓算法的复杂性就是对算法计算所需要的时间和所谓算法的复杂性就是对算法计算所需要的时间和空间的一种度量。空间的一种度量。w不言而喻，对于任意给定的问题，设计出不言而喻，对于任意给定的问题，设计出复杂性尽复杂性尽可能地低的可能地低的算法是我们在设计算法是追求的一个重算法是我们在设计算法是追求的一个重要目标；另一方面，当给定的问题已有多种算法时，要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。循的一个重要准则。w算法的复杂性可以看作是算法运行所需要的计算机资源的量，需要的时间资源的量称作时间复杂性，需要的空间资源的量称作空间复杂性。w算法的复杂性应该是只依赖于算法要解的问题的规模、算法的输入和算法本身的三元函数。C=F(N,I,A)其中，N表示算法要解问题的规模，I表示算法的输入，A表示算法本身，C表示算法的复杂性。复杂性度量函数复杂性度量函数u为了为了简化算法复杂性分析，简化算法复杂性分析，我们引入了复杂性度量函我们引入了复杂性度量函数，该函数表示了算法随问题规模大小变化引起的算数，该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化法中抽象的基本运算执行的次数或存储空间量的变化规律。规律。u假设某个计算问题当输入规模分别为假设某个计算问题当输入规模分别为1 1，2 2，3 3，n n时，经分析算法中抽象的基本运算次数分别为时，经分析算法中抽象的基本运算次数分别为1 1，4 4，9 9，n n2 2，那么，就可以用函数，那么，就可以用函数n n2 2来刻划这个算法的来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为时间复杂性，并称这个算法的时间复杂性度量为(n(n2 2)级。级。u有了复杂性度量函数，一旦选定具体计算机，可以根有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个据这台计算机对某个n n值的实际运算速度比较准确地值的实际运算速度比较准确地估算出对其他的估算出对其他的n n值完成计算所需要的时间。值完成计算所需要的时间。算法的特性算法的特性1.1.有穷性：算法的执行步骤不可以无穷无尽，设计算有穷性：算法的执行步骤不可以无穷无尽，设计算法时应该关注算法结束的条件；法时应该关注算法结束的条件；2.2.确定性：在任何情况下，算法只有唯一的一条执行确定性：在任何情况下，算法只有唯一的一条执行路径，即对相同的操作对象只能得出相同的结果；路径，即对相同的操作对象只能得出相同的结果；3.3.可行性：一个算法必须由可执行的步骤组成，即算可行性：一个算法必须由可执行的步骤组成，即算法中的每一个步骤都应当能有效地执行，并得到确法中的每一个步骤都应当能有效地执行，并得到确定的结果定的结果 ；4.4.输入：一个算法有零个或多个输入，输入是算法的输入：一个算法有零个或多个输入，输入是算法的操作对象；操作对象；5.5.输出：一个算法有一个或多个输出，一个算法必须输出：一个算法有一个或多个输出，一个算法必须有输出，即操作结果，没有输出的算法是毫无意义有输出，即操作结果，没有输出的算法是毫无意义的。的。程序程序w程序程序:是一种事先编制好了具有特殊功能的指是一种事先编制好了具有特殊功能的指令序列。这里的指令既可以是机器指令、汇编令序列。这里的指令既可以是机器指令、汇编语言指令，也可以是高级语言的语句命令，甚语言指令，也可以是高级语言的语句命令，甚至还可以是用自然语言描述的运算、操作命令。至还可以是用自然语言描述的运算、操作命令。w有一种程序的定义，用公式给出：有一种程序的定义，用公式给出：程序数据结构算法程序数据结构算法2.6 2.6 高级语言与程序设计技术和方高级语言与程序设计技术和方法法w计算机语言计算机语言:通常是一个能完整、准确和规则地表达人们的通常是一个能完整、准确和规则地表达人们的意图意图,并用以指挥或控制计算机工作的并用以指挥或控制计算机工作的“符号系统符号系统”。与人。与人类语言一样具有语言的三个基本要素：类语言一样具有语言的三个基本要素：语义、语法和语序语义、语法和语序。w低级语言：机器语言、汇编语言，低级语言：机器语言、汇编语言，与计算机硬件直接相关。与计算机硬件直接相关。w高级语言：是一种由表达各种意义的高级语言：是一种由表达各种意义的“词词”和和“公式公式”，按，按照一定的照一定的“语法规则语法规则”来编写程序的语言，又称为程序设计来编写程序的语言，又称为程序设计语言。语言。w高级语言的特点：高级语言的特点：独立于计算机硬件结构独立于计算机硬件结构 用户使用面向问题的形式来描述任务用户使用面向问题的形式来描述任务 易学、易懂、易查错。易学、易懂、易查错。w第一代语言：机器语言；第一代语言：机器语言；w第二代语言：汇编语言；第二代语言：汇编语言；w第三代语言：过程化的高级程序设计语言，如第三代语言：过程化的高级程序设计语言，如C C语言，语言，PASCALPASCAL语言；语言；w第四代语言：面向问题的、非过程化的程序设计语言，第四代语言：面向问题的、非过程化的程序设计语言，如如C+,Java,C#C+,Java,C#等；等；w第五代语言：更接近自然语言，更简单易用的基于人第五代语言：更接近自然语言，更简单易用的基于人工智能的语言，仍处于概念阶段工智能的语言，仍处于概念阶段,如如PROLOGPROLOG、LISPLISP。计算机语言的分代计算机语言的分代高级语言分类w编译类：编译是指在源程序执行之前，就将源程序编译类：编译是指在源程序执行之前，就将源程序“翻译翻译”成目标代码成目标代码(机器语言机器语言)，因此其目标程序可以脱离其语言，因此其目标程序可以脱离其语言环境独立执行，使用比较方便、效率较高环境独立执行，使用比较方便、效率较高,比如比如C C或或PascalPascal；w解释类：解释方式类似于解释类：解释方式类似于“同声翻译同声翻译”，源程序一边由相，源程序一边由相应语言的解释器应语言的解释器“翻译翻译”成目标代码成目标代码(机器语言机器语言)，一边执行，一边执行，因此效率比较低，而且不能生成可独立执行的可执行文件，因此效率比较低，而且不能生成可独立执行的可执行文件，应用程序不能脱离其解释器应用程序不能脱离其解释器,比如比如Basic,MATLABBasic,MATLAB。高级语言源程序“翻译”过程示意图常见的高级语言w通通用用结结构构化化计计算算机机语语言言：如如BasicBasic（适适用用于于初初学学者者的的计计算算机机语语言言）、PascalPascal（结结构构化化的的程程序序设设计计语语言言，适适用用于于教教学学）、C C（具具有有高高级级数数据据结结构构和和控控制制结结构构,亦亦可可调调用用底底层层功功能能的的通通用用语言）语言）w专专用用结结构构化化计计算算机机语语言言：如如FortranFortran（适适用用于于科科学学计计算算的的语语言）、言）、MATLABMATLAB（矩阵数学计算语言，功能强大矩阵数学计算语言，功能强大）w适适用用于于人人工工智智能能的的计计算算机机语语言言 ：如如PrologProlog（适适用用于于人人工工智智能的专家系统的逻辑性语言）能的专家系统的逻辑性语言）w面面向向对对象象的的计计算算机机语语言言：如如C+C+（扩扩展展的的c c语语言言，具具有有了了面面向向对象的特性）、对象的特性）、JavaJava（纯面向对象语言）（纯面向对象语言）w可可视视化化的的第第四四代代计计算算机机语语言言：如如PowerBuilderPowerBuilder(Sybase(Sybase公公司司开开发发的的可可视视化化数数据据库库应应用用软软件件开开发发工工具具)、DelphiDelphi(Borland(Borland公公司司开开发发的的可可视视化化开开发发工工具具)、Visual Visual FoxproFoxpro（微微软软公公司司设设计计开开发发的的可可视视化化数数据据库库开开发发工工具具）、Visual Visual BasicBasic（BasicBasic语言的扩展，微软公司设计开发的可视化开发工具语言的扩展，微软公司设计开发的可视化开发工具 ）程序设计语言的实现步骤w编译型程序设计语言的实现，大致包括了以下几步：编译型程序设计语言的实现，大致包括了以下几步：(a)(a)编写源程序；编写源程序；(b)(b)对源程序进行编译生成目标代码；对源程序进行编译生成目标代码；(c)(c)连接目标代码生成可执行文件；连接目标代码生成可执行文件；(d)(d)执行可执行文件完成任务。执行可执行文件完成任务。w解释性程序设计语言的实现：包括编写源程序，解解释性程序设计语言的实现：包括编写源程序，解释执行源程序两个过程。释执行源程序两个过程。w对程序结构本质的深入研究促进了对程序质量的认识，开发程对程序结构本质的深入研究促进了对程序质量的认识，开发程序的效率和质量取决于程序设计方法和技术序的效率和质量取决于程序设计方法和技术,多年的研究发展多年的研究发展了许多程序设计方法和技术。了许多程序设计方法和技术。w结构化程序设计结构化程序设计(SP):(SP):：“自顶而下，逐步求精自顶而下，逐步求精”的设计思想，的设计思想，“独立功能，单出、入口独立功能，单出、入口”的模块仅用的模块仅用3 3种种(顺序、分支、循环顺序、分支、循环)基本控制结构的编码原则基本控制结构的编码原则;w面向对象程序设计面向对象程序设计(OOP):(OOP):以对象为中心进行分析和设计，再以对象为中心进行分析和设计，再现了人类认识事物的思维方式和解决问题的工作方式。现了人类认识事物的思维方式和解决问题的工作方式。对象对象是是数据及对这些数据施加的操作结合在一起所构成的独立实体的数据及对这些数据施加的操作结合在一起所构成的独立实体的总称；总称；类类是一组具有相同数据结构和相同操作的对象的描述。是一组具有相同数据结构和相同操作的对象的描述。程序设计方法和技术2.7 2.7 系统软件与应用软系统软件与应用软件件w软件软件是计算机程序、方法、规范及其相应的文稿是计算机程序、方法、规范及其相应的文稿以及在计算机上运行时所必须的数据。以及在计算机上运行时所必须的数据。w软件软件=程序程序+数据数据+文档文档w程程序序是是按按事事先先设设计计的的功功能能和和性性能能要要求求执执行行的的指指令令序列；序列；w数据是使程序能适当地操纵信息的数据结构；数据是使程序能适当地操纵信息的数据结构；w文文档档是是指指描描述述程程序序开开发发，维维护护和和使使用用相相关关的的图图文文材料材料 。软件与硬件的不同w软软件件是是由由开开发发或或工工程程化化而而形形成成的的，而而不不是是传传统统意意义义上上的的制制造造产产生生的的，因因此此软软件件成成本本集集中中于于开开发发和和维维护护上面；上面；w在在软软件件的的运运行行和和使使用用期期间间，没没有有硬硬件件那那样样的的机机械械磨磨损损，老老化化问问题题。然然而而在在其其生生命命期期中中，软软件件会会经经历历修修改改（维维护护），有有可可能能引引入入新新的的错错误误，最最终终将将导导致致软软件本身被抛弃或重新开发；件本身被抛弃或重新开发；w大大多多数数软软件件是是自自定定义义，而而不不是是通通过过已已有有的的构构件件组组装装而来的。而来的。软件系统软件系统 硬件硬件计算机系统计算机系统 操作系统操作系统 支撑软件支撑软件 软件系统软件系统 应用软件应用软件系统软件系统软件w负责管理计算机系统中各种独立的硬件，使负责管理计算机系统中各种独立的硬件，使得它们可以协调工作。得它们可以协调工作。w系统软件使得计算机使用者和其他软件将计系统软件使得计算机使用者和其他软件将计算机当作一个整体，而不需要顾及到底层每算机当作一个整体，而不需要顾及到底层每个硬件是如何工作的。个硬件是如何工作的。w包括操作系统和一系列基本的工具（比如编包括操作系统和一系列基本的工具（比如编译器，数据库管理，存储器格式化，文件系译器，数据库管理，存储器格式化，文件系统管理，用户身份验证，驱动管理，网络连统管理，用户身份验证，驱动管理，网络连接等方面的工具）。接等方面的工具）。支撑软件支撑软件w指在某一特定范围内对各种应用对象具有通指在某一特定范围内对各种应用对象具有通用性的软件。其支撑各种软件的开发与维护用性的软件。其支撑各种软件的开发与维护的软件，又称为软件开发环境，它主要包括的软件，又称为软件开发环境，它主要包括环境数据库、各种接口软件和工具组。环境数据库、各种接口软件和工具组。w著名的软件开发环境有著名的软件开发环境有IBM公司的公司的Web Sphere，微软公司的，微软公司的Studio.NET、Visual Studio等。等。应用软件应用软件w相对于系统软件而言，应用软件是对用户在计算机系统上针相对于系统软件而言，应用软件是对用户在计算机系统上针对各种具体的应用问题开发的一类专用程序或软件的总称。对各种具体的应用问题开发的一类专用程序或软件的总称。w办公自动化软件，如办公自动化软件，如Microsoft Office,WPSw图形图像处理软件，如图形图像处理软件，如Photoshop,Painter,CorelDraww多媒体及动画制作软件多媒体及动画制作软件,如如3DS MAX,Authorware,Directorw网页制作软件，如网页制作软件，如Dreamweaver,F