算法艺术与信息学竞赛 (2010 年度畅销榜NO.231 )

本书较为系统和全面地介绍了算法学最基本的知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容，也是国际青少年信息学奥林匹克（IOI）竞赛和ACM/ICPC国际大学生程序设计竞赛中所需要的。书中分析了相当数量的问题。\r\n 本书共3章。第1章介绍算法与数据结构；第2章介绍数学知识和方法；第3章介绍计算机几何。全书内容丰富，分析透彻，启发性强，既适合读者自学，也适合于课堂讲授。\r\n 本书适用于各个层次的信息学爱好者、参赛选手、辅导老师和高等院校计算机专业的师生。本书既是信息学入门和提高的好帮手，也是一本内容丰富、新颖的资料集。

第1章 算法与数据结构\r\n 1.1 编程的灵魂——数据结构+算法=程序\r\n 1.2 基本算法\r\n 1.3 数据结构（1）——入门\r\n 1.4 数据结构（2）——拓宽和应用举例\r\n 1.5 动态规划\r\n 1.6 状态空间搜索\r\n第2章 数学方法与常见模型\r\n 2.1 代数方法和模型\r\n 2.2 数论基础\r\n 2.3 组合数学初步\r\n 2.4 图论基本知识和算法\r\n 2.5 图论基本算法\r\n第3章 计算机几何初步\r\n 3.1 位置和方向的世界——计算机几何的基本问题\r\n 3.2 多边形和多面体的相关问题\r\n 3.3 打包裹与制造合金——凸包及其应用\r\n 3.4 几种常用的特殊算法\r\n参考文献\r\n索引A 例题\r\n索引B 练习题

刘汝佳，1982年12月生。于2000年3月获得NOI2000全国青少年信息学奥林匹克竞赛一等奖第四名，进入国家集训队，并因此保送到清华大学计算机科学与技术系学习至今。2000年9月建立个人网站“信息学初学者之家（OIBH）”，该网站现已成为国内最具影响力的信息学竞赛网站之一。大一时参加ACM/ICPC国际大学生程序设计竞赛，获得2001年亚洲-上海赛区冠军和2002年世界总决赛银牌（世界第四），并担任2002年和2003年北京赛区裁判。2003年12月为止全国青少年信息学竞赛（NOI）、IOI中国国家队选拔赛、科令营、ACM/ICPC亚洲分区赛命题10余道。担任IOI2002、2003和2004三届中国国家集训队教练，并在重庆、成都、长沙、北京、天津等地授课多次，深受选手欢迎。于2002年底被中国计算机学会聘为全国青少年信息学竞赛科学委员会学生委员。

