计算机基础

计算机基础知识 从基本结构上来讲,电脑可以分为五大部分:运算器、存储器、 控制器、输入设备、输出设备。

计算机基础

（导论）计算与社会

计算

定义：某计算装置上，根据已知条件，从某一个初始点开始，在完成一组良好定义的操作序列后，得到预期结果的过程

算法

定义：一组良好定义的操作序列

特征：

输入

输出

明确性

有限性

有效性

控制结构：

顺序结构

选择结构

循环结构

计算装置

早期：结绳记事、算盘

机械式计算装置 出现在17世纪的西方国家

第一台机械计算器： 舒卡德计算器1623年，特点：

某种机械方式保存参与运算的数和结果

用齿轮作为自动运算的装置

运算法则固定在机械中，以机械运动实现运算

巴贝奇

差分机——>1830年巴贝奇机器分析机

第一个程序：为机器编的世界上第一个程序，伯努利数序列

第一个程序员：艾达劳伦斯，ada以其命名

贡献

第一台具有现代意义的计算机器

提出了程序控制思想

提出了程序设计思想

现代计算机技术的奠基人

1884年，赫尔曼霍雷思 第一台电动计算机

1937-1944年，霍华德艾肯 马克I号-全继电器式计算器

1938-1945年，柯腊德祖斯 Z1，Z2，Z3，Z4计算机。贡献：

针对继电器操作研究了布尔代数的条件命题系统

首次采用二进制数以及浮点数规格化并实现

首次提出存储器概念

图灵机和图灵

图灵机是一个通用的、抽象的计算模型

可计算性：如果为一个任务说明一个指令序列，按照该指令序列执行，能够导致任务的完成，则该任务是可计算的。

图灵机的工作原理

基本思想：用机器模拟人们用纸笔进行数学运算的过程

动作：1、写或擦除某个符号；2、把注意力从纸的一个位置移动到另一个

组成：无限长纸带，读写头，控制规则，状态寄存器

三因素

当前状态

读写头所在方格符号

转换规则

current_state

symbol

action

next_state

图灵机导致了计算的形式概念，即图灵可计算性

图灵机是一类离散的有限状态自动机

图灵被认为奠定了计算机科学的基础

现代电子计算机

第一台能运行的电子数字计算机：ENIAC

ENIAC启发了冯诺依曼

冯诺依曼体系结构，特点：

程序指令和数据都用二进制形式表示

程序指令和数据共同存储在存储器中

自动化和序列化执行程序指令

微型计算机

诞生：阿尔塔8800

计算机网络

第一个计算机网络：ARPANET（阿帕网）

Email,FTP,Telnet,WWW,HTTP

特点：

资源和信息共享

比独立计算机更强壮

信息处理性能有极大的提高

硬件发展阶段：

电子管计算机

晶体管计算机

集成电路计算机

大规模集成电路计算机

摩尔定律

存储能力相对于时间周期将成呈指数式的上升

分类

根据运算速度和存储容量：微型机、小型机、中型机、大型机、巨型机、超级巨型机。 随着计算机性能不断提高，这个分类慢慢不够恰当

根据通用性：通用计算机和嵌入式计算机

根据计算机网络模式C/S：服务器和客户机

发展趋势

微型化

巨型化

网络化

网格计算

普适计算

智能化

计算机技术的应用

科学计算软件：Matlab等

文字处理和办公软件：WPS,Office

管理信息系统（MIS）

计算机辅助系统：CAD,CAM,CAT,CBE等

人工智能系统：Dendral等专家系统、数据挖掘系统、博弈系统、机器翻译系统、声音和图像识别系统

多媒体技术应用系统

嵌入式系统：IA,3C

信息化社会与人

信息成为基本资源，信息技术成为推动社会发展的基本动力

基本特征

信息和知识成为社会进步的决定因素

信息及其相关产业从业者在信息化社会中作用愈发突出

人们工作、学习、生活方式发生巨大变化

信息素养：信息意识、计算思维等

信息安全：数据安全，信息系统安全

计算机犯罪

计算思维

定义：运用计算机科学的基础概念去求解问题、设计系统和理解人类行为

特征

概念化而非程序化

根本的而非刻板的

人的思维方式而非计算机的

数学和工程思维的互补和融合

是思想而不是人造物

面向所有人所有地方

本质

抽象Abstraction

对应建模

自动化Automation

对应模拟

计算思维是人类思想和计算机能力的综合

Python简介

运行环境

脚本script

解释器shell

开发环境IDLE

基本元素

对象、表达式和数值类型

对象

int

float

bool

none

运算符

int，float：+，-，*，//，/，%，**，>，>=，<，<=

bool：and，or，not

对象+运算符=表达式

变量和赋值

大小写不同

注释#

多重赋值

字符串类型和输入

运算符重载

str为序列类型

类型转换：类型名函数，eval函数

内置数据结构

列表list（序列类型）

表示符号[ ]；可删除的数据类型；基本操作：添加3种：append，insert，extend；删除2种：pop，remove；修改：count，index，reverse，sort

元祖tuple（序列类型）

表示符号( )；不可删除的列表；基本操作：索引，截取片段，in，+，len，max，min

字典dictionary

表示符号{ }；组织格式：key:value；基本操作：len，keys，value，in，del

控制语句

分支语句

if，else，elif

语句后加：

循环语句

while，for

语句后加：

for i in range(0,x):

函数

目的：1、降低编程的难度；2、代码重用

def fname(formalparameters): fbody

---形参 ---实参

导入模块

import，from...import

