初赛-2 | Axell's Blog

计算机发展历程

• 计算机采用的电子器件为：第一代是电子管,第二代是晶体管,第三代是中小规模集成电路,第四代是大规模,超大规模集成电路。
• 办公室自动化 (OA) 是计算机的一项应用,按计算机应用的分类,它属于 (信息处理)
• 最早的应用领域: 数值计算(计算弹道)

计算机的应用

• 科学计算(数值计算)

• 信息处理

• 自动控制

• 计算机辅助技术

  • 计算机辅助设计 CAD (Computer Aided Design)
  • 计算机辅助制造 CAM (computer Aided Manufacturing)
  • 计算机辅助教学 CAI (Computer Aided Instruction)
  • 计算机辅助测试 CAT (Computer Aided test)

• 人工智能 AI (Artificial Intelligence)

• 网络应用

第一台电子数字计算机:

• ENIAC,由电子管,继电器组成
• 诞生地: 美国
• 冯诺依曼 (Von Neumann) 在总结ENIAC的研制过程和制订EDVAC计算机方案时,提出两点改进意见是采用二进制和存储程序控制的概念
• ENIAC 并未采用储存程序控制的概念
• 1946年2月 15日,人类历史上公认的第一台现代电子计算机在美国宾夕法尼亚大学诞生,名称为ENIAC。
• 最初被用于弹道计算
• more

冯诺依曼体系结构

1. 程序以数据的形式储存在内存中,一律用二进制表示
2. 进行顺序运算,计算机运行过程中,把要执行的程序和处理的数据首先存入主存储器(内存),计算机执行程序时,将自动地并按顺序从主存储器中取出指令一条一条地执行,这一概念称作顺序执行程序。
3. 计算机由: 控制器,运算器,存储器,输入设备,输出设备五部分组成

主要由五大部件组成

1. 存储器用来存放数据和程序
2. 运算器主要运行算数运算和逻辑运算,并将中间结果暂存到运算器中
3. 控制器主要用来控制和指挥程序和数据的输入运行,以及处理运算结果
4. 输入设备用来将人们熟悉的信息形式转换为机器能够识别的信息形式,常见的有键盘,鼠标等
5. 输出设备可以将机器运算结果转换为人们熟悉的信息形式,如打印机输出,显示器输出等

冯诺依曼体系结构的指令和数据均采用二进制码表示；指令和数据以同等地位存放于存储器中,均可按地址寻访；指令由操作码和地址码组成,操作码用来表示操作的性质,地址码用来表示操作数所在存储器中的位置；指令在存储器中按顺序存放,通常指令是按顺序执行的,特定条件下,可以根据运算结果或者设定的条件改变执行顺序；机器以运算器为中心,输入输出设备和存储器的数据传送通过运算器。

关于冯诺依曼: 数字计算机之父,美籍匈牙利科学家,计算机鼻祖

图灵机的理论模型

奠定了人工智能的基础
注意图灵机只是理想中的,并未被开发出来
图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程,他把这样的过程看作下列两种简单的动作：
在纸上写上或擦除某个符号；
把注意力从纸的一个位置移动到另一个位置；
而在每个阶段,人要决定下一步的动作,依赖于 (a) 此人当前所关注的纸上某个位置的符号和(b) 此人当前思维的状态。
为了模拟人的这种运算过程,图灵构造出一台假想的机器,该机器由以下几个部分组成：
1.一条无限长的纸带 TAPE。纸带被划分为一个接一个的小格子,每个格子上包含一个来自有限字母表的符号,字母表中有一个特殊的符号 表示空白。纸带上的格子从左到右依此被编号为 0,1,2,… ,纸带的右端可以无限伸展。
2.一个读写头 HEAD。该读写头可以在纸带上左右移动,它能读出当前所指的格子上的符号,并能改变当前格子上的符号。
3.一套控制规则 TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作,并改变状态寄存器的值,令机器进入一个新的状态。
4.一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的,并且有一个特殊的状态,称为停机状态。参见停机问题。
注意这个机器的每一部分都是有限的,但它有一个潜在的无限长的纸带,因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

