计算机科学概论（美）布鲁克希尔 这本书非常推荐大家去读一下，作者用非常浅显易懂的语言让你能够对计算机领域有一个全面的认识和了解，我在研一时候读的，这本书让我受益匪浅，对本科学的计算机知识能够串联在一起，也非常入门者读，一定物有所值。
我将此书的第11版中文电子版.pdf放到了网盘

链接：https://pan.baidu.com/s/18c4qrHsoF_B1y3zVygtH5g

提取码：a0ki

绪论

算法：就是完成一项任务所需要的步骤

一旦一个算法被设计出来，那么完成任务就变成了按照指令执行的过程

所以说计算机的智能限制于算法的智能

总结

其实计算机就是一个能够存储（主存）并且处理数据（cpu）的一个机器

Cpu其实就是能够处理数据（指令也是数据），有着控制电路去完成指令（也就是一种机器语言）所指定的操作----说白了就是读取指令数据，根据指令来操作

然后附加的都是外围设备，比如 海存磁盘，鼠标，键盘，显示器等等----这些靠控制器来控制

然后呢，操作系统就是用户与计算机之间的媒介，用户通过操作系统这个软件来使用计算机这台机器，并完成自己的需求

第一章数据存储

如何编码和存储

1.1位和位存储

1.1.1 布尔运算

位 0或1 把01看成真与假的话，那么对位的操作就是布尔运算

3个基本的布尔运算：与 或 异或（进行的是逻辑值的运算）

1.1.2 门和触发器

就是位模式如何存储的

门：可以进行布尔运算的电路

而后者是更复杂的电路（由门组合而成）—能够产生一个0，1的输出—那么它就可以用来存储二进制位（因为还可以通过改变电脉冲来改变它的输出的值）

1.1.3位模式的表示

十六进制计数法----就是用来表示位模式

也就是用一个符号来表示4个位（2的4次方=16 16种组合）

另一种表示位模式的方法是点分十进制—一个字节一个10进制的数

1.2主存储器

主存储器是以称为存储单元的可管理单位组织起来的（一般就是一个字节，8位）

0100 0110

高-----低(最左边是低端位)

那么每个存储单元都有地址（也就是给它的编号），然后顺序排列起来的

除了像触发器那样的存储电路以外，还有就是可以进行读写数据的电路

RAM(random access memory)随机存取存储器----需要拥有刷新电路，具有不稳定性

也就是因为主存的存储单元是独立的有编号的单元，所以它就可以用任何顺序访问存储单元

存储的时候是2的幂会很方便—所以存储的单位是1024

主存储器一般都是电路啊，快速消散电荷啊来存储位的，所以需要刷新电路—就是在1s能够反复的补充电荷很多次

1.3海量存储器

海存有：磁盘 CD sd卡

首先相比主存，它不是电子器件来存储的，一般也做的是机械（物理运动）

磁盘：磁道 扇区 读写磁头

磁道和扇区的划分不是固定化的----它是通过磁盘格式化来磁化形成的

Cd:光学 螺旋式读取数据（所以适合读取连续的数据）

物理记录（就是符合磁盘存储的数据单元） 逻辑记录（实际上信息的单元，比如员工信息）

主存中有缓存区，来保存一部分海存中的文件-----以保证我们是按照逻辑记录来存取的

1.4用位模式表示信息

1.4.1 文本的存储

其实我们就是把文本看作符号，每一个符号都有对应的一个唯一的位模式----这就是编码

这个样子文本就能够用一串位串来表示

但是不同的编码体系，一个符号所对应的位模式也不同

而一个文本也只能呈现一种编码机制

Ascii码一开始一个字符7字节，后来8 再后来出现了unicode—16字节（2^16=65536个字符，可以表示中文等语言）

1.4.2数值的表示

二进制计数法

为什么不把数值也当作字符存储呢？以25为例，相当于两个字符，需要2个字节，并且2个字节所能表示最大的数是99

而我们使用二进制计数法的话 2个字节可以存储0~65535的任意数字

二进制补码—存储整数 浮点计数法—存储带有分数部分的数

1.4.3图像的表示

点（像素）的集合----位图 rgb编码方式 矢量编码方式

1.4.4 声音的表示

固定时间间隔对声波频率的数据的采集—这个是收录声音

但是电子音乐合成器—是编码了乐器本身，而不是音乐本身

1.5二进制系统

10进制的数如何转换为二进制—求余

二进制系统中的小数

小数点后面分别是 2^-1 2^-2 所以它很难表现0.1这样子的数（就是 10^-1）

二进制补码

使用二进制补码的话，一个加法电路和一个取反电路就可以解决加法和减法的问题了

溢出 不是说位数溢出了，而是说结果不对 比如正正得负

1.6整数存储

一般计算机中整数使用二进制补码记数法来表示

就是比如4位数，就用这4位数的组合来表示整数

1.7小数的存储

1.8数据压缩

无损哈夫曼编码，字典编码 和有损

图像压缩----就是GIF（将颜色限制在256色块中）JPEG—就是像素点取平均值

1.9通信差错

奇偶校验位—可以用来检错

纠错编码—既能发现差错，又能纠正差错

就有一个概念就是数字技术和模拟技术

数字技术就是：像字符一样单独存储数值的每一位

模拟技术就是：用一连串的位来表示一个数值（也就是一个单元就存储了一个数值）

数字技术相比模拟技术对错误 的容忍率更高

第二章数据操作

如何操作数据以及如何与外围设备通信

2.1计算机体系结构

2.1.1CPU基础知识

Cpu（central processing unit）中央处理器—控制数据操作的处理器（就是一个小芯片）—包含3个部分 控制单元（协调机器活动的电路） 算术/逻辑单元（进行运算的电路） 寄存器

Cpu和主存储器之间连着一条总线 从主存储器中读取数据到寄存器，进行操作

2.1.2存储程序的概念

一开始要执行的步骤内置于控制单元当中，这个样子步骤更改cpu中的控制单元也得修改（就是对它的电路重新布线）

程序就像数据一样

