知识点汇总

Catalan数

公式1：\(f(n)=\sum_{i=0}^{n-1}f(i)\times f(n-1-i)\),其中\(f(0)=1\)

如何去理解这个公式？

我们可以把这个化为一个二叉树状态方案问题。

当n=1的时候显然方案数为1,即f(1)=1

当n=2的时候，有以下情况

1	0	\(f(1)\times f(0)=1\)
0	1	\(f(0)\times f(1)=1\)

所以f(2)=5

当n=3的时候，有以下情况

2	0	\(f(2)\times f(0)=5\)
1	1	\(f(1)\times f(1)=1\)
0	2	\(f(0)\times f(2)=5\)

所以f(3)=11

那么我们这样往下推，就得到了

n-1	0	\(f(n-1)\times f(0)\)
n-2	1	\(f(n-2)\times f(1)\)
n-3	2	\(f(n-3)\times f(2)\)
……	……	……
2	n-3	\(f(2)\times f(n-3)\)
1	n-2	\(f(1)\times f(n-2)\)
0	n-1	\(f(0)\times f(n-1)\)

故得到上述式子。

公式2：\(f(n)=\frac{1}{n+1}C^n_{2n}\)

应用：

n个元素依次入栈，问出栈的方案数
由n个相同的点组成的二叉树，问不同的状态数数
n边形格子从左下角走到右上角不跨过对角线
给一个式子添加括号，问添加的方案数
n+2个点的凸多边形，分成三角形的方案数
圆上选择2n个点,将这些点成对连接起来，使得所得到的n条线段不相交的方法数
表示集合{1, …,n}的不交叉划分的个数(还可能加上一个条件：其中每个段落的长度为2)
用n个长方形填充一个高度为nn的阶梯状图形的方法个数。

错排公式

公式1：D~n~=(n-1)(D~n-1~+D~n-2~)

证明：

考虑一号位置的那个数，不妨设为k,k>1

分成两种情况。

k号位置的那个数是1，于是剩下n-2个数也是一个错位排列，有D~n-2~中情况。
k号位置的那个数不是1，那么不妨设1原来的位置应该在k，这样就是除k以外的n-1个数的一个错误排列，有D~n-1~种情况

故公式为D~n~=(n-1)(D~n-1~+D~n-2~)

公示2：\(D_n=n!(1-\frac 1{1!}+\frac1 {2!}-\frac1{3!}+\frac1{4!}\cdots+(-1)^{n}\times \frac1{n!})\)

由于常用的是第一个公示，第二个就不证明了……(但是其思想还是要记一记的，利用的是容斥思想)

平面分割问题相关：

n条直线最多能分成的部分数目：\(\frac{n\times(n-1)}2+1\)

证明：

在画第n条直线的时候，保证经过之前画过的n-1条直线，这样就能保证多出来n-1个部分。

推广：

n个平面最多将空间分成的部分：\(g(n)=g(n-1)+f(n-1)=\frac{n^3+5n+6}{6}\)

n条封闭曲线最多将平面分成的部分：\(f(n)=f(n-1)+2(n-1)=n^{2}-n+2\)

n条折线最多将平面分成的部分：\(f(n)=f(n-1)+4(n-1)+2-1=2n^2-n+1\)

n个椭圆最多将平面分成的部分(椭圆两两有交点)：\(f(n) = f(n - 1) + 2(n - 1) = n^2 - n + 2\)(如图所示)

n个三角形最多将平面分成的部分：\(f(n) = f(n - 1) + 6(n - 1) = 3\times n^2 - 3\times n + 2\)

数据结构相关：

顺序存储于非顺序存储：

顺序存储可以形象的理解为内存在一起

队列，栈，…

链表，…

线性数据结构与非线性数据结构：

线性数据结构可以理解为数据存在一串

队列，栈、链表，…

树形结构，…

计算机相关：

计算机发展代：

第一代	1946——1958	电子管
第二代	1959——1964	晶体管
第三代	1965——1970	集成电路
第四代	1971——至今	大规模、超大规模集成电路

EDVAC与ENIAC：

==第一台计算机ENIAC==：在美国宾夕法尼亚大学诞生的第二台电子计算机(第一台是ABC（阿塔纳索夫-贝瑞计算机）)，第一台通用计算机——ENIAC。它是十进制存储的计算机。(注：冯·诺依曼结构出现后才有二进制存储的思想)

==第一台冯·诺伊曼结构的计算机EDVAC==:离散变量自动电子计算机,ENIAC的后代==,是第一台冯·诺伊曼结构的计算机。

约翰·冯·诺依曼理论：

理论要点：

计算机硬件设备由存储器、运算器、控制器、输入和输出设备5部分组成。

存储程序思想——把计算过程描述为由许多命令按一定顺序组成的程序，然后把程序和数据一起输入计算机，计算机对已存入的程序和数据处理后，输出结果。

注意：计算机主机不包含输入和输出设备，其他3部分都有。

计算机分类：