math，random...

面向对象基础

object

代码重用

继承机制

计算思维

计算思维和数学思维的区别

三大思维能力：实验思维、理论思维和计算思维

逻辑思维

定义：研究推理的科学，帮助人们理解事物，建立和检查事实

所有已知事实为前提

设计的三条保证

推理有效性

给计算机的输入可靠性

能解释计算机输出是绝对正确（演绎）的还是可能正确（归纳）的

算法思维

定义：算法是用于完成某个任务的一系列指令或一组规则。算法思维能让人们设计出借助计算机解决问题的算法

构建于逻辑之上，不等同于逻辑，既要基于逻辑判断，又要基于判断做出动作

算法有限性要求算法必须在有限步内必须停下来

问题求解策略

问题求解步骤：理解问题、制定计划、执行计划、检查结果

在问题和答案之间建立一个连接

解题原则：解的质量，协作，迭代

分解法decomposition

定义：将问题或系统拆分成更小、更易管理的小问题或小系统的过程。

形成问题树

分解的结果是制定详细解题计划的起点

模式与归纳

操作步间的模式可归纳为循环

操作步块间的模式可归纳为子过程（函数）

条件和等式间的模式可归纳为规则

抽象与建模

抽象abstraction的两方面含义

舍弃事物非本质特征，仅保留与问题相关的本质特征

从众多的具体实例中抽取出共同的、本质的特征

计算思维是抽象的自动化执行

建模modeling是对现实世界事物的描述，这种描述通常会舍弃一些细节

模型的组成：实体和关系

模型的分类：静态模型和动态模型

E-R图

评价解决方案

解是否正确

基本方法：测试

解的效率如何

两个指标：时间复杂度、空间复杂度

算法

常见算法策略

分治法divide and conquer

贪婪法greedy

回溯法backtracking

分支限界法branch and bound

动态规划dynamic programming

算法描述

文字描述

图形描述

伪码描述

算法示例

辗转相除算法

累加求和算法

背包

递归算法

排序

数据结构

定义：相互之间存在一种或多种特定关系的数据元素的集合。一般涉及数据逻辑结构、数据物理结构和数据结构上的运算

数据逻辑结构：从具体问题抽象出的数学模型，用于描述数据元素及其关系的数学特性

分类

集合结构：set

线性结构：线性表list、栈stack、队列queue、双队列、数组、串

树结构：有层次的嵌套结构，一对多，递归表示，python用元祖数据类型可模拟

图（网）结构：多对多，树结构是图结构的特例，矩阵存储图结构，python用list构成矩阵

数据物理（存储）结构：数据逻辑结构在计算机中的表示

结构映像和非结构映像

数据结构上的运算

结构的生成与销毁

搜索

插入

删除

遍历

程序

本质上是描述一定数据的处理过程

应包括：1、对数据的描述-指定数据结构；2、对操作的描述-操作步骤

程序=数据结构+算法

程序设计语言基本功能：描述数据和对数据的运算。组成：语法、语义、语用

低级语言

机器语言和汇编语言ASM（汇编器）

高级语言

和汇编语言一样需要编译器/解释器

分类

过程式程序设计语言PPL：FORTRAN,C,Pascal,Ada

面向对象程序设计语言OOPL：Smalltalk,C++,Java

函数式程序设计语言FPL：LISP,ML

逻辑程序设计语言LPL：Prolog

数据库技术应用基础

概述

数据库定义：依照某种数据模型组织起来并存放于外部存储器中的数据集合

特点：尽可能不重复，以最优方式为某个特定组织的多种应用服务，数据结构独立于使用它的应用程序，对数据的增删改查由统一软件管理和控制

发展阶段

人工管理阶段

文件系统管理阶段

数据库系统管理DBMS阶段

数据库系统是一个实际可运行的存储、维护数据的应用软件，通常涉及存储介质、处理对象和数据库管理系统等方面

完整的数据库系统应包括：

应用程序

使用程序设计语言开发的软件，实现复杂功能，通过DBMS和数据库交互

数据库

存放原始数据的集合和元数据

以数据文件的形式逻辑存在

数据库管理系统DBMS

操纵和管理数据库的大型系统软件

数据库管理员DBA

通过DBMS提供的界面访问数据库和进行管理

数据库技术管理数据的主要特征

集中控制数据

数据冗余度小

数据独立性强

维持复杂的数据模型

提供数据的安全保障

数据库的应用

无处不在

数据模型

模型是对现实世界的抽象，数据库中由数据模型负责描述和说明数据，数据以及描述数据的数据共同构成数据库

数据模型是数据库系统的核心和基础

数据模型=数据结构+数据操作+数据完整性约束

数据结构

对象和对象之间联系的表达和实现，对系统静态特征的描述

包括数据本身和数据之间的联系两个方面

数据操作

对数据库中对象的实例允许执行的操作集合，对系统的动态特征的描述

主要指检索和更新两类操作

实例： SELECT student_name FROM student WHERE originalplace="湖南"

数据完整性约束

数据的正确性、有效性和相容性 即是否合法、是否在有效范围和同一事实的两个数据是否相同

按应用层次划分类型

数据库设计主要工作：数据库建模

数据库设计步骤：建立概念数据模型，将其转换为逻辑数据模型，再转化为物理数据模型

概念数据模型->

逻辑数据模型->

物理数据模型

概念模型CDM

现实世界到机器世界的一个中间层次，第一层抽象

实体-联系（Entity-Relation，ER）模型

该模型认为世界是由一组被称为实体的基本对象与其之间的联系所构成的