后来冯诺依曼想出了程序像数据一样也存储在主存中，这个样子就可以读取程序，将指令解码来执行它们，然后程序也可以像数据一样很方便的修改

指令构成程序，程序有很多个指令组成

比如一个程序是a+b

那么指令就是：读取a 读取b a和b加法电路 输出结果

寄存器中存放正在使用的数据 主存中是即将用到的数据（数据可能是程序，可能是数据）

CPU高速缓存器：

Cpu****寄存器----cpu的高速缓存器(寄存器的一部分)----主存

主存-----主存的缓存-----海存

提取 解码 执行 写回

2.2机器语言

机器所能识别的指令----这些指令是由二进制编码的

而指令以及它的编码系统称为机器语言****----说明变成指令就是机器语言的形式了

两种CPU体系结构： 复杂指令集 简单指令集

Cpu生产者：intel AMD

指令就是一些操作呀，指令一般分为3类（1）控制类（2）算术/逻辑类（3）数据传输类

（1）指导程序执行 （2）进行运算 （3）请求进行数据的传输（本质是复制）

Cpu所能执行的指令集根据复杂与否可以分为 简单指令集 如 amd

复杂指令集 如intel

指令由操作码和操作数组成，表示了要实现的动作，以及对应的动作更详细的信息

比如 3 5 A 7 （16进制形式）

3表示指令类型为存储 5表示了存储位模式的cpu寄存器 A7表示存储到主存的这个地址中 所以就是：把寄存器5中的数据存储到主存中的A7地址中去

Cpu的位数是指什么意思？

32位和64位操作系统是指：CPU一次处理数据的能力是32位还是64位。现在市场上的CPU一般都是64位的，但是这些CPU并不是真正意义上的64 位CPU，里面依然保留了大部分32位的技术，只是进行了部分64位的改进。32位和64位的区别还涉及了内存的寻址方面，32位系统的最大寻址空间是2^32（bit）= 4（GB）左右，就是指它最大能映射到4GB的内存空间，而64位系统的最大寻址空间的寻址空间则达到了2的64次方（bit）=数值大于1亿GB。换而言之，就是说32位系统的处理器最大只支持到4G内存，而64位系统最大支持的内存高 达亿位数。

2.3程序执行

计算机会按照需要把存储器中的指令复制到cpu中（来执行存储器中的程序），cpu再解码指令再执行

就是cpu不断的读取指令，解析指令，并执行

Cpu有两个专用的寄存器：指令寄存器和程序计数器 从主存中读取指令

2.4算术/逻辑指令

算术/逻辑指令 包含：算术 逻辑（与 或 异或） 移位

2.4.1逻辑运算

与----应用：进行屏蔽----掩码（就是需要遮盖的地方都变成1）；复制位串的一部分

异或----能够求反码（就是和全1的位串进行异或，得到的就是反码）

2.4.3算术运算

就是加减乘除

其实减法可以用加法和取反实现 而乘法就是反复进行加法运算 减法就是反复进行减法运算（6可以减3次2 所以6/2=3）

每种算术运算都有许多种变体：

比如加法，如果数值使用二进制补码记数法----就是直接按位相加

按照浮点记数法----就是得获取尾数，然后根据指数字段来知道小数点的位置，然后相加以后再按照浮点记数法存储

2.5与其他设备通信

主存储器和cpu是计算机的核心

计算机的三大组件：主存 cpu 输入/输出（I/O）设备（其实像磁盘，打印机，鼠标，键盘，显示器都是）

2.5.1控制器的作用

外围设备也是通过控制器来控制的，控制器通过总线连接到cpu和主存的总线上（比如usb控制器）

控制器是一个中间设备，它可能是固定在主板上的电路，也可能是插件式的

USB（universal serial bus）通用串行总线----这个子一个USB控制器就可以控制多种的设备，只要这些设备能够查到USB接口上（这就相当于标准化了）

控制器本身就是一个小型计算机，都有自己的存储电路和简单的cpu—因为也是要去控制一个设备呢对吧

Cpu通过这些总线，就像和主存储器通信一样和各种外部设备通信

然后也是cpu通过专用的控制其他设备的指令（I/O指令）来操作其他设备的数据程序—也就是通过控制器与外围设备进行输入/出

然后控制I/O设备的过程就是：操作系统—驱动程序—驱动控制器—控制

2.5.2直接内存存取

控制器通过总线直接与主存储器进行通信----缺点：CPU与控制器竞争总线存取

2.5.3握手

就是为了解决不同设备之间传输速度不相同的问题—所以握手就是双向通信，告知对方自己的情况----会涉及到位图

2.5.4流行的通信媒介

通信形式包括两种：并行 串行—就是一个信号接着一个信号

近距离usb(串行) 较近距离 以太网（串行）

远距离 电话线 电缆 光纤 等等

2.5.5通信速率

传输数据位的速率是bit/s 1kbit/s=10^3bit/s 要区分b与B（位与字节）

2.6其他体系结构

第三章操作系统

操作系统就是用来协调计算机整体的运行-----让计算机这个硬件变成一个有用的工具

其实就是用户和计算机之间的媒介，用户有需求，然后用户通过操作系统来告诉计算机来做什么

操作系统把用户要完成的程序从海存中调到主存中，并让cpu执行----它来管理如何去完成这些任务（是批处理还是分时，并且如何使用主存----当程序多的时候）

3.1操作系统的发展历史

首先就是一个程序的执行叫做作业，一开始就是批处理么，也就是有一个队列，然后大家排队（操作系统的功能就是接收到这些作业，然后一个着一个执行）

但是这个样子没办法进行交互，所以出现了实时响应（就是得强制响应），然后为了同时相应多个请求，就出现了多道程序设计，分时间片（分时）

这个是核心思想，也就是让cpu在不同的进程间来回切换----来实现“并行”处理

3.2操作系统体系结构

软件：系统软件和应用软件------操作系统本质上就是一个软件----也就是一个让cpu一直在执行的一个程序（开机后）

操作系统组成：

操作系统分为用户界面**（shell 命令行形式 和GUI graphical user interface就是图形化）**和内核

