初赛笔记1——计算机科学基础

计算机科学基础

计算机发展史

通常考察如下知识点:

图灵机

所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

对于任意一个图灵机,因为它的描述是有限的,因此我们总可以用某种方式将其编码为字符串。我们用 表示图灵机 $M$ 的编码。

我们可以构造出一个特殊的图灵机,它接受任意一个图灵机 $M$ 的编码 ,然后模拟 $M$ 的运作,这样的图灵机称为通用图灵机(Universal Turing Machine)。现代电子计算机其实就是这样一种通用图灵机的模拟,它能接受一段描述其他图灵机的程序,并运行程序实现该程序所描述的算法。

冯·诺伊曼结构

数学家冯·诺依曼提出了计算机制造的三个基本原则,即采用二进制逻辑、程序存储执行以及计算机由五个部分组成(运算器、控制器、存储器、输入设备、输出设备),这套理论被称为冯·诺依曼体系结构。

世界上第一个电子计算机

世界上第一台通用计算机 “ENIAC” 于 1946 年 2 月 14 日 在美国宾夕法尼亚大学诞生。

美国国防部用它来进行弹道计算。它是一个庞然大物,用了 $18000$ 个电子管,占地 $150$ 平方米,重达 $30$ 吨,耗电功率约 $150$ 千瓦,每秒钟可进行 $5000$ 次运算。

计算机时代划分

  1. 第一代:1946 到 1958 年,这个时期构成计算机的主要逻辑元件是电子管,称为电子管时代。

  2. 第二代:1959 到 1964 年。第二代计算机用晶体管代替了体积庞大的电子管,人们将这一时代称为晶体管计算机时代。

  3. 第三代:1965 到 1970 年,此阶段以中、小规模集成电路作为计算机的逻辑元件。这一时代称为集成电路计算机时代。

  4. 第四代:从 1970 年至今,随着集成电路集成度的不断提高,采用大规模、超大规模集成电路作逻辑元件,这一时代称为大规模集成电路计算机时代。

  5. 第五代:智能计算机的概念是日本政府于1982年提出的,目标是实现智能计算机。这一目标至今尚未能直接促进计算机的更新换代。

编程语言的发展

现在我们日常使用的编程语言都是高级语言,例如 C/C++/Java/Python/Pascal 等。

世界上第一个被正式推广使用的高级语言是 Fortran。

计算机界奖项

计算机界最高奖项:图灵奖,由美国计算机协会(ACM)于 1966 年设立,专门奖励那些对计算机事业作出重要贡献的个人。其名称取自计算机科学的先驱、英国科学家艾伦·麦席森·图灵(Alan M. Turing)。

目前唯一的华人图灵奖得主为:姚期智。

计算机基本结构与使用

通常考察如下几类知识点:

文件

文件是一段由二进制组成的数据流。一个 0 或者 1 位就就叫做一位。

文件的大小也就是这个数据流由多少个 0 或 1 位组成,比如由 $1024$ 个位组成就说有 $1024$ bits。

我们一般把 $8$ 位叫做一个字节,也就是 $8$ bit= $1$ Byte,一般字节 Byte 会大写开头的 B 以示区分。

而一般会用 $2 ^ {10} = 1024$ 作为字节的换算比例,也就是说:

常见文件类型

二进制文本文件:txt

图像文件:jpg、jpeg、png、gif(动态图片)

视频文件:avi、mp4、mpeg、wmv

音频文件:mp3

计算机硬件组成

计算机网络基础知识

通常考察如下几类知识点:

OSI七层网络协议

由上到下依次是:

这是由国际标准化组织 ISO 于 1981 年正式推荐的规范。

IP地址

这里只讨论 IPv4 相关的知识,IPv4 是 $32$ 位的地址,而 IPv6 是 $128$ 位的地址。

IP 地址(Internet Protocol Address)是指互联网协议地址,又译为网际协议地址。

给因特网上的每台计算机和其它设备都规定了一个唯一的地址,叫做“IP地址”。由于有这种唯一的地址,才保证了用户在连网的计算机上操作时,能够高效而且方便地从千千万万台计算机中选出自己所需的对象来。

IP地址是一个 $32$ 位的二进制数,通常被分割为 $4$ 个“ $8$ 位二进制数”(也就是 $4$ 个字节)。IP地址通常用“点分十进制”表示成($a.b.c.d$)的形式,其中,$a,b,c,d$ 都是 $0$ ~ $255$ 之间的十进制整数。

IP地址分为 $A,B,C,D,E$ 五类,在二进制表示种它们的区分是 $A$ 类地址的第一位总是 $0$,$B$ 类地址的前两位总是 $10$,$C$ 类地址的前三位总是 $110$,$D$ 类前四位固定为 $1110$,$E$ 类前五位固定为 $11110$。

