算法艺术与信息学竞赛

2004年清华大学出版社出版的图书

《算法艺术与信息学竞赛》是2004年清华大学出版社出版的图书，作者是刘汝佳、黄亮。

内容简介

本书即为信息学界著名的两本“黑书”之一（另一本为吴文虎、王建德编著的实用算法的分析与程序设计，这本书现在已经在市场是接近绝版，但是在网上能找到电子书·如果想找到替代品的话可以找另外一本由吴文虎教授以及王建德先生编著的黑书《新编实用算法的分析与程序设计》，由北京邮电出版社2008年出版，此书与原版表面内容相差较大，但实质没有太大差别）。

图书简介

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

本书主页见扩展阅读.

图书目录

第1章算法与数据结构 1

1.1 编程的灵魂——数据结构+算法=程序 1

1.2 基本算法 8

1.2.1 枚举 8

1.2.2 贪心法 13

1.2.3 递归与分治法 19

1.2.4 递推 28

1.3 数据结构（1）——入门 34

1.3.1 栈和队列 35

1.3.2 串 44

1.3.3 树和二叉树 50

1.3.4 图及其基本算法 59

1.3.5 排序与检索基本算法 67

1.4 数据结构（2）——拓宽和应用举例 79

1.4.1 并查集 80

1.4.2 堆及其变种 88

1.4.3 字典的两种实现方式：哈希表、二叉搜索树 96

1.4.4 两个特殊树结构：线段树和Trie 107

1.5 动态规划 113

1.5.1 动态规划的两种动机 113

1.5.2 常见模型的分析 122

1.5.3 若干经典问题和常见优化方法 149

1.6 状态空间搜索 159

1.6.1 状态空间 159

1.6.2 盲目搜索算法 160

1.6.3 启发式搜索算法 168

1.6.4 博弈问题算法 175

1.6.5 剪枝 180

*1.6.6 专题：路径寻找问题 188

*1.6.7 约束满足问题 192

第2章数学方法与常见模型 203

2.1 代数方法和模型 203

2.2 数论基础 216

2.2.1 素数和整除问题 216

2.2.2 进位制 224

2.2.3 同余模算术 228

2.3 组合数学初步 239

2.3.1 鸽笼原理和Ramsey定理 239

2.3.2 排列组合和容斥原理 240

2.3.3 群论与Pólya定理 245

2.3.4 递推关系与生成函数 254

2.3.5 离散变换与反演 262

2.4 图论基本知识和算法 268

2.4.1 基本概念和定理 268

2.4.2 可行遍性问题简介 272

2.4.3 平面图 280

2.4.4 图的基本算法与应用举例 285

2.5 图论基本算法 299

2.5.1 生成树问题 299

2.5.2 最短路问题 304

2.5.3 网络流问题 315

2.5.4 二分图相关问题和模型 329

第3章计算几何初步 346

3.1 位置和方向的世界——计算几何的基本问题 346

3.1.1 从相交到左右——基本问题的转化 348

3.1.2 左右和前后——叉积和点积 350

3.2 多边形和多面体的相关问题 361

3.2.1 卫兵问题——多边形和多面体的概念 361

3.2.2 求多边形、多面体的容积和重心；高维情形 367

3.2.3 判点在形内形外形上；多面体的情形 378

3.3 打包裹与制造合金——凸包及其应用 387

3.3.1 凸包的普遍性和广泛应用性；凸的定义与优美性质 387

3.3.2 凸包的实现 391

3.3.3 凸包算法正确性与时间效率 396

3.3.4 应用举例 401

3.3.5 凸多边形的深入讨论 405

3.4 几种常用的特殊算法 410

3.4.1 蛋糕被切成几块？——离散化法 410

3.4.2 切蛋糕的周长和面积——扫除法 412

3.4.3 凸包与快速排序——分治法 414

3.4.4 凸包的又一种求法——增量法 416

3.4.5 专题——随机增量算法 417

参考文献 424

作者简介

刘汝佳

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

黄亮

自初中起跟随著名“金牌教练”王建德学习程序设计和算法。初三时代表上海代参加NOI’96全国青少年信息学奥林匹克竞赛，获三等奖（总第19名）。高三时取得信息学全国联赛一等奖和数学全国联赛三等奖。进入上海交大后，参加ACM/ICPC 国际大学生程序设计竞赛，代表交大一队于2000年获上海赛区第四名。2002年获全国数学建模竞赛全国一等奖。本科期间在国际学术会议上发表论文3篇，参加了在台湾举行的计算语言学界最高会议COLING’02。2003年本科毕业时被美国哥伦比亚大学、宾夕法尼亚大学和加拿大多伦多大学同时以全额奖学金录取。2003年秋起在宾夕法尼亚大学计算机与信息科学系攻读博士学位。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省