大学计算机教程-计算与人工智能导论（第4版）课件 第1-3章 绪论、计算机系统的组成和工作原理、算法和数据结构

第1章绪论1.1计算机概述1.2信息与信息技术1.3计算思维1.4AI发展、研究内容、应用及挑战1.5集成电路简介第1章绪论1.1计算机概述计算机的发展1946.2ENIACABCIASEDVAC电子管计算机晶体管计算机SSI/MSI计算机LSI/VLSI计算机新一代计算机1954TRADIC195x…..1965197120001964IBM360系列机1964DECPDP-8总线1965.摩尔定律…?电子管磁鼓机器语言计算晶体管磁芯高级语言数据处理SSI,MSI半导体存储(SSI,MSI)OS、DBMS计算、处理、工业控制等领域LSI,VLSI半导体存储(LSI,VLSI)开发平台、分布式网络软件等各领域新技术，智能设备1.1计算机概述计算机的特点:速度快、精度高、信息存储&逻辑判断、自动控制、二进制分类按工作原理:数字计算机、模拟计算机按用途：通用计算机、专用计算机按规模：巨型机、小巨型机、大型机、小型机、工作站、个人计算机应用：计算、数据处理、自动控制、计算机辅助、人工智能、通信？1.2信息与信息技术信息概念信息技术：文字

印刷术

电话、广播和电视使用

现代信息技术(计算机+通信)计算机中信息的表示二进制数、八进制数、十六进制数及转换原码、反码和补码字符编码中西文编码：GB2312、GBK、GB18030;ASCII、EBCDIC、UCS字形码图形图像表示声音的处理与表示011010011101……十进制数二进制数转换方法：

整数和小数分开转换整数部分：除以2逆序取余小数部分：乘以2顺序取整例如：29.6875

11101.1011B

注意：十进制小数（如0.63）在转换时会出现二进制无穷小数，这时只能取近似值129371421222200111余数低位高位整数部分小数部分0.6875×21.37500.75001.50001.0000×2×2×2高位低位二进制数十进制数转换方法：二进制数的每一位乘以其相应的权值，然后累加即可得到它的十进制数值例：11101.1011B

=1×24＋1×23＋1×22＋0×21＋1×20

＋1×2－1＋0×2－2＋1×2－3＋1×2－4

=29.6875

【例】（1）二进制数10110110.1010转换为十进制、八进制、十六进制;

（2）十进制数137.625转换为二进制、八进制、十六进制8位二进制代码无符号整数原码补码0000000000000000001111……………………01111111127127127100000001280－12810000001129－1－127……………………11111111255－127－1ASCII码表区位码国标交换码:区位码+32机内码:

国标码+128一级汉字（3755个）二级汉字（3008个）（扩充使用）位号：

………19423字母、数字和各种符号……区号：191655568794GB2312-80字符集88【例】：“大”字的区号20，位号83，区位码是2083

用2个字节表示为：0001010001010011【例】：计、算、机三个字的机内码分别是：

计

BCC6H1011110011000110B

算

CBE3H1100101111100011B

机

BBFAH1011101111111010B1.3计算思维概念：理论思维；实验思维；计算思维特征：人的思维;可由计算机执行;求解问题思想;概念化而非程序化基本方法约简、嵌入、转化和仿真方法递归&并行计算方法抽象思维方法建模思维方法预防、保护及纠错思维方法启发式推理面向海量数据快速计算，在处理能力和存储容量间折中的思维方法1.4人工智能的发展、

研究内容、应用及挑战概念发展学科诞生与初步发展(20世纪50年代至70年代)学科诞生：1956年达特茅斯学院学术研讨会符号主义兴起:20世纪60年代,符号主义学派专家系统技术低谷与重新崛起(20世纪70年代至90年代)第一次寒冬连接主义兴起:连接主义学派神经网络复兴深度学习与应用(2000年至今)深度学习兴起:GeoffreyHinton技术突破:自动驾驶、AlphaGo等大预言模型:GPT、BERT等发展趋势：通用人工智能;智能设备与AI深度融合;生成式AI兴起;AI助手普及;AI立法与伦理;与其他技术融合1.4人工智能的发展、

研究内容、应用及挑战研究内容三要素:算法、算力、数据主要研究内容：知识表示、自动推理、机器学习、自然语言理解、计算机视觉、智能机器人、自动程