关于图灵: 艾伦·麦席森·图灵,英国 数学家,逻辑学家,被称为计算机科学之父,人工智能之父。

图灵奖: 信息学最高奖项,被誉为信息学的诺贝尔奖(不是菲尔茨奖…),华人学者目前仅有2000年图灵奖得主姚期智

摩尔定律

每隔18个月,在价格不变时,集成电路性能提升1倍

结构化程序理论

其概念最早由E.W.Dijikstra在1965年提出的,是软件发展的一个重要的里程碑。它的主要观点是采用自顶向下,逐步求精及模块化的程序设计方法；使用三种基本控制结构构造程序,任何程序都可由顺序,选择,循环三种基本控制结构构造。结构化程序设计主要强调的是程序的易读性。

面向对象

主要语言: C++,Java,Object-C (C,Pascal不是)

1967年挪威计算中心的Kisten Nygaard和Ole Johan Dahl 开发了Simula67语言,它提供了比子程序更高一级的抽象和封装,引入了数据抽象和类的概念,它被认为是 第一个面向对象语言。
20世纪70年代初,Palo Alto研究中心的Alan Kay所在的研究小组开发出Smalltalk语言,之后又开发出Smalltalk-80,Smalltalk-80被认为是最纯正的面向对象语言,它对后来出现的面向对象语言,如Object-C,C++,Self,Eiffl都产生了深远的影响。

面向对象主要特征：
封装性：封装是一种信息隐蔽技术,它体现于类的说明,是对象的重要特性。封装使数据和加工该数据的方法(函数)封装为一个整体,以实现独立性很强的模块,使得用户只能见到对象的外特性(对象能接受哪些消息,具有那些处理能力),而对象的内特性(保存内部状态的私有数据和实现加工能力的算法)对用户是隐蔽的。封装的目的在于把对象的设计者和对象的使用者分开,使用者不必知晓行为实现的细节,只须用设计者提供的消息来访问该对象。
继承性：继承性是子类自动共享父类之间数据和方法的机制。它由类的派生功能体现。一个类直接继承其它类的全部描述,同时可修改和扩充。继承具有传递性。继承分为单继承(一个子类只有一父类)和多重继承(一个类有多个父类)。类的对象是各自封闭的,如果没继承性机制,则类对象中数据,方法就会出现大量重复。继承不仅支持系统的可重用性,而且还促进系统的可扩充性。
多态性：对象根据所接收的消息而做出动作。同一消息为不同的对象接受时可产生完全不同的行动,这种现象称为多态性。利用多态性用户可发送一个通用的信息,而将所有的实现细节都留给接受消息的对象自行决定,如是,同一消息即可调用不同的方法。例如：Print消息被发送给一图或表时调用的打印方法与将同样的Print消息发送给一正文文件而调用的打印方法会完全不同。多态性的实现受到继承性的支持,利用类继承的层次关系,把具有通用功能的协议存放在类层次中尽可能高的地方,而将实现这一功能的不同方法置于较低层次,这样,在这些低层次上生成的对象就能给通用消息以不同的响应。在OOPL中可通过在派生类中重定义基类函数(定义为重载函数或虚函数)来实现多态性。
综上可知,在面对对象方法中,对象和传递消息分别表现事物及事物间相互联系的概念。类和继承是是适应人们一般思维方式的描述范式。方法是允许作用于该类对象上的各种操作。这种对象,类,消息和方法的程序设计范式的基本点在于对象的封装性和类的继承性。通过封装能将对象的定义和对象的实现分开,通过继承能体现类与类之间的关系,以及由此带来的动态联编和实体的多态性,从而构成了面向对象的基本特征。
面向对象设计是一种把面向对象的思想应用于软件开发过程中,指导开发活动的系统方法,是建立在“对象”概念基础上的方法学。对象是由数据和容许的操作组成的封装体,与客观实体有直接对应关系,一个对象类定义了具有相似性质的一组对象。而每继承性是对具有层次关系的类的属性和操作进行共享的一种方式。所谓面向对象就是基于对象概念,以对象为中心,以类和继承为构造机制,来认识,理解,刻画客观世界和设计,构建相应的软件系统。。按照Bjarne STroustRUP的说法,面向对象的编程范式：
l 决定你要的类；
2 给每个类提供完整的一组操作；
3 明确地使用继承来表现共同点。
由这个定义,我们可以看出：面向对象设计就是“根据需求决定所需的类,类的操作以及类之间关联的过程”。

