信息学奥林匹克竞赛指导

章节摘录

　　显然，图1．2．1中不能求出s至t的关键路径，但这是否意味问题无解呢？不一定。实际上这是试题设计者巧设的一个误区，以此告诫选手，寻求正确算法应从试题给出的条件和目标出发，而不是生搬硬套“本本”上的算法。　　2．每个项目最早开始时间的计算方法　　正确的算法应该是，在项目间制约关系图的基础上，增设一个人度为0的源点s，表示工程开始。s向每一个顶点引出一条权为O的有向弧。为了便于判别图中可能出现的权和非零的有向环，除s外的每一个顶点连一条权为O的自反弧。例如上述例子对应的新图G’见图1．2．2。　　由于在新图G中的每个项目可以独立并行的进行，所以项目i[1≤i≤n（项目数）]的最早开始时间是从源点s到顶点i的最长路径的长度，即最长路径上各活动持续时间之和。显然在图1．2．2中，项目1的最早开始时间一0，项目2的最早开始时间=O。　　如果在图中出现权和大于零的有向环，意味着有向环上的项目应以自己为先决条件，其最早开始时间的计算沿这个有向环死循环下去，势必得出一个无穷大的值，显然这是荒谬的。因此，一旦在计算过程中发现路径长度大于零的有向环，则算法应以无解而告终。

前言

　　国际信息学奥林匹克（International 0lympiad in Informatics，IOI）从1989年到1999年，11年赛事的健康发展得益于联合国教科文组织（UNESCO）为这项赛事所做的准确定位：通过竞赛形式对有才华的青少年起到激励作用，促其能力得以发展；让青少年彼此建立联系，推动经验交流，给学校这一类课程增加活力；建立起教育工作者与专家档次上的国际联系，推进学术思想的交流。概括起来说，就是启迪思路，激励英才，发展学科，促进交流。　　学科奥林匹克是智力与能力的竞赛，注重考查全面素质与创造能力。从这个意义上讲，信息学奥林匹克活动是素质教育的一个大课堂。在我国，每年国家集训队都要将“怎样做人，怎样做事，怎样求知和怎样健体”的指导思想纳入培训计划。这11年中国队共派出参赛选手43人次，累计获金牌23块、银牌11块、铜牌9块，届届名列前茅，正是因为坚持了全面素质教育的指导思想，把造就高素质有创造精神的人才作为活动的定位目标。　　回顾11年的竞赛可以看出，参加高手云集的这种世界大赛是有相当难度的，第一，没有大纲，赛题范围没有界定，谁也无法去猜测每年的主办国会出什么类型的难题；第二，计算机科学与技术发展很快，层出不穷的新思路和新成果会反映到试题中来；第三，所要解决的试题往往涉及图论、组合数学、人工智能等大学开设的课程知识；第四，比较短的给定解题时间与刁难的测试数据让选手必须拿出高超和精巧的解法，无论在时间上还是空间上都是优化的解法才能取得高分。有许多赛题没有固定的现成的解法，选手要在比赛现场凭借实力，理出思路，构建数学模型，写出算法，编出程序，运行并验证整个构思是否正确，出解的时间是否能达到题目的要求，等等。可以看出，在这一过程中最重要的是要有创造能力。为激发创新精神，培养创造能力，就需要树立新的教育观念和教学方法，还要利用现代化的教学手段。引导学生学用电脑，在使用中帮助开发人脑，这可能是信息学奥林匹克活动的最重要的一个特点。我认为在这项活动中应该培养学生的四种能力：自学能力；实践动手能力；创新能力；上网获取信息，并能区分有用信息和无用信息的能力。这样做的结果使许多选手不但有能力在世界赛场上拿金牌，也有能力在学校的学习中名列前茅。

书籍目录

一，第九届国际奥林匹克信息学竞赛中国组队赛试题分析
二，第十四届全国奥林匹克信息学竞赛试题分析
三，第九届国际奥林匹克信息学竞赛试题分析
四，第十届国际奥林匹克信息学中国组队赛试题分析
五，第十五届全国奥林匹克信息学竞赛试题分析
六，第十届国际奥林匹克信息学竞赛试题分析

作者简介

《信息学奥林匹克竞赛指导:97-98竞赛试题解析》由清华大学出版社出版。

图书封面

---

 信息学奥林匹克竞赛指导下载

---