计算机组织原理
ASP
简单登录程序
跳转:
1 | Response.Redirect("URL") |
返回弹窗
1 | Response.Write("<script>alter('用户名或密码错误');</script>") |
文本框的使用
text默认为单行模式
1 | <p>单行模式</p> |
属性栏修改。
判断单选框
单选框将GroupName设置为一样即可
1 | <label>性别</label> |
1 | protected void Button1_Click2(object sender, EventArgs e) |
判断多选框
1 | “+string+” |
下拉框
1 | <asp:DropDownList ID="DropDownList1" runat="server"> |
1 | DropDownList1.SelectedItem.Value |
呈现信息
构造一个用于盛放HTML代码的变量,用Response.Write(HTML),可先用Response.Clear()清理当前页面
转换
Convert.ToDouble()
捕获异常
1 | try{ |
显示数据
1 | inf.InnerHtml=HTML; |
读取全部数据
1 | foreach |
连接数据库
初始
1 | </system.web> |
显示表
拆包
学校教室管理信息系统
数据库部分
创建数据库
1 | --创建数据库School Classroom Management Information System-SCMIS |
创建教师信息表
1 | --创建教师信息表 |
创建学生信息表
1 | --创建学生信息表 |
创建教室信息
1 | --创建教室信息表 |
创建教学楼信息表
1 | --创建教学楼信息表 |
有个信息不匹配,进行修改
1 | alter table 教室信息 |
创建教室使用信息表
1 | --创建教室使用信息表 |
创建课程信息表
1 | --创建课程信息表 |
创建课程时间表
1 | --创建课程时间表 |
修改
1 | alter table 学生信息 add 密码 varchar(15) |
约束
1 | --将教师信息表中教师编号设置为主键约束,身份证号设为唯一约束 |
1 | --将学生信息表中学号设置为主键约束,身份证号设为唯一约束 |
1 | --将教室信息中教室编号设置为主键 |
1 | --将教学楼信息中教学楼编号设置为主键 |
1 | --将教学楼信息中的教学楼编号与教室信息中的教学楼编号添加外键 |
1 | --将教室使用信息表中教学楼编号与教学楼信息表中的教学楼编号添加外键 |
1 | --对课程信息表中课程编号添加主键约束 |
1 | --对教师信息中的性别添加约束 |
修改
1 | alter table 课程时间 |
插入的信息
1 | insert into 教师信息 |
插入课程信息
1 | exec information_entry '数据库','001','周一三四','张三','001','001','1102' |
存储
插入课程信息存储
1 | --插入课程信息 |
修改
1 | create procedure information_entry |
查询指定教室使用情况
1 | --查询指定教室使用情况 |
查询指定课程
1 | create procedure course_query |
租借教室
1 | go |
修改为
1 | declare @state varchar(10) |
判断密码是否正确
1 | create procedure password_query |
删除
1 | create procedure delete_course |
编写存储插入大量数据
1 | --创建循环插入1000条记录的存储过程 |
视图
创建视图,查询张三老师课程
1 | --创建视图,查询计算机学院张三老师所有课程名称 |
例子
1 | exec information_entry '机器学习','004','周六七八','王五','003','002','2202' |
1 | declare @state varchar(10) |
计算机网络
计算机网络和因特网
什么是因特网
具体构成描述
端系统通过通信链路和分组交换机连接到一起。
两种最著名的分组交换机为路由器和链路层交换机。链路层交换机通常用于接入网中,路由器通常用于网络核心中。
端系统通过 因特网服务提供商(Internet Service Provider,ISP)接入因特网。
TCP(Transmission Control Protocol,传输控制协议)和 IP(Internet Protocol,网际协议)是因特网中最为重要的两个协议。
因特网的主要协议称为 TCP/IP协议。
因特网工程任务组。Internet Engineering Task Force,IETF
服务描述
有些应用程序涉及多个相互交换数据的端系统,称为 分布式应用程序
与因特网相连的端系统提供了一套 套接字接口,该接口规定了运行在一个端系统上的程序请求因特网基础设施向运行在另一个端系统上的特定目的地程序交付数据的方式。
协议
协议定义了在两个或多个通信实体之间交换的报文的格式和顺序,以及报文发送和/或接受一条报文或其他事件所采取的动作。
网络边缘
端系统也被称为 主机,因为它们容纳应用程序,主机有时又被划分为客户和服务器。
接入网
家庭介入
宽带住宅接入有两种最流行的类型: 数字用户线(Digital Subscriber Line,DSL)和电缆。
企业(和家庭)接入:以太网和WIFI
局域网LAN
广域无线接入:3G和LTE
物理媒体
物理媒体分成两种类型:导引型媒体和非导引型媒体
网络核心
分组交换
存储转发传输
多数分组交换机在链路的输入端使用 存储转发传输机制。存储转发传输是指在交换机能够开始向输出链路传输该分组的第一个比特之前,必须接收到整个分组。
排队时延和分组丢失
每台分组交换机有多条链路与之相连。对于每条相连的链路,该分组交换机具有一个输出缓存,它用于粗出路由器准备发往那条链路的分组。
转发表和路由选择协议
每台路由器具有一个转发表,用于将目的地址映射成为输出链路。
电路交换
在电路交换网络中,在端系统通信会话期间,预留了端系统间沿路径通信所需要的资源。
电路交换网络中的复用
链路中的电路是通过 频分复用(FDM)或 时分复用(TDM)来实现的。
分组交换与电路交换的对比
趋势朝着分组交换方向发展。
网络的网络
今天的因特网是一个网络的网络,由十多个第一层ISP和数十万个较低层ISP组成。
分组交换网中的时延、丢包和吞吐量
分组交换网中的时延概述
这些时延最为重要的是 节点处理时延、排队时延、传输时延和传播时延,这些时延累加起来是节点总时延。
时延的类型
处理时延
$d_{proc}$
检查分组首部和决定将该分组导向何处所需要的时间是 处理时延的一部分。处理时延也能够包括其他因素,如检查比特级别的差错所需要的时间。
排队时延
$d_{queue}$
在队列中,当分组在链路上等待传输时,他经受排队时延。
传输时延
$d_{trans}$
用L比特表示该分组的长度,用R bps表示从路由器A到路由器B的链路传输速率。传输时延时L/R。这是将所有分组的比特推向链路所需要的时间。
传播时延
$d_{prop}$
从该链路的起点到路由器B传播所需要的时间是传播时延。
排队时延和丢包
令a表示分组到达队列的平均速率(a的单位是分组/秒)。R是传输速率,即从队列中推出比特的速率。假定所有分组都是由L比特组成。则比特到达队列的平均速率是La bps。比率La/R被称为流量强度。
设计系统时流量强度不能大于1
丢包
因为排队容量是有限的,随着流量强度接近1.排队时延并不是无穷大,相反,到达的分组将发现一个满的队列。由于没有地方存储,路由器将丢弃该分组。
计算机网络中的吞吐量
在任何时间瞬间的 瞬时吞吐量是主机B接受到该文件的速率。
协议层次及其服务模型
分层的体系结构
协议分层
各层的所有协议被称为 协议栈。因特网的协议栈由五个层次组成:物理层、链路层、网络层、传输层和应用层。
应用层
HTTP:提供了Web文档的请求和传送。
SMTP:提供了电子邮件报文的传送。
FTP:提供两个端系统间的文件传送。
报文:位于应用层的信息分组称为报文。
运输层
TCP/UDP
报文段:我们把运输层的分组称为报文段。
网络层
因特网的网络层负责将称为 数据报的网络层分组从一台主机移动到另一台主机。
链路层
为了将分组从一个节点移动到路径上的下一个节点,网络层必须依靠该链路层的服务。特别是在每个节点,网络层将数据报下传给链路层,链路层沿着路径将数据报传递给下一个节点。
帧:链路层分组
物理层
物理层的任务是将该帧中的一个个比特从一个节点传递到下一个节点。
OSI模型
开放系统互联模型:应用层、表示层、会话层、传输层、网络层、数据链路层、物理层。
封装
一个应用层报文被传送给传输层,在最简单的情况下,运输层收取到报文并附上附加信息,该首部将被接收端的运输层使用。应用层报文和运输层首部信息一道构成了运输层报文段。以此类推。我们可以看到,在每一层,一个分组具有两种类型的字段:首部字段和有效载荷字段。有效载荷字段通常来自上一层分组。
附加
计算机网络就是自治互联的计算机集合。
协议的三要素:语法、语义、同步/时序。
分组交换网络传输分组的基本工作方式是(存储-转发)。
计算机网络从结构上可以划分为网络核心,网络边缘和接入网。
OSI中应用层,表示层,会话层,传输层为端到端层。实现路由功能为网络层。
应用层
应用层协议原理
网络应用程序体系结构
应用程序体系结构由应用程序研发者设计,规定了如何在各种端系统上组织应用程序。
客户-服务器体系结构中,有一个总是打开的主机称为服务器,它服务于来自许多其他称为客户的主机的请求。
在这个体系中,客户之间不通信;并且服务器具有固定的周知的地址,称为IP地址。
P2P体系结构中,对于位于数据中心的专用服务器有最小的依赖。相反,应用程序在间断连接的主机对之间直接通信,这些主机被称为
对等方。P2P具有自扩展性。
进程通信
客户和服务器进程
在一个P2P文件共享系统中,文件从一个对等方中的进程传输到另一个对等方的进程。通常将这两个进程之一标识为客户,另一个标识为服务器。在P2P共享文件中,一个进程既是客户又是服务器。
进程与计算机网络之间的接口
进程通过一个称为套接字的软件接口向网络发送报文和从网络接收报文。套接字也称为应用程序和网络之间的应用程序编程接口。
应用程序开发者对于运输层的控制权限仅限于:选择运输层协议;也许能设定几个运输层参数。但是对于套接字的运输层段几乎没有控制权。
进程寻址
为标识该接收进程,需定义:主机的地址;在目的主机中指定接收进程的标识符。
在因特网中,主机由I地址标识。
发送进程还必须指定运行在接收主机上的接收进程,目的地端口号用于这个目的,
Web服务器端口号:80
邮件服务器进程:25
FTP:21
可供应用程序使用的运输服务
从四个方面分类:
可靠数据传输
运输层协议能够潜在的向应用程序提供的一个重要服务是进程到进程的可靠数据传输。
吞吐量
具有吞吐量要求的应用程序被称为带宽敏感的应用。
弹性应用能够根据当时可用的带宽或多或少地利用可供使用的吞吐量。
定时
一个保证的例子:发送方注入进套接字中的每个比特到达接收方的套接字不迟于100ms。
安全性
运输协议能够为应用程序提供一种或多种安全性服务。
因特网提供的运输服务
TCP服务
包括面向连接服务和可靠数据传输服务。
面向连接的服务:在应用处数据报文开始流动之前,TCP让客户和服务器互相交换运输层控制信息。这就是握手,在握手阶段后,一个 TCP连接就在两个进程的套接字之间建立。
可靠的数据传送服务:通信进程能够依靠TCP,无差错,按适当顺序交付所有发送的数据。
TCP协议还具有拥塞控制机制。
UDP服务
仅提供最小服务。UDP是无连接的。提供不可靠数据传送服务。
没有拥塞控制机制。
应用层协议
定义了运行在不同端系统上的应用程序进程如何相互传递报文。
特别是应用层协议定义了:
交换的报文类型;
各种报文类型的语法;
字段的语义;
确定一个进程何时以及如何发送报文,对报文进行响应的规则。
Web的应用层协议是HTTP。
电子邮件的主要应用层协议是SMTP。
涉及的网络应用
主要讨论:Web,文件传输,电子邮件,目录服务,流式视频和P2P。
Web和HTTP
HTTP概括
应用层协议为:超文本传输协议(HyperText Transfer Protocol,HTTP).
HTTP由一个客户程序和一个服务器程序实现。
WEB浏览器实现了HTTP的客户端。
Web服务器实现了HTTP的服务器端,用于存储Web对象,每个对象由URL寻址。
HTTP定义了Web客户向Web服务器请求Web页面的方式,以及服务器向客户传送Web页面的形式。
HTTP服务器并不保存关于客户的任何信息,所以我们说HTTP是一个 无状态协议。
非持续连接和持续连接
非持续连接:每一个请求/响应是经一个单独的TCP连接发送。
持续连接:所有请求及其响应经相同的TCP连接发送。
往返时间(RTT):一个短分组从客户到服务器然后再返回客户所花费的时间。RTT包括分组传播时延,分组在中间路由器和交换机上的排队时延以及分组处理时延。
HTTP报文格式
HTTP请求报文
第一行叫请求行。有三个字段,方法字段,URL字段,HTTP版本字段。
之后的行叫做首部行。
第二行指明了对象所在的主机。
第三行该浏览器告诉服务器不要麻烦的使用持续连接,它要求服务器发送完之后就关闭该连接。
第四行指明用户代理,即向服务器发送请求的浏览器的类型。
第五行表示得到该对象的语言版本。
HTTP响应报文
一个初始状态行,六个首部行和实体体。
状态行有三个字段:协议版本字段,状态码,相应状态信息。
第二行告诉客户发送报文完后将关闭该TCP连接。
第三行DATE为服务器产生并发送该响应报文的日期和时间。这个时间是服务器从文件系统中检索到该对象,插入响应报文,并发送该响应报文的时间。
第四行指示该报文由什么服务器产生。
第五行指示了该对象创建或最后修改的时间和日期。
第六行指示了被发送对象中的字节数。
第七行指示了实体体对象是HTML文本。
一些常见的状态码:
200 OK:请求成功
301 Moved Permanently:请求的对象已经被永久转移。
400 Bad Request:一个通用差错码,指示该请求不能被服务器理解。
404 Not Found:被请求的文档不在服务器上。
505 HTTP Version Not Supported:服务器不支持请求报文使用的HTTP版本协议。
用户与服务器的交互:cookie
cookie技术有四个组件:
在HTTP响应报文中的一个cookie首部行;
在HTTP请求报文中的一个cookie首部行;
在用户端系统中保留有一个cookie文件,并由用户的浏览器进行管理;
位于Web站点的一个后端数据库。
Web缓存
也叫代理服务器。其既是客户又是服务器。
内容分发网络CDN
条件GET方法
因特网中的电子邮件
因特网电子邮件系统由三个主要组成部分:用户代理;邮件服务器;简单邮件传输协议(SMTP)。
发送邮件的为SMTP的客户端。
SMTP
SMTP一般不使用中间邮件服务器发送邮件。
与HTTP对比
HTTP是一个拉协议,即在方便的时候,某些人在Web服务器上装载信息,用户使用HTTP从该服务器拉取这些信息。
SMTP基本上是一个推协议,即发送邮件服务器把文件推向接收邮件服务器。
SMTP要求每个报文采用7比特ASCLL码格式。若包含非7比特ASCLL字符,则该报文必须按照7比特ACLL进行编码。
对于一个既包含文本又包含图形的文档。HTTP把每个对象封装到自己的响应报文,而SMTP则把所有报文对象放在一个报文中。
邮件访问协议
用户代理不能通过SMTP得到报文,因为取报文是一个拉操作,而SMTP为一个推操作。所以引入其他协议。
POP3第三版的邮局协议
随着TCP连接,POP3按照三个阶段进行工作:特许,事务处理以及更新。
特许阶段:用户代理发送(以明文形式)用户名和口令以鉴别用户。
事务处理阶段:用户代理取回报文。同时还可以做以下操作,对报文做删除标记,取消报文删除标记,以及获取邮件的统计信息。
更新阶段:出现在客户发出quit命令后,目的是结束POP3会话,这时,邮件服务器删除那些标记为删除的报文。
DNS:因特网的目录服务
我们需要一种能进行主机名到IP地址转换的目录服务。这就是 域名系统DNS的主要任务。DNS是:
一个由分层的DNS服务器实现的分布式数据库;一个使得主机能够查询分布式数据库的应用层协议。
DNS运行在UDP之上,使用53号端口。
DNS其他一些重要服务:
主机别名;邮件服务器别名;负载分配。
DNS工作机理概述
分布式、层次数据库
根DNS服务器
顶级域服务器:com,org,uk等
权威DNS服务器
另外有本地DNS服务器,但不属于该服务器层次结构。
DNS缓存
改善时延性能,减少在因特网上到处传输的DNS报文数量。
DNS记录和报文
共同实现DNS分布式数据库的所有DNS服务器存储了 资源记录(RR),RR提供了主机名到IP地址的映射。
资源记录是一个包含了下列字段的四元组:
1 | (Name,Value,Type,TTL) |
TTL是该记录的生存时间,它记录了资源记录应当从缓存中删除的时间。NAME和VALUE的取值取决于TYPE:
若TYPE=A,则Name为主机名,Value为该主机名对应的IP地址。
若Type=NS,则Name是个域,而Value是个知道如何获得该域中主机IP地址的权威DNS服务器的主机名。
若Type=CNAME,则Value是别名为Name的主机对应的规范主机名。
若Type=MX,则Value是个别名为Name的邮件服务器的规范主机名。
DNS报文
DNS只有查询和回答报文,并且有着相同的格式。
P2P文件分发
分发时间是所有N个对等方得到该文件的副本所需要的时间。
BitTorrent是一种用于分发的流行P2P协议。参与一个特定文件分发的所有对等方的集合称为洪流。
在决定请求哪些块的过程中,采用 最稀缺优先的技术。针对他没有的块在他的邻居中决定最稀缺的块(最稀缺的块就是那些在他的邻居中副本数量最少的块)。
为决定响应哪个请求,他根据当前能够以最高速率向他提供数据的邻居,给出其优先权。每过10秒,重新计算,每过30秒,随机选择一个。
附加
网络应用体系结构主要包括C/S、纯P2P、混合模式三种类型。
流量控制关注的是接收端数据接收处理与缓存能力;拥塞控制关注的是网络传输能力。
HTTP1.0与HTTP1.1的区别
1 | 1.0:非持续性,每个TCP连接最多允许一个传输对象,方法有GET,POST,HEAD |
HTTP无状态性:不记录用户信息
WEB缓存
1 | 缩短客户请求时间;减少机构/组织的流量;在大范围内实现有效的内容分发 |
递归查询与迭代查询
1 | 递归查询请求1次,迭代查询请求多次 |
FTP客户和服务器传递FTP命令时,用的是(建立在TCP之上的控制连接)
典型的邮件接收协议:POP3,IMAP,HTTP
运输层
概述和运输层服务
运输层协议为运行在不同主机上的应用程序之间提供了逻辑通信功能。
运输层和网络层的关系
网络层提供了主机之间的逻辑通信,而运输层为运行在不同主机上的进程之间提供了逻辑通信。
运输层协议只工作在端系统。
因特网运输层概述
UDP用户数据报协议
TCP传输控制协议
因特网网络层协议有一个名字叫IP,即网际协议。IP的服务模型是尽力而为交付服务,但并不做任何保证。故IP也被称为不可靠服务。
UDP和TCP最基本的责任是,将两个端系统间IP的交付服务扩展为运行在端系统上的两个进程之间的交付服务。
将主机间交付扩展到进程间交付被称为 运输层的多路复用与 多路分解。
多路复用与多路分解
将运输层报文段中的数据交付到正确的套接字的工作称为多路分解。
在源主机从不同套接字中收集数据块,并为每个数据块封装上首部信息从而生成报文段,然后将这些报文段传递到网络层,所有这些称为 多路复用。
运输层多路复用要求:套接字有唯一标识符;每个报文段有特殊字段来暗示该报文段要交付的套接字。
如图,这些特殊字段是源端口号字段和目的端口号字段。端口号是一个16比特的数,大小在0-65535之间。0-1023范围的端口号称为周知端口号。
无连接的多路复用与多路分解
一个UDP套接字是由一个二元组全面标识的,该二元组包含一个目的IP地址和一个目的端口号。
如果两个UDP报文段有不同的源,但是具有相同的目的IP地址和目的端口号,那么这两个报文段将通过相同的套接字被定向到相同的进程。
面向连接的多路复用与多路分解
TCP套接字由一个四元组(源IP地址,源端口号,目的IP地址,目的端口号)来标识的。
与UDP不同的是,两个具有不同源IP地址或源端口号的到达TCP报文段将被定向到两个不同的套接字。
无连接运输:UDP
DNS采用UDP。
采用UDP原因:
关于发送什么数据以及何时发送的应用层控制更为精细;
无需建立连接;
无连接状态;
分组首部开销小。
UDP用于承载网络管理数据(SNMP)。
需要注意的是,使用UDP的应用是可能实现可靠数据传输的。
UDP报文段结构
UDP首部只有4个字段,每个字段由两个字节组成。长度字段指示了在UDP报文段中的字节数。接收方使用检验和来判断是否出差错。
UDP检验和
UDP提供检验和的原因是不能保证源和目的之间的所有链路能提供差错检验。在既无法确保逐链路的可靠性,又无法确保内存中的差错检验的情况下,如果端到端数据传输服务要提供差错检测,UDP就必须在端到端基础上在运输层提供差错检测。这是一个在系统设计中被称颂的 端到端原则的例子,该原则表述为因为某种功能必须基于端到端实现。
UDP对差错恢复无能为力。
可靠数据传输原理
rdt 可靠数据传输
udt 不可靠数据传输
构造可靠数据传输协议
经完全可靠信道的可靠数据传输:rdt1.0
经具有比特差错信道的可靠数据传输:rdt2.0
基于肯定确认和否定确认重传机制的可靠数据传输协议称为 自动重传请求协议(ARQ)
ARQ协议中还需要另外三种协议功能来处理存在比特差错的情况:
差错检测;接收方反馈(ACK,NAK);重传
停等:发送方将不会发送新数据,除非发送方确信接收方已正确接收当前分组。
考虑处理受损ACK和NAK时的三种可能:
(1)接收方复述其回答。
(2)增加足够的检验和比特。
(3)收到受损的ACK或NAK时,重传当前数据分组。但无法知道接收到的是新的还是重传。
解决这个问题的方法是在数据分组中添加一新字段,让发送方对其数据进行编号。
rdt2.1使用了从接收方到发送方的肯定确认和否定确认。当接收到失序的分组时,接收方对所接受的分组发送一个肯定确认。如果收到受损的分组,则接收方将发送一个否定确认。如果不发送NAK,而是对上次正确接收分组的一个ACK,也能实现与NAK一样的效果。即接收冗余ACK.
rdt2.2在有比特差错信道上实现的一个无NAK的可靠数据传输协议,
经具有比特差错的丢包信道的可靠数据传输:rdt3.0
基于时间重传,介入倒计时定时器。
rdt3.0又称为比特交替协议。
在数据传输中,检验和、序号、定时器、肯定和否定确定分组这些技术都起到了必不可少的作用。
流水线可靠数据传输协议
信道利用率:发送方实际忙于将发送比特送进信道的那部分时间与发送时间之比。
引入流水线,对可靠数据传输协议带来以下影响:
增加序号范围,每个传输分组必须有唯一的序号;
协议的发送方和接收方不得不缓存多个分组;
解决流水线差错恢复有两种方法,回退N步和选择重传。
回退N步
GBN协议。
我们将基序号(base)定义为最早未确认分组的序号。下一个序号(nextseqnum)定义为最小的未使用序号(即下一个待发分组的序号),则将序号范围分成四段:
1 | [0,base-1]已经发送被确认 |
N常被称为窗口长度。GBN也被称为滑动窗口协议。
采用累积确认,若超时,则重发所有已发送但还未被确认过的分组。
在GBN协议中,接收方丢弃所有失序分组。
选择重传
SR
SR接收方将确认一个正确接收的分组而不管其是否按序。失序的分组将被缓存知道所有丢失分组皆被收到为止。
窗口长度必须小于或等于序号空间大小的一半。
总结
面向连接的运输:TCP
TCP连接
TCP被称为是 面向连接的。中间路由器对TCP连接完全视而不见,他们看到的是数据报,而不是连接。
TCP连接提供的是全双工服务。TCP连接也总是点对点的。
三次握手中前两次不承载有效载荷,第三次可以承载有效载荷。
TCP可从缓存中取出并放入报文段中的数据数量受限于 最大报文段长度(MSS)。
MSS通常根据最初确定的由本地发送主机发送的最大链路层帧长度(即所谓的 最大传输单元MTU)来设置。
TCP为每块客户数据配上一个TCP首部,从而形成多个 TCP报文段。
TCP报文段结构
与UDP一样,首部包含 源端口号, 目的端口号,检验和字段。
TCP报文段首部还包含以下字段:
32比特的 序号字段和32比特的 确认号字段。用来实现可靠数据传输服务。
16比特的 接收窗口字段,用于流量控制。
4比特的 首部字段长度,通常选项字段为空,所以TCP首部的典型长度是20字节。
可选与变长的 选项字段,用于发送方与接收方协商最大报文段长度。
6比特的 标志字段。
序号和确认号
一个报文段的序号是该报文段首字节的字节流编号。
主机A填充进报文段的确认号是主机A期望从主机B收到的下一字节的序号。
TCP只确认该流中至第一个丢失字节为止的字节,所以TCP被称为提供 累积确认。
可靠数据传输
TCP的可靠数据传输服务确保一个进程从其接收缓存中读出的数据流是无损坏、无间隙、非冗余和按序的数据流。
超时间隔加倍
在这种修改中,每次TCP重传时都会将下一次的超时间隔设为先前值的两倍。
快速重传
一旦收到三个冗余ACK,就进行快速重传。
对TCP的一种修改意见是所谓的 选择重传。
流量控制
TCP为它的应用程序提供了 流量控制服务以消除发送方使接收方缓存溢出的可能性。
TCP发送方也可能因为IP网络的拥塞而被遏制,这种形式的发送方的控制被称为拥塞控制。
TCP通过让发送方维护一个被称为 接收窗口的变量来提供流量控制。
当接收窗口等于0时,仍可发送一个较小的数据,以把窗口信息带回来。
TCP连接管理
确认y表明在y之前的所有字节都被正确接收。
拥塞控制原理
当一个分组沿一条路径被丢弃时,每个上游路由器由于转发该分组到丢弃该分组而使用的传输容量最终被浪费。
拥塞控制方法
端到端拥塞控制;
网络辅助的拥塞控制
TCP拥塞控制
指导原则:
1 | 一个丢失的报文段意味着拥塞,因此当丢失报文段时应当降低TCP发送方的速率。 |
TCP拥塞控制算法
慢启动
cwnd(拥塞窗口)的值通常初始置为一个MSS的较小值。当传输的报文段首次被确认就增加一个MSS。成指数增长。
拥塞避免
当进入拥塞状态,cwnd值为上次拥塞的一半,然后线性增长。
快速恢复
阈值前指数,阈值后线性。
TCP拥塞控制
加性増乘性减(丢包由三个冗余ACK)
公平性
TCP具有公平性。
附加
典型的邮件接收协议有 POP,IMAP,HTTP。
实现文件分发应用时,采用P2P技术比典型的client/server技术更快。
发送窗口大小取决于min(rwnd,cwnd).
其中rwnd是接收缓存的空余大小,表示接收方还能接收多少。
cwnd就是我们常常画慢增长曲线,拥塞避免曲线等等分析的纵轴数值。
附一道题:
1 | https://blog.csdn.net/aodubi0638/article/details/102144555 |
接收窗口 发送窗口 拥塞窗口
1 | https://blog.csdn.net/ligupeng7929/article/details/79597423 |
计算UDP校验和时,封装UDP报文段的IP数据报某些字段也会参与:源IP地址,目的IP地址,协议。
网络层
网络层能够被分为两个互相作用的平面:数据平面和控制平面。
网络层概述
网络层的作用:即将分组从一台发送主机移到一台接收主机。为此,需要使用两种重要的网络层功能:
转发:当一个分组到达某路由器的一条输入链路时,该路由器必须将该分组移动到适当的输出链路。
路由选择:当分组从发送方流向接收方时,网络层必须决定这些分组所采用的路由或路径。计算这些路径的算法被称为 路由选择算法。
转发:将分组从一个输入链路接口转移到适当的输出链路接口的路由器本地工作。
路由选择:确定分组从源到目的地所采取的端到端路径的网络范围处理过程。
每台路由器中有一个关键元素是它的 转发表。
网络层核心功能
转发与路由
转发:将分组从路由器的输入端口到合适的输出端口。
路由:确定分组从源到目的经过的路径。
连接建立
某些网络的重要功能:ATM,X.25,帧中继
数据分组传输之前两端主机需要首先建立虚拟、逻辑连接
网络层连接是两个主机之间(路径上的路由器等网络设备参与其中),传输层连接为两个应用进程间(对中间网络设备透明)
网络层服务模型
无连接服务(connection-less service)
1 | 不事先为系列分组的传输确定传输路径; |
连接服务(connection service)
1 | 首先Wie系列分组的传输确定从源到目的经过的路径; |
虚电路与数据报网络
虚电路:一条从源主机到目的主机,类似于电路的路径。
1 | 分组交换 |
通信过程:呼叫建立->数据传输->呼叫拆除
每个分组携带虚电路表示(VCID),而不是目的主机地址。
虚电路经过的每个网络设备,维护每条经过它的虚电路连接状态。
每条虚电路包括
1 | 从源主机到目的主机的一条路径 |
虚电路信令协议:
用于VC的建立,维护拆除
数据报网络
网络层无连接;每个分组携带目的地址;路由器根据分组的目的地址转发分组。
路由算法确定通过网络的端到端路径;咋混发表确定在本路由器如何转发分组。
最长前缀匹配优先。
数据报网络简化网络,复杂边缘。
VC网络简化边缘,复杂网络。
IPv4协议
IP数据报
版本:4比特
首部长度:4比特(以4字节为单位)
服务类型:8比特,区分服务(只有在网络提供服务时才使用,通常取0)
长度:IP分组的总字节数,最大长度65535B
寿命:TTL,占8位,标识IP分组在网络中可以通过的路由器数。TTL=0,则丢弃该分组。
协议:8位,指示封装的是哪个协议。
首部校验和:16位,计算校验和时,置全0。逐跳计算
最大传输单元MTU-链路层数据帧可封装数据的上限。
不同链路的MTU不同。
IP数据分片
IP分片到达目的主机后进行重组。
标识字段占16位:标识一个IP分组。每产生IP分组+1.
标志位:3位。保留|DF|MF
1 | DF=1禁止分片 |
片偏移:13比特,相对偏移量。片偏移字段以8字节为单位。
分片时每个分片的标识复制原IP分组的标识。
IP编址
32比特
IP地址
1 | 网络号-高位比特 |
IP子网:IP地址具有相同网络号的设备接口
不跨越路由器可以彼此物理联通的接口。
有类IP地址
IP子网与子网划分
子网掩码:32比特
取值:NetID、SubID全取1
HostID全取0
将IP分组的目的IP地址与子网掩码按位与运算,提取子网地址。
主机路由:子网掩码 255.255.255.255
CIDR与路由聚合
无类域间路由CIDR
消除传统的ABC类地址界限。
无类地址格式:
1 | a.b.c.d/x x为前缀长度 |
提高IPV4地址空间分配效率;
提高路由效率
DHCP协议
动态主机配置协议。
从服务器动态获取:
1 | IP地址 |
默认网关:IP或数据报要离开时送到哪个接口
由于DHCP具有将主机连接进一个网络的网络相关方面的自动能力,故他又被称为 即插即用协议或 零配置。
NAT
网络地址转换。
所有离开本地网络去往Internet的数据报的源IP地址需替换为相同的NAT
动机:
1 | 只需从ISP申请一个IP地址,IPV4地址耗尽。 |
互联网控制报文协议(ICMP)
支持路由器
1 | 差错报告 |
两类ICMP报文:
差错报告报文(5种)
1 | 目的不可达 |
网络探寻报文(2组)
1 | 回声请求与应答报文 |
IPv6简介
最初动机:32位IPV4地址分配完
其他动机:改进首部格式
1 | 快速转发/处理数据报 |
IPV6数据报格式:
1 | 固定长度40字节基本首部 |
其他改变:
1 | 检验和彻底移除,以减少每跳处理时间。 |
ICMPV6:
1 | 附加报文类型 |
IPV6基本地址类型
1 | 单播:一对一通信 |
隧道:IPV6数据报作为IPV4数据报的载荷进行封装,穿越IPV4网络。
路由算法
路由算法
链路状态路由算法
距离向量路由算法
会带来无穷计数问题
毒性逆转
定义最大度量
层次化路由
管理自治:每个网络的管理可能都期望自主控制其网内的路由
聚合路由器为一个区域:自治系统AS
同一AS内的路由器运行相同的路由算法
网关路由器:位于AS边缘;通过链路连接其他AS的网关路由器
转发表由AS内部路由算法与AS间路由算法共同配置。
Internet路由
RIP协议
若180s没有收到通告,则邻居/链路失效
OSPF协议
优点(rip不具备)
BGP协议
附加
拥塞丢失时发送抑制源站报文。
RIP为UDP协议传输报文。
链路层和局域网
概述
节点:运行链路层协议的任何设备。包括主机,路由器,交换机和WiFi接入点。
链路层提供的服务
1 | 成帧 |
链路层在何处实现
链路层的主体部分是在 网络适配器中实现的,网络适配器有时也称 网络接口卡(NIC)。位于网络适配器核心的是链路层控制器。
差错检测和纠正技术(EDC)
奇偶校验
单个奇偶校验
1 | 发送信息有d比特,增加一个附加比特,使得d+1个比特中1的总数为偶数。 |
二维奇偶校验
接收方检测和纠正错误的能力被称为 前向纠错(FEC)。
检验和方法
需要相对小的分组开销。
循环冗余检测
CRC,也称多项式编码。
考虑d比特的数据D。发送方和接收方首先必须协商一个r+1比特模式,称为 生成多项式,将其表示为G。G的最高有效位比特是1.对于一个给定的数据段D,发送方要选择r个附加比特R,并将它们附加到D上,使得得到的d+r比特模式用模二运算恰好能被G整除。接收方用G去除接收到的d+r比特,若余数为非零,则出现差错。
$D*2^rXOR\ R=nG$
即$D*2^r=nG\ XOR\ R$
$R=remainder\ \frac{D*2^r}{G}$
多路访问链路和协议
多路访问控制MAC
MAC地址为链路层地址。
点对点链路:由链路一端的单个发送方和链路另一端的单个接收方组成。eg:点对点协议(PPP),高级数据链路控制(HDLC)。
广播链路:让多个发送和接收节点都连接到相同的单一的,共享的广播信道上。
信道划分协议
时分多路复用TDM;频分多路复用FDM
TMD的缺陷
1 | 节点被限制于R/Nbps的平均速率,即使他是唯一有分组要发送的节点。 |
FDM将Rbps信道划分为不同的频段(每个频段具有R/N带宽)。同样也限制了带宽。
第三种信道划分协议是码分多址(CDMA)。
CDMA对每个节点分配一种不同的编码,然后每个节点用它唯一的编码来对它发送的数据进行编码。
随机接入协议
在随机接入协议中,一个传输节点总是以信道的全部速率进行发送。当有碰撞时,涉及碰撞的每个节点反复地重发它的帧,但是在重发之前会等待一个随机时延。
时隙ALOHA
ALOHA协议
非时隙ALOHA:更加简单,无需同步。
当有新的帧生成时,立即发送。
载波侦听多路访问CSMA
载波侦听:即一个节点在传输前先听信道,若来自另一个节点的帧正在向信道发送,节点则等待直到检测到一小段时间没有传输,然后开始传输。
P坚持CSMA:以概率P发送,一直侦听。
具有碰撞检测的载波侦听多路访问(CSMA/CD)
碰撞检测:当一个传输节点在传输时一直在侦听此信道。如果它检测到另一个节点在传输干扰帧,他就停止传输,在重复“侦听-当空闲时传输”循环之前等待一段随机时间。
CSMA/CD效率
定义为:当有大量的活跃节点,且每个节点有大量的帧要发送时,帧在信道中无碰撞地传输的那部分时间在长期运行时间中所占的份额。
二进制指数后退算法
轮流协议
轮询协议:要求节点之一被指定为主节点。主节点以循环的方式轮询每个节点。
缺点:引入轮询时间;若主节点有故障,则整个信道不可操作。
令牌传递协议:没有主节点,一个被称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换。
交换局域网
链路层寻址和ARP
MAC地址
并不是主机或路由器具有链路层地址,而是它们的适配器(即网络接口)具有链路层地址。
链路层地址也叫LAN地址,物理地址或MAC地址。
对大多数局域网而言,MAC地址长度为6字节。没有两块适配器具有相同的地址。
对于使用六字节地址的局域网(以太网和802.11)来说,广播地址为48个连续的1.
地址解析协议(ARP)
用于对网络层地址和链路层地址进行转换。
以太网
以太网:物理拓扑
1 | 总线:所有结点在同一冲突域 |
1 | 无连接:发送帧的网卡与接收帧的网卡不握手 |
以太网CSMA/CD算法
数据字段:46-1500字节。MTU为1500字节,不包含头部
目的地址:6字节。目的适配器的MAC地址。
源地址:6字节。传输该帧到局域网上的适配器的MAC地址。
类型字段:2字节,允许以太网复用多种网络层协议。
CRC:4字节,循环冗余检测
前同步码:8字节
链路层交换机
交换机自身对子网中的主机和路由器是透明的。
交换机转发和过滤
过滤:决定一个帧应该转发到某个接口还是应当将其丢弃的交换机功能。
转发:决定一个帧应该被导向哪个接口,并把帧移动到那些接口的交换机功能。
这两个功能借助于 交换机表。
表项包含
1 | 一个MAC地址; |
自学习
交换机是即插即用设备。
链路层交换机的性质
消除碰撞;异质的链路;管理。
交换机和路由器进行对比
虚拟局域网
VLAN
动态成员:端口可以动态分配给不同VLAN
在VLAN间转发:通过路由
多线缆连接
PPP
附加
MTU、IP MTU、TCP MSS设置上的区别及联系
1 | 1.MTU是一个二层的概念,即最大传输单元(Maximum Transmission Unit,MTU);以太网最大的mtu就是1500(它是不包含二层头部的,加上头部应该为1518 bytes,2bit的以太网类型+6bit的DMAC+6bit的SMAC+4bit的FCS),每个以太网帧都有最小的大小64bytes,最大不能超过1518bytes |
物理层
数据通信基础
物理介质
信道与信道容量
基带传输基础
频带传输基础
典型数字基带信号码型
- 数据传输速率=波特率*log2(幅值相位组合)
附加
CDMA
1 | https://blog.csdn.net/qq_43262059/article/details/106201119 |
FTP
1 | FTP协议运行在TCP连接上,保证了文件传输的可靠性。 |
在划分VLAN的以太网交换机的Trunk端口间传输的帧是802.1帧。
利用链路控制协议,大多数的产品通过协商可以省略标志符和地址字段,并且把协议字段由 2个字节减少到 1个字节。
二进制数字调制系统中,频带利用率最低的是2FSK。
SQL SERVER
库
Transact-SQL语言
DCL数据控制语言(进行安全性管理)
GRANT 授予权限
REVOKE 收回权限(不影响该用户从其他角色作为成员继承许可权限)
DENY 收回权限(禁止该用户从其他角色作为成员继承许可权限)
DDL数据定义语言(执行数据库任务)
CREATE 创建数据库或数据库对象
ALTER 修改——
DROP 删除——
DML数据操作语言(操作数据库中各对象)
select 从表或试图中检索数据
insert ——插入数据
update ——修改
delete ——删除
数据库
包含三个基本文件
(1)基本数据文件:有且只有一个 .mdf
(2)辅助数据文件:自由选择,0,1,2 .ndf
(3)日志文件:由于恢复数据库所需要的事务日志信息,至少一个。 .ldf
创建数据库
附一个源码
1 | create database DB2 |
修改数据库名字
1 | --修改数据库的名字 |
添加辅助文件
1 | --在DB1中添加一个辅助文件日志文件 |
添加日志文件
add log file
删除数据库
drop database 数据库名
表
设计表
创建需要确定下列特征:
要包含的数据类型;
表中的列数,每一列中数据的类型和长度;
哪些列允许空值;
是否要使用以及何处使用约束;
哪些是主键,哪些为外键。
数据类型
Bigint 大整型 8字节
int 常用的整型 4字节
smallint 小整型 2字节
tinyint 微整型 1字节
Bit 位类型 其取值只有0/1
decimal[(p[,s])]和numeric[(p[,s])] p总位数,s小数位 p默认为18,s默认为0
Money存储的货币值由八个字节,前四个代表整数,后四代表小数
日期和时间
Datetime 长度8字节
1753.1.1-9999.12.31
Smalldatetime 四字节
1900.1.1-2079.12.31
字符串
Char(n) n单位为字节,表示输入字符串的最大值,若超过则不存,小于则添加空格
varchar(n) 变动长度
Unicode
Nchar
Nvarchar
二进制字符串
Binary:binary(n)存储图像等数据
varbinary(n)
创建表
切换数据库名字 use 数据库名字
1 | --创建课程表(课程编号,课程名称,课程教师,上课时间) |
修改表
添加列:
1 | alter table 课程表 |
修改数据类型
1 | alter table 课程表 |
删除列
1 | alter table 课程表 |
修改列名
1 | exec sp_rename'表名.列名',‘新列名' |
修改表名
1 | exec sp_rename'原表名',‘新表名' |
约束
主键约束PRIMARY KEY
唯一确定表中每一按条记录的表示符
外键约束FOREIGN KEY
用于建立和加强两个表数据之间的连接
唯一约束UNIQUE
指定一个列或多个列的值具有唯一性,可为空
检查约束CHECK
限制输入值
默认约束DEFAULT
插入操作中没有提供输入值时系统会自动添加指定值
创建约束
1 | alter table 表名 |
1 | -对表中的课程编号添加主键约束 |
1 | --对课程名称添加一个唯一约束unique |
1 | --给上课教室添加默认约束 |
1 | --给上课教室添加检查约束 |
外界约束前提,列中的数据类型必须保持一致。引用的列必须为主键约束或者唯一约束。两个表的列名尽量一致。
删除约束
alter table 表名
drop constraint 约束名
若被引用要先删除外界约束再删除主键约束
在定义时约束
T-SQL语言
基本概念
标识符:数据库对象的名称
常规标识符与分隔标识符
常规标识符规则
第一个字符必须是英文大小写字母;_;@;#
后续字符除了第一字符,还有十进制数字,美元符号($)
批处理:一次处理多条语句
常量和变量
局部变量用DECLARE语句声明,作用范围仅在程序内部,局部变量的名称自己定义,以@开头。
声明语法
1 | DECLARE @name datatype |
对局部变量赋值
1 | SET @NAME=expression |
SET只能对一个变量赋值
SELECT可以对多个赋值
PRINT输出
1 | --声明两个变量 |
全局变量是事先定义好的,不允许创建修改,以@@开头
运算符
算数运算符
赋值运算符=
位运算符:两个整数类型表达式
比较运算符:除text,ntext.image数据类型外都可以用
逻辑运算符:
AND如果两个表达式都为true,则结果为true
BETWEEN如果操作数在某个范围,则结果为true
IN
LIKE
NOT
OR
一元运算符
流控制语句
BEGIN…END用于将多个语句组合为一个逻辑块
IF…ELSE
WHILE
BREAK
CONTINUE
CASE
1 | case |
WAITFOR延迟语句可以将它之后的语句在一个指定的时间间隔后执行
1 | Waitfor delay 'time'|time'time' |
1 | waitfor delay '00:00:03' |
GOTO
return无条件退出语句
数据库操作实例
查询数据
SELECT
1 | --查询教师 |
select *为查询所有列
DISTINCT
删除重复行
1 | --去重复 |
distinct后只能跟一个列
TOP
用于规定要返回的查询结果的数目
1 | --返回前3行所有数据 |
去掉重复数据后,后面的数据往前补
1 | select distinct top 3 任课教师 |
别名
1 | --别名查询,方式一 |
1 | 方式二 |
1 | 方式三 |
计算列
1 | seclect '原始学号'=学号,'调整学号'=学号-10 |
选择查询
基本语法
1 | SELECT LIST |
比较搜索条件
1 | <>不等于 |
1 | --查询任课教师为孙大烈的课程名称 |
范围搜索条件
包括范围
排他范围
1 | select 课程编号 |
列表搜索条件
IN关键字使用户可以与列表中的任意值匹配。
1 | select 课程编号 |
搜索条件中的字符匹配符
LIKE搜索匹配指定模式字符串
通配符
1 | % 替代0/多个字符 |
1 | 查询出姓王的老师 |
涉及空置的查询
NULL在数据库中表示不确定的值
判断为空
1 | 列名 is (not) null |
聚合函数
对一组值执行计算,并返回单个值。
1 | SUM([distinct]<列名>) |
1 | select 聚合函数 from 表名 |
1 | select sum (grade) as '总成绩' |
数据分组
group by根据一个或多个列对结果进行分组
1 | select 年级,SUM(人数) as '总人数', |
having通常与group by子句一起使用。
后跟查询条件
having子句可以包含聚合函数,where不可以
1 | select 学号,SUM(成绩) as '总成绩' |
order by
用于对指定结果进行排序,默认升序
降序排序可以用DESC关键字
1 | 查看成绩表 |
1 | select * |
表连接
从多个相关表中查询数据
内部连接
1 | select list from 表名1,表名2 |
查询学生的学号,姓名,性别,以及所在的班级名称和年级
1 | select 学生信息.姓名,学生信息.学号,学生信息.性别,班级信息.班级名称,班级信息.年级 |
1 | select 学生信息.姓名,学号,性别,//偷懒写法 |
内部连接只有共同匹配到的结果才会有输出
外部连接
外部连接会返回from子句中提到的至少一个表的所有行。
分为左外部连接、右外部链接和全外部连接
左外部连接对连接条件中左边的表不加限制,其余同理。
先写为左表,后写为右表。
left outer join,若左表的某行在右表没有找到匹配的行,则结果集中的右表的相对应的位置为null
right outer join
full outer join
子查询
用来表示where子句的条件
子查询用圆括号括起来
嵌套子查询与相关子查询
嵌套子查询
一个子查询可以包含另一个查询
1 | --查询计算机系学生选修了哪些课程 |
where子句后条件要什么,子查询就查什么
1 | select sno,grade |
相关子查询(单值子查询)
这样的子查询只返回一个值,然后将一列值与查询返回的值进行比较
在查询基础上创建新表
使用select …into语句可以在查询的基础上创建新表。
语法为
1 | select list |
添加数据
使用Insert和values插入
1 | insert[into] 表名[列名] |
使用insert和select插入行
使用select子句将一个表或多个表的值添加到另一个表中。
修改数据
update修改表中数据语法形式
1 | update 表名 set 列名=表达式 |
1 | update 成绩表 |
如果条件不统一,更改的值也不一样,则分开来写。
1 | update 成绩表 |
删除数据
1 | delete from 表名 |
(删除行)
1 | 删除固定行 |
视图
视图是基于某个查询结果的虚表。
标准视图、索引视图、分区视图。
视图的优点
着重于特定数据
简化数据操作
自定义数据
导出和导入数据
跨服务器组合分区数据
创建视图
1 | create view [数据库名 ] 视图名 |
1 | create view View_班级信息 |
修改视图名字
sp_rename修改视图名字
1 | exec sp_rename 'view_班级信息','view_班级信息2' |
对于表的操作,视图同样可以使用。
管理视图
1 | inbseret into view_学生信息 |
视图信息更改,原表信息也会更改。
alter既能修改数据内容,修改数据结构。
删除视图
1 | drop view 视图名1,视图名2 |
有条件删除
1 | delete from 视图名 |
索引
对数据库表中一个或多个列的值进行排序的结构。用来定位。
作用
加快数据检索;保持数据一致性;实现表与表之间参照完整性。
选择创建索引的数据列
定义有主键和外键的列;在指定范围中快速或频繁查询的列;连接中频繁使用的列;需要按排序顺序快速或频繁检索的列
类型
聚集索引:
索引的顺序决定了表中行的存储顺序,因此每个表中只能有一个聚集索引。
非聚集索引:
索引中的逻辑顺序并不等同与表中行的物理顺序。
事务
事务是作为单个逻辑单元执行的一系列操作。不可分割。
四大特性:
原子性;一致性;隔离性;永久性。
1 | begin transaction |
存储
系统存储过程
exec执行
用户自定义存储过程
参数有输入和输出参数
1 | create proc[edure] 存储过程名 |
参数可以设置默认值
数据库设计基础
E-R图
MySQL
MySQL
数据库基础
数据库系统概述
DB :database数据库
DBMS :Database Management System数据库管理系统
SQL :Structure Query Language专门用来与数据库通信的语言
数据模型
数据模型由数据结构,数据操作和完整性约束构成。
常见的数据模型
层次模型:用树形结构表示实体类型及实体间的联系的数据模型称为层次模型。
网状模型:用有向图结构表示实体类型以及实体间联系的数据模型称为网状模型。用网状模型编写应用程序及其复杂,数据的独立性较差。
关系模型:以二维表来描述数据。
关系数据库的规范化
根据满足规范的条件不同,可以分为五个等级:第一范式(1NF)、…,第五范式(5NF)。一般情况下,只要把数据规范到第三范式标准就可以。
第一范式
在第一范式中,数据表的每一行只包含一个实体的信息,并且每一行的每一列只能存放实体的一个属性。
第二范式
第二范式应该首先满足第一范式,第二范式要求数据库表中的每个实体必须可以被唯一的区分。为了实现区分各行记录,通常需要为表设置一个区分列,用以存储各个实体的唯一标识。
第三范式
第三范式要求一个关系表中不包含已在其他表中已包含的非关键字信息。
关系数据库的设计原则
○数据库内数据文件的数据组织应该获得最大限度的共享、最小的冗余度,消除数据及数据依赖关系中的冗余部分,是依赖于同一个数据模型的数据达到有效的分离。
○保证输入、修改数据时数据的一致性与正确性。
○保证数据与使用数据的应用程序之间的高度独立性。
实体与关系
一对一关系
一对多关系
多对多关系
数据库的体系结构
数据库三级模式结构
模式
也称逻辑模式或概念模式,是数据库中全体数据的逻辑结构和特征的描述,是所有用户的公共数据拼图。一个数据库只有一个模式,模式处于三级结构中的中间层。
外模式
也称用户模式,是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述,是数据库用户的数据视图,是与某一应用有关的数据的逻辑表示。外模式是模式的子集,一个数据库可以有多个外模式。
外模式是保证数据安全性的一个有力措施。
内模式
也称存储模式,一个数据库只有一个内模式。他是数据结构和存储方式的描述,是数据在数据库内部的表示方式。
三级模式之间的映射
数据库管理系统在三级模式之间提供了两层映射,分别为
外模式/模式映射
对于同一个模式可以由多个外模式。对于每一个外模式,数据库系统都有一个外模式/模式映射。当模式改变时,由数据库管理员作出改变,保证数据与程序的逻辑独立性。
模式/内模式映射
唯一,定义了数据库的全局逻辑结构与存储之间的对应关系。当数据库的存储结构改变时,有数据库管理员对其作出改变。保证数据与程序的物理独立性。
计算机组成原理
计算机系统概论
计算机的基本组成
冯诺依曼计算机的特点
(1)计算机由运算器,存储器,控制器,输入设备,输出设备五大部件组成。
(2)指令和数据以同等地位存放于存储器内,可按地址访问。
(3)指令和数据均用二进制数表示。
(4)指令由操作码和地址码组成,操作码用来表示操作的性质,地址码用来表示操作数在存储器中的位置。
(5)指令在存储器内顺序存放。
(6)机器以运算器为中心,输入输出设备与存储器间的数据传送通过运算器完成。
计算机的硬件框图
通常把运算器与控制器统称为中央处理器,即CPU。把输入/输出设备成为I/O设备,也可称为外部设备。
CPU与主存储器合起来称为主存。
控制元(CU)用来解释存储器中的指令,并发出各种操作命令来执行指令。
计算机硬件的主要技术指标
机器字长;
存储容量:MAR位数反映的存储单元的个数,MDR的位数反映了存储字长;
运算速度:MIPS(百万条指令每秒),CPI(执行一条指令所需的时钟周期);
附加
指令字长=存储字长=机器字长(三者可以相等也可以不等)
1 | 机器字长:CPU一次能处理的二进制数据的最大位数。通常与CPU内寄存器的位数有关。栗子:windows 64位/32位,这里的64位和32位指的就是该操作系统的机器字长。 |
用以指定待执行指令所在地址的是程序计数器
磁盘驱动器具有输入及输出功能
完整的计算机系统应该包括配套的硬件设备和软件系统
计算机与日常使用的袖珍计算器的本质区别在于自动化程度的高低。
有些计算机将一部分软件永恒地存于只读存储器中,称为固件
计算机系统软件包括:
1 | 标准程序库,如监控程序,用于监视计算机工作 |
存储元件(又称存储基元、存储元)用来存放一位二进制信息。存储单元由若干个存储元件组成,能存放多位二进制信息。每个存储单元中二进制代码的组合即为存储字,它可代表数值、指令、地址或逻辑。每个存储单元中二进制代码的位数就是存储字长。
计算机系统量化分析基础
计算机体系结构的概念
计算机体系结构概念的演变
阿姆道尔首次明确计算机体系结构是程序员所看到的计算机的属性,即概念性结构与功能特性。
对于通用寄存器型机器,这些属性主要是指:
1 | (1)数据表示:硬件能直接辨认和处理的数据类型 |
计算机体系结构、组成和实现
体系结构包括以下三个方面
1 | (1)计算机指令系统 |
系列机
1 | 一种指令集结构可以有多种组成。同样,一种组成可以有多种物理实现。系列机就是指在一个厂家生产的具有相同的指令集结构,但具有不同组成和实现的一系列不同型号的机器。 |
兼容性
1 | 向上(下)兼容指的是按某档机器编制的程序,不加修改的就能运行于比它高(低)档的机器 |
计算机体系结构的发展
并行性
1 | 计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。 |
从执行程序的角度来看,并行性等级从低到高可分为
1 | 指令内部并行:单条指令中各微操作之间的并行。 |
从处理数据的角度来看,并行等级从低到高可分为:
1 | 字串位串:每次只对一个字的一位进行处理。 |
按照指令和数据的关系,把计算机系统的结构分为4类。Flynn分类法
1 | 单指令流单数据流SISD |
提高并行性的技术途径
1 | (1)时间重叠 |
耦合度 反映多机系统中各机器之间物理连接的紧密程度和交互作用能力的强弱。
量化设计的基本原则:
1 | 1.大概率事件优先原则 |
具有高性能价格比的计算机系统是一个带宽平衡的系统,而不是看它使用的某些部件的性能
CPU性能公式
1 | 执行一个程序所需的CPU时间 |
总线
总线的基本概念
总线是连接多个部件的信息传输线,是各部件共享的传输介质。在某一时刻,只允许有一个部件向总线发送信息,而多个部件可以同时从总线上接受相同的信息。
M总线:存储总线
I/O总线:输入输出总线
总线的分类
片内总线
芯片内部 的总线
系统总线
计算机各部件之间 的信息传输线
数据总线
1 | 用来传输各功能部件之间的数据信息 |
地址总线
1 | 用来指出数据总线上的源数据或目的数据在主存单元的地址或I/O设备的地址。 |
控制总线
1 | 发出各种控制信号的传输线。 |
通信总线
用于 计算机系统之间 或 计算机系统与其他系统(如控制仪表、移动通信等)之间的通信
有串行通信和并行通信两种。
总线特性及性能指标
总线特性
总线的性能指标
总线结构
单总线结构
双总线结构
三总线结构
主存总线用于CPU与主存之间的传输;I/O总线供CPU与各类I/O设备之间传递信息;DMA总线用于高速I/O设备(磁盘,磁带等)与主存之间直接交换信息。
另一种三总线结构
Cache可通过系统总线与主存传递信息;且I/O设备与主存之间的传输也不必通过CPU,还有一条扩展总线。
SCSI:小型计算机接口;MODEM:调制解调器
四总线结构
高速总线上挂了一些告诉的I/O设备。
总线控制
总线判优控制
总线上所连接的各类设备,按其对总线有无控制功能可分为主设备(模块)和从设备(模块)两种。
集中式判优控制将控制逻辑集中在一处,如CPU;后者将控制逻辑分散在与总线连接的各个部件或设备上。
1 | 特点:只需要很少几根线就能按一定优先次序实现总线控制,并且很容易扩展设备,但对电路故障很敏感,且优先级别低的设备很难获得请求 |
1 | 对电路故障不如链式查询方法敏感,但增加了控制线(设备地址)数,控制也较复杂。 |
1 | 响应速度快,优先次序控制灵活,但控制线数量多,总线控制更复杂。 |
总线通信控制
目的:解决通信双方 协调配合 问题
总线传输周期(一次总线操作的时间)
1 | 申请分配阶段 主模块申请,总线仲裁决定 |
总线通信的四种方式
1 | 同步通信 由统一时标 控制数据传送 |
同步式
异步
应答方式又分为三种
1 | 不互锁方式: |
异步串行通信的数据传送速率用波特率来衡量。波特率是指单位时间内传送二进制数据的位数,单位用bps(位/s),记作波特。
同步传送速度高于异步传送。
半同步
1 | 同步 发送方 用系统 时钟前沿 发信号,接收方 用系统 时钟后沿 判断、识别 |
适用于系统工作速度不高但又包含了由许多工作速度差异较大的各类设备组成的简单系统。半同步通信比异步通信简单,可靠性高。缺点是对系统时钟频率不能要求太高,故从整体看,系统工作速度还不是很高。
分离式通信
1 | 一个总线传输周期 |
特点
1 | 1. 各模块有权申请占用总线 |
附加
影响总线带宽的因素:总线宽度,传输距离,总线发送和接受电路工作频率的限制以及数据传输形式。
PCI总线是一个与处理器时钟频率无关的告诉外部总线。
AGP总线是显卡专用的局部总线。
计算机之间的远距离通信除了直接由网卡经网线传输外,还可用RS-232总线通过载波电话线传输。
总线管理主要包括判优控制和通信控制。
在高档PC机中,系统总线主要连接CPU和存储器;PCI总线主要连接多媒体卡,高速局域网适配器,高性能图形版等高速部件;ISA或EISA总线连接图文传真机、调制解调器,打印机等低速部件。系统总线和PCI通过PCI桥路相连,PCI总线又通过标准总线控制器与IS和EIS总线相连。
指令系统
机器指令
每一趟机器语言的语句称为机器指令,又将全部机器指令的集合称为机器的指令系统。
指令由地址码和操作码构成。操作码可固定可不固定。
1 | 扩展操作码技术:操作码的位数随地址数的减少而增加 |
四地址指令:
需进行四次访存,取指令一次,取两个操作数两次,存放结果一次
三地址指令:
下条指令地址隐藏在程序计数器PC中,同样也需要进行四次访存。
二地址指令:
一地址指令:
零地址指令:无地址码
早起计算机指令字长、机器字长和存储字长均相等。
操作数类型和操作类型
操作类型
1 | 数据传送; |
寻址方式
分为数据寻址与指令寻址
指令寻址
分为顺序寻址和跳跃寻址。
数据寻址
指令地址码字段称为形式地址,记为A;而操作数的真实地址称为有效地址,记为EA。
立即寻址
1 | 形式地址A就是操作数 |
直接寻址
1 | A=EA |
隐含寻址
1 | 操作数地址隐含在操作码中 |
间接寻址
1 | 有效地址由形式地址间接提供 |
寄存器寻址
1 | EA=R_i |
寄存器间接寻址
1 | EA=(R_i)有效地址在寄存器中 |
基址寻址
1 | (1)采用专用寄存器作基址寄存器 |
1 | (2) 采用通用寄存器作基址寄存器 R0 作基址寄存器 |
变址寻址
1 | EA = ( IX ) +A IX 为变址寄存器(专用) |
相对寻址
1 | EA = ( PC ) + A |
堆栈寻址
多个寄存器可构成硬堆栈,指定的存储空间构成软堆栈。
指令系统结构的分类
CPU中用来存储操作数的存储单元主要有
1 | 堆栈,累加器,一组寄存器 |
寄存器-寄存器型
1 | 优点:指令字长固定,指令结构简洁,是一种简单的代码生成模型,各种指令的执行时钟周期数相近。 |
寄存器-存储器型
1 | 优点:可以在ALU指令中直接对存储器操作数进行引用,而不必先用load指令进行加载,容易对指令进行编码,目标代码比较紧凑。 |
存储器-存储器型
1 | 优点:目标代码最紧凑,不需要设置存储器来保存变量。 |
指令系统的设计和优化
基本原则
包括指令的功能设计和指令格式的设计
在确定哪些基本功能用硬件来实现时,主要考虑3个因素:速度,成本,灵活性
1 | 硬件实现:速度快,成本高。灵活性差 |
对指令系统的基本要求
1 | 完整性,规整性,正交性,高效率,兼容性 |
控制指令
1 | “调用者保存”(caller saving)方法:如果采用调用者保存策略,那么在一个调用者调用别的过程时,必须保存调用者所要保存的寄存器,以备调用结束返回后,能够再次访问调用者。 |
指令操作码的优化
等长扩展码
1 | 便于分级译码 |
定长操作码
1 | 固定长度的操作码:所有指令的操作码都是同一的长度。 |
指令系统的发展和改进
一个方向是强化指令功能,实现软件功能向硬件功能转移,基于这种指令集结构而设计实现的计算机系统称为复杂指令集计算机(CISC)。
八十年代发展起来的精简指令集计算机(RISC),其目的是尽可能地降低指令集结构的复杂性,以达到简化实现,提高性能的目的。
面向目标程序增强指令功能
提高运算型指令功能;
提高传送指令功能;
增加程序控制指令功能。
面向高级语言和编译程序改进指令系统
增加对高级语言和编译系统支持的指令功能;
高级语言计算机指令系统。
附加
零操作数来自栈顶和次栈顶。
寄存器间址有利于编制循坏程序。
在非立即寻址的一地址格式指令中,其中一个操作数通过指令的地址字段安排在寄存器或存储器中。
一个较完善的指令系统应该包括数据传送,算术逻辑运算,程序控制,输入输出,其他。
变址寻址只要用于处理数组程序;基址寻址支持多道程序的应用。
RR型指令,执行指令时不访问存储器。
RS型指令,执行指令时需访问存储器,且通过变址运算,时间最长。
CPU设计与实现
CPU的结构
CPU的寄存器
用户可见寄存器
1 | (1) 通用寄存器 |
控制寄存器
1 | 其中 MAR、MDR、IR 用户不可见 |
状态寄存器
1 | PSW寄存器 存放程序状态字 |
运算方法与ALU
算数移位运算
有符号数移位称为算数移位,无符号数移位称为逻辑移位。
单符号位判断溢出与双符号位判断溢出。
浮点四则运算
浮点加减法
1 | 对阶:求阶差,小阶向大阶对其 |
多级时序系统
指令周期
取出并执行一条指令所需的全部时间
微指令分析
1 | 取指阶段: |
在机器周期所含时钟周期数 相同 的前提下,
两机 平均指令执行速度之比 等于 两机主频之比
一个指令周期包含若干个机器周期
一个机器周期包含若干个时钟周期
附加
流水线
概述
流水线特点
1 | 流水过程由多个相关的子过程组成,这些子过程称为流水线的“级”或“段”。段的数目称为流水线的“深度”。 |
分类
1 | 单功能流水线和多功能流水线 |
1 | 静态流水线和动态流水线 |
1 | 部件级、处理机级及处理机间流水线 |
1 | 标量流水处理机和向量流水处理机 |
1 | 线性流水线和非线性流水线 |
基本流水线
性能分析
吞吐率
1 | 吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。 |
1 | 最大吞吐率取决于流水线中最慢一段所需的时间,该段成为流水线的瓶颈 |
加速比
1 | 流水线速度与等功能的非流水线速度之比 |
效率
1 | 流水线的设备利用率 |
效率是实际加速比S与最大加速比m之比。
当△t0不变时,流水线的效率与吞吐率呈正比。为提高效率而采取的措施,也有助于提高吞吐率。
注
1 | 流水线并不能减少(而且一般是增加)单条指令的执行时间,但能够提高吞吐率 |
流水线冲突
流水线冲突是指相邻或相近的两条指令因存在某种关联,后一条指令不能在原先指定的时钟周期开始执行。
三种不同类型的冲突
1 | 结构冲突(Structural Hazard):当指令在重叠执行过程中,硬件资源满足不了指令重叠执行的要求而发生的冲突。 |
导致结构冲突的常见原因:
1 | 功能部件不是全流水 |
避免结构冲突的方法:
1 | 所有功能单元完全流水化 |
有些设计方案允许结构冲突存在
1 | 降低成本 |
数据冲突
1 | 产生原因:当指令在流水线中重叠执行时,流水线有可能改变指令读/写操作数的顺序,使之不同于它们在非流水实现时的顺序,这将导致数据冲突。 |
1 | 通过定向技术减少数据冲突带来的暂停 |
编译调度
1 | 编译器可以通过重新排列代码的顺序来消除这种暂停,这种技术就是“流水线调度”或“指令调度” |
1 | 指令发射(Issue):指令从流水线的译码段进入执行段的过程称为指令发射。 |
指令级并行
记分牌的性能受限于以下几个方面:
1 | 程序代码中可开发的并行性,即是否存在可以并行执行的不相关的指令。 |
Tomasulo算法的优点
1 | 分布式硬件冲突检测。 |
缺点
1 | 高复杂性:需要大量硬件 |
分支预测
1 | 最简单的分支预测策略 |
machine learning
绪论
奥卡姆剃刀:若有多个假设与观察一致,则选择最简单的那个。
NFL定理(No Free Lunch Theorem):所有学习算法期望性能相同。
Independent and identically distributed,独立同分布,IID
模型评估与选择
经验误差与过拟合
若在m个样本中有a个样本分类错误,则称错误率为E=a/m;
精度=1-错误率;
学习器在训练集上的误差称为训练误差或经验误差,在新样本的误差称为泛化误差。
过拟合:把训练样本自身的一些特点当成了所有潜在样本都会具有的一般性质,这样就会导致泛化性能下降。
欠拟合:训练样本的一般性质尚未学好。
评估方法
留出法
直接将数据集划分为两个互斥的集合,其中一个集合作为训练集,另一个作为测试集。
分层采样:保留类别比例的采样方式。
交叉验证法
先将数据集D划分为k个大小相似的互斥子集,每次用k-1个子集的并集作为训练集,余下的那个子集作为测试集,从而进行k次训练和测试,最终返回k个测试的均值。通常把交叉验证法称为k折交叉验证法。
当k=m时,得到交叉验证法的特例:留一法(Leave-One-Out,简称LOC)。留一法评估结果往往比较准确,但计算开销较大。
自助法
以自主采样为基础,给定包含m个样本的数据集,每次随机从中挑选一个并放回,重复执行m次,则得到一个包含m个样本的数据集$D’$,样本在m次采样中始终不被取得的概率取极限为0.368.这样的测试结果,也称为包外估计。
自助法在数据集较小,难以有效划分训练/测试集时很有用。但是自助法产生的数据集会改变初始数据集分布,这会引入估计偏差,因此,在数据量足够时,留出法和交叉验证法更加常用。
性能度量
在预测任务中,给定样例集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$,其中$y_i$是示例$x_i$的真实标记。
回归任务最常用的性能度量是均方误差。
下面是一些常用的性能度量。
错误率与精度
对样本集D,分类错误率定义为
精度定义为
查准率、查全率与F1
查准率P:$P=\frac{TP}{TP+FP}$
查全率R:$R=\frac{TP}{TP+FN}$
查准率与查全率为一对矛盾的度量。通常只有在一些简单任务中,才可能使查准率与查全率都很高。
若一个学习器的PR曲线完全被另一个学习器的曲线包住,则可断言,后者的性能优于前者。
平衡点(Break-Even Point,简称BEP)为查准率与查全率相等时的取值。
但BEP度量还是简单一点,更为常用的是F1度量:
F1度量的一般形式-$F_\beta$
$\beta$>1查全率有更大影响。
ROC与AOC
ROC曲线的纵轴是真正例率(True Positive Rate,TPR),横轴是假正例率(False Positive Rate,FPR)
若一个学习器的ROC曲线被另一个学习器的曲线完全“包住”,则可断言后者性能优于前者。但是当有交叉时,一般难以判断,此时较为合理的依据是比较ROC曲线下的面积,即AUC.(Area Under ROC Curve)
$l_{rank}$定义为
AUC=1-$l_{rank}$
以下为对$l_{rank}$的通俗解释:
假设我们在做一个手写数字识别,识别样本数字是否为5,输入12个数字,经过算法得出每个数字的打分从小到大如下(分越高表示算法认为这个数字越接近5,用A表示正例,B表示反例):B1,B2,B3,B4,A1,B5,A2,A3,B6,A4,A5,A6
对于第一个正例A1,有两个反例比他大,则为2,对于第二三个正例,有一个,其余没有,则分子为2+1+1+0+0+0=4,分母为正例数,反例数=6*6=36,则此时$l_{rank}$为4/36=1/9
代价敏感错误率与代价曲线
代价敏感错误率为
在非均等代价下,ROC曲线不能直接反映出学习器的期望总体代价,而代价曲线则可达到该目的。
代价曲线图的横轴是取值为[0,1]的正概率代价
代价曲线图的横轴是取值为[0,1]的正例概率代价
其中p是样例为正例的概率;纵轴是取值为[0,1]的归一化代价
代价曲线绘制很简单:ROC曲线上每一点对应了代价平面上的一条线段,设ROC曲线上点的坐标为(FPR,TPR),则可计算出FNR,然后在代价平面上绘制一条从(0,FPR)到(1,FNR)的线段,线段下的面积表示了该条件下的期望总体代价。
比较检验
本节默认以错误率为性能度量,用$\epsilon$表示
假设检验
泛化错误率为$\epsilon$的学习器在一个样本上犯错的概率是$\epsilon$;测试错误率$\hat{\epsilon } $意味着在m个测试样本中恰好有$\hat{\epsilon } $*m个被误分类。
我们可使用“二项检验”来对“$\epsilon$<=$\hat{\epsilon}_0$”这样的假设进行检验。
在很多时候我们并不是做一次留出法估计,而是通过多次重复留出法或是交叉验证法等进行多次训练和测试,这样会得到多个测试错误率,此时可用”t-检验”。平均测试错误率$\mu$和方差$\sigma^2$为
考虑到k个测试错误率可看作泛化错误率$\epsilon_0$的独立采样,则变量
服从自由度为k-1的t分布。
交叉验证t检验
对于两个学习器A和B,若我们使用k折交叉验证法得到的错误测试率分别为$\epsilon^A_1$…和$\epsilon_1^B$…,则可使用k折交叉验证”成对t检验”来进行比较检验。可根据差值来对学习器A与B性能相同这个假设做t检验,计算出插值的均值$\mu$和方差$\sigma^2$,在显著度$\alpha$下,若变量
小于临界值,则假设不能被拒绝。
McNemar检验
若我们做的假设是两学习器性能相同,则应有$e{01}=e{10}$,那么变量$|e{01}-e{10}|$应当服从正态分布。McNemar检验考虑变量
服从自由度为1的$\chi^2$分布
Friedman检验与Nemenyi后续检验
之前介绍的都是在一个数据集上比较两个算法的性能,而在很多时候,我们会在一组数据集上比较多个算法。此时可以使用基于算法排序的Friedman检验。
当所有算法性能相同这个假设被拒绝,则说明算法的性能显著不同,这时需要后续检验来区分,常用的有Nemenyi后续检验。
偏差与方差
偏差度量了学习算法的期望预测与真实结果的偏离程度,即刻画了学习算法本身的拟合能力。
方差度量了同样大小的训练集的变动所导致的学习性能的变化,即刻画了数据扰动所造成的影响。
噪声则表达在当前任务上任何学习算法所能达到的期望泛化误差的下界,即刻画了学习问题本身的难度,
泛化误差可分解为偏差、方差与噪声之和。
线性模型
基本形式
f(x)=w1x1+w2x2+…+wdxd+b
一般用向量形式写成
线性回归
线性回归试图学得
多元线性回归
对数线性回归
广义线性模型
对数几率回归
对数几率函数,“Sigmod函数”,将Z值转换为1个接近0或1的y值,并且其输出在z=0附近变化很陡。
带入得
将上述式子变换得
注:极大似然估计,梯度下降法,牛顿法,请参考实验。
线性判别分析
线性判别分析(Linear Discriminant Analysis,简称LDA)是一种经典的线性学习方法。
LDA的思想非常朴素:给定训练样例集,设法将样例投影到一条直线上,使得同类样例的投影点尽可能接近、异类样例的投影点尽可能远离;在对新样本进行分类时,将其投影到同样的这条直线上,再根据投影点的位置来确定新样本的类别。
定义类内散度矩阵
类间散度矩阵$S_b=(\mu_0-\mu_1)(\mu_0-\mu_1)^T$
则有最大化目标
这就是LDA想要最大化的目标,即$S_b与S_w$的“广义瑞利商”。
上述式子只与$w$的方向有关,与长度无关,故不是一般性,令$w^TS_ww=1$,根据拉格朗日乘子法,等价于
注意到$S_bw$的方向恒为$\mu_0-\mu_1$
则令$S_bw=\lambda(\mu_0-\mu_1)$
代入得$w=S^{-1}_w(\mu_0-\mu_1)$
考虑到数值解的稳定性,在实践中通常是对$S_w$进行奇异值分解,即$S_w=U\Sigma V^T$
值得一提的是,LDA可从贝叶斯决策理论的角度来阐述,并可以证明,当两类数据同先验、满足高斯分布且协方差相等时,LDA可达到最优分类。
可将LDA推广到多分类任务。
多分类学习
多分类学习的基本思路是拆解法,即将多分类任务拆为若干个二分类任务求解 。最经典的拆分策略有三种,一对一(one vs one,OvO),一对其余(one vs rest,OvR),多对多(manay vs many,MvM)。
OvO将这N个类别两两配对,从而产生N(N-1)/2个二分类任务。
OvR则是每次将一个类的样例作为正例,所有其他类的样例作为反例来训练N个分类器。在测试时若仅有一个分类器预测为正类,则对应的类别标记作为最终分类结果。若有多个分类器预测为正类,则通常考虑各分类器的预测置信度,选择置信度最大的类别标记作为分类结果。
可以看出,OvR只需要训练N个分类器,而OvO需训练N(N-1)/2个分类器,因此,OvO的存储开销和测试时间开销通常比OvR大。但在训练时,OvR的每个分类器均使用全部训练样例,而OvO的每个分类器仅用到两个类的样例,因此,在类别很多时,OvO的训练时间开销通常比OvR更小。至于预测性能,多数情况下二者差不多。
介绍一种MvM最常用的技术,纠错输出码(Erroe Correcting Output Codes,ECOC),它是将编码的思想引入类别拆分,并尽可能在解码过程中具有容错性。EOOC工作过程主要分为两步:
编码:对N个类别做M次划分,每次划分将一部分划分为正类,一部分划分为反类,从而形成一个二分类训练器;这样一共产生M个训练集,可训练出M个分类器。
解码:M个分类器对测试样本进行预测,这些预测标记组成一个编码。将这个预测编码与每个类别各自的编码进行比较,返回其中距离最小的类别作为最终预测结果。
对于同一个学习任务,EOOC编码越长,纠错能力越强。
类别不平衡问题
一个基本策略是再缩放。
大体有三种做法:
欠采样:去除一些样例使得正反例数目接近
过采样:增加一些样例使得正反例数目接近
第三类是基于原始数据训练,,再进行阈值转移。
欠采样法的时间开销通常远小于过采样。过采样法不能简单对初始样本进行重复采样,否则会过拟合。
决策树
基本流程
决策树学习基本算法
划分选择
信息增益
信息熵为度量样本集合纯度最常用的一种指标。假定样本集合D中第k类样本所占的比例为$p_k$,则D的信息熵定义为
Ent(D)的值越小,则D的纯度越高。
假定离散属性有v个可能的取值,若使用a来对样本集D进行划分,则会产生V个分支结点,其中第v个分支结点包括了D中所有在属性a上取值为$a^v$的样本,记为$D^v$。则可又获得信息增益:
著名的ID3决策树学习算法就是以信息增益为准则来选择划分属性的。
X和Y的交互信息
样本熵:各类样本熵之和
增益率
但是,显而易见,信息增益准则对于可取数目较多的属性有所偏好,所以我们引入增益率。著名的C4.5决策树算法便是使用增益率来哈分最优划分属性的。增益率定义为
需要注意,增益率准则对于可取纸2数目较少的属性有所偏好,因此C4.5并不是直接使用增益率准则来进行划分的,而是采用了一个启发式算法,先从候选划分属性中zhaochu1信息增益高于平均水平的属性,再从中选择增益率最高的。
基尼系数
CART决策树采用基尼指数来选择划分属性。数据集D的纯度可用基尼系数来度量:
直观理解的话,基尼系数反应了从数据集D中随机抽取两个样本,其分类不一致的概率。
属性a的基尼系数定义为
剪枝处理
剪枝(pruning)是决策树学习算法对应过拟合的主要手段。决策树基本策略有预剪枝(prepruning)和后剪枝(postpruning)。
预剪枝是在决策树生成过程中,对每个结点在划分前进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点;后剪枝则是先从训练集生成一颗完整的决策树,然后自底向上地对非叶结点进行考察,若将该节点对应的子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。
预剪枝使决策树很多分支都没有展开,降低了过拟合风险,减少了决策树训练时间开销和测试时间开销,但会带来欠拟合的风险。
后剪枝决策树的欠拟合风险很小,泛化性能往往优于预剪枝决策树。
连续与缺失值
连续值处理
由于连续属性的可取数目不再有限,因此不能直接根据连续属性的可取值来对结点进行划分。此时,连续属性离散化技术派上用处。最简单策略就是采用二分法,正是C4.5决策树算法采用的机制。
缺失值处理
在以下三方面影响到决策树构建
影响杂质测量计算方式;影响如何将缺失值的实例分配到子节点;影响具有缺失值的测试实例如何被分配
原信息增益=去除缺失值信息增益*(去除后的样本数/总样本数)
多变量决策树
每个节点划分为线性分类器。对属性的线性组合进行测试。
考点
基于决策树分类的优点
构建过程计算资源开销小;
分类未知样本速度极快;
对于小规模的树比较容易解释;
在许多小的简单数据集合性能与其他方法相近。
TOP-DOWN决策树
过拟合
pre-pruning
如果所有的实例都属于同一类别就停止;如果所有的属性值都一样就停止。
更加具有限制性的,如果实例的数量少于用户指定的阈值;如果实例的类别分布与可用的特征无关;如果扩展当前节点不能改善纯度。(基尼系数或信息增益)
post-pruning
将决策树增长到其全部内容,以自下而上的方式修剪。若修剪后泛化错误得到改善,则将子树替换为叶子。可使用MDL修剪。
MDL
最小描述长度准则—Minimum Description Length
分发实例的过程,将缺失值按照权重分别分发给不同的分支。如下图:
对于新实例有缺失值的情况下如何分类,也要利用概率来看。
惩罚项
惩罚项比重影响 :比重大时降低模型复杂度 ;比重适当时模型复杂度与问题匹配 ;比重小时、退化成原模型
支持向量机
support vector machine,SVM
间隔与支持向量
给定训练集样本D,分类学习最基本的想法就是基于训练集D在样本空间中找到一个划分超平面。
在样本空间中,划分超平面可通过如下线性方程来描述:$w^T x+b$
其中$w$为法向量,决定了超平面的方向,b为位移量。我们将该平面记做(w,b)
样本空间中任一点x到该超平面的距离可写为
假设超平面可将训练样本正确分类,对于$(x_i,y_i)$,若$y_i=1$,则有$w^T x+b>$0,若为-1则<0
令
如图所示,距离超平面最近的这几个训练样本使上述等号成立,他们被称为支持向量,两个异类支持向量,两个异类支持向量到超平面的距离之和为$\gamma=\frac{2}{||w||}$,它被称为间隔。
想要找到最大间隔,即找到最大$w与b$,使得$\lambda$最大。
显然,为了最大化间隔,仅需要最大化$||w||^{-1}$,这等价于最小化$||w||^2$,于是便有
这就是SVM的基本型。
对偶问题
对于SVM的基本型,添加拉格朗日乘子$\alpha\ge0$,则该问题拉格朗日函数可以写为
其中$\alpha_i=(\alpha_1,\alpha_2,…,\alpha_m)$
分别求偏导,$w=\sum{i=1}^{m}\alpha_i y_i x_i,0=\sum{i=1}^{m}\alpha_i y_i$
代入,可得对偶问题如下
解出$\alpha$后,求出w与b即可得到模型
因为上述过程需要满足KK条件,即要求
$\alpha_i\ge0$
$y_if(x_i)-1\ge0$
$\alpha_i(y_if(x_i)-1)=0$(13)
若$\alpha_i$=0,则该样本不会在12的求和中出现,也就不会对f(x)有影响‘
若后面等于0,则所对应的样本点位于最大间隔边界上,是一个支持向量。
如何求解11呢?我们介绍一种高效的SMO算法。
暂且跳过这部分。
核函数
若在原始样本空间内不存在一个能正确划分两类样本的超平面,面对这类问题,我们可将样本从原始空间映射到一个高维的特征空间,使得样本在这个高维空间内线性可分。并且若原始空间有限,则一定存在一个高维特征空间使样本可分。
令$\phi(x)$表示将x映射后的特征向量,于是,在特征空间中划分超平面所对应的模型可以表示为
$f(x)=w^T\phi(x)+b$
同上,其对偶问题是
求解21会涉及到计算$\phi(x_i)^T\phi(x_i)$,这是样本$x_i与x_j$映射到特征空间后的内积,计算困难,为了避开这个障碍,可以设想一个这样的函数
即$x_i与x_j$在特征空间的内积等于他们在原始样本空间中通过函数$\kappa$计算的结果。
则可进行求解,求解得
这里的$\kappa(,)$就是核函数,24显示出模型最优解可通过训练样本的核函数展开,这一展开式也称为“支持向量展式”。
关于核函数,我们有以下定理:
暂且略过
软间隔与正则化
大多数时候我们很难找到合适的核函数,所以为了缓解这一问题,我们会允许支持向量机在一些样本上出错。为此要引入软间隔的概念。
软间隔则是允许某些样本不满足约束
$y_i(w^Tx_i+b)\ge1$(28)
当然,在最大化间隔的同时,不满足约束的样本应尽可能少。于是,优化目标可以写为
贝叶斯分类器
贝叶斯决策论
[最大后验估计(Maximum-a-Posteriori (MAP) Estimation) ]
最大似然估计(MLE)选择值 使观察到的数据的概率最大化
最大后验估计(MAP) 选择在观察到的数据和先验条件下最有可能的值
缺点
MLE: 如果数据集太小,就会过度拟合
MAP: 两个有不同预设的人最终会导致不同的估计值
极大似然估计
朴素贝叶斯分类器
半朴素贝叶斯分类器
其中$pa_i$为属性$x_i$所依赖的属性,称为$x_i$的父属性。问题的关键转换为如何确定每个属性的父属性,不同的做法产生不同的独依赖分类器。
最直接的做法是假设所有属性都依赖于同一个属性,称为“超父”,然后通过交叉验证等模型选择方法来确定超父属性,由此形成了SPODE(Super-Parent ODE)方法,例如(b)中,$x_1$是超父属性。
TAN则是在最大带权生成树算法的基础上,通过以下步骤化简为(c)的树形结构。
贝叶斯网
Directed Acyclic Graph(DAG):有向无环图
Conditional Probability Table(CPT):条件概率表
具体来说,一个贝叶斯网B由结构G和参数$\theta$两部分构成,即$B=
网络结构G为DAG,其每个结点对应于一个属性,若两个属性有直接依赖关系,则他们由一条边连接起来;参数$\theta$定量描述这种依赖关系,假设属性$xi$在G中的父节点为$\pi_i$,则$\theta$包含了每个属性的条件概率表$\theta{x_i|\pi_i}=P_B(x_i|\pi_i)$
结构
给定父节点集,贝叶斯网假设每个属性与它的非后裔属性独立。
为了分析有向图中变量间的条件独立性,可使用有向分离。我们先把有向图转变成为一个无向图:
*找出有向图中的所有V型结构,在V型结构的两个父节点之间加上一条无向边;
*将所有有向边改为无向边
由此产生的无向图称为道德图,令父节点相连的过程称为道德化。
若变量x和y能在图上z分开,即从道德图中将变量集合z去除后,x和y分属两个连通分支,则称x和y被z有向分离,$x\perp y|z$成立。
学习
贝叶斯网学习的首要任务就是根据训练数据集来找出结构最恰当的贝叶斯网。评分搜索是求解这一问题的常用办法。具体来说,我们先定义一个评分函数,以此来评估贝叶斯网与训练数据的契合程度,然后基于这个评分函数来寻找结构最优的贝叶斯网。
常用评分函数通常基于信息论准则,此类准则将学习问题看作一个数据压缩任务,学习的目标是找到一个能以最短编码长度描述训练数据的模型,此时编码的长度包括了描述模型自身所需的编码位数和使用该模型描述数据所需的编码位数。对于贝叶斯网学习而言,模型就是一个贝叶斯网,同时,每个贝叶斯网描述了一个在训练数据上的概率分布,我们应选择那个综合编码长度最短的贝叶斯网,这就是最小描述长度准则。(Minimal Description Length,MDL)
给定训练集D,贝叶斯网$B=
其中,|B|是贝叶斯网的参数个数;$f(\theta)$表示描述每个参数$\theta$所需的编码位数。而
是贝叶斯网B的对数似然。显然,28的第一项是计算编码贝叶斯网B所需的编码位数,第二项是表述B所对应的概率分布$P_B$对D的描述有多好。此时,学习任务转换为优化任务,寻找一个贝叶斯网B使得评分函数最小。
若$f(\theta)=1$,则得到AIC评分函数。
若$f(\theta) =\frac12log\ m$,则得到BIC评分函数。
当=0时,评分函数退化为负对数似然函数,学习任务退化为极大似然估计。
为最小化评分函数,只需要对网络结构进行搜索,而候选结构的最优参数可直接在训练集计算得到。
但是,在所有可能的网络空间搜索最优贝叶斯网络是一个NP问题。一般有两种策略在有限时间内求得近似解,第一种为贪心法,第二种是通过给网络结构施加约束来削减搜索空间。
推断
贝叶斯网络的近似推断常使用吉布斯采样来完成,这是一种随机采样方法。
EM算法
在现实中,会存在许多未观测变量。未观测变量的学名是隐变量,令X表示已观测变量集,Z表示隐变量集,$\theta$表示模型参数,若想要对$\theta$做极大似然估计,则应最大化对数似然
$LL(\theta|X,Z)ln\ P(X,Z|\theta)$
由于Z是隐变量,我们可通过对Z计算期望,来最大化已观测数据的对数“边际似然”
$LL(\theta|X)=ln\ P(X|\theta)=ln\sum_{Z}P(X,Z|\theta)$(35)
聚类
聚类任务
在无监督学习中,训练样本的标记信息是未知的,目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律,为进一步的数据分析提供基础,此类学习任务应用最广的是聚类。
聚类试图将数据集中的样本划分为若干个通常是不相交的子集,每个子集称为一个簇。
性能度量
聚类性能度量也称为聚类“有效性指标”。
聚类性能度量大致有两类,一类是将聚类结果与某个“参考模型”进行比较,称为“外部指标”;另一类是直接考察聚类结果而不利用任何参考模型,称为“内部指标”。
距离计算
对函数$dist$,若他是一个距离度量,则需要满足一些基本性质
非负性:$dist(x_i,x_j)\ge0$
同一性:$dist(x_i,x_j)=0当且仅当x_i=x_j$
对称性
直递性
对于给定样本
最常用的闵可夫斯基距离
当p=2时,闵可夫斯基距离即为欧氏距离
当p=1时,闵可夫斯基距离即为曼哈顿距离
定义域为{1,2,3}这样的属性为有序属性,而定义域为{飞机,轮船,火车}则为无序属性,闵可夫斯基距离用于有序属性。
对无序属性可采用VDM(Value Difference Metric)。令$m{u,a}$表示属性u上取值为a的样本数,$m{u,a,i}$表示在第i个样本簇中在属性u上取值为a的样本数,k为样本簇数,则属性u上两个离散值a与b之间的VDM距离为
于是,将闵可夫斯基距离和VDM结合即可处理混合属性。假定有$n_c$个有序属性、$n-n_c$个无序属性,不失一般性,令有序属性排列在无序属性之前,
当空间中不同属性的重要性不同时,可使用加权距离。
需要注意的是,通常我们是基于某种形式的距离来定义“相似度度量”,距离越大,相似度越小,然而用于相似度度量的距离未必一定要满足距离度量的所有基本性质。不满足直递性的距离称为非度量距离。
原型聚类
也称为基于原型的聚类,此类算法假设聚类结构能通过一组原型刻画。通常对原型进行初始化,然后对原型进行迭代更新求解。
k均值算法
给定样本集$D={x_1,x_2,..,x_m}$,“k均值”算法针对聚类所得簇划分$C={C_1,C_2,…,C_k}$最小化平方误差
k均值算法采用了贪心策略,通过迭代优化来近似求解式。
学习向量量化
Learning Vector Quantization(LVQ)与一般的聚类算法不同,LVQ假设数据样本带有标记类别,学习过程利用样本的这些监督信息来辅助聚类。
给定样本集
每个样本$xj$是由n个属性描述的特征向量$(x{j1};x{j2};…;x{jn})$,$y_i\in \gamma$是样本$x_j$的类别标记。LVQ的目标是学得一组n维向量${p_1,p_2,…,p_n}$,每个原型向量代表一个聚类簇,簇标记$t_i \in \gamma$。
高斯混合模型
参考下面这篇文章
https://zhuanlan.zhihu.com/p/30483076
密度聚类
此类算法假设聚类结构能通过样本分布的紧密程度确定。
DBSCAN是一种著名的密度聚类算法,它基于一组“邻域”参数$(\varepsilon,MinPts)$来刻画样本分布的紧密程度。给定数据集$D={x_1,x_2,…,x_m}$,定义以下概念
$\varepsilon-$邻域:对于x,其$\varepsilon$邻域包含样本集D中与$x_j$的距离不大于$\varepsilon$的样本
核心对象:若x的$\varepsilon$邻域至少包含MinPts个样本,则为一个核心对象
密度直达:若$x_j$位于$x_i$的$\varepsilon$邻域中,且$x_i$是核心对象,则称$x_j$由$x_i$密度直达
密度可达:对$x_i$与$x_j$,若存在样本序列
其中$p1=x_i,p_n=x_j$且$p{i+1}$由$p_i$密度直达,则称$x_j$由$x_i$密度可达
密度相连:对$x_i$与$x_j$,若存在$x_k$使得$x_k$使得二者均由$x_k$密度可达,则称二者密度相连。
DBSCAN将簇定义为:由密度可达关系导出的最大的密度相连样本集合。
层次聚类
层次聚类试图在不同层次上对数据集进行划分,从而形成树形的聚类结构。数据集的划分可采用“自顶向上”的聚合策略,也可采用“自顶向下”的分拆策略。
AGNES是一种采用自底向上聚合策略的层次聚类算法。它先将数据集中的每个样本看作一个初始聚类簇,然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并。
当聚类簇距离由
计算时,AGNES算法被相应地称为单链接,全链接和均链接算法。
降维与度量学习
k近邻学习
k-Nearest Neighbor,简称kNN学习是一种常用的监督学习方法。
其工作机制是:给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个邻居的信息来进行预测。
k近邻学习没有显示的训练过程,是“懒惰学习”的主要代表,此类学习技术在训练阶段仅仅是把样本保存起来,训练时间开销为0,待收到测试样本后再进行处理;相应的,那些在训练阶段就对样本进行学习处理的方法称为急切学习。
k近邻的错误率小于贝叶斯的两倍。
低维嵌入
通过某种数学变换将原始高维属性空间转变为一个低维子空间。
若要求原始空间中样本之间的距离在低维空间中得以保持,即得到多维缩放(Multiple Dimensional Scaling,MDS)这样一种经典的降维方法。
主成分分析
Principal Component Analysis,PCA
Untitled
Verilog
数字表示
基本格式:< 位宽 >’< 数制的符号 >< 数值 >
h十六进制
d十进制
o八进制
b二进制
向量
可直接进行加减等运算,方括号位于向量名前方。eg: reg [7:0] data
数组
方括号位于数组名的后面。括号内的第一个数字为第一个元素的序号,第二 个数字为最后一个元素的序号,中间用冒号隔开。
eg: wire array [15:0];
参数
可以通过 parameter 关键字声明参数以增强模块可拓展性和可读性。
在模块实例化时,可以使用 #() 将所需的实例参数覆盖模块的默认参数。
局部参数可以用 localparam 关键字声明,它不能够进行参数重载。
eg:
1 | module adder #( |
在我们例化这个模块时,可以进行如下操作:
1 | // 覆盖宽度,修改为 6 |
局部参数 localparam 和参数类似,但是不能在例化时被覆盖。
运算
按位运算
按位取反 ~
按位与 &
按位或 |
按位异或 ^
逻辑运算
• 逻辑取反!
• 逻辑与 &&
• 逻辑或 ||
缩减运算
• 缩减与 &:对一个多位操作数进行缩减与操作,计算所有位之间的与操作结果,例如:&(4’b1011) 的结果为 0
• 缩减或 |:对一个多位操作数进行缩减或操作,计算所有位之间的或操作结果。例如:|(4’b1011) 的结果为 1
• 缩减异或 ^:对一个多位操作数进行缩减异或操作,计算所有位之间的异或操作结果。例如: ^(4’b1011) 的结果为 1
缩减或非、缩减异或、缩减同或是类似的。
移位运算
• 逻辑右移>>:1 个操作数向右移位,产生的空位用 0 填充
• 逻辑左移<<:1 个操作数向左移位,产生的空位用 0 填充
• 算术右移>>>:1 个操作数向右移位。如果是无符号数,则产生的空位用 0 填充;有符号数则用其符号 位填充
• 算术左移<<<:1 个操作数向左移位,产生的空位用 0 填充
其他运算
• 拼接 {,}:2 个操作数分别作为高低位进行拼接,例如:{2’b10,2’b11} 的结果是 4’b1011
• 重复 {n{m}}:将操作数 m 重复 n 次,拼接成一个多位的数。例如:a=2’b01,则 {2{a}} 的结果 是 4’b0101
• 条件? ::根据? 前的表达式是否为真,选择执行后面位于: 左右两个语句。例如:assign c = (a > b) ? a : b,如果 a 大于 b,则将 a 的值赋给 c,否则将 b 的值赋给 c
组合逻辑
always
不推荐使用 always 块来表示组合逻辑。不正确的使用会生成大量锁存器。
下面的例子是一个 32-5 优先编码器,如果 tlb_hit_array 全为 0,那么 tlb_hit_index 也为 0。 always 块中被赋值的变量只能是 reg 类型,但是该编码器并不会综合出寄存器或者锁存器,这是因为 Verilog 中的寄存器 (reg) 和硬件上的寄存器不能完全等价。 如果去掉 tlb_hit_index = 5’d0; 一句,则会综合出锁存器。
1 | reg [4 :0] tlb_hit_index; |
模块声明和例化
模块被包含在关键字 module、endmodule 之内。
1 | module adder ( // 模块名称声明 |
Generate 块
这里只介绍 generate for 块。
generate for 的主要功能就是对模块或组件以及 always 块、assign 语句进行复制。 使用 generate for 的时候, 必须要注意以下几点要求
• 在使用 generate for 的时候必须先声明一个 genvar 变量,用作 for 的循环变量。genvar 是 generate 语句中的一种变量类型,用于在 generate for 语句中声明一个正整数的索引变量。
• for 里面的内嵌语句, 必须写在 begin-end 里
• 尽量对 begin-end 顺序块进行命名
generate for 的语法示例如下:
1 | genvar i; |
测试代码
时延语句
仿真中还经常使用时延来构造合适的仿真激励。它是不可综合的,仅能够在仿真中使用。时延分两类,一是 语句内部时延,二是语句间时延,其示例如下所示:
1 | // 语句内部时延 |
两种方式都表达在五个时间单位后,将 A 的值赋为 1。
initial 语句
一般用来生成复位信号和激励。只在仿真开始时执行一次。
1 | // 测试代码中 |
会生成一个 100MHz 的时钟,一个 50ns 有效的复位信号。
系统任务
系统任务可以被用来执行一些系统设计所需的输入、输出、时序检查、仿真控制操作。所有的系统任务名称 前都带有符号 $ 使之与用户定义的任务和函数相区分。
常见的系统任务:
• $display:用于显示指定的字符串,然后自动换行(用法类似 C 语言中的 printf 函数)
• $time:可以提取当前的仿真时间
• $stop:暂停仿真
• $finish:终止仿真
• $random:生成随机数
• $readmemh:读入一个 16 进制数的文件以初始化 reg
测试设计
测试最基本的结构包括信号声明、激励和模块例化。 测试模块声明时,一般不需要声明端口。因为激励信号一般都在测试模块内部,没有外部信号。 声明的变量应该能全部对应被测试模块的端口。当然,变量不一定要与被测试模块端口名字一样。但是被测试模块输入端对应的变量应该声明为 reg 型,输出端对应的变量应该声明为 wire 型。 仿真过程中可以使用 $display 显示当前仿真进度或者测试结果。 在测试完成或者发现错误时可以使用 $finish; 或者 $stop; 来停止仿真。