操作系统的内核的主要功能

（1）文件目录管理

（2）内存管理（就是如何分配内存，找到需求并为它们分配空间，并且限制它们所能使用的空间；当内存不够大的时候还需要进行页面调度，就是在海存中按照内存的格式来存储数据，这个单位就叫做页面，然后数据就在内存和海存之间来回切换，所迫切需要的4GB一定会在内存中，然后相当于有了虚拟内存）

（3）外围设备驱动程序(操作系统中的驱动程序----驱动程序来控制驱动器进而控制外围设备)

（4）调度 就是程序执行的顺序

（5）分派 程序活动时间的分配

3.2.3系统启动

如何启动操作系统？----目的就是让cpu最先启动操作系统

操作系统存储在海量存储器中

主存储器具有可失性，故分出一片区域称为ROM（read only memory只读存储器），即可长期保存，只读，不容易被修改

程序计数器一般被初始化为特定的地址，以使cpu能够执行第一条指令，来实现初始程序。

引导程序（booting）就存储在ROM中，开机后最先实现这个程序

功能：引导cpu将操作系统从海存中调度到主存中，然后cpu执行跳转指令，转到操作系统这个程序的存储区，操作系统就会接管并开始控制计算机的活动。

为什么操作系统存储在海存中？

首先主存具有可失性 其次若全部存在主存中，降低了主存的性能

再次操作系统需要经常更新，所以存放在海存中

固件（固件程序）

ROM中还存放着的一组程序，用于初始化i/o设备，为操作系统的启动做准备

因为这种程序既不是硬件，也不是存储在海量中的那些软件那样易修改----故被称之为固件----可以被引导程序所使用

就是在操作系统启动前，实现基本的输入输出（如键盘的输入，显示器的文本显示，从海存磁盘中读取数据等）

常用的固件系统：BIOS EFI CFE

3.3协调机器的活动

程序和进程

程序 和 进程

程序:一组静态的指令 软件=程序+文档

进程：程序的动态的活动

进程状态：某时刻进程的信息，或者说，某时刻下，机器的快照

操作系统管理进程

操作系统管理进程的两个程序; 调度程序 分派程序-----就是控制执行顺序+时间分配

调：控制哪些活动可以执行，以及执行顺序

分：控制给这些活动的时间分配

如何实现进程的管理？----调度程序

1.调度程序会在主存中维护一个进程表（就是进程对应的信息），存储进程的执行状态（就绪：可以执行，等待：因为要等待某个外部事件而发生中断）和它对应的存储区以及优先级------->产生就绪队列

2.用户每发出一个请求就把这个进程放入到进程池里面（其实就相当于一个作业的大池子）

查看window的任务管理器就能看到进程池----你能看到有多少的进程，并且**分配了多少的内存（这个是由内存管理程序分配给它的）**以及进程对应的状态

你会发现很多操作系统进程和用户进程

3.Cpu会按照进程表，执行里面的状态为就绪的进程

多道程序设计的实现

分派任务或者说多道程序设计是如何实现的？----操作系统的分派程序

即在分时/多任务操作系统中

将时间划分为多个时间片，每个进程被分配一个时间片，然后cpu依次执行它们——进程切换/上下文切换

如何在进程间跳转呢？

分派程序给每个进程分配一个时间片，使用中断程序（分派程序的一部分），中断程序会发出中断信号来指示时间片的结束，使cpu在执行完时间片后保存当前的进程信息，然后切换至下一个---->进程切换/上下文切换

中断信号使控制权从进程重新回到分派程序，然后分派程序从就绪队列（调度程序维护的）里面找优先级最好的进行来让cpu执行

事实上，中断已经成为一种处理事务的机制，如**点击鼠标等都可以产生中断来让cpu响应。**中断也分优先级，最高的和电源故障有关。

多道程序设计的优点？

\1. 能够停止进程，并重新启动它（这个重现启动的功能是cpu实现的—就是保存之前的信息，也从侧面佐证了操作系统对cpu的影响，它保存了中断前的进程的状态）

\2. 相比进程顺序执行----即进程必须等着进程再执行 ‘并行’提高了效率。

**也就是我们能够利用等待的时间去完成别的任务—**这允许比如程序在等待i/o请求时，或者等着用户输入下一个响应才能执行的进程还能够执行其他的任务

第四章 组网及因特网

**内容：**网络的结构与操作 应用 及网络安全问题 重点：因特网

4.1网络基础

4.1因特网

4.3万维网

4.4因特网协议

4.5安全性

4.1网络基础

网络的分类

第一种 LAN局域网 MAN城域网 WAN广域网

第二种 公开与否 公开的—例因特网 专用的

因特网提供了一组TCP/IP协议群，允许计算机通过这些标准来连接到因特网上

第三种 按照拓扑类型，即计算机的连接模式

总线型：各个计算机连接到一条总线上，直接进行通信 应用：以太网

星型;各个计算机连接到一个中心上，通过它来实现间接通信 应用：无线网络

如：连接到因特网的多数用户住宅wifi网络 那个路由器就是中心接入点

以上也是二者的主要区别----即直接通信还是间接通信

两者在物理上有时候区别并不大，有时候总线型就像星型：

总线型有时候会用到集线器，就时是一个很短的总线，将计算机连接到总线上-----------总线型就是一个计算机发送信息会发给所有的计算机，而所有的计算机也会监听的到

以太网：是一组标准，用于创建总线型的网络

主要提供了 传输报文的格式标准，二进制传输的表示方式以及CSMA/CD对传输的限制

总线型和星型所使用的不同的传输协议

CSMA/CD(detetion) 检测冲突—总线

就是当两个计算机同时都往总线上传输数据时，这个冲突会被检测到，然后计算机会等待一段时间后再重新进行传输

CSMA/CA(avoid) 避免冲突—星型

由于无线范围问题，网络中的计算机不一定能检测到其他计算机的信号，

因此它们每次想传输数据时，不会直接发送，而是会等待一段时间，这段时间信道没有被占用的话就传，如果在这段时间有别的计算机在传，就再等待

这就避免了新来的与已在等待的之间会冲突

