月度归档： 2009年12月

由于信息奥林匹克竞赛没有统一的大纲，所以教师普遍感到指导起来特别困难。指导信息学奥林匹克竞赛的教师必须了解所涉及的基本知识，不断扩充新的知识。

信息学奥林匹克竞赛的比赛方式是让选手在限定的时间内，用计算机编程的方法解决给定的任务。优胜者将是具有创新能力、对信息科学技术领域的知识有较广博涉猎的选手。

信息学奥林匹克竞赛所需要的知识和能力包括：

1. 数学建模的知识和能力
   既要有常用的数学知识，如代数、几何、组合数学（主要包括加法原理、乘法原理、排列与组合、递推关系、鸽巢原理、容斥原理、母函数、Polya原理、拉丁方）、数论（主要包括整除和同余等）等，又要有把实际问题转化为数学模型的能力。
2. 算法分析与设计的知识和能力
   建好数学模型后必须用相关的算法来解决数学问题，由于程序的计算时间也是检查的范围，所以必须有优化算法的能力，要掌握时间的复杂性分析的相关知识。
   常用的算法设计方法有：
   1. 递归方法。递归是通过调用自身来完成与自身要求相同但规模较小的子问题的求解，可以简化程序，但功能强大，能求解许多问题，如阶乘函数、Fibonacci数、Hanoi塔问题等。所以，应用算法解决实际问题时，递归方法是非常有效的。
   2. 分治策略。分治策略是“分而治之”的意思，即把原问题分解成若干个子问题，用求解子问题来解决原问题，往往比较简单。利用分治策略可以解决涉及二分查找、整数乘法、矩阵乘法等的实际问题。
   3. 动态规划问题。动态规划方法是将要求解的问题逐层分解成一级一级、规模逐步缩小的子问题，知道可以直接求出其解的子问题为止。分解成的所有子问题按层次关系构成一棵树，树根就是原问题。动态规划方法可以解决涉及最短路劲问题、旅行商问题、矩阵链乘问题、最长公共子序列问题、图的任意两点间的最短距离问题、整数规划问题、可靠性问题、同顺序流水作业的任务安排问题、设备更新问题等的实际问题。

   常用的算法有：

   1. 排序算法。包括冒泡排序、堆排序、归并排序、递归排序、插入排序、Shell排序、基数排序、下溢排序、插入归并排序等。但要注意，对任意n个数的排序，基于比较的排序算法，理论上已经证明其时间复杂性的下界约为nlog2^n-1.44n+0.5log2^n+1.325。目前最好的排序算法是Ford-Johnson归并插入分类法，其时间复杂性为nlog2^n-4n/3+0.5log2^n+(15+(-1)^m)/12(其中n=2^m)，已接近理论下界。任何比它好的算法，一般都是对特殊的问题而言的。
   2. 最短路径有关的算法。包括最短路径问题、旅行商问题、Kruskal算法、Prim算法、Dijkstra算法、遗传算法等。
   3. 矩阵乘积算法。包括Strassen算法、Winograd算法、“三个苏联人算法”。
   4. 数据压缩算法。包括Huffman编码、FFT算法等。
   5. 作业调度算法。包括同顺序的Flowshop问题、带时间期限的Flowshop问题、并行机问题等。
   6. 线性规划和整数规划问题。
   7. 关于树的算法。包括二分树、AVL树、2-3树、2-3-4树等。
   8. 分支界定法。
   9. 并行算法。
   10. 深度优先搜索（DFS）算法和广度优先搜索(BFS)算法。
   11. 网络流算法。包括最大流和最小费用流算法。
   12. Greed算法。
   13. 随机化和近似算法。
3. 数据结构和程序设计的知识和能力
   利用算法解决了数学问题后必须用程序来实现，所以必须有相关的数据结构知识（主要包括线性表、串、数组、树、图、指针和链表）和程序设计能力、学生必须掌握一种程序设计语言。