序设计、生成式人工智能(AIGC)应用：人脸识别、自动驾驶汽车、机器翻译、智能客服机器人、智能外呼机器人、个性化推荐挑战伦理挑战技术挑战治理挑战社会挑战1.5集成电路简介集成电路发展IC卡智能设备与机器人技术100019701975198019851990199520001000010000010610x106100x10640048008808080868028680386PentiumPentiumIIPentiumIIIPentium4晶体管数8048620101000x106CORE2DuoCORE2QuadCOREi7计算机发展、特点及分类信息概念及表达计算思维人工智能概念、发展、研究内容、应用与挑战集成电路简介本章小结第2章计算机系统的组成和工作原理2.1计算机系统的基本组成2.2微型计算机系统的组成2.3计算机软件2.4计算机的工作原理2.1计算机系统的基本组成计算机系统硬件软件中央处理器(CPU)：运算器、控制器等连线及控制：主板等内存：主存RAM、BIOSROM、缓存Cache等主机外设外存:磁盘、闪盘、光盘等输入设备:鼠标、键盘、摄像头、麦克风等输出设备:显示器、打印机等系统软件应用软件操作系统：Windows、UNIX、Linux、iOS、AndroidOS等语言处理系统:C++、Java、Python等语言翻译系统数据库管理系统：Oracle、SQLite等系统工具:诊断工具、整理工具等Word、Excel、QQ等计算机系统层次结构图器件与电路功能部件(运算器、控制器、存储器、输入设备、输出设备)指令集结构(ISA)应用软件语言处理系统数据库管理系统系统工具计算机硬件体系结构

操作系统/虚拟机软件硬件（程序+数据+文档）（物理装置总称）计算机的逻辑组成：冯.诺依曼结构运算器+控制器+存储器+输入设备+输出设备用二进制数表示指令和数据用“存储程序控制”工作方式输入设备输出设备存储器运算器控制器数据流控制流典型的冯·诺依曼计算机结构2.2微型计算机系统的组成输入输出设备CPU内存条（主存）主板（总线）硬盘（外存）电源微型计算机的主板(总线)PCI-E总线插槽I/O接口插座内存条插槽CPU插座硬磁盘键盘鼠标光盘闪盘网线音箱麦克风

CPUUSB控制器外存控制器CPU总线接口部件运算器(ALU)控制器声卡网卡寄存器堆处理器总线PCI-E扩展槽显示器

主机南桥芯片北桥芯片显卡DMI总线PCI-E芯片组主存储器存储器总线I/O总线打印机外设外设操作码地址码指令的格式中央处理器(CPU)构成：控制器,运算器(ALU),寄存器,接口部件指令系统RISC:Power,SPAC,CRISP,AMD29000,ARM等CISC:x86,x86-64CPU接口部件指令cache数据cache程序计数器PC指令寄存器IR译码器……控制信号寄存器堆ALU数据或地址指令地址码操作码地址线数据线地址下址逻辑控制器时钟脉冲intel酷睿i9CPU及插座内存存储器的层次结构寄存器&高速缓存(cache)主存概念:存储单元,地址容量:KB,MB,GB,TB等开机内存：BIOSROM&CMOS存储器;UEFI内存外存寄存器（SRAM）高速缓冲cache（SRAM）主存储器（DRAM、ROM）辅助存储器（磁盘、光盘、闪盘）后备存储器（磁带机、磁盘阵列等）CPU及接口内主机速度容量位价格快小高慢大低微型计算机的层次化存储结构外设内存条和内存条插槽10010010100110111101001010110011……1001011100000000000000010000001000000011……11111111地址存储单元数据内容主存储器地址与存储单元字选择线W位线D1位线D0VccT5T6T1T2T3T4数据线(位线)地址线（字选择）总线与I/O接口微机主板组成芯片组：南北桥芯片组;PCH单芯片总线(插槽)：CPU插座,内存插槽,PCI-E插槽（PCI，PCI-Exn）性能:总线带宽＝总线位宽×总线工作频率×传输次数I/O接口：I/O控制器+I/O插座I/O控制卡显卡:GPU+显存+接口部件网卡声卡:DSP,AD转换器,电子合成器,混音器,接口部件等集成I/O接口USB接口PS/2接口,SATA接口视频接口VGA、HDMI、DVI、DP网络RJ-45接口音频接口(开机内存)PS/2DVIVGAUSB2.0HDMIRJ45音频接口USB3.0主板上的SATA接口PCI-E总线插槽I/O接口插座内存条插槽CPU插座硬磁盘键盘鼠标光盘闪盘

