计算机基础ppt课件

计算机基础知识,计算机组成计算机操作系统计算机网络数据库软件工程数据结构、算法、程序,陈海新2017.04.27,1.计算机系统的组成,计算机是由存储器、运算器、控制器、输入设备和输出设备等五大部件所构成。,请求信号、数据流,控制信号,冯诺依曼，1945,计算机系统,1.计算机系统的组成,系统软件,应用软件,计算机的软件系统包括,1.计算机系统的组成,（1）操作系统（2）语言处理程序（3）支撑软件（4）数据库系统,系统软件是指控制和协调计算机及其外部设备，支持应用软件的开发和运行的软件。其主要的功能是进行调度、监控和维护系统等等。系统软件是用户和裸机的接口。,1.计算机系统的组成,2.计算机操作系统,2.计算机操作系统,2.计算机操作系统,2.计算机操作系统,2.计算机操作系统,2.计算机操作系统,2.计算机操作系统,计算机网络的发展的四个阶段：1.第一阶段：“诞生阶段”以主机为中心的联机终端系统，“计算机终端”系统2.第二阶段：“形成阶段”以通信子网为中心的主机互连，“计算机-计算机”网络3.第三阶段：互联互通阶段体系结构标准化网络层次结构，对每层进行了精确定义4.第四阶段：高速网络技术阶段Internet网时代的到来,3.计算机网络,1.第一阶段：“诞生阶段”以主机为中心的联机终端系统,特征：终端(Terminal)共享主机(Host)的软硬件资源单台主机：执行计算和通信任务多台终端：执行用户交互(终端集中器/终端服务器)连接方式：本地或远程,T,T,T,T,T,HOST,通信线路,3.计算机网络,2.第二阶段：“形成阶段”通信子网为中心的主机互连,特征多个终端联机系统互联，形成了多主机互联网络网络结构从“主机终端”转变为“主机主机”,3.计算机网络,演变阶段1通信任务从主机中分离，由通信控制处理机（CCP）完成CCP：处理主机之间通信任务的专用计算机,3.计算机网络,两层网络概念的出现由CCP组成的传输网络通信子网，提供信息传输服务建立在通信子网基础上的主机集合资源子网，提供计算资源,CCP,CCP,HOST,HOST,T,T,T,T,T,T,CCP,HOST,T,T,T,通信子网,3.计算机网络,18,演变阶段2通信子网规模逐渐扩大私有社会公用公用数据通信网PSTNX.25优点降低用户系统建设成本提高通信线路利用率兼容性好,3.计算机网络,3.第三阶段：互联互通阶段体系结构标准化网络,为什么需要标准化？不同网络设备之间的兼容性和互操作性是推动网络体系结构的标准化的原动力而兼容性和互操作性的最终目的仍是资源共享标准化的时机？先制定标准再开发还是先开发再制定标准？各厂商、研究机构、大学在网络技术、方法、理论等方面的研究日趋成熟是基础,3.计算机网络,4.第四阶段：高速网络技术阶段,因特网的出现标志着网络时代的到来因特网是全球性的网络丰富的信息和便利的使用是其规模迅速增长的主要驱动力截止到2000年,Internet的规模为网络数达到105数量级,主机数达到107数量级,用户数108数量级，主干速率大于2.5Gbit/s,3.计算机网络,21,计算机网络体系结构的形成,相互通信的两个计算机系统必须高度协调工作才行，而这“协调”是相当复杂的。“分层”可将庞大而复杂的问题，转化为若干较小的局部问题，而这些较小的局部问题就比较易于研究和处理。,3.计算机网络,OSI与TCP/IP体系结构的比较,应用层,传输层,网络层,表示层,会话层,数据链路层,物理层,7654321,OSI的体系结构,应用层,网络接口层,网际层IP,(各种应用层协议如TELNET,FTP,SMTP等),传输层(TCP或UDP),TCP/IP的体系结构,3.计算机网络,分层的好处,1.各层之间是独立的。2.灵活性好。3.结构上可分割开。4.易于实现和维护。5.能促进标准化工作。,若层数太少，就会使每一层的协议太复杂。层数太多又会在描述和综合各层功能的系统工程任务时遇到较多的困难。,3.计算机网络,五层协议的体系结构：,TCP/IP是四层的体系结构：应用层、运输层、网际层和网络接口层。最下面的网络接口层并没有具体内容。因此往往采取折中的办法，即综合OSI和TCP/IP的优点，采用一种只有五层协议的体系结构。,3.计算机网络,计算机1向计算机2发送数据,5,4,3,2,1,5,4,3,2,1,计算机1,AP2,AP1,计算机2,应用程序数据,10100110100101比特流110101110101,注意观察加入或剥去首部（尾部）的层次,应用程序数据,3.计算机网络,网络接口卡,网络接口卡（NIC，简称网卡）能够使工作站、服务器、打印机或其他节点通过网络介质接收并发送数据。网络接口卡常被称为网络适配器。属于OSI模型的物理层。,3.计算机网络,中继器,中继器是一种放大或模拟数字信号的网络连接设备。中继器属于OSI模型中的物理层。它们只是转发信号，但同时也转发了信号的噪声，,3.计算机网络,集线器,集线器能与网络中的打印服务器、交换器、文件服务器或其他的设备连接。集线器属于OSI模型中的物理层。,3.计算机网络,网桥,网桥这种设备看上去有点像中继器。它具有单个的输入端口和输出端口，它与中继器的不同之处就在于它能够解析它收发的数据。网桥属于OSI模型的数据链路层,3.计算机网络,交换机,交换机属于OSI模型的数据链路层，并且，它还能够解析出MAC地址信息。事实上，它相当于多个网桥。,3.计算机网络,路由器,路由器是一种多端口设备，它可以连接不同传输速率并运行于各种环境的局域网和广域网，也可以采用不同的协议。路由器属于OSI模型的网络层设备。,3.计算机网络,数据库系统的产生与发展,数据库基本概念1）数据(Data)数据是描述事物的符号记录。2）信息(Information)通常被认为是具有一定含义的、经过加工的、对决策有价值的数据。3）数据库(Database,DB)数据库是指长期存储在计算机内，有组织的、可共享的数据集合。,4.数据库,数据结构是所研究的对象类型的集合。用于描述数据的静态特征。包括：数据的类型、内容和性质的对象（事物）；数据之间联系的对象（联系）。数据操作是对数据库中各种对象的实例允许执行的操作的集合。用于描述数据的动态特征。完整性约束完整性规则的集合。如性别只能有男和女之分，年龄不能为0等。,数据模型概述,4.数据库,最常用的数据模型,1层次模型,层次模型（HierarchicalModel）是一种以记录某一事物的类型为根节点的有向树。,4.数据库,2网状模型,最常用的数据模型,网状模型是层次模型的扩展，表示多个从属关系的层次结构，呈现一种交叉关系的网状结构。,4.数据库,关系模型（RelationalModel）是指虽具有相关性而非从属性的平行的数据之间按照某种序列排列的集合关系。关系模型是由若干个关系模式组成的集合，关系模式的实例称为关系，而每个关系实际上就是一张二维表格。,4.数据库,最常用的数据模型,3关系模型,基本概念,关系：一个关系对应一张表元组：表中的一行属性：表中的一列主码：表中的某个属性或属性组，它可以唯一确定一个元组域：属性的取值范围分量：元组中的一个属性值关系模式：对关系的描述,4.数据库,关系的性质,1)关系中每一数据项不可再分，是最基本的单位。2)每一列数据项是同属性的。列数根据需要而设，且各列的顺序是任意的。3)每一行记录由一个事物的诸多属性项构成。记录的顺序可以是任意的。4)一个关系是一张二维表，不允许有相同的字段名，也不允许有相同的记录行。5)每个关系都有称之为关键字的属性集唯一标识各元组。,4.数据库,软件工程把整个软件开发过程视为一项工程，把整个工程分成若干个阶段，制定每个阶段的计划，逐个实施。软件生命周期的六个步骤，即制定计划、需求分析、设计、程序编码、测试及运行维护。,5.软件工程,5.软件工程,软件开发V模型,制定计划确定要开发软件系统的总目标给出功能、性能、可靠性以及接口等方面的要求完成该软件任务的可行性研究估计可利用的资源(硬件、软件、人力等)、成本、效益、开发进度制定出完成开发任务的实施计划，连同可行性研究报告，提交管理部门审查,5.软件工程,需求分析和定义对用户提出的要求进行分析并给出详细的定义编写软件需求说明书或系统功能说明书及初步的系统用户手册评审,5.软件工程,软件设计概要设计把各项需求转换成软件的体系结构。结构中每一组成部分都是意义明确的模块，每个模块都和某些需求相对应。详细设计对每个模块要完成的工作进行具体的描述，为源程序编写打下基础。编写设计说明书，提交评审。,5.软件工程,程序编写(软件实现)把软件设计转换成计算机可以接受的程序代码，即写成以某一种特定程序设计语言表示的“源程序清单”写出的程序应当结构良好、清晰易读，且与设计相一致,5.软件工程,软件测试单元测试，查找各模块在功能和结构上存在的问题并加以纠正集成测试，将已测试过的模块按一定顺序组装起来按规定的各项需求，逐项进行有效性测试，决定已开发的软件是否合格，能否交付用户使用,5.软件工程,运行/维护改正性维护运行中发现了软件中的错误需要修正适应性维护为了适应变化了的软件工作环境，需做适当变更完善性维护为了增强软件的功能需做变更预防性维护“把今天的方法学用于昨天的系统以满足明天的需要”。为进一步改进软件打基础,5.软件工程,基本概念和术语,数据(Data)：在计算机科学中是所有能输入到计算机中并能被计算机程序处理的符号的总称。数据包含的内容随着计算机的发展而扩大例如：数字、字母、汉字、图形、图像、声音都称为数据。注意：专业术语中，数据已经不是“数值”。,6.数据结构、算法、程序,基本概念和术语,数据元素(DataElement)：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。人是一个数据元素，通常作为整体进行处理。数据元素还不是组成数据的最小单位。,6.数据结构、算法、程序,基本概念和术语,数据结构（DataStructures):带结构的数据元素的集合。结构：数据元素之间存在的约束关系数据元素之间不是孤立的，而是相互之间存在着一种或多种特定的关系,6.数据结构、算法、程序,一种数据结构包含下面三个方面：逻辑结构：表示数据元素之间的逻辑关系。Data_Structure=(D,S)物理结构：数据结构在计算机存储器中的映射（或表示），又称存储结构，也称存储表示结构的行为特征作用于数据结构上的运算。例如：检索，插入，删除等。,6.数据结构、算法、程序,逻辑结构,根据数据元素间关系的基本特性，有四种基本数据结构集合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树图形结构多个对多个，如图,6.数据结构、算法、程序,（1）顺序存储（向量存储）以存储位置的相对位置来表示数据元素之间的逻辑关系。,存储结构(storagestructure)：数据结构在计算机中的表示。,要在计算机中实现数据结构的操作，如何在计算机中实现对各种数据及其关系的表示？,6.数据结构、算法、程序,顺序存储,6.数据结构、算法、程序,6.数据结构、算法、程序,(2)链式存储以附加信息（指针）表示数据元素间的逻辑关系所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。,6.数据结构、算法、程序,1536,元素2,1400,元素1,1346,元素3,元素4,1345,h,链式存储,h,6.数据结构、算法、程序,(3)索引存储使用该方法存放元素的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），其中的关键字是能唯一标识一个结点的那些数据项。(4)散列存储通过构造散列函数，用函数的值来确定元素存放的地址。,6.数据结构、算法、程序,数据的逻辑结构,数据的存储结构,数据的运算,线性结构,非线性结构,顺序存储,链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个方面：,：检索、排序、插入、删除、修改等,6.数据结构、算法、程序,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法是指解决问题的一种方法或一个过程。,算法和算法分析,6.数据结构、算法、程序,N.沃思（NiklausWirth)教授提出：程序=算法+数据结构程序设计：为计算机处理问题编制一组指令集算法：怎样处理问题，解决问题的策略数据结构：要处理的信息如何表示，问题的表示模型,6.数据结构、算法、程序,N.沃思（NiklausWirth)教授提出：程序=算法+数据结构以上公式说明了如下两个问题：（1）数据上的算法决定如何构造和组织数据（算法数据结构）。（2）算法的设计依赖于作为基础的数据结构（数据结构算法）。,6.数据结构、算法、程序,算法的5个特性,有穷性：算法必须总是在执行有穷步后结束，每一步在有穷时间内完成。确定性：组成算法的每条指令是清晰，无歧义的。可行性：算法是可执行的。输入：有零个或多个外部提供的量作为输入。输出：算法产生至少一个量作为输出。,6.数据结构、算法、程序,数据结构的主要内容,数学模型解题思路,问题,抽象,数据结构算法,数据类型程序,设计,编码,运行,图计算机解决问题的一般过程,6.数据结构、算法、程序,算法设计的要求1.正确性：算法应当满足具体问题的需求。,正确的含义有4个层次的级别：1、程序不含语法错误；2、程序对于几种输入数据有正确的结果；3、程序对于典型、苛刻、刁难性的数据有正确的结果；4、对于一切合法的输入数据都有正确结果。,6.数据结构、算法、程序,算法设计的要求2.可读性：有助于人对算法的理解。,算法主要是为了人的阅读和交流，晦涩难懂的程序容易隐藏错误，难以调试和修改。,6.数据结构、算法、程序,算法设计的要求3.健壮性：适当处理任何错误输入。,对于输入非法的数据时，算法能够给出反应作出处理，而不会出现莫名奇妙的错误。,6.数据结构、算法、程序,算法设计的要求4.效率和低存储量需求。,效率是指算法执行的时间，执行时间短的算法效率高。存储量需求是指算法执行过程中所需要的最大存储空间，显然是越低越好。,6.数据结构、算法、程序,算法效率的度量,算法的时间代价(或称时间复杂度)执行时间越短，算法效率越高。,6.数据结构、算法、程序,度量算法的执行时间,(1)事后统计法：运行程序后通过若干统计数据来分辨优劣。缺陷：必须先运行依算法编制的程序，一些大型算法要运行则比较费时费力；所得时间的统计量依赖于计算机的硬件、软件等环境因素，容易掩盖算法本身的优劣。,6.数据结构、算法、程序,度量算法的执行时间,(2)事前分析估算法依据的影响因素：依据的算法选用何种策略；问题的规模；书写程序的语言；编译程序时所产生的机器代码的质量；机器执行指令的速度。,6.数据结构、算法、程序,度量算法的执行时间,(2)事前分析估算法分析方法：找出算法中最重要的操作基本操作，计算它们的运行次数。基本操作通常是算法最内层循环中最费时的操作,6.数据结构、算法、程序,时间复杂度一般情况下，算法中基本操作重复执行次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n)它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。称做算法的渐近时间复杂度（asymptotictimecomplexity),简称时间复杂度。,6.数据结构、算法、程序,时间复杂度的意义反映了随着问题规模的增加，算法消耗时间的增加度。,问题规模增加,执行时间增长快,执行时间增长慢,算法效率低,算法效率高,6.数据结构、算法、程序,算法A：inti,sum=0,n=100;for(i=1;i=n;i+)sum=sum+i;printf(“%d”,sum);,算法B：intsum=0,n=100;sum=(1+n)*n/2;printf(“%d”,sum);,哪个算法效率更高？,6.数据结构、算法、程序,由于时间复杂度考虑的只是问题规模n的增长率，则在难以精确计算基本操作执行次数的情况下，只需求出它关于n的增长率或阶即可。,f(n)=3n2+n,6.数据结构、算法、程序,for(i=0;in;i+)S(i);,for(i=0;in;i+)for(j=0;jn;j+)S(i,j);,f(n)=n，时间复杂度为O(n),f(n)=n2，时间复杂度为O(n2),S(i);,f(n)=1，时间复杂度为O(1),6.数据结构、算法、程序,例：NXN矩阵相乘for(i=1;i=n;i+)for(j=1;j=n;j+)cij=0;for(k=1;k10i=i+1elsei=i-1endif,分类,机器语言,汇编语言,高级语言,（2）语言处理程序,6.数据结构、算法、程序,C语言的发展及其特点,运算符丰富。有34种运算符把括号、赋值、强制类型转换等都作为运算符处理表达式类型多样化,6.数据结构、算法、程序,C语言的发展及其特点,数据类型丰富。包括:整型、浮点型、字符型、数组类型、指针类型、结构体类型、共用体类型；C99又扩充了复数浮点类型、超长整型(longlong)、布尔类型(bool)；指针类型数据，能用来实现各种复杂的数据结构(如链表、树、