静态实体模型

主要要素

实体entity

可以互相区别的客观事物和概念统一抽象为实体

可以是客观存在的也可以是抽象的

实体集entity set

相同性质或类型的实体的集合

也可以简称为实体

属性property

实体集中每个成员具有的描述性性质，是对实体特征的描述

属性有取值范围，称为域

实体键entity key

由能够唯一标识一个实体的属性或者属性组 组成

能唯一标识实体的极小属性组为该实体集的实体键

一个实体集有多个实体键，则从中选择一个作为实体集的主键

联系relation

实体间的关系抽象称为联系

一对一联系1：1

一对多联系1：n

多对多联系m：n

联系也可以有自己的属性

E-R图

实体集符号□

属性符号○

联系符号◇

实体键符号 _

概念建模5步：确定实体集、标识联系、标识属性并将属性与实体或联系相关联、确定属性域、确定实体键

扩充（Enhanced）的E-R模型

谓词模型

逻辑模型LDM

用户从数据库能看到的模型，是具体的DBMS支持的数据模型

既要面向用户，又要面向系统

是对概念模型的分解和细化

数据库的演变表征逻辑模型的发展

网状、层次数据库系统->

关系数据库系统->

面向对象数据库系统

层次模型

网状模型

关系模型

关系数据库以关系模型为基础，可以看做是许多表的集合，每张表代表一个关系

涉及基本概念：关系（二维表）、关系框架（第一行）、属性（每一列）、元组（其他行）、超关键字/键（唯一标识的属性集合）、候选关键字/键（唯一标识的讥笑属性集合）、主关键字/键（被选用的候选关键字）、外部关键字/键（属性子集，子集为外部关系的超关键字）

基本运算

实例

SELECT * FROM student WHERE originalplace="X"

SELECT teachername,professionaltitle FROM teacher

SELECT student.studentname FROM student,course,study WHERE course.teacherID='X' AND course.courseID=study.courseID AND study.studentID=student.studentID

含义

在student表中查找籍贯为X的元组，并返回所有行和列

在teacher表中查找教师名字和职称，并返回该两列

查找学习了教师编号为X的教师讲授课程的同学的名字，并返回学生名字列

实例

INSERT INTO student VALUES('XH010','张三','男','广东')

DELETE FROM course WHERE teacherID='X'

UPDATE study SET score=92 WHERE studentID='X' AND courseID='Y'

含义

在student表中插入一条记录，学号，姓名，性别和籍贯等信息

在course表中删除教师编号为X的教师讲授的所有课程

修改学号为X的学生课程编号为Y的课程成绩为92

完整性约束

由DBMS自动完成检验

保证数据库数据和现实世界的一致性

分类

域完整性（domain integrity）约束

属性值是否取自值域及属性是否可为null

实体完整性（entity integrity）约束

主键属性不能为null

引用完整性（referential integrity）约束

外部键不能取null或引用不存在候选键

用户自定义完整性约束

E-R模型到关系模型的转化

遵循原则

实体转化：每一个实体转化为一个关系，实体属性转化为关系属性，实体主键转化为关系主键

实体1：学生（学号，姓名，性别，籍贯），主键：学号

实体2：课程（课程编号，课程名称，学时，教师编号），主键：课程编号，外键：教师编号

实体3：教师（教师编号，姓名），主键：教师编号

一对一联系转化：将任意一方的主键放入另一方的关系中，若联系本身也有属性，则也将属性放入关系中

一对多联系转化：将一方的主键放入多方的关系中，作为多方的外键

多对多联系转化：为多对多联系创建一个新的关系，将参与该联系的双方主键放入该关系，作为外键，双方的主键组合构成新关系的主键，若联系本身也有属性，则也将属性放入关系中

关系：学习（学号，课程编号，成绩），主键：学号，课程编号

数据库管理系统

DBMS功能：

对数据库的定义

数据库的操作及优化

数据库的控制运行

数据库的恢复和维护

数据库的数据管理

提供数据库的多种接口

常见DBMS软件：

国产： OpenBASE， DM7， GBASE， 金仓数据库

国际主流： Oracle的Oracle， IBM的DB2， Microsoft的Access，SQL Seerver， 以及Sybase，Informix，Foxpro等

开源： My SQL SAP DB(MaxDB) PostgreSQL Derby Firebird HSQL Berkeley DB等

计算机发展新技术

高性能计算HPC

泛指计算速度快、计算量大、计算效率高的一类计算

超级计算

关键技术，主要是： 并行计算Parallel Computing的关键技术

目的：1、提供更快速度；2、解决传统计算机无法解决的问题

并行计算机

三要素：结点、互联网络、内存

体系结构

按数据流和指令流多倍性

单指令流单数据流SISD

普通串行机

单指令流多数据流SIMD

不同数据相同运算有优势，专门设计

多指令流单数据流MISD

少见

多指令流多数据流MIMD

更加灵活，通用

并行向量处理机PVP

银河一号、银河二号

对称多处理机SMP

曙光一号

大规模并行处理机MPP

曙光1000

分布式共享存储多处理机DSM

银河三号、神威一号

集群Cluster

曙光2000，曙光3000

按系统结构

互联网络技术

两个层次：结点内和结点外

Myrinet，ATM，FDDI等

5种访存模型

均匀访存模型UMA、非均匀访存模型NUMA、全高速缓存访存模型COMA、高速缓存一致性非均匀访存模型CC-NUMA、非远程访存模型NORMA

典型应用

大科学、大工程、产业升级、信息化建设

