信息学奥赛之数学一本通
豆瓣
[中]林厚从
简介
《青少年信息学奥林匹克竞赛实战辅导丛书:信息学奥赛之数学一本通》的适用对象包括：中学信息学奥林匹克竞赛选手及辅导老师、大学ACM程序设计比赛选手及教练、高等院校计算机相关专业的师生、程序设计爱好者等。数学是计算机程序设计的灵魂。利用数学方面的知识、数学分析的方法以及数学题解的技巧，可以使得程序设计变得轻松、美观、高效，而且往往能反映出问题的本质。在国内外各项程序设计比赛（比如，ACM、NOI）活动中，越来越多地用到各种复杂的数学知识，对选手的数学修养要求越来越高。编写《青少年信息学奥林匹克竞赛实战辅导丛书:信息学奥赛之数学一本通》的目的就在于给广大ACM队员、NOI选手以及编程爱好者，系统分析一些程序设计中常用的数学知识和数学方法。
目录
第1章数论
1.1整除
1.2同余
1.3最大公约数
1.3.1辗转相除法
1.3.2二进制算法
1.3.3最小公倍数
1.3.4扩展欧几里得算法
1.3.5求解线性同余方程
1.4逆元*
1.5中国剩余定理
1.6斐波那契数
1.7卡特兰数
1.8素数
1.8.1素数的判定
1.8.2素数的相关定理
1.8.3Miller—Rabin素数测试
1.8.4欧拉定理
1.8.5PollardRho算法求大数因子
1.9Baby—Step—Giant—Step及扩展算法
1.10欧拉函数的线性筛法
1.11本章习题
第2章群论
2.1置换
2.1.1群的定义
2.1.2群的运算
2.1.3置换
2.1.4置换群
2.2拟阵
2.2.1拟阵的概念
2.2.2拟阵上的最优化问题
2.3Burnside引理
2.4Polya定理
2.5本章习题
第3章组合数学
3.1计数原理
3.2稳定婚姻问题*
3.3组合问题分类
3.3.1存在性问题
3.3.2计数性问题
3.3.3构造性问题
3.3.4最优化问题
3.4排列
3.4.1选排列
3.4.2错位排列
3.4.3圆排列
3.5组合
3.6母函数*
3.6.1普通型母函数
3.6.2指数型母函数
3.7莫比乌斯反演
3.8Lucas定理
3.9本章习题
第4章概率
4.1事件与概率
4.2古典概率
4.3数学期望
4.4随机算法
4.5概率函数的收敛性*
4.6本章习题
第5章计算几何
5.1解析几何初步
5.1.1平面直角坐标系
5.1.2点
5.1.3直线
5.1.4线段
5.1.5多边形
5.1.6圆
5.2矢量及其运算
5.2.1矢量的加减法
5.2.2矢量的数量积
5.2.3矢量的矢量积
5.3计算几何的基本算法
5.4平面凸包
5.5旋转卡壳
5.5.1计算距离
5.5.2外接矩形
5.5.3三角剖分
5.5.4凸多边形属性
5.6半平面交
5.7离散化
5.8本章习题
第6章矩阵
6.1矩阵及其运算
6.1.1矩阵的基本运算
6.1.2矩阵的乘法运算
6.1.3矩阵的行列式
6.1.4矩阵的特殊类别
6.2数字方阵
6.3线性方程组及其解法
6.3.1高斯消元法
6.3.2LU分解法
6.4Matrix—Tree定理
6.5本章习题
第7章函数
7.1函数的基本知识
7.1.1函数的特性
7.1.2常见的函数类型
7.2函数的单调性
7.3函数的凹凸性
7.4SG函数
7.5快速傅立叶变换
7.6快速数论变换
7.7本章习题