白衣苍狗

DancingLinksX|精确覆盖&重复覆盖

Dylan 发布于 2017-12-27 收录于 OI

DancingLinksX|精确覆盖&重复覆盖

本文介绍DLX及其在精确覆盖和重复覆盖问题中的应用。

在DLX之前先了解精确覆盖和重复覆盖。

精确覆盖

给出一个仅有0、1的矩阵，选择其中的一些行使得这些行组成的集合中每一列都有且仅有一个1，求方案的存在性及具体方案。

重复覆盖

给出一个仅有0、1的矩阵，选择其中的一些行使得这些行组成的集合中每一列都至少有一个1，求方案的存在性及具体方案。

最小生成树

Dylan 发布于 2017-12-16 收录于 OI

最小生成树

无向图：Prim&Kruskal

Prim

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
//Prim
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
using namespace std;
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}
template<typename T>
void read(T& w)
{
	char r;
	for(r=getchar();r<48||r>57;r=getchar());
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
}
const int maxn=103;
const int maxm=maxn*(maxn-1)/2;
int n,m;
struct EDGE
{
	int to,nxt,w;
	void init(int too,int nxtt,int ww)
	{
		to=too,nxt=nxtt,w=ww;
	}
}edge[maxm<<1];
int ek=0;

int node[maxn];
void addEdge(int from,int too,int ww)
{
	edge[++ek].init(too,node[from],ww);
	node[from]=ek;
}
void input()
{
	read(n),read(m);
	int x,y,l;
	for(int i=1;i<=m;++i)
	{
		read(x),read(y),read(l);
		if(x!=y)
		{
			addEdge(x,y,l);
			addEdge(y,x,l);
		}
	}
}
bool operator<(const EDGE& a,const EDGE& b)
{
	return a.w<b.w;
}
template<typename T>
struct HEAP
{
	T ary[maxm<<1];
	int f;
	HEAP(){f=0;}
	void clear(){f=0;}
	bool empty(){return f==0;}
	void push(const T& w)
	{
		ary[++f]=w;
		for(int k=f;k!=1&&ary[k]<ary[k/2];k=k/2)
		{
			Swap(ary[k],ary[k/2]);
		}
	}
	T top(){return ary[1];}
	T pop()
	{
		T tmp=ary[1];
		ary[1]=ary[f--];
		for(int k=1,son=k*2;son<=f;k=son,son=k*2)
		{
			if(son+1<=f&&ary[son+1]<ary[son])
				son=son+1;
			if(ary[son]<ary[k])
				Swap(ary[son],ary[k]);
			else break;
		}
		return tmp;
	}
};
int s=1;
bool vis[maxn];
HEAP<EDGE> h;
int Prim()
{
	int sum=0;
	for(int k=2,ff=1;k<=n;++k)
	{
		vis[ff]=true;
		for(int i=node[ff];i;i=edge[i].nxt)
		{
			int v=edge[i].to;
			if(!vis[v])
				h.push(edge[i]);
		}
		EDGE tmp;
		for(tmp=h.pop();vis[tmp.to];tmp=h.pop());
		ff=tmp.to;
		sum+=tmp.w;
	}
	return sum;
}
int main()
{
	input();
	printf("%d\n",Prim());
	return 0;
}

有向图：朱刘算法

概念

最小树形图算法（时间复杂度O(VE)）

数论

Dylan 发布于 2017-12-13 收录于 OI

数论

最大公因数GCD

辗转相除法

略。

Stein

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
//Stein
gcd(a,b)
{    
    if(a==b)
    {
        gcd=a;
        return;
    }
    if(a为偶数b为奇数)//一定没有2因子
        gcd=gcd(a/2,b);
    if(a为奇数b为偶数)//同上
        gcd=gcd(a,b/2);
    if(a,b均为偶数)
        gcd=2*gcd(a/2,b/2);//一定有2因子
    if(a,b均为奇数)
    {
        if(a<b)    gcd=gcd(b,a);
        gcd=gcd(a-b,b);
    }
}

斐波那契数列最大公因数的性质

gcd(fn,fm)=f(gcd(n,m))

逆元

概念

定义

对于互质的a,m∈N，称满足下式的最小x∈N为a在模m意义下的逆元（或数论倒数）。

$$ ax\equiv1\pmod{m} $$

在代码中，由于逆元的英文为Inverse element，常常用inv(a)表示a的逆元（模数m一般定义为全局变量）