发展挑战

技术瓶颈：存储墙、可靠性墙、能耗墙、通信墙、编程墙

云计算CC

核心理念：通过不断提高云的处理能力，减少用户终端的处理负担，最终使用户终端简化成单纯的输入输出设备，并能按需享受云的强大计算能力

特点：超大规模、虚拟化、高可靠性、通用性、高可扩展性、按需服务、经济性、潜在危险性

服务层次：基础设施即服务IaaS（对所有设施的利用，任意部署）、平台即服务PaaS（应用程序部署）、软件即服务SaaS（基础程序，不需部署）

大数据BigData

定义：无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合

特征4V(5V)：1、数据量大Volume；2、数据类型多样Variety；3、处理速度快Velocity；4、价值密度低Value；（5、真实性Veracity）

处理基本流程：

数据抽取与集成

数据分析

数据解释

大数据和云计算的关系：云计算是大数据的IT基础，提供平台和支撑技术；大数据是云计算的重要应用

人工智能AI

范畴：研究、开发用于模拟、眼神和扩展人的智能的理论、方法、技术及应用系统的一门技术科学

定义：用人工方法在机器上实现的智能

约翰·麦卡锡：人工智能之父

AlphaGo

搜索：采用合适的技术来模仿人类求解问题，搜索是问题求解的基本方法之一

知识表示与推理

机器学习

分类：监督学习、无监督学习、半监督学习和强化学习

深度学习

智能控制

驱动智能机器自主实现其目标的过程

自主机器人的控制是一种典型的智能控制

新型计算技术

量子计算QC

按照量子物理规律完成计算任务

具有经典计算不可比拟的计算优势

光计算

采用光学方法来实现运算处理和数据传输的技术

分为模拟光计算和数学光计算

生物计算

利用生物工程和生物学来实现计算的技术

数据结构扩展

数据结构(Data Structure)是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

逻辑结构

集合

哈希表（散列表）hash

线性（特殊树）

线性表list

栈stack：特殊线性表

先进后出FILO

队列queue：特殊线性表

先进先出FIFO

数组array

树形（特殊图）

堆heap：特殊树

大顶堆

小顶堆

树tree

二叉树

图形

图graph

物理结构

顺序存储： 一段连续的内存空间。 优点：随机访问； 缺点：插入删除效率低，大小固定。

链式存储： 不连续的内存空间。 优点：大小动态扩展，插入删除效率高； 缺点：不能随机访问。

索引存储： 为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。 优点：对顺序查找的一种改进，查找效率高； 缺点：需额外空间存储索引。

散列存储： 选取某个函数，数据元素根据函数计算存储位置可能存在多个数据元素存储在同一位置，引起地址冲。 优点：查找基于数据本身即可找到，查找效率高，存取效率高； 缺点：存取随机，不便于顺序查找。

科学计算

略

信息、编码及数据表示

信息的（香农Shannon）定义：信息是事物运行状态或存在方式的不确定性表述，即信息是确定性和非确定性、预期和非预期的组合。

信息熵：解决信息量的度量问题

度量尺度的三条原则

能度量任何消息，和消息种类无关

度量方法应该和消息重要程度无关

消息中所含信息量和消息内容的不确定性有关

信息量相关公式

P(x)表示消息x发生的概率，1≥P(x)≥0

I表示消息x中所含的信息量，I=I[P(x)]，连续，严格递减函数

P(x)=1时，I=0；P(x)=0时，I=∞

自信息量I(x)=loga1/P(x)=-logaP(x)

若a=2，信息量单位为bit，简称b

若a=e，信息量单位为nat

若a=10，信息量单位为Hartley

自信息量说明：1、事件x发生以前，事件发生的不确定性的大小；2、事件x发生以后，事件x所含或所能提供的信息量（无噪）

n 平均信息量H(x)=-Σpi log2pi (bit) i=1

信息量I=信息数n×平均信息量H

假设S为信源，H(S)为信源S的熵

信源的熵可以指

信源输出后消息所提供的平均信息量

信源输出前信源的平均不确定性

投6面骰子的熵H≈2.585bit

投硬币的熵H=1bit

任意消息的信息量由用于传输该消息的1和0的数量构成

石头上摔鸡蛋的熵H=0bit

信息的随机性

编码

定义：任意消息都可只用1和0这两个符号构成的字符串表示，这种表示即编码

基本解释

将符号0解释为假（F），将符号1解释为真（T）

布尔运算

异或xor

非not

或or

与and

位运算

数字电路实现

将0-1串解释为数值，称为二进制

1GB=1024MB,1MB=1024KB,1KB=1024B,1B（字节）=8b（位）

二进制运算

进制转换

16进制、8进制、2进制、10进制转换

信息的数字化：将声、光、电、磁等信号及语言、图像、报文等信息转变成为0-1符号串编码后进行处理、存储、传递

数值的数字化

二进制转换为十进制

十进制转换为二进制

整数转换：除2取余法

小数转换：乘2取整法

不能精确表示

二进制位数越高，表示精度越高

即使位数足够，部分小数仍然无法精确表示

浮点数表示实数

计算机数值表示

带符号不含小数点的数值编码方式

正数的原码、反码、补码完全相同

原码

最多表示2n次方-1个整数，8位原码表示255个数，-127~+127

0有两种表示：000...0和100...0

简单直观，便于理解

反码（过渡形式）

负数的反码由原码数字部分按位取反

补码

最多表示2n次方个整数，8位原码表示256个数，-128~+127

负数补码为其反码加1

0有一种表示：000...0

