《计算机科学概论复习》课件

计算机科学概论复习欢迎参加计算机科学概论复习课程！本次课程旨在帮助大家回顾和掌握计算机科学的核心概念，为期末考试做好充分准备我们将系统梳理课程内容，重点讲解难点和易错点，并通过实例分析加深理解希望通过本次复习，大家能够对计算机科学有一个更全面、更深入的认识课程概述课程目标课程内容学习方法全面复习计算机科学概论的核心知识点，主要涵盖计算机系统组成、软件系统、算认真听讲，积极思考，课后及时复习多包括计算机基础、算法与数据结构、数据法设计与分析、常用数据结构、数据库系做练习题，加深理解充分利用网络资源库、网络、安全、人工智能和量子计算等统原理、计算机网络基础、网络安全技术，查阅相关资料如有疑问，及时向老师重点掌握基本概念、原理和方法，提高、人工智能的基本概念和方法以及量子计或同学请教鼓励小组讨论，共同进步分析问题和解决问题的能力，培养计算思算初步等内容维计算机基础知识计算机发展简史计算机系统组成12从算盘到现代计算机，经历了计算机系统由硬件系统和软件机械计算机、电子管计算机、系统组成硬件系统包括中央晶体管计算机和集成电路计算处理器（）、存储器、输CPU机等阶段每一次变革都带来入输出设备等软件系统包括了计算能力的巨大提升，推动操作系统、系统软件和应用软了科技进步和社会发展件数据表示与存储3计算机内部采用二进制表示数据常用的数据表示形式有整数、浮点数、字符等存储器是计算机中存储数据和程序的部件，分为内存和外存硬件组成中央处理器存储器主板CPU是计算机的核心部存储器分为内存和外存主板是计算机的骨架，CPU件，负责执行指令和进内存是直接访问连接、存储器、输CPU CPU行运算的性能指的存储器，速度快但容入输出设备等各个部件CPU标包括主频、核心数和量小外存用于长期存主板的芯片组决定了缓存大小等的架储数据，速度慢但容量计算机的性能和扩展能CPU构分为和两大常用的外存有硬盘力常见的主板接口有CISC RISC种、固态硬盘和盘等、和等U PCIeUSB SATA计算机存储系统存储层次结构计算机存储系统采用层次结构，包括高速缓存、内存、外存等高速缓存速度最快但容量最小，外存速度最慢但容量最大每一层存储器都为上一层提供缓冲，提高系统性能内存管理操作系统负责管理内存的分配和回收常用的内存管理技术有虚拟内存、分页和分段等虚拟内存技术允许程序使用超过实际内存大小的空间磁盘管理操作系统负责管理磁盘的组织和访问常用的磁盘管理技术有文件系统、磁盘调度和磁盘碎片整理等文件系统将磁盘空间组织成文件和目录，方便用户管理数据输入输出设备输入设备1输入设备用于将外部信息输入到计算机中常用的输入设备有键盘、鼠标、扫描仪、摄像头等输入设备将用户的信息转换为计算机能够理解的数字信号输出设备2输出设备用于将计算机内部的信息输出到外部常用的输出设备有显示器、打印机、音箱等输出设备将计算机的数字信号转换为用户能够理解的文字、图像或声音接口I/O3接口是计算机与外部设备之间的桥梁，负责数据传输和控制常I/O用的接口有、和等接口的性能指标包括I/O USBHDMI SATAI/O传输速度和支持的设备类型计算机软件软件开发过程软件开发过程包括需求分析、设计、编软件的分类2码、测试和维护等阶段每个阶段都有其特定的任务和目标软件开发是一个计算机软件分为系统软件和应用软件迭代的过程，需要不断地改进和完善系统软件负责管理和维护计算机系统，1包括操作系统、编译程序和数据库管理软件质量系统等应用软件用于解决特定问题，包括文字处理软件、图像处理软件和游软件质量是衡量软件是否满足用户需求戏等的重要指标软件质量的因素包括功能3性、可靠性、易用性和效率等软件质量保证贯穿于软件开发的整个过程操作系统进程管理进程是计算机中正在运行的程序的实例操作系统负责创建、调度和销毁进程进程管理包括进程同步、1进程通信和死锁处理等内存管理2操作系统负责管理内存的分配和回收常用的内存管理技术有虚拟内存、分页和分段等虚拟内存技术允许程序使用超过实际内存大小的空间文件系统3操作系统负责管理磁盘的组织和访问常用的磁盘管理技术有文件系统、磁盘调度和磁盘碎片整理等文件系统将磁盘空间组织成文件和目录，方便用户管理数据设备管理4操作系统负责管理计算机的输入输出设备设备管理包括设备驱动程序、中断处理和传输等设备驱动程序是操作系统与设备之间的接口DMA系统软件编译程序1编译程序将高级语言程序转换为机器语言程序编译过程包括词法分析、语法分析、语义分析和代码生成等阶段编译程序是软件开发的重要工具链接程序2链接程序将多个目标文件链接成一个可执行文件链接过程包括符号解析和重定位等步骤链接程序是大型软件开发中必不可少的工具调试程序调试程序用于检测和修复程序中的错误调试程序可以单步执3行程序、查看变量的值和设置断点等调试程序是软件开发过程中重要的工具应用软件文字处理软件图像处理软件文字处理软件用于创建、编辑和图像处理软件用于编辑和处理图格式化文本文件常用的文字处像文件常用的图像处理软件有理软件有、、和Microsoft WordAdobe PhotoshopGIMP和等等图像处理软件广Office LibreOfficeWriter Paint.NET文字处理软件是日常办公的重泛应用于设计、摄影和艺术等领要工具域数据库管理软件数据库管理软件用于创建、管理和维护数据库常用的数据库管理软件有、和等数据库管理软件是企业信MySQL Oracle Microsoft SQL Server息管理的重要工具编程语言高级语言低级语言编程范式高级语言是面向程序员的编程语言，易于低级语言是面向计算机的编程语言，包括编程范式是编程风格和方法的集合常用学习和使用常用的高级语言有、汇编语言和机器语言低级语言可以直接的编程范式有面向过程编程、面向对象编C C++、和等高级语言需要通过控制计算机硬件，效率高但难以学习和使程和函数式编程等不同的编程范式适用Java Python编译器或解释器转换为机器语言才能执行用机器语言是计算机唯一能够直接执行于不同的问题和应用场景的语言算法基础算法的定义算法的设计方法12算法是解决特定问题的有限步常用的算法设计方法有分治法骤序列算法必须具有确定性、动态规划、贪心算法和回溯、可行性和有穷性算法可以法等不同的算法设计方法适用自然语言、流程图或伪代码用于不同的问题选择合适的等方式描述算法设计方法可以提高算法的效率算法的表示3算法可以使用自然语言、伪代码或者流程图表示自然语言描述算法简单易懂，但是容易产生歧义伪代码是一种介于自然语言和编程语言之间的描述方式，清晰简洁流程图使用图形符号表示算法的步骤，直观形象算法时间复杂度时间复杂度的定义时间复杂度的计算时间复杂度的比较时间复杂度是衡量算法计算时间复杂度需要分时间复杂度越低，算法执行时间随输入规模增析算法中基本操作的执的效率越高表示O1长的度量时间复杂度行次数基本操作是指常数时间复杂度，效率通常用大记号表示算法中执行次数最多的最高表示平方O On^2常用的时间复杂度有操作时间复杂度通常时间复杂度，效率较低、、取基本操作执行次数的在选择算法时，应尽O1Olog n On、和最高阶项量选择时间复杂度低的On lognOn^2等算法常见算法分析排序算法常用的排序算法有冒泡排序、选择排序、插入排序、快速排序和归并排序等不同的排序算法适用于不同的数据规模和数据特点快速排序和归并排序的平均时间复杂度为，效率较高On logn查找算法常用的查找算法有顺序查找、二分查找和哈希查找等不同的查找算法适用于不同的数据结构和查找条件二分查找的时间复杂度为，效Olog n率较高哈希查找的时间复杂度为，效率最高O1图算法常用的图算法有深度优先搜索、广度优先搜索、最短路径算法和最小生成树算法等图算法广泛应用于网络路由、地图导航和社交网络分析等领域数据结构概述数据结构的定义1数据结构是组织和存储数据的方式数据结构影响算法的效率和程序的性能常用的数据结构有线性表、树和图等选择合适的数据结构可以提高程序的效率数据结构的分类2数据结构分为线性结构和非线性结构线性结构包括线性表、栈和队列等非线性结构包括树和图等不同的数据结构适用于不同的应用场景数据结构的选择3选择数据结构需要考虑数据的特点和操作的需求如果需要频繁查找数据，可以选择哈希表如果需要频繁插入和删除数据，可以选择链表如果需要表示层次关系，可以选择树线性表顺序存储结构顺序存储结构将线性表的数据元素存储在一组连续的存储单元中顺序存储结2构的优点是访问速度快，缺点是插入和线性表的定义删除操作效率低线性表是由个数据元素组成的有限序n1列线性表中的数据元素具有线性关系链式存储结构线性表可以用顺序存储结构或链式存链式存储结构将线性表的数据元素存储储结构实现在一组任意的存储单元中每个数据元素包含一个指向下一个数据元素的指针3链式存储结构的优点是插入和删除操作效率高，缺点是访问速度慢栈和队列栈栈是一种特殊的线性表，只允许在表的一端进行插入和删除操作栈的操作特点是后进先1出（）栈可以用顺序存储结构或链式存储结构实现LIFO队列队列是一种特殊的线性表，只允许在表的一端进行插入操作，在另一端进行删2除操作队列的操作特点是先进先出（）队列可以用顺序存储结构或FIFO链式存储结构实现应用3栈常用于表达式求值、函数调用和递归等场景队列常用于任务调度、消息传递和缓冲区管理等场景树形结构树的定义1树是由个节点组成的有限集合树中的节点具有层次关系树的根节点没有父节点，其余节点都有一个父节n点树可以用来表示层次关系、组织结构和决策过程等二叉树2二叉树是一种特殊的树，每个节点最多有两个子节点二叉树可以用顺序存储结构或链式存储结构实现二叉树常用于搜索、排序和索引等场景树的遍历树的遍历是指按照一定的顺序访问树中的每个节点常用的树3的遍历方式有前序遍历、中序遍历和后序遍历等不同的遍历方式适用于不同的应用场景图论基础图的定义图的分类图的存储图是由顶点和边组成的集合顶点表示图分为有向图和无向图有向图的边具图可以用邻接矩阵或邻接表存储邻接实体，边表示实体之间的关系图可以有方向，无向图的边没有方向图还可矩阵用一个矩阵表示顶点之间的关系，用来表示网络、地图和社交关系等以分为带权图和不带权图带权图的边邻接表用链表表示每个顶点的邻居节点具有权值，不带权图的边没有权值不同的存储方式适用于不同的图和应用场景排序算法冒泡排序快速排序归并排序冒泡排序是一种简单的排序算法它重复快速排序是一种高效的排序算法它使用归并排序是一种分而治之的排序算法它地遍历要排序的列表，比较每对相邻的项分而治之的策略来排序一个列表在这个将列表分成两个相等的部分，分别对它们目，并交换它们的顺序，如果它们的顺序算法中，一个元素作为枢轴被选择，然后进行排序，然后将它们合并成一个排序后错误这个过程会重复进行直到没有再需列表被分割成两个子列表一个包含小于的列表这种递归地分割和合并列表的方要交换，这意味着列表已经排序枢轴的元素，另一个包含大于枢轴的元素法保证了高效的排序这个过程递归地应用于子列表查找算法顺序查找二分查找12顺序查找，也称为线性查找，二分查找是一种高效的查找算是一种最简单的查找算法它法，适用于已排序的列表它通过逐个检查列表中的每个元通过将列表分成两半，并检查素，直到找到匹配的元素或到中间元素来工作如果中间元达列表的末尾为止素是目标值，则查找成功如果目标值小于中间元素，则在左半部分继续查找，否则在右半部分继续查找哈希查找3哈希查找是一种高效的查找算法，它使用哈希函数将键映射到值哈希表是一种数据结构，用于存储键值对通过哈希函数，可以快速地找到与给定键对应的值数据库基础数据库的定义数据库的特点数据库的管理数据库是按照数据结构数据库具有数据共享、数据库管理系统（来组织、存储和管理数数据独立、数据完整性）是用于管理数DBMS据的仓库数据库中的和数据安全等特点数据库的软件系统数据可以被多个用户或据共享是指多个用户或提供数据的存储DBMS应用程序共享数据库应用程序可以同时访问、检索、更新和安全保系统提供数据的存储、数据库中的数据数据护等功能常用的检索、更新和安全保护独立是指数据与应用程有、DBMS MySQL等功能序分离，应用程序的修和OracleMicrosoft改不会影响数据的存储等SQLServer方式数据库系统结构三级模式结构两级映像数据独立性数据库系统采用三级模式结构，包括概念模数据库系统采用两级映像，包括外模式概数据独立性是指数据与应用程序分离的特性/式、外模式和内模式概念模式描述数据库念模式映像和概念模式内模式映像外模逻辑数据独立性是指当概念模式改变时，/的整体结构，外模式描述用户所看到的数据式概念模式映像保证数据的逻辑独立性，外模式可以保持不变物理数据独立性是指/视图，内模式描述数据的物理存储方式概念模式内模式映像保证数据的物理独立当内模式改变时，概念模式可以保持不变/性数据库模型关系模型1关系模型是目前最常用的数据库模型关系模型使用关系（表）来表示数据，关系中的每个列称为属性，每行称为元组关系模型使用关系代数或关系演算来操作数据层次模型2层次模型使用树形结构来表示数据层次模型中的每个节点称为记录，记录之间的关系称为父子关系层次模型的优点是结构清晰，缺点是灵活性差网状模型3网状模型使用网状结构来表示数据网状模型允许一个节点有多个父节点，因此比层次模型更灵活网状模型的缺点是结构复杂，难以维护数据库语言关系代数关系代数是一种用于操作关系的抽象语言关系代数包括选择、投影、并、交SQL

