acm介绍.ppt

上海市控江中学王建德
全国奥林匹克信息学联赛
最近三年
全国分区联赛复赛
虽然最近三年全国奥林匹克信息学复赛中含许多可“一题多解”的试题,但如果按照较优算法标准分类的话,大致可分为
题型
题型
与课内知识和编程基础相关
自由落体、级数求和、乒乓球、麦森数、不高兴的津津、花生采摘、津津的储蓄计划
构造法
均分纸牌、传染病控制、火星人
数据结构
字符近似查找、合并果子(堆排序)、栈、 FBI树(二叉树)、神经网络(图)
枚举法
虫食算、侦探推理
回溯法
选数、字串变换
动态程序设计方法
过河卒、数字游戏、加分二叉树、合唱队形
几何计算
矩形覆盖
特点
1、凸现信息学知识和学科知识整合的趋势。为了考核学生运用学科知识的能力,激发学生的创造力,2002年全国奥林匹克信息联赛(NOIP)中学科类的试题增加,并且首次出现了计算几何类的试题(矩形覆盖)。这说明信息学与学科的依赖关系日益凸现,学科基础好、尤其是数学素质好的人虽然不一定会编程,但希望学习编程的人愈来愈多;编程解题能力强的人势必有数学的潜质和爱好,他们中愈来愈多的人也希望深造数学。各门学科的交融和整合是奥林匹克信息学联赛活动发展的一个大趋势(有专家提议,数学教材讲算法,信息科技教材讲语言,上海的信息科技教材出现真值表(初中)和c语言(高中))。
2、“构造法”或贪心策略类试题的引入,使得算法知识的不确定性和不稳定性增加。这正体现了科学的本质—知识是不断推陈出新的。
3、试题的综合性增加,并不一定随知识的分类而发生变化,有时几乎找不到一个单一的经典算法(字串变换——回溯法中有字符串处理),也找不到一个纯粹的数据结构问题(级数求和——需要为表达式的计算结果设计合适的数据类型),关键是你从哪个角度去分析,也就是说能不能综合所学的知识,应用自如地解决问题。选手的综合素质愈高,得胜的机率愈大;
4、经常面对着不知道算法的试题,面对着谁都不知如何处置的情境(经常出现许多选手在一题中得0分、优秀选手表现失常的情况),因此必须使学生正确地理解问题、深入问题的空间并形成解决问题的意识、习惯和能力。能不能创造性地应答没有遇到过的挑战,成为培训的基本要求和目标。
1、培养问题意识和问题能力。创造始于问题。“有了问题才会思考,有了思考才有解决问题的方法,才有找到独立思路的可能(陶行知)”。有问题虽然不一定有创造,但没有问题一定没有创造(想一想当前的解法有没有缺陷,有没有更好的算法,它与哪些问题有联系,与哪些知识相关联,还可以拓延出哪些问题,要解决这些问题还需要哪些知识);
启示
2、处理好前沿性与基础性、直线培训和散点培训、循序渐进与跳跃式的矛盾。如果恪守按部就班的培训程序,不谋求跳跃式学习,将离全国和国际奥林匹克信息学活动的前沿、离世界程序设计知识的前沿愈来愈远。因此在进行基础课程学习的同时,必须有追逐前沿的选择性学习。这里,有时候心理的障碍比科学上的障碍更难跨越,敢不敢的问题比能不能的问题更突出。其实在学习中或多或少地都有必要的跳跃,不少人还能够实现比较大的跳跃( 爱笛生小学三年级退学、)
学生必须学会从浩如烟海的信息中选择最有价值的知识,构建个性化(符合自己能力结构和兴趣结构)和竞争需要的知识结构
培训内容要有选择性,因为除了出题者,谁也说不清楚在未来竞赛中究竟什么知识是必要的(对基础的理解是主观的选择。例如中国、美国和俄罗斯的理科教材大不相同,有的同年级同学科的教材相差三分之二),因此不可能把所有重要的东西都选择好了给学生,而是应该将直线培训与散点培训相结合,选择部分重要的东西交给学生,让他们自己去探索若干知识点之间的联系,补充自己认为需要补充的知识。
3、参与活动的学生应由竞争关系和独立关系(你做你的,我干我的,程序和算法互相保密,彼此津津乐道于对方的失败和自己的成功)转向合作学习的关系(通过研讨算法、集中编程、互测数据等互相合作的方式完成学习任务)
学生的心理调适:
我掌握的知识仅不过是沧海一粟(进取心);
固守错误的概念比一无所知更可怕(明智);
三人之行必有我师(谦虚);
知识生产社会化条件下人的基本素质之一是合作精神(现在的重大科学发明需要成百上千科学家进行长期甚至跨国的合作,例如制作windows,人类基因工程)(现代意识);
前提条件:水平相当的同质成员或各有所长(包括数学知识、编程能力和思维方式等解题所需的各种因素)的异质成员是开展合作学习的组织基础;
合作学习的效应:
集思广益容易出好的算法;
群体设计的测试数据相对全面;
在群体活动中能比较客观的反映自己能力情况;
每个学生在付出与给予中可提高合作精神和编程能力,成功者往往是那些相容性好、乐于帮助他人,并且善于取他人之长的学生(符文杰、张一