CPUUSB控制器外存控制器CPU总线接口部件运算器(ALU)控制器寄存器堆PCI-E扩展槽PCH显卡DMI主存I/O总线打印机显示核心、PCI-E控制器、内存控制器PCI-E存储器总线显示器主板总线&接口中央处理器内存储器系统总线I/O控制器外存储器输出设备输入设备I/O控制器I/O控制器I/O插座I/O插座外存储器接口主机外设微型计算机的外部设备外部输入设备键盘:USB接口,PS/2接口鼠标:dpi/cpi扫描仪、摄像头、数码相机和数码摄相机:CCD,CMOS触摸屏等其他传感器外部输出设备显示器打印机外部存储设备磁盘闪盘光盘感光器件CCD和CMOS3D鼠标被测信号被测信号被测信号传感器……传感器预处理微处理机微处理器存储器接口外部信号智能传感器组成3D打印机读写磁头磁盘盘片传动手臂传动轴主轴扇区磁道柱面闪存颗粒结构

浮栅层控制栅绝缘层隧穿层--------SD针式打印机激光打印机喷墨打印机微型计算机的主要性能指标运算速度(MIPS,MFLOPS)吞吐率执行时间:主频,CPI,外频,cache容量,内核架构字长内存储器容量外存储器容量外设及软件配置2.3计算机软件软件分类系统软件:操作系统、语言处理系统、数据库管理系统、系统工具应用软件:办公多媒体软件、通讯软件、存储软件、AI软件操作系统作用:管理软硬件资源,提供应用程序接口,提供友好人机界面功能处理器管理(任务管理):带优先级时间片轮转内存管理:虚拟内存文件管理(外存管理):多层文件夹设备管理:轮询,中断,DMA常见操作系统:DOS,Windows,Unix,Linux,macOS,iOS,HarmonyOS等

裸机操作系统语言处理系统数据库管理系统系统工具应用软件多层次计算机系统结构虚拟内存（pagefile.sys）虚拟空间2虚拟空间1物理内存程序设计语言分类机器语言汇编语言高级语言:Fortran,BASIC,Pascal,C/C++,C#,Java,Python程序语言处理系统:解释,汇编程序语言构成…,EXTop=1,ALUSelA=1,ALUSelB=11,ALUop=add,IorD=1,Read,MemtoReg=1,RegWr=1,temp=v[k];v[k]=v[k+1];v[k+1]=temp;lw$15,0($2)lw$16,4($2)sw$16,0($2)sw$15,4($2)10001100010011110000000000000000100011000101000000000000000001001010110001010000000000000000000010101100010011110000000000000100软件硬件高级语言程序汇编语言程序机器语言程序编译汇编指令集(InstructionSetArchitecture,ISA)机器解释控制信号编译程序操作系统应用程序指令集结构ISA最终用户应用程序员系统管理员系统程序员汇编程序CPU+主存+I/O数字设计电路设计应用软件办公软件：MicrosoftOffice、WPSoffice、GoogleDocs、CajViewer、AdobeReader等图像处理软件:AdobePhotoshop、GIMP、美图秀秀等图形动画软件:AutoCAD、CorelDraw、Flash、3DMax、Maya、即梦AI等。视频处理软件:AdobePremiere、会声会影、QuickTime、RealPlayer、暴风影音、MediaPlayer、可灵AI等。音频处理软件:CoolEdit、AdobeAudition、Audacity等通信社交软件:QQ、微信、腾讯会议、钉钉、Facebook、Twitter、YouTube、IE、Chrome、Safari等网络存储软件:百度网盘、腾讯微云、iCloud、阿里云盘等2.4计算机工作原理存储程序和程序控制的思想存储程序程序控制指令和指令系统指令格式:操作码+操作数地址指令种类:控制、传送、处理、I/O、其他指令系统分类累加器型、栈型、通用寄存器型、Load/Store型CISC、RISC指令的执行过程操作码02H地址5B1A0HPCIR译码器通用寄存器0000001CH

………………016C6820H……001CH…………00120025H……0020H……01A0H……内存代码区数据区ALU控制信号下址计算总线①③

④

⑤②

CPU取指段译码段取数段执行段写回段指令1取指段译码段取数段执行段写回段指令2取指段译码段取数段执行段写回段指令3执行时间