矩阵

Dylan 发布于 2017-12-08 收录于 OI

矩阵

概念

定义矩形的数组

特殊矩阵

零矩阵：所有元素均为0的矩阵

单位矩阵（E或I）：对角线元素为1，其他元素为0的矩阵（A*E=A）

方阵：列数与行数相等的矩阵

对称矩阵：转置矩阵与原矩阵相同的矩阵

在编程求解有关矩阵的题目时，可以使用下面的模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<typename T>//使用泛型以适用不同的数据类型
struct MATRIX
{
    T ary[maxn][maxn];
    T* operator[](int pos)//这样定义后可以用matrix[i][j]直接访问矩阵元素
    {
        return ary[pos];
    }
    void clear()
    {
        for(int i=0;i<=n;++i)
        {
            for(int j=0;j<=n;++j)
            {
                ary[i][j]=0;
            }
        }
    }
    MATRIX()//结构体的构造函数
    {
        memset(ary,0,sizeof(ary));
    }
    void sete()//初始化为单位矩阵
    {
        clear();
        for(int i=1;i<=n;++i)
            ary[i][i]=1;
    }
};

基本操作

初等变换

行初等变换

交换两行
用k乘i行（k!=0）
i+=j*k(k!=0)

列初等变换类似。

希尔排序模板

Dylan 发布于 2017-11-10 收录于 OI

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//希尔排序 
template<typename T>
void Swap(T& a,T& b){T t=a;a=b;b=t;}

template<typename T>
void shellSort(T* ary,int l,int r)//默认为<,r为超尾 
{
	int len=(r-l);
	for(int k=len/2;k>=1;--k)
		for(int i=l+k-1;i<=r;++i)
			for(int j=i;j-k>=l&&ary[j]<ary[j-k];j-=k)
				Swap(ary[j],ary[j-k]);
}

template<typename T>
void shellSort(T* ary,int l,int r,bool comp(const T& a,const T& b))//r为超尾 
{
	int len=(r-l);
	for(int k=len/2;k>=1;--k)
		for(int i=l+k-1;i<=r;++i)
			for(int j=i;j-k>=l&&comp(ary[j],ary[j-k]);j-=k)
				Swap(ary[j],ary[j-k]);
}

RMQ问题与ST表

Dylan 发布于 2017-11-10 收录于 OI

RMQ问题与ST表

ST表

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
ST表
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
using namespace std;
template<typename T>
T Max(const T& a,const T& b){return a>b?a:b;}
template<typename T>
void read(T& w)
{
	char r;int f=1;
	for(r=getchar();(r<48||r>57)&&r!='-';r=getchar());
	if(r=='-')r=getchar(),f=-1;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
}
const int maxn=int(1e5+3);
const int maxm=int(1e6+3);
int n,m;
int f[maxn][20];
int a[maxn];
void input()
{
	read(n),read(m);
	for(int i=1;i<=n;++i)
	{
		read(a[i]);
	}
}
void initF()
{
	for(int i=1;i<=n;++i)
	{
		f[i][0]=a[i];
	}
	for(int k=1;(1<<k)<=n;++k)
	{
		for(int i=1;i<=n;++i)
		{
			f[i][k]=f[i][k-1];
			if(i+(1<<(k-1))<=n&&f[i+(1<<(k-1))][k-1]>f[i][k])//caution! 下标可能越界
				f[i][k]=f[i+(1<<(k-1))][k-1];
		}
	}
}
int lg[maxn];
void initLG()
{
	lg[1]=0;
	lg[2]=1;
	for(int i=3;i<=n;++i)
	{
		lg[i]=lg[i/2]+1;
	}
}
int askmax(int l,int r)
{
	int len=r-l+1;
	int k=lg[len];
	return Max(f[l][k],f[r-(1<<k)+1][k]);
}
void solve()
{
	int l,r;
	for(int i=1;i<=m;++i)
	{
		read(l),read(r);
		printf("%d\n",askmax(l,r));
	}
}
int main()
{
	input();
	initLG();
	initF();
	solve();
	return 0;
} 