信息学(informatics)是一门新兴的学科，主要是指利用计算机及其程序设计来分析问题、解决问题的学问。随着计算机逐步深入生活，网络日趋普及，“信息革命”已经到来。信息学的地位逐步提高，青少年信息学竞赛也方兴未艾，在世界范围内受到了越来越多的重视。国际上，信息学竞赛主要分为两类：中学生的国际信息学奥林匹克和大学生的国际大学生程序设计竞赛。国际信息学奥林匹克(International Olympiad in lnformatics.IOI)始于1989年，是联合国教科文组织倡导举行的五项国际学科奥林匹克之一。中国队每届都取得了名列前茅的佳绩，所有选手全部获奖，多次总分名列第一。国际大学生程序设计竞赛(ACM International Collegiate Programming Contest, ACM/ICPC)分为地区赛和国际总决赛，中国从1996年开始参加，现有3个地区赛赛点。清华大学、上海交通大学和中山大学等学校多次进入国际总决赛。上海交通大学队还获得了2002年的世界冠军的好成绩。从大局看，竞赛不是目的，而是推动普及的手段。虽然国内在培养信息学的优秀人才方面做了很大的努力，而且成绩斐然，但仍然存在一些遗憾之处： 第一，书籍资料的缺乏性。由于信息学竞赛的普及不如其他学科竞赛，辅导教师和研究人员相对匮乏，参与写作的人员也较少，致使国内此类书籍缺乏，而好书尤其缺乏。由此造成了不少信息学爱好者求书无门。另外，一些已出版的同类书籍或艰深难懂，或教条灌输，使不少爱好者望而却步，中途放弃，以至于信息学竟成了一种“曲高和寡”的学问。然而，社会信息化和信息学普及的大势已不可逆转，所以，信息学竞赛呼唤通俗易懂又有相当学术含量的好书。 第二，地区的不平衡性。由于信息学发展的时间毕竟不算长，很多地区在中学阶段刚刚开设或者还未开设信息学课程，师资力量相对比较薄弱。而且，信息学竞赛相对于其他学科，毕竟上手比较困难，这使得每年都有相当数目的信息学爱好者因为自学难度过大而中途放弃，从而导致国内信息学教学水平存在着很明显的地区不平衡性。很多地处信息学竞赛起步较晚地区的信息学爱好者们渴望能买到既实用又便于自学的书籍。 第三，国内视野的局限性。国内不少从事信息学竞赛研究的教育工作者把大部分精力放到了国内竞赛题目的研究中，而忽视了其他国家和地区的竞赛题目和研究成果。信息学竞赛题目的风格和内容往往受到本地传统文化等因素的影响，不同地区的题目往往有较大差异，因此熟悉各个国家的出题风格和特点，训练自己各方面的解题能力是很有必要的。所以，对于中高层选手和长期从事信息学竞赛辅导的老师来说，很需要紧跟国际动向、充分介绍国外成果的好书。 总之，从以上3点可以看出，国内信息学的普及度还远远不够。本书的出版，一方面是为了弥补国内信息学便于自学的普及读物方面的不足，拉近国内信息学竞赛起步较晚地区与发达地区的差距。另一方面是为了向国内读者介绍国外最新研究成果和竞赛试题，填补这方面的空白，拉近国内和国际最新发展的距离。 本书在理论方面参考了国外的最新研究成果的论文报告，在实际运用方面大量选用了在国内研究较少的外国竞赛的优秀题目，对信息学竞赛理论研究和实践都具有一定的参考价值，同时本书也是一本难得的资料集。 本书分为3章，第1章介绍算法与数据结构。算法与数据结构是信息学中最重要的部分之一，内容多而杂，不容易从整体上把握。本章的前三节介绍复杂度分析基本理论、基础算法和基础数据结构，重在给读者一定的感性认识，然后分三个专题介绍三个重要的问题：数据结构的应用、动态规划和搜索。第2章介绍信息学中用到的数学。数学是信息学的基础，因此本书专门用一章的篇幅加以详细论述。本章容量大，理论性比第1章强，涉及到基本代数方法、初等数论、组合数学和图论等问题。第3章介绍计算几何的基础知识、基本算法以及技巧。3．1节从最基本的位置和方向问题介绍叉积和点积；3．2节过渡到多边形、多面体及其容积、重心的求取以及形内形外的判断；3．3节讨论凸包这个最基本的几何模型及其应用；3.4节介绍了几个常用的特殊算法，包括分治法、离散化和扫描法，还介绍了增量和随机增量算法。 本书包含的内容非常多，各个层次、各种需求的读者都能在本书中找到适合自己的内容。本书丰富的内容能给读者以很大的选择余地，不同难度的例题和习题中既有引导读者兴趣的入门题目，又有极富挑战性的精彩题目，习题编号前的。越多，表示作者越推荐。 本书的第1章和第2章由刘汝佳编写，第3章由黄亮编写，在成书过程中还得到了很多老师和选手的大力支持。 在第3章的写作过程中，上海交通大学ACM代表队的不少队员和教练给了作者许多帮助。 要特别感谢陆靖；感谢远在美国的陈晓敏，他与作者进行了多次富有启发意义的讨论并提供了不少国内罕见的资料；感谢吕侣、陶云峰、杨寅、严琦琦、林晨曦、龚理、田斌、张羲等同学对本书写作的支持和与作者进行的讨论。 感谢世界著名计算几何学家Joseph O'Rourke博士对作者的启发。 在前两章的写作过程中，部分IOI2002和IOI2003中国国家集训队的成员提出了不少宝贵的意见，也提供了一些资料作为帮助，他们是王知昆、张一飞、李睿、何林、毛子青、骆骥、齐鑫、赵爽、金恺、李益明、符文杰、刘才良、张宁、黄芸。 感谢俞玮和林希德，他们与作者一起进行了大量的试题翻译工作，并讨论和撰写了题目分析。 感谢在讨论中启发作者思维并教会作者不少知识的外国朋友们：瑞典的Jimmy Mardell、加拿大的Derek Kisman、波兰的Tomasz Malesinski、乌克兰的Alexandar Grushetsky、保加利亚的Petko Minkov。 感谢中国著名人像摄影家魏德运先生在本书的出版过程中所给予的帮助。 感谢北京师范大学ACM代表队的吴莹莹同学为本书的出版所给予的大力支持和帮助。 特别感谢在本书写作过程中对作者大力支持的各位老师!他们是：IOI中国队总教练吴文虎老师、ACM/ICPC清华大学代表队总教练王帆老师和邬晓钧老师、ACM/ICPC上海交通大学代表队总教练俞勇教授、ACM/ICPC德黑兰赛区总裁判Ramtin Khosravi先生、ACM/ICPC世界总决赛裁判Shahriar Manzoor先生和ACM/ICPC世界总决赛筹划指导委员会的Miguel Revilla先生。