北京大学《计算概论》课件：ch

北京大学《计算概论》IntroductiontoComputation—信息科学技术学院·理科基础课程Contents课程目录北京大学《计算概论》核心知识体系与学习路径概览。01计算机基础认知02算法与数据结构03程序设计语言基础04控制流程与函数05高级编程技术06面向对象程序设计CHAPTER01计算机基础认知从发展历程到硬件组成，建立对计算机系统的整体认知Chapter01·计算概论计算机发展历程计算机的发展经历了从机械计算到电子计算、从大型机到个人电脑、从单机到互联网的四大阶段演进，每一次跨越都深刻改变了人类处理信息的方式。ENIAC—1946年世界上第一台通用电子计算机01机械计算时代：从算盘到巴贝奇差分机，人类开始探索用机械装置替代人工计算，奠定了自动化计算的思想基础。MechanicalEra02电子计算机诞生：1946年ENIAC问世标志着电子计算时代到来，占地170平方米、重30吨，但运算速度实现质的飞跃。1946·ENIAC03个人计算机兴起：20世纪80年代苹果与IBM推动PC普及，计算机从科研机构和大型企业走入普通家庭和办公室。1980s·PCEra04互联网时代：全球信息互联互通，云计算与移动计算兴起，计算机从独立工具演化为社会基础设施的核心组成。InternetAgeHardwareArchitecture计算机硬件组成总览现代计算机硬件由CPU、内存、存储设备和输入输出设备四大核心组件构成，它们通过总线互联、协同工作，共同完成从数据输入到处理再到输出的完整计算流程。中央处理器CPU计算机的"大脑"，负责执行指令和数据处理，运算速度以GHz为单位衡量核心参数包括核心数、线程数和缓存大小，直接影响并行计算和多任务处理能力GHz运算内存RAM临时存储正在运行的程序和数据，读写速度极快但断电即丢失容量通常为8-64GB，是CPU与硬盘之间的高速数据缓冲区8–64GB存储设备硬盘（HDD/SSD）用于长期保存操作系统、软件和用户文件SSD读写速度远超传统机械硬盘，已成为现代计算机的主流配置SSD主流InstructionCycleCPU的工作原理CPU通过"取指-译码-执行-写回"四步循环不断执行指令，这一过程称为指令周期（InstructionCycle），每秒可循环数十亿次，是冯·诺依曼架构计算机运行的核心机制。FETCH取指令CPU从内存的程序计数器指定地址读取下一条待执行指令，送入指令寄存器暂存指令寄存器DECODE译码控制单元解析指令的操作码和地址码，确定需要执行的运算类型及参与运算的数据位置控制单元EXECUTE执行算术逻辑单元（ALU）执行指令指定的操作，如加减乘除运算、逻辑比较或数据搬运ALUWRITE-BACK写回将运算结果写入目标寄存器或内存地址，更新程序状态，准备进入下一个指令周期寄存器/内存Chapter07存储设备层次结构计算机采用多级存储体系来平衡速度、容量与成本：内存速度最快但容量小且易失，硬盘容量大且持久但速度较慢，不同存储介质形成互补的层次结构。常见存储设备特性对比存储设备读写速度典型容量断电保持主要用途内存（RAM）极快（GB/s级）8–64GB否（易失性）临时存储正在运行的程序和数据固态硬盘（SSD）快（数百MB/s）256GB–4TB是（非易失）存储操作系统、软件和用户文件机械硬盘（HDD）较慢（百MB/s）1–16TB是（非易失）大容量数据长期存储与备份光盘（CD/DVD）慢（数MB/s）700MB–8.5GB是（非易失）数据备份、多媒体分发与归档存储设备在速度、容量和持久性上形成互补的层次结构，内存最快但易失，硬盘容量大且持久，光盘便于分发归档HARDWARE·I/O输入与输出设备输入设备将人类指令和数据转化为计算机可处理的电信号，输出设备将计算结果转化为人类可感知的视觉、听觉或物理形式，二者共同构成人机交互的完整通道。输出设备显示器：以视觉形式呈现计算机处理结果，是最核心的输出设备打印机与绘图仪：将数字内容输出为纸质文档或大幅面工程图纸投影仪与音箱：分别用于大屏视觉展示和音频播放，适合演示和多媒体场景输入设备键盘：输入文字、数字和命令的主要设备，是最基础的人机交互工具鼠标：控制光标移动、选择和操作图形界面元素，实现直观的指向式交互麦克风与摄像头：分别用于语音输入、音频录制和图像视频采集，支持多媒体交互CHAPTER02算法与数据结构理解计算的核心——从问题定义到算法设计与效率分析COMPUTINGFUNDAMENTALS程序的基本概念程序是按特定顺序排列的计算机指令序列，具有自动执行、数据处理和可重复使用三大核心特征，它将人类的解题思路转化为计算机可以理解和执行的精确操作步骤。指令序列程序由一系列按特定顺序排列的计算机指令组成，每条指令对应一个基本操作，共同完成复杂任务SEQUENCE自动执行程序一旦加载到内存并启动，计算机便能自动逐条执行指令，无需人工逐步干预AUTO数据处理程序接收输入数据，通过预设的计算逻辑进行处理，最终产生符合预期的输出结果PROCESS可重复使用同一程序可以多次执行并处理不同的输入数据，实现"一次编写、多次使用"的高效复用REUSABLECOMPUTATIONINTRODUCTION算法的概念与特性算法是解决特定问题的明确步骤集合，必须满足有限性、确定性、输入、输出和可行性五大基本特性，是连接问题定义与程序实现的核心桥梁。算法设计五要素问题定义—明确要解决的问题边界和约束条件，是算法设计的起点输入与输出规范—确定算法需要什么数据作为输入、预期产生什么样的输出处理步骤与效率—设计具体的求解步骤，并优化时间和空间执行效率算法五大特性有限性—算法必须在有限步骤内完成，不能陷入无限循环确定性—每个步骤必须有明确无歧义的定义，相同输入必须得到相同输出输入—算法有零个或多个输入，作为运算对象的量输出—算法必须有一个或多个输出，反映对输入数据加工后的结果可行性—算法的每一步都必须是可执行的，能够通过有限次基本运算实现Representation算法的表达方式算法可通过自然语言、流程图、伪代码和程序代码四种方式表达，从自然语言到代码精确度逐步提升、可读性逐步降低，伪代码在精确性与可读性之间取得了最佳平衡。01自然语言用日常语言描述算法步骤，易于理解但可能存在歧义，适合初步沟通和问题概述高可读性精确度较低02流程图用标准图形符号表示算法流程——菱形判断、矩形操作、箭头流向——直观可视化但不适合复杂算法可视化复杂度受限03伪代码结合自然语言和程序设计语言特点，既易读又较为精确，是学术交流和算法教学中最常用的表达方式最佳平衡精确与可读兼顾04程序代码用特定编程语言（如C++、Python）编写，是最精确的表达方式，可直接被编译器转化为可执行程序最高精确度可直接执行COMPLEXITYANALYSIS算法时间复杂度分析时间复杂度用大O表示法衡量算法执行时间随输入规模增长的趋势，从O(1)到O(n²)各级别差异显著，选择合适算法对大规模数据处理性能影响巨大。当输入规模从10增长到1000时，不同复杂度的操作次数差异从数倍扩大到数千倍。O(logn)—对数级增长最平缓，n=1000时仅约10次操作，是二分查找等高效算法的典型复杂度。O(n)—线性增长，操作次数与输入规模成正比，如遍历数组。n=1000时为1000次。O(nlogn)—超线性增长，归并排序等最优比较排序的复杂度。n=1000时达10,000次操作。不同时间复杂度的增长趋势对比X轴：输入规模n·Y轴：相对操作次数Chapter03程序设计语言基础从机器语言到高级语言，掌握编程的基本元素与数据类型PROGRAMMINGLANGUAGES程序设计语言的层次程序设计语言从机器语言到脚本语言经历四个层次的抽象递进，底层语言执行效率高但编写困难，高层语言开发效率高但需要编译器或解释器转译。01底层语言机器语言直接由0和1组成的二进制指令，计算机可直接执行，效率最高但人类几乎无法阅读和编写。BinaryInstructions02底层语言汇编语言用ADD、MOV等助记符表示机器指令，比机器语言更易读，但仍需直接操作硬件寄存器。Mnemonics03高层语言高级语言语法接近自然语言，如C++、Java等，需通过编译器转化为机器码，易学易用且跨平台能力强。Compiled04高层语言脚本语言如Python、JavaScript，通常由解释器逐行执行，适合快速开发和自动化任务，开发效率极高。InterpretedSECTION03·DATATYPES数据类型体系数据类型决定数据的存储方式和可执行操作，基本类型（int/float/char/bool）处理单一值，复合类型（数组/结构体/类）组织复杂数据，合理选择数据类型是高效编程的基础。基本数据类型int整数存储无小数部分的数值，如42、-7，占用4字节内存空间，支持加减乘除等算术运算与大小比较操作float浮点数存储带小数的数值，如3.14、-0.001，精度有限但表示范围大，适用于科学计算与工程测量场景char/bool字符与布尔char存储单个字符如'A'、'#'，bool仅有true/false两种状态，专用于逻辑判断与条件控制流程复合数据类型Array数组同类型数据的有序集合，通过下标索引访问元素，支持一维线性表与多维矩阵结构，便于批量数据处理Struct结构体将不同类型的相关数据组合为整体，如姓名、年龄、成绩组成学生记录，实现数据的逻辑关联与统一管理Class类面向对象编程的核心机制，将数据属性与操作方法封装为独立单元，支持继承、多态与信息隐藏特性Operators基本运算符体系运算符是程序执行计算和逻辑判断的核心工具，算术、关系、逻辑和位运算四类运算符覆盖了从数值计算到条件判断再到底层位操作的完整操作需求。四类基本运算符及其功能运算符类型运算符符号功能说明典型应用算术运算符+-*/%执行基本数学运算，%为取余运算计算平均值、判断奇偶性关系运算符==!=><>=<=比较两个值的大小关系，返回布尔值条件判断、循环终止条件逻辑运算符&&||!组合多个布尔条件进行逻辑运算多条件筛选、复杂业务规则位运算符&|^~<<>>直接对二进制位进行操作权限掩码、性能优化、加密算法四类运算符分别服务于数值计算、条件比较、逻辑组合和底层位操作，是构建程序逻辑的基本工具CHAPTER04控制流程与函数掌握程序执行的四种控制结构与函数模块化编程方法PROGRAMMINGFUNDAMENTALS控制流程语句程序通过顺序、选择、循环和跳转四种控制结构管理执行流程，这四种结构可灵活组合构建任意复杂的程序逻辑，是结构化程序设计的理论基础。SEQUENTIAL顺序结构按语句书写顺序依次执行，是程序的基本执行方式BasicLOOP循环结构for适合已知次数重复，while适合条件驱动，do-while保证至少执行一次3TypesSELECTION选择结构if-else根据条件真假执行不同分支，switch-case根据值匹配对应分支BranchJUMP跳转语句break跳出循环或switch，continue跳过本次迭代，return从函数返回结果ControlFunctions&Procedures函数与过程函数通过将特定功能封装为独立模块实现代码复用，其四要素——定义、函数体、参数传递和返回值——构成了模块化编程的基础框架，显著提升代码可读性和可维护性。函数定义指定函数名、参数列表和返回值类型，如intadd(inta,intb)声明一个接收两个整数并返回整数的函数。intadd(a,b)函数体编写实现具体功能的代码块，是函数的核心逻辑所在，应遵循单一职责原则。单一职责参数传递值传递复制实参副本，不影响原始数据；引用传递直接操作原始数据，适合大规模数据场景。值传递/引用传递返回结果通过return语句将计算结果返回给调用者，无返回值的函数称为过程（void），执行完毕后自动返回。return/voidALGORITHMPARADIGMS递归与经典算法范式递归、贪心算法和动态规划是三种核心算法范式：递归通过函数自调用分解问题，贪心在每步选择局部最优解，动态规划通过保存子问题解避免重复计算，三者各有适用场景。递归Recursion函数调用自身来分解问题，必须设定明确的终止条件（basecase）。典型应用包括阶乘计算、斐波那契数列和树的遍历，是理解分治思想的基础。BaseCase·终止条件贪心Greedy每一步都选择当前最优解，期望通过局部最优达到全局最优。适用于找零钱、活动安排、最小生成树等问题，但需证明贪心选择性质。LocalOptimal·局部最优动态规划DP将复杂问题分解为重叠子问题，通过保存已解决的子问题结果避免重复计算。如背包问题、最长公共子序列，核心在于状态定义与转移方程。OverlappingSub·重叠子问题CHAPTER05高级编程技术掌握数组、字符串处理和文件操作等实用编程技能DATASTRUCTURE数组数据结构数组是连续内存中同类型数据的有序集合，支持O(1)时间的随机访问，一维数组适合线性数据组织，二维数组适合矩阵和表格数据，是构建复杂数据结构的基础。一维数组01声明与初始化如intarr[5]={1,2,3,4,5}，在内存中连续分配5个整数空间，元素地址依次递增02核心操作通过下标arr[i]实现O(1)随机访问，支持遍历、排序和搜索等基础操作03内存特性连续存储带来缓存友好性，但插入删除需要移动大量元素，时间复杂度为O(n)二维数组01表格结构如intmatrix[3][3]声明3×3矩阵，通过matrix[i][j]定位行列元素，内存按行优先存储02典型应用矩阵运算、图像处理、游戏棋盘、动态规划状态表等场景的核心数据结构03多维扩展可扩展至三维及以上，用于表示立体空间数据、RGB图像通道等多维信息STRINGOPERATIONS字符串操作字符串是处理文本数据的基本类型，长度计算、连接、子串提取和比较是四种核心操作，不同编程语言对字符串的底层实现和API设计存在显著差异。长度计算获取字符串包含的字符数，如strlen('Hello')返回5，是遍历和分配内存的基础操作。strlen()连接操作将两个或多个字符串合并为一个新字符串，如'Hello'+'World'→'HelloWorld'。concat子串提取从原字符串中截取指定位置和长度的子序列，如substr(0,4)从'Introduction'中提取'Intr'。substr()比较操作逐字符比较两个字符串的字典序大小关系，返回相等、大于或小于的判断结果，广泛用于排序和搜索。strcmp()FILEOPERATIONS文件读写操作文件操作遵循"打开-读写-定位-关闭"标准流程，需要指定文件名和访问模式，操作完成后必须关闭文件以释放系统资源，是程序持久化数据的基本手段。打开文件指定文件名和打开模式（r只读/w只写/a追加），系统返回文件指针作为后续操作的句柄。正确选择模式是确保数据安全的第一步。读取与写入支持逐字符、逐行或按块读写，可根据需求选择格式化输入输出或二进制方式操作。灵活的读写策略能提升程序处理大文件的效率。移动文件指针通过fseek等函数调整读写位置，实现随机访问文件中的任意数据段。精确定位让文件操作更加高效灵活。关闭文件操作完成后调用fclose释放文件句柄和缓冲区，确保数据写入磁盘并防止资源泄漏。及时关闭是良好的编程习惯。Debugging程序调试与错误处理程序错误分为语法错误、运行时错误和逻辑错误三类，其中逻辑错误最难排查。掌握编译器报错解读、调试器使用和单元测试三种核心调试策略，是编写正确程序的关键实践能力。语法错误违反编程语言语法规则，如缺少分号、括号不匹配，编译器会直接报错并指出大致位置，是最容易修复的错误类型。初学者应养成仔细阅读报错信息的习惯，快速定位问题所在。SyntaxError运行时错误程序编译通过但执行中崩溃，如除以零、数组越界、空指针，需要分析崩溃现场和调用栈来定位问题根源。异常处理机制和防御性编程可有效预防此类错误。RuntimeError逻辑错误程序正常运行但输出结果不符合预期，是最难发现的错误，需要通过打印变量值、单步调试和单元测试逐步排查。算法理解和边界条件分析是避免逻辑错误的关键。LogicError调试策略善用编译器错误信息、利用调试器设置断点和观察变量、编写单元测试验证模块功能、通过代码审查发现潜在问题。系统化的调试方法能显著提升问题解决效率。DebugStrategyChapter06面向对象程序设计理解封装、继承与多态三大核心特性，掌握现代编程范式OBJECT-ORIENTEDPROGRAMMING面向对象三大特性封装、继承与多态是面向对象编程的三大核心特性：封装保护内部数据安全，继承实现代码层级复用，多态支持接口的灵活实现，三者协同构建了可维护、可扩展的软件架构。封装Encapsulation将数据（属性）和方法（函数）捆绑为独立对象，通过访问控制（public/private）隐藏内部实现细节。对外只暴露必要接口，使用者无需了解内部机制，提升代码安全性和可维护性。继承Inheritance子类自动拥有父类的属性和方法，在此基础上扩展新功能或重写已有方法。实现代码层级复用，减少重复代码，建立"一般到特殊"的类型层次体系。多态Polymorphism同一接口可有不同的实现方式，运行时根据对象类型自动调用对应方法。使代码更灵活、更易扩展，新增子类无需修改调用方代码，符合开闭原则。OOPFundamentals类与对象类是定义属性和行为的抽象模板，对象是类的具体实例。类描述"是什么"，对象代表"具体是谁"，二者是抽象与具体的关系，是面向对象编程最基本的概念对。Class类（Class）类是对象的抽象模板，定义了一类事物共有的属性（数据成员）和行为（成员函数）。它规定了对象"应该有什么"和"能做什么"，是创建对象的蓝图。如定义Student类包含name、id、score属性和enroll()、queryGrade()方法，描述"学生"的通用特征与行为能力。抽象模板只定义规范，不分配内存Object对象（Object）对象是类的具体实例，拥有类定义的属性和方法，但各对象的属性值可以不同。每个对象在内存中独立存在，保存自己的状态数据。如studentA和studentB都是Student类的对象，分别有各自的姓名和成绩，独立存储、互不影响，可执行