运算速度	每秒亿次以上	每秒几千万次左右	每秒几百万次左右	\	\
特点+用途	运算速度快，存储量大，结构复杂，价格昂贵。主要于尖端科学研究领域。(如我国的银河)	通常用于国家及科研机构以及重点理、工科类学校	通常用在一般的科研与设计机构以及普通高校等。	目前应用最广泛的机型。如通常所说的386、486、586以及奔腾系列等型机都属于微型机	主要用于图形、图像处理和计算机辅助。它实际上是一台性能更高的微型机。

计算机应用：

科学计算
信息处理
自动控制
计算机辅助奇数
人工智能
网络应用

计算机系统的基本结构：

CPU

CPU由运算器，控制器和一些寄存器组成。

运算器顾名思义是用来做运算的。控制器是计算机的只会系统。

CPUT的主要性能指标是主频和字长。

(Intel最早发明的是微处理器，而不是CPU)

存储器

存储器的主要功能是用来保存各类程序的数据信息。它可以分为主存储器与副主存储器两个部分。

主存储器(也称为内存储器)，属于主机的一部分。用于存放系统正在执行的数据和程序，属于临时存储器。
辅助存储器(也成外存储器)，属于外部设备。用于存放暂时不用的数据和程序，属于永久存储器。

两个存储器与CPU的关系：

graph LR
CPU-->内存储器
内存储器-->CPU
外存储器-->内存储器
内存储器-->外存储器

内存储器

内存储器也称为主存，它与CPU一起构成了计算机的主机部分，它也可以直接被CPU访问。内存中的每个存储单位可以放1个8位2进制数(1位16进制数)，即一个Byte(字节)。

内存出其通常可以分为随机存储器RAM，只读存储器ROM和高速缓冲存储器Cache。

RAM是一种能读能写的存储器，断电后数据全部丢失。
ROM是一种只能读入，其存储内容是在制作改村吃起的时候被存入的。断电后数据不会丢失。
Cache是指在CPU与内存之间设置的一级或者两级高速小容量存储器。

外存储器。

外存储器容量一般较大，而且大部分可以移动，便于在不同计算机之间进行信息交流。

在微型机内，常用的外存有软盘、硬盘、闪存和光盘4种。

存取速度：寄存器>高速缓存>内存>磁盘

总线结构：

按照总线上存储信息的不同，总线可以分为数据总线(DB)、地址总线(AB)和控制总线(CB)三种

数据总线：传递数据信息。
地址总线：传递地址信息。
控制总线：传递信号，协调各部件之间的操作。

主要性能指标：

字长：影响到精度、功能和速度。
运算速度：顾名思义影响速度。
主频：指计算机CPU的时钟频率。
内存容量：顾名思义内存大小。

软件系统：

系统软件

操作系统：如果Windows,Linux,UNIX,MS-DOS
语言处理程序：分为三类——机器余元、汇编语言和高级语言
系统管理和服务软件：包括了数据库管理系统，实用工具服务软件等。

应用软件

通常的应用软件有以下几个：（1）字处理软件；（2）电子制表软件；（3）计算机辅助设计软件；（4）图形软件；（5）教育软件；（6）电子游戏软件。

计算机指令

指令是一串儿进制代码，它规定你够了由计算机执行的程序的一步操作。

指令系统是一个计算机所能识别并可执行的全部指令的集合。例如，80386的指令系统共有123种指令，可分为9类指令操作：数据传递、算数运算、逻辑运算、串操作、未操作、程序控制、高级语言指令、保护模式、处理器控制指令。

程序是计算机为了执行某种操作任务而将一条条指令按照一定的顺序排列起来的指令集。

计算机语言：

机器语言

==计算机最早的语言处理程序。==它是计算机能直接是别的语言，而且速度快。因为用二进制代码来编写计算机程序，因此也被称为“二进制语言”

缺点：书写困难、记忆复杂，一般很难掌握。

汇编语言

由于机器语言的缺陷，人们开始借助符号写程序，代替掉机器指令，产生的语言叫汇编语言。但是汇编语言编写的源程序不能直接被计算机直接识别，必须用某种特殊的软件将用汇编语言写的源程序翻译和连接成能被计算机直接识别的二进制代码。

示意图如下。

graph LR
汇编源程序--翻译程序-->目标程序
目标程序--连接程序-->可执行程序

优点：

1、因为用汇编语言设计的程序最终被转换成机器指令，故能够保持机器语言的一致性，直接、简捷，并能像机器指令一样访问、控制计算机的各种硬件设备，如磁盘、存储器、CPU、I/O端口等。使用汇编语言，可以访问所有能够被访问的软、硬件资源。

2、目标代码简短，占用内存少，执行速度快，是高效的程序设计语言，经常与高级语言配合使用，以改善程序的执行速度和效率，弥补高级语言在硬件控制方面的不足，应用十分广泛。

缺点：

1、汇编语言是面向机器的，处于整个计算机语言层次结构的底层，故被视为一种低级

