《计算机科学基础》课件

计算机科学基础探索计算机科学的核心概念和基础知识课程目标与学习成果掌握计算机科学基础理论培养算法思维与问题解决能力了解软硬件系统工作原理计算机科学的历史发展1机械计算时代算盘、帕斯卡计算器2电子计算机诞生ENIAC(1946年)3个人计算机革命AppleII、IBMPC4互联网与移动时代计算机系统的基本组成硬件系统CPU、内存、存储、输入输出设备系统软件操作系统、编译器、驱动程序应用软件办公软件、浏览器、专业工具数据硬件系统：中央处理器（CPU）控制单元指令解码与执行控制1算术逻辑单元数学计算与逻辑运算2寄存器组暂存数据与指令3缓存加速数据访问硬件系统：存储器1寄存器最快、容量最小2缓存高速、小容量3主存(RAM)中速、易失性4辅存(硬盘/SSD)硬件系统：输入输出设备输入设备键盘、鼠标、触摸屏、麦克风输出设备显示器、打印机、扬声器通用设备软件系统：操作系统概述进程管理任务调度与资源分配内存管理分配、回收、虚拟内存文件系统数据组织与存储用户界面软件系统：应用软件生产力工具文档处理、电子表格多媒体软件图像处理、视频剪辑专业应用数据表示：二进制系统1计算机中的基本数据单位只使用0和1两个数字2位(bit)与字节(byte)8位=1字节3二进制加法0+0=0,0+1=1,1+1=10所有数据最终都转为二进制数据表示：其他进制及转换二进制八进制十进制十六进制00001111102221133310044410101210A10000201610数据表示：ASCII码和UnicodeASCII7位编码，表示128个字符主要用于英文字符Unicode统一字符编码支持世界上几乎所有文字UTF-8Unicode的变长编码方式网络传输中最常用布尔代数与逻辑门1基本逻辑运算与(AND)、或(OR)、非(NOT)2复合逻辑门与非(NAND)、或非(NOR)、异或(XOR)3组合电路加法器、编码器、解码器4时序电路触发器、计数器、寄存器计算机网络基础1234局域网(LAN)连接邻近区域的计算机广域网(WAN)跨地理区域的网络互联网全球计算机网络互联系统网络协议通信规则与标准网络协议：TCP/IP1应用层HTTP、FTP、SMTP2传输层TCP、UDP3网络层IP、ICMP、路由4链路层以太网、WiFi、ARP互联网与万维网浏览器网页内容渲染与展示HTML网页内容结构标记CSS网页样式与布局JavaScript网页交互功能实现信息安全基础机密性保护信息不被未授权访问完整性确保信息未被篡改可用性确保系统服务正常提供认证与授权身份验证与权限管理密码学简介对称加密使用相同密钥加解密AES、DES非对称加密公钥加密，私钥解密RSA、ECC哈希函数单向映射，不可逆MD5、SHA算法概念与特性1定义解决问题的明确步骤序列2输入与输出有明确的输入和预期输出3确定性相同输入产生相同输出4有穷性在有限步骤内结束基本算法设计技巧分治法将问题分解为子问题贪心算法每步选择当前最优解动态规划存储子问题解以避免重复计算回溯法尝试所有可能，遇到死路返回时间复杂度与空间复杂度问题规模(n)O(1)O(logn)O(n)O(n²)排序算法算法名称平均时间复杂度最坏时间复杂度空间复杂度冒泡排序O(n²)O(n²)O(1)选择排序O(n²)O(n²)O(1)插入排序O(n²)O(n²)O(1)快速排序O(nlogn)O(n²)O(logn)归并排序O(nlogn)O(nlogn)O(n)堆排序O(nlogn)O(nlogn)O(1)搜索算法顺序搜索从头到尾依次比较时间复杂度O(n)二分搜索要求数据已排序时间复杂度O(logn)哈希搜索利用哈希函数直接定位平均时间复杂度O(1)数据结构：数组与链表数组连续内存空间随机访问O(1)插入删除O(n)链表非连续内存空间随机访问O(n)插入删除O(1)数据结构：栈与队列栈后进先出(LIFO)只能在顶端操作应用：函数调用、表达式求值队列先进先出(FIFO)一端入队一端出队应用：任务调度、缓冲区数据结构：树二叉树每个节点最多两个子节点二叉搜索树左子树小于根，右子树大于根平衡树左右子树高度差不超过1数据结构：图有向图边有方向性无向图边无方向性加权图边有权重值数据结构：哈希表键值待存储数据的标识哈希函数将键映射到数组索引数组存储快速查找与修改冲突解决链表法或开放寻址法程序设计基础问题分析理解需求与约束1算法设计确定解决问题的步骤2代码实现用编程语言表达算法3测试调试验证结果并修复问题4高级程序设计语言概述编译型语言C/C++、Java一次编译多次运行解释型语言Python、JavaScript边解释边执行混合型C#、Java编译为中间代码再解释面向对象程序设计1类与对象类是对象的模板，对象是类的实例2封装隐藏实现细节，提供公共接口3继承子类继承父类的属性和方法4多态同一接口，不同的实现方式函数式程序设计纯函数相同输入产生相同输出，无副作用不可变数据数据创建后不可修改高阶函数函数可作为参数和返回值递归而非循环通过递归实现迭代操作数据库系统概述数据库管理系统数据的组织、存储与管理查询语言用于访问和操作数据事务管理保证数据完整性安全机制控制用户访问权限关系数据库模型表(Table)行和列组成的二维结构键(Key)主键、外键、唯一键关系(Relationship)表与表之间的连接SQL语言基础数据定义CREATE、ALTER、DROP创建和修改数据库结构数据操作SELECT、INSERT、UPDATE、DELETE查询和修改数据内容数据控制GRANT、REVOKE控制用户对数据的访问权限操作系统：进程管理进程创建分配资源与PCB1进程调度决定CPU分配顺序2进程通信共享内存与消息传递3进程终止释放资源4操作系统：内存管理物理内存实际的RAM硬件资源虚拟内存程序看到的连续地址空间页面置换内存与硬盘间数据交换内存保护进程间隔离，防止非法访问操作系统：文件系统1文件组织目录结构、文件属性2文件操作创建、读写、删除3存储分配连续分配、链接、索引4文件共享多用户访问控制编译原理概述源代码高级语言程序编译器翻译器目标代码机器语言或中间代码执行结果程序运行输出词法分析与语法分析词法分析将源程序转换为记号流识别标识符、关键字、常量语法分析根据语法规则构建语法树检查程序结构正确性代码优化与目标代码生成中间代码生成独立于特定机器的表示代码优化提高执行效率，减少资源消耗目标代码生成转换为特定机器的指令集人工智能导论知识表示如何存储和组织知识1推理系统从已知推导出新结论2机器学习从数据中学习模式3自然语言处理理解和生成人类语言4计算机视觉理解图像和视频内容5机器学习基础监督学习有标签数据训练分类、回归无监督学习无标签数据发现模式聚类、降维强化学习通过奖惩机制学习策略决策控制深度学习简介输入层接收原始数据隐藏层多层非线性变换输出层生成预测结果计算机图形学基础几何建模创建三维物体几何表示渲染生成逼真图像动画创建物体运动效果交互技术实时响应用户操作虚拟现实与增强现实虚拟现实(VR)完全沉浸式数字环境头戴式显示器增强现实(AR)在现实世界叠加虚拟内容智能手机、AR眼镜混合现实(MR)现实与虚拟世界融合虚拟物体与现实交互并行计算与分布式系统并行计算多处理器同时执行计算任务共享内存模型分布式系统多台独立计算机协同工作通过网络通信云计算技术1软件即服务(SaaS)应用软件服务2平台即服务(PaaS)开发平台服务3基础设施即服务(IaaS)计算资源服务大数据处理技术大数据特点：容量数据规模巨大大数据特点：速度数据产生和处理速度快大数据特点：多样性结构化和非结构化数据大数据特点：价值从数据中挖掘有用信息物联网概述感知层传感器数据采集1网络层数据传输与通信2处理层数据存储与计算3应用层智能服务与控制4软件工程基础1需求工程识别和定义用户需求2系统设计架构与模块划分3编码实现按设计规范编写代码4测试验证发现并修复缺陷软件开发生命周期需求分析确定系统功能与约束系统设计划分模块与确定接口编码实现编写代码与单元测试系统测试集成测试与验收测试运维支持部署维护与升级更新敏捷开发方法用户故事简洁的功能需求描述1迭代开发小周期、快速交付2持续集成频繁合并代码和测试3团队协作自组织团队，紧密沟通4计算机伦理与职业道德数据隐私保护用户个人信息知识产权尊重软件著作权系统安全防范恶意利用社会责任考虑技术的社会影响开源软件与知识产权开源许可证GPL、BSD、MIT不同程度的使用限制商业软件版权保护使用需付费授权软件专利保护创新算法和技术独占权利计算思维分解将复杂问题拆分为小问题模式识别发现问题中的共性抽象提取关键特征，忽略细节算法设计设计解决问题的步骤计算机科学前沿技术前沿技术正在改变世界量子计算简介1量子比特可同时表示0和1的叠加态2量子纠缠量子位之间的关联关系3量子算法Shor算法、Grover算法4应用