100...0表示其所能表达的最小整数

加减运算简单

补码的运算

[X+Y]补=[X]补+[Y]补

[X-Y]补=[X]补+[-Y]补

补码减法由加法实现

补码加法时，数位符同样参与运算，进位自动忽略

补码运算的溢出

当加法两个操作数符号位相同，结果的符号位相反时时，则出现溢出

补码的原理

引入模module的概念，模运算（A+B）mod C

小数点的处理方法

定点数格式

表示整数和纯小数

一个定点数只有一个编码，可以是原码或者补码

浮点数格式

表示整数、纯小数和混合数

科学计数法

对于R进制，任何一个有穷数可表示为M×RE

M尾数

纯小数，用原码（或补码）表示

E阶码

整数，用补码表示

阶码位于尾数之前

一般的，阶码补码8位2进制，尾数原码16位二进制

尾数原码时，非0数规格化编码最高位为1

尾数补码时，正数规格化编码最高位为1，负数编码最高位为0

字符的数字化

标准编码方案

ASCII

GB2312-80

GBK

GB18030-2000(GB2K)

GB2312解决问题：1、汉字排序问题；2、编码形式问题（基于区位码）

区位码=区码+位码

Unicode

统一码，2006年最新版本Unicode 5.0.0

汉字能够进一步扩充

声音的数字化

模拟量描述：振幅、周期、频率

定义：把模拟声音信号转换为数字音频的过程

三个步骤：采样、量化、编码

影响数字音频质量因素

采样频率：采样频率越高，声音还原质量越好

奈奎斯特Nyquist采样定理：只要采样频率不低于声音信号最高频率的两倍，就能够由采样信号还原成原来的声音

量化位数（采样精度）：量化位数越高，声音振幅划分越细，失真越小

声道数：声道数越多，效果更丰富

音频数字量计算

音频数字量（字节）=（采样频率Hz×量化位数×声道数×持续时间s）/8

音频压缩

图像的数字化

量化方法不同，颜色模型不同

RGB

相加混色模型

显示器选用

颜色=R%+G%+B%

CMY(K)

相减混色模型

印刷体选用

定义：把连续图像转换成计算机能够记录和处理的数字图像的过程

三个步骤：采样、量化、编码

影响数字图像质量因素

图像分辨率：数字图像的像素数量

扫描分辨率

屏幕分辨率

像素（位）深度：表示每个像素颜色所使用的二进制位数bit

24位：真彩色图像

8位：256颜色

1位：黑白

灰度图像（8、16、16位灰度）

图像数字量计算

图像数字量（字节）=（图像总像素×像素深度）/8

图像数据压缩

信息处理

数据压缩

行程编码：重复的数据用该值以及重复的次数（行程长度）来代替

无损压缩和有损压缩

生成图像验证码

绘制分形图形

计算机系统

概述

计算机定义：计算机是一种可编程机器，它接收输入，存储并处理数据，然后按某种有意义的格式进行输出

可编程：能给计算机下一系列命令，并且这些命令能够被保存在计算机中，并在某个时刻能被取出执行

计算机系统一般组成

硬件系统

主机

中央处理器

内存储器

总线

输入输出接口I/O

外部设备

外存储器

输入设备

输出设备

其他

软件系统

系统软件

操作系统

系统应用程序

应用软件

硬件系统结构：冯诺依曼体系结构

核心思想：存储程序，不需改变机器结构，就能使其具备各种功能

把程序从控制器中剥离出来，将程序和数据以同样形式存储于主存中

体系结构组成5部分

存储器

运算器

控制器

输入设备

输出设备

软件系统

软件定义：是在计算机系统支持下，能够完成特定功能和性能的程序、数据和相关的文档

软件=知识+程序+数据+文档

软件是抽象的逻辑产品，而不是物理产品

分类

系统软件和应用软件

实时软件和非实时软件

单机软件和网络软件

事务处理软件、科学和工程计算软件

基于传统算法的软件和基于符号演算和推理规则的人工智能软件

分层结构

<硬件系统>

系统软件

支撑软件

应用软件

计算机硬件系统

中央处理器CPU

对应控制器和运算器

组成

算数逻辑运算器ALU

实现数据的算数运算和逻辑运算

计算结果存储于寄存器组

控制单元CU

功能：指令的分析、指令及操作数的传送、产生控制和协调整个CPU工作所需的时序逻辑

组成

指令寄存器IR

指令译码器ID

操作控制器OC

运转流程：OC从主存取指令-存放于IR中-ID译码出操作码和操作数； 操作码控制ALU运算、传输数据，通过OC发送控制信号； 操作数送至ALU进行运算，在OC控制下保存到寄存器中。

寄存器组

1、通用寄存器

2、专用寄存器

寄存器组中寄存器数量是有限的

CPU内部总线

定义：总线是一组导线，是各种公共信号线的集合

数据总线DB

地址总线AB

控制总线CB

指令

CPU执行的最小单位

组成

操作码

操作数

CPU的指令是由指令集体系结构ISA规定的

ISA是与程序设计有关的计算机结构的一部分

指令系统包括：复杂指令集CISC和精简指令集RISC

程序（尤其指ASM）：用于控制计算机行为完成某种任务的指令序列

三种指令类型

操作指令

数据移动指令

控制指令

CPU工作过程

循环执行指令的过程

指令的执行过程是在控制单元的控制下精确、逐步完成的

指令周期：执行的步骤顺序

每一步称为一个节拍

四个阶段

取指令

译码

执行

写结果

时钟周期

