算法艺术和信息学竞赛

所需积分/C币:9 2015-12-14 11:53:58 17.96MB PDF
2
收藏 收藏
举报

本书即为信息学界著名的两本“黑书”之一(另一本为吴文虎、王建德编著的实用算法的分析与程序设计,这本书现在已经在市场是接近绝版,但是在网上能找到电子书·如果想找到替代品的话可以找另外一本由吴文虎教授以及王建德先生编著的黑书《新编实用算法的分析与程序设计》,由北京邮电出版社2008年出版,此书与原版表面内容相差较大,但实质没有太大差别)。
内容简介 本书较为系统和全面地介绍了算法学最基本的知识。这些知识秆技巧既是高等院校“算法与数据结 构”课程的主要内容,乜是国际青少年信息学奥匹克(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冒

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

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

试读结束, 可继续阅读

9积分/C币 立即下载