语言，通常是为特定的计算机或系列计算机专门设计的。不同的处理器有不同的汇编语言语法和编译器，编译的程序无法在不同的处理器上执行，缺乏可移植性；

2、难于从汇编语言代码上理解程序设计意图，可维护性差，即使是完成简单的工作也需要大量的汇编语言代码，很容易产生bug，难于调试；

3、使用汇编语言必须对某种处理器非常了解，而且只能针对特定的体系结构和处理器进行优化，开发效率很低，周期长且单调。

高级语言。

高级语言的翻译程序方式有两种：编译与解释。(这也就将高级语言分成了编译性语言与解释性语言)

Pascal、Fortran、Cobol、等高级语言为编译性高级语言

Basic、PHP、Python等高级语言被称为解释性高级语言

而Pascal、C、C++语言都是能书写编译程序的高级程序设计语言。

编译高级语言缺点：每次修改原程序后，必须重新编译。

面向对象语言

面向对象语言借鉴了20世纪50年代的人工智能语言LISP，引入了动态绑定的概念和交互式开发环境的思想；始于20世纪60年代的离散时间模拟语言Simula67，引入了类的耀岭河集成，成型与20世纪70年代的Smalltalk

面向对象语言的发展有两个方向：

纯面向对象语言，如SmallTalk、EIFFEL等；
混合型面向对象语言，即在过程是语言其他语言中加入类、继承等成分，如C++、Objective-C等

(一般前面有Objective的都是面向对象语言)

信息编码：

有关二进制、八进制、十进制、十六进制

表示各个进制所用到的结尾：

二进制（B）(Binary)

八进制（O）(Octonary)

十进制（D）(Decimal)

十六进制（H）(hexadecimal)

scanf：

二进制没有

八进制是%o

十进制%d(常用)
十六进制是%x或者是%X(与上方的H不同，别搞混了)

其中八进制读入和十六进制读入++必须是正数++。

基本概念

编码

计算机要处理的数据除了数值数据外，还有各类符号、图形、图像和声音等非数值数据。而计算机智能识别两个数字。要使计算机能处理这些信息，首先必须将各类信息转换成“0”和“1”，这一过程叫做编码

数据

能被计算机接受和处理的符号的集合都被称为数据。

比特

比特(Bit：——二进制数位)是指1位二进制的数码（即0或1）。比特是计算机中表示信息的数据编码中的最小单位。（1Byte=8Bit）

字节

字节(Byte)表示被处理的一组连续的二进制数字。通常由8为二进制数字表示一个字节，即一个字节由8个比特组成。

字节是存储器系统的最小存放单位。

字符表示

字符是人与计算机交互过程中不可缺少的重要信息。要是计算机能处理、存储字符信息，首先必须有二进制的“0”和“1”代码对字符进行编码。

ASCII码

ASCII码是美国国家标准委员会指定的一种包括数字、字母、通用符号和控制符号在内的字符编码集，全称为美国国家信息交换标准代码。ASCII码为一种7位的二进制码，是目前计算机中，特别是微型计算机中使用最为普遍的字符编码集。

内码和外码

内码：输入到计算及内部的文本对应的ASCII码
外码：在计算及内部的ASCII码对应的文本。

通常一个西文字母占一个字节(半角)，一个中文字符占两个字节。

汉字信息编码

汉字交换码

汉字交换码是指不同的具有汉字处理功能的计算机系统之间在交换汉字信息时所使用的代码标准。自国家标准GB2312-80发布以来，我国一直沿用该标准所规定的国标准码做为统一的汉字信息交换码（GB5007-85五星字符代码）

汉字交换码中包含了6763个汉字，其中按使用频率分为一级汉字(3755个)以及二级汉字(3008个),一级汉字按照拼音排序，二级汉字按照部首排序。该标准还包含标点符号、数种西文字母、图形、数码等符号682个。

区位码的区码和位码均采用01~94的十进制，国标码采用十六进制的21H~73H(H表示16进制数)。两者的关系：区位码的区码和位码均加上32(十进制)就变成了国标码

字形存储码

字形存储吗是指提供计算机输出汉字(显示或打印)采用的二进制信息，也称为字模。通常采用的是数字化点阵字模。

一般的点阵规模有16*16，24*24等，每一个点用一个bit存储。在相同点阵中，不管其笔画简繁，每个汉字所占的字节数相同(因为都是这个点阵，没多没少，不过是存储的二进制状态发生了变化。)

为了节省存储空间，欧变采用字形数据压缩计数。所谓矢量汉字，是指用矢量的方法将汉字点阵字模进行压缩后得到的汉字字形的数字化信息。

计算机病毒

安全管理电脑的方法：

加强对关于计算机病毒及其危害的教育。
定期进行检查与测试
谨慎使用公共软件，防止计算机病毒的传播与扩散
使用口令的时候，尽可能选择随机字符作为口令，让口令本身无意义，不要用名字生日等作为口令。
严禁将其他部门的程序带入本系统。
不允许随便将本系统与外界系统接通。
不允许将各种游戏软件装入计算机系统
使用杀毒软件（但是不要被病毒360骗了！！！！！！！！！）