计算机系统

计算机系统

硬件系统

主机

CPU

^

^

内存

^

外设

输入,输出设备

^

^

外存

软件系统

系统软件

^

应用软件

CPU

中央处理器主要包括运算器(算术逻辑运算单元,ALU,Arithmetic Logic Unit)和高速缓冲存储器(Cache)及实现它们之间联系的数据(Data),控制及状态的总线(Bus)。它与内部存储器(Memory)和输入/输出(I/O)设备合称为电子计算机三大核心部件。
物理结构: CPU包括运算逻辑部件,寄存器部件和控制部件等。

• 字长是CPU的主要性能指标之一,它表示: CPU一次能处理的二进制位数
• 主频(CPU Clock Speed,CPU一秒钟完成的指令周期数)=外频×倍频
• 主机: CPU+内储存器(ROM,RAM,Cache)
• 主要厂家: Intel AMD
• 主要型号: 奔腾(32bit) 酷睿(64bit)
• Central Processing Unit

计算机的指令由操作码和操作数(可以没有)组成

CPU寄存器

寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件,它们可用来暂存指令,数据和地址。在中央处理器的控制部件中,包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处理器的算术及逻辑部件中,寄存器有累加器(ACC)。

在CPU中至少要有六类寄存器：指令寄存器(IR),程序计数器(PC),地址寄存器(AR),数据寄存器(DR),累加寄存器(AC),程序状态字寄存器(PSW)。这些寄存器用来暂存一个计算机字,其数目可以根据需要进行扩充。

通用寄存器的位数=CPU字长

1. 数据寄存器

数据寄存器(Data Register,DR)又称数据缓冲寄存器,其主要功能是作为CPU和主存,外设之间信息传输的中转站,用以弥补CPU和主存,外设之间操作速度上的差异。

数据寄存器用来暂时存放由主存储器读出的一条指令或一个数据字；反之,当向主存存入一条指令或一个数据字时,也将它们暂时存放在数据寄存器中。

数据寄存器的作用是 ：

(1)作为CPU和主存,外围设备之间信息传送的中转站；

(2)弥补CPU和主存,外围设备之间在操作速度上的差异；

(3)在单累加器结构的运算器中,数据寄存器还可兼作操作数寄存器。

2. 指令寄存器

指令寄存器(Instruction Register,IR)用来保存当前正在执行的一条指令。

当执行一条指令时,首先把该指令从主存读取到数据寄存器中,然后再传送至指令寄存器。

3. 程序计数器

程序计数器(Program Counter,PC)用来指出下一条指令在主存储器中的地址。

在程序执行之前,首先必须将程序的首地址,即程序第一条指令所在主存单元的地址送入PC,因此PC的内容即是从主存提取的第一条指令的地址。

当执行指令时,CPU能自动递增PC的内容,使其始终保存将要执行的下一条指令的主存地址,为取下一条指令做好准备。若为单字长指令,则(PC)+1àPC,若为双字长指令,则(PC)+2àPC,以此类推。

但是,当遇到转移指令时,下一条指令的地址将由转移指令的地址码字段来指定,而不是像通常的那样通过顺序递增PC的内容来取得。

因此,程序计数器的结构应当是具有寄存信息和计数两种功能的结构。

4. 地址寄存器

地址寄存器(Address Register,AR)用来保存CPU当前所访问的主存单元的地址。

由于在主存和CPU之间存在操作速度上的差异,所以必须使用地址寄存器来暂时保存主存的地址信息,直到主存的存取操作完成为止。

当CPU和主存进行信息交换,即CPU向主存存入数据/指令或者从主存读出数据/指令时,都要使用地址寄存器和数据寄存器。

如果我们把外围设备与主存单元进行统一编址,那么,当CPU和外围设备交换信息时,我们同样要使用地址寄存器和数据寄存器。