总线型网络互联：

使用三种设备 中继器 网桥 交换机

中继器：就是简单的进行转发

网桥：A网络和B网络通过网桥连接起来，仅当A向B发时才向网桥另一端发送数据，这样不会使A，B互相影响，占用信道-----就是能够分段

交换机：提供多条路线的网桥

不同类型之间的网络之间互联----互联网（internet）

注：区别于Internet（因特网）----最大的互联网—相当于一个专有名词

网络不能直接和网络进行连接（因为不同特性的网络有着不同的特性，如星型和总线型以太网控制传输的协议不同），故用路由器进行连接，路由器允许网络之间互联，而不用在意网络内部具体的特性

路由器起到的作用：进行数据的转发 起源地 目的地 路由器会维护一个转发表

这样计算机就既有了本地地址（自己网络内中的地址）又有了外部地址（连入因特网的地址）

网关：一个网络与 互联网链接的点 一般是指路由器，通过它网络能与互联网上其他的网络通信

而对连入因特网的家用wifi网络来说，网关指的是网路的接入点和与接入点相连的路由器

进程间的通信（注意是进程间的通信方式）

有两种形式服务器/客户端模式 p2p模式

区别：服务器客户端模式，服务器会一直处于启动状态，为客户端提供服务

P2P模式常用于用户间实时聊天，用户一起竞技性游戏，以及进行文件的分享（如音乐电影）

往往需要中央分发器，进行所分享的文件的文件，至少让用户找到源

缺乏中央服务器也带来了版权问题

分布式系统

旨在去中心化，没有中央服务器这一说

1.集群计算2.网格计算（耦合度更低）3.云计算—每个计算机作为云的一部分，也可以从云中获取服务，而不需要知道具体是谁。同时也带来了安全隐患。

4.2因特网

因特网体系结构

因特网从一个项目成熟后逐渐成为一个商业服务，连接因特网的服务由ISP（因特网服务提供商）提供，因特网是一个分层的网络，最高两层实际上是路由器组成的网络，用于连接各个具体的网络。

作为底层的实际连入因特网的设备称为终端/主机，它不仅仅指个人计算机，也指很多其他设备，如摄像头等等

因特网实际上就是一个通信的系统

接入因特网不同的方法：

1.拨号入网—使用电话线来接入网络

2.无线广播的卫星系统 有线电视的电缆 专用的电话数据线 光纤----统称宽带技术

3. wifi连接—在接入点进行广播，广播范围内（如覆盖校园的）都可以通过接入点连入网络，这个范围通常称为热点 手机中相似的就是服务区。通过路由器也可以创建本地热点

因特网编址

连接在因特网上的每一台主机都有一个唯一的ip地址，首先组织机构会把ip地址分发给ISP，然后这样使它们分发给细化区域的主机

Ipv4 使用32位来标识地址，利用点分十进制来标记，如192.23.45.12 ，每个数字用来表示8位

而ip地址并不方便记忆，于是出现了域，用来表示某一特定区域--------另一个编码系统

域是向左延伸的，如bjut.edu.cn cn是国际顶级域名，edu表示教育机构（com商业，org非盈利性组织等等），而bjut就是具体的单位所分配到的域

在单位或组织注册/分配到域之后，它可以划分子域来管辖组织内的不同的计算机，如mail.bjut/log.bjut----用于为个体获取助记标识符

域名服务器—对域名到ip进行登记与解析，分配到域的单位可以自己维护域名服务器，也可以使用ISP的域名服务器

所有因特网范围内的域名服务器组成了域名系统（DNS）

因特网应用：

邮箱服务：使用SMTP协议

文件传输：FTP协议 ，首先客户端下载一个ftp软件包，然后它就能连接到文件提供者进行文件的传输 应用：常用来传输非公开的文件----使用口令

远程登录：最初的远程登录包括口令也是通信的一部分，因此SSH是更安全的远程通信

会对传输的数据进行加密，然后验证双方的身份

无线电话的发展：

1G：通过无线电波传递语音信号

2G：用数字信号对语音信号进行编码，并可以传递其他的文字信息如文本

3G：更高的效率，并可以传输视频

4G：完全基于Ip，手机设备相当于一个拥有与计算机相同带宽的一个移动计算机

4.3万维网

概念

超文本文档—包含链接到其他文本的文本文档，链接不仅仅只限于文本，也包含图像，影音等内容，因此又称为 超媒体

而这些相互连接的文档形成了一个网状结构，并且应用至整个因特网范围—形成了万维网（www,web,w3）

一个超文本文档成为网页，多个紧密联系的网页称之为网站

万维网实现

客户端—浏览器，通过浏览器来检索网页，并进行显示

每一个网页都有唯一标识的地址称之为URL—连接到对的服务器和对应的文件

http://www.cnblogs.com/avenwu/archive/2012/01/16/2324175.html

URL包含了很多信息 使用的协议 ，中断主机的标识 目标主机下文件的路径 文件名

有时候也不需要指定特定的细致的地址，直接输一个网站的地址时，会有一个默认显示的页面----主页

服务器—提供用户所需文件的计算机

传输的协议—HTTP，使超文本在客户端和浏览器之间进行传输，就是它们通信的一个规范标准

HTML

网页的内容其实就是普通的字符，但是它使用了一些特殊的标记，来告诉浏览器如何显示它----这个标记系统称之为HTML，超文本标记语言

这告诉浏览器，网页如何显示，需要哪些媒体资源，以及它链接到了哪些其他网页

Html—提供排版格式 浏览器—进行排版的排版工

XML

Html存储的仍是文本信息，就是一个一个字符显示编码的那种----线性的

但有些数据是有自身结构的，比如一段音乐，它没办法一个个字符编码；XML可以标记非文本信息，就是将它们的属性标记为标签

XML允许用户开发独立地标记语言，并能够被识别，修改；两者的区别是一个是基于语义，一个是基于内容

这对搜索引擎来说，有很大的区别；因为使用html的话是基于文字内容来进行搜索；而使用xml是基于语义来搜索

客户端与服务器端的活动