计算机病毒的特性：

隐蔽性（你看不出来）
潜伏性（依附于其他媒体的“再生”能力）
传播性（不断进行病毒体的再生与扩散）
激发性（在一定条件刺激下，病毒程序迅速活跃起来）
破坏性和危害性（一旦满足条件要求被激活并发起攻击，就会迅速扩展，使整个计算机系统无法正常运行。）

原码、补码、反码、尾数、阶码

机器数与真值

在计算机中表示数值的数字符号只有0或者1两个数码，我们规定最高位为符号位，并用0表示正数，1表示负数。为了简化机器的运算操作，人们采用了原码，补码和反码及移码等编码方式进行编码。为区别起见，我们将数在机器中的这些编码表示称为机器数，而将原来一般书写的数字称为机器数的真值。

原码、补码、反码

原码：直接在真值前加符号即可。

反码：在原数字前加符号位，如果为正数就不用动，如果是负数就要把所有的位取反。

补码：在原数字前加符号位，如果为正数就不用动，如果是负数就为反码的数字最后一位+1。

从以上定义可知：一个正数的三种码表示形式相同，符号位为0，而数值都是真值。而一个负数的原码、反码、补码符号位都为1，数值位原码是真值本身，反码是各位取反，补码是各位取反+1。真值0的原码和反码表示都是不唯一的，而补码是唯一的
\([+0]_{\text{原}}=000\dots0\ ,\ [-0]_{\text{原}}=100\dots0\ \\\)

\([+0]_{\text{反}}=000\dots1\ ,\ [-0]_{\text{反}}=111\dots1\ \\\)

\([+0]_{\text{补}}=[-0]_{\text{补}}=000\dots0\ \\\)

(因为补码的-0为111…1，+1后就变回000…0了)

注：不同编码表示的证书范围是这样的(以n为二进制位为例)

\(\text{原码}：0\sim2^n-1(\text{无符号}),-2^{n-1}-1\sim2^{n-1}-1(\text{有符号})\\\)

\(\text{反码}：-2^{n-1}-1\sim 2^{n-1}-1(\text{不存在无符号情况})\\\)

\(\text{补码}：-2^{n-1}\sim 2^{n-1}-1(\text{不存在无符号情况})\)

很明显能看出补码的范围最大。

数的定点表示与浮点表示。

在计算机中，小守护点一般有两种表示方法，一种是小数点固定在某一位置的定点表示法；另一种是小数点的位置可任意移动的浮点表示法。相应于这两种表示的计算机分别称为定点计算机和浮点计算机。

定点表示法

及其中的所有小数的小数点位置是固定不变的，因而小数点就不必使用记号表示出来。实际上，小数点可固定在任意一个位置上。

浮点表示法

在数的定点表示法中，由于数的表示范围较窄，常常不能按组各种数值的需要。为了扩大数的表示范围，方便用户使用，有些计算及使用浮点数表示法。

计算机多数情况下采用浮点数表示数值。他其实类似于科学技术法，是以下形式的。

\(A=2^B\times C\)

其中，B是A的阶码，是有符号的正数；C是A的尾数，会死熟知的有效数字部分，一般规定去二进制定点纯小数形式。

如：\(1011101\ B=2^{+7}\times 0.1011101\ ,\ 101.1101=2^{+3}\times 0.1011101\ ,\ 0.01011101 B=2^{-1}\times 0.1011101\)

也就是说我们要保证整数尾数C的整数部分为0，然后后面跟上小数。

计算机网络：

网络的定义

所谓计算机网络，其实就是利用线路与设备，把不同地理位置上的多台计算机连接起来。

计算机网络是现代通信技术和计算机技术相结合的产物

网络中的计算机与计算机之间的通信依靠协议进行。协议是计算机收、法数据的规则。

==TCP/IP==：用于网络的一组通信协议。包括扩IP和TCP两个部分。

网络的发展

计算机网络的发展过程大概可以分为三个阶段：

远程终端联机阶段：主机——终端

计算机网络阶段：

计算机——计算机
Internet阶段：Internet

网络的主要功能

资源共享；
信息传输；
分布处理；
综合信息服务。

网络的分类：

局域网(Local Area Netword)

一般局限在1km范围内，局域网内传输效率较高，误码率第，结构简单，容易实现，具体标准是美国电气工程师协会（IEEE）制定的IEEE802系列标准

城域网（Metropolitan Area Network）

范围为几千米到几十千米以内。

广域网（Wide Area Network）

范围在几十千米到几千千米以上。

注意：MAN和WAN一般是由多个LAN构成的。

按照网络的拓扑结构进行分类：星形(菊花图)，总线形，环形，树形，网状形。