5. 累加寄存器

累加寄存器通常简称累加器(Accumulator,AC),是一个通用寄存器。

累加器的功能是：当运算器的算术逻辑单元ALU执行算术或逻辑运算时,为ALU提供一个工作区,可以为ALU暂时保存一个操作数或运算结果。

显然,运算器中至少要有一个累加寄存器。

6. 程序状态字寄存器

程序状态字(Program Status Word,PSW)用来表征当前运算的状态及程序的工作方式。

程序状态字寄存器用来保存由算术/逻辑指令运行或测试的结果所建立起来的各种条件码内容,如运算结果进/借位标志(C),运算结果溢出标志(O),运算结果为零标志(Z),运算结果为负标志(N),运算结果符号标志(S)等,这些标志位通常用1位触发器来保存。

除此之外,程序状态字寄存器还用来保存中断和系统工作状态等信息,以便CPU和系统及时了解机器运行状态和程序运行状态。

因此,程序状态字寄存器是一个保存各种状态条件标志的寄存器。

储存器

主要有: RAM,ROM,Cache,硬盘,U盘…
CPU–Cache–RAM–外储存器
注意读取速度: 寄存器>Cache>RAM>外储存器

容量的计算

1 Byte=8 bit (8位=1字节)
1 KB=1024 Byte
1 MB=1024 KB
1 GB=1024 MB
1 TB=1024 GB
1 PB=1024 TB

图片大小的计算,视频大小的计算: 单图大小 时间 帧频
帧频: 中国 25fps , 欧美 32fps

USB

USB 1.0
传输速率 低速:1.5Mbps,高速12Mbps(=1.5MB/s)
USB 2.0
传输速率 最高速:480Mbps(=60MB/s)
USB 3.0
传输速率 最高速:5.0Gbps(=500MB/s) (因为加入了纠错码,实际速度不是理论的640MB/s)

Mbps : Million bits per second (8 bit(s) = 1 B(Byte))

BIOS

基本输入输出系统,是一组固化在计算机主板ROM上的程序

总线结构

连接CPU,储存器,I/O设备…

计算机的总线可以划分为数据总线(DB),地址总线(AB)和控制总线(CB),分别用来传输数据,数据地址和控制信号。总线是一种内部结构,它是cpu,内存,输入,输出设备传递信息的公用通道,主机的各个部件通过总线相连接,外部设备通过相应的接口电路再与总线相连接,从而形成了计算机硬件系统。

数据总线: 连接CPU和各部件,通常是双向的,具体传输方向由CPU控制
地址总线: CPU通过地址总线中传送的地址信息访问存储器。通常地址总线是单向的。同时,地址总线的宽度决定可以访问的存储器容量大小,如20条地址可以控制1MB的存储空间。
控制总线: 用来传送控制信号,以协调各部件之间的操作。控制信号包括CPU对内存储器和接口电路的读写控制信号,中断响应信号,也包括其他部件传送给CPU的信号,如:中断申请信号,准备就绪信号等。

寻址能力

32位地址总线 -> 4GB 内存
30位地址总线 -> 1GB 内存

计算公式 : $M=\frac {2^n}{2^{30}} GB$
Eg: 64KB=>16根地址总线,所以内存地址范围是: 0000~FFFF

计算机性能指标

1. CPU字长
2. 运算速度: MIPS(Million of Instructions Per Second,每秒百万条指令)
3. 主频: 指计算机CPU的时钟频率
4. 内存容量

操作系统

主要特征: 并发性,共享性,不确定性,虚拟性

主要有: MS-DOS,Windows,Linux,Unix,OS/2,OS/360(IBM),Chrome OS(Google)

