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

北京大学《计算概论》课件欢迎来到北京大学《计算概论》课程。本课程将带您深入了解计算机科学的基础知识，从硬件到软件，从算法到编程语言。让我们一起开启这段激动人心的学习之旅。计算机发展历程1机械计算时代从算盘到差分机，人类开始探索机械计算的可能性。2电子计算机诞生ENIAC的出现标志着电子计算机时代的到来。3个人计算机兴起苹果和IBM推动了个人计算机的普及。4互联网时代全球信息互联互通，计算机成为日常生活的一部分。计算机的硬件组成中央处理器（CPU）计算机的大脑，负责执行指令和数据处理。内存（RAM）临时存储数据和程序的地方，速度快但容量有限。存储设备如硬盘，用于长期存储数据和程序。输入输出设备如键盘、鼠标、显示器等，用于人机交互。CPU的工作原理取指令从内存中获取下一条要执行的指令。译码解释指令的含义，确定需要执行的操作。执行执行指令指定的操作，如算术运算或数据移动。写回将操作结果存储到指定的位置。存储设备介绍内存（RAM）速度快，容量小，断电数据丢失。主要用于临时存储正在运行的程序和数据。硬盘（HDD/SSD）容量大，速度相对较慢，可长期保存数据。用于存储操作系统、软件和用户文件。光盘（CD/DVD）便于携带和分发，容量适中，主要用于数据备份和多媒体存储。输入设备键盘用于输入文字、数字和命令的主要设备。鼠标用于控制光标，选择和操作图形界面元素。麦克风用于语音输入和音频录制。摄像头用于图像和视频输入。输出设备输出设备将计算机处理的结果以可感知的形式呈现给用户。常见的输出设备包括显示器、打印机、投影仪、音箱和绘图仪等。程序的基本概念指令序列程序是一系列按特定顺序排列的计算机指令。自动执行程序能够被计算机自动执行，无需人工干预。数据处理程序可以处理输入数据，产生期望的输出结果。可重复使用同一程序可以多次执行，处理不同的输入数据。算法的基本概念1问题定义明确要解决的问题。2输入规范确定算法的输入数据。3处理步骤设计解决问题的具体步骤。4输出规范定义算法的预期输出。5效率考虑优化算法的执行效率。算法的基本特性有限性算法必须在有限步骤内完成。确定性每个步骤必须有明确的定义。输入算法有零个或多个输入。输出算法有一个或多个输出。算法的基本表达自然语言用日常语言描述算法步骤，易于理解但可能存在歧义。流程图用图形符号表示算法流程，直观但不适合复杂算法。伪代码结合自然语言和程序设计语言的特点，既易读又较为精确。程序代码用特定编程语言编写，最精确但需要编程知识。算法的时间复杂度分析1O(1)常数时间，最优复杂度。2O(logn)对数时间，如二分查找。3O(n)线性时间，如遍历数组。4O(nlogn)线性对数时间，如快速排序。5O(n^2)平方时间，如简单排序算法。程序设计语言概述机器语言直接由计算机执行的二进制代码，效率高但编写困难。汇编语言使用助记符表示机器指令，比机器语言更易读。高级语言接近自然语言，如C++、Java、Python等，易学易用。脚本语言如JavaScript、Python，通常用于快速开发和自动化任务。数据类型基本数据类型整数（int）浮点数（float）字符（char）布尔（bool）复合数据类型数组结构体类基本运算符算术运算符+、-、*、/、%（加、减、乘、除、取余）关系运算符==、!=、>、<、>=、<=（等于、不等于、大于、小于等）逻辑运算符&&（与）、||（或）、!（非）位运算符&、|、^、~、<<、>>（按位与、或、异或、取反、左移、右移）控制流程语句顺序结构按照语句的先后顺序依次执行。选择结构if-else、switch-case等条件判断语句。循环结构for、while、do-while等重复执行语句。跳转语句break、continue、return等控制程序流程。函数与过程1定义函数指定函数名、参数列表和返回值类型。2函数体编写实现函数功能的代码。3参数传递可以通过值传递或引用传递。4返回结果使用return语句返回函数结果。数组一维数组线性排列的同类型数据集合，如intarr[5]。二维数组表格形式的数据结构，如intmatrix[3][3]。数组操作元素访问遍历排序搜索字符串操作长度计算获取字符串的字符数。连接将两个或多个字符串合并。子串提取字符串的一部分。比较判断两个字符串是否相等或大小关系。文件读写操作打开文件指定文件名和打开模式（读/写/追加）。读取/写入从文件读取数据或向文件写入数据。移动文件指针调整读写位置。关闭文件完成操作后释放文件资源。面向对象程序设计1封装将数据和方法捆绑在一起。2继承子类继承父类的属性和方法。3多态同一接口，不同实现。面向对象编程是一种程序设计范式，它将数据和操作数据的函数绑定在一起，形成一个独立的对象。这种方法有助于提高代码的可重用性和可维护性。类与对象类类是对象的模板，定义了对象的属性和方法。它是一种抽象的数据类型。对象对象是类的实例，具有类定义的属性和方法。它是程序中的具体实体。成员变量类中定义的变量，用于存储对象的状态。成员函数类中定义的函数，用于操作对象的数据。继承与多态继承子类继承父类的属性和方法，实现代码重用。多态同一方法在不同对象上有不同的行为。重写子类重新定义父类的方法。接口定义方法的契约，但不实现。异常处理try块包含可能抛出异常的代码。catch块捕获并处理特定类型的异常。throw语句手动抛出异常。finally块无论是否发生异常都会执行的代码。泛型编程类型参数化使用占位符类型定义类或方法。代码重用一份代码可以用于多种数据类型。类型安全编译时类型检查，减少运行时错误。性能优化避免类型转换，提高运行效率。网络基本概念协议定义数据如何在网络上传输。IP地址标识网络上的设备。端口区分同一设备上的不同服务。数据包网络传输的基本单位。应用层协议应用层协议定义了应用程序如何在网络上交换数据。常见的应用层协议包括HTTP（网页）、FTP（文件传输）、SMTP（电子邮件）、DNS（域名解析）和MQTT（物联网通信）等。传输层协议TCP面向连接，可靠传输，适用于要求数据完整性的应用。UDP无连接，快速传输，适用于实时性要求高的应用。网络层协议IP负责数据包的寻址和路由。ICMP用于发送错误消息和操作信息。ARP将IP地址转换为物理地址。OSPF动态路由协议，用于路由器间通信。数据链路层协议以太网最常用的局域网技术。