优点	通信协议简单，对外围站点要求不高，单个站点故障不会影响全网。	结构简单，可靠性高；布线容易，连线总长度小于星形结构	传输速度高，传输距离远；各节点的地位和作用相同；各节点传输信息的时间固定；容易进行分布式控制
缺点	电路利用率低，连线费用大，网络性能依赖中央节点，每个站点需要一个专用链路	总线任务重，易产生瓶颈问题；总线本身的故障对系统是毁灭性的	站点的故障会形成整个网络的崩溃

网络拓扑结构是指计算机网络节点和通信链路所组成的几何形状。

Internet网是当今世界上规模最大、用户最多、影响最广泛的计算机互联网。Internet网上联有大大小小成千上万个不同的拓扑结构的局域网、城域网和广域网。因此，Internet网本身的拓扑只是一个虚拟的拓扑结构，无固定形式。

按采用的交换技术进行分类：电路交换、报文交换、分组交换

网络的体系结构

国际标准化组织(ISO)提出的开放式系统（OSI）互联参考模型。它将数据从一个站点到达另一个站点的工作按层分割成七个不同的任务。

但是并不是长成下图这个样子！

graph LR
计算机A应用层-->计算机B应用层
计算机B应用层-->计算机A应用层
计算机A表示层-->计算机B表示层
计算机B表示层-->计算机A表示层
计算机A会话层-->计算机B会话层
计算机B会话层-->计算机A会话层
计算机A传输层-->计算机B传输层
计算机B传输层-->计算机A传输层
计算机A网络层-->计算机B网络层
计算机B网络层-->计算机A网络层
计算机A链路层-->计算机B链路层
计算机B链路层-->计算机A链路层
计算机A物理层-->计算机B物理层
计算机B物理层-->计算机A物理层

应该是每一层向下传递，然后传到互联物理传输媒体，然后传到另一台机子。

应该是这样的

graph TB
计算机A应用层-->计算机A表示层
计算机A表示层-->计算机A会话层
计算机A会话层-->计算机A传输层
计算机A传输层-->计算机A网络层
计算机A网络层-->计算机A链路层
计算机A链路层-->计算机A物理层
计算机A物理层-->互联物理传输媒体
互联物理传输媒体-->计算机B物理层
计算机B物理层-->计算机B链路层
计算机B链路层-->计算机B网络层
计算机B网络层-->计算机B传输层
计算机B传输层-->计算机B会话层
计算机B会话层-->计算机B表示层
计算机B表示层-->计算机B应用层
计算机A表示层-->计算机A应用层
计算机A会话层-->计算机A表示层
计算机A传输层-->计算机A会话层
计算机A网络层-->计算机A传输层
计算机A链路层-->计算机A网络层
计算机A物理层-->计算机A链路层
互联物理传输媒体-->计算机A物理层
计算机B物理层-->互联物理传输媒体
计算机B链路层-->计算机B物理层
计算机B网络层-->计算机B链路层
计算机B传输层-->计算机B网络层
计算机B会话层-->计算机B传输层
计算机B表示层-->计算机B会话层
计算机B应用层-->计算机B表示层

举个最简单的例子，如果你是按照图1进行传输的话，

因此，应该是一级一级向下传输的。

IP地址

所谓Ip地址，是用于表示Internet网络上节点的32位地址(IPv4是这样的，当然IPv6会不同，他是128位的，分8组，每组16位)。对于Internet网络上的每个节点，都必须指派一个唯一的地址，它由网络ID和唯一的主机ID组成。改地址通常用由句点分割的八位字节的是十进制数表示(如192.168.40.88)

IP分为A、B、C、D、E五大类，其中A、B、C为常用类，都由网络ID和主机ID两个部分组成。

网络ID也称为网络地址，标识大规模TCP/IP网际网络(由网络组成的网络)内的单个网段，连接到并共享访问同一网络的所有系统在其完整的IP地址内都有一个公共的网络ID，这个ID也用于唯一的识别大规模的网际网络内部的每个网络

主机ID也称为主机地址，识别每个网络内部的TCP/IP节点（工作站、服务器、路由器或其他TCP/IP设备），每个设备的主机ID唯一的识别所在网络内的单个系统。

A类地址：1.0.0.1~126.255.255.254，主机ID占3Byte(3位数，2个小数点)

B类地址：128.1.0.1~191.255.255.254，主机ID占2Byte(2为数，1个小数点)

C类地址：192.0.0.1~223.255.255.254，主机ID占1Byte(1位数，0个小数点)

注：

1.尽管IP地址的主机号的每个域的取值范围是0~255，但主机ID所有域都为0或者255，例如网络ID为10，就不能把10.0.0.0或者10.255.255.255分配给主机；如果网络ID为192.114.31，就不能吧192.114.31.0和192.114.31.255分配给主机。

2.专用网络寻址选项：如果某个链接仅存在于群集结点之间，并且不支持其他网络的客户机，可以为它配置私有的IP地址，而不是企业的正式IP网络地址。经过Internet编号指派机构(IANA)协商同意，几个IP网络被保留下来以用作企业内部私有。这些保留的号码是：

A类：10.0.0.0~10.255.255.255
B类：172.16.0.0~172.31.255.255
C类：192.168.0.0~192.168.255.255

