内容简介 · · · · · ·
《算法艺术与信息学竞赛》较为系统和全面地介绍了算法学最基本的知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容,也是国际青少年信息学奥林匹克(IOI)竞赛和ACM/ICPC国际大学生程序设计竞赛中所需要的。书中分析了相当数量的问题。
本书共3章。第1章介绍算法与数据结构;第2章介绍数学知识和方法;第3章介绍计算机几何。全书内容丰富,分析透彻,启发性强,既适合读者自学,也适合于课堂讲授。
本书适用于各个层次的信息学爱好者、参赛选手、辅导老师和高等院校计算机专业的师生。本书既是信息学入门和提高的好帮手,也是一本内容丰富、新颖的资料集。
目录 · · · · · ·
第1章算法与数据结构
1.1编程的灵魂--数据结构+算法=程序
1.2基本算法
1.2.1枚举
1.2.2贪心法
1.2.3递归与分治法
1.2.4递推
1.3数据结构(1)--入门
1.3.1栈和队列
1.3.2串
1.3.3树和二叉树
1.3.4力瘃其基本算法
1.3.5排序与检索基本算法
1.4数据结构(2)--拓宽和应用举例
1.4.1并查集
1.4.2堆及其变种
1.4.3字典的两种实现方式:哈希表.二叉搜索树
1.4.4两个特殊树结构:线段树和Trie
1.5动态规划
1.5.1动态规划的两种动机
1.5.2常见模型的分析
1.5.3若干经典问题和常见优化方法
1.6状态空间搜索
1.6.1状态空间
1.6.2盲目搜索算法
1.6.3启发式搜索算法
1.6.4博弈问题算法
1.6.5剪枝
*1.6.6专题:路径寻找问题
*1.6.7约束满足问题
第2章数学方法与常见模型
2.1代数方法和模型
2.2数论基础
2.2.1素数和整除问题
2.2.2进位制
2.2.3同余模算术
2.3组合数学初步
2.3.1鸽笼原理和Ramsey定理
2.3.2排列组合和容斥原理
2.3.3群论与Polya定理
2.3.4递推关系与生成函数
2.3.5离散变换与反演
2.4图论基本知识和算法
2.4.1基本概念和定理
2.4.2可行遍性问题简介
2.4.3平面图
2.4.4图的基本算法与应用举例
2.5图论基本算法
2.5.1生成树问题
2.5.2最短路问题
2.5.3网络流问题
2.5.4二分图相关问题和模型
第3章计算机几何初步
3.1位置和方向的世界--计算机几何的基本问题
3.1.1从相交到左右--基本问题的转化
3.1.2左右和前后--叉积和点积
3.2多边形和多面体的相关问题
3.2.1卫兵问题--多边形和多面体的概念
3.2.2求多边形.多面体的容积和重心,高维情形
3.2.3判点在形内形外形上,多面体的情形
3.3打包裹与制造合金--凸包及其应用
3.3.1凸包的普遍性和广泛应用性,凸的定义与优美性质
3.3.2凸包的实现
3.3.3凸包算法正确性与时间效率
3.3.4应用举例
3.3.5凸多边形的深入讨论
3.4几种常用的特殊算法
3.4.1蛋糕被切成几块?--离散化法
3.4.2切蛋糕的周长和面积--扫除法
3.4.3凸包与快速排序--分治法
3.4.4凸包的又一种求法--增量法
3.4.5专题--随机增量算法
参考文献
· · · · · · (收起)
喜欢读"算法艺术与信息学竞赛"的人也喜欢的电子书 · · · · · ·
喜欢读"算法艺术与信息学竞赛"的人也喜欢 · · · · · ·
算法艺术与信息学竞赛的话题 · · · · · · ( 全部 条 )



算法艺术与信息学竞赛的书评 · · · · · · ( 全部 3 条 )

内容很不错,讲解的言简意赅,直达本质