客户端和服务器端除了进行文件页面的显示之外，还需要有更多的交互—客户端/服务器端活动

客户端活动：javascript，flash

服务器端活动：servlet/jsp；asp；php—通过客户端的信息来显示特定的页面

4.4因特网协议

还有一种是中和了之后的五层协议

​ 注：**TCP/IP****是指一组协议簇，而不是仅指这两个协议。**因特网的响应都是毫秒级的

基于一种分层的思想，即各层对各层是透明的

TCP/IP：分 应用层，传输层， 网络层，数据链路层

应用层：准备报文，加上目的地址

传输层：将应用层发送的报文进行分组，因为长的报文不好传输，容易造成堵塞，每个分组都会被赋予编号，以保证最后可以拼接起来–**-**协议TCP/UDP

TCP/UDP的区别：

TCP 面向连接，并且会对数据的发送进行确认和分组重发，会有对信道是否堵塞有监控的意识

应用上：UDP由于更加快速及时的特点，应用于:交互式游戏，DNS查找

TCP应用于对时间不是很敏感的服务，如邮件传输

网络层和数据链路层共同组成了路由器所提供的服务：即实际的在网络间的传输和转发；网络层负责确定往哪传输，数据链路层负责实际在信道中的传输----网络层协议 IP

网路层会维护路由器中的转发表，而链路层需要处理个体网络特有的细节，如是以太网还是WIFI网—CSMA/CA还是CSMA/CD协议

具体的传输过程：

具体的一次传输过程:逐层向下传输，并加上每一层特有的协议信息—协议头 ,在传到网路层的时候会查看路由表，看现在是不是终点，若不是继续向下传到链路层进行转发，直到传到目的地，则逐层上传，根据协议，能够分出哪一部分是协议哪一部分是数据。

应用层包含了诸多的应用，向应用层传数据的时候是如何区别的呢?

这个是传输层所需要完成的任务，传输层为每个应用分配唯一的端口；一些常用的应用会有默认的端口，如ftp 20/21,http 80等等。

跳数—IP层的一个概念

会在分组中加入一个值，用于控制分组在网络中被转发的次数，每转发一次数值减一，以防止分组在网络中无终止的漫游，如64跳数。

4.5安全性

1.1网络攻击的一些概念

蠕虫 病毒 木马

1,2网络攻击的一些形式：

拒绝服务攻击（Dos）

将一些缺乏安全保障的客户机利用起来 ，作为傀儡，向目的机发起大量连续的请求，使目的机无法为正常的用户提供服务。

2防护和对策

2,1防火墙：用于过滤向目的地传输（如一个关键的网络节点）进来的数据，通过检查各层协议的表头，来检查是否是正确的源地址，源端口等等。

网关防火墙：拒绝所有地址显示为内部地址的访问，以防外来者伪造为内部人员来窃取与攻击----欺骗

个人计算机防火墙;拒绝一些不需要的服务端口所传来的数据，如如果不使用ftp的话，就不接受来自对应端口传输的数据。

2.2 代理服务器

一个组织如果经常访问同一个服务器，那么很容易使服务器通过获取的信息而了解这个网络内部的组织与结构，则代理服务器起到了一个中介的作用，即客户端通过代理服务器来和服务器进行通信。

2.3 审计软件 防病毒软件

加密

3.1口令：口令（类似于password）只是针对于具体在计算机端访问的控制，但是信息在信道上传输的时候是没有保护的，是赤裸的

3.2加密：对传输的数据进行加密，这样即使在传输过程截取了，也无法直接获取信息

所以多出来了很多软件的安全版本，

ftp—ssh http—https—对传输的信息进行了加密处理

3.3非对称密钥：公钥 私钥

机制：私钥自己保存，然后将公钥发给需要与自己进行通信的人，公钥加密私钥解密，反之也可以，私钥加密公钥解密-----前者用于数据传输，后者相当于署名/签名，因为私钥是唯一的，可用作一种鉴别

公钥体制是基于RSA算法的，被应用域PGP软件包中，用户可以免费试用这一机制

但是也出现了一个问题，比如你与银行采用公钥体制进行加密，如何确定给你公钥的人就是银行呢，万一是伪造者呢？也就是身份认证的问题-------就是要确定私钥持有者是正确的一方，并且公钥传输到正确的地方？----通过认证机构维护的证书

认证机构：维护相关方的信息和公钥；认证机构会提供一个证书，证书包含了有关方的信息和公钥

3.4鉴别和数字签名-----确认报文的作者实际上就是他们声称的那一方

由于私钥是唯一的，只有持有者有，则用私钥加密的文件只有持有者这一来源，因此可用私钥对文件进行加密----数字签名；接收者可用公钥对数字签名进行解密，从而能够确定确定文件的来源就是私钥持有者。

3.5数字签名和身份认证的机制

例子:B认证A，并且A向B发送数据

A(私钥持有者)----认证机构---->B（公钥获取者）

A向验证发送数据，首先B要在认证机构中验证A的身份----数字证书，认证机构维护者用户的证书，里面包含了用户的信息以及它的公钥；B验证成功A的身份，并从证书中获取到A的公钥；-----------身份认证，即确保A是正确的人

在B认证了A的身份之后，A向B发送文件，文件用私钥加密，形成----数字签名；B接收到后用A的公钥进行解密，如果能够正确解密等验证，则可确认这个文件就是A发过来的。-----------确保是A发过来的

即身份认证和数字签名都是提供的一种服务，现实生活中往往会双向认证，并且利用数字签名的机制来进行数据的往来。

算法

算法就是解决一个问题的步骤，算法的设计往往比算法的实现更重要

算法的定义：一个可终止过程的一组有序的、无歧义的、可执行的步骤的集合

算法的实现：

理解问题

寻找一个能够解决问题的算法的思路

阐述算法并用程序表现出来

设计算法的几种方法：

自顶向下，逐步细化----从一般发展到特殊

自下向上，从一个个具体问题的解决开始-----从特殊发展到一般

查看相似的问题的解决方式来找到一些借鉴

反向解决问题

算法中使用的一些重复结构：