二维RMQ（正方形情况）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//二维RMQ-正方形
int fm[maxn][maxn][8];
int fn[maxn][maxn][8];
void initMaxMin()
{
	for(int k=0;(1<<k)<=s;++k)
	{
		for(int i=1;i+(1<<(k))-1<=n;++i) for(int j=1;j+(1<<(k))-1<=m;++j)
		{
			if(k==0)
			{
				fm[i][j][0]=fn[i][j][0]=a[i][j];
			}
			else
			{
				fm[i][j][k]=
				Max(
					Max(
						fm[i][j][k-1],
						fm[i+(1<<(k-1))][j][k-1]),
					Max(
						fm[i][j+(1<<(k-1))][k-1],
						fm[i+(1<<(k-1))][j+(1<<(k-1))][k-1])
				);
				fn[i][j][k]=
				Min(
					Min(
						fn[i][j][k-1],
						fn[i+(1<<(k-1))][j][k-1]),
					Min(
						fn[i][j+(1<<(k-1))][k-1],
						fn[i+(1<<(k-1))][j+(1<<(k-1))][k-1])
				);
			}
		}
	}
}
int qMax(int ax,int ay,int bx,int by)
{
	int k=log2(bx-ax+1);
	return Max(
		Max(
			fm[ax][ay][k],
			fm[bx-(1<<k)+1][ay][k]),
		Max(
			fm[ax][by-(1<<k)+1][k],
			fm[bx-(1<<k)+1][by-(1<<k)+1][k])
	);
}
int qMin(int ax,int ay,int bx,int by)
{
	int k=log2(bx-ax+1);
	return Min(
		Min(
			fn[ax][ay][k],
			fn[bx-(1<<k)+1][ay][k]),
		Min(
			fn[ax][by-(1<<k)+1][k],
			fn[bx-(1<<k)+1][by-(1<<k)+1][k])
	);
}

初赛1——计算机结构与原理

Dylan 发布于 2017-10-30 收录于 OI

在幕布中查看（密码：LAN）

计算机结构与原理
- 冯诺依曼架构
  - 组成
    - 存储器、运算器、控制器、输入设备、输出设备
  - 存储程序
    - 将程序与数据一起存储、处理