> 更多书评 3篇
读书笔记 · · · · · ·
我来写笔记-
康桥语冰 (夜深忽梦少年事)
个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟 对于编程能力的提高也没有想象中的高 看得出来作者都是竞赛和学术的大牛型人物,但是多数地方没有讲的非常清楚。(个人智商低,理解起来有些费力呀~) 本书作为题库,还是非常不错的 另外。。。。。。排版太糟糕了2011-08-31 09:43
-
1.1 编程的灵魂——数据结构+算法 = 程序 算法(algorithm)就是解决问题的方法或者过程。 数据结构(data structure)是数据的计算机表示和相应的一组操作。 时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。 程序一: fact = 1; for (int i = 1;i <= n; i++) fact *= i; 共执行了n个基本操作; 程序二: sum = 0; for (int i = 1; i <... (1回应)
2011-02-01 13:42 1人喜欢
1.1 编程的灵魂——数据结构+算法 = 程序 算法(algorithm)就是解决问题的方法或者过程。 数据结构(data structure)是数据的计算机表示和相应的一组操作。 时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。 程序一:
fact = 1; for (int i = 1;i <= n; i++) fact *= i;
共执行了n个基本操作; 程序二:
sum = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum += a[i][j];
执行了n^2个基本操作; 程序一的渐进时间复杂度低,因此更优。 复杂度分析的常用符号 - 若存在两个正常数c和n0,对任意的 n > n0 都有 |T(n)|<=c|f(n)|,则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。 - T(n)的增长速度不会比f(n)差。 - 大O表示法(big-Oh notation)表示的是运行时间的上限。 - 小o表示法,表示这个上限是“松”的。 简化法则 - 简化的方法是忽略常数和低次项,如 3n^4 + 8n^2 + n + 2 = O(n^4) 复杂度的等级 - 多项式算法 - 它的运行时间随着规模的扩大增长不大,因此叫做有效算法; - 指数级算法 - 运行时间增长很快,不是有效算法。 - 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性 - 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构 - n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法(如二级检索),分阶段算法(如二分图匹配的 Hopcroft 算法),或者待定参数的算法。a是最后解出的最优参数。 时空辩证关系 - 时间换空间 - 常用方法是重复计算 - 空间换时间 - 常用方法是预处理 P类问题和NP问题 - 如果一个问题可以在多项式时间内被确定机解决,则它属于 P 类问题 - 如果它可以在多项式时间内被非确定机解决,则它属于 NP 类问题 NP完全(NPC)问题 - 满足: - 属于NP - NP 中的每个问题都可以使用多项式归约到它 Monte-Carlo算法、RP类问题 - 如果一个问题存在一个随机算法,使得它有50%以上的概率得到期望的结果,那么这个问题属于RP类,该算法称为 Monte-Carlo
1回应 2011-02-01 13:42
-
康桥语冰 (夜深忽梦少年事)
个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟 对于编程能力的提高也没有想象中的高 看得出来作者都是竞赛和学术的大牛型人物,但是多数地方没有讲的非常清楚。(个人智商低,理解起来有些费力呀~) 本书作为题库,还是非常不错的 另外。。。。。。排版太糟糕了2011-08-31 09:43
-
1.1 编程的灵魂——数据结构+算法 = 程序 算法(algorithm)就是解决问题的方法或者过程。 数据结构(data structure)是数据的计算机表示和相应的一组操作。 时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。 程序一: fact = 1; for (int i = 1;i <= n; i++) fact *= i; 共执行了n个基本操作; 程序二: sum = 0; for (int i = 1; i <... (1回应)
2011-02-01 13:42 1人喜欢
1.1 编程的灵魂——数据结构+算法 = 程序 算法(algorithm)就是解决问题的方法或者过程。 数据结构(data structure)是数据的计算机表示和相应的一组操作。 时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。 程序一:
fact = 1; for (int i = 1;i <= n; i++) fact *= i;
共执行了n个基本操作; 程序二:
sum = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum += a[i][j];
执行了n^2个基本操作; 程序一的渐进时间复杂度低,因此更优。 复杂度分析的常用符号 - 若存在两个正常数c和n0,对任意的 n > n0 都有 |T(n)|<=c|f(n)|,则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。 - T(n)的增长速度不会比f(n)差。 - 大O表示法(big-Oh notation)表示的是运行时间的上限。 - 小o表示法,表示这个上限是“松”的。 简化法则 - 简化的方法是忽略常数和低次项,如 3n^4 + 8n^2 + n + 2 = O(n^4) 复杂度的等级 - 多项式算法 - 它的运行时间随着规模的扩大增长不大,因此叫做有效算法; - 指数级算法 - 运行时间增长很快,不是有效算法。 - 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性 - 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构 - n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法(如二级检索),分阶段算法(如二分图匹配的 Hopcroft 算法),或者待定参数的算法。a是最后解出的最优参数。 时空辩证关系 - 时间换空间 - 常用方法是重复计算 - 空间换时间 - 常用方法是预处理 P类问题和NP问题 - 如果一个问题可以在多项式时间内被确定机解决,则它属于 P 类问题 - 如果它可以在多项式时间内被非确定机解决,则它属于 NP 类问题 NP完全(NPC)问题 - 满足: - 属于NP - NP 中的每个问题都可以使用多项式归约到它 Monte-Carlo算法、RP类问题 - 如果一个问题存在一个随机算法,使得它有50%以上的概率得到期望的结果,那么这个问题属于RP类,该算法称为 Monte-Carlo
1回应 2011-02-01 13:42
-
康桥语冰 (夜深忽梦少年事)
个人觉得这本书并没有像书名一样令人对算法上升到艺术层次的感悟 对于编程能力的提高也没有想象中的高 看得出来作者都是竞赛和学术的大牛型人物,但是多数地方没有讲的非常清楚。(个人智商低,理解起来有些费力呀~) 本书作为题库,还是非常不错的 另外。。。。。。排版太糟糕了2011-08-31 09:43
-
1.1 编程的灵魂——数据结构+算法 = 程序 算法(algorithm)就是解决问题的方法或者过程。 数据结构(data structure)是数据的计算机表示和相应的一组操作。 时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。 程序一: fact = 1; for (int i = 1;i <= n; i++) fact *= i; 共执行了n个基本操作; 程序二: sum = 0; for (int i = 1; i <... (1回应)
2011-02-01 13:42 1人喜欢
1.1 编程的灵魂——数据结构+算法 = 程序 算法(algorithm)就是解决问题的方法或者过程。 数据结构(data structure)是数据的计算机表示和相应的一组操作。 时空开销增长 - 在算法设计出来以后直接对算法进行分析。估计它的时间效率和空间开销。 - 只关心在问题规模扩大时时空开销的增长情况。 程序一:
fact = 1; for (int i = 1;i <= n; i++) fact *= i;
共执行了n个基本操作; 程序二:
sum = 0; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) sum += a[i][j];
执行了n^2个基本操作; 程序一的渐进时间复杂度低,因此更优。 复杂度分析的常用符号 - 若存在两个正常数c和n0,对任意的 n > n0 都有 |T(n)|<=c|f(n)|,则称T(n)在集合O(f(n))中。记作T(n) = O(f(n))。 - T(n)的增长速度不会比f(n)差。 - 大O表示法(big-Oh notation)表示的是运行时间的上限。 - 小o表示法,表示这个上限是“松”的。 简化法则 - 简化的方法是忽略常数和低次项,如 3n^4 + 8n^2 + n + 2 = O(n^4) 复杂度的等级 - 多项式算法 - 它的运行时间随着规模的扩大增长不大,因此叫做有效算法; - 指数级算法 - 运行时间增长很快,不是有效算法。 - 包含 Ackermann 函数反函数的算法往往代表着算法使用了并查集或者利用了某函数的凹凸性 - 含 logn 的往往是用了递归、二分或者操作时间复杂度表达式含 logn 的数据结构 - n^(1/2) 或者用更“奇怪”的常数a作为指数的 O(n^a) 类算法的往往是多级算法(如二级检索),分阶段算法(如二分图匹配的 Hopcroft 算法),或者待定参数的算法。a是最后解出的最优参数。 时空辩证关系 - 时间换空间 - 常用方法是重复计算 - 空间换时间 - 常用方法是预处理 P类问题和NP问题 - 如果一个问题可以在多项式时间内被确定机解决,则它属于 P 类问题 - 如果它可以在多项式时间内被非确定机解决,则它属于 NP 类问题 NP完全(NPC)问题 - 满足: - 属于NP - NP 中的每个问题都可以使用多项式归约到它 Monte-Carlo算法、RP类问题 - 如果一个问题存在一个随机算法,使得它有50%以上的概率得到期望的结果,那么这个问题属于RP类,该算法称为 Monte-Carlo
1回应 2011-02-01 13:42
论坛 · · · · · ·
ACM Fighting~ | 来自star | 3 回应 | 2012-03-09 |
非常好的书 | 来自hehehehe | 2010-10-31 | |
当年还没有上市的时候,lrj 签名送的一本 | 来自雨寒月 | 3 回应 | 2010-08-07 |
微言大义 | 来自absolute | 2009-08-10 | |
这本书的资料还算比较全…… | 来自已注销 | 1 回应 | 2009-01-12 |
0 有用 ส้? 2007-05-13
讲的挺好
3 有用 BYVoid 2012-05-27
非常差勁,許多內容都是國家集訓隊作業
0 有用 轰小云@七汉字 2005-10-24
没下决心千万别看
0 有用 henix 2012-07-12
ACM经典用书
0 有用 仙道 2015-04-15
IOer必備
0 有用 Dan 2020-12-15
@2010-11-22 01:40:34 @2020-07-09 19:03:42
0 有用 [已注销] 2020-07-09
@2010-11-22 01:40:34
0 有用 不会飞的章鱼 2019-10-28
上大学时借的是一高中打过OI的朋友的书看完的
0 有用 咕噜丹vjudge 2019-03-07
黑皮书~
0 有用 p1rate 2018-09-27
看完感觉确实要去学一学语文了😅😅😅