2、差、笛卡尔积和连接等操作关系代（结构化查询语言）是用于操作关SQL数是的基础理论SQL系数据库的标准语言包括数据定SQL1义语言（）、数据操纵语言（关系演算DDL）和数据控制语言（）DML DCL关系演算是另一种用于操作关系的抽象可以用于创建表、插入数据、查询SQL语言关系演算包括元组关系演算和域数据、更新数据和删除数据等关系演算关系演算使用谓词逻辑来描3述查询条件关系演算是的另一种SQL基础理论网络基础知识网络的定义网络是由多个计算机或其他设备通过通信线路连接起来的集合网络可以用于数据传输、资源共1享和信息交换等网络的规模可以从小型局域网到大型互联网网络的分类网络可以分为局域网（）、城域网（）和广域网（）局域网覆盖LAN MANWAN2范围小，传输速度快广域网覆盖范围大，传输速度慢城域网介于局域网和广域网之间网络的拓扑结构常用的网络拓扑结构有星型、环型、总线型和网状型不同的拓扑结构3具有不同的优缺点星型拓扑结构中心化程度高，易于管理，但单点故障风险高网状拓扑结构可靠性高，但成本高参考模型OSI应用层1应用层是参考模型的最高层，提供应用程序与网络之间的接口应用层协议包括、和等应用层协议定义了应用程序之间交换数据的格式和规则OSI HTTPFTP SMTP传输层2传输层提供端到端的可靠数据传输服务传输层协议包括和提供面向连接的可靠传输服务，提供无连接的不可靠传输服务TCP UDPTCP UDP网络层3网络层负责将数据包从源主机路由到目标主机网络层协议包括协议提供无连接的不可靠数据传输服务网络层使用地IP IP IP址来标识主机数据链路层4数据链路层负责将数据帧从一个节点传输到另一个节点数据链路层协议包括以太网和数据链路层使WiFi用地址来标识节点MAC物理层5物理层负责在物理介质上传输比特流物理层协议包括电缆、光纤和无线电物理层定义了物理信号的特性，如电压、频率和调制方式等协议簇TCP/IP协议协议IP TCP协议（网际协议）是协协议（传输控制协议）提供IP TCP/IP TCP议簇的核心协议协议提供无面向连接的可靠数据传输服务IP连接的不可靠数据传输服务协议在数据传输之前建立连IP TCP协议使用地址来标识主机接，在数据传输之后释放连接IPIP协议负责将数据包从源主机路由协议使用序列号来保证数据TCP到目标主机的可靠传输协议UDP协议（用户数据报协议）提供无连接的不可靠数据传输服务协UDP UDP议不需要建立连接，直接发送数据包协议的优点是速度快，缺点是UDP不可靠协议常用于实时应用，如视频会议和在线游戏等UDP网络安全概述安全威胁安全目标安全措施网络安全威胁包括恶意软件、网络攻击和网络安全的目标是保证数据的机密性、完网络安全措施包括防火墙、入侵检测系统数据泄露等恶意软件包括病毒、蠕虫和整性和可用性机密性是指只有授权的人、加密和身份验证等防火墙用于阻止未木马等网络攻击包括拒绝服务攻击、员才能访问数据完整性是指数据不能被经授权的访问入侵检测系统用于检测网注入攻击和跨站脚本攻击等数据泄篡改可用性是指授权的人员可以随时访络攻击加密用于保护数据的机密性身SQL露是指敏感数据被未经授权的人员访问或问数据份验证用于验证用户的身份窃取密码学基础密码学的定义密码学的分类12密码学是研究信息加密和解密密码学分为对称密码和非对称的科学密码学可以用于保护密码对称密码使用相同的密数据的机密性、完整性和身份钥进行加密和解密非对称密验证密码学是网络安全的重码使用不同的密钥进行加密和要基础解密非对称密码的优点是安全性高，缺点是速度慢哈希函数3哈希函数是一种单向函数，用于将任意长度的数据映射到固定长度的哈希值哈希函数具有抗碰撞性，即很难找到两个不同的数据具有相同的哈希值哈希函数常用于数据完整性校验和密码存储常见加密算法AES RSA SHA（高级加密标准）是一种非对称加密（安全散列算法）AES RSASHA是一种对称加密算法，算法，广泛应用于数字是一种哈希函数，用于是目前最常用的加密算签名和密钥交换等领域生成数据的哈希值法之一的优点是的安全性基于大有多个版本，包括AES RSASHA速度快，安全性高数分解的困难性、RSASHA-1SHA-256支持位、的缺点是速度慢和等AES128192SHA-512位和位密钥长度和256SHA-256SHA-比更安全512SHA-1信息安全原则最小权限原则最小权限原则是指用户或应用程序只应被授予完成其任务所需的最小权限最小权限原则可以减少安全风险如果用户或应用程序被攻击，攻击者只能访问其被授予的权限范围内的资源纵深防御原则纵深防御原则是指采用多层安全措施来保护信息系统纵深防御原则可以提高系统的安全性如果攻击者突破了一层安全措施，仍然需要突破其他层安全措施才能访问系统安全意识原则安全意识原则是指提高用户和管理员的安全意识安全意识是网络安全的重要组成部分用户和管理员应该了解常见的安全威胁，并采取相应的安全措施人工智能概论人工智能的定义1人工智能是研究如何使计算机能够像人类一样思考、学习和解决问题的科学人工智能的目标是构建智能系统，能够执行人类智能的任务人工智能的分类2人工智能可以分为强人工智能和弱人工智能强人工智能是指具有与人类一样的智能的系统弱人工智能是指只能执行特定任务的系统，如语音识别和图像识别等人工智能的应用3人工智能广泛应用于各个领域，包括医疗、金融、交通和教育等人工智能可以用于疾病诊断、风险评估、自动驾驶和智能辅导等知识表示产生式表示产生式表示使用规则来表示知识规则由条件和结论组成产生式表示的优点2是模块化和易于理解，缺点是推理效率逻辑表示低逻辑表示使用逻辑语言来表示知识常1用的逻辑语言有一阶谓词逻辑逻辑表语义网络表示示的优点是精确和推理能力强，缺点是语义网络表示使用图形来表示知识语表示复杂知识困难义网络由节点和边组成节点表示概念，边表示概念之间的关系语义网络表3示的优点是直观和易于理解，缺点是推理能力弱机器学习算法监督学习监督学习是指使用带有标签的数据来训练模型常用的监督学习算法有线性回归、逻辑回1归、支持向量机和决策树等监督学习常用于分类和回归问题无监督学习2无监督学习是指使用没有标签的数据来训练模型常用的无监督学习算法有聚类和降维等无监督学习常用于数据分析和模式识别强化学习强化学习是指通过与环境交互来学习最优策略强化学习算法通过3奖励和惩罚来调整模型参数强化学习常用于游戏和机器人控制等领域自然语言处理词法分析1词法分析是指将文本分解成词语的过程词法分析是自然语言处理的基础常用的词法分析工具有和Jieba等NLTK句法分析2句法分析是指分析句子的语法结构的过程句法分析可以用于理解句子的含义常用的句法分析方法有依存句法分析和短语结构句法分析语义分析3语义分析是指理解句子的语义的过程语义分析可以用于机器翻译和问答系统等语义分析需要使用知识库和推理规则计算机视觉图像分类目标检测图像分类是指将图像划分到不同目标检测是指在图像中识别和定的类别常用的图像分类算法有位目标常用的目标检测算法有卷积神经网络图像分类广泛应和等目YOLO FasterR-CNN用于图像搜索和目标识别等领域标检测广泛应用于自动驾驶和视频监控等领域图像分割图像分割是指将图像划分成不同的区域常用的图像分割算法有和FCN U-等图像分割广泛应用于医学图像分析和遥感图像分析等领域Net量子计算机量子比特量子纠缠量子叠加量子比特是量子计算机的基本单位量子量子纠缠是指两个或多个量子比特之间存量子叠加是指一个量子比特可以同时处于比特可以处于和的叠加态量子比特在关联关系量子纠缠可以用于量子通信和的状态量子叠加可以用于并行计0101比传统比特具有更强的计算能力量子比和量子计算量子纠缠是量子计算机的核算量子叠加是量子计算机的核心特性之特使用量子力学原理来实现心特性之一一量子原理基础叠加态量子纠缠12叠加态是量子力学中的一个基量子纠缠是一种特殊的量子现本概念，指的是一个量子系统象，指的是两个或多个量子系可以同时处于多个可能的状态统之间存在着强烈的关联，即例如，一个量子比特可以同使它们在空间上彼此分离当时处于和的状态，这与经测量其中一个系统的状态时，01典比特只能处于或的状态会立即影响到其他系统的状态01不同，无论它们之间的距离有多远量子测量3量子测量是指对量子系统的状态进行观测的过程量子测量会导致量子系统的状态发生坍缩，即从叠加态变为一个确定的状态量子测量是量子力学中一个重要的概念，也是量子计算的基础量子门和量子电路量子门量子电路量子算法量子门是量子电路中的量子电路是由多个量子量子算法是运行在量子基本元件，用于对量子门组成的，用于实现特计算机上的算法量子比特进行操作量子门定的量子算法量子电算法利用量子力学的特可以改变量子比特的状路可以通过改变量子比性，可以解决一些传统态，例如将其从变为特的状态来实现对问题计算机无法解决的问题01，或者将其从叠加态变的求解量子电路的设，或者可以更快地解决为一个确定的状态常计是量子计算中的一个一些传统计算机可以解见的量子门有重要研究方向决的问题著名的量子门、算法有算法和Hadamard CNOTShor门和门等算法等T Grover量子算法算法算法量子模拟算法Shor Grover算法是一种量子算法，用于解决大数算法是一种量子算法，用于在无序量子模拟算法是一种量子算法，用于模拟量Shor Grover分解问题算法的复杂度比传统算法列表中查找目标元素算法的复杂子系统的行为量子模拟算法可以用于研究Shor Grover低得多，可以快速分解大数算法的度比传统算法低得多，可以更快地找到目标材料科学、药物发现和化学反应等领域量Shor出现对密码学产生了重大影响元素算法广泛应用于数据库搜索子模拟算法是量子计算的重要应用方向之一Grover和模式匹配等领域。