一些特殊点

A: 127.0.0.0~127.255.255.255 被保留

B: 191.255.255.255是广播地址

IP地址的表示方法：采用点分十进制记法（Dotted Decimal Notation），即将32bit的IP地址中的每8位用。等效的十进制表示，并每8位之间加上一个点，即4段热进制为组成，“.”隔开，每组数字的取值范围只能是0~255

因特网

TCP/IP概述

应用层	Telnet、FTP和e-mail等
传输层	TCP和UDP
网络层	IP、ICMP和IGMP
网络接口层	设备驱动程序及接口卡

因特网概述

因特网是一个建立在网络互联基础上的最大的、开放的全球性网络。因特网拥有数千万台计算机和上一个用户，是全球信息资源的超大型集合体。

因特网起源于20世纪60年代中期，由美国国防部高级研究计划局（ARPA）资助的ARPANET，伺候提出的TCP/IP协议为因特网的发展奠定了基础。

我国正式接入因特网是在1994年4月。

我国的Internet发展情况为20世纪80十年代末、90年代初才起步。

因特网提供的服务

Internet的服务有电子邮件、远程登录、文件传输、信息服务等……

万维网（WWW）

全球信息网，又称万维网（World Wide Web），是一个全球规模的信息服务系统，有遍布于全世界的数以万计的Web站点组成。

电子邮件（E-mail）

格式：邮箱名@邮箱所在主机的域名

文件传输协议(FTP)

用于在计算机建传输文件，如下载软件等。

FTP几乎可以传输所有类型的文件，包括文本、二进制可执行、声音、图像、数据压缩文件等。

远程登录（Telnet）

指通过Internet与其他主机连接

Telnet是远程登录服务的一个协议，该协议定义了远程用户与服务器交互的方式。允许用户在一台联网的计算机登录到一个远程分时系统时，想使用自己的计算机一样使用该系统。

浏览网页的相关概念

WWW与HTML

WWW是因特网上集文本、声音、图像、视频等多媒体信息与一身的全球信息资源网络，是因特网上的重要组成部分。

WWW的网页文件是用超文本标记语言HTML(Hyper Text Markup Language)编写的,并在超文本传输协议(Hyper Text Transmission Protocol,HTTP)支持下运行的。

URL其实就是因特网上的资源地址。其格式：协议名：//IP地址或者域名

浏览器

WWW浏览器是一个客户端的程序，其主要功能是使用户获取因特网上的各种资源，常用的浏览器有Microsoft的Internet Explorer(IE)

电子邮箱的相关概念

电子邮箱概述

因特网上是用最为广泛的一种服务。

电子邮箱使用的协议

有简单邮箱传输协议(Simple Message Transfer Protocol,SMTP)、电子邮箱扩展协议(Multipurpose Internet Mail Extensions,MIME)和POP(Post Office Protocol)协议。(POP又被称为POP3)

(SMTP：发送，POP：接收，IMAP：发送+接收(双向))

P/NP/NPC/HP-Hard关系：

摘自dsjkafdsaf大佬

P类问题：存在多项式时间算法的问题。

NP类问题：能在多项式时间内验证得出一个正确解的问题。

P类问题是NP问题的子集，因为存在多项式时间解法的问题，总能在多项式时间内验证他。

NPC类问题（Nondeterminism Polynomial complete）：存在这样一个NP问题，所有的NP问题都可以约化成它。

换句话说，只要解决了这个问题，那么所有的NP问题都解决了。其定义要满足2个条件：

首先，它得是一个NP问题；
然后，所有的NP问题都可以约化到它。

要证明NPC问题的思路就是：

先证明它至少是一个NP问题，再证明其中一个已知的NPC问题能约化到它。

NP-Hard问题是这样一种问题，它满足NPC问题定义的第二条但不一定要满足第一条（就是说，NP-Hard问题要比 NPC问题的范围广，NP-Hard问题没有限定属于NP），即所有的NP问题都能约化到它，但是他不一定是一个NP问题。

NP-Hard问题同样难以找到多项式的算法，但它不列入我们的研究范围，因为它不一定是NP问题。即使NPC问题发现了多项式级的算法，NP-Hard问题有可能仍然无法得到多项式级的算法。事实上，由于NP-Hard放宽了限定条件，它将有可能比所有的NPC问题的时间复杂度更高从而更难以解决。

BIOS

BIOS是英文"Basic Input Output System"的缩略词，直译过来后中文名称就是"基本输入输出系统"。在IBM PC兼容系统上，是一种业界标准的固件接口。BIOS这个字眼是在1975年第一次由CP/M操作系统中出现。 BIOS是个人电脑启动时加载的第一个软件。

其实，它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序，它可从CMOS中读写系统设置的具体信息。其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。此外，BIOS还向作业系统提供一些系统参数。系统硬件的变化是由BIOS隐藏，程序使用BIOS功能而不是直接控制硬件。现代作业系统会忽略BIOS提供的抽象层并直接控制硬件组件。

