全国信息学奥林匹克竞赛中级指导教师培训班
教学大纲
中国计算机学会将定期举办全国信息学奥林匹克中级指导教师培训班，旨在提高各地中学从事信息学奥林匹克培训指导教师的整体水平，从而更好地在中学里开展计算机应用和程序设计的普及教育，为培养高水平的计算机专业人才奠定良好的基础。

培训班将依据《全国青少年信息学奥林匹克联赛（NOIP）大纲》确定教学内容。

鉴于培训时间较短（一般在一周左右），教学以传授相关知识为主，学员业务能力的提高主要依靠个人自身的努力。

通过培训，应使学员了解参与信息学竞赛必备的知识要点；掌握基本的程序设计、算法和数据结构的有关内容；经过继续努力，可以独立承担NOIP
提高组的培训工作。

培训班还将为从事信息学奥林匹克培训的一线教师提供一个直接交流的平台，交流和探讨各校的培训内容、方法、培训模式和成功的经验，以便推动全国各省市信息学奥林匹克竞赛水平的均衡发展。

二、教学内容
（1）程序设计语言概要
由于学员水平不一，使用的程序设计语言不同，有必要用一定的时间介绍培训中将要使用的程序设计语言的核心内容（条件语句、循环语句、指针、结构、函数（或过程）的定义和引用等）。

建议任课教师使用C/C++语言，也可以使用Pascal语言。

程序运行环境由任课教师参照NOIP竞赛环境选定。

建议适当介绍如何检验程序的正确性和如何设计测试数据。

（2）算法设计与数据结构基础
（2.1 ）递归回溯与基本搜索方法（递归的基本思想与实现过程，深度优先搜索，n
后问题、0-1背包问题、图的m着色、连续邮资问题、最大团问题等；近几年NOIP相关试题）。

（2.2 ）贪心算法（单源最短路径、最小生成树、哈夫曼编码等）。

（2.3 ）线性结构、图与树的相关问题（链表、堆栈、队列、串、哈希表、树的存贮结构、几类典型的二叉树、树的遍历、图的存贮结构、图的遍历、图的连通性、拓扑排序与关键路径等；近几年NOIP相关试题）
（2.4 ）分治算法（二分搜索、棋盘覆盖问题、快速排序、跳马问题）
（2.5 ）动态规划（基本思想、0-1背包问题、矩阵连乘问题、最长公共子列、最
优二叉搜索树等；近几年NOIP相关试题）
（3）历届NOIP综合性试题分析（适当选择各届联赛（提高组）的最后一题进行分析研究）
三、其他活动
（1 ）经验交流与讨论
（2 ）教学检测与评估
在培训后期进行一次上机考试，以了解教学效果和学员程序设计能力的基本情况四、具体时间安排
说明：
（1）上述时间安排不是强制性的，任课教师可就授课内容和授课顺序做适当调整。

（2）授课使用的参考书目由任课教师在培训班开课之前根据授课内容确定，并与教学
大纲一同下发给学员。

五、参考教材
[1] 中国计算机学会主编，2006全国信息学奥林匹克年鉴，河南电子音像出版社，郑州，2007年1月。

[2] 中国计算机学会主编，2007全国信息学奥林匹克年鉴，河南电子音像出版社，郑州，2008年1月。

[3] 吴文虎、李立新等，全国信息学奥林匹克联赛试题精解（2001-2003 ）（普及本），清华大学出版社，北京，2004年7月。

[4] 吴文虎等，全国信息学奥林匹克联赛培训教程（二）（普及本），清华大学出版社，北京，2006年12月重印。

⑸向期中，信息学奥林匹克教程-数据结构篇，湖南师范大学出版社，长沙，2006 年8月。

[6]李学武，中学生学C语言，清华大学出版社，北京，2004年8月。

六、证书
参照《全国信息学奥林匹克指导教师评级条例》，由中国计算机学会另行制定颁发指导教师证书的具体实施办法。

七、中级大纲编写步骤
1、由朱全民、庄燕文、曹利国分别提供大纲初稿
2、由李学武、朱全民负责对上述初稿进行初审、编定
3 、由王宏、孙辉负责共同复审和最终定稿
2008年12月1日。