节拍细化后分为的每个动作占一个时钟周期

3.3GHz即33亿个指令周期

存储系统

主存储器(内存)

对应存储器

组成

存储体

由若干主存单元组成

主存地址：可根据主存地址独立对各单元数据进行读写，访问时间和访问地址无关

易失性存储器

主存又称随机访问存储器RAM

不断充电刷新保持信息存储的叫动态存储器Dynamic RAM

非易失性存储器

只读存储器ROM

主存容量

存储器访问时间

存储周期

外围电路

数据寄存器MDR

地址寄存器MAR

辅存储器(外存)

存放永久保存的数据

后备存储器

高速缓冲存储器Cache

介于CPU和主存之间，可在CPU内，也可在CPU外

L1（CPU内），L2（CPU外）两级高速缓存

理论基础为局部性原理，即CPU对主存的访问总是局限在整个贮存的某个部分中

存储系统的分层概念

顶端CPU内寄存器，而后依次SRAM，DRAM，disk，tape

总线

对应互连线，传输命令和数据

定义：连接计算机各部件的一组电子管道，负责在各个部件之间传递信息

特点：公用性

总线分类方式

传输数据不同

数据总线、地址总线、控制总线

位置和连接设备不同

内部总线

系统总线

ISA,PCI,AGP,PCI-E

外部I/O总线

Centronics,RS-232,USB,IEEE-1394，IDE,SCSI

总线特性

物理特性

功能特性

电气特性

时间特性

总线性能指标

3、总线宽度

2、总线频率

1、总线带宽

总线带宽MB/s=总线频率MHz×总线宽度b/8

输入输出系统

组成：输入输出控制器、控制软件、设备

控制方式

程序查询方式

程序中断方式

节省CPU时间

适用于随机出现的服务

直接主存访问方式DMA

硬件执行I/O交换

需要更多硬件，适用于主存和高速外围设备之间大批量数据交换

传输数据三步走：预处理、正式传送和后处理

DMA接管时，CPU访问的console：停止CPU访问主存、周期挪用和MDA和CPU交替访问主存

操作系统

在计算机系统中的作用：资源管理者和用户接口双重角色

资源管理者

硬件资源：处理机、存储器、输入输出设备

软件资源：信息（通常是文件）

主要工作：跟踪资源状态、分配资源、回收资源和保护资源

用户接口

操作系统的体系结构

Shell外壳

用于操作系统和用户的通信，提供各种命令供用户使用

内核

功能：处理机管理、存储管理、设备管理、文件管理

常用操作系统：Windows，UNIX，Linux，Mac OS，Android

进程管理

进程是对正在运行的程序的一种抽象，是资源分配和独立运行的基本单位

进程管理很大程度上是对CPU的管理，即如何将CPU分配给程序使其能够运行

多任务操作系统->程序并发执行

处理能力增加

进程：可并发执行的程序在一个数据集合上的运行过程，是资源分配和调度的一个独立单位

进程特性：动态性、并发性、结构特性、独立性、不确定性

进程分类：系统进程和用户进程

系统进程是操作系统用来管理系统资源活动的并发过程

用户进程是操作系统提供服务的对象，是系统资源的实际使用者

进程和程序的联系和区别

4、进程和程序密切相关 同一程序多次运行，对应多个进程 一个进程可以通过调用激活多个程序

3、进程与程序的组成不同 进程包括程序、数据和进程控制块PCB 程序是一组指令的有序集

2、进程是暂时的，程序是永久的

1、进程是动态的，程序是静态的

运行中的进程三种状态

运行状态：正在CPU中运行的状态，此时进程已获取资源

阻塞状态：进程等待某事件完成而暂时不能运行的状态

就绪状态：等待CPU的状态

就绪队列

资源等待队列

各状态间并非都可以互相转换

进程管理的主要任务

4、唤醒进程

3、阻塞进程

2、撤销进程

1、创建进程

5进程调度

按照某种策略选择一个进程，使其获得CPU的工作称为进程调度，常用调度策略：

先来先服务

时间片轮转

优先级法

多级反馈队列轮转

管理进程的专用数据结构：进程控制块PCB

PCB为进程存在的唯一标志

进程存在生命周期

存储管理

操作系统对存储系统的管理，主要是指对主存储器的管理

主要目的：1、满足多个用户对主存的要求，使多个程序都能运行；2、方便用户使用内存

实现功能

3、主存区域保护

2、逻辑地址到物理地址转换

1、主存分配回收

4、主存逻辑扩充

虚拟存储管理技术

把有限的主存空间和大容量外存统一管理，构成大容量虚拟存储器

解决主存空间容量不足的问题，扩充主存空间

理论依据：程序的局部有限性原理，80%的时间只访问20%的代码。一个程序运行时，将当前运行所必须的部分程序和数据存入主存，其他存于外存，当所访问信息不在主存时，系统将自动将其从外存调入主存，主存中暂时不用的信息也可调至外存，以腾出空间供其他程序使用

如主存大小64MB，地址总线32位，虚存最大容量为2的32次方B=4GB

文件管理

对软件资源进行管理

软件以文件形式存储

文件定义：存储在外部存储介质上的、具有符号名的一组相关信息的集合。

文件包括：文件内容和文件属性

文件分类

按用途分类：系统文件、库文件、用户文件

按性质分类：普通文件、目录文件、特殊文件

按保护级别分类：只读文件、读写文件、可执行文件、不保护文件

按文件数据形式分类：源文件、目标文件、可执行文件

文件目录项：文件控制块FCB