- 硬件
  - CPU
    - 组成
      - 运算器
      - 控制器
      - 寄存器
    - 参数
      - 字长
        一次处理数据的能力
        32位CPU
        64位CPU
      - 主频
      - MIPS
      - 指令集
        复杂指令集（CISC）
        精简指令集（RISC）
      - 高速缓存
      - 寻址单元=2^n
      - 制造工艺：xxnm
    - 发展
      - 电子管、晶体管时期
      - Intel
        第一个微处理器(有争议）
        第一款微处理器应该是美国军方研制，用于F-14雄猫战机中由6颗晶片组成的中央空气数据计算机：CADC（CenterAir Data Computer）
        第一款商用处理器
        4004
        808x
        8080
        8088
        x86
        286：16bit
        386：32bit
        486
        奔腾
        I
        II
        III
        IV
        安腾
        64bit
        赛扬
        低端
        至强
        服务器
        对处理器
        酷睿
  - 内存（主存）
    - CPU能直接寻址的存储空间
    - 分类
      - RAM
        随机存储器
        存储单元的内容可按需随意取出或存入，且存取的速度与存储单元的位置无关的存储器
        DRAM
        动态：需要不断高速刷新
        SRAM
        静态
      - ROM
      - Cache
    - 发展：SDR、DDR2~4
  - 外存
  - 总线
    - 内部总线
      - 连接CPU内部各个模块
    - 外部总线（系统总线）
      - 连接CPU、存储器和IO系统
      - 分类
        数据总线
        地址总线
        控制总线
- 软件
  - BIOS
    - 启动时加载的第一个软件
    - UEFI：统一的可扩展固件接口
  - 操作系统
    - 例： windows、Linux、Unix、FreeBSD、NetWare、OS/2、Mac OS
  - 应用软件
  - 编程
    - 语言
      - 机器语言
        不可移植
        由01组成
      - 汇编语言
        是一种用于电子计算机、微处理器、微控制器或其他可编程器件的低级语言，亦称为符号语言。在汇编语言中，用助记符（Mnemonics）代替机器指令的操作码，用地址符号（Symbol）或标号（Label）代替指令或操作数的地址。在不同的设备中，汇编语言对应着不同的机器语言指令集，通过汇编过程转换成机器指令
        难移植
        低级语言
      - 高级语言
        命令式语言：这种语言的语义基础是模拟“数据存储/数据操作”的图灵机可计算模型，十分符合现代计算机体系结构的自然实现方式。其中产生操作的主要途径是依赖语句或命令产生的副作用。现代流行的大多数语言都是这一类型，比如 Fortran、Pascal、Cobol、C、C++、Basic、Ada、Java、C# 等及各种脚本语言
        函数式语言：这种语言的语义基础是基于数学函数概念的值映射的λ算子可计算模型。适合于进行人工智能等工作的计算。典型的函数式语言如 Lisp、Haskell、ML、Scheme 、F#等。
        逻辑式语言：这种语言的语义基础是基于一组已知规则的形式逻辑系统。这种语言主要用在专家系统的实现中。最著名的逻辑式语言是 Prolog。
        面向对象语言：现代语言中的大多数都提供面向对象的支持，但有些语言是直接建立在面向对象基本模型上的，语言的语法形式的语义就是基本对象操作。主要的纯面向对象语言是 Smalltalk
        虽然各种语言属于不同的类型，但它们各自都不同程度地对其他类型的运算模式有所支持。
  - 常见文件格式
- 发展
  - 世界
    - ENIAC【美】
      - 1946
      - 宾夕法尼亚大学
    - 发展
      - 1-电子管
      - 2-晶体管
      - 3-中小规模集成电路
      - 4-（超）大规模集成电路
      - 5-光、超导、人工智能、生物
  - 中国
    - 电子管：1958-1964
      - 第一台电子数字计算机（103机）：1958-8-1
      - 第一台大型通用电子数字计算机（104机）
      - 第一台自行设计小型通用电子数字计算机（107机）：1960-4
      - 第一台自行设计的大型通用数字电子管计算机（119机）：1964
    - 晶体管：1965-1972
      - 第一台大型晶体管计算机（109乙机）：1965
    - 中小规模集成电路：1973-80s初
      - 100万次/s大型机：1973
      - 100万次/s小型机：1974
    - 超大规模
    - 银河-I（每秒上亿次）：1983
    - 银河-II（每秒10亿次）：1992
    - 银河-III（百亿次）：1997
    - 第一款通用CPU：龙芯：2001
  - 摩尔定律
    - 当价格不变时，集成电路上可容纳的晶体管数目，约每隔18个月便会增加一倍，性能也将提升一倍
  - 钟摆定论
- 周边
  - 计算机特点
    - 运算速度快
    - 运算精度高
    - 具有记忆能力
    - 具有逻辑判断能力
    - 具有自动控制能力
  - 分类
    - 巨型机
    - 大型机
    - 小型机
    - 微型机
    - 单片机
  - 应用
    - 数值计算
    - 自动控制
    - 事物处理
    - 辅助教学（CAI）
    - 辅助设计（CAD）
    - 辅助测试（CAT）
    - 信息检索
    - 出版印刷
    - 网络通信
    - 多媒体技术
汉字信息编码
- 输入码
  - 区位码
  - 音码
  - 形码
  - 音形码
- 区位码
- 国标码=区位码+20H
- 机内码=国标码+80H
- 字形码

初赛2——计算机科学家

Dylan 发布于 2017-10-30 收录于 OI

在幕布中查看（密码：LAN）

计算机科学家
- 帕斯卡【法】
  - 机械计算机：加法器
- 莱布尼茨【徳】
  - 乘法器
- 巴贝奇【英】
  - 分析机
- 阿达·洛芙莱斯【英】
  - 首个程序员
  - 女
- 图灵【英】
  - 同性恋
    - 死于自杀
    - 2013年被赦免
  - 图灵机
    - 停机问题
    - 通用图灵机
  - 二战中破译密码
  - 人工智能之父
    - 《机器能思考吗》
    - 图灵测试
  - 图灵奖
    - 计算机界的诺贝尔奖
- 香农【美】
  - 信息理论、信息熵
  - 符号逻辑和开关理论
  - 《通讯的数学原理》
- 冯·诺依曼【美籍匈牙利】
  - 原子弹
  - 博弈论
  - 计算机结构-冯诺依曼体系结构
    - 二进制
    - 程序存储
  - （死于癌症）
- <中国>
  - 慈云桂
    - 中国巨型机之父
    - 银河-I
  - 王选
    - 汉字激光照排系统之父
    - “有市场眼光的科学家”
    - 伍豪之剑
    - 科教兴国，人才强国
  - 姚期智
    - 图灵奖唯一华裔计算机科学家
- 邓尼斯•里奇 & 肯•汤姆森
  - C语言
  - 1983图灵奖
OI系列竞赛概况

初赛3——数学

Dylan 发布于 2017-10-30 收录于 OI

在幕布中查看（密码：LAN）

计算机数学
- 数制
  - 转换
    - 整数
      - ->：除K取余，逆序
      - <-：加权求和
    - 小数
      - ->：乘二取整，顺序
      - <-：加权求和
  - 计算
- 数据存储
  - 机器数
    - 真值
    - 原码
      - 最高位为符号位
    - 反码
      - 正数：=原码
      - 负数：=原码符号位不变，其余位取反
    - 补码
      - 正数：=原码
      - 负数：=反码+1
      - n位补码表示范围：[-2^(n-1),2(n-1)-1]
      - 原码+补码=模
      - 补码的补码=原码
  - 小数
    - 定点数
      - 小数点在符号位后
    - 浮点数
      - 阶码
      - 尾数
      - 规格化
  - ASCII码
  - BCD码
- 逻辑运算
  - 创立
    - 乔治·布尔【英】
  - 基本运算
    - 与∧/·
    - 或∨/+
    - 非¬
    - 公式
      - 变量与常量关系
        A+1=1
        A+0=A
        A·1=A
        A·0=0
      - 重叠律
        A+A=A
        A·A=A
      - 互补律
        A+(¬A)=1
        A·(¬A)=0
      - 交换律
        A+B=B+A
        A·B=B·A
      - 结合律
        A+(B+C)=(A+B)+C
        A·(B·C)=(A·B)·C
      - 分配律
        A·(B+C)=A·B+A·C
        A+(B·C)=(A+B)·(A+C)
      - 反演律
        ¬(A+B)=(¬A)·(¬B)
        ¬(A·B)=(¬A)+(¬B)
      - 还原律
        ¬(¬A)=A
      - 吸收律
        A·(A+B)=A
        A+(A·B)=A
  - 复合运算
    - 同或⊙
    - 异或⊕
    - 公式
      - 变量与常量关系
        A⊙0=¬A
        A⊙1=A
        A⊕0=A
        A⊕1=¬A
      - 互补律
        A⊙(¬A)=0
        A⊕(¬A)=1
      - 重叠律
        A⊙A=1
        A⊕A=0
      - 调换律
        A⊙B=C <=> A⊙C=B <=> B⊙C=A
        A⊕B=C <=> A⊕C=B <=> B⊕C=A
  - 表示方法
    - 真值表
    - 卡诺图
- 排列组合
  - 圆周排列
    - Q(n,m)=A(n,m)/m=n!/[m(n-m)!]
    - n=m时：N=(n-1)!
  - 错排
    - D(n) = (n-1) [D(n-2) + D(n-1)]
    - D(1)=0,D(2)=1
    - D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].
    - D(n)=n*D(n-1)+(-1)^n
  - 可重组合
    - 在n个不同元素中取m个可以重复的组合
    - 无限
      - =C(n+m-1,m)
      - (x+y+z)^n的项数=C(n+3-1，n)
    - 有限
      - =n!/(a1!*a2!*…*ak!)
  - 不相邻组合
    - 从A={1，2，…n}取m个不相邻的数的组合
    - =C(n-m+1,m)
  - 卡特兰数Catalan
    - 式子
      - h(1)=1
      - h(n)=h(1)*h(n-1)+h(2)*h(n-2)+…+h(n-1)*h(1)
      - h(n)=h(n-1)*(4n-2)/(n+1)
      - h(n)=C(2n,n)/(n+1)=C(2n,n)-C(2n,n-1)
    - 直接应用
      - 括号化
      - 两排站队
      - 剧院买票找零（10/5）
      - 出栈次序
      - 多边形划分三角形
      - 给定顶点组成二叉树
      - 方格行走不穿越对角线
      - 二进制有n个1的方案数
  - 第二类斯特林数
    - 将n个不同的元素分成m个集合的方案数
    - S(n+1,m)=S(n,m-1)+m*S(n,m)
    - S(n,0)=0
    - S(n,1)=1
    - S(n,n)=1
  - 抽屉原理