\1. 循环(loop)

\2. 迭代/递归----把每一阶段重复当做前一阶段的子任务

通常，递归程序将终止条件的测试设计在请求继续活动激活之前

查找算法：顺序查找法，二分查找，

排序算法-----不允许挪用其他的空间来挤出更多的空间，有效利用存储空间

插入排序算法----重复地移动表项，并将它插到前面的有序子序列中

选择排序 冒泡排序

衡量算法的机制：

算法分析通常包括最优情况，最差情况和平均情况分析

首先当数据量增大时，算法的执行时间会响应的增长，那么两者之间可以存在一个函数关系；比如logn和n2的增长曲线是不同的，这体现了它们随数据增长之后的性能；通常我们将体现出相同曲线的算法划分为同一个量级，记作o（logn）。知道特定算法属于的类型使我们可以预测它的性能，并且拿它与能够完成相同工作的算法进行比较。

数据结构

数据结构相当于一个抽象工具，我们对数据有了一定的组织结构，它不是实际上在计算机存储的形式，或者说，它使得用户能够按这样的组织结构来访问数据，而不需要考虑它实际上是如何存储的。

分类：

1.同构数组

即一个数据中的成员都有相同的数据类型和结构，如一个人12个月的成绩

2.异构数组

一个数据中的成员有着不同的含义，如一个员工的工资，姓名—这些称之为部件

3．列表：按顺序排列的数据

现实生活中很多数据的数据集合都可以看成是列表，如文本，音乐，清单等等

4栈和队列

对顺序表的访问存储有一定的限制，就构成了栈和队列。

栈就是只能在一头进出----后进先出

这种数据结构的应用常常应用于输入顺序和输出顺序相反的情况；即回溯活动，也应用于迭代结构。

​ 队列;队头进队尾出—先进先出

这种数据结构常常用于排队机制，如计算机的批处理，作业都进行了排队；也应用于缓存机制，这能够保障进入缓存区的顺序就是它从缓存区输出的顺序。

5树

就是一种分层次等级的结构

数据结构的一些重要的概念

抽象 静态和动态 指针

1.静态和动态：组织数据结构时，我们需要了解我们的数据时静态的还是动态的；静态的就是指数据结构的形态和大小是不会改变的；而动态是指数据结构会有增加和删除操作，即数据的缩小和扩充。

2.指针：既然对存储单元进行了编号，即数字化，那么这个编号即地址也可以作为信息存储，cpu中的指令寄存器就是指针，它存储的是下一个指令的地址。

而指针也会带来一些问题，Java就针对于指针增加了一些限制，即它采用了一种特殊的形式—引用，即指针必须要有明确的指向的对象，并且这个对象也必须要存在。

数据结构的实现----在计算机内存中的存储方式

1.异构数组：

每个数据项使用连续的地址，为每个部件分配固定的大小。

每个部件使用单独的存储空间，并用指针连接起来，这样子便于数据的修改，而不用重新分配

2.列表的存储：

静态存储：基于数组的方式，使用一片连续的地址来进行存储—邻接表

动态存储：采用指针的形式存储起来----链表

3.栈和队列：一般是使用类似于邻接表的形式来实现，

栈和队列都会有对应的头尾指针，如果只是单纯的让指针沿着一个方向移动的话，那么它们会像蛇一样无止境前进，因此给了它们固定的活动空间-----循环队列/栈

4.树，以二叉树为例，树的每个节点包含了三个信息—节点，左子树指针，右子树指针。

那么只要把每个节点存储下来即可。

可以链式存储，也可以顺序存储。

\3. 数据结构的操作 p257

数据库

数据库就是对数据进行组织，方便用户进行提取和查看；数据挖掘：在数据集中确定和寻找数据的模式。

9.1基本概念：

1**.**管理数据的不同阶段：

文件管理：是单一的一维的存储

数据库管理：根据数据项之间的关联进行存储，是多维的；信息可以从不同的角度来获取。

模式：

2.针对于安全的问题，只能让特定的人访问特定的数据，即访问控制，提出了****模式的概念。

模式：整个数据库的结构。子模式：进行了限制的数据库，针对于特定的用户只能访问特定的子模式。

3.分布式数据库：

即数据库的存储是分散的，单个计算机存储的数据可以是碎片数据，也可以是数据的副本。

存储数据的副本，可以使数据的传输效率更高。

但是分布式数据也存在着问题：1.如何让用户实际使用时感受不到是分布式的，即能像连贯式的系统那样工作？2.当数据更新时，如何及时更新副本使其保持一致？

4.数据库管理系统（DBMS）

由DBMS在实际操控数据库

优势：

\1. 提供了一个抽象工具，使得应用程序不需要了解数据库是如何实际存储的，而只需要去应用即可。

\2. 提供了对数据访问控制的手段 能够按照模式，子模式来进行访问控制

\3. 提供了数据独立性，改变数据只需要改变数据库组织本身而不需要改变应用程序

5.数据库模型：数据库的概念视图，就是数据的组织形式（不需要要考虑实际是怎样存储的）

分为 关系模型 和 面向对象模型

9.2****关系型数据库：

即用列和项，表格的形式来存储

当在员工信息中添加其职位经历时，有两种方法：

\1. 直接在员工信息里添加多列，并存储这些数据，但出现一个问题，即信息的冗余。

当一个员工曾任多个职位时，员工信息就要存储多次

当一个职位有多员工就职时，职位信息会存多次

当一个职位没有员工就职时，这个职位的信息就会消失

原因就是因为在一个表里面加入了太多的概念

\2. 将这些信息分为3个表，即员工基本信息表，职位信息表，以及就职经历

这样子，它们就是相互关联的3个表

缺点：有时候对表的分离会造成信息的丢失，有时不会，后者称之为无损分离。

比如都是多对多的情况时，一个员工会对应一个职位，一个职位会对应一个部门，但是这个员工不一定在这个部门，比如当很多部门有相同的职位的情况下。

9.3面向对象型数据库

数据都是按照对象来存储的，然后数据之间的关系就表现对象间的链接，就像连线了一样。