桌面操作系统主要用于个人计算机上。个人计算机市场从硬件架构上来说主要分为两大阵营,PC 机与 Mac 机,从软件上可主要分为两大类,分别为类 Unix 操作系统和 Windows 操作系统：
Unix 和类 Unix 操作系统：Mac OS X,Linux 发行版(如 Debian,Ubuntu,Linux Mint,openSUSE,Fedora,Mandrake,Red Hat,Centos 等)；
微软公司 Windows 操作系统：Windows 98,Windows 2000,Windows XP,Windows Vista,Windows 7,Windows 8,Windows 8.1,Windows10 等
服务器
服务器操作系统一般指的是安装在大型计算机上的操作系统,比如 Web 服务器,应用服务器和数据库服务器等。服务器操作系统主要集中在三大类：
Unix 系列：SUNSolaris,IBM-AIX,HP-UX,FreeBSD,OS X Server 等；
Linux 系列：Red Hat Linux,CentOS,Debian,UbuntuServer 等；
Windows 系列：Windows NT Server,Windows Server 2003,Windows Server 2008,Windows Server 2008 R2,windows server 2012,windows server technical 等。
典型操作系统：
unix ,Linux ,mac os,windows,ios,android,WP,Chrome OS
操作系统分系统软件和应用软件；
系统软件如 Windows,linux,Dos,程序语言设计,语言处理程序,数据库管理程序 等等；

计算机语言

编写计算机程序所使用的的语言称为程序设计语言。通常分为三类:机器语言,汇编语言和高级语
言。

1. 机器语言
   机器语言是计算机能直接识别的语言,而且速度快。但机器语言书写困难,记忆复杂,一般很难掌

握。

1. 汇编语言
   用一些符号代替机器指令所产生的语言称为汇编语言,不能被计算机直接识别,需要特殊的程序将源程序翻译和连接成可执行的二进制代码

   st=>operation: 汇编源程序
   e=>operation: 可执行程序
   op1=>operation: 目标程序
   c1=>start: 翻译程序
   c2=>start: 连接程序

   st(right)->c1(right)->op1(right)->c2(right)->e

2. 高级语言
   计算机并不能直接接受和执行用高级语言编写的源程序,源程序在输人计算机时,道“翻译程序”翻

译成机器语言形式的目标程序,计算机才能识别和执行。这种“翻译”通新两种方式,即编译方式和解释
方式。
编译方式是:编译方式的翻译工作由“编译程序”来完成,它是先将整个源程序都转鞋二进制代码,
生成目标程序.然后把目标程序连接成可执行的程序,以完成源程序要处理运算并取得结果。

st=>operation: 高级语言
e=>operation: 可执行程序
op1=>operation: 目标程序
c1=>start: 编译程序
c2=>start: 连接程序

st(right)->c1(right)->op1(right)->c2(right)->e

解释方式是:源程序进人计算机时,解释程序边扫描边解释,对源程序的语句解释一条,执行一条,
不产生目标程序。

st=>operation: 高级语言
e=>operation: 可执行程序
c2=>start: 解释程序

st(right)->c2(right)->e

Pascal,Fortran,Cobol等高级语育执行行编译方式；
Baic,PHP语言则以执行解释方式为主；
而Pascel,C,C++语言是能书写编译程序的高级程序设计语言。

编码

英文编码

ASCII码 (American Standard Code for Information Interchange)
美国标准信息交换代码
基本ASCII共128(0127)个,但储存为1字节,所以基本ASCII最高位恒为0
拓展ASCII共128(128255)个,最高位恒为1

总的来说,ASCII是8位二进制码

中文编码

1. 国标码(GB2312-80),分为一级汉字(3755个,按拼音排序)和二级汉字(3008个,按部首排序)

2. 区位码,分为区码和位码,都为01~94的十进制

3. 区位码->国标码的转换:

   • 区码和位码分别加32(base 10)
   • eg: “国”,区码25,位码90,区位码2590,国标码397A(base 16),即(25+32)_10=39_16,(90+32)_10=7A_16

4. 区位码->机内码的转换

   • 区码和位码分别加160(base 10)
   • eg: 区码30,位码63,机内码

5. 国标码->机内码的转换

   • 国标码加8080(base 16)或32896(base 10)

外码,内码

内码(机内码),即计算机储存的信息,西文1B,中文2B
外码,即计算机显示在屏幕上的字符

原码,反码,补码

机器数和真值

在学习原码, 反码和补码之前, 需要先了解机器数和真值的概念.

1,机器数

一个数在计算机中的二进制表示形式,  叫做这个数的机器数。机器数是带符号的,在计算机用一个数的最高位存放符号, 正数为 0, 负数为 1.
比如,十进制中的数 +3 ,计算机字长为 8 位,转换成二进制就是 00000011。如果是 -3 ,就是 10000011 。
那么,这里的 00000011 和 10000011 就是机器数。

2,真值

因为第一位是符号位,所以机器数的形式值就不等于真正的数值。例如上面的有符号数 10000011,其最高位 1 代表负,其真正数值是 -3 而不是形式值 131(10000011 转换成十进制等于 131)。所以,为区别起见,将带符号位的机器数对应的真正数值称为机器数的真值。
例：0000 0001 的真值 = +000 0001 = +1,1000 0001 的真值 = –000 0001 = –1

码别

无符号范围

有符号范围

原码

$0$~$2^{n}-1$

$-2^{n-1}+1$~$2^{n-1}-1$

反码

NULL

$-2^{n-1}+1$~$2^{n-1}-1$

补码

NULL

$-2^{n-1}$~$2^{n-1}-1$

注意: 0的原码和反码不唯一,但补码唯一
一般来说,计算机中N位2进制表示的范围: 无符号$02^{n}-1$,有符号$-2^{n-1}$$2^{n-1}-1$

原码,反码,补码的转换

对于正数,原码,反码,补码都一样
对于负数/0,

1. 反码,就是原码除符号位取反
2. 补码,就是反码+1

小数的表示

1. 定点表示法(定点计算机很少了)
2. 浮点表示法

浮点表示法

分为尾数,阶码两部分,N=$2^E*S$,E为阶码(Expoent),S为尾数(Mantissa)
Eg: 00001001 B=$2^{+8}*0.00001001$

网络

计算机网络最大的优点: 资源共享
网络的主要功能: 资源共享,信息传输,分布处理,综合信息服务

网络的发展历程

远程终端联机阶段: 计算机–终端
计算机网络阶段:

1. 计算机–计算机
2. Internet

互联网起源于20世纪60年代中期,是美军在ARPA(阿帕网ARPANET,美国国防部研究计划署)制定的协定下,首先用于军事连接,后将美国西南部的加利福尼亚大学洛杉矶分校,斯坦福大学研究学院,UCSB(加利福尼亚大学)和犹他州大学的四台主要的计算机连接起来。这个协定由剑桥大学的BBN和MA执行,在1969年12月开始联机。
另一个推动 Internet发展的广域网是NSF网,它最初是由美国国家科学基金会资助建设的,目的是连接全美的5个超级计算机中心,供100多所美国大学共享它们的资源。NSF网也采用TCP/IP协议,且与Internet 相连。

我国Internet的发展情况：
八十年代末,九十年代初才起步。
1989年我国第一个公用分组交换网CNPAC建成运行。
我国已陆续建成与Internet互联的四个全国范围的公用网络：
中国公用计算机互联网(CHINANET),中国金桥信息网(CHINAGBN)
中国教育和科研计算机网(CERNET),中国科学技术网(CSTNET)

顶级域名有三类：
• 国家顶级域名,如cn(中国),us(美国),uk(英国),mo(澳门),tw(台湾),sg(新加坡)；
• 国际顶级域名—— int ,国际性组织可在int 下注册；
• 通用顶级域名,如：com(商业组织),net(网络组织),edu(教育),gov(政府),org(非盈利性组织),mil(军事部门)……
有了域名标识,对于计算机用户来说,在使用上的确方便了很多。但计算机本身并不能自动识别这些
域名标识,于是域名管理服务器DNS(domain name system)就应运而生了。

万维网: World Wide Web(WWW)
远程登陆: Telent协议
URL: Uniform Resource Locator(统一资源定位符)

调制解调器(Modem)是Modulator（调制器）与Demodulator（解调器）的简称,中文称为调制解调器,它是在发送端通过调制将数字信号转换为模拟信号,而在接收端通过解调再将模拟信号转换为数字信号的一种装置。
所谓调制,就是把数字信号转换成电话线上传输的模拟信号；解调,即把模拟信号转换成数字信号。合称调制解调器。

网络的分类

