冬令营讲义王建德提要

1、2003 年冬令营讲义2002 年虽然 2001 年信息学活动的简析信息学竞赛中含许多可“一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为2002 年竞赛概述算法知识分布特点：1、凸现信息学知识和数学知识整合的趋势。为了考核学生的数学能力，激发学生的创造力，2002 年信息竞赛(NOI)、IOI 组队赛和 IOI，数论(荒岛野人)、组合分析(机器人 M 号)、图论类(玩具兵)的试题增加，并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与数学的依赖关系日益凸算法分区联赛赛组队赛物理题落体字符串处理字符近似查找并查集与路径压缩模拟策略灭鼠行动回溯法购房计划数算选数、字串变换动态

2、程序设计方法级数求和、 均分纸牌贪吃的九头龙过河卒二分图的匹配玩具兵“构造法”解题调皮的小孩、新俄罗斯方块丹奇方块贪心法月亮森林数论（最大公约数）荒岛野人组合分析（函数）机器人 M 号几何计算（点和矩形的关系）矩形覆盖现，数学素质好的人虽然不一定会编程，但希望学习编程的人愈来愈多；编程解题能力强的人势必有数学的潜质和，他们中愈来愈多的人也希望深造数学。两门学科的交融和整合是信息学活动发展的一个大趋势（有提议，数学讲算法，信息科技讲语言，的信息科技出现真值表（初中）和 c 语言（高中）。2、“构造法”(调皮的小孩、新俄罗斯方块、丹奇方块 )或贪心策略类试题（月亮森林）的引入，使得算法知识的不确定

3、性和不稳定性增加。这正体现了科学的本质知识是不断推陈出新的。3、试题的综合性增加，并不一定随知识的分类而发生变化，有时几乎找不到一个单一的经典算法(玩具兵通过最短路径构造二分图)，也找不到一个纯粹的数据结构问题（要求计算并查集中元素的相对位置），关键是你从哪个角度去分析，也就是说能不能综合所学的知识，应用自如地解决问题。选手的综合素质愈高，得胜的机率愈大； ?4、经常面对着不知道算法的试题，面对着谁都不知如何处置的情境（经常出现许多选手在一题中得 0 分、优秀选手表现失常的情况），因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、和能力。能不能创造性地应答没有遇到过的，成为培训

4、的基本要求和目标。启 示：1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考，有了思考才有解决问题的方法，才有找到独立思路的可能（）”。有问题虽然不一定有创造，但没有问题一定没有创造（想当前的解法有没有缺陷，有没有更好的算法，它与哪些问题有联系，与哪些知识相关联，还可以出哪些问题，要解决这些问题还需要哪些知识）；?2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的。如果恪守按部就班的培训程序，不谋求跳跃式学习，将离和国际奥信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时，必须有追逐前沿的选择性学习。这里，有时候心理的障碍比科学上的更难，敢

5、不敢比能不能更突出。其实在学习中或多或少地都有必要的跳跃，不少人还能够实现比较大的跳跃（ 2002 年noi 中的函数、冬令营营员讲的 polya 定理、博弈原理和遗传算法，小学三年级退学、.大学三年级退学）学生必须学会从浩如烟海的信息中选择最有价值的知识，构建个性化（符合自己能力结构和结构）和竞争需要的知识结构培训内容要有选择性，因为除了出题者，谁也说不清楚在未来竞赛中究竟什么知识是必要的（对基础的理解是的选择。例如中国、和俄罗斯的理科大不相同，有的同年级同学科的相差三分之二），因此不可能把所有重要的东西都选择好了给学生，而是应该将直线培训与散点培训相结合，选择部分重要的东西交给学生，让他们

6、自己去探索若干知识点之间的联系，补充自己认为需要补充的知识。3、参与活动的学生应由竞争关系和独立关系（你做你的，程序和算法互相，彼此津津乐道于对方和自己的成功）转向合作学习的关系（通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务）前提条件：水平相当的同质成员或各有（包括数学知识、编程能力和思维方式等解题所需的各种）的异质成员是开展合作学习的组织基础；学生的心理调适：我掌握的知识仅不过是沧海一粟(进取心)；固守错误的概念比一无所知更可怕（明智）；三人之行必有我师（谦虚）；知识生产社会化条件下人的基本素质之一是合作精神（现在的科学发明需要成百上千科学家进行长期甚至的合作，例如制作 windows，人类基因工程）（现代意识）；合作学习的效应：集思广益容易出好的算法；群体设计的测试数据相对全面；在群体活动中能比较客观的反映自己能力情况；每个学生在付出与给予中可提高合作精神和编程能力，成功者往往是那些相容性好、 乐于帮助他人，并且取