Huffman编码：

出现频率越高的字符，要编码越短。因此我们有能看出它的贪心策略。

特别的，一种编码不能是另一种编码的前缀。

服务器操作系统：

服务器操作系统是服务器上常见的操作系统，常见的有CentOS、Ubuntu、Windows Server、macOS Server

注意苹果的macOS Server的大小写！(普通的Mac是M大写，而这里的m小写)

一些比较常见的操作系统：

DOS、Windows、UNIX、Linux、Mac OS……

还有一些：Chrome OS

自己在网上搜到的：

Windows,Linux,Dos,Unix这些是常用的，其他不常用的太多了
早期操作系统（专利保护）
TRS-DOS，ROM OS's
TI99-4
Commodore PET，64，和 VIC-20，
第一套IBM-PC
苹果电脑
Sinclair Micro和QnX等
非Unix商业操作系统
CPM操作系统
MP/M-80
UCSD P-system
Mini-FLEX
SSB-DOS
CP/M-86
DR-DOS
FreeDOS
MS-DOS
PC-DOS
Mach 由卡纳尼基梅隆大学研究
L4微内核 第二代微内核
CHORUS
Choices
Multics
OS-9
NSJ
Netware:一种网络服务器操作系统
Unix及类似系统
A/UX(Apple UNIX)
Unix
微软Xenix
ChorusOS
Cromix
UNIflex
OS-9
IBM的AIX
BSD
FreeBSD
NetBSD
OpenBSD
DragonFly BSD
PC-BSD
Digital UNIX，即之后康柏Tru64
DNIX
HP的HP-UX
GNU/Hurd
SGI的IRIX
Inferno
Linux（或称GNU/Linux）
Mac OS X
MenuetOS
Minix
OSF/1
Plan9
SCO的SCO UNIX
Sun的SunOS，即之后的Solaris
System V
Ultrix
UniCOS
麒麟操作系统(Kylin),由国防科技大学、中软公司、联想公司、浪潮公司和民族恒星公司五家单位合作研制的服务器操作系统
OS/390
z/OS
Syllable
其他
Acorn
Arthur
ARX
RISC OS
RISCiX
Amiga
AmigaOS
Atari ST
TOS
MultiTOS
MiNT
苹果电脑（Apple/Macintosh）
Apple DOS
ProDOS
Mac OS
Mac OS X
pink OS
BeOS
A/UX
Be
BeOS
BeIA
Digital/康柏（Compaq）
AIS
OS-8
RSTS/E
RSX-11
RT-11
TOPS-10
TOPS-20
VMS（后更名为OpenVMS）
IBM
OS/2
AIX
OS/400
OS/390
VM/CMS
DOS/VSE
VSE/SP
VSE/ESA
OS/360
MFT
MVT
SVS
MVS
TPF
ALCS
z/OS
PC-DOS
pink OS
微软（Microsoft）
MS-DOS
Xenix
Microsoft Bob
基于MS-DOS操作系统的Windows
Windows 1.0
Windows 2.0
Windows 3.1
Windows 95
Windows 98
Windows ME
Windows NT
Windows NT 3.5
Windows NT 4
Windows 2000
Windows XP
Windows XP Media Center Edition
Windows XP Home Edition
Windows XP Professional
Windows XP Professional x64 Edition
Windows Server 2003
Windows Server 2003 64-bit Edition
Windows Vista
Windows Vista Home Basic
Windows Vista Home Premium
Windows Vista Business
Windows Vista Ultimate
Windows Vista Enterprise
Windows Vista Starter
Novell
NetWare
Unixware
SUSE Linux
NeXT
NEXTSTEP（即之后的Mac OS X）
Plan 9
Inferno
Prime Computer
Primos
西门子
BS2000 - 用于西门子公司的大型主机。
SINIX（也称Reliant UNIX） - 用于西门子公司的UNIX电脑系统。
个人电子助理（PDA）操作系统
Palm OS
Pocket PC
EPOC
Microsoft Windows CE
Linux

主定理

假设有递推关系式\(T(n)=aT(\frac n b)+f(n)\)，其中 \(n\)为问题规模，\(a\)为递推的子问题数量，\(\frac n b\)为每个子问题的规模（假设每个子问题的规模基本一样），\(f(n)\)为递推以外进行的计算工作。

\(a≥1\)，\(b>1\)为常数，\(f(n)\)为函数，\(T(n)\) 为非负整数。则有以下结果（分类讨论）：

（1）若\(f(n)=O(n^{\log_ba-\epsilon})\)那么\(T(n)=\Theta(n^{\log_ba})\)

（2）若\(f(n)=\Theta(n^{\log_ba})\)那么\(T(n)=\Theta(n^{\log_ba}logn)\)

（3）若\(f(n)=\Omega(n^{\log_ba+\epsilon})\)且对于某个常数\(c<1\)和所有充分大的\(n\)有\(af(\frac n b)\le cf(n)\)，那么\(T(n)=\Theta(f(n))\)