1. 局域网(LAN)
2. 城域网(MAN)
3. 广域网(WAN)

TCP/IP四层模型与OSI参考模型

TCP/IP 4层协议

OSI 7层协议

应用层(见下)

应用层

^

表示层

^

会话层

传输层(TCP,UDP协议)

传输层

网络层(IP协议,ICMP)

网络层

链路层(硬件)

链路层

^

物理层

1.链路层 (数据链路层/网络接口层) ：包括操作系统中的设备驱动程序,计算机中对应的网络接口卡

2.网络层 (互联网层) ：处理分组在网络中的活动,比如分组的选路。

3.运输层：主要为两台主机上的应用提供端到端的通信。

4.应用层：负责处理特定的应用程序细节。

TCP: (Transmission Control Protocol 传输控制协议)
UDP: (User Datagram Protocol 用户数据报协议)

IPv4 IPv6

IPv4: 32位(4Byte),表示时用四个点隔开,每一段<=255(可容纳$2^{32}-1$台设备)
IPv6: 128位(16Byte)(可容纳$2^{128}-1$台设备)(同时,IPv6安全性更高)

5 类IP地址

IP地址采用:点分十进制记法

类别

地址范围

IP地址前4bit

保留地址

A

1.0.0.1~126.255.255.254

0_*_

10.0.0.1~10.255.255.254

B

128.1.0.1~191.255.255.254

10**

172.16.0.1~172.31.255.254

C

192.0.0.1~223.255.255.254

110*

192.168.0.1~192.168.255.254

D

224.0.0.1~239.255.255.254

1110

NULL

E

240.0.0.1~255.255.255.254

1111

保留,做研究用

IP地址由: 网络地址和(子网)主机地址组成,由子网掩码区分
eg:

IP

192.168.0.1

11000000.10101000.00000000.00000001

掩码

255.255.255.255

11111111.11111111.11111111.00000000

网络号

192.168.0.0

11000000.10101000.00000000.00000000

子网主机号

0.0.0.1

00000000.00000000.00000000.00000001

应用层常见协议

1. HTTP协议 (Hyper Text Transfer Protocol,超文本传输协议)
2. FTP协议 (File Transfer Protocol,文件传输协议)
3. SMTP 协议 (简单邮件传送协议,用户发信到邮件网关的传输协议)
4. DNS协议 (域名解析协议)
5. POP协议(Post Office Protocol 3,邮局协议/邮件接收协议)
6. IMAP协议 (Internet Mail Access Protocol,Internet邮件访问协议)

字符串

1. 空串也是子串
2. 字符串的起始位置通常为0
3. substr(a,b)是指从第a位开始,截取长度为b的字符串并返回
4. for (int i=1;i<=4;++i) cout<<’a’+i;输出的是bcde

表达式

前缀表达式(波兰式),中缀表达式,后缀表达式(逆波兰式)的转换:

1. 前->中 从后往前扫,遇到数字压入栈中,遇到操作符弹出两个数字,运算后压入栈中
2. 后->中 从前往后扫,遇到数字压入栈中,遇到操作符弹出两个数字,运算后压入栈中
3. 中->后 按照优先级加上(),然后把每一个运算符移到它后面的一个)的右侧,最后去掉括号
4. 中->前 按照优先级加上(),然后把每一个运算符移到它前面的一个(的左侧,最后去掉括号
5. 前->后 前->中->后
6. 后->前 后->中->前

算法

性质

1. 有穷性: 在执行有限步后可以得到答案
2. 确切性: 保证对于任何输入,都有唯一路径
3. 输入: 可以无输入(已经内嵌在程序中)
4. 输出: 至少一个输出(否则无意义)

结构

1. 顺序结构
2. 选择结构
3. 循环结构
   3.1. 当型循环型

3.2. 直到循环型

排序

1. 插入排序
2. 选择排序
3. 冒泡排序
4. 归并排序
5. 快速排序
6. 基数排序(不基于比较)
7. 希尔排序
8. 二叉树排序 (即堆排序)
9. 桶排序

排序的稳定性: 选择,希尔,快速,堆排序不稳定
排序中的Rank[i]: 往往储存a[i]在第几个

逻辑运算

1. 注意运算优先级
2. 使用&&时,如果前一个为false,则后一条直接跳过不执行(初赛常考)

二分写法

常规

int l=1,r=n,mid;
while (l<=r){
  mid=(l+r)/2;
  if (...){
    l=mid+1;
  }else{
    r=mid-1;
  }
}

右偏(右指针储存答案)

int l=1,r=n,mid;
while (l<r){
  mid=(l+r)/2;
  if (...){
    l=mid+1;
  }else{
    r=mid;  //r直接储存答案
  }
}

左偏(左指针储存答案)

int l=1,r=n,mid;
while (l<r){
  mid=(l+r+1)/2;
  if (...){
    r=mid-1;
  }else{
    l=mid;  //l直接储存答案
  }
}

组合数学

计算公式:
$ C^m_n = \frac {n!}{m!(n-m)!} $
$ P^m_n = \frac {n!}{(n-m)!} $

1. $2^{n}=C_{n}^{0}+C_{n}^{1}+ \dots +C_{n}^{n}$ (杨辉三角)

2. 错排公式 : $D_n = (n-1) \times (D_{n-1}+D_{n-2})$ 其中: $D_1=0,D_2=1,D_3=2,D_4=9$ more

3. 重复组合:n个不同元素,取出r个,且可以重复,不计顺序的方法数: $H_n^r=C^{r}_{n+r-1}$

   • 例: 从n堆颜色不同的小球(每堆有无限个)中,选出r个小球的方式

4. 重复排列:n个不同元素,取出r个,且可以重复,计顺序的方法数: $U_n^r=n^r$

more

二项式定理:
$ (a+b)^n = \sum^{n}_{i=0} C_n^i a^{n-i} b^i $

取石子游戏

位运算

数学符号

计算机符号

C++

∨

or

\

\

∧

and

&&

┐

not

!

⊕

xor

/^/

xor:

1. a xor a = 0
2. a xor 0 = a

注意区分xor的c++表达式和and的数学表达式的区别!!
数学优先级: and>or !!
C++优先级: == > & > ^ > | > && > ||

集合运算: 并,交,差,非(补)运算 (优先级 : 补>交,并)

进制

进制

基数

符号

10

10

D

16

16

H

8

8

O

2

2

B

进制的转换:

1. 2,8,16->10 带权展开,相加即可

2. 10->2

   • 整数部分:可以/2取余,后逆序输出
   • 小数部分:可以*2取整,后顺序输出

3. 10->8,10->16: 先转换为2进制,整数部分向左,小数部分向右,每3(4)位转化成一位

栈(stack)

又称:后进先出表(LIFO: Last in, First out)

上溢出错: 栈顶指针大于开辟的空间

常用的算法:

• 进栈 PUSH
• 获取栈顶元素 TOP
• 弹出栈顶元素 POP
• 判断是否为空栈 IsEmpty

队列(queue)

又称:先进先出表(FIFO: First in, First out)
使用循环队列时,判断队列是否满用 head!=tail
上溢出错: tail指针大于开辟的空间
假溢出: tail过大,但head前任然有空间(可以用循环队列克服)
循环队列入队算法:

• tail++
• if (tail==n+1) tail=1;
• if (tail==head) cout<<”error,the queue is full”
• else Q[tail]=x
  循环队列计算元素个数公式 $d=(tail-head+n) \mod n$

常用的变量:
head,tail // l,r // front,rear

树

遍历:前序,中序,后序,层次,dfs,bfs

术语:

1. 满二叉树
2. 均衡二叉树
3. 完全二叉树
4. 哈夫曼树:more
5. 最小生成树

树和二叉树的转换: more

图

拓扑排序: more
排序求交换任意(相邻)两数的最小次数

NOIP常识

NOIP 推荐的环境：(pascal 类)free pascal,Lazarus；(c 及 c++ 类)Dev C++,gcc/g++,RHIDE；NOIP 不推荐的环境：Turbo pascal 7(TP7),Turbo C(TC),Visual C++(VC)。

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Link to this article: https://blog.axell.top/archives/42/