信息学奥赛基本知识 信息学奥赛大纲

2021年4月2日，中国计算机学会（CCF）发布《全国青少年信息学奥林匹克系列竞赛大纲》。

信息学与数学密切相关，本文为《大纲》中涉及的数学知识清单。下文中[x]为难度系数。

入门级

数及其运算

[1]数的概念，算术运算（加、减、乘、除、求余）

[1]数的进制：二进制、八进制、十六进制和十进制及其转换

[2]编码：ASCII码，哈夫曼编码，格雷码

初中数学

[1]初中代数

[1]初中平面几何

初等数论

[3]整除、因数、倍数、指数、质数、合数、同余等概念

[3]唯一分解定理

[3]欧几里德算法（辗转相除法）

[4]埃氏筛法和线性筛法求素数

组合数学

[2]加法原理

[2]乘法原理

[4]排列及计算公式

[4]组合及计算公式

[4]杨辉三角公式

提高级

高中数学

[5]代数

[6]解析几何

[6]立体几何

初等数论

[5]同余式

[7]欧拉定理和欧拉函数

[7]费马小定理

[7]威尔逊定理

[7]裴蜀定理

[7]逆元

[7]扩展欧几里得算法

[7]孙子定理（中国剩余定理）

组合数学

[6]可重集排列

[6]可重集组合

[6]错排列、圆排列

[6]鸽巢原理

[6]二项式定理

[7]容斥原理

[7]卡特兰数

线性代数

[5]矩阵概念

[6]稀疏矩阵，三角矩阵，对称矩阵

[6]矩阵的初等变换

[6]矩阵的加减乘和转置运算

[7]线性方程组的高斯消元法

,