数学与信息学-jiangli.pptVIP

数学与信息学竞赛 姜黎 信息学竞赛中通常用到的数学致知识 组合数学相关知识 集合论的初步知识 图论知识与算法 初等数论知识 解析几何基本知识 组合数学相关知识 对于联赛来说应当掌握基本的排列组合计数方法、简单的容斥原理以及抽屉原理，递推关系的建立方法。但对于更高层次的选手来说，应当掌握Polya、Ramsey等定理，在NOI2006中有便有一道题，就可用Polya优化。 集合论的初步知识 信息学联赛中一般很少直观的应用集合论部分的重要知识，但是在理论证明过程中却显示出了相当的重要性。联赛选手可以越过这一部分。 图论知识与算法 这部分的知识略显重要了,首先要掌握,基本概念、定理等理论知识.然后熟练运用常用算法,如:最短路、最小生成树等等.联赛应用比较多的为常用的算法了.但是有难度的竞赛还是考察灵活运用基本知识解决问题的能力. 初等数论知识 如果说数学是科学的皇后，那么数论就是皇后的皇冠，数论难题便是皇冠上的一颗明珠。一般来说信息学竞赛中的数学难题除了组合数学外，数论也是一个能够出难题的部分。对于联赛来说，只需掌握数论的皮毛即可。例如 算术基本定理、最大公约数和最小公倍数、素数的相关知识等等的基本知识要做到灵活运用。 像欧拉定理、费尔马小定理等、中国剩余定理、康托展开式等等的则不需要掌握。 解析几何基本知识 这部分知识用处虽然不广泛，但是难免会遇到。因为计算几何的题目有些难度，联赛所掌握的知识一般来说无法解决，然而，由于解析几何的特点，特别适合设计算法。对于这部分题目，解析几何只是作为解题的一小部分出现。比如前几年联赛题中就用到了欧式距离公式，所以只要平时所学知识牢固，一般没有问题。 总结 　 信息学是数学的一条分支，纵观古今，哪一为信息学大师不是数学家？像当今世界最伟大的数学家哈密尔顿等等都在数学上有很高的建树。因此数学与信息学竞赛变的更加密切将会是一个大的趋势。 * 除去简单的计数、统计以外还通常用到以下知识: *