每一种CPU都有它自己认识的一套指令，含义事先约定。该CPU的指令系统操作码操作数地址ADD$2$4如：一条指令0110000010000100数据所在的地址“hello”Red：shell命令行处理Blue：可执行文件加载Cyan：hello程序执行过程“hello”“hello,world/n”“hello,world\n”所有过程都是在CPU执行指令所产生的控制信号的作用下进行的。unix>./hellohello,worldunix>[Enter]程序的执行过程指令的执行过程流水线技术Pentium处理器中以双流水线方式执行指令的过程本章小结计算机系统的基本组成微型计算机系统的组成计算机软件计算机的工作原理第3章算法和数据结构3.1算法的相关概念3.2穷举算法3.3查找算法3.4排序算法3.5递归算法3.6数据结构3.1算法的相关概念算法概念：算法&程序算法特点:确定性、有穷性、可行性、输入、输出算法性能:正确性、可读性、健壮性、时间复杂度、空间复杂度算法描述自然语言描述流程图描述伪代码描述程序设计语言描述起始或结束处理输入或输出判断连接点预定义过程不同的执行方向语句1语句2语句3三种基本结构的流程图描述条件语句1语句2YN条件语句1语句2NYa.顺序结构b.分支结构b.循环结构第1步：将数值1给变量t。第2步：将数值2给变量i。第3步：使变量t和变量i相乘，将结果存放到变量t中。第4步：将变量i的值加1。第5步：如果变量i的值不大于6，则重新执行第3步到第5步。如果变量i的值大于6，则算法结束。6!算法自然语言描述计算6!算法的流程图描述开始1=>ti>62=>it*i=>ti+1=>i结束Y输出tNBegin1=>t2=>iDo{t*i=>t;i+1=>i}untili>6;PrinttEnd

计算6!算法的伪代码描述#include"stdio.h"intmain(){ inti,t; t=1; i=2; do{

t=t*i;

i=i+1;

}while(i<=6); printf("t=%d",t);}计算6!的C语言程序3.2穷举算法算法思想步骤确定枚举对象及范围明确问题解答具体要求罗列所有可能的情况，逐一求解筛选答案，直到找到所有解常见的穷举算法：顺序、排列、组合例鸡兔同笼是在1500年前《孙子算经》中提出的数学问题：“今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？”。其大意是：有若干只鸡兔同在一个笼子里，从上面数，有35个头，从下面数，有94只脚。问笼中各有多少只鸡和多少只兔？开始1=>aa>3535-a=>ba*2+b*4=94输出a,ba+1=>a结束YYNN鸡兔同笼穷举算法流程图Step1:初始化鸡的数量1=>a。Step2:判断鸡的数量a是否大于35，若大于35转Step7。Step3:计算兔的数量35-a=>b。Step4:计算腿的数量a*2+b*4=9是否成立，若不成立，转Step6。Step5:输出鸡和兔的数量a和b。Step6:更新鸡的数量a+1=>a。转Step2。Step7:算法结束。例输入一个大于2的整数，判断其是否为质数。用穷举法求解算法用自然语言描述如下。Step1:输入数据到n。Step2:初始化数据2=>i。Step3:判断i是否等于n。若是，则转Step6。Step4:判断n除i的余数是否为0。若是，转Step6。Step5:更新数据i+1=>i，转Step3。Step6:判断i是否等于n。若是，输出“n是质数”，否则输出“n不是质数”。Step7:程序结束。开始i=n?N除i余数为0?输出”该数不是质数”i+1=>i结束YYNN输出”该数是质数”输入数到ni=n？YN质数判断穷举算法流程图3.3查找算法算法思想步骤顺序查找步骤从待查找序列中顺序选择一个元素，比较目标与当前元素如果相等，则查找成功，返回元素位置如果不相等，继续查找，直到找到目标或遍历完整个序列二分查找步骤：有序序列中查找①初始化：0=>low,len-1=>high②如果low>high，转⑤③mid=(low+high)/2④比较mid位置元素a[mid]与目标k。若k=a[mid]，返回mid，查找成功。若k>a[mid],mid+1=>low。