- 约瑟夫问题
  - N=2：
    - k=log2(N),x=2*(N-2^k)+1
  - N=n：从0开始编号f[1]=0;f[i]=(f[i-1]+m) mod i; (i>1）
- 表达式
  - 前缀表达式
  - 中缀表达式
  - 后缀表达式
  - 表达式转换
- 千禧难题
  - P，NP，NPC
    - P：所有可以在多项式时间内求解的判定问题构成P类问题。判定问题：判断是否有一种能够解决某一类问题的能行算法的研究课题。
    - NP：所有的非确定性多项式时间可解的判定问题构成NP类问题。非确定性算法：非确定性算法将问题分解成猜测和验证两个阶段。算法的猜测阶段是非确定性的，算法的验证阶段是确定性的，它验证猜测阶段给出解的正确性。
    - NPC：P=NP？ NP中的某些问题的复杂性与整个类的复杂性相关联.这些问题中任何一个如果存在多项式时间的算法,那么所有NP问题都是多项式时间可解的.这些问题被称为NP-完全问题(NPC问题)。
  - 霍奇猜想
  - 庞加莱猜想
  - 黎曼假设
  - 杨－米尔斯存在性和质量缺口
  - 纳维叶－斯托克斯方程的存在性与光滑性
  - 贝赫和斯维讷通－戴尔猜想

初赛4——网络

Dylan 发布于 2017-10-30 收录于 OI

在幕布中查看（密码：LAN）

网络
- 首个计算机网络：1969Arpanet，是Internet的前身
- 分类
  - 拓扑结构
    - 星型，环型，总线，分布，树型，网状，蜂窝
  - 规模
    - 局域网，城域网，广域网
- 协议与模型
  - OSI参考模型
    - 结构
      - 物理层：光纤、同轴电缆、双绞线、中继器和集线器
        最重要、最基础的一层，它建立在传输媒介基础上，起建立、维护和取消物理连接作用，实现设备之间的物理接口。物理层之接收和发送一串比特(bit)流，不考虑信息的意义和信息结构。
      - 数据链路层：二层交换机、网桥、网卡
        将比特信息封装成数据帧Frame，起到在物理层上建立、撤销、标识逻辑链接和链路复用以及差错校验等功能。通过使用接收系统的硬件地址或物理地址来寻址。建立相邻结点之间的数据链路，通过差错控制提供数据帧（Frame）在信道上无差错的传输，同时为其上面的网络层提供有效的服务。
        在不可靠的物理介质上提供可靠的传输。该层的作用包括：物理地址寻址、数据的成帧、流量控制、数据的检错、重发等。
      - 网络层：网关、路由器
        用于控制通信子网的操作，是通信子网与资源子网的接口。
        IP地址
      - 传输层
        为上层提供端到端（最终用户到最终用户）的透明的、可靠的数据传输服务
      - 会话层
        会话层不参与具体的传输，它提供包括访问验证和会话管理在内的建立和维护应用之间通信的机制。如服务器验证用户登录便是由会话层完成的。
      - 表示层
        表示层是为在应用过程之间传送的信息提供表示方法的服务，它关心的只是发出信息的语法与语义。表示层要完成某些特定的功能，主要有不同数据编码格式的转换，提供数据压缩、解压缩服务，对数据进行加密、解密。例如图像格式的显示，就是由位于表示层的协议来支持。
      - 应用层
        网络应用层是通信用户之间的窗口，为用户提供网络管理、文件传输、事务处理等服务。其中包含了若干个独立的、用户通用的服务协议模块。
  - TCP/IP（传输控制协议）参考模型
    - 结构：
      - 网络接口层
        主机必须使用某种协议与网络相连。
      - 网络层
        使主机可以把分组发往任何网络，并使分组独立地传向目标。
      - 传输层
        源端和目的端机器上的对等实体可以进行会话。（TCP/IP）
      - 应用层
        包含高层协议（TELNET、FTP、SMTP、DNS、NNTP、HTTP）
    - TCP
      - 可靠的数据流服务，采用“带重传的肯定确认”技术来实现传输的可靠性
      - 传输层
    - IP（网协）
      - IPv4
        地址长32位
        表示：每八位一段十进制
        分类
        A：1.0.0.0—126.0.0.0
        B：128.0.0.0—191.255.0.0
        C：192.0.0.0—223.255.255.0
        D：224.0.0.0—239.255.255.255
        E：240.0.0.0—255.255.255.254
      - IPv6
        地址长128位
        表示：每十六位一段十六进制
    - UDP
      - 面向无连接的通讯协议，UDP数据包括目的端口号和源端口号信息，由于通讯不需要连接，所以可以实现广播发送。
    - 域名
  - FTP
  - SMTP
  - POP3
- 网络安全