新建一个对象，然后与相关的对象链接起来即可。这样查询一个对象所链接的对象就可以知道他的信息了。

相比于关系型，面向对象型数据库往往和应用程序保持了相同的泛型。从长远来看更好维护，因为有一种两者之间可以互相通信的感觉。

9.4维护数据的完整性

1． 提交/回滚协议

一个事务往往会有很多个步骤，而当处于这个步骤的中间状态时，数据库很可能出现数据不一致的状态。

如一个转账事务，会从一个账户扣钱，而向另一个账户增加钱，而在某一个状态下这笔资金是不存在在数据库中的。

为了避免在这种状态下，系统出现故障，从而使数据库处于不一致状态，出现了提交/回滚协议。

当事务未执行时出现故障：

事务在允许对数据库进行操作前，先将它要进行的操作先写入日志中。把一个事务所有的步骤记录到日志的那个点，叫做提交点。

​ DBMS可以根据日志来重现发生过的事务。相当于为事务在数据库中的发生提供了一种保障。

而当在执行到事务的中间状态时：

也可以利用日志回滚，也就是撤销已经执行了的那部分操作。而如果事务之间对资源的获取是相互嵌套相互影响的状态，也会出现级联回滚的问题。

如何处理并行的事务？

并行的事务可能会相互影响，因此有两种办法，一种是限制访问，即按照作业队列的方式，一次执行一条，但是效率不高；

另一种是使用调度程序，分时间片地来执行事务，类似于多道程序处理机制，但是它们会有互斥的可能

2.锁定协议。

锁定协议：就是会对事务会进行分类，即它的访问类型会分为：共享型访问和互斥型。

共享型访问往往不会对数据库的数据造成修改，因此可以并行处理，互斥型就会对访问的数据进行上锁，当访问结束以后再对数据进行解锁。

但是上锁，容易出现死锁问题，比如同时的互斥访问，这时就可以按照早到原则，早到的可以获取其他事务获取的资源优先处理，并且同时有 同情心原则，即被获取了资源的新事务会随着等待变老，然后优先处理。

9.5传统文件管理衍生出的技术

1. 顺序文件

其实生活中很多文件都是顺序存储的文件，比如文本文档，音频，视频等

以及针对于顺序文件的合并出现了----归并算法

2. 索引技术/索引文件

当数据的存储并不是顺序存储时，查找就会非常麻烦，解决方法，建立索引

索引包含数据中的键值以及数据所对应的存储位置，索引会作为一个单独的组件存储在海存中，通常主存访问数据时，会先获取索引文件，然后根据索引来查找对应的数据。

3. 散列技术/散列文件

存储索引文件会占用很多的存储空间。因此出现了散列技术—不是从索引中查找键，而是根据键值来直接确定记录的位置。

首先会有预先准备好的存储桶，数据的键值会根据特定使得算法来决定他们被存储到拿个桶中。而这个算法就是散列函数。

那个如何查找文件呢？

将其对应的编号进行散列计算，以确定相应的桶，再在相应的桶中检索对应的数据。

散列函数的应用：用于信息的认证（见信息安全中的使用），其实早在校验位中就用到了使用散列函数来校验数据是否完整正确的概念。

比如：编号除以41（准备了41个桶），然后根据余数来决定他们被存储在哪个桶中

群集现象：就是没有分配均匀，某个箱中出现了分配不成比例的情况，比如很多。

那问什么设定为41而不是40呢？

因为40会出现很多公因数，比如5，那么5的倍数来除时，5这个因子就会出现在余数中，这样子就会出现聚集现象。

因此被除数一般都是素数。

碰撞：当使用散列函数出现相同的值时就相当于出现了碰撞；

碰撞现象和聚集现象是没办法避免的，但是解决方法有两个1.扩展桶的大小2.设置一个备用桶。但是这无可避免地会降低散列存储的性能。

但根据经总结所得，当被存储的数据占存储总容量的一半时，是一个性能的临界点，这个比例称之为负载因子,当负载因子小于50%时性能最佳，当高于75%时，效率会变得很低，因此当比例达到75%时，应及时扩展总容量的大小。

散列用作大存储器中的存储结构—散列文件 用作主存中的存储结构—散列表

9.6数据挖掘

数据挖掘和数据库技术是堂兄弟的关系，任何一方的发展都会带动另一方的发展。

两者的区别：数据挖掘，发现隐藏在数据的未知模式，而数据库技术就是对已知的数据进行组织管理。

数据挖掘操作的是静态的数据集合，称为数据仓库，它常常是当前数据库的一个快照。经常与统计学息息相关。

数据挖掘的表现方式：

\1. 类型描述和类型识别

前者发现描述一组数据项的属性 后者发现区别数据项的属性

比如前者相当于发现买二手车的人有怎样的属性 而后者就是发现能区分买新车和买二手车的顾客的特性

\2. 聚类分析 就是发现类型 能引导发现组群的数据项的特性

比如说分析一部电影的观众年龄，发现受众群体是10-17和30-45之间的等等。

\3. 关联分析 发现不同数据之间的关联

\4. 孤立点分析 发现不符合数据特征的数据，常用来检测异常等等

\5. 序列模式分析 确定随时间变化的行为模式

比如股票市场，天气等

数据关联可以预见未来的行为

人工智能

11.1智能与机器

智能体：能够对环境的刺激做出响应的装置

接收并理解环境的刺激----感知，涉及到图像处理与分析，自然语言处理等

做出响应----简单的应答式的响应

更高层次的响应----这就要求学习，过程性学习（学习怎样），知识性学习（学习什么）

2.研究方法

两种路线

2.1工程路线----侧重于展示智能行为，即应用理论 面向性能

2.2 理论路线—从计算的角度来研究动物（人类）的智能，即发现研究理论 面向理论

**例子：**针对于copy这一命令，基于工程路线，它不需要去理解copy这一命令，它只需要能够将这一命令与其他命令区别开来，并且按照预先指定好的步骤来执行这个命令即可。

而理论工程就是完整地去考虑英语语言，考虑它的含义等等。

11.2感知