要牢牢记住！很有用！

均摊复杂度：

一个操作慢，但是其他操作快，合在一起的总复杂度/总操作时间，就是它的均摊复杂度。

运算符号优先级：

C++运算符优先级表，从上到下，从左到右，优先级依次减弱。

1	::	范围解析	自左向右
2	++	--	后缀自增/后缀自减
	()	括号	~
	[]	数组下标	~
	.	成员选择（对象）	~
	?>	成员选择（指针）	~
3	++ --	前缀自增/前缀自减	自右向左
	+ ?	加/减	~
	! ~	逻辑非/按位取反	~
	(type)	强制类型转换	~
	*	取指针指向的值	~
	&	某某的地址	~
	sizeof	某某的大小	~
	new,new[]	动态内存分配/动态数组内存分配	~
	delete,delete[]	动态内存释放/动态数组内存释放	~
4	.* ->*	成员对象选择/成员指针选择	自左向右
5	* / %	乘法/除法/取余	~
6	+ ?	加号/减号	~
7	<< >>	位左移/位右移	~
8	< <=	小于/小于等于	~
	> >=	大于/大于等于	~
9	== !=	等于/不等于	~
10	&	按位与	~
11	^	按位异或	~
12	\|	按位或	~
13	&&	与运算	~
14	\|\|	或运算	~
15	?:	三目运算符	自右向左
16	=	赋值	~
	+= ?=	相加后赋值/相减后赋值	~
	*= /= %=	相乘后赋值/相除后赋值/取余后赋值	~
	<<= >>=	位左移赋值/位右移赋值	~
	&= ^= \|=	位与运算后赋值/位异或运算后赋值/位或运算后赋值	~
17	throw	抛出异常	~
18	,	逗号	自左向右

图灵奖

图灵奖是于1966年设立的

唯一一名华裔图灵奖得主：姚期智(姚班就是这么来的)

排序相关：

插入排序	\(O(n^2)\)	\(O(n)\)（好）	稳定
冒泡排序	\(O(n^2)\)	\(O(n)\)（好）,\(O(n^3)\)（坏）	稳定	交换次数为逆序对个数
选择排序	\(O(n^2)\)	/	不稳定
计数排序	\(O(n+m)\)	/	稳定	n为元素个数，m为元素范围
堆排序	\(O(nlogn)\)	/	不稳定	在元素全部相同的情况下，复杂度为\(O(n)\)
快速排序	\(O(nlogn)\)	\(O(n^2)\)(坏)	不稳定
希尔排序	\(O(n^{1.5})\)	\(O(nlogn)\)（下限）	不稳定	复杂度受争议
基数排序	\(O(n*m)\)	/	稳定	m为最大数位数/所排序数为正数
归并排序	\(O(nlogn)\)	/	稳定	可用于求逆序对

总线：

系统总线

分类：数据总线、地址总线、控制总线

理解：就像邮递员收发邮件。数据总线就像改邮递员一次最多收发几公斤邮件。比如8位的单片机数据总线就像邮递员一次可以最多收8公斤邮件。16位的单片机数据总线就像邮递员一次可以最多收16公斤邮件。(也就是说是一个范围限制)

DSP一次可以传输32位，就像邮递员一次可以最多收32公斤邮件。

地址就像邮递员负责的派送范围，（也就是寻址空间）比较某人负责哪几个小区，这几个小区的人有需求可以联系到他派送邮件。超出这个范围他不响应，也就是不负责。

控制总线有点类似于给这个邮递员打电话，下命令。是收快递还是发快递，联系方式，地址等信息。

设地址总线位数为\(n\)位，则寻址空间大小为\(2^n\) Byte

打印技术：

针孔打印技术：

打下去一个孔就是1，没打下去就是0。

喷墨打印技术：

喷墨打印技术是将彩色液体油墨经喷嘴变成细小微粒喷到印纸上，有的喷墨打印机有三个或四个打印喷头，以便打印黄、品红、青、黑四色；有的是共用一个喷头，分四色喷印。

激光打印技术(现在常用)：

激光打印机接收打印命令，处理传到激光器，激光射到感光鼓，此时感光鼓通电，从磁棒上面吸取碳粉颗粒，激光照射的行成文档或图案，其余刮入废粉仓。

热升华照片打印：

热升华技术是利用热能将颜料转印至打印介质上，每种颜色的浓淡由打印头的温度变化控制，最大可以有256级等级。因为颜料是通过升华过程气相施加到纸张上的，因此三种基色相互融合可以形成连续的色阶，比之喷墨打印的墨滴效果好很多。单就打印效果而言，彩色热升华打印机可说是数码相机的最佳拍档，因此，这种打印机又常被称作彩色数码照片打印机，特别适合打印时对人像精致细腻的皮肤质感的要求，也具有长久保存不易退色的特点。

这里顺便把计算机三原色也写下来吧：红、蓝、绿

与美术三原色不同的原因：电脑是光学三原色，而美术是印刷三原色

计算

CSP2019初赛知识点梳理