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

PekingUniversity北京大学《计算概论》IntroductiontoComputation—理科计算机基础教育核心课程Contents课程目录北京大学《计算概论》核心模块与知识脉络概览。01课程概述与计算思维02计算机系统基础03程序设计基础04算法与数据结构CHAPTER01课程概述与计算思维了解课程定位、教学理念与计算思维的核心方法论COURSEOVERVIEW课程定位与概况《计算概论》是北大覆盖面最广的理科计算机基础课，年选课超2000人，以"立足基础、因材施教、强化实践"为教学理念，构建了从理论到实践的多层次教学体系，是北大理科本科生计算机教育的基石。北京大学信息科学技术学院教学楼01覆盖最广的主干基础课：面向全校理学、工学、医学一年级学生开设，是信息科学技术学院选课人数最多的课程，年选课规模超2000人02三位一体教学理念：经过许卓群、代亚非等教师十余年建设，形成"立足基础、因材施教、强化实践"的教学体系03分层次因材施教：A类面向电子信息科学类专业，深度更大；B类面向其他理科专业，注重通识应用04多层次实践环境：以北大网络教学平台为基础，依托国家级计算机实验教学示范中心，构建开放的教学与实验环境TeachingSystem因材施教的分层教学体系课程根据学生专业背景与基础水平实施精细化分层教学，电子信息科学类设实验班、普通班与辅导班三级，其他理科设通选课、元培班与普通班三级，确保不同起点的学生都能获得适切的教学支持。电子信息科学类（A类）01实验班：面向基础好、领悟力强的学生，提供更具深度和挑战性的教学内容与实验项目，培养拔尖创新人才。02普通班：面向大多数学生，按标准教学大纲稳步推进，确保核心知识点的扎实掌握，兼顾理论与实践。03辅导班：面向基础较薄弱的学生，提供个别辅导与额外练习机会，帮助跟上课程进度，夯实基础能力。其他理科专业（B类）01通选课：供各院系基础较好的学生选修，内容侧重计算思维与编程能力的通识培养，拓展跨学科视野。02元培班：面向北大元培学院学生，结合跨学科背景设计特色教学内容，强调通识教育与专业融合。03普通班：面向各院系其他学生，以实用编程技能与计算机基础素养为核心目标，注重应用能力培养。INFRASTRUCTURE教学平台与实践环境课程构建了以POJ在线评测系统和PG编程网格为核心的实践支撑体系，结合北大网络教学平台与国家级实验教学示范中心，形成了从在线学习、编程练习到竞赛培养的完整实践教学闭环。北京大学计算机实验室·学生上机编程实拍01POJ在线评测系统：支持代码自动评测与即时反馈，覆盖数百道编程练习题，是学生日常训练的核心工具02PG编程网格系统：提供更丰富的项目管理与协作功能，支持团队编程作业与综合性实验的在线提交与评阅03网络教学平台：为师生提供功能完善的互动空间，包含课件下载、作业提交、讨论区等一站式教学资源04ACM/ICPC竞赛通道：实践教学与大学生程序设计竞赛紧密结合，为有潜力的学生提供从课堂到赛场的进阶通道METHODOLOGY计算思维导论计算思维是运用计算机科学基本概念进行问题求解的通用方法论，其核心包含分解、模式识别、抽象与算法设计四大要素，是贯穿整门课程的思维主线，也是理工科学生必备的底层能力。分解Decomposition将复杂问题拆解为更小、更易管理的子问题，逐步击破，降低问题求解的整体难度。拆解模式识别PatternRecognition发现数据或问题中的规律与共性，利用已知模式加速新问题的理解与求解。规律抽象Abstraction忽略非本质细节，提取问题的核心结构与关键变量，用数学或符号化的方式建立模型。建模算法设计AlgorithmDesign制定清晰、有序、可执行的求解步骤，确保方案可被计算机或人类精确复现。步骤CHAPTER02计算机系统基础从信息表示到硬件组成，理解计算机的工作原理COMPUTING·INTERNET计算机与互联网发展历程从1946年ENIAC诞生至今，计算机经历了电子管、晶体管、集成电路、大规模集成电路四代演变，遵循摩尔定律实现性能指数级增长；互联网从军事网络ARPANET发展为全球信息基础设施，深刻重塑了人类社会的生产与生活方式。1946第一代：电子管计算机1946年ENIAC诞生标志着电子计算机时代开启，第一代计算机使用电子管，体积庞大、功耗高、可靠性有限50s-60s第二、三代：晶体管与集成电路晶体管计算机显著缩小体积并提升可靠性，集成电路计算机进一步实现微型化18-24M摩尔定律驱动指数增长芯片晶体管数每18-24个月翻倍，计算性能指数增长，现代智能手机算力已远超早期超级计算机1969互联网：从ARPANET到全球基础设施经TCP/IP协议统一、万维网发明、移动互联网普及，演变为覆盖全球的信息基础设施ENIAC·1946年·世界上第一台通用电子计算机CHAPTER02·DATAREPRESENTATION二进制数制与信息编码基础二进制是计算机信息处理的基石，源于电子器件"开/关"两种天然状态。所有数据均需转换为二进制编码才能被计算机存储与运算。数制基础仅使用0和1两个数码，逢二进一，与电子器件高低电平天然对应，是硬件实现的最优数制选择0·1数制转换十进制转二进制采用除2取余逆序排列法，反向采用按权展开求和法，两者互为逆运算互为逆运算机器码表示原码、反码、补码解决负数编码问题，补码可统一加减运算，是现代计算机采用的标准方案补码字符编码ASCII码用7位编码128个字符，Unicode扩展至全球文字统一编码，UTF-8是最广泛的实现方案UTF-8DIGITALENCODING多媒体信息的数字化编码声音、图像等多媒体信息通过采样-量化-编码流程实现数字化。声音质量取决于采样频率与量化位数，图像数据量由分辨率与色深决定。编码与压缩技术（如JPEG、MP3）在保证质量的前提下大幅减小数据体积，是多媒体应用的基石。声音数字化采样（按固定时间间隔取值）、量化（连续幅度映射为离散数值）、编码（转为二进制存储），三步完成模拟信号到数字信号的转换。采样频率越高，还原音质越真实。44.1kHz/16bit数字图像像素矩阵构成图像，每个像素用RGB三通道各8位共24位表示真彩色，分辨率越高数据量越大。位图与矢量图分别适用于照片和图形设计场景。1920×1080≈6MB压缩编码JPEG有损压缩去除人眼不敏感的高频信息，压缩比可达10:1以上；PNG无损压缩保留全部细节，适合图标与截图。合理选择格式平衡质量与体积。JPEGvsPNG文字编码从ASCII（128字符）发展到Unicode覆盖全球文字，UTF-8以变长编码方案兼容ASCII并成为互联网主流标准。中文常用三字节表示，兼顾效率与兼容性。ASCII→UTF-8COMPUTERARCHITECTURE计算机硬件组成与体系结构计算机遵循冯·诺依曼体系结构，由运算器、控制器、存储器、输入设备和输出设备五大部件组成。CPU通过总线与内存、外设连接，形成"存储程序、顺序执行"的工作模式。软件系统从硬件到操作系统再到应用软件形成层层递进的抽象层次。核心硬件部件01CPU包含运算器和控制器，负责执行指令、进行算术逻辑运算并协调各部件工作，是计算机的核心处理单元02内存存放正在运行的程序与数据，按地址寻址访问，读写速度快但断电后数据丢失，是CPU直接交互的存储层03总线是CPU与内存、外设之间的公共信息通道，分为数据总线、地址总线和控制总线三类，构成系统互联骨架软件层次结构01硬件层由物理电子器件构成的计算基础，提供最基本的运算与存储能力，是软件运行的物质载体02操作系统层管理硬件资源、提供文件系统和进程调度机制，是用户与硬件之间的重要桥梁和抽象层03应用软件层在操作系统之上运行的各类程序，直接服务于用户的具体业务需求，实现特定功能目标COMPUTINGFUNDAMENTALSCPU工作原理与指令执行CPU通过"取指—译码—执行"的指令周期循环工作，以地址总线寻址、数据总线传输的方式访问主存储器。图灵机模型从理论上证明了通用计算的可行性，而现代CPU在此基础上通过流水线、多核、缓存等技术实现了数十亿次/秒的运算速度。01指令周期四阶段：包含取指（从内存读取指令）、译码（解析操作类型与操作数）、执行（运算器完成计算）、写回（结果存入寄存器或内存）四个阶段取指→译码→执行→写回02三总线协同访存：CPU通过地址总线发出目标内存地址，经控制总线指定读/写操作，再通过数据总线传输实际数据，三者协同完成内存访问地址·控制·数据03图灵机理论基石：具备读写头、无限长纸带和有限状态控制器的简单机器，理论上可计算所有可被算法描述的问题图灵完备04现代CPU性能增强：通过指令流水线（多级重叠执行）、多核并行、多级缓存（L1/L2/L3）等技术大幅提升指令吞吐量与运算效率Pipeline·Multi-Core·CacheCOMPUTERARCHITECTURE存储系统层次结构计算机存储系统采用'金字塔'层次设计：速度逐级递减而容量逐级递增，以少量高速存储配合大量低速存储，在成本与性能间取得最优平衡。01寄存器：位于CPU内部，访问速度最快（<1ns），容量仅数十个，存放当前正在执行的指令和操作数<1ns02高速缓存：分L1/L2/L3三级，利用时间局部性和空间局部性原理，缓存CPU近期可能再次访问的数据1–12ns03主内存：容量通常8–64GB，访问速度约50–100ns，存放正在运行的程序代码和活跃数据集70ns04外存：HDD、SSD、光盘、U盘，容量可达TB级，断电后数据不丢失，用于长期存储程序和文件TB级存储层次访问速度对比单位：纳秒（ns），对数刻度·越低越快COREFUNCTIONS操作系统功能与文件系统操作系统是连接硬件与应用软件的桥梁，核心职责包括进程调度、内存管理、文件系统组织和设备控制。文件系统以树形目录结构组织磁盘数据，配合权限机制保障信息安全，是所有应用程序运行的基础支撑环境。进程管理操作系统通过调度算法（如时间片轮转、优先级调度）分配CPU时间，实现多程序并发执行的假象。时间片轮转内存管理采用分页或分段机制为每个进程分配独立的虚拟地址空间，既保护进程间数据隔离又提高内存利用率。虚拟地址空间文件系统以树形目录结构组织文件与文件夹，支持文件的创建、读写、删除与权限控制，是数据持久化的基础。树形目录信息安全操作系统提供用户认证、文件权限（读/写/执行）、数据加密接口和防火墙等基础安全机制。权限控制COMPUTERSCIENCE·LECTURE16互联网基础与通信协议互联网以TCP/IP协议族为核心规则体系，通过路由器、交换机等硬件设备实现全球互联。IP协议负责数据包路由，TCP保证可靠传输，HTTP、DNS等应用层协议在此基础上构建了万维网、电子邮件等丰富的网络服务生态。数据中心与网络基础设施实景SECTION01·网络基础设施路由器与交换机通过光纤、卫星、海底电缆等通信链路互联，构成全球性的数据包转发网络DNS域名系统将人类可读的域名（如）解析为IP地址，是互联网可用性的关键基础设施SECTION02·核心协议体系IP协议：为每台设备分配唯一地址并负责数据包的路由转发，是互联网互联互通的基础层协议TCP协议：通过三次握手建立连接、序号确认和重传机制，保证数据在不可靠网络上的可靠传输HTTP协议：定义客户端与服务端的请求-响应规范，是万维网数据传输的应用层核心协议CHAPTER03程序设计基础从C/C++语言入门到函数、数组与指针，建立编程核心能力ChapterFoundation程序设计概述与语言演进程序设计是将问题转化为计算机可执行指令的过程，遵循'问题分析→算法设计→编码→测试→维护'的完整生命周期。编程语言从机器语言到汇编再到高级语言逐步演进，C/C++因兼具高级语言的表达力和底层系统的控制力，被选为本课程教学语言。程序设计完整流程Lifecycle从实际问题出发，经过问题抽象与数学建模、算法设计与选择、代码编写与规范、测试调试与优化，最终得到正确可靠的程序。这一过程体现了系统化的问题解决思维，是软件工程的核心方法论。机器语言与汇编语言Low-Level机器语言是纯二进制指令，直接由CPU执行但难以编写维护；汇编语言用助记符替代二进制码，可读性提高但仍依赖硬件。两者是理解计算机底层执行机制的重要基础。高级语言与C/C++High-Level高级语言接近自然语言和数学表达式，具有跨平台特性和丰富的数据结构支持，C/C++是其中的经典代表。C语言高效灵活，C++扩展了面向对象特性，广泛应用于系统开发和高性能计算领域。规范化编程风格BestPractice课程要求变量命名语义化、代码缩进统一、关键逻辑添加注释，建立规范化的编程风格，养成良好工程习惯。规范的代码不仅易于阅读维护，更是团队协作和软件质量保障的重要基石。DATATYPES基本数据类型与变量C语言中每个变量都必须声明数据类型，类型决定了内存分配大小和可表示的数值范围。整型、浮点型、字符型是三种基本类型，配合const常量和类型转换机制，构成了程序数据处理的基础框架。C语言基本数据类型速查表数据类型关键字字节数取值范围整型int4-2³¹~2³¹-1短整型short2-2¹⁵~2¹⁵-1长整型longlong8-2⁶³~2⁶³-1单精度浮点float4约±3.4×10³⁸，7位有效数字双精度浮点double8约±1.7×10³⁰⁸，15位有效数字字符型char1-128~127（ASCII编码）数据类型决定了内存大小和数值范围，选择合适类型是高效编程的基础CLANGUAGEFUNDAMENTALS运算符与表达式C语言提供算术、关系、逻辑、位运算等丰富的运算符体系。表达式的求值遵循严格的优先级和结合性规则，整数除法的截断行为、自增运算符的前后置差异以及短路求值是初学者最常踩的陷阱。算术运算符包含+、-、*、/、%，整数除法会截断小数部分（如7/2=3而非3.5），%取模运算仅适用于整数类型。7/2=3关系运算符>、<、>=、<=、==、!=比较两个值的大小关系，结果为0（假）或1（真），需注意==与赋值=的区别。0|1逻辑运算符&&（与）、||（或）、!（非）具有短路求值特性：若左侧已能确定结果，右侧表达式不会被执行。短路求值自增与自减++和--分前置（先加后用）与后置（先用后加），在复杂表达式中行为不同，建议单独成行使用以避免歧义。++vs--CONTROLFLOW程序控制结构：分支与循环分支结构（if-else/switch）和循环结构（for/while/do-while）是程序逻辑的两大骨架。分支实现条件判断下的路径选择，循环实现代码块的重复执行，两者的灵活嵌套组合可表达任意复杂的程序逻辑。BRANCHING分支结构if-else根据条件表达式的真假选择执行路径，支持嵌套和elseif链实现多条件分支判断switch-case适用于对单一变量的等值匹配场景，需注意每个case后的break防止贯穿执行ITERATION循环结构for由初始化、条件判断、更新三部分组成，最适合已知循环次数的迭代场景while在每次迭代前检查条件，适合循环次数不确定、由运行时数据驱动的场景do-while先执行再判断，保证循环体至少执行一次，适用于需要至少一次交互的输入验证条件路径选择根据运行时条件动态决定执行分支，支持多层嵌套与多条件链式判断if-else·switch重复执行控制三种循环形式覆盖已知次数、条件驱动和至少一次执行的全部迭代场景for·while·do-whileMODULE04·FUNCTIONS函数与模块化编程函数是代码复用和模块化设计的核心机制。通过将程序分解为功能单一的函数，可以提高代码的可读性、可维护性和复用性。理解参数传递、作用域和递归调用是掌握函数编程的关键。函数声明与原型指定返回类型、函数名和参数列表，使编译器在调用前能进行类型检查，通常放在头文件中。良好的原型设计是模块化编程的基础。核心概念：原型参数传递机制C语言默认值传递——实参副本传给形参，修改不影响原变量；C++可通过引用传递实现双向交互，提升效率并支持多返回值。核心概念：值传递变量作用域分为局部（函数内可见）和全局（文件内可见），局部变量优先，合理使用可减少命名冲突和副作用，增强代码的封装性与安全性。核心概念：局部优先函数递归调用函数调用自身的编程技巧，需明确终止条件避免无限递归，经典应用包括阶乘、斐波那契和汉诺塔问题，体现分治思想。核心概念：终止条件CHAPTER04·DATASTRUCTURES数组与字符串处理数组是连续内存中存储同类型元素的线性结构，支持下标O(1)随机访问但大小固定。C语言字符串是以'\0'结尾的字符数组，标准库提供了丰富的字符串操作函数，但需警惕缓冲区溢出这一最常见的安全隐患。01intarr[10]数组声明时指定类型和大小（如intarr[10]），编译器分配连续内存空间，通过下标从0开始访问，越界访问会导致未定义行为。02intmatrix[3][4]多维数组本质是数组的数组，二维数组intmatrix[3][4]可理解为3行4列的矩阵，在内存中按行优先顺序线性存储。03'\0'C语言字符串是字符数组，以'\0'标记结束位置；strlen计算长度、strcpy复制、strcmp比较、strcat拼接是四个最常用的字符串函数。04缓冲区溢出是C字符串操作最常见安全漏洞：向固定大小数组写入超出其容量的数据会覆盖相邻内存，应使用strncpy等安全版本函数。CHAPTER·POINTERS指针：C语言的灵魂指针存储变量的内存地址，通过解引用实现间接访问，是C语言进行底层内存操作的核心工具。指针与数组天然关联，配合动态内存分配（malloc/free）可实现灵活的数据结构，但空指针、野指针和内存泄漏是使用指针时最常见的错误。01指针基础指针变量存储内存地址而非数据值，'&'取地址运算符获取变量地址，'*'解引用运算符访问地址所指向的值&*02数组与指针数组名退化为指向首元素的指针，arr[i]等价于*(arr+i)，指针算术运算使遍历数组可以不依赖下标arr[i]≡*(arr+i)03动态内存malloc/free实现动态内存分配与释放，在堆区按需申请内存空间，使用后必须free否则导致内存泄漏malloc/free04常见错误空指针解引用（未初始化就使用）、野指针（指向已释放内存）、内存泄漏（忘记free）是最常见的三类错误NULL·野指针·泄漏CLANGUAGE·CUSTOMTYPES结构体与自定义数据类型结构体（struct）将不同类型的数据成员组合为一个逻辑整体，是构建复杂数据结构的基本工具。配合typedef简化类型声明、枚举enum定义命名常量集合，三者共同构成了C语言用户自定义类型体系的完整框架。struct结构体.将不同类型变量封装为复合类型，各成员通过.运算符访问复合封装typedef别名为已有类型创建别名，简化复杂类型声明，提升代码可读性与可维护性可读简化enum枚举定义命名整数常量集合，默认从0递增，增强代码语义表达能力语义常量结构体指针->用->访问成员，配合动态内存创建链表结构动态链表CHAPTER·FILEI/O文件输入输出操作文件操作使程序能够将数据持久化到磁盘，是程序与外部数据交互的核心手段。C语言通过FILE指针统一管理文件流，提供格式化读写与二进制读写两套接口，正确使用需严格遵循"打开→检查→读写→关闭"的操作规范。文件打开fopen以指定模式打开文件（'r'只读、'w'写入会清空、'a'追加、'rb'/'wb'二进制），返回FILE指针供后续操作使用。fopen格式化读写fprintf将格式化数据写入文件，fscanf从文件读取格式化数据，用法与printf/scanf类似但目标为文件流。fprintf二进制读写fread/fwrite按数据块读写，适合处理结构体数组等非文本数据，效率高于逐字符或格式化操作。fread安全检查必须检查fopen返回值是否为NULL（文件不存在或权限不足），程序结束前调用fclose确保缓冲区数据刷入磁盘并释放资源。fcloseChapter04算法与数据结构掌握递归、排序、链表与栈队列等经典算法和数据结构ALGORITHM·递归思想递归算法：大事化小的思维递归通过函数调用自身将问题分解为更小的同类子问题，核心是递归关系与终止条件，需警惕指数级重复计算。01递归函数两大必备要素递归关系定义大问题如何分解为小问题，基础情况作为终止条件防止无限递归导致栈溢出。递归关系+终止条件02阶乘：递归经典入门n!=n×(n-1)!每次递归将问题规模减1，终止条件为n=0时返回1，时间复杂度O(n)。O(n)03斐波那契的效率陷阱F(n)=F(n-1)+F(n-2)的朴素递归产生大量重复子问题计算，时间复杂度O(2ⁿ)，效率极低。O(2ⁿ)04汉诺塔：递归的威力将n个盘子的移动分解为三次n-1规模的子问题，展示递归处理复杂问题的强大能力。2ⁿ−1步经典排序算法与效率分析排序算法是算法学习的基石。冒泡、选择、插入排序实现简单但时间复杂度为O(n²)，适合小规模数据；快速排序采用分治策略平均达到O(nlogn)，是实践中最常用的排序算法。理解算法复杂度差异是培养计算效率意识的关键一步。经典排序算法对比算法名称最佳时间平均时间最差时间稳定性冒泡排序O(n)O(n²)O(n²)稳定选择排序O(n²)O(n²)O(n²)不稳定插入排序O(n)O(n²)O(n²)稳定快速排序O(nlogn)O(nlogn)O(n²)不稳定归并排序O(nlogn)O(nlogn)O(nlogn)稳定快速排序平均效率最优，归并排序保证最坏情况仍为O(nlogn)且稳定AlgorithmDesign贪心算法与动态规划贪心算法每步选择局部最优解以期达到全局最优，实现简单但不适用于所有问题；动态规划通过保存子问题的解避免重复计算，可求解具有最优子结构和重叠子问题性质的复杂优化问题，两者是算法设计中最重要的两大策略。贪心算法核心思想：每步选择当前最优方案，不做回溯，期望局部最优累积为全局最优，时间复杂度通常较低经典案例：活动选择问题（按结束时间排序后贪心选取）、霍夫曼编码（每次合并频率最低的两棵树）动态规划核心思想：将问题分解为重叠子问题，用表格存储已求解的子问题结果（记忆化），避免重复计算实现多项式时间复杂度经典案例：0-1背包问题（容量约束下的最优选择）、最长公共子序列（字符串相似度度量）、斐波那契数列优化DATASTRUCTURE·LINKEDLIST链表：动态数据结构基础链表通过指针将分散的内存节点串联为线性序列，突破了数组大小固定的限制，支持O(1)的动态插入与删除。单链表、双向链表和循环链表是三种基本变体，理解链表是从静态数组思维跃迁到动态数据结构思维的关键一步。01单链表结构节点包含数据域和next指针，各节点在内存中不连续分布，通过指针链接形成逻辑线性序列02插入与查找插入只需修改相邻节点指针（O(1)），无需移动后续元素，但查找仍需从头遍历（O(n)）03双向链表每个节点增加prev指针指向前驱，支持双向遍历，删除操作更方便但仍需O(n)查找04循环链表尾节点next指向头节点形成环，适合周期性遍历场景，如循环调度、约瑟夫环问题链表操作时间复杂度对比操作类型时间复杂度说明插入O(1)位置已知时删除O(1)位置已知时查找O(n)需遍历链表n为链表长度·位置已知时插入/删除为O(1)DATASTRUCTURE栈与队列栈（LIFO后进先出）和队列（FIFO先进先出）是两种操作受限的线性数据结构，限制反而赋予了它们独特的应用价值。栈是函数调用管理和表达式解析的核心机制，队列是任务调度和广度优先搜索的基础设施，两者在系统软件和算法设计中不可或缺。栈（Stack）-LIFO01栈仅允许在栈顶进行push（入栈）和pop（出栈）操作，后进先出的特性天然适合需要逆序处理的场景02核心应用：函数调用栈管理嵌套调用的执行与返回、中缀表达式转后缀并求值、括号匹配与撤销操作（Undo）LastIn,FirstOut队列（Queue）-FIFO01队列在队尾enqueue（入队）、在队首dequeue（出队），先进先出的特性保证按到达顺序处理任务02核心应用：操作系统进程调度与I/O缓冲、网络数据包的有序传输、图的广度优先搜索（BFS）算法实现FirstIn,Fir