算法艺术与信息学竞赛

所需积分/C币:50 2016-01-11 15:34:00 17.94MB PDF
3
收藏 收藏
举报

算法艺术与信息学竞赛
算法艺术与信息学竞賽 刘汝佳黄亮著 清华大学出版社 北京 内容简介 本书较为系统和全面地介绍了算法学最基本的知识。这些知识秆技巧既是高等院校“算法与数据结 构”课程的主要内容,乜是国际青少年信息学奥匹克(OI)竞赛和 ACMICPC压际大学生程字设计竞 赛中所需要的,书中分析了相当数量的问题 本书共3章。第Ⅰ章介绍算法与效据筇构;第2章介绍数学知识和方法:第3章介绍计算几何。全 内容丰富,分析透彻,启发性强,既适合读者自学,世适合于课学讲授。 本书适用于各个层次的信息学爱好者、参赛选手、辅导老师和高等院校汁算机专业的拆生,本书既 是信息学入门和提高的好帮手,也足一4内卡高、新颖的资率集 版权所有,翻印必究 本书封面貼有清华大学出版社激光防伪标签.无标签者不得销售。 臼书在版编目(C|P)数据 算法艺术与信思学亮!刘汝佳,黄著.—北京:清华大学出版杜,203 sBN7-302478009 I.算 ①刘…②黄…[l算法-白学参考瓷料I.Q24223 中因版本图书馆CP数据核字(200)第5045号 出版者:清华大学出饭社 地址:北京清华大学学研大夏 hetp:.www.lup.com.rn 部端:100084 社总机:C10-6277017 客户服务:Q10-62776969 组稿编輯:欢振旭 文稿辑:余姬陈韦凯 封面设计:钱诚 版式设计:郑軼文 印刷者:清华大学印刷厂 装订者;二河李旗店少明装订厂 发行者:新华书店总店北京行所 本:1$5×250印张:28字数:618千字 版次:204年1月第1版204年1月第次印刷 书号:ISBN7-302-780-9TP。5685 印:1~40C0 定价 〔元 计算机解题的核心是算法设计。算法设计涉及许多先絛的基碚知识,包括数据结构、 高级语言程序设计、离散数学、图论、组合数学、人工智能、计算几何等。当然还包括除 数学与信息学之外的其他学科知识,因为没有这些姸识,往往连趣目都会看不懂,这可能 也是要求参加ACM大赛的选手应该具备全面科学素养的原因之 刘汝佳、黄亮两位作者都曾在高中时参加过信息学奥林匹克竞赛活动,他们在如何用 计算机解难题方面投入过很大精力,有着比较丰富的经验。在上大学之后,义投入了大量 精力帮助训练中国队的小选手和参加ACM世界大学生程序设计人赛。他们深感这些活动 对提高学生的能力和全面素质所起的巨大作用。因此,他们利用课余时间,广泛收集各地 各类试题,并着力研究、分析与归类,想出比较好的解法,特别是总结出若干的思路和经 验写成书和大家共亨从他们开始动笔到成书期间又花了大量的心血,对一些难题的解法 也有了独到的见解。这盍书应该说是很难得的经验之谈。对个編程高手来说,借鉴别人 的经验是十分重要的。因此,我想将这本书推荐给参加IOI的中学生和参加ACM/CPC的 大学生阅读。 本书的命名也有独到之处。就我本人的教学经历来看,算法的确是艺术。艺术与科学 本来就是孪牛姊妹,不科学的东西谈不上共术。艺术给人以美的感受,而算法属于数学文 化范畴,数学的美在算法中得到了充分的体现,特别是当令数学己经进入新的机器时代, 利用计算机求解问题,需要人充分开动脑筋,解决一系列难点,解题过程本身就是一个精 益求精追求完美的过程。在这样一个过程巾,编程者在利出艰辛的努力之后,会有一种获 得成功的愉悦。正如一些数学大师所言:数学是理性的艺术,是创造性的艺术。在编程解 题的过程中,通过理性的思维和理性的实践,你一定会感受到算沄艺术的无穷魅力。·一个 颇具匠心的好算法会计你拍案叫绝,感受到它的思维艺术之美。我们许多参加过IO和 ACMACPC程序设计大赛的选手,当问起他们当年的拼搏是否艰古时,他们都说苦中有乐, 苦中有形。这可能就是感受到了这种思维艺术的魅力 科学思维能力的提高是成就事业最重要的一个因素,秀望本书对你思维能力的提高能 有很大的帮助。 清华大学计算机系教掇,博士生导师 信恩学奥林匹克中国队总教练 水力 2003年12月 言 信息学( informatics)是一门新兴的学科,主要是指利用计算机及其程序设计来分析问 题、解决问题的学问。随着计算机逐步深入生活,网络囗趋普及,“信息命”已经到来。 信息学的地位逐步提高,青少年信息学竞赛也方兴未艾,在世界范围内受到了越来越多的 重枧。国际上,信息学竞赛主要分为两类:中学生的国际信息学奥林匹克和大学生的国际 大学生程序设计竞赛。国际信息学奥林匹克( International Olympiad in Informatics.O)始 于1989年,是联合国教科文组织倡导举行的五项国际学科奥林匹克之一。中国队每届都取 得了名列前茅的佳绩,萨有选手全部获奖,多次总分名列笫·。国际大学生程序设计竞窭 ( ACM Intemational Collegiate Programming Contest,ACM/ICPC分为地区篑和国际总决 赛,中国从199年开始参加,现有3个地区赛赛点清华大学、上海交通大学和中山大学 等学校多次进入国际总决赛。上海交通大学队还扶得了2002年的界冠军的好成绩。从大 局看,竞赛不是目的,而是推动普及的手段。虽然国内在培养信息学的优秀大才方面做了 很大的努力,而且成绩斐然,但仍然存在一些遗憾之处: 第一,书籍资料的缺乏性。由于信息学竞赛的普及不如其他学科竞赛,辅导教师和研 究人员相对匮乏,参与写作的人员也较少,致使国内此类书籍缺乏,而好书尤其乏。由 此造成了不少信息学爱好者求书无门另外,一些已出版的回类书籍或艰深难懂,或教条 灌输,使天少爱好者望而却步,中途放弃,以至于信息学竞成了一种“曲高和寡”的学问。 然而,社会信息化和信息学普及的大势已不可逆转,所以,信息学竞赛呼唤通俗易懂叉有 框当学术含量的好书 第二,地区的不平衡性。由于信息学发展的时间毕竞不算长,很多地区在中学阶段刚 刚开设或者还未开设信息学课程,师资力量相对比较淖弱。而且,信息学竞赛相对于其他 学科,毕竟上手比较困难,这使得每年都有相当数目的信息学爱好者因为自学难度过大而 中途放弃,从而导致国内信息学教学水平存在着很明显的地区不平衡性。很多地处信息学 竞赛起步较晚地区的信息学爱好者们渴望能买到既实用又使于自学的书籍。 第三,国内视野的局限性。国内不少从事信息学竞赛研究的教育工作者把大部分精力 放到了国内竞赛题目的研究中,而忽视了其他国家和地区的克赛题目和研究成果。信息学 竞赛题日的风格和内容往往受到本地传统文化等因紊的影响,不同地区的题目往往有较大 差异,因此熟悉各个国家的出题风格和特点,训练自己各方面的解题能力是很有必要的。 所以,对于中高层选手和长期从事信息学竞赛辅导的老师来说,很需要紧跟国际动向、充 分介绍国外成果的好书 总之,从以上3点可以看出.国内信息学的普及度还递远不够。本书的出版,一方面 足为了弥补国内信息学便于自学的普及读物方面的不是,拉近国内信息学竞赛起步较晚地 算法艺术与信总学竞赛 区与发达地区的差距。另灬方哇是为了向国内读者介绍国外最新研究成果和竞赛试题,填 补这面的空白,拉近国内利国际最新发展的距离。 本书在理论方面参考国外的最新研究成果的论文报告,在实际运用方面大量选用了 在国内研究较少的外国竞赛的优秀题目,对信息学竞赛理论研究和实践都具有一定的参考 价值,同时本书也是一本难得的资料集。 本书分为3章,第1章介纲算法与数据结构。算法与数据结构是信息学中最重要的部 分之一,内容多而杂,不容易从整体上把握。本章的前三节介绍复杂度分析基本理论、基 础算法和基础数据结构,重在给读者定的感性认识,然后分三个专题介绍个重要的问 题:数据结构的应用、动态规划和搜索。第2章介绍信息学中用到的数学。数学是信息学 的基础,囚此本书专门用一章的篇幅加以详细论述。本章容最大,瑮论性比第1章强,涉 及到基本代数方法、初等数论、组合数学和图论等问题。第3章介绍计算几何的基础知识、 基本算法以及技巧。3.1节从最基本的位置和方向问题介绍叉积和点积;32节过渡到多边 形、多面仁及其容积、重心的求取以及形内形外的判断;3.3节讨论凸包这个最基本的几何 模型及其应用:34节介绍了几个常用的特殊算法,包插分治法、离散化和扫描法,还介绍 了增蠶和随机增胤算法 本书包含的内容非常多,各个层次、各种需求的读者都能在本书中找到逅合白己的内 容。本书丰富的内容能给读者以很大的选择余地,不同难度的例题和习题中既有引导读者 兴趣的入门题目,又有极富挑战性的精彩题目,习题编号前的*越多,表示作者越推荐 本书的第t章和第2章由刘汝住编写,第3由黄亮编写,在成书过程中还得到了很 多老师和选于的大力支持。 在第3章的写作过程中,上海交通大学ACM代表队的不少队员和教练给了作者许多 帮助 要特别感谢陆靖;感谢远在美国的陈晓敏,他与作者进行了多次富有启发意义的讨论 并提供了不少国内罕见的资料;感谢吕倡、陶云峰、杨寅、严琦琦、林晨曦、龚蓮、田斌、 张羲等同学对本书写作的支持和与作者进行的讨论。 感谢世界著名计算几何学家 Joseph O Rourke博士对作者的启发。 在前两章的写作过程中,部分IOI2002和[OI2003中国黑家集训队的成吴提出了不少 宝贵的意见,也提供了一些资料作为帮助,他们是平知昆、张飞、李睿、何林、毛子青 骆曠、齐鑫、赵爽、金恺、李益明、符文杰、刘才良、张宁、黄芸。 感谢俞玮和林希德,他们与作者一起进行了大量的试题翻译工作,并讨论和撰写了题 日分析 感谢在讨论中启发伫者思维并教会作者不少知识的外国朋友们:瑞典的Jmy del加拿大的 Derek Kisman波兰的 omasz malesinski乌克兰的 Alexandar Grushetsky 保加利亚的 Petko minkoy 感谢中国著名人像摄影家魏德运先生在木书的出版过程中所给予的帮助。 感谢北京师范大学ACM代表队的吴莹莹同学为本书的出版所给予的大力支持利帮助。 特别感谢在本书写作过程中对作者太力支持的各位老师!他们是:IO中国队总教练吴 文虎老师、 ACMUICPC清华大学代表队总教练王帆老师和邬晓钧老炳、 ACMICPC上海交 递大学代表队总教练俞勇教授、ACM/ICPC德黑兰赛区总裁判 Ramtin khosray先生 ACMICPC世界总决赛裁判 Shahar manzoor先生和 ACMICPO世界总决赛筹划指导委员 会的 Miguel Revilla先生。 作者 2003年12月2冒 如何阅读本书 欢逛大家阅读本书!为了更好地发挥本书的作用,我们建议在阅读本书之前先熟悉本 书的内容概况和特点,花一些时间来认真看看“如何阅读本书”部分。 本书的读者对象 本书的读者大致分为四类,我们分别给出不同的建议,供参考。 第一类,中学倍息学竞凝选手 中学生的竞分为不同的层次。从纯普及的分区联赛,到普及兼选拔的NO全国青少 年信息学奥林匹克竞赛,纯选拔性质的IO中国国家队选拔赛CTSC和纯竞赛性质的Ir 国际青少年信息学竞赛,需要掌握的内容和难度都有很大的变化。分区联赛的选手应当学 习一门程序设计语言并算握到相当熟练的程度,然后学习本书中比较重要而易懂的内容 NOI选手应当学会书中除了部分高难度的例趣和带*内容之外的其他内容,而国家集训队 员应当尽凰掌握书中所有内容并完成大部分习题。极少数习题只是提供绘有兴趣的读者过 行研究,而不用强自己掌握。由于中学生竞赛对算法设计的要求很高,所以这类读者 应该特别注意体会书中例题并完成习题。 第二类, ACMICPC大学生程序设计竞赛选手 大学生竞赛的特点和中学生不一样。 ACMICPo中编程速度和正确性显得尤其重要, 而对算法设计的要求从整体上比中学生竞赛低了很多。针对比赛的这个特点,建议这一类 读者重点阅读1.3节、21节、22节、23节的全部内容以及1.4节、1.5节、1.6节、2.5节 中的理论部分和比较简单的例题,而其他内容只需要学习基础内容和 ACMICPO,UVA Problem archive和 Ural state Proble Archive中的例题,其中难度过大的题目可略过国 内ACM竟正处在发展阶段,有一大批选于刚刚接触到竞赛,经验还不够。建议这些选 手先浏览全书,然后先阅读理论部分,龇过一些思路巧妙或者难度很大的题日,ACM竟赛 中,速度和正确性是非常重要的,因此强烈建议大家把书中大部分的程序都亲自编写一下, 并加入到自己的程序库中 第三类,竞賽辅导教师和教练 敦师和选手不一样,他们往往有比较充足的时间且不月花很多精力来训练自己的编程 能力与保持状态,因此可以更从容地阅读本书。建议各位老师能通读全书,不断找出自己 最感兴趣的部分深入阅读,用这种方式逐渐了解本书的所有肉容。对于教师来说,了解仝 貌是非常重要的,因为这可以极大地帮助学生沿蓍正确的路子学习和训练。 算法艺术与信息学竞赛 第四类,计算机编程爱好者和其他读者 兴趣是最好的老师。这类读者可以随意选择感兴越的内容进行学习,如L.2节、I,3 节、25屿等节的题目都很有趣。另外,由于读者可以忽略大部分的证明和复杂度分析,而 重点体会书中涵的思想,这样的学习必将是有趣和吸引人的。 本书的目标和特点 学习信息学主要有两个层次的要求:理解和掌握。本书尽量让读者多理解一些难于理 解的内容,著想熟练地掌握,读者必须另外下很大的功夫,配合阅读其他书籍并做大量的 练习,进行一些实践。限于篇幅,很多理论和题目的细节木书都无暇顾及。这屐不大影响 读者理解内容的精髓,但是当读者在细究·些问题〈例如-些术语的准确定义、证明、伪 代码和一些实现细等)时会发现书中并未提到。其实,在多数情况下,这些内容可以在 同类书中学到,也可在作者为本书专门设订的主页上找到丰富的学习资料。突出特色,启 发思维才是本书的目标 本书的特点有三个。了解了这些特点有助于读者在学习的过程中有意识地体会作者的 另一个用意”,从而最大限度地掌握内容。 第一个特点是启发性。这也是本书相对比国内已出版的同类书籍最大的特色,与传统 此类书籍“填鸭式”灌输算法不同,本书力我教科书式的死板讲解,力争引导读者进行创 造性的思维,点拨关键思路,使读者在探索中自然领悟算法的精髓,并为其优美所吸引 激发浓厚的兴趣。传统书籍讲新算法时,往往作为一个全新的事物引入,而不是转化为已 学的知识,也不讲与其他算法的联系,导致学生认为倍息学千头万绪,琐碎复杂,而始终 不得其精髓,更个用说“融会贯通”。其实算法都是相通的,万变不离其宗。故本书讲解 时,大多先由一个有趣的实例引出,引导读者从几个已学的方向自行探索,逐步挞弃错误 的方向,改为正确的方向.循循善诱,一步步把读者引向正确的算法,让读者觉得.新算 法不过就是从老算法演化而来,并不深奥难懂。因此,建议读者在阅读时特别注意各个知 识点是怎样被引入的。一个知识点引用得越曲折,说明这个知识点越是重要,越有可学之 处。总之,本书能启发读者进行创造性思维,自然体会算法和知识的芷确性、优美性、深 刻性、广泛性和统一性,不仅能化为已用,还能有所创新。 第二个特点是信息量大。本书在描述算法时尽可能简洁,突出主要矛盾。书中涉及的 源程序在本书网站上都有,而书上的篇幅尽可能多的讨论算法的精髓、与其他算法的异同 比较时空复杂度优劣、适用条件、互相转化等,大部分内容都是同类书籍中很难找到的。 读者也许会抱怨某些知识讲得不够深,不够细,但实际上这些有限的篇幅被用来讲解更为 有用的知识了。我们用网蚱来保证读者可以有条件学习到这些知识.而腾出更多的篇幅来 介绍本书特有的内容。倍息学竟赛是一种讲究创新的比赛,木书在讲解知识之余十分注重 茧励读者思维创新,在介绍大量知识和技巧的同时给读者留下广阔的思维空间。书中某些 问题只是轻描淡写地提了一句,但是为读者提供了很大的思考空间,读者可以独立研究

...展开详情
试读 127P 算法艺术与信息学竞赛
立即下载 身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 签到新秀

  • 分享王者

关注 私信
上传资源赚钱or赚积分
最新推荐
算法艺术与信息学竞赛 50积分/C币 立即下载
1/127
算法艺术与信息学竞赛第1页
算法艺术与信息学竞赛第2页
算法艺术与信息学竞赛第3页
算法艺术与信息学竞赛第4页
算法艺术与信息学竞赛第5页
算法艺术与信息学竞赛第6页
算法艺术与信息学竞赛第7页
算法艺术与信息学竞赛第8页
算法艺术与信息学竞赛第9页
算法艺术与信息学竞赛第10页
算法艺术与信息学竞赛第11页
算法艺术与信息学竞赛第12页
算法艺术与信息学竞赛第13页
算法艺术与信息学竞赛第14页
算法艺术与信息学竞赛第15页
算法艺术与信息学竞赛第16页
算法艺术与信息学竞赛第17页
算法艺术与信息学竞赛第18页
算法艺术与信息学竞赛第19页
算法艺术与信息学竞赛第20页

试读结束, 可继续阅读

50积分/C币 立即下载