FCB包括：文件存取控制信息、文件结构信息、文件使用信息、文件管理信息

常见文件操作：创建、删除、截断、读、写、读写定位、打开、关闭

文件系统：对文件实施管理、控制与操作的一组软件。

目录：文件的集合，同时自身也是文件

常见目录操作：创建、删除、检索、打开、关闭

文件系统主要功能：1、实现文件按名存取；2、分配和管理文件存储空间；3、建立并维护文件目录； 4、提供合适的文件存取方法；5、实现文件的共享与保护；6、提供用户使用文件的接口。

设备管理

按照共享属性将设备分类为：独占设备、共享设备、虚拟设备

逻辑设备名->物理设备名

操作系统进行地址转换完成

实现了设备无关性

Windows的设备管理器实现

其他管理功能：数据交换、提供接口、统一管理设备、设备分配与释放

操作系统把输入输出软件分为：中断处理程序、设备驱动程序、设备无关的I/O软件、用户软件四个层次

用户接口

人机接口

命令控制界面

命令行界面CLI

脱机控制方式和联机控制方式

图形用户界面GUI

窗口管理器是核心

API接口

由一组系统调用组成

以程序库的方式出现

操作系统的加载

通过自举完成

自举程序存储于只读存储器ROM中

主要功能：指导CPU将外存上某特定区域的操作系统加载到主存中，并在加载完成后修改CPU指令计数器，使其指向操作系统在主存中的地址

其他程序也保存于ROM中

所有这些程序被称为基本输入输出系统BIOS(BASIC I/O System)

利用python使用操作系统

psutil模块

import psutil

查看进程信息、查看系统存储信息、文件操作等

计算机网络及应用

计算机网络基础

发展史

60s-70s

萌芽：面向终端的计算机网络

主从式网络

70s

计算机局域网形成

多级互联网络-多处理机为中心

ARPAnet：资源子网和通信子网

80s

成熟：计算机局域网络产品化和标准化

7层OSI模型框架1977年提出，1984年发布，促成全网互联

90s至今

更加成熟，Internet诞生

数字信号出现和光纤接入

美国国家信息基础设施NII

分类

按网络传输技术分类

广播式网络和点对点式网络

按传输速率分类

高速网（宽带网）和低速网（窄带网）

按传输介质分类

有线网和无线网

按规模和覆盖范围分类

局域网(Local Area Network)LAN、城域网MAN(Metropolitan Area Network)和广域网(WAN,Wide Area Network)WAN

按网络拓扑结构分类

总线形、星形、环形网络，以及在此基础上的树形和网状网络

令牌环网

按服务模式分类

对等网、客户机/服务器（C/S）、专用服务器

按管理性质分类

公用网、专用网和利用公用网组建的专用网

计算机网络体系结构和协议

为进行网络数据交换而建立的规则、标准或约定称为网络协议

网络协议三要素：语法、语义、同步

体系结构

计算机网络的体系结构指计算机网络各层次及其协议的集合

物理媒体上为实通信。其它层均为虚通信

为何分层：复杂系统分解、功能分层、相对独立、屏蔽细节、利于交流、理解和标准化

常见体系结构：ISO/OSI, V Series,X Series, 802 Series

ISO/OSI体系结构

七个协议层

物理层

依赖网络，实现通信子网功能

数据链路层

传统的交换机制所在层

网络层

路由概念

传输层

最重要的一层，唯一负责总体数据传输和控制的层

会话层

表示层

应用层

面向应用，实现资源子网功能

应用层到物理层的封装

名字指出我们所要寻找的资源，地址指出资源在哪，路由告诉我们如何到达

计算机网络传输介质及设备

主要介质：双绞线、同轴电缆、光导纤维

双绞线分屏蔽双绞线和非屏蔽双绞线，适用于短距传输

同轴电缆常用于总线型拓扑结构

常见网络设备

网络接口卡NIC

有地址，且全球唯一，称为介质访问控制（Media Access Control，MAC）地址

集线器Hub

物理层设备

网桥Bridge

数据链路层设备

交换机Switch

数据链路层设备

路由器Router

网络层设备

网关Gateway

不是完全意义上的网络硬件，更像软件硬件的综合

Internet基础

概述

技术上来看，Internet是一个网络的合集

凡是采用TCP/IP协议并且能够与Internet中任何一台主机进行通信的计算机都可看作是Internet的一部分

优点：灵活多样的入网方式、造就了网络服务的灵活性、多种技术融合、资源丰富、功能最强的信息网络

接入互联网方式

公共交换电话网ISP-RAS

综合业务数字网ISDN

非对称数字用户线ASDL

线缆调制解调器Cable-Modem

局域网

TCP/IP协议

Internet基础协议

参考OSI，为分层结构

网络接口层（数据链路层）

对应物理层和数据链路层

网络层（IP层）

对应网络层

传输层

提供应用层之间的通信，即端到端的通信

应用层

实质是一个协议簇

TCP和UDP是两个传输层协议

TCP为可靠性传输，UDP为不可靠传输

IP是网络层协议

被TCP和UDP使用

ICMP是IP协议的附属协议

IGMP用来把UDP数据报多播到多台主机

ARP和RARP是某些网络接口用的特殊协议

应用层协议：FTP,SMTP,Telnet

采用分组交换技术，将用户数据划分为若干组，并以组为单位进行传输和交换

IP地址

32位二进制数，以点分十进制表示

由网络标识和主机标识组成

网络标识和主机标识不能全为1或者全为0， 主机标识全为0代表是本网段的网络地址号， 全为1代表本网段的广播地址

