![](https://csdnimg.cn/release/download_crawler_static/88399758/bg1.jpg)
CSP-J/S 第一轮知识点选讲
NOIP
(全国青少年信息学奥林匹克竞赛)于
2019
年取消。取而代之的是由
CCF
推出的非专
业级软件能力认证,也就是现在的
CSP-J/S
。
信息学史及基本知识
一、信息学及计算机史
计算机的顶级奖项:图灵奖、冯·诺依曼奖
图灵奖:由
ACM
(美国计算机协会)设立于
1966
年。是“计算机界的诺贝尔奖”。
冯·诺依曼奖:由
IEEE
设立。
对信息科学做出突出贡献的大神:图灵(所以才有个奖),冯 · 诺伊曼
中国获图灵奖的大神:姚期智(清华就有姚班,就是以他的名字命名的)
世界第一台电子计算机:埃尼阿克(
ENIAC
),于
1946
年
2
月
14
日(够虐狗的)在美国宾
夕法尼亚大学诞生。又被叫做电子管计算机。
二、关于编程
编程语言:
分两类:面向对象和面向过程。
高级语言和低级语言的区别:
高级语言需要编译运行,常数较大,运行速度慢。而低级语言常数极小,运行速度快。此外,
高级语言更容易移植。
常见低级语言:汇编
面向对象的高级语言:
C++
,
Java
,
EIFFEL
,
Simula 67
等。
面向过程的高级语言:
C
,
Fortran
语言。
递归编程:
递归是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用
于解决很多的计算机科学问题。简单来讲,就是“自身调用自身”(在函数中)。
P
类
/NP
类
/NPC
类问题:
1
、
P
类问题:如果一个问题能找到一个在多项式时间内解决它的算法,那么这个问题就是
P
问题。例如乘法、人名排序
2
、
NP
类问题:注意:
NP
问题不是非
P
类问题,而是在多项式时间内验证一个解的问题。
或者,我们可以将其理解为在多项式时间内猜出一个解的问题。著名的
NP
类问题:旅行家
推销问题
(TSP)
。即有一个推销员,要到
n
个城市推销商品,他要找出一个包含所有
n
个城
市的环路,这个环路路径小于
a
。
这个问题如果单纯的用枚举法来列举的话会有
(n-1)
!种,已经不是多项式时间的算法了,
(
注:
阶乘算法比多项式的复杂
)
。那怎么办呢?我们可以用猜的,假设我人品好,猜几次就猜中
了一条小于长度
a
的路径,我画画画画,好的,我得到了一条路径小于
a
的环路,问题解决
了,皆大欢喜。可是,我不可能每次都猜的那么准,也许我要猜完所有种情况呢?所以这是
一个
NP
类问题。我们能在多项式时间内验证并得出问题的一个正确解,可是我们却不知道
该问题是否存在一个多项式时间的算法,每次都能解决他
(
注意,这里是不知道,不是不存
在!
)
。
3
、
NPC
类问题
,NP
完全问题:定义如下:如果一个问题是
NP
问题,而且所有的
NP
问题都
可以约化到它。那么它就是
NPC
类问题。再来介绍一下关于约化的定义:如果一个问题
A
可以约化为问题
B
,含义就是这个问题
A
可以用问题
B
的解法来解决。例如一元一次方程的