感知涉及到很多领域，目前有图像和语言

理解图像有两种方式，一种是基于像素，看位图是否匹配；一种是基于几何图形，即形状

2.1理解一个图像包含两个步骤—图像处理和图像分析

前者的缺点是对限制大小，在大小不同的情况下，没办法匹配像素；后者是查找比较模糊

图像处理----标识图像的特征，就是标识图像中的各种成分

研究课题：

平滑—去除缺陷

轮廓增强—使区域的边界更清晰，就是将图像变成线条画

区域查找—标识图像中的区域

图像分析----理解这些特征代表什么，类似于人思考的方式，先假定像什么，再与猜测的可能的对象进行比对来分析

​ 2.2 自然语言处理

​ 2.2.1针对于单个句子的分析

​ 这包含了三个层面----语法层面，语义层面，上下文分析

​ 语法层面，分析单词在语法上的作用；语义层面，分析单词在语义上的作用，这使得计算机能够将 A给B一个苹果 和 B收到A的一个苹果 理解为相同的含义

上下文分析–结合语境分析当前句子的作用和含义

2.2.1针对于整个文档

​ 这涉及到了信息检索和信息提取，而提取又有两种方法，一种是提供一种框架来提取信息-----即提取信息的结构；比如提取一个病人的信息，按照病人的名字，病史，病症这样的结构来提取文档中的信息。另一种方式是为信息创建一个链式的语义网。

11.3推理

对于八数码游戏，对问题的解决有这样一种办法那就是列出所有的可能，并且为这些所有的可能都列出解决方法。但是这并不现实，因为常常有上万种可能，这不现实

所有，我们的机器需要有自己解决问题的能力，也就是推理能力

其实推理常常有很多共性，我们可以将这些共性提取成一个实体，也就是—产生式系统

产生式系统包含三个部分：

1.状态 就是这个系统可能处于的各种状态 目标状态 初始状态

2.产生式 对系统的操作，就是将一个状态变成另一个状态

每一个产生式是基于一定的条件的，比如说这个游戏拼图的移动，一定是要它周围有空的位置它才可以移动

3.控制系统 控制执行哪些产生式，能够从初始到目标—程序化

产生式系统的应用：

根据产生式系统，可以为一个系统描绘它部分的状态图，也就是状态之间相互关联的图

那么对于这个游戏，从状态图角度来思考，其实就相当于从初始状态出来，在状态图中，找到能够达到目标状态的路径。

如果一个问题能够根据产生式系统来描绘，那么它的解决方法就能够根据一条路径来明确表达

产生式系统很适用于类似于这样子的情况，就是在规定的环境背景下，比如象棋。

产生式系统的另一种情况是应用推理规则—从旧命题中形成新命题—模拟因果推理

主体的状态会不断地改变

这个很适用于专家系统，专家系统利用它来产生结论。

搜索树

从目标状态出发，把所有的可能都列出来，然后又从这些可能出发，列出可对它们进行的操作，这样就会形成一个一层一层向下的搜索树，这样当最底层出现目标状态时，说明这个搜素图中含有了我们所需要的路径。

首先从底层的目标状态出发，往上回溯—并且利用栈，一边回溯，一边压栈，这样子就可以找到从初始到目的的路径。这样子对树的要求就是，要有子节点指向父节点的指针。

启发式搜索

但是当情况变复杂的时候，完整地建立一个搜索树是不现实的。

所有我们不再采用 广度优先的思想，而是深度优先的思想，即我们不是横向寻找，而是**直接纵向向下走，**也成为最佳优先结构

这有点像我们人在面对游戏时的想法，我们不会考虑所有的情况，而是会走最有希望的步骤，然后一步一步往下走

那么如何衡量几个状态中谁是最有希望的呢？-----通过启发式来衡量

对状态通过启发值来进行衡量，就是看它到目标状态的“距离”，启发值越小，代表与目标状态越接近。----衡量规划代价的一个尺度

启发值应具备两个特征：

1. 对剩余的工作量有一个合理的估计2）启发值的计算要不复杂     
   

那么设定启发值的规则很重要，因为启发值越准确，那么所做的决定也就更准确—启发式搜索

比如说针对于这个游戏，规则可以是不在目标位置的木块的个数，作为当前状态的启发值

但是有时候有些木块离目标位置很远，需要移很多下，那么规则还可以是：所有木块到大目标位置的距离的和作为启发值

基于启发式搜索的思路：

从目标状态出发，查看它所有可能的下一步的启发值，然后从启发值最小的出发，如此反复，直到到达目标地点—就是考虑树中每个节点的启发，然后从启发值最小的叶子节点进行搜索

这样子即使启发式早期饶了一些远路，但是相比构建搜索树的代价还是优化了很多。

对启发式的优化----A***算法----寻找很多搜索问题的最优解**

应用：比如行车路线的设定，人们往往想找一条最近的路，而不是任意一条能够到达的路

它与启发式的区别：它会考虑整体步骤的代价，而不仅仅基于对剩余成本的推测

11.4其他研究领域

知识的表达和处理

知识包括陈述性和过程性知识；有时候知识的确定不是明确的，而是含蓄的

学习

学习可以分三个等级，模仿，监督学习，强化学习

1.模仿—人类直接演示一个任务的步骤，而计算机仅仅是记录这些步骤

2.监督学习就是通过学习人们的正确示范，来决定处理事务的决策—对正确示例进行归纳，其中人们的大量示范和训练称之为训练集

应用，比如说无人驾驶车，就是通过大量的联系，在自己做出决策后，再看驾驶员的示范，然后通过比较双方数据上的差异，使两者尽可能相似。

3.强化学习，给予一般规则，然后通过反复试验，会让机器自己判断任务的成功和失败，会有自主决策的能力

应用：机器下象棋围棋时

P349待看

面向对象与面向过程

面向过程比面向对象性能要高，因为类调用需要实例化，Linux、unix一般就采用面向过程开发，性能最重要

缺点：没有面向对象易维护，易复用，易扩展

面向对象：封装，继承，多态，使得系统低耦合，更加灵活，易于维护