五类IP地址，互联网常用的为ABC3类，D类多用于广域网，E类为保留地址

A类地址，前8位为网络标识，且前1位为0，后24位为主机标识， 网络标识范围：1~126（127为保留地址）， 主机标识范围：0.0.1~255.255.254

B类地址，前16位为网络标识，且前2位为10，后16位为主机标识， 网络标识范围：128.0~191.255， 主机标识范围：0.1~255.254

C类地址，前24位为网络标识，且前3位为110，后8位为主机标识， 网络标识范围：192.0.0~223.255.255， 主机标识范围：1~254

D类地址，前4位为1110，多点广播地址，后28位为小组标识， 地址范围：224.0.0.0~239.255.255.255

E类地址，前5位为11110，保留地址， 地址范围：240.0.0.0~255.255.255.255

按用途划分为私有地址和公有地址

公有地址在广域网使用，在局域网也能使用

私有地址只能在局域网使用

A类私有地址：10.0.0.1~10.255.255.254

B类私有地址：172.16.0.1~172.31.255.254

C类私有地址：192.168.0.1~192.168.255.254

主机标识再细分

为便于管理分为子网标识和主机标识

子网掩码的概念

32位字符串，其中值为1的位留给网络标识和子网标识，值为0的位留给主机标识

通过“按位与”实现完成识别IP地址的网络标识和主机标识

IP地址和子网掩码按位与得到网络标识

IP地址和子网掩码的反码按位与得到主机标识

C类地址为192.9.200.13，子网掩码为255.255.255.0，则 IP地址和子网掩码按位与得到192.9.200.0， 其中前24位属于网络标识，即192.9.200， 与子网掩码取反按位与得到0.0.0.13， 其中后8位属于主机标识，即13

子网的主机标识均为...1~...254的范围， 如C类地址分为四个子网，则四个子网网址范围为： .1~.62； .65~.126； .129~.190； .193~.254； 即不能所有位全为0或1

域名

域名到IP地址的解析称为域名解析，通过域名服务器（Domain Name Server）DNS完成

Internet应用

万维网WWW

world wide web

核心技术

超文本传输协议http

TCP80端口

统一资源定位符url

协议可以是http、ftp等

E-Mail

涉及主要概念

邮件用户代理MUA

邮件传输代理MTA

邮件投递代理MDA

遵循简单邮件传输协议，SMTP

邮局协议版本3，POP3

TCP110端口

FTP

采用客户端/服务器模式

TCP21端口监听

TCP20端口传输

比HTTP协议复杂在于用到两个TCP连接，即控制连接和数据连接

两种工作方式，即主动方式PORT和被动方式PASV

搜索引擎

通国遍历web空间进行扫描

无线网络

通信介质

微波通信

卫星通信

红外通信和激光通信

微波、红外线和激光都需要在发送方和接收方之间建立一条视线通路，所以他们统称视线媒体

无线个人网WPAN

蓝牙

无线局域网WLAN

802.11系列

WIFI商业认证

无线城域网WMAN

802.16系列

多个无线频段

WiMax认证

无线广域网WWAN

802.20和3G,4G,5G等标准

3G：W-CDMA,CDMA2000，TD-SCDMA

4G：LTE-Advanced,802.16m,TD-LTE-Advanced,FDD-LTE-Advanced

物联网IoT

起源于网络无线射频识别系统RFID

概念：物物相连的互联网

以互联网为基础

定义：通过信息传感设备，按约定的协议，把任意物品同互联网相连，进行信息交换和通信，实现对物品的智能化识别、定位、跟踪和管理

基本特征：全面感知、可靠传送、智能处理

3项关键技术：传感器技术、RFID技术、嵌入式系统技术

体系结构分层：感知层、网络层、应用层

姓名

教师编号

教师

讲授

性别

学时

课程名称

课程编号

成绩

籍贯

姓名

学号

课程

学习

学生

H

D

F

G

E

C

B

A

TCP/IP模型

应用层

传输层（TCP/UDP）

网络层（IP层）

网络接口层（数据链路层）

OSI参考模型

应用层

表示层

会话层

传输层

网络层

数据链路层

物理层

线性链表

存储不连续

不需初始化（固定存储空间）

插入删除不需移动表中元素，方便快捷

占用空间大

不能随机访问

树

每个节点有零个或多个子节点；

有且仅有一个根结点（没有父节点的节点称为根节点）；

每一个非根节点有且只有一个父节点；

除了根节点外，每个子节点可以分为多个不相交的子树；

二叉树

特性

每个结点最多有两颗子树，结点的度最大为2。

左子树和右子树是有顺序的，次序不能颠倒。

即使某结点只有一个子树，也要区分左右子树。

逻辑形态（递归）

空二叉树

只有根节点的二叉树

只有左子树

只有右子树

完全二叉树： 叶子节点只可能出现在层序最大的两层上，并且某个节点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1

满二叉树： 如果一棵二叉树只有度为0的节点和度为2的节点，并且度为0的节点在同一层上，则这棵二叉树为满二叉树

相关概念

根节点

分支节点：非终端

叶结点：终端

遍历

前序遍历

访问根结点的操作发生在遍历其左右子树之前ABDEGCFH(根开左右下到底)

中序遍历

访问根结点的操作发生在遍历其左右子树之中DBGEACHF(左父右画倒三角)

后序遍历

访问根结点的操作发生在遍历其左右子树之后DGEBHFCA(先左再右最后父)

层序遍历

一层一层的遍历ABCDEFGH