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

北京大学《计算概论》课件欢迎来到北京大学《计算概论》课程本课程将带您深入了解计算机科学的基础知识，从硬件到软件，从算法到编程语言让我们一起开启这段激动人心的学习之旅计算机发展历程机械计算时代1从算盘到差分机，人类开始探索机械计算的可能性电子计算机诞生2ENIAC的出现标志着电子计算机时代的到来个人计算机兴起3苹果和IBM推动了个人计算机的普及互联网时代4全球信息互联互通，计算机成为日常生活的一部分计算机的硬件组成中央处理器（）内存（）CPU RAM计算机的大脑，负责执行指令和临时存储数据和程序的地方，速数据处理度快但容量有限存储设备输入输出设备如硬盘，用于长期存储数据和程如键盘、鼠标、显示器等，用于序人机交互的工作原理CPU取指令从内存中获取下一条要执行的指令译码解释指令的含义，确定需要执行的操作执行执行指令指定的操作，如算术运算或数据移动写回将操作结果存储到指定的位置存储设备介绍内存（）硬盘（）光盘（）RAM HDD/SSD CD/DVD速度快，容量小，断电数据丢失主要用容量大，速度相对较慢，可长期保存数便于携带和分发，容量适中，主要用于数于临时存储正在运行的程序和数据据用于存储操作系统、软件和用户文据备份和多媒体存储件输入设备键盘鼠标用于输入文字、数字和命令的主要设用于控制光标，选择和操作图形界面备元素麦克风摄像头用于语音输入和音频录制用于图像和视频输入输出设备输出设备将计算机处理的结果以可感知的形式呈现给用户常见的输出设备包括显示器、打印机、投影仪、音箱和绘图仪等程序的基本概念指令序列自动执行程序是一系列按特定顺序排列的程序能够被计算机自动执行，无计算机指令需人工干预数据处理可重复使用程序可以处理输入数据，产生期同一程序可以多次执行，处理不望的输出结果同的输入数据算法的基本概念问题定义1明确要解决的问题输入规范2确定算法的输入数据处理步骤3设计解决问题的具体步骤输出规范4定义算法的预期输出效率考虑5优化算法的执行效率算法的基本特性有限性确定性算法必须在有限步骤内完成每个步骤必须有明确的定义输入输出算法有零个或多个输入算法有一个或多个输出算法的基本表达自然语言流程图伪代码程序代码用日常语言描述算法步骤，易用图形符号表示算法流程，直结合自然语言和程序设计语言用特定编程语言编写，最精确于理解但可能存在歧义观但不适合复杂算法的特点，既易读又较为精确但需要编程知识算法的时间复杂度分析O11常数时间，最优复杂度Olog n2对数时间，如二分查找On3线性时间，如遍历数组On logn4线性对数时间，如快速排序On^25平方时间，如简单排序算法程序设计语言概述机器语言汇编语言直接由计算机执行的二进制代使用助记符表示机器指令，比机码，效率高但编写困难器语言更易读高级语言脚本语言接近自然语言，如C++、Java、如JavaScript、Python，通常Python等，易学易用用于快速开发和自动化任务数据类型基本数据类型复合数据类型•整数（int）•数组•浮点数（float）•结构体•字符（char）•类•布尔（bool）基本运算符算术运算符关系运算符+、-、*、/、%（加、减、乘、除、==、!=、、、=、=（等于、不取余）等于、大于、小于等）逻辑运算符位运算符（与）、||（或）、!（非）、|、^、~、、（按位与、或、异或、取反、左移、右移）控制流程语句顺序结构按照语句的先后顺序依次执行选择结构if-else、switch-case等条件判断语句循环结构for、while、do-while等重复执行语句跳转语句break、continue、return等控制程序流程函数与过程定义函数函数体12指定函数名、参数列表和返回编写实现函数功能的代码值类型参数传递返回结果34可以通过值传递或引用传递使用return语句返回函数结果数组一维数组二维数组数组操作线性排列的同类型数据集合，如int表格形式的数据结构，如int•元素访问arr

[5]matrix

[3]

[3]•遍历•排序•搜索字符串操作长度计算连接获取字符串的字符数将两个或多个字符串合并子串比较提取字符串的一部分判断两个字符串是否相等或大小关系文件读写操作打开文件读取/写入移动文件指针关闭文件指定文件名和打开模式（读/从文件读取数据或向文件写入调整读写位置完成操作后释放文件资源写/追加）数据面向对象程序设计封装1将数据和方法捆绑在一起继承2子类继承父类的属性和方法多态3同一接口，不同实现面向对象编程是一种程序设计范式，它将数据和操作数据的函数绑定在一起，形成一个独立的对象这种方法有助于提高代码的可重用性和可维护性类与对象类对象成员变量成员函数类是对象的模板，定义了对象对象是类的实例，具有类定义类中定义的变量，用于存储对类中定义的函数，用于操作对的属性和方法它是一种抽象的属性和方法它是程序中的象的状态象的数据的数据类型具体实体继承与多态继承多态子类继承父类的属性和方法，实同一方法在不同对象上有不同的现代码重用行为重写接口子类重新定义父类的方法定义方法的契约，但不实现异常处理块try包含可能抛出异常的代码块catch捕获并处理特定类型的异常语句throw手动抛出异常块finally无论是否发生异常都会执行的代码泛型编程类型参数化代码重用使用占位符类型定义类或方法一份代码可以用于多种数据类型类型安全性能优化编译时类型检查，减少运行时错避免类型转换，提高运行效率误网络基本概念协议IP地址定义数据如何在网络上传输标识网络上的设备端口数据包区分同一设备上的不同服务网络传输的基本单位应用层协议应用层协议定义了应用程序如何在网络上交换数据常见的应用层协议包括HTTP（网页）、FTP（文件传输）、SMTP（电子邮件）、DNS（域名解析）和MQTT（物联网通信）等传输层协议TCP UDP面向连接，可靠传输，适用于要求数据完整性的应用无连接，快速传输，适用于实时性要求高的应用网络层协议IP ICMP负责数据包的寻址和路由用于发送错误消息和操作信息ARP OSPF将IP地址转换为物理地址动态路由协议，用于路由器间通信数据链路层协议以太网Wi-Fi最常用的局域网技术无线局域网标准PPP HDLC点对点协议，用于拨号和一些广域网连接高级数据链路控制，用于同步数据传输物理层协议有线传输无线传输网络接口通过电缆传输数据，如双绞线、同轴电缆和通过电磁波传输数据，如无线电、微波和红连接计算机和网络的硬件，如网卡和调制解光纤外线调器。