若k<a[mid],mid-1=>high。转②。⑤查找失败，返回失败标记-1。例在有序数组A=[9，11，18，21，25，31，45，55，68]中查找数字33的位置并输出。若找不到，输出“该元素找不到”。911182125314555689111821253145556891118212531455568leftmidrightleftrightmidleftrightmid91118212531455568leftright二分查找算法查找目标元素过程开始Low>high?33=A[mid]?找到，输出mid0=>low,8=>high结束YYNN输出”未找到目标”33>A[mid]?(low+high)/2=>midmid+1=>lowmid-1=>highNY3.4排序算法冒泡排序算法思想步骤初始化待排序序列为整个数组。按从前往后的顺序，将待排序序列中相邻两元素两两进行比较，若前面元素大于后面元素则交换相邻两元素的位置。缩小待排序范围，将当前待排序序列最后一个元素剔除。重复步骤②直到待排序序列只包含1个元素。例:用冒泡排序算法对数组A=[5,7,8,9,3,1]进行升序排序。A[0]A[1]A[2]A[3]A[4]A[5]578931578931578931578931578391578319(a)第1轮比较A[0]A[1]A[2]A[3]A[4]A[5]578319578319578319573819573189(b)第2轮比较A[0]A[1]A[2]A[3]A[4]A[5]573189573189537189531789(c)第3轮比较A[0]A[1]A[2]A[3]A[4]A[5]531789351789315789(d)第4轮比较A[0]A[1]A[2]A[3]A[4]A[5]315789135789(e)第5轮比较图3-17冒泡排序过程示意图Step1:初始化0=>i。Step2:判断i是否小于5。若否，则转Step9。Step3:初始化0=>j。Step4:判断j是否小于5-i。若否，则转Step8。Step5:判断A[j]是否大于A[j+1]。若否，则转Step7。Step6:交换A[j]和A[j+1]，即A[j]=>tmp,A[j+1]=>A[j],tmp=>A[j+1]。Step7:j+1=>i。转Step4。Step8:i+1=>i。转Step2。Step9:算法结束。选择排序算法思想步骤初始化当前交换位置为待排序序列第一个元素位置。在剩余待排序元素中，选择最小元素，与当前交换位置元素交换。排除已排序元素，重复步骤②，直到所有元素都被排序。例:用选择排序算法对数组A=[5,7,8,9,3,1]进行升序排序。578910311789103513891075min13591078第1次交换选择排序算法排序过程第2次交换第3次交换第4次交换iiminiminimin1357109813578910第5次交换第6次交换iiminminStep1:初始化待排序序列首元素位置0=>i和元素个数7=>n。Step2:判断i是否小于n-1。若否，转Step9。Step3:初始化待排序最小元素位置i=>min和当前位置i+1=>j。Step4:判断j是否小于n。若否，转Step7。Step5:判断A[min]是否大于A[j]。若是，则j=>min。Step6:j+1=>j，转Step4。Step7:交换A[min]和A[i]，即A[min]=>tmp，A[i]=>A[min]，tmp=>A[i]。Step8:i+1=>i，转Step2。Step9:算法结束。插入排序算法思想步骤初始化将待排序序列的第一个元素作为有序序列。选择待排序序列第一个元素，将其插入到有序序列中。缩小待排序序列范围，重复步骤②直到完成所有元素插入。例:用插入排序算法对数组A=[5,7,8,9,3,1]进行升序排序。578931A[0]A[1]A[2]A[3]A[4]A[5](a)第1次插入d=7(b)第2次插入A[0]A[1]A[2]A[3]A[4]A[5]578931d=8578931A[0]A[1]A[2]A[3]A[4]A[5]d=9(c)第3次插入插入排序过程示意图A[0]A[1]A[2]A[3]A[4]A[5]578931578991578891577891(d)第4次插入557891d=3357891A[0]A[1]A[2]A[3]A[4]A[5]357891357899357889357789(e)第5次插入355789d=1335789135789Step1:6=>n，0=>i。Step2:若i=n-1，转Step7。Step3:A[i+1]=>d,i=>j。Step4:若d>=A[j]或j<0，转Step6。Step5:A[j]=>A[j+1]，j-1=>j，转Step4。Step6:d=>A[j+1]，i+1=>i，转Step2。Step7:算法结束。3.5递归算法算法思想递推算法步骤确定递推的变量；建立递推关系式；确定递推的初始（边界）条件；明确递推终止的条件，控制递推过程，实现问题求解;递归算法步骤确定递归对象；建立递归关系式；明确递归终止条件，控制递归过程，实现问题求解;例：如果每对兔子（一雄一雌）每月能生一对小兔子（也是一雄一雌，下同），每对兔子第一个月没有生殖能力，但从第二个月以后便能每月生一对小兔子。假设这些兔子都没有死亡现象，那么从第一对刚出生的兔子开始，12个月以后会有多少对兔子？

用递推算法求解斐波那契数列问题的自然语言描述如下。Step1:设置初始条件1=>F1,1=>F2，3=>n。Step2:若n>12，转Step4。Step2:根据递推公式计算F=F1+F2。Step3:n+1=>n，F2=>F1，F=>F2，转Step2。Step4:输出F。Step5:算法结束。开始1=>F1,1=>F2,3=>nn>12?F1+F2=>F输出Fn+1=>n结束YN用递归算法求解斐波那契数列问题的自然语言描述如下。Step1:定义斐波那契数列问题求解过程F，参