子网掩码

子网掩码不能单独存在,它必须结合IP地址一起使用。子网掩码只有一个作用,就是将某个IP地址划分成网络地址和主机地址两部分。

通过计算机的子网掩码判断两台计算机是否属于同一网段的方法是,将计算机十进制的IP地址和子网掩码转换为二进制的形式,然后进行二进制“与” (AND) 计算(全 1 则得 1,不全 1 则得 0),如果得出的结果是相同的,那么这两台计算机就属于同一网段。

类别子网掩码的二进制数值子网掩码的十进制数值
A11111111 00000000 00000000 00000000255.0.0.0
B11111111 11111111 00000000 00000000255.255.0.0
C11111111 11111111 11111111 00000000255.255.255.0

使用方式

域名以及 DNS

域名(英语:Domain Name),又称网域,是由一串用点分隔的名字组成的Internet上某一台计算机或计算机组的名称,用于在数据传输时对计算机的定位标识(有时也指地理位置)。

比如 jisuanke.com

域名系统(英文:Domain Name System,缩写:DNS)是互联网的一项服务。它作为将域名和IP地址相互映射的一个分布式数据库,能够使人更方便地访问互联网。

域名分级

顶级域名

顶级域名是域名中只包含一个点的后缀。

国家顶级域名:.cn(中国), .jp(日本) 等等。 国际顶级域名:.com(工商业),.net(网络提供商),.org(非盈利组织)等等。

二级域名

顶级域名到它前面一个点。

比如 xx.xx.edu.cn 是在国家顶级域名 .cn 下的二级域名 .edu 表示教育部门。

再往前就是三级、四级域名等等。

常见协议介绍

程序设计基础知识

通常考察如下几类知识点:

高级语言

高级语言是相对于机器语言的一类语言,换言之,在我们熟知的编程语言中,除了机器码、汇编语言以外,都是高级语言,包括 C、C++、Python、Scratch、Java 等。

汇编语言和机器码是一一对应的关系,可以理解为同一指令的两种不同展现形式,都不属于高级语言。

第一门高级语言是 FORTRAN,诞生于 1954 年,随后陆续诞生了 C、C++、Java、Python 等语言。

程序语言除了分为高级语言和机器语言外,还可以分为面向对象、面向过程的语言。我们学过的 C++ 语言是面向对象的语言,以及 Python、Java 也都是面向对象的语言;而 FORTRAN、C 语言则是面向过程的语言。

编译

一些编译型的高级语言在经过编译器的某些步骤后会被翻译成机器语言,这个过程之一就叫编译。我们经常会使用类似 Codeblocks、Dev-C++、VS 之类的工具来一键运行所写程序,但是这些工具都不是编译器,而叫做集成开发环境 IDE(Integrated Development Environment)。

真正的 C/C++ 编译器有 gcc、g++、clang、msvc 等。

C/C++ 从代码到机器码的过程是:预处理、编译、汇编、链接

解释型语言

例如 Python 就是一种解释型语言,此类语言是没有编译过程的,他们直接就可以按语义解释执行。这类语言的优点是写起来比较容易上手,省去了编译运行的复杂性,它有一些缺点比如由于不能生成可运行的二进制文件它必须将源码提供给客户。

C/C++ 基础类型

C/C++ 属于静态类型语言,所有的变量必须声明它的类型。

比如:int a = 0;,变量 a 在它的作用域内就一直会是整型类型。

基础类型之间可以互相转换,一般分为显式强制类型转换和隐式强制类型转换。

比如:

int a = (int)(1.0 / 2);

那么变量 a 的值就是 $0$,因为从 double 到 int 的强制类型转换会把 double 的小数位抹掉,即 $0.5$ 向下取整。

int a = 1;
double b = 2.3;
a = b;

这种就叫做隐式强制类型转换,a 的值变为 $2$。

变量进行类型转换时,还有以下的规则:

当出现在表达式里时,有符号和无符号的 char 和 short 类型都会自动转化成 int 型。float 类型也会自动转化成 double 类型。

在包含两种数据类型的任何运算里,两个值都被转换成两种类型里面的较高级别。

类型级别从高到低的顺序是 long double、double、float、unsigned long long、long long、long、unsigned int 和 int。

在赋值语句中,计算的最后结果将被转化成要被赋值的那个变量的类型。

作为参数传递的时候,char 和 short 会被转化成 int,float 会被转化成 double。

C/C++ 基础类型占用字节数

在 C/C++ 中,每种类型都有其固定的占用空间,下面给出表格: